Question

Use the two-phase simplex method to solve the problem

max z = 3х + х) s.t. ху + х = 3 2х + x2 3 4 x + x2 = 3 х1, х2 = 0

Answer 1

1 The given problem is; Max - 3x1 +22 X + x2 > 3 24. + x2 < 4 x1 + x2 = 3 X1, X, YO The above problem can be rewri Hen aus ; Max Z = 344 +22 St. x1 + x2 7,3 22, +32 54 x1 + x2 7,3 x1 + x2 = 3 24,X2 > 0 since the first and third constraints are same (x1+2273) thuis we con say that the third constraint is a redundant : The standard form of the given problem is as follows Cintroducing slack, suaplus and artificial variables); More ·Z = 32 + x2 +0.X3 - M. X4 +0.25 +0.Xe ;(Mis a . large st. 2, +X, - tg + 24 = 3 number) 2x1 + x2 +25. = 4 4 + x2 + xe = 3 21, X2, 23, 24, 25,X >0 where x3 = surplus variable XA - artificial variable 25,24 = slock variables. - To solve the problem by Two Phase Simplex Method, we consider the following steps

variable xa and zero to PHASE-I : Bu - ö By assjaning a cost (-1) to the artificial 24 and 2ero to all other variables the new objective function is ; max 2 = 0.x, +0.25 +0.23 -1.74 +0.75 +0.25 Man So, the auxilary auxilary problem problem of is such that , phase -I x1 + x₂ - Xz+x4 = 3 221 + x2 + x = 4 x + x2 + x6 =3 xi 7,0 for i=1,2,...,6. we now construct the initial simplex table of Phase I TG TO 0 0 I O o eB ZB b a X2 X3 X4 Xg xe 1- 3 1 1 0 0 0 % 4 I[2] | 0 0 1 0 | O 2 .3 1 0 0 0 1 T Z- T-1 al T o o ot Since (2,-41) and (22-(2) are of some value and negative most any one of them is entering variable.

O- Let, Entering variable Min } }, ,7Y=4, which corresponds to 45. teaving variable = x5 - The next table is ; . 19 10 0 0 1 0 0 | CB RB x x x x x x -1 X T o - 1 1/2 0 0 24 2 12 0 0 12. o o zelio 12 0 0 -12 I. - G o -1/2 o 1/2 o since 22-4 =-1/2 is the negative most, x2 is the Entering variable .. Min ti y ý i cunich corresponds to both XA and xo . So either of them can be chosen as - Let, leaving variable = x4 rearing variable. The next table is; 19o 0 0 -1 0 0 ICB XB b x x x3 x4 xs xe 10 X 20 1 -2 2 - 0 1024 0 1 1 1 0 O re o lo 0 -1 0 1 T Zj- G o o o o o Since all Zj-cj yo and no artificial variable appears in the basis therefore an optimum basic feasible solution to the arrilary linear programming problem has been reached therefore we proceed on to Phase -f .

associated! n! Here we consider the actual costs function is with the original variables · The objective therefore ; Further We will not 7 considen the Max Z = 3x1 + x2 +0.25 +0.25 +0.28 Lartificial variable Using the optimum simplex table of phase -I as the initial simplex table of phase-l, we construct . the following table; G 3 1 oo o I To Roba X2 X3 xs xel | 22 | 2 0 1 -2 -1 0 3 21 1 0 1 1 0 0 24 10 0 0 1 0 1 Zi-Glo o 2 o since all Zi-G 70, we have reached the optimum stage and the optimal solution is given by 24 = 1 , X2 = 2 and Zmax = 3+2 = 5.