Class 12 Mathematics Linear Programming Problems Notes and Important Questions

Class 12 Linear Programming Problems Notes (Mathematics)

Linear Programming Exercise 17.1 . 1. Reformulate the following LP problem into standard form. a) Maximize P = 20x + 30y s.t. 3x + y Soln: Let r and s be non-negative slack variable 3x + y + r.1 + s.0 + p.0 = 15 x + 3y + r.0 + s.1 + p.0 = 12 – 20x – 30y + r.0 + s.0 + p.1 = 0 b) Maximize F = 7x + 5y s.t. 4x + 3y Soln: Let r and s be non-negative slack variable 4x + 3y + r.1 + s.0 + 2x + y + r.0 + s.1 + p.0 = 12 – 7x – 5y + r.0 + s.0 + p.1 = 0 2. Using simplex method, find the optimal solutions of the following LP problems. a) Maximize Z = 2x + y s.t. x + Soln: Let r and s be non-negative x + 2y + r.1 + s.0 + z.0 = x + y + r.0 + s.1 + z.0 = 6 – 2x – y + r.0 + s.0 + z.1 = 0 The initial simplex tableau with the coefficients of the objective function in the last row is, B.V. x r 1 s – 2 Here, the last row contain negative entry. So, th most negative entry. So, the first column is pivot column and first row is pivot row. So, 1 is pivot element. Applying R1 R1 – R B.V. x y 0 s 1

Since all entries in the last row are non  max. Z = 12 when x = 6, y = 0 such that Z = 2x + y  12 = Reformulate the following LP problem into standard form. Maximize P = 20x + 30y s.t. 3x + y ≤ 15, x + 3y ≤ 12, x, y ≥ 0 negative slack variables, then the standard form of given LPP 3x + y + r.1 + s.0 + p.0 = 15 x + 3y + r.0 + s.1 + p.0 = 12 30y + r.0 + s.0 + p.1 = 0 Maximize F = 7x + 5y s.t. 4x + 3y ≤ 48, 2x + y ≤ 20, x, y ≥ 0 negative slack variables, then the standard form of given LPP 4x + 3y + r.1 + s.0 + p.0 = 48 2x + y + r.0 + s.1 + p.0 = 12 5y + r.0 + s.0 + p.1 = 0 Using simplex method, find the optimal solutions of the following LP problems. Maximize Z = 2x + y s.t. x + 2y ≤ 10, x + y ≤ 6, negative slack variables, then the standard form of given LPP y + r.1 + s.0 + z.0 = 10 y + r.0 + s.1 + z.0 = 6 y + r.0 + s.0 + z.1 = 0 The initial simplex tableau with the coefficients of the objective function in the last row is, y r s Z RHS 2 1 0 0 10 1 0 1 0 6 – 1 0 0 1 0 Here, the last row contain negative entry. So, the solution Z = 0 is not optimal and most negative entry. So, the first column is pivot column and first row is pivot row. So, 1 is R2 and R3 R3 + 2R2, we get y r s Z RHS 1 1 -1 0 1 0 1 0 1 0 2 1 12 Since all entries in the last row are non-negative, so the solution is optimal. max. Z = 12 when x = 6, y = 0 such that 12 = 2 × 6 + 0  12 = 12(true) given LPP is given LPP is Using simplex method, find the optimal solutions of the following LP problems. given LPP is The initial simplex tableau with the coefficients of the objective function in the last row is, RHS Ratio 10 10/1 = 10 6 6/1 = 6 0 6 < 10 not optimal and – 2 is the most negative entry. So, the first column is pivot column and first row is pivot row. So, 1 is RHS Ratio

negative, so the solution is optimal.

b) Maximize Z = x + 3y s.t. x + y Soln: Let r and s be non-negative slack variable, then the x + y + r.1 + s.0 + z.0 = 5 3x + y + r.0 + s.1 + z.0 = – x – 3y + r.0 + s.0 + z.1 = 0 The initial simplex tableau with the coefficients of the objective function in the last row is, B.V. x r 1 s 3 – 1 Here, the last row contain negative entry. So, most negative entry. So, the first column is pivot column and first row is pivot row. So, 1 is pivot element. Applying R2 R2 – R B.V. x y 1 s 2

Since all entries in the last row are non  max. Z = 15 when x = 0, y = 5 such that Z = x + 3y c) Maximize F = 5x + 12y s.t. 3x + y Soln:Let r and s be non-negative slack variable 3x + y + r.1 + s.0 + x + 2y + r.0 + s.1 + – 5x – 12y + r.0 + s.0 + The initial simplex tableau with the coefficients of the objective function in the last row is, B.V. x r 3 s 1 – 5 Here, the last row contain negative entry. So, 12 is the most negative entry. So, the So, 2 is pivot element. Applying R2R2 2 , we get B.V. x y 3 s 1/2 – 5 Linear Programming Computational Methods Maximize Z = x + 3y s.t. x + y ≤ 5, 3x + y ≤ 15, negative slack variable, then the standard form of given LPP is x + y + r.1 + s.0 + z.0 = 5 3x + y + r.0 + s.1 + z.0 = 15 3y + r.0 + s.0 + z.1 = 0 simplex tableau with the coefficients of the objective function in the last row is, y r s Z RHS 1 0 0 1 0 1 0 15 – 3 0 0 1 Here, the last row contain negative entry. So, Z = 0 is not the optimal solution and most negative entry. So, the first column is pivot column and first row is pivot row. So, 1 is R1 and R3 R3 + 3R1, we get y r s Z RHS 1 1 0 0 0 -1 1 0 10 0 3 0 1 15 Since all entries in the last row are non-negative, so the solution is optimal. max. Z = 15 when x = 0, y = 5 such that  15 = 0 + 3  5  15 Maximize F = 5x + 12y s.t. 3x + y ≤ 12, x + 2y ≤ 12, negative slack variables, then the standard form of given LPP 3x + y + r.1 + s.0 + F.0 = 12 x + 2y + r.0 + s.1 + F.0 = 12 12y + r.0 + s.0 + F.1 = 0 initial simplex tableau with the coefficients of the objective function in the last row is, y r s F RHS 1 1 0 0 12 0 1 0 12 – 12 0 0 1 Here, the last row contain negative entry. So, F = 0 is not the optimal solution 12 is the most negative entry. So, the second column is pivot column and first row is pivot row. So, 2 is pivot element. , we get y r s F RHS 1 1 0 0 12 1 0 1/2 0 – 12 0 0 1 Linear Programming *349* Computational Methods standard form of given LPP is simplex tableau with the coefficients of the objective function in the last row is, RHS Ratio 5 5/1 = 5 15 15/1 = 15 0 6 < 10 optimal solution and – 3 is the most negative entry. So, the first column is pivot column and first row is pivot row. So, 1 is RHS Ratio 5 ….. 10 …..

negative, so the solution is optimal.  15 = 15(true) given LPP is initial simplex tableau with the coefficients of the objective function in the last row is, RHS Ratio 12 12/1 = 12 12 12/2 = 6 0 6 < 12 the optimal solution. In the last row – column is pivot column and first row is pivot row. RHS Ratio 12 …. 6 ….

