Two Phase Method: Linear Programming

In Two Phase Method, the whole procedure of solving a linear programming problem (LPP) involving artificial variables is divided into two phases.

In phase I, we form a new objective function by assigning zero to every original variable (including slack and surplus variables) and -1 to each of the artificial variables. Then we try to eliminate the artificial varibles from the basis. The solution at the end of phase I serves as a basic feasible solution for phase II. In phase II, the original objective function is introduced and the usual simplex algorithm is used to find an optimal solution. The following are examples of Two Phase Method.

Two Phase Method: Minimization Example 1

Minimize z = -3x₁ + x₂ - 2x₃

subject to

x₁ + 3x₂ + x₃ ≤ 5
2x₁ – x₂ + x₃ ≥ 2
4x₁ + 3x₂ - 2x₃ = 5

x₁, x₂, x₃ ≥ 0

Solution.

Changing the sense of the optimization

Any linear minimization problem can be viewed as an equivalent linear maximization problem, and vice versa. Specifically:

Minimizec_jx_j = Maximize(- c_j)x_j

If z is the optimal value of the left-hand expression, then -z is the optimal value of the right-hand expression.

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

x₁ + 3x₂ + x₃ + x₄ = 5
2x₁ – x₂ + x₃ – x₅ = 2
4x₁ + 3x₂ - 2x₃ = 5

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

Where:
x₄ is a slack variable
x₅ is a surplus variable

Now, if we let x₁, x₂ and x₃ equal to zero in the initial solution, we will have x₄ = 5 and x₅ = -2, which is not possible because a surplus variable cannot be negative. Therefore, we need artificial variables.

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

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

Where A₁ and A₂ are artificial variables.

Phase 1 of Two Phase Method

In this phase, we remove the artificial variables and find an initial feasible solution of the original problem. Now 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

Initial basic feasible solution

The intial basic feasible solution is obtained by setting
x₁ = x₂ = x₃ = x₅ = 0

Then we shall have A₁ = 2 , A₂ = 5, x₄ = 5

Two Phase Method: Table 1

On small screens, scroll horizontally to view full calculation

Key column = x₁ column
Minimum (5/1, 2/2, 5/4) = 1
Key row = A₁ row
Pivot element = 2
A1 departs and x₁ enters.

Table 2

A2 departs and x₂ enters.
Here, Phase 1 terminates because both the artificial variables have been removed from the basis.

Phase 2 of Two Phase Method

The basic feasible solution at the end of Phase 1 computation is used as the initial basic feasible solution of the problem. The original objective function is introduced in Phase 2 computation and the usual simplex procedure is used to solve the problem.

Table 3

Use horizontal scrollbar to view full calculation

Table 4

Don't be impatient. The next table is the last table.

Two Phase Method: Final Optimal Table

An optimal policy 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.