Answer to Question #104828 in Operations Research for Biraj Chhetri

Question

Solve the following LP problem using the two-phase simplex method.

Manimize Z=X1-X2-3X3

Subjects to constraints
-2X1+2X2+3X3=2

2X1+3X2+4X3=1
And
X1, X2, X3≥0

Answer 1

We introduce one artificial non-negative variable ri in each equation of the system of constraints.

We get the following system of restrictions, $-2x1+2x2+3x3+r1=2$

$2x1+3x2+4x2 +r2=1$

with basis variables r1, r2.

The purpose of solving the auxiliary problem is to obtain an admissible basic solution that does not contain artificial variables (r1, r2). To do this, we form an auxiliary objective function: $G=r1+r2$ ;

To solve the auxiliary problem by the simplex method, we express the function G in terms of free variables, for this:

  - subtract equation 1 from the function G

  - subtract equation 2 from the function G

Function G will take the form:

G $=-5x1-7x3+3$

 Now we can form the initial simplex table.

Initial Simplex Table

x1 x2 x3 r1 r2 answer the attitude

r1 -2 2 3 1 0 2 $2/3$

r2 2 3 4 0 1 1 0.25

Z 1 -1 -3 0 0 0 -

G 0 -5 -7 0 0 -3 -

Iteration

x1 x2 x3 r1 answer the attitude

r1 -3.5 -0.25 0 1 1.25 -

x3 0.5 0.75 1 0 0.25 -

Z 2.5 1.25 0 0 0.75 -

G 3.5 0.25 0 0 -1.25 -

The optimal solution to the auxiliary problem is obtained (the minimum of the function G is found since there are no negative coefficients in the function line). The value of the function G is positive and there are artificial variables in the basis; therefore, the original problem is unsolvable due to the inconsistency of the constraint system.