*350* Solution Manual to Basic Mathematics Linear Programming Applying R1 R1 – R B.V. x y 5/2 s 1/2

Since all entries in the last row are non  max. F = 72 when x = 0, y = 6 F = 5x + 12y d) Max. Z = 4x – 6y s.t. 2x Soln: Let r and s be non-negative slack variable 2x – 3y + r.1 + s.0 + x + y + r.0 + s.1 + – 4x – 6y + r.0 + s.0 + The initial simplex tableau with the coefficients of the objective function in the last row is, B.V. x r s 1 – 4 Here, the last row contain negative entry. So, most negative entry. So, the first column is pivot column and first row is pivot element. Applying R1R1 2 , we get B.V. x x 1 s 1 – 4 Applying R2 R2 – R B.V. x x 1 s 0

Since all entries in the last row are non  max. Z = 16 whe Z = 4x - 6y e) Maximize U = 25x + 45y s.t. x + 3y Soln: Let r and s be non-negative slack variable x + 3y + r.1 + s.0 + 2x + 3y + r.0 + s.1 + – 25x – 45y + r.0 + s.0 + Solution Manual to Basic Mathematics R2 and R3 R3 + 12R2, we get y r s F RHS 0 1 -1/2 0 1 0 1/2 0 0 0 6 1 72 Since all entries in the last row are non-negative, so the solution is optimal. max. F = 72 when x = 0, y = 6 such that  72 = 0 + 126  72 = 72 (true) 6y s.t. 2x – 3y ≤ 8, x + y ≤ 24, negative slack variables, then the standard form of given LPP 3y + r.1 + s.0 + Z.0 = 8 x + y + r.0 + s.1 + Z.0 = 24 y + r.0 + s.0 + Z.1 = 0 The initial simplex tableau with the coefficients of the objective function in the last row is, y r s Z RHS -3 1 0 0 1 0 1 0 24 6 0 0 1 Here, the last row contain negative entry. So, Z = 0 is not the optimal solution and most negative entry. So, the first column is pivot column and first row is pivot row , we get y r s Z RHS -3/2 1/2 0 0 1 0 1 0 24 6 0 0 1 R1 and R3 R3 + 4R1, we get y r s Z RHS -3/2 1/2 0 0 5/2 -1/2 1 0 20 0 2 0 1 16 Since all entries in the last row are non-negative, so the solution is optimal. = 16 when x = 4, y = 0 such that  16 = 44 – 0  16 = 16 (true) Maximize U = 25x + 45y s.t. x + 3y ≤ 21, 2x + 3y ≤ 24, negative slack variables, then the standard form of given LPP x + 3y + r.1 + s.0 + U.0 = 21 2x + 3y + r.0 + s.1 + U.0 = 24 45y + r.0 + s.0 + U.1 = 0 RHS Ratio 6 12 6 6

negative, so the solution is optimal. 72 = 72 (true) given LPP is The initial simplex tableau with the coefficients of the objective function in the last row is, RHS Ratio 8 8/2 = 4 24 24/1 = 24 0 4 < 24 is not the optimal solution and – 4 is the pivot row hence 2 is RHS Ratio 4 ….. 24 …..

RHS Ratio 8 ….. 20 …..

negative, so the solution is optimal. 16 = 16 (true) given LPP is

The initial simplex tableau with the coefficients of the objective function in the last row is, B.V. x r 1 s 2 – 25 Here, the last row contain negative entry. So, most negative entry, the second pivot element. Applying R1R1 3 , we get B.V. x y 1/3 s 2 – 25 Applying R2 R2 – 3R B.V. x y 1/3 s – 10 Here, the last row still contains negative value second row is pivot row hence Applying R1 R1 – 1/3R B.V. x y 0 x 1

Since all entries in the last row are non  max. U = 345 when x = 3, y = 6 U = 25x + 45y  345 = 345 (true) f) Maximize P = 8x + 10y s.t. x + 2y Soln: Let r and s be non-negative slack variable x + 2y + r.1 + s.0 + p.0 = 30 2x + 2y + r.0 + s.1 + p.0 = 40 – 8x – 10y + r.0 + s.0 + p.1 The initial simplex tableau with the coefficients of the objective function in the last row is, B.V. x r 1 s 2 – 8 Linear Programming Computational Methods The initial simplex tableau with the coefficients of the objective function in the last row is, y r s U RHS 1 0 0 21 3 0 1 0 24 –45 0 0 1 Here, the last row contain negative entry. So, U = 0 is not the optimal solution , the second column is pivot column and first row is pivot row , we get y r s U RHS 1 1/3 0 0 3 0 1 0 24 –45 0 0 1 3R1 and R3 R3 + 45R1, we get y r s U RHS 1 1/3 0 0 0 –1 1 0 0 15 0 1 315 row still contains negative value – 10. So, the first column is pivot column and second row is pivot row hence 1 is pivot element. 1/3R2 and R3 R3 + 10R2, we get y r s U RHS 1 2/3 –1/3 0 0 -1 1 0 0 5 10 1 345 Since all entries in the last row are non-negative, so the solution is optimal. = 345 when x = 3, y = 6 such that  345 = 253 (true) Maximize P = 8x + 10y s.t. x + 2y ≤ 30, 2x + 2y ≤ 40, negative slack variables, then the standard form of given LPP x + 2y + r.1 + s.0 + p.0 = 30 2x + 2y + r.0 + s.1 + p.0 = 40 10y + r.0 + s.0 + p.1 = 0 The initial simplex tableau with the coefficients of the objective function in the last row is, y r s P RHS 1 0 0 30 2 0 1 0 40 –10 0 0 1 Linear Programming *351* Computational Methods The initial simplex tableau with the coefficients of the objective function in the last row is, RHS Ratio 21 21/3 = 7 24 24/3 = 8 0 7 < 8 not the optimal solution. Since – 4 is the column is pivot column and first row is pivot row hence 3 is RHS Ratio 7 …….. 24 …….. 0 …… RHS Ratio 7 7/1/3 = 21 3 3/1 = 3 315 3 < 21 n is pivot column and RHS Ratio 6 ………. 3 ………. 345 ……. negative, so the solution is optimal. 3 +456 given LPP is The initial simplex tableau with the coefficients of the objective function in the last row is, RHS Ratio 30 30/2 = 15 40 40/2 = 20 0 15 < 20

*352* Solution Manual to Basic Mathematics Linear Programming Here, the last row contain negative entry. So, most negative entry, the second pivot element. Applying R1R1 2 , we get B.V. x y 1/2 s 2 – 8 Applying R2 R2 – 2R B.V. x y 1/2 s – 3 Here, the last row still contains negative value second row is pivot row hence Applying R1 R1 – 1/2R B.V. x y 0 s 1

