System Engineering 3(3+0)

LESSON 4. Artificial Variable Techniques- Two Phase Method

ALGORITHM OF TWO PHASE METHOD

 The iterative procedure of the algorithm may be summarizing as below:

Step 1:

Write the given L.P.P into its standard form and check whether there exists a starting basic feasible solution.

• If there is a ready starting basic feasible solution, go to Phase 2.

• If there does not exist a ready starting basic feasible solution, go on to the next step.

PHASE 1

Step 2:

Add the artificial variable to the left side of the each equation that lacks the needed starting basic variables. Construct an auxiliary objective function aimed at minimizing the sum of all artificial variables

Thus, the new objective is to

Minimize z = A₁ +A₂ + A₃ + ………. +A_n

Maximize z^* = - A₁ - A₂ - A₃ -………..-A_n

where A_i (i = 1,2,3…m)are the non-negative artificial variables.

Step 3:

Apply simplex algorithm to the specially constructed L.P.P. The following three cases arise at the least interaction:

• Max z^* < 0 and at least one artificial variable is present in the basis with positive value. In such case, the original L.P.P does not possess any feasible solution.

• Max z^* = 0 and at least artificial variable is present in the basis at zero value. In such a case, the original L.P.P possess the feasible solution. In order to get basic feasible solution we may proceed directly to Phase 2 or else eliminate the artificial basic variable and then proceed to Phase 2.

• Max z^* = 0 and no artificial variable is present in the basis. In such a case, a basic feasible solution to the original L.P.P has been found. Go to Phase 2.

PHASE 2

Step 4:

Consider the optimum basic feasible solution of Phase 1 as the starting basic feasible solution for the original L.P.P. Assign actual coefficients to the variables in the objective function and a value zero to the artificial variables that appear at zero value in the final simplex table of Phase 1.

Apply usual simplex algorithm to the modified simplex table to get the optimum solution of the original problem.

Example:

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:

                             Minimize  = Maximize

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

Where 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

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

 Iteration 1:

 

	cj	0	0	0	0	0	-1	-1
cB	Basic variables B	x1	x2	x3	x4	x5	A1	A2	Solution values b (= XB)
0	x4	1	3	1	1	0	0	0	5
-1	A1	2	-1	1	0	-1	1	0	2
-1	A2	4	3	-2	0	0	0	1	5
zj–cj		-6	-2	1	0	1	0	0

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

Iteration 2:

 

	cj	0	0	0	0	0	-1
cB	Basic variables B	x1	x2	x3	x4	x5	A2	Solution values b (= XB)
0	x4	0	7/2	1/2	1	1/2	0	4
0	x1	1	-1/2	1/2	0	-1/2	0	1
-1	A2	0	5	-4	0	2	1	1
zj-cj		0	-5	4	0	-2	0

 A₂ 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.

 

Iteration 3:

 

	cj	3	-1	2	0	0
cB	Basic variables B	x1	x2	x3	x4	x5	Solution values b (= XB)
0	x4	0	0	33/10	1	-9/10	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	-9/10	0	-13/10

 

Iteration 4:

 

	cj	3	-1	2	0	0
cB	Basic variables B	x1	x2	x3	x4	x5	Solution values b (= XB)
0	x4	0	9/4	3/2	1	0	15/4
3	x1	1	3/4	-1/2	0	0	5/4
0	x5	0	5/2	-2	0	1	1/2
zj-cj		0	13/4	-7/2	0	0

 

Iteration 5:

	cj	3	-1	2	0	0
cB	Basic variables B	x1	x2	x3	x4	x5	Solution values b (= XB)
2	x3	0	3/2	1	2/3	0	5/2
3	x1	1	3/2	0	1/3	0	5/2
0	x5	0	11/2	0	4/3	1	11/2
zj-cj		0	17/2	0	7/3	0

 

Result:

             An optimal policy is x₁ = 5/2, x₂ = 0, x₃ = 5/2. The associated optimal value of the objective function is

Max z = 3 x (5/2) – 0 + 2 x (5/2) = 25/2.