This article throws light upon the top two artificial variable techniques for solving L.P.P. The techniques are: 1. The Big-M technique. 2. The Two Phase Method.
1. The Big-M Method:
This method consists of the following basic steps:
Step 1:
ADVERTISEMENTS:
Express the L.P.P in the standard form.
Step 2:
Add non-negative artificial variables to the left hand side of all the constraints of (= or ≥) type when artificial variables are added, it causes violation of the corresponding constraints. This difficulty is removed by introducing a condition which ensures that artificial variables will be zero in the final solution.
On the other hand, if the problem does not have a solution at least one of the artificial variables will appear in the final solution with positive value. This is achieved by assigning a very large price to these variables in the objective function such large price will be designated by -M for maximization problem +M for minimization problem where M> 0.
ADVERTISEMENTS:
Step 3:
In the last, use the artificial variable for the starting solution and proceed with the usual simplex routine until the optimal solution is obtained.
Example 1:
Solve by using Big -M method the following L.P.P:
Solution:
Step 1:
Introducing slack, surplus and artificial variable, the system of constraint equations become:
Step 2:
ADVERTISEMENTS:
Assigning the large negative price-M to the artificial variable a1 and a2, the objective function becomes:
Max z = -2×1 – x2 + OS1 + OS2 – Ma1 – Ma2
Step 3:
ADVERTISEMENTS:
Construct simplex Table
Since M is as large as possible Δ3, Δ5, Δ6, are all positive, consequently, the optimal solution is
x1 = 3/5
x2 = 6/5
max Z = -12/5
Example 2:
Solve by Big –M method
Solution:
x1, x2, x3, x4 ≥ 0
Since the constraints of the given problem are equations, introduce the artificial variables a1 > 0, a2 > 0. The problem thus becomes
Now applying the usual simplex method the solution is obtained as follows:
Since all Δj > 0 Therefore an optimum bases solution has been obtained.
x1 x2 = x3 = 15/6 = 5/3, x4 = 0
And max z = 15
Example 3:
Minimixe z = 2y1 + 3y2
Solution:
Introducing slack or surplus variables the problem may be written as
Where y1, y2, S1, S2, A1, A2 all > 0 Now applying the usual simplex method the solution is obtained as follows:
Since all Δj > 0 therefore basic feasible solution is obtained
y1 = 4, y2 = 1
and minimum value of z = -z1 = 11
Example 4:
Use Big-M method to maximize z = 3x1 – x2
Solution:
By introducing the surplus variable S1 > 0 artificial variable a1 > 0 and slack variable S2 > 0, S3 > 0, the problem becomes
Now applying the usual simplex method the solution is obtained as follows:
2. Two Phase Method:
This method solves the L.P problem in two phase.
Phase I:
It consists of the following steps:
Step 1:
Ensure that all bi are non-negative. If some of them are negative, make them non-negative by multiplying both sides of these inequalities equation by – 1.
Step 2:
Express the constraints in the standard form and non-negative variables to the left hand sides of all the constraints of (= or >) type
Step 3:
Formulate a new objective function which consists of the sum of the artificial variables
w = A1 + A2+… + An
The function w is known as the infeasibility form,
Step 4:
Using simplex method minimizes the function w subject to the above constraints of the original problem and obtain the optimum basic feasible solution. These cases arise.
(i) Min. w > 0 and at-least one artificial variable appear in the column variables in current solution at positive level. In such a case, No feasible solution exists for the original L.P.P and the procedure is terminated.
(ii) Min w = 0 and at-least one artificial variable appears in column ‘variables in current solution’ at Zero level. In such a case, the optimum basic feasible solution to the infeasibility from (Auxiliary L.P.P.) may or may not be a basic feasible solution to the given L.P.P to obtain basic feasible solution, we continue phase I and try to drive all artificial variable out of the basis and then proceed to phase II.
(iii) Min. w = 0 and no artificial variable appear in the columns variables in current solution. In such a case, a basic feasible solution to the original L.P.P. has been found. Proceed to phase II.
Phase II:
Use the optimum basic feasible solution for the original L.P.P. Using simplex method make iterations till all optimal basic feasible solution for it is obtained.
It may be noted that the new objective function W is always of minimization type regardless of whether the given L.P.P is of maximization or minimization type.
Example 1:
Use two-phase method to solve for L.P.P
Solution:
Phase 1:
It consists of the following steps:
Step 1:
First of all we observe that all bj are non-negative. So this step is not necessary in the present problem.
Step 2:
Adding slack variables the given constraints take the form:
Step 3:
The infeasibility form w = A1 + OS1 + OS2
Step 4:
We are thus to minimize equation min W = A1 subject to constraints equations construct the simplex table as follows.
Here min W=A1
Max w1 = (min w)= -A1
But under some columns Δj < 0 therefore the current basic feasible solution can be improved.
Step 5:
Iterate toward an optimal solution replace S1 by x2.
This is shown in following table:
Dj = Zj – Cj is either positive or Zero under all columns, an optimal basic feasible solution to the auxiliary L.P.P has been obtained
However since max w = -2 min w = -w1 = 2 which is > 0 and artificial variable A1 appears in column current solutions variables level (a1 = 2), the given L.P.P does not possess any feasible solutions and the procedure stops.
Example 2:
Use two phase simplex method to max
Solution Phase 1:
It consists of the following steps:
Step 1:
First of all we observe that all b1 should be non-negative. Since for the second constraint should be negative. b2 = -2. We multiply both sides by -1 transforming it to
4x1 – 7x2 – 5x3 ≤ 2
Step 2:
Adding slack and artificial variables, we get
Step 3:
We introduce a new objective function
Step 4:
But in simplex method it can be change max w1 = -(min w)= – a1
Step 5:
Perform optimality test
In the second table:
There is a tie for the key row, x1 is the key column and x2, column is the first column of the identity, but we find that x2 column does not break the tie. The next column of the identity, viz., S2 Column yield a1 row as the key row.
In the third table:
All Δj ≥ 0 therefore this is the optimal basic feasible solution for the auxiliary problem.
Also since min w = 0 and no artificial variable appear in the column in current solution. Therefore this table yields the basic feasible solution for the original problem.
Phase II:
The original objective function is
Max z= 3x1 + 2x2 + 2x3 + os1 + os2+ os3 we are now to maximize in subject to the original constraints. Using the solution of table (3) as the starting solution for phase II and carrying out computations using simplex method we get next table (4).
Table (5) indicates all Δj ≥ 0. This table givens optimal basic feasible solution as:
x1 = 1
x2 = 2/7 and max z = 25/7
x3 = 0