Since all entries in the last row are non  max. P = 180 when x = 10, y = 10 P = 8x + 10y g) Maximize F = 5x1 + 3x Soln: Let r and s be non-negative slack variable 2x1 + x2 + r.1 + s.0 + x1 + 2x2 + r.0 + s.1 + – 5x1 – 3x2 + r.0 + s.0 + The initial simplex tableau with the coefficients of the objective function in the last row is, B.V. x1 R S 1 – 5 Here, the last row contain negative entry. So, most negative entry in the last row, hence 2 is pivot element. Solution Manual to Basic Mathematics Here, the last row contain negative entry. So, P = 0 is not the optimal solution most negative entry, the second column is pivot column and first row is pivot row , we get y r s P RHS 1 1/2 0 0 15 2 0 1 0 40 –10 0 0 1 2R1 and R3 R3 + 10R1, we get y r s P RHS 1 1/2 0 0 15 0 –1 1 0 10 0 5 0 1 150 Here, the last row still contains negative value – 3. So, the first column is pivot column second row is pivot row hence 1 is pivot element. 1/2R2 and R3 R3 + 3R2, we get y r s P RHS 1 1 –1/2 0 10 0 -1 1 0 10 0 2 3 1 180 Since all entries in the last row are non-negative, so the solution is optimal. = 180 when x = 10, y = 10 such that  180 = 810 +1010  180 = 180 (true) + 3x2 s.t. 2x1 + x2 ≤ 40, x1 + 2x2 ≤ 50, negative slack variables, then the standard form of given LPP + r.1 + s.0 + F.0 = 40 + r.0 + s.1 + F.0 = 50 + r.0 + s.0 + F.1 = 0 initial simplex tableau with the coefficients of the objective function in the last row is, x2 r s F RHS 1 1 0 0 40 2 0 1 0 50 –3 0 0 1 Here, the last row contain negative entry. So, F = 0 is not the optimal solution in the last row, the first column is pivot column and first row is pivot row 2 is pivot element. is not the optimal solution. Since – 10 is the column is pivot column and first row is pivot row hence 2 is RHS Ratio 15 …….. 40 …….. 0 …… RHS Ratio 15 15/1/2 =

10 10/1 = 10 150 10 < 30 the first column is pivot column and RHS Ratio 10 ………. 10 ………. 180 ……. negative, so the solution is optimal.  180 = 180 (true) given LPP is initial simplex tableau with the coefficients of the objective function in the last row is, RHS Ratio 40 40/2 = 20 50 50/1 = 50 0 20 < 50 not the optimal solution. Since – 5 is the the first column is pivot column and first row is pivot row

Applying R1R1 2 , we get B.V. x1 x1 1 S 1 – 5 Applying R2 R2 – R B.V. x1 x1 1 S 0

Here, the last row still contains negative value and second row is pivot row hence Applying R2 R2 2/3, we get B.V. x1 x1 1 x2 0

Applying R1 R1 – 1/2 B.V. x1 x1 1 x2 0

Since all entries in the last row are non  max. F = 110 when x F = 5x1+3x2 h) Maximize C = 7x + 5y s.t. 4x + 3y Soln: Let r and s be non-negative slack variable 4x + 3y + r.1 + s.0 + 2x + y + r.0 + s.1 + – 7x – 5y + r.0 + s.0 + The initial simplex tableau with the coefficients of the objective function in the last row is, B.V. x r 4 s – 7 Here, the last row contain negative entry. So, most negative entry in the last row row hence 2 is pivot element. Applying R2R2 2 , we get B.V. x r 4 y 1 – 7 Linear Programming Computational Methods , we get x2 r s F RHS 1/2 1/2 0 0 20 2 0 1 0 50 –3 0 0 1 R1 and R3 R3 + 5R1, we get x2 r s F RHS 1/2 1/2 0 0 20 3/2 -1/2 1 0 30 -1/2 5/2 0 1 100 still contains negative value – 1/2. So, the second column is pivot column and second row is pivot row hence 3/2 is pivot element. 2/3, we get x2 r s F RHS 1/2 1/2 0 0 20 1 -1/3 2/3 0 20 -1/2 5/2 0 1 100 1/2 R1 and R3 R3 + 1/2 R2, we get x2 r s F RHS 0 2/3 -1/3 0 10 1 -1/3 2/3 0 20 0 7/3 1/3 1 110 Since all entries in the last row are non-negative, so the solution is optimal. max. F = 110 when x1 = 10, x2 = 20 such that  110 = 510 +320  110 = 110 (true) Maximize C = 7x + 5y s.t. 4x + 3y ≤ 48, 2x + y ≤ 20, negative slack variables, then the standard form of given LPP 4x + 3y + r.1 + s.0 + C.0 = 48 2x + y + r.0 + s.1 + C.0 = 20 5y + r.0 + s.0 + C.1 = 0 itial simplex tableau with the coefficients of the objective function in the last row is, y r s C RHS 3 1 0 0 48 1 0 1 0 20 –5 0 0 1 Here, the last row contain negative entry. So, C = 0 is not the optimal solution in the last row, the first column is pivot column and second 2 is pivot element. , we get y r s C RHS 3 1 0 0 48 1/2 0 1/2 0 10 –5 0 0 1 Linear Programming *353* Computational Methods RHS Ratio 20 …….. 50 …….. 0 …… Ratio 20/1/2 = 40 30/3/2 = 20 20 < 40 column is pivot column RHS Ratio 20 ………. 20 ………. 100 ……. RHS Ratio 10 ………. 20 ………. 110 ……. negative, so the solution is optimal.  110 = 110 (true) given LPP is itial simplex tableau with the coefficients of the objective function in the last row is, RHS Ratio 48 48/4 = 12 20 20/2 = 10 0 10 < 12 the optimal solution. Since – 7 is the second row is pivot RHS Ratio 48 …….. 10 …….. 0 ……

*354* Solution Manual to Basic Mathematics Linear Programming Applying R1 R1 – 4R B.V. x r 0 y 1

Here, the last row still contains negative value first row is the pivot row hence Applying R2 R2 – 1/2R B.V. x x 0 y 1

Since all entries in the last row are non  max. C = 82 when x = 6, y = 8 such that C = 7x+5y i) Maximize Z = 5x + 5y s.t. 2x + y Soln: Let r and s be non-negative slack variable 2x + y + r.1 + s.0 + z.0 = 20 2x + 3y + r.0 + s.1 + z.0 = 24 – 5x – 5y + r.0 + s.0 + z.1 = 0 The initial simplex tableau with the coefficients of the objective function in the last row is, B.V. x r s 2 – 5 Here, the last row contain negative entry. So, most negative entry, the first column is pivot column and first row is pivot row element. Applying R1 1 R 2 , we get B.V. x x 1 s 2 – 5 Applying R2 R2 – 2R B.V. x x 1 s 0

