Simplex Method

Two Phase Method

In this method, the whole procedure of solving a linear programming problem 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.

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.

If the objective function is in minimization form, then convert it into maximization form.

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

The surplus variable x5 represents the extra units.

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

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

Table 1

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

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

Table 4

"The most useful virtue is patience" - John Dewey

Table 5

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.