Question

solve the following LP. Formulate and algebraically solve the problem.

what is the new optimal z value

show that the current basis is optimal

max z=65x1+25x2+20x3

8x1+6x2+x3<=48

4x1+2x2+1.5x3<=20

2x1+1.5x2+0.5x3<=8

x2<=5

x1,x2,x3>=0

Answer 1

max z = 65x1 + 25x2 + 20x3

8x1 + 6x2 + x3 <= 48

4x1 + 2x2 + 1.5x3 <= 20

2 x1 + 1.5x2 + 0.5x3 <= 8

x2 <= 5

x1,x2,x3,x4 >= 0

now we can add slack variables to get equations from inequalities.

Equations from given inequalities.

8x1 + 6x2 + x3 + s1 = 48

4x1 + 2x2 + 1.5x3 + s2 = 20

2 x1 + 1.5x2 + 0.5x3 + s3 = 8

x2 + s4 = 5

And - 65X₁ - 25X₂ - 20X₃ + z = 0

Now we can matrix representation of initial tableau for above equations.

X₁     X₂      X₃      S₁     S₂     S₃     S₄     p            

8        6      1        1      0      0      0      0      48    

4        2      3/2     0      1      0      0      0      20    

2      3/2   1/2    0      0      1      0      0      8     

0        1         0       0      0      0      1      0      5     

-65    -25    -20    0      0      0      0      1      0

Here the most negative element in the bottom row will indicates the pivot element so here -65 ,so we have in column 1 so I am taking 1^st column as a pivot column and for pivot row the least positive result when last column divided by pivot column will indicates so

i.e. +min (48/8 , 20/4 , 8/2) = 8/2 so 3^rd row as a pivot row.

R₃-> R₃ (1/2)

X₁     X₂      X₃      S₁     S₂     S₃     S₄     p            

8        6      1        1      0      0      0      0      48    

4        2      3/2     0      1      0      0      0      20    

1      3/4   1/4    0      0     1/2   0      0      4     

0        1         0       0      0      0      1      0      5     

-65    -25    -20    0      0      0      0      1      0

R₁-> R₁ - 8R₃   R₂-> R₂ - 4R₃      R₅-> R₅ + 65R₃

X₁     X₂      X₃      S₁     S₂     S₃     S₄     p            

0        0      -1        1      0      -4     0      0      16    

0      -1     1/2      0      1      -2     0      0      4     

1      3/4    1/4     0      0      1/2    0      0      4     

0         1        0       0       0       0       1      0      5     

0      95/4   -15/4 0      0      65/2   0      1      260

Here the most negative element in the bottom row will indicates the pivot element so here -15/4 ,so we have in column 3^rd so I am taking 3^rd column as a pivot column and for pivot row the least positive result when last column divided by pivot column will indicates so

i.e. +min (4/(1/2) , 4/(1/4)) = 4/(1/2) so 2^nd row as a pivot row.

R₂-> R₂ (2)

X₁     X₂      X₃      S₁     S₂     S₃     S₄     p            

0        0      -1        1      0      -4     0      0      16    

0      -2      1        0      2      -4     0      0      8

1      3/4    1/4     0      0      1/2    0      0      4     

0         1        0       0       0       0       1      0      5     

0      95/4   -15/4 0      0      65/2   0      1      260

R₁-> R₁ + R₂   R₃-> R₃ - (1/4)R₂      R₅-> R₅ + (15/4)R₂

X₁     X₂      X₃      S₁     S₂       S₃     S₄     p            

0     -2       0      1       2      -8     0      0      24    

0      -2       1     0      2      -4     0      0      8     

1      5/4     0      0   -1/2   3/2     0      0      2     

0         1      0      0      0        0        1      0      5     

0      65/4   0      0   15/2   35/2   0      1      290

So now we did not have any negative elements in bottom row so we can stop the iterations. Now the optimum solution is Maximum Z = 290   At    x1= 2 , x2 = 0 , x3 = 8