Here, the last row still contains negative value and second row is the pivot row hence Solution Manual to Basic Mathematics 4R2 and R3 R3 + 7R2, we get y r s C RHS 1 -2 0 8 1/2 0 1/2 0 10 -3/2 0 7/2 1 70 Here, the last row still contains negative value-3/2. So, the second column is pivot column first row is the pivot row hence 1 is pivot element. 1/2R1 and R3 R3 + 3/2R1, we get y r s C RHS 1 1 –2 0 0 -1/2 3/2 0 0 3/2 1/2 1 82 Since all entries in the last row are non-negative, so the solution is optimal. . C = 82 when x = 6, y = 8 such that  82 = 76 +58  82 = 82 (true) Maximize Z = 5x + 5y s.t. 2x + y ≤ 20, 2x + 3y ≤ 24, negative slack variables, then the standard form of given LPP 2x + y + r.1 + s.0 + z.0 = 20 2x + 3y + r.0 + s.1 + z.0 = 24 5y + r.0 + s.0 + z.1 = 0 initial simplex tableau with the coefficients of the objective function in the last row is, y r s Z RHS 1 1 0 0 20 3 0 1 0 24 – 5 0 0 1 Here, the last row contain negative entry. So, Z = 0 is not the optimal solution most negative entry, the first column is pivot column and first row is pivot row , we get y r s Z RHS 1/2 1/2 0 0 10 3 0 1 0 24 – 5 0 0 1 2R1 and R3 R3 + 5R1, we get y r s Z RHS 1/2 1/2 0 0 10 -1/2 1 0 4 -5/2 5/2 0 1 50 Here, the last row still contains negative value – 5/2. So, the second column is pivot column and second row is the pivot row hence 2 is pivot element. RHS Ratio 8/1 = 8 10/1/2 = 20 8 < 20 column is pivot column and RHS Ratio 8 ………. 6 ………. 82 ……. negative, so the solution is optimal.  82 = 82 (true) given LPP is initial simplex tableau with the coefficients of the objective function in the last row is, RHS Ratio 20 20/2 = 10 24 24/2 = 12 0 10 < 12 is not the optimal solution. Since, – 5 is the most negative entry, the first column is pivot column and first row is pivot row hence 2 is pivot RHS Ratio 10 …….. 24 …….. 0 …… RHS Ratio 10/1/2 = 20 4/2 = 2 2 < 20 he second column is pivot column

Applying R2R2 2 , we get B.V. x x 1 y 0

Again, applying R1 B.V. x x 1 y 0

Since all entries in the last row are non  Max. Z = 55 when x Z = 5x +5y  55 = 5 j) Max Z = 5x1 + 7x2 subject to 2x Soln: Let r and s be non-negative slack variable 2x1 + 3x2 + r + 0.s + 0.z = 13 3x1+ 2x2 + 0.r + 0.s + 0.z = 12 -5x1 - 7x2 + 0.r + 0.s + 1.z = 0 The initial simplex tableau is given below: B.V. x1 r 2 s 3 -5 Here, the last row contain negative entry. So, most negative entry, the pivot element. Applying R2 2 R 3 , we get B.V. x1 x2 2/3 s 3 -5 Applying R2 R2 – 2R B.V. x1 x2

s 5

– 1

Here, the last row still contains negative value second row is the pivot row hence5/3 Linear Programming Computational Methods y R s Z RHS 1/2 ½ 0 0 10 1 -1/4 1/2 0 -5/2 5/2 0 1 50 R1 – 1/2R2 and R3 R3 + 5/2R2, we get y R s Z RHS 0 -3/4 -1/4 0 1 -1/2 1/2 0 0 5/4 5/4 1 55 Since all entries in the last row are non-negative, so the solution is optimal. 5 when x = 9, y = 2 such that  55 = 59 +52  55 = 55 (true) ubject to 2x1 + 3x2 13, 3x1 + 2x2 12, x1, x2 0 negative slack variables, then the standard form of given LPP + r + 0.s + 0.z = 13 + 0.r + 0.s + 0.z = 12 + 0.r + 0.s + 1.z = 0 The initial simplex tableau is given below: x2 r S Z RHS 1 0 0 13 2 0 1 0 12 -7 0 0 1 0 Here, the last row contain negative entry. So, Z = 0 is not the optimal solution most negative entry, the second column is pivot column and first row is pivot row 3 , we get x2 r S Z RHS 1 1/3 0 0 13/3 2 0 1 0 12 -7 0 0 1 0 2R1 and R3 R3 + 7R1, we get x2 r S Z RHS 1 1 3 0 0 13

0 2 3 1 0 10

0 7 3 0 1 91

Here, the last row still contains negative value – 1/3. So, the first column is pivot column and second row is the pivot row hence5/3 is pivot element. Linear Programming *355* Computational Methods RHS Ratio 10 …….. 2 …….. 50 …… RHS Ratio 9 ………. 2 ………. 55 ……. negative, so the solution is optimal. 55 = 55 (true) given LPP is Ratio 13/3 = 4.33 12/2 = 6 4.33 < 6 is not the optimal solution. Since, – 7 is the column is pivot column and first row is pivot row hence 3 is Ratio ……… ……… ……… Ratio 13/3 2/3 = 6.5 10/3 5/3 = 2 2 < 6.5 first column is pivot column and

*356* Solution Manual to Basic Mathematics Linear Programming Applying R13 5 × R1, we get B.V. x1 x2 r S Z RHS Ratio x2 2

1 1

0 0 13

…….. x1 1 0 - 2

0 2 ……….. -1

0 7

0 1 91

……… Applying R1 R1 - 2 3 R2 and R3 R3 + 1 3 R2, we get B.V. x1 x2 r s Z RHS x2 0 1 3/5 - 2/5 0 3 x1 1 0 - 2/5 3/5 0 2 0 0 11/5 1/5 1 31 Since all entries in the last row are non – negative, the solution of the given LP problem is optimal.  Max. Z = 31 when x1 = 2 and x2 = 3 such that Z = 5x1 + 7x2  31 = 5 2 + 73  31 = 31 (true) k) Maximize g = 15x + 12y s.t. 2x + 3y ≤ 21, 3x + 2y ≤ 24, Soln: Let r and s be non-negative slack variables, then the standard form of given LPP is 2x + 3y + r.1 + s.0 + g.0 = 20 2x + 3y + r.0 + s.1 + g.0 = 24 – 15x – 12y + r.0 + s.0 + g.1 = 0 The initial simplex tableau with the coefficients of the objective function in the last row is, B.V. x y r s g RHS Ratio r 2 3 1 0 0 21 21/2 = 10.5 s 3 2 0 1 0 24 24/3 = 8 – 15 – 12 0 0 1 0 8 < 10.5 Here, the last row contain negative entry. So, g = 0 is not the optimal solution. Since – 15 is the most negative entry in the last row, the first column is pivot column and second row is pivot row hence 2 is pivot element. Applying R2R2 3 , we get B.V. x y r s g RHS Ratio r 2 3 1 0 0 21 …….. x 1 2/3 0 1/3 0 8 …….. – 15 – 12 0 0 1 0 …… Applying R1 R1 – 2R2 and R3 R3 + 15R2, we get B.V. x y r s g RHS Ratio r 0 5/3 1 -2/3 0 5 5/5/3 = 3 x 1 2/3 0 1/3 0 8 8/2/3 = 12 0 – 2 0 5 1 120 3 < 12 Here, the last row still contains negative value – 2. So, the second column is pivot column and first row is the pivot row hence 5/3 is pivot element.

