Two-phase simplex method max:Z=3x₁−x₂

Idea of the two-phase method. Phase I removes the artificial variables by maximising −(sum of artificial variables) (the same as minimising their sum). If the optimum is 0, a basic feasible solution of the original problem has been found. Phase II then optimises the real objective function starting from that solution.

Step 1: Standard form.

• 2x₁ + x₂ ≥ 2: subtract surplus variable s₁ and add artificial variable A₁.
• x₁ + 3x₂ ≤ 2: add slack variable s₂.
• x₂ ≤ 4: add slack variable s₃.

2x₁ + x₂ − s₁ + A₁ = 2
x₁ + 3x₂ + s₂ = 2
x₂ + s₃ = 4

Phase I. Maximize Z′ = −A₁ (cost 0 for all other variables). Starting basis: A₁, s₂, s₃.

Table 1

          Cj  0  0  0 -1  0  0         
Basis     CB x₁ x₂ s₁ A₁ s₂ s₃  b Ratio
---------------------------------------
A₁        -1  2  1 -1  1  0  0  2     1
s₂         0  1  3  0  0  1  0  2     2
s₃         0  0  1  0  0  0  1  4     -
---------------------------------------
          Zj -2 -1  1 -1  0  0 -2      
       Cj-Zj  2  1 -1  0  0  0         
Entering: x₁   Leaving: A₁   Pivot = 2

Table 2

          Cj  0   0    0  0  0  
Basis     CB x₁  x₂   s₁ s₂ s₃ b
--------------------------------
x₁         0  1 1/2 -1/2  0  0 1
s₂         0  0 5/2  1/2  1  0 1
s₃         0  0   1    0  0  1 4
--------------------------------
          Zj  0   0    0  0  0 0
       Cj-Zj  0   0    0  0  0  

In the last table of Phase I, Max Z′ = 0 and A₁ is no longer in the basis, so the original problem is feasible. Delete the A₁ column and go to Phase II.

Phase II. Restore the original objective: Maximize Z = 3x₁ − x₂ + 0s₁ + 0s₂ + 0s₃, starting with the final basis of Phase I (x₁, s₂, s₃).

Table 1

          Cj  3   -1    0  0  0        
Basis     CB x₁   x₂   s₁ s₂ s₃ b Ratio
---------------------------------------
x₁         3  1  1/2 -1/2  0  0 1     -
s₂         0  0  5/2  1/2  1  0 1     2
s₃         0  0    1    0  0  1 4     -
---------------------------------------
          Zj  3  3/2 -3/2  0  0 3      
       Cj-Zj  0 -5/2  3/2  0  0        
Entering: s₁   Leaving: s₂   Pivot = 1/2

Table 2

          Cj  3  -1  0  0  0  
Basis     CB x₁  x₂ s₁ s₂ s₃ b
------------------------------
x₁         3  1   3  0  1  0 2
s₁         0  0   5  1  2  0 2
s₃         0  0   1  0  0  1 4
------------------------------
          Zj  3   9  0  3  0 6
       Cj-Zj  0 -10  0 -3  0  

All Cj − Zj ≤ 0, so the solution is optimal.

Answer: x₁ = 2, x₂ = 0, Maximum Z = 6.