Graphical and Simplex Methods
We will cover following topics
Graphical Method
Graphical method of linear programming is used to solve problems by finding the highest or lowest point of intersection between the objective function line and the feasible region on a graph.
The graphical method can be broken down into the following 7 steps:
Step 1: Define Constraints
Step 2: Define the Objective Function
Step 3: Plot the constraints on a graph paper
Step 4: Highlight the feasible region on the g
Step 5: Plot the objective function on the graph
Step 6: Find the optimum point
Step 7: Find the coordinates of the optimum point
Simplex Method
Step 1: Insert slack variables and find slack equations.
Step 2: Rewrite the objective function and put it below the slack equations.
Step 3: Write the initial simplex tableau.
Step 4: Find the pivot element by finding the most negative indicator in last row and using the smallest quotient rule.
Step 5: Perform the pivot operation.
Step 6: Are there any more negative indicators in the last row? If Yes, Go to Step 4, Else the maximum has been reached.
PYQs
Graphical Method
1) Use graphical method to solve the linear programming problem.
Maximize Z=3x1+2x2
subject to
x1−x2≥1,
x1+x2≥3 and
x1,x2,x3≥0
[2019, 10M]
2) Using graphical method, find the maximum value of
2x+ysubject to
4x+3y≤12 4x+y≤8 4x−y≤8 x,y≥0
[2017, 10M]
3) Find the maximum value of
5x+2ywith constraints
x+2y≥1, 2x+y≤1 x≥0 and y≥0
by graphical method.
[2016, 10M]
4) Maximize
z=2x1+3x2+6x3subject to
2x1+x2+x3≤5 3x2+2x3≤6 x1≥0, x2≥0, x3≥0
Is the optimal solution unique? Justify your answer.
[2016, 20M]
5) Solve graphically:
Maximize
Z=6x1+5x2,
subject to:
2x1+x2≤216
x1+x2≤11
x1+2x2≥6
5x1+6x2≤90
x1x2≥0
[2014, 10M]
6) Maximize z=2x1+3x2−5x3,
subject to x1+x2+x3=7
and 2x1−5x2+x3≥10, xi≥0
[2013, 10M]
7) Minimize z=5x1−4x2+56x3−8x4,
subject to the constraints
x1+2x2−2x3+4x4≤40 2x1−x2+x3+2x4≤84x1−2x2+x3−x4≤10,
xi≥0[2013, 30M]
8) For each hour per day that Ashok studies mathematics, it yields him 10 marks and for eaach hour that he studies physics, it yields him 5 marks. He can study at most 14 hours a day and he must get at least 40 marks in each. Determine graphically how many hours a day he should study mathematics and physics each, in order to maximize his marks?
[2012, 12M]
9) Maximize: Z=3x1+5x2+4x3 subject to:
2x1+3x2≤8,
3x1+2x2+4x3≤15,
2x2+5x3≤10,
xi≥0
[2009, 30M]
Simplex Method
1) Solve the linear programming problem using Simplex method.
Maximize $Z=x_1+2x_2-3x_3-2x_4$
subject to
x1+2x2−3x3+x4=4,
x1+2x2+x3+2x4=4 and
x1, x2, x3, x4≥0
[2019, 15M]
2) Solve the following linear programming problem by simplex method. Maximize z=3x1+5x2+4x3, subject to:
2x2+3x2≤8
2x1+5x2≤10
3x1+2x2+4x3≤15x3
x1,x2,x3≥0
[2017, 20M]
3) Find the initial basic feasible solution of the following transportation problem using Vogel’s approximation methods and find the cost.
Destinations
D1D2D3D4D5O14703614O212−3389O33−140517838138
[2017, 15M]
4) Solve the following linear programming problem by the simplex method. Write its dual. Also, write the optimal solution of the dual from the optimal table of the given problem:
Maximize Z=2x1−4x2+5x3,
subject to:
x1+4x2−2x3≤2
−x1+2x2+3x3≤1
x1,x2,x3≥0
[2015, 20M]
5) Find all optimal solutions of the following linear programming problem by the simplex method.
Maximize
Z=30x1+24x2,
subject to:
5x1+4x2≤200
x1≤32
x2≤40
x1x2≥0
[2014, 20M]
6) Solve by simplex method. Maximize
Z=5x1+x2,
subject to constraints:
3x1+5x2≤15
5x1+2x2≤10
x1, x2≥0
[2011, 12M]
7) Put the following in slack form and describe which of the variables are 0 at each of the vertices of the constraint set and hence determine the vertices algebraically:
Maximize Z=4x+3y, subject to:
x+y≤4
−x+y≤2
x,y≤0
[2007, 12M]
8) Solve the following by Simplex method:
Maximize u=x+y,
subject to:
−x+y≤1
x−2y≤4
x,y≥0
[2007, 30M]
9) Use the simplex method to solve the problem.
Maximize u=2x+3y, subject to:
−2x+3y≤2
3x+2y≤5
x,y≥0
[2006, 30M]
10) Use the simplex method to solve the problem. Maximize Z=5x1+2x2, subject to:
6x1+x2≥12
4x1+3x2≥12
x1+2x2≥4
x1, x2≥0
[2005, 30M]
11) Use simplex method to solve the linear programming problem.
Maximize
Z=3x1+2x2,
subject to:
x1+x2≤4
x1−x2≤2
x1, x2≥0
[2004, 12M]
12) An animal feed company must produce 200 kg of a mixture consisting of ingredients X1 and X2 daily. X1 costs Rs 3 per Kg and X2 costs Rs 8 per Kg. No more than 80 Kg of X1 can be used, and at least 60 Kg of X2 must be used. Formulate a linear programming model of the problem and use Simplex method to determine the ingredients X1 and X2 to be used to minimize cost.
[2003, 15M]
13) Using Simplex method,
Maximize Z=45x1+80x2,
subject to:
5x1+20x2≤400
10x1+15x2≤450
x1, x2≥0
[2002, 12M]
14) Using simplex method,
Maximize Z=5x1+3x2,
subject to:
x1+x2≤2
5x1+2x2≤10
3x1+8x2≤12
x1, x2≥0
[2002, 15M]