Linear Programming *357* Computational Methods Applying R13 5 R1, we get B.V. X y R s g RHS Ratio y 0 1 3/5 -2/5 0 3 …….. x 1 2/3 0 1/3 0 8 …….. 0 – 2 0 5 1 120 …… Applying R2 R2 – 2/3R1 and R3 R3 + 2R1, we get B.V. g y R s g RHS Ratio y 0 1 3/5 -2/5 0 3 ………. x 1 0 2/5 3/5 0 6 ………. 0 0 6/5 21/5 1 126 ……. Since all entries in the last row are non-negative, so the solution is optimal.  Max. g = 126 when x = 6, y = 3 such that g= 15x + 12y  126 = 15 6 + 12 3  126 = 126 (true) l) Maximize z = 10x1 + 12x2 s.t. 3x1 + x2 ≤ 12, x1 + 2x2 ≤ 14, Soln: Let r and s be non-negative slack variables, then the standard form of given LPP is 3x1 + x2 + 1.r + 0.s + 0.z = 12 x1 + 2x2 + 0.r + 0.s + 0.z = 14 - 10x1 - 12x2 + 0.r + 0.s + 1.z = 0 The initial simplex tableau is given below: B.V. x1 x2 R s z RHS Ratio r 3 1 1 0 0 12 12/1 = 12 s 1 2 0 1 0 14 14/2 = 7 – 10 – 12 0 0 1 0 7 < 12 Here, the last row contain negative entry. So, z = 0 is not the optimal solution. Since – 12 is the most negative entry in the last row, the second column is pivot column and second row is pivot row hence 2 is pivot element. Applying R2R2 2 , we get B.V. x1 x2 R s z RHS Ratio r 3 1 1 0 0 12 ……… x2 1/2 1 0 1/2 0 7 ……… – 10 – 12 0 0 1 0 ……… Applying R1 R1 – R2 and R3 R3 + 12R2, we get B.V. x1 x2 R s z RHS Ratio r 5/2 0 1 –1/2 0 5 5 5/2 = 2 x2 1/2 1 0 1/2 0 7 7 1/2 = 14 – 4 0 0 6 1 84 2 < 14 Here, the last row still contains negative value – 4. So, the first column is pivot column and first row is the pivot row hence 5/2 is pivot element. Applying R22 5 × R2, we get B.V. x1 x2 R S z RHS Ratio x1 1 0 2/5 –1/5 0 2 …….. x2 1/2 1 0 1/2 0 7 ……….. – 4 0 0 6 1 84 ………

*358* Solution Manual to Basic Mathematics Linear Programming Now, perform the operation R2 R2 – 1/2 R1 and R3 R3 + 4R1, B.V. x1 x2 R s P RHS x1 1 0 2/5 –1/5 0 2 x2 0 1 -1/5 3/5 0 6 0 0 8/5 26/5 1 92 Since all entries in the last row are non-negative, so the solution is optimal.  Max. z = 92 when x1 = 2, x2 = 6 such that z= 10x1 + 12x2  92 = 102 + 126  92 = 92 (true) 3. Find the dual problem corresponding to each of the following linear programming problems a) Maximize P = 8x + 36y s.t 2x + 6y  18 x + 6y  12 x, y  0 The augmented matrix form of given LPP is  The dual problem of given LPP is minimize P* = 18u + 12v s.t. 2u + v  8 6u + 6v  36  u + v  6 u, v  0. b) Maximize Z = 30 x + 20y s.t. 3x + y  15 x + 3y  12 x, y  0 The augmented matrix form of given LPP is  The dual problem of given LPP is Minimize Z* = 15u + 12 v s.t 3u + v  30 u + 3v  20 u, v  0

constraints objective function A =

A = T

constraints objective function A =

AT =

Linear Programming *359* Computational Methods c) Minimize W = 12x + 18y s.t. x + 2y  8 4x + 4y  24 x, y  0 The augmented matrix of given LP problem is  The dual of given LPP is Maximize W* = 8u + 24v s.t. u + 4v  12 2u + 4v  18 u, v  0 d) Minimize P = 32x + 84y s.t. x + 3y  50 2x + 4y  80 x, y  0 The augmented matrix of given LPP is  The dual of given LPP is Maximize P* = 50u + 80v s.t u + 2v  32 3u + 4v  84 u, v  0 4. Find the optimal solution of the following LP problems a) Minimize Z = 20x + 12y s.t 2x + 2y  20 5x + y  5 x, y  0 The augmented matrix of given LPP is  The dual of given LPP is

A =

A = T

A = 1

A = T

constraints objective function A =

AT =

*360* Solution Manual to Basic Mathematics Linear Programming Maximize Z* = 20u + 5v s.t. 2u + 5v  20 2u + v  12 u, v  0 Introducing the non-negative slack variables x and y, the LP problem is 2u + 5v + x = 20 2u + v + y = 12 20u + 5v = Z* i.e. 2u + 5v + x + 0.y + 0.Z* = 20 2u + v + 0.x + y + 0.Z* = 12 – 20u – 5v + 0.x + 0.y + Z* = 0 The initial simplex table of the problem is given by Basic variables u v x y Z* R.H.S. Ratio x 2 5 1 0 0 20 20

y 2 1 0 1 0 12 12

–20 –5 0 0 1 0 The most negative entry is last row is – 20  u-column is pivot column and the least ratio dividing R.H.S. by pivot column elements is 12 2 = 6  row second is pivot row. Hence 2 is the pivot entry. R2:1 2 R2 Basic variables u v x y Z* R.H.S. x 2 5 1 0 0 20 u 1 1 2 0 1 2 0 6 –20 –5 0 0 1 0 R1: R1 – 2R2, R3 : R3 + 20 R2 Basic variables u v x y z* R.H.S. x 0 4 1 –1 0 8 u 1 1 2 0 1 2 0 6 0 5 0 10 1 120 Since all entries in the last row are non-negative, the solution is optimal  Max. Z* = 120 at u = 6, v = 0  Min. Z = 120 when x = 0, y = 10 b) Minimize Z = 24x + 6y s.t. 3x + y  40 4x + 2y  25 x, y  0 The augmented matrix form of given LPP is

A =

A = T

Linear Programming *361* Computational Methods  The dual of given LPP is Maximize Z* = 40u + 25v s.t. 3u + 4v  24 u + 2v  6 u, v  0 Introducing the non-negative slack variables x and y, the LP problem is 3u + 4v + x = 24 u + 2v + y = 6 40u + 25v = Z* i.e. 3u + 4v + x + 0.y + 0Z* = 24 u + 2v + 0.x + y + 0.Z* = 6 – 40u – 25v + 0.x + 0.y + Z* = 0 The initial simplex table of the problem is given by Basic variables u v x y Z* R.H.S. Ratio x 3 4 1 0 0 24 3

