min P cT x Summary subject to Ax b,
x, b 0. Initialization: Select a basic feasible solution
1
xB bB b0,
with B the basis matrix.
Optimality Test: The current basis is optimal, if
Reduced costs
cT cT cTB1N0. N N B
Otherwise, select a variable
x that satisfies c 0 as the entering variable.
tt
2/24/2020 @2020 New York University Tandon 85 School of Engineering
Recursive Step: Compute
Find an index s (determining the leaving variable, sth. basic variable in B) such that:
bs bi a0
min i,t
a 1im a s,t i,t
The Pivot: From the pivot entry as,t , update the
basis matrix B and the vector of basis variables GO BACK TO STEP 2.
x. B
2/24/2020 @2020 New York University Tandon School of Engineering
86
1 ABA.
tt
min Px 2x 12
In compact notation:
An Exercise
subjectto 2xx x 2 123
x 2x x 7 124
x x3 15
x , x , x , x , x 0. 12345
minPcTx, subjectto: Axb, x0, b0.
2/24/2020 @2020 New York University Tandon 87 School of Engineering
Answer
Check the sign of reduced cost at each step cT cT cTB1N.Ifall 0,thenSTOP.
N N B Step 1:
Step 2:
2/24/2020
@2020 New York University Tandon 88 School of Engineering
TT x x,x,x,x x,x
B345N12 cT 0, 0, 0, cT 1, 2
BN
TT x x,x,x,x x,x
B245N13 cT 2, 0, 0, cT 1, 0
BN
Step 3:
TT x x,x,x,x x,x
Step 4:
TT x x,x,x,x x,x
2/24/2020
@2020 New York University Tandon 89
B215N34 cT 2, 1, 0, cT 0, 0
BN
B213N45 cT 2, 1, 0, cT 0, 0
BN
Optimal, because
cT cT cTB1N(1,2)0.
N
School of Engineering
NB
Initial tableau:
The Simplex Tableau
Basic xB xN rhs -P cBT cTN 0
xB BNb Next, Basic xB xN rhs
2/24/2020
B I B1N B1b @2020 New York University Tandon
90
-P 0 cT cTB1N cTB1b xNBB
School of Engineering
The Simplex Tableau
For illustration purpose, study the same example.
Basic x1 x2 x3 x4 x5 rhs -P -1 -2 0 0 0 0
x3 -211002
x4 x5
-1 2 0 1 0 7 100013
2/24/2020
@2020 New York University Tandon 91 School of Engineering
Use the rule to select the pivot entry
s=3, t=2:
b ba0
s mini i,t
a 1im a
s,t i,t Basic x1 x2 x3 x4 x5 rhs
-P -1 -2 0 0 0 0 x
x3 -211002
x4 5
-1 2 0 1 0 7 100013
2/24/2020
@2020 New York University Tandon 92 School of Engineering
Add 2 times the x3 row to the P row and subtract 2 times the x3 row from the x4 row:
Basic x1 x2 x3 x4 x5 rhs -P -5 0 2 0 0 4
x2 -211002
x4 5
3 0 -2 1 0 3 100013
2/24/2020
@2020 New York University Tandon 93 School of Engineering
Basic x1 x2 x3 x4 x5 rhs -P 0 0 -4/3 5/3 0 9
x x2
0 1 -1/3 2/3 0 4 1 0 -2/3 1/3 0 1 0 0 2/3 -1/3 1 2
x1 5
2/24/2020
@2020 New York University Tandon 94 School of Engineering
Final Step (Optimal solution):
Basic x x x3 x4 x rhs
125
-P 0 0 0 1 2 13
x2 x1
0 1 0 1/2 1/2 5 100013 0 0 1 -1/2 3/2 3
x3 2/24/2020
@2020 New York University Tandon School of Engineering
95
Final Step (Optimal solution):
Basic x x x3 x4 x rhs
125
-P 0 0 0 1 2 13
x2 x1
0 1 0 1/2 1/2 5 100013
x3
P 13, atx x 3, x 5.
3
0 0 1 -1/2 3/2
2/24/2020 @2020 New York University Tandon School of Engineering
96
132
Solve the minimization problem:
2/24/2020
@2020 New York University Tandon 97 School of Engineering
An Exercise
minP 3x x 3x 123
subjectto 2x x x 2 123
x 2x 3x 5 123
2x 2x x 6 123
x 0, x 0, x 0. 123
-P
Answer
First tableau (pivoting 1 leads to less computation):
x1 x2 x3 x4 x5 x6
-3 -1 -3 0 0 0 0
2111002 1230105 2210016
2/24/2020 @2020 New York University Tandon 98 School of Engineering
rhs
-P
Answer (contd)
Second tableau:
x1 x2 x3 x4 x5 x6
-1 0 -2 1 0 0 2
2111002 -3 0 1 -2 1 0 1 -2 0 -1 -2 0 1 2
2/24/2020 @2020 New York University Tandon 99 School of Engineering
rhs
-P
Answer (contd)
Third tableau:
x1 x2 x3 x4 x5 x6
-7 0 0 -3 2 0 4
5 1 0 3 -1 0 1 -3 0 1 -2 1 0 1 -5 0 0 -4 1 1 3
2/24/2020 @2020 New York University Tandon 100 School of Engineering
rhs
-P
0 6/5
0 3/5 -1/5 0 1/5 1 -1/5 2/5 0 8/5
Answer (contd)
Fourth tableau:
x1 x2 x3 x4
x5 x6
3/5 0 27/5
0 7/5
1 1/5
0 3/5
0 1 0 -1 0 1 4
2/24/2020 @2020 New York University Tandon 101 School of Engineering
rhs
Answer (contd)
2/24/2020
@2020 New York University Tandon 102 School of Engineering
Optimal solution, read from the last tableau: x* 1,x* 0,x* 8,x* 0,x* 0,x* 4.
15235456
P* 27. 5
Artificial Variables
Goal: Find an (initial) basic feasible solution for the standard LP Problem:
min PcTx subject to Ax b,
2/24/2020 @2020 New York University Tandon 103 School of Engineering
x 0.
The TwoPhase Method
The phase-I problem:
min P a
i i
subjectto Ax ab, x, a 0,
T
a a ,, a : artificial variables
1m
A direct application of the simplex method yields a basic feasible solution (not optimal)
for the original P !!
2/24/2020 @2020 New York University Tandon 104 School of Engineering
2/24/2020
@2020 New York University Tandon 105 School of Engineering
An Example
min P2x 3x 12
subjectto 3x2x14 12
2x 4x 2 12
4x 3x 19 12
x , x 0. 12
2/24/2020
@2020 New York University Tandon 106 School of Engineering
An Example (contd)
min P2x 3x 12
subjectto 3x2x 12
14 2
2x 4x x 123
x 19 124
4x 3x
x , x , x , x 0.
1234
No obvious basic feasible solution, due to less than (three) slack variables.
Phase1 Problem:
subjectto
3x 2x a 14 121
min Pa a 12
2x 4x x a 2 1232
4x 3x x 19 124
x,x,x,x,a,a 0. 123412
Now the (initial) basic feasible variable
TT x a,a,x withvalues 14,2,19 .
B124
2/24/2020 @2020 New York University Tandon 107 School of Engineering
Applying the simplex technique,
Initial tableau:
x1 x2 x3 x4 a1 a2 0000110
P
3 2 0 0 1 0 14
2/24/2020
@2020 New York University Tandon 108 School of Engineering
2 -4 -1 0 0 1 2 4 3 0 1 0 0 19
rhs
(Use elimination to the first row to make the entries for the initial basic variables 0.)
First tableau:
x1 x2 x3 x4 a1 a2
-5 2 1 0 0 0 -16
P
3 2 0 0 1 0 14
2 -4 -1 0 0 1 2
4 3 0 1 0 0 19
2/24/2020 @2020 New York University Tandon 109 School of Engineering
rhs
(The basic variable a2 leaving, so delete the irrelevant a2 column:)
Second tableau:
x1 x2 x3 x4 a1
0 -8 -3/2 0 0 -11
P
0 8 3/2 0 1 11
2/24/2020
@2020 New York University Tandon 110 School of Engineering
1 -2 -1/2 0 0 1 011210 15
rhs
(The basic variable x4 leaving, but cannot delete the relevant x4 column:)
Third tableau:
0 P
0 -1/22 8/11
-1/11 1/11
2/24/2020
@2020 New York University Tandon School of Engineering
111
x1 x2 x3 x4
a1 0
rhs
0 0
1 0
0 1
1/22 -8/11 -3/22 2/11
1
2/11 1/11
0 0
41/11 15/11
(The basic variable a1 leaving, so delete the irrelevant a1 column:)
Third tableau:
x1 x2 x3 x4 P
rhs 0000 0
2/24/2020
@2020 New York University Tandon 112 School of Engineering
0 0 1 -16 2 1 0 0 -2 4 0103 1
PhaseII Problem: P=21 + 32
Initial tableau:
-P
2/24/2020
@2020 New York University Tandon 113 School of Engineering
x1 x2 x3 x4
2300 0
0 0 1 -16 2 1 0 0 -2 4 0103 1
rhs
PhaseII Problem: P=21 + 32
First tableau (Use elimination to the first row to make the entries for the initial basic variables 0):
-P
2/24/2020
@2020 New York University Tandon 114 School of Engineering
x1 x2 x3 x4
0 0 0 -5 -11
0 0 1 -16 2 1 0 0 -2 4 0103 1
rhs
PhaseII Problem: P=21 + 32
Second tableau:
-P
-28/3 22/3 14/3
2/24/2020
@2020 New York University Tandon School of Engineering
115
x1 x2 x3 x4 0 5/3 0 0
rhs
016/3 1 0 1 2/3 0 0 0 1/3 0 1
1/3
So, the optimal solution is
P* 28 , or P* 28
33
which is attained at the following minimizer:
x* 14, x* 0, x* 22, x* 1. 132 3343
2/24/2020 @2020 New York University Tandon 116 School of Engineering
2/24/2020
@2020 New York University Tandon 117 School of Engineering
An Exercise
minP4x x x 123
subjectto 2x x 2x 4 123
3x 3x x 3 123
x 0, i1,2,3 i
Degeneracy
A linear program is degenerate, if a basic variable equals zero, i.e., the last column b contains a zero.
2/24/2020 @2020 New York University Tandon 118 School of Engineering
x ba0b0 t min i i,t s
1ima a
Cycling
In case of degeneracy, it may happen that
i,t s,t
Then, the performance function does not improve:
PPcxP tt
eventually leading to the cycling problem,
i.e., the (leaving) basic variable xs will be re-chosen as the entering variable in a few steps.
2/24/2020 @2020 New York University Tandon 119 School of Engineering
2/24/2020
@2020 New York University Tandon School of Engineering
120
A Degenerate LP Problem
For the following LP problem, the simplex method cycles indefinitely!
minP3x 150x 1 x 6x 41 2503 4
subjectto 1x60x1x9x0 41 2253 4
1x 90x 1 x 3x 0 21 2503 4
x3 1 xi 0, 1i4.
Blands Rule
Goal: to avoid cycling. Make the following changes in the simplex method,
a) select the lowestindexed favorable column to enter the basis, using the rule:
b) In case of ties or undecision, select the lowest indexed column to leave the basis.
jmin j: c 0 . j
2/24/2020 @2020 New York University Tandon 121 School of Engineering
2/24/2020
@2020 New York University Tandon 122 School of Engineering
The Perturbation Method
This is another efficient method to avoid cycling or minimize computation time.
The simplex method will surely terminate if applied to the LP with perturbed constraints:
Ax b where,forsufficientlysmall0 0,
,2,,m 000
Reviews
There are no reviews yet.