LP: big M method

When the linear problem has constraints with bi negative as well as equalities, then it is difficult to find a starting solution. It is then necessary to use the method of the big M which consists of adding artificial variables having a great impact on the objective function (negative if max, positive if min) with bi positives. Here is an example of a linear problem before and after the transformation of the big M:

LP28

Which gives the resolution of the following simplex:

LP29

The solution vector is (6, 10, 0, 5, 0, 0), so we can remove the artificial variables (6, 10, 0, 5) to solve the simplex. It is then necessary to continue the resolution of the simplex by removing the columns in big M.

Publicités