y 1 2 0 1 0 6 1

–40 –25 0 0 1 0 The most negative entry is last row is – 40 u-column is pivot column and the least ratio dividing R.H.S. by pivot column element is 1 6  row second is pivot row. Hence 1 is the pivot entry. R1: R1 – 3R2, R3: R3 + 40 R2 Basic variables u v x y Z* R.H.S. x 0 - 2 1 –3 0 6 u 1 2 0 1 0 6 0 55 0 40 1 240 Since all entries in the last row are non-negative, the solution is optimal  Max. Z* = 240 at u = 6, v = 0  Min. Z = 240 when x = 0, y = 40 c) Minimize P = 6x + 20y s.t. 2x + y  6 – 3x + y  – 9 x, y  0 The given problem can be rewrite as Minimize P = 6x + 20y s.t. 2x + y  6 3x – y  9 x, y  0 The augmented matrix form of given LPP is

–1

A =

–1

A = T

*362* Solution Manual to Basic Mathematics Linear Programming  The dual of given LPP is Maximize P* = 6u + 9v s.t. 2u + 3v  6 u – v 20 u, v  0 Introducing the non-negative slack variables x and y, the LP problem is 2u + 3v + x = 6 u - v + y = 20 6u + 9v = P* i.e. 2u + 3v + x + 0.y + 0.P* = 6 u - v + 0.x + y + 0.P* = 20 – 6u – 9v + 0.x + 0.y + P* = 0 The initial simplex table of the problem is given by Basic variables u v x y P* R.H.S. Ratio x 2 3 1 0 0 6 6/3 y 1 -1 0 1 0 20 20/–1 –6 –9 0 0 1 0 The most negative entry is last row is – 9  v-column is pivot column and the only positive ratio dividing R.H.S. by pivot column element is 3 6  row first is pivot row. Hence 3 is the pivot entry. R1: 3 1 R1 Basic variables u v x y P* R.H.S. v 2/3 1 1/3 0 0 2 y 1 -1 0 1 0 20 – 6 –9 0 0 1 0 R2: R2 + R1, R3 : R3 + 9 R1 Basic variables u v x y P* R.H.S. v 3 2 1 3 1 0 0 2 y 3 5 0 3 1 1 0 22 0 0 3 0 1 18 Since all entries in the last row are non-negative, the solution is optimal  Max.P* = 18 at u = 0, v = 2  Min P = 18 at x = 3, y = 0 d) Minimize C = 8x + 10y s.t. x + 2y  3 2x + 2y  4 x, y  0 The augmented matrix of given LPP is

A =

A = T

Linear Programming *363* Computational Methods  The dual of given LPP is Maximize C* = 3u + 4v s.t. u + 2v  8 2u + 2v  10 u, v  0. Introducing the non-negative slack variables x and y, the LPP in standard form is u + 2v + x = 8 2u + 2v + y = 10 3u + 4v = C* i.e. u + 2v + x + 0.y + 0.C* = 8 2u + 2v + 0.x + y + 0.C* = 10 – 3u – 4v + 0.x + 0.y + C* = 0 The initial simplex table of the problem is given by Basic variables u v x y C* R.H.S. Ratio x 1 2 1 0 0 8 2

y 2 2 0 1 0 10 2

–3 –4 0 0 1 0 The most negative entry in last row is – 4  v-column is pivot column and the least ratio dividing R.H.S. by pivot column element is 2 8  row first is pivot row. Hence 2 is the pivot entry. R1: 2 1 R1 Basic variables u v x y C* R.H.S. v 2 1 1 2 1 0 0 4 y 2 2 0 1 0 10 – 3 –4 0 0 1 0 R2: R2 - 2R1, R3 : R3 + 4 R1 Basic variables u v x y C* R.H.S. Ratio v 2 1 1 2 1 0 0 4 8 2 / 1 4  y 1 0 -1 1 0 2 2

2  -1 0 2 0 1 16 Since all entries in the last row are not non-negative, the solution is not optimal. Again, the most negative entry is last row is – 1  u-column is pivot column and the least ratio dividing R.H.S. by pivot column element is 1 2  row second is pivot row. Hence 1 is the pivot entry. R1: R1 - 2 1 R2, R3 : R3 + R2

*364* Solution Manual to Basic Mathematics Linear Programming Basic variables u v x y C* R.H.S. v 0 1 1 - 2 1 0 3 u 1 0 -1 1 0 2 0 0 1 1 1 18  Max.C* = 18 at u = 2, v = 3  Min. C = 18 at x = 1, y = 1 e) Minimize U = 3x1 + x2s.t. 2x1 + x2 14 x1 – x2 4 x1, x2 0 The augmented matrix form of given LPP is  The dual of given LPP is Maximize U* = 14u + 4v s.t. 2u + v  3 u – v 1 u, v  0 Introducing the non-negative slack variables x1 and x2, the LP problem is 2u + v + x1 = 3 u - v + x2 = 1 14u + 4v = U* i.e. 2u + v + x1 + 0.x2 + 0.U* = 3 u - v + 0.x1 + x2 + 0.U* = 1 – 14u - 4v + 0.x1 + 0.x2 + U* = 0 The initial simplex table of the problem is given by Basic variables u v x1 x2 U* R.H.S. Ratio x1 2 1 1 0 0 3 2

x2 1 -1 0 1 0 1 1

– 14 - 4 0 0 1 0 The most negative entry is last row is – 14  u-column is pivot column and least ratio dividing R.H.S. by pivot column element is 1 1  row second is pivot row. Hence 1 is the pivot entry. R1: R1 - 2R2, R3: R3 + 14 R2 Basic variables u v x1 x2 U* R.H.S. Ratio x1 0 3 1 -2 0 1 3

u 1 - 1 0 1 0 1 1

 0 -18 0 14 1 14

–1

A = 2

–1

A = T

Linear Programming *365* Computational Methods Since all entries in the last row are not non-negative, the solution is not optimal. Again, the most negative entry is last row is – 18  v-column is pivot column and only the positive ratio dividing R.H.S. by pivot column element is 3 1  row first is pivot row. Hence 3 is the pivot entry. R1: 3 1 R1 Basic variables u v x1 x2 U* R.H.S. v 0 1 3 1 - 3 2 0 3

u 1 -1 0 1 0 1 0 -18 0 14 1 14 Operating R2: R2 + R1 R3: R3 + 18R1 Basic variables u v x1 x2 U* R.H.S. v 0 1 3 1 - 3 1 0 3

u 1 0 3

1 0 3

