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.