Chapter 4 Linear Programming: The Simplex Method
Chapter 4
Linear Programming: The Simplex Method
n
An Overview of the Simplex Method
n
Standard Form
n
Tableau Form
n
Setting Up the Initial Simplex Tableau
n
Improving the Solution
n
Calculating the Next Tableau
n
Solving a Minimization Problem
n
Special Cases
Overview of the Simplex Method
n
Steps Leading to the Simplex Method
Steps Leading to the Simplex Method
Formulate
Formulate
Problem
Problem
as LP
as LP
Put In
Put In
Standard
Standard
Form
Form
Put In
Put In
Tableau
Tableau
Form
Form
Execute
Execute
Simplex
Simplex
Method
Method
Example: Initial Formulation
n
A Minimization Problem
A Minimization Problem
MIN 2
MIN 2
x
x
1
1
- 3
- 3
x
x
2
2
- 4
- 4
x
x
3
3
s. t.
s. t.
x
x
1
1
+
+
x
x
2
2
+
+
x
x
3
3
<
<
30
30
2
2
x
x
1
1
+
+
x
x
2
2
+ 3
+ 3
x
x
3
3
>
>
60
60
x
x
1
1
-
-
x
x
2
2
+ 2
+ 2
x
x
3
3
= 20
= 20
x
x
1
1
,
,
x
x
2
2
,
,
x
x
3
3
>
>
0
0
Standard Form
n
An LP is in
standard form
when:
•
All variables are non-negative
•
All constraints are equalities
n
Putting an LP formulation into
standard form
involves:
•
Adding
slack variables
to “
<
“ constraints
•
Subtracting
surplus variables
from “
>
”
constraints.
Example: Standard Form
n
Problem in Standard Form
Problem in Standard Form
MIN
MIN
2
2
x
x
1
1
- 3
- 3
x
x
2
2
- 4
- 4
x
x
3
3
s. t.
s. t.
x
x
1
1
+
+
x
x
2
2
+
+
x
x
3
3
+
+
s
s
1
1
= 30
= 30
2
2
x
x
1
1
+
+
x
x
2
2
+ 3
+ 3
x
x
3
3
-
-
s
s
2
2
= 60
= 60
x
x
1
1
-
-
x
x
2
2
+ 2
+ 2
x
x
3
3
= 20
= 20
x
x
1
1
,
,
x
x
2
2
,
,
x
x
3
3
,
,
s
s
1
1
,
,
s
s
2
2
>
>
0
0
Tableau Form
n
A set of equations is in
tableau form
if for each
equation:
•
its right hand side (RHS) is non-negative, and
•
there is a basic variable. (A
basic variable
for an
equation is a variable whose coefficient in the
equation is +1 and whose coefficient in all other
equations of the problem is 0.)
n
To generate an initial tableau form:
•
An artificial variable must be added to each
constraint that does not have a basic variable.
Example: Tableau Form
n
Problem in Tableau Form
Problem in Tableau Form
MIN 2
MIN 2
x
x
1
1
- 3
- 3
x
x
2
2
- 4
- 4
x
x
3
3
+ 0
+ 0
s
s
1
1
- 0
- 0
s
s
2
2
+
+
Ma
Ma
2
2
+
+
Ma
Ma
3
3
s. t.
s. t.
x
x
1
1
+
+
x
x
2
2
+
+
x
x
3
3
+
+
s
s
1
1
= 30
= 30
2
2
x
x
1
1
+
+
x
x
2
2
+ 3
+ 3
x
x
3
3
-
-
s
s
2
2
+
+
a
a
2
2
= 60
= 60
x
x
1
1
-
-
x
x
2
2
+ 2
+ 2
x
x
3
3
+
+
a
a
3
3
= 20
= 20
x
x
1
1
,
,
x
x
2
2
,
,
x
x
3
3
,
,
s
s
1
1
,
,
s
s
2
2
,
,
a
a
2
2
,
,
a
a
3
3
>
>
0
0
Simplex Tableau
n
The
simplex tableau
is a convenient means for
performing the calculations required by the simplex
method.
Setting Up Initial Simplex Tableau
n
Step 1:
Step 1:
If the problem is a minimization problem,
If the problem is a minimization problem,
multiply the objective function by -1.
multiply the objective function by -1.
n
Step 2:
Step 2:
If the problem formulation contains any
If the problem formulation contains any
constraints with negative right-hand sides,
constraints with negative right-hand sides,
multiply each constraint by -1.
multiply each constraint by -1.
n
Step 3:
Step 3:
Add a slack variable to each
Add a slack variable to each
<
<
constraint.
constraint.
n
Step 4:
Step 4:
Subtract a surplus variable and add an
Subtract a surplus variable and add an
artificial variable to each
artificial variable to each
>
>
constraint.
constraint.
Setting Up Initial Simplex Tableau
n
Step 5:
Step 5:
Add an artificial variable to each = constraint.
Add an artificial variable to each = constraint.
n
Step 6:
Step 6:
Set each slack and surplus variable's
Set each slack and surplus variable's
coefficient in the objective function equal to
coefficient in the objective function equal to
zero.
zero.
n
Step 7:
Step 7:
Set each artificial variable's coefficient in the
Set each artificial variable's coefficient in the
objective function equal to -
objective function equal to -
M
M
, where
, where
M
M
is a
is a
very large number.
very large number.
n
Step 8:
Step 8:
Each slack and artificial variable becomes one
Each slack and artificial variable becomes one
of the basic variables in the initial basic
of the basic variables in the initial basic
feasible solution.
feasible solution.
Simplex Method
n
Step 1: Determine Entering Variable
Step 1: Determine Entering Variable
•
Identify the variable with the most positive value
Identify the variable with the most positive value
in the
in the
c
c
j
j
-
-
z
z
j
j
row. (The entering column is called
row. (The entering column is called
the
the
pivot column
pivot column
.)
.)
n
Step 2: Determine Leaving Variable
Step 2: Determine Leaving Variable
•
For each positive number in the entering column,
For each positive number in the entering column,
compute the ratio of the right-hand side values
compute the ratio of the right-hand side values
divided by these entering column values.
divided by these entering column values.
•
If there are no positive values in the entering
If there are no positive values in the entering
column, STOP; the problem is unbounded.
column, STOP; the problem is unbounded.
•
Otherwise, select the variable with the minimal
Otherwise, select the variable with the minimal
ratio. (The leaving row is called the
ratio. (The leaving row is called the
pivot row
pivot row
.)
.)
Simplex Method
n
Step 3: Generate Next Tableau
Step 3: Generate Next Tableau
•
Divide the pivot row by the
Divide the pivot row by the
pivot element
pivot element
(the
(the
entry at the intersection of the pivot row and pivot
entry at the intersection of the pivot row and pivot
column) to get a new row. We denote this new
column) to get a new row. We denote this new
row as (row *).
row as (row *).
•
Replace each non-pivot row
Replace each non-pivot row
i
i
with:
with:
[new row
[new row
i
i
] = [current row
] = [current row
i
i
] - [(
] - [(
a
a
ij
ij
) x (row *)],
) x (row *)],
where
where
a
a
ij
ij
is the value in entering column
is the value in entering column
j
j
of row
of row
i
i
Simplex Method
n
Step 4: Calculate
Step 4: Calculate
z
z
j
j
Row for New Tableau
Row for New Tableau
•
For each column
For each column
j
j
, multiply the objective function
, multiply the objective function
coefficients of the basic variables by the
coefficients of the basic variables by the
corresponding numbers in column
corresponding numbers in column
j
j
and sum
and sum
them.
them.
Simplex Method
n
Step 5: Calculate
Step 5: Calculate
c
c
j
j
-
-
z
z
j
j
Row for New Tableau
Row for New Tableau
•
For each column
For each column
j
j
, subtract the
, subtract the
z
z
j
j
row from the
row from the
c
c
j
j
row.
row.
•
If none of the values in the
If none of the values in the
c
c
j
j
-
-
z
z
j
j
row are positive, GO
row are positive, GO
TO STEP 1.
TO STEP 1.
•
If there is an artificial variable in the basis with a
If there is an artificial variable in the basis with a
positive value, the problem is infeasible. STOP.
positive value, the problem is infeasible. STOP.
•
Otherwise, an optimal solution has been found. The
Otherwise, an optimal solution has been found. The
current values of the basic variables are optimal. The
current values of the basic variables are optimal. The
optimal values of the non-basic variables are all zero.
optimal values of the non-basic variables are all zero.
•
If any non-basic variable's
If any non-basic variable's
c
c
j
j
-
-
z
z
j
j
value is 0, alternate
value is 0, alternate
optimal solutions might exist. STOP.
optimal solutions might exist. STOP.
Example: Simplex Method
n
Solve the following problem by the simplex method:
Solve the following problem by the simplex method:
Max 12
Max 12
x
x
1
1
+ 18
+ 18
x
x
2
2
+ 10
+ 10
x
x
3
3
s.t. 2
s.t. 2
x
x
1
1
+ 3
+ 3
x
x
2
2
+ 4
+ 4
x
x
3
3
<
<
50
50
x
x
1
1
-
-
x
x
2
2
-
-
x
x
3
3
>
>
0
0
x
x
2
2
- 1.5
- 1.5
x
x
3
3
>
>
0
0
x
x
1
1
,
,
x
x
2
2
,
,
x
x
3
3
>
>
0
0
n
Writing the Problem in Tableau Form
Writing the Problem in Tableau Form
We can avoid introducing artificial variables to
We can avoid introducing artificial variables to
the second and third constraints by multiplying each
the second and third constraints by multiplying each
by -1 (making them
by -1 (making them
<
<
constraints). Thus, slack
constraints). Thus, slack
variables
variables
s
s
1
1
,
,
s
s
2
2
, and
, and
s
s
3
3
are added to the three
are added to the three
constraints.
constraints.
Max 12
Max 12
x
x
1
1
+ 18
+ 18
x
x
2
2
+ 10
+ 10
x
x
3
3
+ 0
+ 0
s
s
1
1
+ 0
+ 0
s
s
2
2
+ 0
+ 0
s
s
3
3
s.t. 2
s.t. 2
x
x
1
1
+ 3
+ 3
x
x
2
2
+ 4
+ 4
x
x
3
3
+
+
s
s
1
1
= 50
= 50
-
-
x
x
1
1
+
+
x
x
2
2
+
+
x
x
3
3
+
+
s
s
2
2
= 0
= 0
-
-
x
x
2
2
+ 1.5
+ 1.5
x
x
3
3
+
+
s
s
3
3
= 0
= 0
x
x
1
1
,
,
x
x
2
2
,
,
x
x
3
3
,
,
s
s
1
1
,
,
s
s
2
2
,
,
s
s
3
3
>
>
0
0
Example: Simplex Method
Example: Simplex Method
n
Initial Simplex Tableau
Initial Simplex Tableau
x
x
1
1
x
x
2
2
x
x
3
3
s
s
1
1
s
s
2
2
s
s
3
3
Basis
Basis
c
c
B
B
12 18 10 0 0 0
12 18 10 0 0 0
s
s
1
1
0 2 3 4 1 0 0 50
0 2 3 4 1 0 0 50
s
s
2
2
0 -1 1 1 0 1 0 0 (* row)
0 -1 1 1 0 1 0 0 (* row)
s
s
3
3
0 0 -1 1.5 0 0 1 0
0 0 -1 1.5 0 0 1 0
z
z
j
j
0 0 0 0 0 0 0
0 0 0 0 0 0 0
c
c
j
j
-
-
z
z
j
j
12 18 10 0 0 0
12 18 10 0 0 0
Example: Simplex Method
n
Iteration 1
Iteration 1
•
Step 1: Determine the Entering Variable
Step 1: Determine the Entering Variable
The most positive
The most positive
c
c
j
j
-
-
z
z
j
j
= 18. Thus
= 18. Thus
x
x
2
2
is the entering
is the entering
variable.
variable.
•
Step 2: Determine the Leaving Variable
Step 2: Determine the Leaving Variable
Take the ratio between the right hand side and
Take the ratio between the right hand side and
positive numbers in the
positive numbers in the
x
x
2
2
column:
column:
50/3 = 16 2/3
50/3 = 16 2/3
0/1 = 0 minimum
0/1 = 0 minimum
s
s
2
2
is the leaving variable and the 1 is the pivot
is the leaving variable and the 1 is the pivot
element.
element.
Example: Simplex Method
n
Iteration 1 (continued)
Iteration 1 (continued)
•
Step 3: Generate New Tableau
Step 3: Generate New Tableau
Divide the second row by 1, the pivot element.
Divide the second row by 1, the pivot element.
Call the "new" (in this case, unchanged) row the "*
Call the "new" (in this case, unchanged) row the "*
row".
row".
Subtract 3 x (* row) from row 1.
Subtract 3 x (* row) from row 1.
Subtract -1 x (* row) from row 3.
Subtract -1 x (* row) from row 3.
New rows 1, 2, and 3 are shown in the upcoming
New rows 1, 2, and 3 are shown in the upcoming
tableau.
tableau.
Example: Simplex Method
n
Iteration 1 (continued)
Iteration 1 (continued)
•
Step 4: Calculate
Step 4: Calculate
z
z
j
j
Row for New Tableau
Row for New Tableau
The new
The new
z
z
j
j
row values are obtained by
row values are obtained by
multiplying the
multiplying the
c
c
B
B
column by each column, element
column by each column, element
by element and summing.
by element and summing.
For example,
For example,
z
z
1
1
= 5(0) + -1(18) + -1(0) = -18.
= 5(0) + -1(18) + -1(0) = -18.
Example: Simplex Method
n
Iteration 1 (continued)
Iteration 1 (continued)
•
Step 5: Calculate
Step 5: Calculate
c
c
j
j
-
-
z
z
j
j
Row for New Tableau
Row for New Tableau
The new
The new
c
c
j
j
-
-
z
z
j
j
row values are obtained by
row values are obtained by
subtracting
subtracting
z
z
j
j
value in a column from the
value in a column from the
c
c
j
j
value
value
in the same column.
in the same column.
For example,
For example,
c
c
1
1
-
-
z
z
1
1
= 12 - (-18) = 30.
= 12 - (-18) = 30.
Example: Simplex Method
n
Iteration 1 (continued) - New Tableau
Iteration 1 (continued) - New Tableau
x
x
1
1
x
x
2
2
x
x
3
3
s
s
1
1
s
s
2
2
s
s
3
3
Basis
Basis
c
c
B
B
12 18 10 0 0 0
12 18 10 0 0 0
s
s
1
1
0 5 0 1 1 -3 0 50 (* row)
0 5 0 1 1 -3 0 50 (* row)
x
x
2
2
18 -1 1 1 0 1 0 0
18 -1 1 1 0 1 0 0
s
s
3
3
0 -1 0 2.5 0 1 1 0
0 -1 0 2.5 0 1 1 0
z
z
j
j
-18 18 18 0 18 0 0
-18 18 18 0 18 0 0
c
c
j
j
-
-
z
z
j
j
30 0 -8 0 -18 0
30 0 -8 0 -18 0
Example: Simplex Method
n
Iteration 2
Iteration 2
•
Step 1: Determine the Entering Variable
Step 1: Determine the Entering Variable
The most positive
The most positive
c
c
j
j
-
-
z
z
j
j
= 30.
= 30.
x
x
1
1
is the entering
is the entering
variable.
variable.
•
Step 2: Determine the Leaving Variable
Step 2: Determine the Leaving Variable
Take the ratio between the right hand side and
Take the ratio between the right hand side and
positive numbers in the
positive numbers in the
x
x
1
1
column:
column:
50/5 = 10 minimum
50/5 = 10 minimum
There are no ratios for the second and third rows
There are no ratios for the second and third rows
because their column elements (-1) are negative.
because their column elements (-1) are negative.
Thus,
Thus,
s
s
1
1
(corresponding to row 1) is the leaving
(corresponding to row 1) is the leaving
variable and 5 is the pivot element.
variable and 5 is the pivot element.
Example: Simplex Method
n
Iteration 2 (continued)
Iteration 2 (continued)
•
Step 3: Generate New Tableau
Step 3: Generate New Tableau
Divide row 1 by 5, the pivot element. (Call this new
Divide row 1 by 5, the pivot element. (Call this new
row 1 the "* row").
row 1 the "* row").
Subtract (-1) x (* row) from the second row.
Subtract (-1) x (* row) from the second row.
Subtract (-1) x (* row) from the third row.
Subtract (-1) x (* row) from the third row.
•
Step 4: Calculate
Step 4: Calculate
z
z
j
j
Row for New Tableau
Row for New Tableau
The new
The new
z
z
j
j
row values are obtained by
row values are obtained by
multiplying the
multiplying the
c
c
B
B
column by each column,
column by each column,
element by element and summing.
element by element and summing.
For example,
For example,
z
z
3
3
= .2(12) + 1.2(18) + .2(0) = 24.
= .2(12) + 1.2(18) + .2(0) = 24.
Example: Simplex Method
n
Iteration 2 (continued)
Iteration 2 (continued)
•
Step 5: Calculate
Step 5: Calculate
c
c
j
j
-
-
z
z
j
j
Row for New Tableau
Row for New Tableau
The new
The new
c
c
j
j
-
-
z
z
j
j
row values are obtained by
row values are obtained by
subtracting
subtracting
z
z
j
j
value in a column from the
value in a column from the
c
c
j
j
value in
value in
the same column.
the same column.
For example, c
For example, c
3
3
-z
-z
3
3
= 10 - (24) = -14.
= 10 - (24) = -14.
Since there are no positive numbers in the
Since there are no positive numbers in the
c
c
j
j
-
-
z
z
j
j
row, this tableau is optimal. The optimal solution
row, this tableau is optimal. The optimal solution
is:
is:
x
x
1
1
= 10;
= 10;
x
x
2
2
= 10;
= 10;
x
x
3
3
= 0;
= 0;
s
s
1
1
= 0;
= 0;
s
s
2
2
= 0 s
= 0 s
3
3
= 10, and
= 10, and
the optimal value of the objective function is 300.
the optimal value of the objective function is 300.
Example: Simplex Method
n
Iteration 2 (continued) – Final Tableau
Iteration 2 (continued) – Final Tableau
x
x
1
1
x
x
2
2
x
x
3
3
s
s
1
1
s
s
2
2
s
s
3
3
Basis
Basis
c
c
B
B
12 18 10 0 0 0
12 18 10 0 0 0
x
x
1
1
12 1 0 .2 .2 -.6 0 10 (* row)
12 1 0 .2 .2 -.6 0 10 (* row)
x
x
2
2
18 0 1 1.2 .2 .4 0 10
18 0 1 1.2 .2 .4 0 10
s
s
3
3
0 0 0 2.7 .2 .4 1 10
0 0 0 2.7 .2 .4 1 10
z
z
j
j
12 18 24 6 0 0 300
12 18 24 6 0 0 300
c
c
j
j
-
-
z
z
j
j
0 0 -14 -6 0 0
0 0 -14 -6 0 0
Exercise: Simplex Method
Solution: Simplex Method
n
To solve this problem using the simplex method, we
first multiply the objective function by 1 to convert
the minimization problem into the following
equivalent maximization problem:
Solution: Simplex Method
n
The tableau form for this problem is as follows:
Solution: Simplex Method
n
The initial simplex tableau is shown here:
Solution: Simplex Method
n
At the first iteration,
x
1
is brought into the basis and
a
1
is removed. After dropping the
a
1
column from the
tableau, the result of the first iteration is as follows:
Solution: Simplex Method
n
Continuing with two more iterations of the simplex
method provides the following final simplex tableau:
Special Cases
n
Infeasibility
n
Unboundedness
n
Alternative Optimal Solution
n
Degeneracy
Infeasibility
n
Infeasibility
is detected in the simplex method when
an artificial variable remains positive in the final
tableau.
Example: Infeasibility
n
LP Formulation
LP Formulation
MAX 2
MAX 2
x
x
1
1
+ 6
+ 6
x
x
2
2
s. t. 4
s. t. 4
x
x
1
1
+ 3
+ 3
x
x
2
2
<
<
12
12
2
2
x
x
1
1
+
+
x
x
2
2
>
>
8
8
x
x
1
1
,
,
x
x
2
2
>
>
0
0
Example: Infeasibility
n
Final Tableau
Final Tableau
x
x
1
1
x
x
2
2
s
s
1
1
s
s
2
2
a
a
2
2
Basis
Basis
C
C
B
B
2
2
6
6
0
0
0 -
0 -
M
M
x
x
1
1
2
2
1 3/4
1 3/4
1/4
1/4
0
0
0
0
3
3
a
a
2
2
-
-
M
M
0 -1/2 -1/2
0 -1/2 -1/2
-1
-1
1
1
2
2
z
z
j
j
2 (1/2)
2 (1/2)
M
M
(1/2)
(1/2)
M
M
M
M
-
-
M
M
-2
-2
M
M
+3/2
+3/2
+1/2
+1/2
+6
+6
c
c
j
j
-
-
z
z
j
j
0 -(1/2)
0 -(1/2)
M
M
-(1/2)
-(1/2)
M
M
-
-
M
M
0
0
+9/2
+9/2
-1/2
-1/2
Example: Infeasibility
In the previous slide we see that the tableau is
In the previous slide we see that the tableau is
the final tableau because all
the final tableau because all
c
c
j
j
-
-
z
z
j
j
<
<
0. However, an
0. However, an
artificial variable is still positive, so the problem is
artificial variable is still positive, so the problem is
infeasible.
infeasible.
Unboundedness
n
A linear program has an
unbounded solution
if all
entries in an entering column are non-positive.
Example: Unboundedness
n
LP Formulation
LP Formulation
MAX 2
MAX 2
x
x
1
1
+ 6
+ 6
x
x
2
2
s. t. 4
s. t. 4
x
x
1
1
+ 3
+ 3
x
x
2
2
>
>
12
12
2
2
x
x
1
1
+
+
x
x
2
2
>
>
8
8
x
x
1
1
,
,
x
x
2
2
>
>
0
0
Example: Unboundedness
n
Final Tableau
Final Tableau
x
x
1
1
x
x
2
2
s
s
1
1
s
s
2
2
Basis
Basis
c
c
B
B
3
3
4
4
0
0
0
0
x
x
2
2
4
4
3
3
1
1
0
0
-1
-1
8
8
s
s
1
1
0
0
2
2
0
0
1
1
-1
-1
3
3
z
z
j
j
12
12
4
4
0
0
-4
-4
32
32
c
c
j
j
-
-
z
z
j
j
-9
-9
0
0
0
0
4
4
Example: Unboundedness
In the previous slide we see that
c
4
-
z
4
= 4 (is
positive), but its column is all non-positive. This
indicates that the problem is unbounded.
Alternative Optimal Solution
n
A linear program has
alternate optimal solutions
if
the final tableau has a
c
j
-
z
j
value equal to 0 for a
non-basic variable.
Example: Alternative Optimal Solution
n
Final Tableau
Final Tableau
x
x
1
1
x
x
2
2
x
x
3
3
s
s
1
1
s
s
2
2
s
s
3
3
s
s
4
4
Basis
Basis
c
c
B
B
2
2
4 6 0
4 6 0
0 0
0 0
0
0
s
s
3
3
0 0
0 0
0 2 4
0 2 4
-2 1
-2 1
0 8
0 8
x
x
2
2
4 0
4 0
1 2 2
1 2 2
-1 0
-1 0
0 6
0 6
x
x
1
1
2 1
2 1
0 -1 1
0 -1 1
2 0
2 0
0 4
0 4
s
s
4
4
0 0
0 0
0 1 3
0 1 3
2 0
2 0
1 12
1 12
z
z
j
j
2
2
4 6 10
4 6 10
0 0
0 0
0 32
0 32
c
c
j
j
–
–
z
z
j
j
0
0
0 0 -10
0 0 -10
0 0
0 0
0
0
In the previous slide we see that the optimal
solution is:
x
1
= 4,
x
2
= 6,
x
3
= 0, and
z
= 32
Note that
x
3
is non-basic and its
c
3
-
z
3
= 0. This 0
indicates that if
x
3
were increased, the value of the
objective function would not change.
Another optimal solution can be found by choosing
x
3
as the entering variable and performing one iteration
of the simplex method. The new tableau on the next
slide shows an alternative optimal solution is:
x
1
= 7,
x
2
= 0,
x
3
= 3, and
z
= 32
Example: Alternative Optimal Solution
Example: Alternative Optimal Solution
n
New Tableau
New Tableau
x
x
1
1
x
x
2
2
x
x
3
3
s
s
1
1
s
s
2
2
s
s
3
3
s
s
4
4
Basis
Basis
c
c
B
B
2 4 6
2 4 6
0 0
0 0
0 0
0 0
s
s
3
3
0
0
0 -1 0
0 -1 0
2 -1
2 -1
1 0 2
1 0 2
x
x
3
3
6
6
0 .5 1
0 .5 1
1 - .5 0 0 3
1 - .5 0 0 3
x
x
1
1
2
2
1 .5 0
1 .5 0
2 1.5 0 0 7
2 1.5 0 0 7
s
s
4
4
0
0
0 - .5 0 2 2.5 0 1 9
0 - .5 0 2 2.5 0 1 9
z
z
j
j
2 4 6 10
2 4 6 10
0
0
0 0 32
0 0 32
c
c
j
j
-
-
z
z
j
j
0 0 0 -10
0 0 0 -10
0
0
0 0
0 0
Degeneracy
n
A
degenerate solution
to a linear program is one in
which at least one of the basic variables equals 0.
n
This can occur at formulation or if there is a tie for
the minimizing value in the ratio test to determine
the leaving variable.
n
When degeneracy occurs, an optimal solution may
have been attained even though some
c
j
–
z
j
> 0.
n
Thus, the condition that
c
j
–
z
j
<
0 is sufficient for
optimality, but not necessary.
Dive into the foundational concepts and practical implementation of the Simplex Method for solving linear programming problems. Explore how to set up and improve the Simplex tableau, calculate subsequent steps, and handle special cases efficiently. From standard form to minimizing objectives, this guide equips you with the essential knowledge to tackle optimization challenges.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Chapter 4 Linear Programming: The Simplex Method An Overview of the Simplex Method Standard Form Tableau Form Setting Up the Initial Simplex Tableau Improving the Solution Calculating the Next Tableau Solving a Minimization Problem Special Cases 1
Overview of the Simplex Method Steps Leading to the Simplex Method Formulate Problem as LP Put In Standard Form Put In Tableau Form Execute Simplex Method 2
Example: Initial Formulation A Minimization Problem MIN 2x1 - 3x2 - 4x3 s. t. x1 + x2 + x3 < 30 2x1 + x2 + 3x3 > 60 x1 - x2 + 2x3 = 20 x1, x2, x3 > 0 3
Standard Form An LP is in standard form when: All variables are non-negative All constraints are equalities Putting an LP formulation into standard form involves: Adding slack variables to < constraints Subtracting surplus variables from > constraints. 4
Example: Standard Form Problem in Standard Form MIN 2x1 - 3x2 - 4x3 s. t. x1 + x2 + x3 + s1 = 30 2x1 + x2 + 3x3 - s2 = 60 x1 - x2 + 2x3 = 20 x1, x2, x3, s1, s2 > 0 5
Tableau Form A set of equations is in tableau form if for each equation: its right hand side (RHS) is non-negative, and there is a basic variable. (A basic variable for an equation is a variable whose coefficient in the equation is +1 and whose coefficient in all other equations of the problem is 0.) To generate an initial tableau form: An artificial variable must be added to each constraint that does not have a basic variable. 6
Example: Tableau Form Problem in Tableau Form MIN 2x1 - 3x2 - 4x3 + 0s1 - 0s2 + Ma2 + Ma3 s. t. x1 + x2 + x3 + s1 = 30 2x1 + x2 + 3x3 - s2 + a2 = 60 x1 - x2 + 2x3 + a3 = 20 x1, x2, x3, s1, s2, a2, a3 > 0 7
Simplex Tableau The simplex tableau is a convenient means for performing the calculations required by the simplex method. 8
Setting Up Initial Simplex Tableau Step 1: If the problem is a minimization problem, multiply the objective function by -1. Step 2: If the problem formulation contains any constraints with negative right-hand sides, multiply each constraint by -1. Step 3: Add a slack variable to each < constraint. Step 4: Subtract a surplus variable and add an artificial variable to each > constraint. 9
Setting Up Initial Simplex Tableau Step 5: Add an artificial variable to each = constraint. Step 6: Set each slack and surplus variable's coefficient in the objective function equal to zero. Step 7: Set each artificial variable's coefficient in the objective function equal to -M, where M is a very large number. Step 8: Each slack and artificial variable becomes one of the basic variables in the initial basic feasible solution. 10
Simplex Method Step 1: Determine Entering Variable Identify the variable with the most positive value in the cj - zj row. (The entering column is called the pivot column.) Step 2: Determine Leaving Variable For each positive number in the entering column, compute the ratio of the right-hand side values divided by these entering column values. If there are no positive values in the entering column, STOP; the problem is unbounded. Otherwise, select the variable with the minimal ratio. (The leaving row is called the pivot row.) 11
Simplex Method Step 3: Generate Next Tableau Divide the pivot row by the pivot element (the entry at the intersection of the pivot row and pivot column) to get a new row. We denote this new row as (row *). Replace each non-pivot row i with: [new row i] = [current row i] - [(aij) x (row *)], where aij is the value in entering column j of row i 12
Simplex Method Step 4: Calculate zj Row for New Tableau For each column j, multiply the objective function coefficients of the basic variables by the corresponding numbers in column j and sum them. 13
Simplex Method Step 5: Calculate cj - zj Row for New Tableau For each column j, subtract the zj row from the cjrow. If none of the values in the cj - zj row are positive, GO TO STEP 1. If there is an artificial variable in the basis with a positive value, the problem is infeasible. STOP. Otherwise, an optimal solution has been found. The current values of the basic variables are optimal. The optimal values of the non-basic variables are all zero. If any non-basic variable's cj - zj value is 0, alternate optimal solutions might exist. STOP. 14
Example: Simplex Method Solve the following problem by the simplex method: Max 12x1 + 18x2 + 10x3 s.t. 2x1 + 3x2 + 4x3 < 50 x1 - x2 - x3 > 0 x2 - 1.5x3 > 0 x1, x2, x3 > 0 15
Example: Simplex Method Writing the Problem in Tableau Form We can avoid introducing artificial variables to the second and third constraints by multiplying each by -1 (making them < constraints). Thus, slack variables s1, s2, and s3 are added to the three constraints. Max 12x1 + 18x2 + 10x3 + 0s1 + 0s2 + 0s3 s.t. 2x1 + 3x2 + 4x3 + s1 = 50 - x1 + x2 + x3 + s2 = 0 - x2 + 1.5x3 + s3 = 0 x1, x2, x3, s1, s2, s3 > 0 16
Example: Simplex Method Initial Simplex Tableau x1x2 x3s1s2s3 Basis cB 12 18 10 0 0 0 s1 0 2 3 4 1 0 0 50 s2 0 -1 1 1 0 1 0 0 (* row) s3 0 0 -1 1.5 0 0 1 0 zj 0 0 0 0 0 0 0 cj - zj 12 18 10 0 0 0 17
Example: Simplex Method Iteration 1 Step 1: Determine the Entering Variable The most positive cj - zj = 18. Thus x2 is the entering variable. Step 2: Determine the Leaving Variable Take the ratio between the right hand side and positive numbers in the x2 column: 50/3 = 16 2/3 0/1 = 0 minimum s2 is the leaving variable and the 1 is the pivot element. 18
Example: Simplex Method Iteration 1 (continued) Step 3: Generate New Tableau Divide the second row by 1, the pivot element. Call the "new" (in this case, unchanged) row the "* row". Subtract 3 x (* row) from row 1. Subtract -1 x (* row) from row 3. New rows 1, 2, and 3 are shown in the upcoming tableau. 19
Example: Simplex Method Iteration 1 (continued) Step 4: Calculate zj Row for New Tableau The new zj row values are obtained by multiplying the cB column by each column, element by element and summing. For example, z1 = 5(0) + -1(18) + -1(0) = -18. 20
Example: Simplex Method Iteration 1 (continued) Step 5: Calculate cj - zj Row for New Tableau The new cj-zjrow values are obtained by subtracting zj value in a column from the cj value in the same column. For example, c1-z1 = 12 - (-18) = 30. 21
Example: Simplex Method Iteration 1 (continued) - New Tableau Basis cB 12 18 10 0 0 0 s1 0 5 0 1 1 -3 0 50 (* row) x2 18 -1 1 1 0 1 0 0 s3 0 -1 0 2.5 0 1 1 0 zj -18 18 18 0 18 0 0 cj - zj 30 0 -8 0 -18 0 x1x2 x3s1s2s3 22
Example: Simplex Method Iteration 2 Step 1: Determine the Entering Variable The most positive cj - zj = 30. x1 is the entering variable. Step 2: Determine the Leaving Variable Take the ratio between the right hand side and positive numbers in the x1 column: 50/5 = 10 minimum There are no ratios for the second and third rows because their column elements (-1) are negative. Thus, s1 (corresponding to row 1) is the leaving variable and 5 is the pivot element. 23
Example: Simplex Method Iteration 2 (continued) Step 3: Generate New Tableau Divide row 1 by 5, the pivot element. (Call this new row 1 the "* row"). Subtract (-1) x (* row) from the second row. Subtract (-1) x (* row) from the third row. Step 4: Calculate zj Row for New Tableau The new zjrow values are obtained by multiplying the cB column by each column, element by element and summing. For example, z3 = .2(12) + 1.2(18) + .2(0) = 24. 24
Example: Simplex Method Iteration 2 (continued) Step 5: Calculate cj - zj Row for New Tableau The new cj-zj row values are obtained by subtracting zj value in a column from the cjvalue in the same column. For example, c3-z3 = 10 - (24) = -14. Since there are no positive numbers in the cj - zj row, this tableau is optimal. The optimal solution is: x1 = 10; x2 = 10; x3 = 0; s1 = 0; s2 = 0 s3 = 10, and the optimal value of the objective function is 300. 25
Example: Simplex Method Iteration 2 (continued) Final Tableau Basis cB 12 18 10 0 0 0 x1 12 1 0 .2 .2 -.6 0 10 (* row) x2 18 0 1 1.2 .2 .4 0 10 s3 0 0 0 2.7 .2 .4 1 10 zj 12 18 24 6 0 0 300 cj - zj 0 0 -14 -6 0 0 x1x2 x3s1s2s3 26
Solution: Simplex Method To solve this problem using the simplex method, we first multiply the objective function by 1 to convert the minimization problem into the following equivalent maximization problem: 28
Solution: Simplex Method The tableau form for this problem is as follows: 29
Solution: Simplex Method The initial simplex tableau is shown here: 30
Solution: Simplex Method At the first iteration, x1 is brought into the basis and a1 is removed. After dropping the a1 column from the tableau, the result of the first iteration is as follows: 31
Solution: Simplex Method Continuing with two more iterations of the simplex method provides the following final simplex tableau: 32
Special Cases Infeasibility Unboundedness Alternative Optimal Solution Degeneracy 33
Infeasibility Infeasibility is detected in the simplex method when an artificial variable remains positive in the final tableau. 34
Example: Infeasibility LP Formulation MAX 2x1 + 6x2 s. t. 4x1 + 3x2 < 12 2x1 + x2 > 8 x1, x2 > 0 35
Example: Infeasibility Final Tableau x1 2 1 3/4 0 -1/2 -1/2 -1 2 (1/2)M (1/2)MM -M -2M +3/2 +1/2 0 -(1/2)M -(1/2)M -M +9/2 -1/2 x2 6 s1 0 1/4 0 s2 0 -M a2 CB Basis x1 a2 -M cj - zj 2 0 1 3 2 zj +6 0 36
Example: Infeasibility the final tableau because all cj- zj< 0. However, an artificial variable is still positive, so the problem is infeasible. In the previous slide we see that the tableau is 37
Unboundedness A linear program has an unbounded solution if all entries in an entering column are non-positive. 38
Example: Unboundedness LP Formulation MAX 2x1 + 6x2 s. t. 4x1 + 3x2 > 12 2x1 + x2 > 8 x1, x2 > 0 39
Example: Unboundedness Final Tableau Basis cB 4 0 zj x1 3 3 2 12 -9 x2 4 1 0 4 0 s1 0 0 1 0 0 s2 0 x2 s1 cj - zj -1 -1 8 3 -4 4 32 40
Example: Unboundedness positive), but its column is all non-positive. This indicates that the problem is unbounded. In the previous slide we see that c4 - z4 = 4 (is 41
Alternative Optimal Solution A linear program has alternate optimal solutions if the final tableau has a cj - zj value equal to 0 for a non-basic variable. 42
Example: Alternative Optimal Solution Final Tableau x1 x2 Basis cB2 4 6 0 0 0 0 s3 0 0 0 2 4 -2 1 0 8 x2 4 0 1 2 2 -1 0 0 6 x1 2 1 0 -1 1 2 0 0 4 s4 0 0 0 1 3 2 0 1 12 zj2 4 6 10 0 0 0 32 cj zj0 0 0 -10 0 0 0 x3 s1 s2 s3 s4 43
Example: Alternative Optimal Solution solution is: In the previous slide we see that the optimal x1 = 4, x2 = 6, x3 = 0, and z = 32 Note that x3 is non-basic and its c3 - z3 = 0. This 0 indicates that if x3 were increased, the value of the objective function would not change. Another optimal solution can be found by choosing x3 as the entering variable and performing one iteration of the simplex method. The new tableau on the next slide shows an alternative optimal solution is: x1 = 7, x2 = 0, x3 = 3, and z = 32 44
Example: Alternative Optimal Solution New Tableau x1 x2 x3 s1 2 4 6 0 0 0 -1 0 2 -1 0 .5 1 1 - .5 0 0 3 1 .5 0 2 1.5 0 0 7 0 - .5 0 2 2.5 0 1 9 s2 s3 s4 0 0 1 0 2 Basis cB s3 0 x3 6 x1 2 s4 0 cj - zj zj 2 4 6 10 0 0 0 0 -10 0 0 0 32 0 0 45
Degeneracy A degenerate solution to a linear program is one in which at least one of the basic variables equals 0. This can occur at formulation or if there is a tie for the minimizing value in the ratio test to determine the leaving variable. When degeneracy occurs, an optimal solution may have been attained even though some cj zj > 0. Thus, the condition that cj zj < 0 is sufficient for optimality, but not necessary. 46