0 0 6 2 1 20  Max.U* = 20 at u = 3 4 , v = 3 1 Min. U = 20 at x = 6, y = 2 f) Minimize Z = 4x + 8y s.t. 2x + y  6 x + 2y  6 x, y  0 The augmented matrix form of given LPP is  The dual of given LPP is Maximize Z* = 6u + 6v s.t. 2u + v  4 u + 2v  8 u, v  0 Introducing the non-negative slack variables x and y, the LP problem is 2u + v + x = 4 u + 2v + y = 8 6u + 6v = Z* i.e. 2u + v + x + 0.y + 0.Z* = 4 u + 2v + 0.x + y + 0.Z* = 8 – 6u – 6v + 0.x + 0.y + Z* = 0 The initial simplex table of the problem is given by Basic variables u v x y Z* R.H.S. Ratio x 2 1 1 0 0 4 2

y 1 2 0 1 0 8 1

-6 -6 0 0 1 0

A = 2

A = T

*366* Solution Manual to Basic Mathematics Linear Programming The negative entry is last row are both – 6. So, let us take u-column is pivot column and least ratio dividing R.H.S. by pivot column elements is 2 4  row first is pivot row. Hence 2 is the pivot entry. R1: 2 1 R1, Basic variables u v x y Z* R.H.S. u 1 2

1 0 0 2 y 1 2 0 1 0 8 -6 -6 0 0 1 0 R2: R2 – R1, R3: R3 + 6R1 Basic variables u v x y Z* R.H.S. u 1 2

1 0 0 2 2 / 1 2 = 4 y 0 2 3 - 2 1 1 0 6 2 / 3 6 = 4 0 -3 3 0 1 12 Since all entries in the last row are not non-negative, the solution is not optimal. Again, the most negative entry is last row is – 3  v-column is pivot column and the ratios dividing R.H.S. by pivot column element are both 4  row second shall be now the pivot row. Hence 2 3 is the pivot entry. R2: 3 2 R2 Basic variables u v x y Z* R.H.S. u 1 2

1 0 0 2 v 0 1 3

 3 2 0 4 0 -3 3 0 1 12 R1: R1– 2 1 R2, R3: R3 + 3R2 Basic variables u v x y Z* R.H.S. u 1 0 3

 0 0 v 0 1 3

 3 2 0 4 0 0 2 2 1 24  Max.C* = 24 at u = 0, v = 4  Min. C = 24 at x = 2, y = 2 g) Minimize U = 24x + 16y s.t. 2x + y  10 8x + 8y  64 x 0, y  0 The augmented matrix form of given LPP is

A = 2

A = T

Linear Programming *367* Computational Methods  The dual of given LPP is Maximize U* = 10u + 64v s.t. 2u + 8v  24 u + 8v  16 u, v  0. Introducing the non-negative slack variables x and y, the LP problem is 2u + 8v + x = 24 u + 8v + y = 16 10u + 64v = Z* i.e. 2u + 8v + x + 0.y + 0.U* = 24 u + 8v + 0.x + y + 0.U* = 16 – 10u – 64v + 0.x + 0.y + U* = 0 The initial simplex table of the problem is given by Basic variables u v x y U* R.H.S. Ratio x 2 8 1 0 0 24 3

24  y 1 8 0 1 0 16 2

16  -10 -64 0 0 1 0 The negative entry is last row is – 64v-column is pivot column and least ratio dividing R.H.S. by pivot column element is 2

16   row second is pivot row. Hence 8 is the pivot entry. R2: 8 1 R2, Basic variables u v x y U* R.H.S. Ratio x 2 8 1 0 0 24 v 8 1 1 0 8 1 0 2 -10 -64 0 0 1 0 R1: R1 – 8R2, R3: R3 + 64R2 Basic variables u v x y U* R.H.S. Ratio x 1 0 1 -1 0 8 8

8  v 8 1 1 0 8 1 0 2 16 8 / 1 2  -2 0 0 8 1 128 Since all entries in the last row are not non-negative, the solution is not optimal. Again, the most negative entry is last row is – 2  u-column is pivot column and the ratios dividing R.H.S. by pivot column element is 8

8   row first is the pivot row. Hence 1 is the pivot entry. R2: R2 – 8 1 R1, R3: R3 + 2R1

*368* Solution Manual to Basic Mathematics Linear Programming Basic variables u v x y U* R.H.S. Ratio u 1 0 1 -1 0 8 v 0 1 – 8

1 0 1 0 0 2 6 1 144  Max. U* = 144 at u = 0, v = 4  Min. U = 144 at x = 2, y = 6 h) Minimize F = 20x1 + 48x2s.t. x1 + 3x2 11 x1 + 2x2 9 x1, x2 0. The augmented matrix form of given system is  The dual of given LPP is Maximize F* = 11u + 9v s.t. u + v  20 3u + 2v  48 u, v  0 Introducing the non-negative slack variables x1 and x2, the LP problem is u + v + x1 = 20 3u + 2v + x2 = 48 11u + 9v = F* i.e. u + v + x1 + 0.x2 + 0.F* = 20 3u + 2v + 0.x1 + x2 + 0.F* = 48 - 11u - 9v + 0.x1 + 0.x2 + F* = 0 The initial simplex table of the problem is given by Basic variables u v x1 x2 F* R.H.S. Ratio x1 1 1 1 0 0 20 20

20  x2 3 2 0 1 0 48 16

48  -11 -9 0 0 1 0 The most negative entry in last row is – 11  u-column is pivot column and least ratio dividing R.H.S. by pivot column element is 16

48   row second is pivot row. Hence 3 is the pivot entry. R2: 3 1 R2, Basic variables u v x1 x2 F* R.H.S. Ratio x1 1 1 1 0 0 20 u 1 3 2 0 3 1 0 16 -11 -9 0 0 1 0

A =

A = T

Linear Programming *369* Computational Methods R1: R1 – R2, R3: R3 + 11R2 Basic variables u v x1 x2 F* R.H.S. Ratio x1 0 3 1 1 - 3 1 0 4 12 3 / 1 4  u 1 3 2 0 3 1 0 16 24 3 / 2 16  0 3

 0 3 11 1 176 Since all entries in the last row are not non-negative, the solution is not optimal. Again, the most negative entry is last row is 3

  v-column is pivot column and the ratios dividing R.H.S. by pivot column element is 12 3 / 1 4   row first is the pivot row. Hence 3 1 is the pivot entry. R1: 3R1 Basic variables u v x1 x2 F* R.H.S. Ratio v 0 1 3 -1 0 12 u 1 3 2 0 3 1 0 16 0 3

 0 3 11 1 176 R2: R2 – 3 2 R1, R3: R3 3

 R1 Basic variables u v x1 x2 F* R.H.S. Ratio v 0 1 3 -1 0 12 u 1 0 -2 3 5 0 8 0 0 5 2 1 196  Max. F* = 196 at u = 8, v = 12  Min. C = 196 at x1 = 5, x2 = 2 5. a) A small scale dealer deals in a rice and wheat. He has Rs. 1500 for investment. A bag of rice costs him Rs. 180 and a bag of wheat Rs. 120. He has a storage capacity of 10 bags only. He sells a bag of rice at a profit of Rs. 11 and a bag of wheat at a profit of Rs. 8. How many bags of each must he buy to make a maximum profit? Also find the maximum profit. Soln: Let x and y are the nuber of rice and wheat bags. Here, the dealer sells a bag of rice at a profit of Rs. 11 and a bag of wheat at a profit of Rs. 8. Therefore profit function is given by P = 11x + 8y Also, A bag of rice costs him Rs. 180 and a bag of wheat Rs. 120. He has Rs. 1500 for investment. Therefore 180x + 120y  1500  3x + 2y  25 Also, He has a storage capacity of 10 bags only. Therefore, x + y  10 the corresponding LP problem is formulated as Maximize P = 11x + 8y s.t. 3x + 2y  25 x + y  10 x, y  0 Introducing the non-negative slack variables r and s, the LP problem is 3x + 2y + r = 25 x + y + s = 10 11x + 8y = P

