Lecture_6_Artificial variable technique

6.1 Computational Procedure of Big – M Method (Charne’s Penalty Method)
Step 1 – Express the problem in the standard form.
Step 2 – Add non-negative artificial variable to the left side of each of the equations
corresponding to the constraints of the type ‘?’ or ‘=’.
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 (provided the solution of the problem exists).
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 (per unit penalty) to these variables in the objective function. Such large price will be
designated by –M for maximization problems (+M for minimizing problem), where M > 0.
Step 3 – In the last, use the artificial variables for the starting solution and proceed with the usual
simplex routine until the optimal solution is obtained.
6.2 Worked Examples
Lecture 6
Linear programming :
Artificial variable technique :
Big - M method
1
Example 1
Max Z = -2x1 - x2
Subject to
3x1 + x2 = 3
4x1 + 3x2 ? 6
x1 + 2x2 ? 4
and x1 ? 0, x2 ? 0
Solution
SLPP
Max Z = -2x1 - x2 + 0s1 + 0s2 - M a1 - M a2
Subject to
3x1 + x2 + a1= 3
4x1 + 3x2 – s1 + a2 = 6
x1 + 2x2 + s2 = 4
x1 , x2 , s1, s2, a1, a2 ? 0