OQM Lecture Note - Part 4 Big-M Method and Two-Phase Simplex Method
OQM Lecture Note - Part 4 Big-M Method and Two-Phase Simplex Method
OQM Lecture Note - Part 4 Big-M Method and Two-Phase Simplex Method
1
In searching for an initial bfs, we see that s1 = 4 could be used as a basic (and
feasible) variable for the row-1 equation. If we multiply row 2 by −1, we see that
e2 = −20 could be used as a basic variable for row 2. Unfortunately, e2 = −20
violates the sign restriction e2 ≥ 0. Finally, in row 3 there is no readily apparent
basic variable.2 Thus, in order to use the Simplex method, each of rows 2 and
3 needs a basic variable which is feasible. To remedy this problem, we simply
“invent” a basic feasible variable for each equation that needs one. Since these
variables are created and are not real variables existing in the standard form of
the original LP, we call them artificial variables. If an artificial variable is added
to row i, we label it ai . In the considered LP, we need to add an artificial variable
a2 to row 2 and an artificial variable a3 to row 3. The resulting canonical form is
Rectifying the objective function in this way makes it extremely costly for an
artificial variable to be positive. With this modified objective function, it seems
reasonable that the optimal solution to (3) will have a2 = a3 = 0. In this case,
the optimal solution to (3) will solve the original standard form (1). It sometimes
happens, however, that in solving (3), some of the artificial variables may assume
positive values in the optimal solution. If this occurs, the original problem has no
feasible solution. For obvious reasons, the method we have just outlined is often
called the Big-M method.
Now we give the formal description of the Big-M method.
2
Notice that row 3 does not satisfy the requirement of the canonical form.
2
Step 1. Modify the constraints so that the rhs of each constraint is nonnegative.
This requires that each constraint with a negative rhs be multiplied through
by −1.3
Step 2. Convert the system of constraints to standard form, i.e. add a slack variable
si in the lhs of each ≤ constraint and subtract an excess variable ei from
the lhs of each ≥ constraint.
Step 3. For each constraint without a slack variable si , add an artificial variable ai
in the lhs. Also add the sign restriction ai ≥ 0.
Step 4. Let M denote a very large positive number. If the LP is a min problem,
add (for each artificial variable) Mai to the objective function. If the LP
is a max problem, add (for each artificial variable) −Mai to the objective
function.
Step 5. Because each artificial variable will be in the initial basis, all artificial vari-
ables must be eliminated from row 0 to make a canonical form before begin-
ning the Simplex procedure. The choice of the entering variable depends on
the multiplier of M since M is a very large positive number. For example,
4M − 2 is more positive than 3M + 900, and −6M + 5 is more negative than
−5M − 40. Now solve the transformed problem by the Simplex method. If
all artificial variables are equal to zero in the optimal solution, then we have
found the optimal solution to the original LP. If any artificial variables are
positive in the optimal solution, then the original problem is infeasible.4
When an artificial variable leaves the basis, its column may be dropped from
future tableaux because the purpose of an artificial variable is only to get a
initial bfs. Once an artificial variable leaves the basis, we no longer need it.5
Now we resume solving the modified LP (3), which actually can be obtained by
going through Steps 1–4. Going to Step 5, we first rearrange row 0,
to satisfy the canonical form. Because a2 and a3 are in the initial bfs, they must
be eliminated from row 0. To eliminate a2 and a3 from row 0, simply replace row
0 by row 0 +M(row 2)+M(row 3). This yields the new row 0:
Combining the new row 0 with rows 1–3 yields the initial tableau shown below.
3
Remember that if you multiply an inequality by any negative number, the direction of the
inequality is reversed. For example, we would transform the inequality x1 + x2 ≥ −1 into
−x1 − x2 ≤ 1. The inequality x1 − x2 ≤ −2 would be transformed into −x1 + x2 ≥ 2.
4
We have ignored the possibility that when the modified LP (with the artificial variables) is
solved, the final tableau may indicate that the LP is unbounded. If the final tableau indicates
the LP is unbounded and all artificial variables in this tableau equal zero, then the original LP
is unbounded. If the final tableau indicates that the LP is unbounded and at least one artificial
variable is positive, then the original LP is infeasible.
5
Despite this fact, we will maintain the artificial variables in all tableaux when doing Primal-
Dual transformation which will be introduced in the following lectures.
3
basis x1 x2 s1 e2 a2 a3 rhs ratio test
z 2M − 2 4M − 3 0 −M 0 0 30M
1 1 4
s1 2 4
1 0 0 0 4 ( 41 )
= 16
20
a2 1 3 0 −1 1 0 20 3
*
10
a3 1 1 0 0 0 1 10 1
= 10
We are solving a min problem, so the variable with the most positive coefficient
in row 0 should enter the basis. Because 4M > 2M, variable x2 should enter
the basis. The ratio test indicates that x2 should enter the basis in row 2, which
means the artificial variable a2 will leave the current basis. The most difficult
part of doing the pivot is eliminating x2 from row 0. First, replace row 2 by 31 (row
2). Thus, the new row 2 is
1 1 1 20
x1 + x2 − e2 + a2 = .
3 3 3 3
We can now eliminate x2 from row 0 by adding −(4M − 3)(new row 2) to row 0.
Then we have the new row 0:
2M − 3 M −3 3 − 4M 10M + 60
z+ x1 + e2 + a2 = .
3 3 3 3
After using EROs to eliminate x2 from row 1 and row 3 as well, we obtain the
following tableau.
5 1 1 7 ( 37 ) 28
s1 12
0 1 12
− 12 0 3 ( 125
)
= 5
1 ( 20 )
x2 3
1 0 − 31 1
3
0 20
3
3
( 31 )
= 20
2 1 ( 10 )
a3 3
0 0 3
− 13 1 10
3
3
( 32 )
= 5*
Because 2M 3
> M3 , we next enter x1 into the basis. The ratio test indicates that
a3 in the third row shall leave the current basis. Then our next tableau will have
a2 = a3 = 0. After the similar EROs, we have the following new tableau.
basis x1 x2 s1 e2 a2 a3 rhs
z 0 0 0 − 12 1−2M
2
3−2M
2
25
s1 0 0 1 − 18 1
8
− 85 1
4
x2 0 1 0 − 12 1
2
− 21 5
1
x1 1 0 0 2
− 21 3
2
5
4
Because all variables in row 0 have nonpositive coefficients, this is an optimal
tableau; all artificial variables are equal to zero in this tableau, so we have found
the optimal solution to the original LP problem: x1 = 5, x2 = 5, s1 = 41 , e2 = 0
with zmin = 25. Note that to obtain this optimal solution the a2 column could
have been dropped after a2 left the basis (at the conclusion of the first pivot), and
the a3 column could have been dropped after a3 left the basis (at the conclusion
of the second pivot).
Now let’s consider another example, which is obtained by modifying Example 1.
Example 2
min z = 2x1 + 3x2
s.t. 21 x1 + 41 x2 ≤ 4
x1 + 3x2 ≥ 36
x1 + x2 = 10
x1 , x2 ≥ 0.
After going through Steps 1–5 of the Big-M method, we obtain the initial tableau
below.
Because 4M ≥ 2M, we enter x2 into the basis. The ratio test indicates that x2
should be entered in row 3, causing a3 to leave the basis. After entering x2 into
the basis, we obtain the tableau as follows.
basis x1 x2 s1 e2 a2 a3 rhs
z 1 − 2M 0 0 −M 0 3 − 4M 6M + 30
1
s1 4
0 1 0 0 − 14 3
2
a2 −2 0 0 −1 1 −3 6
x2 1 1 0 0 0 1 10
5
objective function. The introduction of such large numbers into the problem can
cause round-off errors and other computational difficulties. For this reason, most
computer codes solve LPs by using the two-phase Simplex method.
Step 1. Modify the constraints so that the rhs of each constraint is nonnegative.
This requires that each constraint with a negative rhs be multiplied through
by −1.
Step 2. Convert the system of constraints to standard form, i.e. add a slack variable
si in the lhs of each ≤ constraint and subtract an excess variable ei from
the lhs of each ≥ constraint.
Step 3. For each constraint without a slack variable si , add an artificial variable ai
in the lhs. Also add the sign restriction ai ≥ 0.
Step 4. For now, ignore the original LP’s objective function. Instead solve an LP
with an objective function “min w = (sum of all the artificial variables)”.
This is called the Phase-I LP. The act of solving the Phase-I LP will force
the artificial variables to be zero.
Because each ai ≥ 0, solving the Phase-I LP will result in one of the follow-
ing three cases:
6
Case 3. The optimal objective value wmin = 0 and at least one artificial variable
remaining in the optimal Phase-I basis:
In this case, we can find an optimal solution to the original LP by
dropping from the optimal Phase-I tableau the columns corresponding
to the nonbasic artificial variables and the variables in the original
standard form that have negative coefficients in row 0 of the optimal
Phase-I tableau, and reintroducing the original objective function.
min w = a2 + a3
1
s.t. x
2 1
+ 14 x2 + s1 = 4
x1 + 3x2 − e2 + a2 = 20
x1 + x2 + a3 = 10
x1 , x2 , s1 , e2 , a2 , a3 ≥ 0.
We have an obvious initial bfs (s1 = 4, a2 = 20, a3 = 10) for Phase I and thus can
generate the initial tableau.
basis x1 x2 s1 e2 a2 a3 rhs
w 0 0 0 0 -1 -1 0
1 1
s1 2 4
1 0 0 0 4
a2 1 3 0 -1 1 0 20
a3 1 1 0 0 0 1 10
Note, however, that we still need to eliminate a2 and a3 in row 0 to satisfy the
canonical form. So the first step in Phase I is always to get rid of the coefficients
−1 in row 0 (above the artificial variables) by adding all rows corresponding to
artificial variables, which are row 2 and row 3 in this case, to row 0. Then We
obtain the following new tableau.
7
basis x1 x2 s1 e2 a2 a3 rhs
w 2 4 0 -1 0 0 30 R0′ ← R0 + R2 + R3
1 1
s1 2 4
1 0 0 0 4
a2 1 3 0 -1 1 0 20
a3 1 1 0 0 0 1 10
The obtained tableau satisfies the conditions: There exists the identity matrix
with all corresponding reduced costs being zeros, and the rhs vector is nonnega-
tive.
Now we can proceed with Simplex procedure. Since Phase-I LP is always a min-
imisation problem, we choose the entering variable by looking for the nonbasic
variable with the most positive reduced cost. So x2 will be entered into the new
basis. By the ratio test, the second component of the basic, a2 , is leaving.
basis x1 x2 s1 e2 a2 a3 rhs
2 1
w 3
0 0 3
- 43 0 10
3
R0′′ ← R0′ − 4R2′′
5 1 1 7
s1 12
0 1 12
- 12 0 3
R1′′ ← R1′ − 41 R2′′
1
x2 3
1 0 - 31 1
3
0 20
3
R2′′ ← 31 R2′
2 1
a3 3
0 0 3
- 13 1 10
3
R3′′ ← R3′ − R2′′
There still exist some positive reduced costs in the current tableau, so the Simplex
procedure must be continued.
8
Again, we need to enter x1 and leave a3 , and do the pivoting. Then the following
Simplex tableau is yielded.
basis x1 x2 s1 e2 a2 a3 rhs
w 0 0 0 0 -1 -1 0
s1 0 0 1 - 18 1
8
- 58 1
4
x2 0 1 0 - 12 1
2
− 12 5
1 1 3
x1 1 0 0 2
-2 2
5
Now all reduced costs are nonpositive, so it is the final optimal Phase-I tableau.
Since we have wmin = 0 and the optimal basis (s1 , x2 , x1 ) = ( 41 , 5, 5), i.e. no
artificial variables are in the optimal Phase-I basis, the problem is an example of
Case 2. We now drop the columns for the artificial variables a2 and a3 (we no
longer need them) and reintroduce the original objective “min z = 2x1 + 3x2 ” to
generate the Phase-II tableau as follows.
basis x1 x2 s1 e2 rhs
z -2 -3 0 0 0
s1 0 0 1 - 18 1
4
x2 0 1 0 - 12 5
1
x1 1 0 0 2
5
Again, before performing Simplex procedure we need to do some EROs for row
0 to make the canonical form as follows.
basis x1 x2 s1 e2 rhs
x2 0 1 0 - 21 5
1
x1 1 0 0 2
5
Since none of the reduced costs is positive, this Simplex tableau is the final one.
So the optimal solution of the original LP in standard form is
1
(x1 , x2 , s1 , e2 ) = (5, 5, , 0)
4
with zmin = 25.
9
Example 2
Then for the second constraint, we need to introduce an artificial variable a1 since
x4 cannot be a part of the initial bfs.
The Phase-I LP is shown as follows:
min w = a1
s.t. 2x1 + 3x2 + x3 = 6
3x1 + x2 − x4 + a1 = 3
x1 ,x2 , x3 ,x4 , a1 ≥ 0
Choose (x3 , a1 ) = (6, 3) as the initial basis and draw up the following tableau:
basis x1 x2 x3 x4 a1 rhs
w 0 0 0 0 -1 0
x3 2 3 1 0 0 6
a1 3 1 0 -1 1 3
basis x1 x2 x3 x4 a1 rhs
w 3 1 0 -1 0 3 R0′ ← R0 + R2
x3 2 3 1 0 0 6
a1 3 1 0 -1 1 3
Now we can progress with the Simplex method. Choose the most positive reduced
cost to determine the entering variable, and find the leaving variable using the
ratio test as follows.
7
Notice that the notation used for slack or excess variables is flexible.
10
basis x1 x2 x3 x4 a1 rhs ratio test
w 3 1 0 -1 0 3
6
x3 2 3 1 0 0 6 2
=3
3
a1 3 1 0 -1 1 3 3
= 1*
Entering x1 and leaving a1 , we do the pivoting and have the following new tableau.
basis x1 x2 x3 x4 a1 rhs
w 0 0 0 0 -1 0
7 2
x3 0 3
1 3
- 23 4
1
x1 1 3
0 - 31 1
3
1
Since no positive reduced cost exists, this is the final tableau. The optimal
objective value is wmin = 0, and a1 is not in the optimal Phase-I basis. This is
another example of Case 2. Hence we can generate Phase-II initial tableau by
combining the original objective function with the constraints from the optimal
Phase-I tableau. In other words, the Phase-I optimal basis (x3 , x1 ) = (4, 1) is
exactly the initial feasible basis of the Phase-II LP.
Dropping the column of artificial variable a1 and reintroducing the original ob-
jective “max z = 4x1 + 5x2 ”, we have the Phase-II tableau as follows.
basis x1 x2 x3 x4 rhs
z -4 -5 0 0 0
7 2
x3 0 3
1 3
4
1
x1 1 3
0 - 31 1
Again, some EROs in row 0 are needed to make the canonical form.
basis x1 x2 x3 x4 rhs
z 0 - 11
3
0 - 43 4 R0′ ← R0 + 4R2
7 2
x3 0 3
1 3
4
1
x1 1 3
0 - 31 1
Now we can proceed with the Simplex method. Choose the most negative reduced
cost to determine the entering variable, and find the leaving variable using the
ratio test.
11
basis x1 x2 x3 x4 rhs ratio test
z 0 - 11
3
0 - 43 4
7 2 4 12
x3 0 3
1 3
4 ( 37 )
= 7
*
1
x1 1 3
0 - 31 1 1
( 31 )
=3
Entering x2 and leaving x3 , we do the pivoting and have the following new tableau.
basis x1 x2 x3 x4 rhs
11
z 0 0 7
- 72 72
7
R0′′ ← R0′ + 11 ′′
3
R1
3 2 12
x2 0 1 7 7 7
R1′′ ← 37 R1′ (go first)
x1 1 0 - 71 - 73 3
7
R2′′ ← R2′ − 13 R1′′
3 2 12 ( 12 )
x2 0 1 7 7 7
7
2 = 6*
7
x1 0 0 - 71 - 37 3
7
null
Entering x4 and leaving x2 , we do the pivoting and have the following new tableau.
basis x1 x2 x3 x4 rhs
z 0 1 2 0 12 R0′′′ ← R0′′ + R1′′
7 3
x4 0 2 2
1 6 R1′′′ ← 72 R1′′ (go first)
3 1
x1 1 2 2
0 3 R2′′′ ← R2′′ + 37 R1′′′
Since none of the reduced costs is negative, this is the final Phase-II tableau.
The optimal solution to the original LP is (x1 , x2 ) = (3, 0) with zmax = 12.
12
Example 3
The Phase-I LP is
min w = a1 + a2
1 1
s.t. x
2 1
+ x
4 2
+ x 3 = 4
x1 + 3x2 − x4 + a1 = 36
x1 + x2 + a2 = 10
x1 ,x2 , x3 ,x4 , a1 , a2 ≥ 0
After one Simplex iteration, we obtain the final Phase-I tableau below.
basis x1 x2 x3 x4 a1 a2 rhs
w -2 0 0 -1 0 -4 6
1
x3 4
0 1 0 0 - 14 3
2
a1 -2 0 0 -1 1 -3 6
x2 1 1 0 1 0 1 10
Example 4
Notice that we can use x4 as a basic variable for the fourth constraint. So we use
artificial variables a1 , a2 , a3 as basic variables for the first three constraints. The
Phase-I objective is “min w = a1 + a2 + a3 ”. After one Simplex iteration, we can
get the final Phase-I tableau below.
13
basis x1 x2 x3 x4 x5 x6 a1 a2 a3 rhs
w -1 0 0 0 0 0 0 0 -1 0
a1 1 -1 0 0 2 0 1 0 0 0
a2 -2 1 0 0 -2 0 0 1 0 0
x3 1 0 1 0 1 -1 0 0 1 3
x4 -1 2 0 1 1 2 0 0 -1 1
Notice that we have wmin = 0 and two artificial variables, a1 and a2 , remain
in the optimal Phase-I basis (of course, at a zero level). This is an example of
Case 3. To set up the initial Phase-II tableau, we drop the columns of the nonbasic
artificial variable(s), which is a3 in this example, and of the original variables with
a negative coefficient in the optimal Phase-I tableau. In this instance, there is
only one such variable, which is x1 . So, the initial tableau for Phase II is shown
below.
basis x2 x3 x4 x5 x6 a1 a2 rhs
z -10 0 0 -7 -14 0 0 0
a1 -1 0 0 2 0 1 0 0
a2 1 0 0 -2 0 0 1 0
x3 0 1 0 1 -1 0 0 3
x4 2 0 1 1 2 0 0 1
Since the row-0 coefficients, i.e. reduced costs, of all the basic variables are zero,
this is a canonical form. Then we commence the first Simplex iteration by entering
x6 and leaving x4 . After the pivoting procedure, we have the following tableau.
basis x2 x3 x4 x5 x6 a1 a2 rhs
z 4 0 7 0 0 0 0 7
a1 -1 0 0 2 0 1 0 0
a2 1 0 0 -2 0 0 1 0
1 3 7
x3 1 1 2 2
0 0 0 2
1 1 1
x6 1 0 2 2
1 0 0 2
Since all reduced costs are nonnegative, this is the optimal Phase-II tableau. The
optimal solution to the original LP is
7 1
(x1 , x2 , x3 , x4 , x5 , x6 ) = (0, 0, , 0, 0, )
2 2
with the optimal objective value zmax = 7.
Further reading: Section 4.12 an 4.13 in the reference book “Operations Research: Appli-
cations and Algorithms” (Winston, 2004)
14