*370* Solution Manual to Basic Mathematics Linear Programming i.e. 3x + 2y + r + 0.s + 0.P = 25 x + y + 0.r + s + 0.P = 10 - 11x – 8y + 0.r + 0.s + P = 0 The initial simplex table of the problem is given by Basic variables x y r s P R.H.S. Ratio r 3 2 1 0 0 25 33 . 8

25  s 1 1 0 1 0 10 10

10  -11 -8 0 0 1 0 The most negative entry in last row is – 11  x-column is pivot column and least ratio dividing R.H.S. by pivot column element is 33 . 8

25   row first is pivot row. Hence 3 is the pivot entry. R1: 3 1 R1, Basic variables x y s r P R.H.S. Ratio x 1 3

1 0 0 3

r 1 1 0 1 0 10 -11 -8 0 0 1 0 R2: R2 – R1, R3: R3 + 11R1 Basic variables x y s r P R.H.S. Ratio x 1 3

1 0 0 3

3 / 2 3 / 25  r 0 3 1 - 3 1 1 0 3 5 5 3 / 1 3 / 5  0 3

 3 11 11 1 3

Since all entries in the last row are not non-negative, the solution is not optimal. Again, the most negative entry is last row is 3

  y-column is pivot column and the ratios dividing R.H.S. by pivot column element is 5 3 / 1 3 / 5   row second is the pivot row. Hence 3 1 is the pivot entry. R2: 3R2 Basic variables x y r s P R.H.S. Ratio x 1 3

1 0 0 3

y 0 1 -1 3 0 5 0 3

 3 11 11 1 3

R1: R1 – 3 2 R2, R3: R3 + 3 2 R2 Basic variables x y r s P R.H.S. Ratio x 0 0 1 -2 0 5 y 0 1 -1 3 0 5 0 0 3 13 1 95  Max. P = 95 at x = 5, y = 5

Linear Programming *371* Computational Methods b) A farmer can obtain two types of fertilizers. A bag of fertilizer M cost Rs. 50 and contains 6 kg of Nitrogen and 3kg of Potassium. A bag of fertilizer N costs Rs. 40 and contains 3 kg of Nitrogen and 3kg of Potassium. If a farmer wants to add at least 30 kg of Nitrogen and at least 18 kg of Potassium to each plot of land, how many bags of each types of fertilizer should be used to minimize the cost of fertilizing a plot of land? Also find the minimum cost. Let x and y are no. of bags of fertilizer M and N. Since each bag of fertilizer M cost Rs. 50 and fertilizer N cost Rs. 40, the cost function C = 50x + 40y Each bag of fertilizer M has 6 kg Nitrogen and fertilizer N has 3kg Nitrogen and at least 30 kg of Nitrogen is to add then we have 6x + 3y  30  2x + y  10 Similarly, each bag of fertilizer M has 3 kg potassium and fertilizer N has 3 kg potassium and at least 18 kg of potassium is to add, then 3x + 3y  18  x + y  6  The LPP for given problem is Minimize C = 50x + 40y s.t. 2x + y  10 x + y  6 x, y  0. Now, we solve the problem using simplex. The augmented matrix form of given LPP is  The dual of given LPP is Maximize C* = 10u + 6v s.t. 2u + v  50 u + v  40 u, v  0 Introducing non-negative slack variables x and y we have 2u + v + x = 50 u + v + y = 40 – 10u –6v = C* i.e. 2u + v + x + 0.y + 0.C* = 50 u + v + 0.x + y + 0.C* = 40 – 10u – 6v + 0.x + 0.y + C* = 0 The initial simplex table to solve the problem is Basic variable u v x y C* R.H.S. Ratio x 2 1 1 0 0 50 50/2 = 25 y 1 1 0 1 0 40 40/1 = 40 –10 – 6 0 0 1 0 The most negative in last raw is – 10u- column is pivot column. The least ratio dividing R.H.S. by pivot column element is 50/2= 25 row second is pivot element R1: 1/2R1 Basic variable u v x y C* R.H.S. u 1 1/2 1/2 0 0 25 y 1 1 0 1 0 40 – 10 -6 0 0 1 0

A = 2

A = T

*372* Solution Manual to Basic Mathematics Linear Programming Operating, R2: R2 – R1, R3: R3 + 10R2 Basic variable u v x y C* R.H.S. Ratio u 1 1/2 1/2 0 0 25 25 1/2 =50 y 0 1/2 -1/2 1 0 15 15 1/2 = 30 0 – 1 5 0 1 250 Here the solution is not optimal since the cost raw consists non-negative entries –1 v – column is pivot column. The least ratio dividing R.H.S by pivot column element is 15 1/2 = 30, row second is pivot row. Operating, R2: 2R2 Basic variable u v x y C* R.H.S. u 1 1/2 1/2 0 0 25 v 0 1 –1 2 0 30 0 – 1 5 0 1 250 Operating R1: R1 – 1 2 R2 and R3: R3 + R2 0 u v x y C* R.H.S. u 1 0 1 –1/2 0 10 v 0 1 –1 2 0 30 0 0 4 2 1 280 Here, the solution is optimal as we have the last raw consisting non-negative entries.  Minimum of C* = 280 at u = 10, v = 30  Maximum of C = 280 at x = 4, y = 2 Hint and Solution of MCQ's 1. The different terms used in LPP are all of objective function, decision variable and constraints 2. To get the maximum profit with limited resourced, the method used in the LPP is a mathematical method. 3. The aim of LPP is to optimize the objective function. 4. The variable used to change the greater than inequality into equality is surplus variable. To change greater than inequality, A(x)  b in to the equality of the form A(x) + s = b, the value s is called surplus variable for s  0 5. The presentation of objective function Z = 3x + 4y with non-negative slack variables r and s is – 3x – 4y + 0.r + 0.S + Z = 0 6. The entering variable is the most negative value in pivot column. 7. The outgoing or departing variable is the variable in the row containing the least value of RHS entry corresponding pivot column entry 8. The pivot element in the simplex tableau is any element common to pivot column and pivot row. 9. In the tableau most negative in last row = – 5  Column 1st is entering column RHS  Corresponding to pivot column entry are such that:

3 <4 1 Row 1st is pivot raw common element of 1st column 1st row is 3 which is the pivot element. 10. The optimal value of objective function is obtained when all entries in the last row of simplex tableau is non-negative. 