Artificial Starting Solution The Big M Method
The linear programming problem in which all constraints are () with
nonnegative right-hand sides offers a all-slack starting basic feasible
solution. Problems with (=) and/or () constraints need to use artificial
variables to the beginning of simplex algorithm. There are two meth-
ods: the M-method(also called the Big M-method) and the Two-Phase
method.
OPERATIONS RESEARCH
Artificial Starting Solution The Big M Method
Example
Maximize Z = 2x1 + x2 3x3
subject to
x1 + x2 + x3 6
2x1 + x2 = 14
x1, x2, x3 0
After converting to standard form we have:
Maximize Z = 2x1 + x2 3x3
subject to
x1 + x2 + x3 s1 = 6
2x1 + x2 = 14
x1, x2, x3, s1 0
OPERATIONS RESEARCH
Artificial Starting Solution The Big M Method
Adding Artificial Variables
The above system of equations is not in basic form - there is not a
basic variable in each equation.
If the equation i does not have a slack (or a variable that can play the
role of a slack), an artificial variable, ai , is added to form a starting
solution similar to the all-slack basic solution. However, because the
artificial variables are not part of the original linear model, they are as-
signed a very high penalty in the objective function, thus forcing them
(eventually) to equal zero in the optimal solution.
In the considering example we add two artificial variables a1 and a2 .
OPERATIONS RESEARCH
Artificial Starting Solution The Big M Method
Penalty Rule for Artificial Variables.
Given M, a sufficiently large positive value (mathematically, M ),
the objective coefficient of an artificial variable represents an
appropriate penalty if:
M, in maximization problems
Artificial variable objective coefficient =
M, in minimization problems.
So we have:
Maximize Z = 2x1 + x2 3x3 Ma1 Ma2
subject to
a1 +x1 + x2 + x3 s1 = 6
a2 +2x1 + x2 = 14
x1, x2, x3, s1, a1, a2 0
OPERATIONS RESEARCH
Artificial Starting Solution The Big M Method
The Big M Method Calculations
First and second simplex tableau are as follows:
cB BV a1 a2 x~1 x2 x3 s1 Solution
a~1 1 0 1 1 1 1 6 6/1 = 6
a2 0 1 2 1 0 0 14 14/2 = 7
Z 100 100 -2 1 3 0 2000
x1 1 0 1 1 1 1 6
a~2 2 1 0 1 2 2 2 2/2 = 1
Z 102 100 0 1 -1 2 2012
The optimal simplex tableau:
BV a1 a2 x1 x2 x3 s1 Solution
1 1
x1 0 2 1 2 0 0 7
1
s1 1 2 0 12 1 1 1
Z 100 101 0 0 3 0 14
Optimal solution is: x1 = 7, s1 = 1, x2 = x3 = 0 with Z = 14.
OPERATIONS RESEARCH
Artificial Starting Solution The Big M Method
No Feasible Solution - an Example
The use of the penalty M will not force an artificial variable to zero level
in the final simplex iteration if LPP does not have a feasible solution
(i.e. the constraints are not consistent). In this case, the final simplex
tableau will include at least one artificial variable at positive level.
Solve the problem :
max Z = 2x1 + 2x2
6x1 + 4x2 24
x1 5
x1 , x2 0
The standard form:
max Z = 2x1 + 2x2
s1 +6x1 + 4x2 = 24
x1 s2 = 5
x1 , x2 , s1 , s2 0
OPERATIONS RESEARCH
Artificial Starting Solution The Big M Method
Using The Big M Method to Solve the Problem
It is enough to add only one artificial variable :
max Z = 2x1 + 2x2 Ma2
s1 +6x1 + 4x2 = 24
a2 +x1 s2 = 5
x1 , x2 , s1 , s2 0
OPERATIONS RESEARCH
Artificial Starting Solution The Big M Method
The Big M Method Calculations
cB BV s1 a2 x~1 x2 s2 Solution
0 s~1 1 0 6 4 0 24 24/6 = 4
M a2 0 1 1 0 1 5 5/1 = 5
Z 0 0 M 2 2 M 5M
cB BV s1 a2 x1 x2 s2 Solution
1 2
2 x1 6 0 1 3 0 4
M a2 16 1 0 32 1 1
1 1 2 2
Z 6M + 3 0 0 3M 3 M M + 8
The last simplex tableau is optimal - all Z - row coefficients are
nonnegative. The artificial variable a2 is basic variable with positive
value so the problem is not consistent - it has no feasible solutions.
OPERATIONS RESEARCH
