Skedbooks
←
Operations Research

Artificial Variable Method Or Two Phase Method

Introduction:

In linear programming problems sometimes we see that the constraints may have ≥, ≤ or = signs. In such problems, basis matrix is not obtained as an identity matrix in the first simplex table; therefore, we introduce a new type of variable called, the artificial variable.

Artificial variable:

  •        These variables are fictitious and cannot have any physical meaning.
  •         The introduction of artificial variable is merely to get starting basic feasible solution, so that simplex procedure may be used as usual until the optimal solution is obtained.
  •          Artificial variable can be eliminated from the simplex table as and when they become zero i.e., non–basic. This process of eliminating artificial variable is performed in PHASE I of the solution.
  •          PHASE II is then used for getting optimal solution.
  •          Here the solution of the linear programming problem is completed in two phases, this method is known as TWO PHASE SIMPLEX METHOD.
  •          Hence, the two–phase method deals with removal of artificial variable in the first phase and work for optimal solution in the second phase.
  •         If at the end of the first stage, there still remains artificial variable in the basic at a positive value, it means there is no feasible solution for the problem given. In that case, it is not necessary to work on phase II.
  •          If a feasible solution exists for the given problem, the value of objective function at the end of phase I will be zero and artificial variable will be non-basic.
  •          In phase II original objective coefficients are introduced in the final tableau of phase I and the objective function is optimize.

Example1: By using two phase method find whether the following problem has a feasible solution or not?

Maximize Z = 4a 5b s.t. Simplex version is: Max. Z = 4a 5b 0S1 0S2 – MA s.t.

2a 4b ≤ 8 2a 4b 1S1 0S2 0A = 8

1a 3b ≥ 9 and both a and b are ≥ 0. 1a 3b 0S1 – 1S2 1A = 9 and

a, b, S1, S2, A all are ≥ 0

Phase I

Maximize Z = 0a 0b 0S1 0S2 – 1A s.t.

2a 4b 1S1 0S2 0A = 8

1a 3b 0S1 – 1S2 1A = 9 and a, b, S1, S2 and A all ≥ 0.