Answer to Question #235131 in Linear Algebra for mickey

Question

5)Solve the following linear programming problem using two phase method. 

Minimize z = -3x1 + x2 - 2x3 

Subject to 

x1 +3x2 +x3 ≤5 

2x1 –x2 +x3 ≥2 

4x1 + 3x2 - 2x3 = 5 

x1, x2, x3 ≥ 0 

Answer 1

SOLUTION

Changing the minimisation to maximization

Maximize z = 3x₁ – x₂ + 2x₃

subject to

x₁ + 3x₂ + x₃ ≤ 5

2x₁ – x₂ + x₃ ≥ 2

4x₁ + 3x₂ - 2x₃ = 5

x₁, x₂, x₃ ≥ 0

Converting inequalities to equalities and introducing slack, surplus and artificial variables:

x₁+ 3x₂+ x₃+ x₄= 5

2x₁– x₂+ x₃– x₅+ A₁= 2

4x₁+ 3x₂ - 2x₃ + A₂ = 5

x1, x2, x3, x4, x5, A₁, A₂ ≥ 0

Where:

A1 and A2 are artificial variables

x₄ is a slack variable

x₅ is a surplus variable

.

Phase 1 The objective function can be expressed as

Maximize 0x₁ + 0x₂ + 0x₃ + 0x₄ + 0x₅ + (–A₁) + (–A₂)

subject to

x₁ + 3x₂ + x₃ + x₄ = 5

2x₁ – x₂ + x₃ – x₅ + A₁ = 2

4x₁ + 3x₂ - 2x₃ + A₂ = 5

x₁, x₂, x₃, x₄, x₅, A₁, A₂ ≥ 0

Two Phase Method: Table 1

 c_j 0 0 0 0 0 -1 -1 X_B

c_{B Bv} x₁ x₂ x₃ x₄ x₅ A₁ A₂

0 x₄ 1 3 1 1 0 0 0 5

-1 A₁ 2 -1 1 0 -1 1 0 2

-1 A₂ 4 3 -2 0 0 0 1 5

z_j–c_j.  -6 -2 1 0 1 0 0 

Key column = x₁ column

Key row = A₁ row

Key element = 2

X_{B... solution values}

A1 departs and x₁ enters.

TABLE 2

CJ 0 0 0 0 0 -1 X_B

CB BV X1 X2 X3 X4 X5 A2

0 X4 0 7/2 1/2 1 1/2 0 4

0 X1 1 -½ ½ 0 -½ 0 1

-1 A2 0 5 -4 0 2 1 1

Z_j- C_j 0 -5 4 0 -2 0

A2 departs and x₂ enters.

Both the artificial variables have been removed from the basis.

Phase 2:

TABLE 3

 c_j 3 -1 2 0 0

CB BV x₁ x₂ x₃ x₄ x_{5 XB}

0 x₄ 0 0 33/10 1 -9/13 33/10

3 x1 1 0 1/10 0 -3/10 11/10

-1 x2 0 1 -4/5 0 2/5 1/5

Zj-Cj 0 0 -3/10 0 -13/10

TABLE 4

 c_j 3 -1 2 0 0 

c_B Bv x₁ x₂ x₃ x₄ X5 XB

0 x₄ 0 9/4 3/2 1 0 15/4

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

0 x₅ 0 5/2 -2 0 1 1/2

z_j-c_j.  0 13/4 -7/2 0 0 

Two Phase Method: Optimal Table

  c_j 3 -1 2 0 0  xb

Bv x₁ x₂ x₃ x₄ x₅

2 x₃ 0 3/2 1 2/3 0 5/2

3 x11 3/2 0 1/3 0 5/2

0 x₅ 0 11/2 0 4/3 1 11/2

z_j-c_j  0 17/2 0 7/3 0 

An optimal is x₁ = 5/2, x₂ = 0, x₃ = 5/2. The associated optimal value of the objective function is z = 3 X (5/2) – 0 + 2 X (5/2) = 25/2.