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.

Big M Method

PYQs

Graphical Method

1) Use graphical method to solve the linear programming problem.
Maximize $Z = 3 x_{1} + 2 x_{2}$
subject to
$x_{1} - x_{2} \geq 1$ ,
$x_{1} + x_{2} \geq 3$ and
$x_{1}, x_{2}, x_{3} \geq 0$

[2019, 10M]

2) Using graphical method, find the maximum value of

2 x + y

subject to

$4 x + 3 y \leq 12$ $4 x + y \leq 8$ $4 x - y \leq 8$ $x, y \geq 0$

[2017, 10M]

3) Find the maximum value of

5 x + 2 y

with constraints

$x + 2 y \geq 1$ , $2 x + y \leq 1$ $x \geq 0$ and $y \geq 0$

by graphical method.

[2016, 10M]

4) Maximize

z = 2 x_{1} + 3 x_{2} + 6 x_{3}

subject to

$2 x_{1} + x_{2} + x_{3} \leq 5$ $3 x_{2} + 2 x_{3} \leq 6$ $x_{1} \geq 0$ , $x_{2} \geq 0$ , $x_{3} \geq 0$

Is the optimal solution unique? Justify your answer.

[2016, 20M]

5) Solve graphically:

Maximize
$Z = 6 x_{1} + 5 x_{2}$ ,
subject to:
$2 x_{1} + x_{2} \leq 216$
$x_{1} + x_{2} \leq 11$
$x_{1} + 2 x_{2} \geq 6$ $5 x_{1} + 6 x_{2} \leq 90$
$x_{1} x_{2} \geq 0$

[2014, 10M]

6) Maximize $z = 2 x_{1} + 3 x_{2} - 5 x_{3}$ ,

subject to $x_{1} + x_{2} + x_{3} = 7$

and $2 x_{1} - 5 x_{2} + x_{3} \geq 10$ , $x_{i} \geq 0$

[2013, 10M]

7) Minimize $z = 5 x_{1} - 4 x_{2} + 56 x_{3} - 8 x_{4}$ ,

subject to the constraints

x_{1} + 2 x_{2} - 2 x_{3} + 4 x_{4} \leq 40

2 x_{1} - x_{2} + x_{3} + 2 x_{4} \leq 8

$4 x_{1} - 2 x_{2} + x_{3} - x_{4} \leq 10$ ,

x_{i} \geq 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 = 3 x_{1} + 5 x_{2} + 4 x_{3}$ subject to:

$2 x_{1} + 3 x_{2} \leq 8$ ,
$3 x_{1} + 2 x_{2} + 4 x_{3} \leq 15$ ,
$2 x_{2} + 5 x_{3} \leq 10$ ,
$x_{i} \geq 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
$x_{1} + 2 x_{2} - 3 x_{3} + x_{4} = 4$ ,
$x_{1} + 2 x_{2} + x_{3} + 2 x_{4} = 4$ and
$x_{1}$ , $x_{2}$ , $x_{3}$ , $x_{4} \geq 0$

[2019, 15M]

2) Solve the following linear programming problem by simplex method. Maximize $z = 3 x_{1} + 5 x_{2} + 4 x_{3}$ , subject to:
$2 x_{2} + 3 x_{2} \leq 8$
$2 x_{1} + 5 x_{2} \leq 10$
$3 x_{1} + 2 x_{2} + 4 x_{3} \leq 15 x_{3}$
$x_{1}, x_{2}, x_{3} \geq 0$

[2017, 20M]

3) Find the initial basic feasible solution of the following transportation problem using Vogel’s approximation methods and find the cost.
$D e s t i n a t i o n s$ $\begin{array}{cccccc} D_{1} & D_{2} & D_{3} & D_{4} & D_{5} \\ O_{1} & 4 & 7 & 0 & 3 & 6 & 14 \\ O_{2} & 1 & 2 & - 3 & 3 & 8 & 9 \\ O_{3} & 3 & - 1 & 4 & 0 & 5 & 17 \\ 8 & 3 & 8 & 13 & 8 \end{array}$

D e m a n d

[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 = 2 x_{1} - 4 x_{2} + 5 x_{3}$ ,

subject to:

$x_{1} + 4 x_{2} - 2 x_{3} \leq 2$
$- x_{1} + 2 x_{2} + 3 x_{3} \leq 1$
$x_{1}, x_{2}, x_{3} \geq 0$

[2015, 20M]

5) Find all optimal solutions of the following linear programming problem by the simplex method.
Maximize
$Z = 30 x_{1} + 24 x_{2}$ ,
subject to:
$5 x_{1} + 4 x_{2} \leq 200$
$x_{1} \leq 32$
$x_{2} \leq 40$
$x_{1} x_{2} \geq 0$

[2014, 20M]

6) Solve by simplex method. Maximize
$Z = 5 x_{1} + x_{2}$ ,
subject to constraints:
$3 x_{1} + 5 x_{2} \leq 15$
$5 x_{1} + 2 x_{2} \leq 10$
$x_{1}$ , $x_{2} \geq 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 = 4 x + 3 y$ , subject to:
$x + y \leq 4$
$- x + y \leq 2$
$x, y \leq 0$

[2007, 12M]

8) Solve the following by Simplex method:
Maximize $u = x + y$ ,
subject to:
$- x + y \leq 1$
$x - 2 y \leq 4$
$x, y \geq 0$

[2007, 30M]

9) Use the simplex method to solve the problem.
Maximize $u = 2 x + 3 y$ , subject to:
$- 2 x + 3 y \leq 2$
$3 x + 2 y \leq 5$
$x, y \geq 0$

[2006, 30M]

10) Use the simplex method to solve the problem. Maximize $Z = 5 x_{1} + 2 x_{2}$ , subject to:
$6 x_{1} + x_{2} \geq 12$
$4 x_{1} + 3 x_{2} \geq 12$
$x_{1} + 2 x_{2} \geq 4$
$x_{1}$ , $x_{2} \geq 0$

[2005, 30M]

11) Use simplex method to solve the linear programming problem.
Maximize
$Z = 3 x_{1} + 2 x_{2}$ ,
subject to:
$x_{1} + x_{2} \leq 4$
$x_{1} - x_{2} \leq 2$
$x_{1}$ , $x_{2} \geq 0$

[2004, 12M]

12) An animal feed company must produce 200 $k g$ of a mixture consisting of ingredients $X_{1}$ and $X_{2}$ daily. $X_{1}$ costs Rs 3 per Kg and $X_{2}$ costs Rs 8 per Kg. No more than 80 Kg of $X_{1}$ can be used, and at least 60 Kg of $X_{2}$ must be used. Formulate a linear programming model of the problem and use Simplex method to determine the ingredients $X_{1}$ and $X_{2}$ to be used to minimize cost.

[2003, 15M]

13) Using Simplex method,
Maximize $Z = 45 x_{1} + 80 x_{2}$ ,
subject to:
$5 x_{1} + 20 x_{2} \leq 400$
$10 x_{1} + 15 x_{2} \leq 450$
$x_{1}$ , $x_{2} \geq 0$

[2002, 12M]

14) Using simplex method,
Maximize $Z = 5 x_{1} + 3 x_{2}$ ,
subject to:
$x_{1} + x_{2} \leq 2$
$5 x_{1} + 2 x_{2} \leq 10$
$3 x_{1} + 8 x_{2} \leq 12$
$x_{1}$ , $x_{2} \geq 0$

[2002, 15M]

Big M Method

1) Solve the following linear programming problem by Big M-method and show that the problem has finite optimal solutions. Also, find the value of the objective function:
Minimize $z = 3 x_{1} + 5 x_{2}$ subject to $x_{1} + 2 x_{2} \geq 8$
$3 x_{1} + 2 x_{2} \geq 12$ ,
$5 x_{1} + 6 x_{2} \geq 60$ ,
$x_{1}, x_{2} \geq 0$

[2018, 20M]

< Previous Next >