Evaluating a new variable Dual Simplex Method
Operations Research III: Theory
Sensitivity Analysis and Dual Simplex Method
Ling-Chieh Kung
Department of Information Management
National Taiwan University
OR III: Dual Simplex Method 1 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
Road map
I Evaluating a new variable.
I Dual simplex method.
OR III: Dual Simplex Method 2 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
A motivating example
I Consider the following example.
I A company is selling two products. Producing 1 unit of product 1
requires 1 unit of resource 1 and 1 unit of resource 2. Producing 1 unit
of product 2 requires 1 unit of resource 1 and 2 units of resource 2.
Each unit of products 1 and 2 can be sold at $2 and $3, respectively.
The total amounts of resources 1 and 2 it has are 4 and 6 units,
respectively. Find an optimal production plan that maximize its total
sales revenue.
I The Linear Programming formulation:
max 2x1 + 3x2
s.t. x1 + x2 ≤ 4
x1 + 2x2 ≤ 6
x1 , x2 ≥ 0.
OR III: Dual Simplex Method 3 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
A motivating example
I We may use the simplex method to solve it:
−2 −3 0 0 0 0 −1 2 0 8
1 1 1 0 4 → 1 1 1 0 4
1 2 0 1 6 0 1 −1 1 2
0 0 1 1 10
→ 1 0 2 −1 2
0 1 −1 1 2
I An optimal solution is (x∗1 , x∗2 ) = (2, 2). The objective value is z ∗ = 10.
OR III: Dual Simplex Method 4 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
A new activity
I Suppose that the company now may produce the third product. 1 unit
of product 3 requires only 1 unit of resource 2 and can be sold at 8.
The new Linear Programming formulation:
max 2x1 + 3x2 + 8x3
s.t. x1 + x2 ≤ 4
x1 + 2x2 + x3 ≤ 6
x1 , x2 , x3 ≥ 0.
I May we find an optimal plan?
OR III: Dual Simplex Method 5 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
A new activity
I We may always solve the new linear program from scratch:
−2 −3 −8 0 0 0 0 −1 −8 2 0 8
1 1 0 1 0 4 → 1 1 0 1 0 4
1 2 1 0 1 6 0 1 1 −1 1 2
0 0 −7 1 1 10 0 7 0 −6 8 24 6 13 0 0 8 48
→ 1 0 −1 2 −1 2 → 1 1 0 1 0 4 → 1 1 0 1 0 4
0 1 1 −1 1 2 0 1 1 −1 1 2 1 2 1 0 1 6
I An optimal solution is (x∗∗ ∗∗ ∗∗
1 , x2 , x3 ) = (0, 0, 6) with z
∗∗
= 48.
OR III: Dual Simplex Method 6 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
May we do better?
I Do we really need to solve the new problem from scratch?
I We just solved a problem with n activities and obtained an optimal
solution.
I The new problem has n + 1 activities. The original n activities remain
unchanged. The resources remain unchanged.
I The new problem is so similar to the original problem!
I May we go from an optimal solution of the original problem
instead of going from the very beginning? That may save a lot of time!
I If the original problem’s feasibility is a question (i.e., the two-phase
implementation is needed), the difference becomes more obvious!
OR III: Dual Simplex Method 7 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
May we do better?
I The answer is definitely yes!
I When the decision variable set changes from (x1 , x2 ) to (x1 , x2 , x3 ), the
solution (x∗1 , x∗2 , 0) is certainly feasible for the new problem.
I Just like removing the newly added column in the new problem.
I We simply ignore the new option.
I All we need to do is to check whether we should produce some
product 3.
I If no, the current solution (x∗1 , x∗2 , 0) is optimal.
I If yes, we increase the nonbasic variable x3 until one basic variable
becomes 0.
I How to determine this?
I All we need is the reduced cost of x3 !
OR III: Dual Simplex Method 8 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
Evaluating the new activity
I Now we are ready to evaluate the new activity (product 3).
I Our original problem:
max 2x1 + 3x2
s.t. x1 + x2 ≤ 4
x1 + 2x2 ≤ 6
x1 , x2 ≥ 0.
I Our new problem:
max 2x1 + 3x2 + 8x3
s.t. x1 + x2 ≤ 4
x1 + 2x2 + x3 ≤ 6
x1 , x2 , x3 ≥ 0.
OR III: Dual Simplex Method 9 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
Evaluating the new activity
I After we solve the original problem, we have B ∗ = (x1 , x2 ) and
N ∗ = (s1 , s2 ).
I The optimal basis is B ∗ .
I When we have the new decision variable x3 , it is 0 (nonbasic) at the
beginning.
I Therefore, to solve the new problem, we may start from the basis
B = (x1 , x2 ) and the set of nonbasic variables N = (x3 , s1 , s2 ).
I Setting x3 = 0 is definitely feasible.
I These B and N allow us to obtain the initial tableau for the new
problem.
I We do not need to start from scratch.
OR III: Dual Simplex Method 10 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
Evaluating the new activity
I The initial tableau for the new
I Recall that we have the optimal
problem should have only one
tableau for the original problem:
column missing:
0 0 1 1 10
0 0 ? 1 1 10
1 0 2 −1 2
1 0 ? 2 −1 2
0 1 −1 1 2
|{z} | {z } 0 1 ? −1 1 2
basic nonbasic
|{z} | {z }
basic nonbasic
OR III: Dual Simplex Method 11 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
Evaluating the new activity
I Let’s calculate the values in that column.
I The vector of constraint coefficients for 0 0 ? 1 1 10
nonbasic variables is A−1
B AN .
I For column j, that column is A−1B Aj . 1 0 ? 2 −1 2
I In our example, it is
0 1 ? −1 1 2
2 −1 0 −1 |{z} | {z }
= .
−1 1 1 1 basic nonbasic
I The vector of reduced costs for nonbasic
variables is cTB A−1 T 0 0 −7 1 1 10
B AN − cN .
I For column j, that value is cTB A−1
B Aj − cj . 1 0 −1 2 −1 2
I In our example, it is
−1
0 1 1 −1 1 2
2 3 − 8 = −7. |{z} | {z }
1
basic nonbasic
OR III: Dual Simplex Method 12 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
Evaluating the new activity
I Let’s go from the initial tableau for the new problem:
0 0 −7 1 1 10 0 7 0 −6 8 24 6 13 0 0 8 48
1 0 −1 2 −1 2 → 1 1 0 1 0 4 → 1 1 0 1 0 4
0 1 1 −1 1 2 0 1 1 −1 1 2 1 2 1 0 1 6
I An optimal solution is (x∗∗ ∗∗ ∗∗
1 , x2 , x3 ) = (0, 0, 6) with z
∗∗
= 48.
I This is exactly omitting the first few iterations from the very
beginning to the initial tableau!
I Time is thus saved.
I We may further speed up by using the matrix representation.
I There is no need to work with the full tableau.
OR III: Dual Simplex Method 13 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
Road map
I Evaluating a new variable.
I Dual Simplex Method.
OR III: Dual Simplex Method 14 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
A new constraint
I Recall our example
max 2x1 + 3x2
s.t. x1 + x2 ≤ 4
x1 + 2x2 ≤ 6
x1 , x2 ≥ 0.
I We know how to evaluate a new activity.
I What if now we have a new constraint? For example, how about
max 2x1 + 3x2
s.t. x1 + x2 ≤ 4
x1 + 2x2 ≤ 6
x1 ≤ 1
x1 , x2 ≥ 0?
OR III: Dual Simplex Method 15 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
A new constraint
I Intuitively, we may plug in the original optimal solution
(x∗1 , x∗2 ) = (2, 2) into the new constraint.
I If it is feasible, it is optimal for the new problem.
I In our example, it is not feasible because 2 > 1.
I What if it is not feasible?
I Let’s look at the tableau to give us more ideas.
OR III: Dual Simplex Method 16 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
The new tableau with the new constraint
I Recall our original optimal tableau
0 0 1 1 10
1 0 2 −1 2
0 1 −1 1 2
I With a new constraint x1 ≤ 1 (which also introduces a new slack
variable s3 ), what should the new tableau look like?
I We again rely on the matrix representation.
OR III: Dual Simplex Method 17 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
The new tableau with the new constraint
I Let’s include s3 to be a basic variable (as that new constraint is
violated).
I Let B = (x1 , x2 , s3 ) and N = (s1 , s2 ).
2 1 1 0
I We have cB = 3 , cN = 0 , AB = 1 2 0 ,
0
0 1 0 1
1 0 4
AN = 0 1 , and b = 6 .
0 0 1
2 −1 0 2 −1
I We then have A−1
B =
−1 1 0 , A−1
B AN =
−1 1 ,
−2 1 1 −2 1
2
A−1 2 , cTB A−1 T
1 1 , and cTB A−1
B b = B AN − cN = B b = 10.
−1
OR III: Dual Simplex Method 18 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
The new tableau with the new constraint
I This gives us a new tableau
0 0 1 1 0 10
1 0 2 −1 0 2
0 1 −1 1 0 2
0 0 −2 1 1 −1
| {z} | {z } |{z}
basic nonbasic basic
OR III: Dual Simplex Method 19 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
An infeasible basis
I The tableau:
0 0 1 1 0 10
1 0 2 −1 0 2
0 1 −1 1 0 2
0 0 −2 1 1 −1
I This is an invalid simplex tableau: Its RHS column contains a
negative value.
I In other words, B = (x1 , x2 , s3 ) is infeasible, as we already know.
I What should we do?
OR III: Dual Simplex Method 20 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
Linear Programming duality
I Recall that we know how to deal with a new variable.
I We evaluate its reduced cost.
I We run some simplex iterations if needed.
I We do not know how to deal with a new constraint.
I We do not know how to run simplex iterations.
I But wait... we know Linear Programming duality.
I We know a primal constraint is a dual variable.
I If a primal LP has one new constraint, it dual LP will has one new
variable.
I We know how to deal with the dual LP!
OR III: Dual Simplex Method 21 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
Linear Programming duality
I Our original primal LP is
max 2x1 + 3x2
s.t. x1 + x2 ≤ 4
x1 + 2x2 ≤ 6
x1 , x2 ≥ 0.
I Our original dual LP is
min 4y1 + 6y2
s.t. y1 + y2 ≥ 2
y1 + 2y2 ≥ 3
y1 , y2 ≥ 0.
OR III: Dual Simplex Method 22 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
Linear Programming duality
I Our primal LP with a new constraint is
max 2x1 + 3x2
s.t. x1 + x2 ≤ 4
x1 + 2x2 ≤ 6
x1 ≤ 1
x1 , x2 ≥ 0.
I Our dual LP with a new variable is
min 4y1 + 6y2 + y3
s.t. y1 + y2 + y3 ≥ 2
y1 + 2y2 ≥ 3
y1 , y2 , y3 ≥ 0.
I The original dual LP’s optimal solution isn’t optimal for the new dual LP.
I We may solve the new dual LP to solve the new primal LP.
OR III: Dual Simplex Method 23 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
The dual simplex method
I While we understand the idea, we do not really need to work on the
dual LP.
I We may use the dual simplex method directly.
I The (primal) simplex method for a maximization problem:
I Look for a negative reduced cost for an entering variable.
I Do the ratio test to find a RHS value hitting 0 first for a leaving
variable.
I We maintain primal feasibility and fix dual infeasibility.
I The dual simplex method for a maximization problem:
I Look for a negative RHS value for a leaving variable.
I Do the ratio test to find a reduced cost hitting 0 first for an entering
variable.
I We maintain dual feasibility and fix primal infeasibility.
OR III: Dual Simplex Method 24 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
An example
I Recall our new (primal) problem and its invalid tableau:
max 2x1 + 3x2 0 0 1 1 0 10
s.t. x1 + x2 ≤ 4
x1 + 2x2 ≤ 6 1 0 2 −1 0 2
x1 ≤ 1 0 1 −1 1 0 2
x1 , x2 ≥ 0. 0 0 −2 1 1 −1
I Look for a negative RHS value for a leaving variable:
I s3 should be the leaving variable.
I Where is the pivot?
I We need to fix primal infeasibility by making that −1 nonnegative.
I The pivot should be negative so that a row operation does the fix.
OR III: Dual Simplex Method 25 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
Pivoting
0 0 1 1 0 10 0 0 1 1 0 10
1 0 2 −1 0 2 row operation −1
−−−−−−−−−−−→ 1 0 2 0 2
0 1 −1 1 0 2 on row 3 0 1 −1 1 0 2
0 0 −2 1 1 −1 0 0 1 − 12 − 12 1
2
3 1 19
0 0 0 2 2 2
row operation 1 0 0 0 1 1
−−−−−−−−−−−−−−→
on row 0, 1, and 2 0 1 0 1
− 12 5
2 2
0 0 1 − 12 − 12 1
2
OR III: Dual Simplex Method 26 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
Pivoting
I After one iteration, we obtain
3 1 19
0 0 0 2 2 2
1 0 0 0 1 1
1
0 1 0 2 − 12 5
2
0 0 1 − 12 − 12 1
2
I s3 leaves and s1 enters.
I The current basic solution is (x1 , x2 , s1 , s2 , s3 ) = (1, 5 , 1 , 0, 0). It is
2 2
feasible.
I It corresponds to the solution (x1 , x2 ) = (1, 5 ) with z = 19 . It is optimal.
2 2
OR III: Dual Simplex Method 27 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
Another (purely pedagogical) example
I What if we have multiple negative RHS values? E.g.,
0 0 1 1 0 10
1 0 −2 −1 0 −2
0 1 −1 1 0 2
0 0 −2 1 1 −1
I In this case, pick anyone you like.
I E.g., if you adopt the smallest index rule, we will pick x1 .
I What if we have multiple negative numbers in that row?
I We need to maintain dual feasibility (make reduced costs nonnegative).
I A ratio test will help us pick one (which one)?
OR III: Dual Simplex Method 28 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
Another (purely pedagogical) example
1
I Pivoting at −2 is good (and | −2 1
| < | −1 |):
1 1
0 0 1 1 0 10 2 0 0 2 0 9
1 0 −2 −1 0 −2 → − 12 0 1 1
2 0 1
0 1 −1 1 0 2 − 12 1 0 3
2 0 3
0 0 −2 1 1 −1 −1 0 0 2 1 1
1
I Pivoting at −1 is bad (and | −1 1
| > | −2 |):
0 0 1 1 0 10 1 0 −1 0 0 8
1 0 −2 −1 0 −2 → −1 0 2 1 0 2
0 1 −1 1 0 2 1 1 −3 0 0 0
0 0 −2 1 1 −1 −1 0 −4 0 1 −3
OR III: Dual Simplex Method 29 / 30 Ling-Chieh Kung (NTU IM)
Evaluating a new variable Dual Simplex Method
Remarks
I The dual simplex method helps us deal with additional constraints.
I The pivoting rule:
I Leaving: a basic variable that is negative (a row with a negative RHS).
I Ratio test: For those nonbasic columns with negative elements in the
leaving row, let the reduced costs as numerators and absolute values of
the negative elements as denominators.
I Entering: a nonbasic variable (a column) with the smallest ratio.
I It is used in many situations, e.g.:
I When we use branch and bound to solve an integer program, we
keep adding constraints to existing nodes.
I To solve a new node with one additional constraint, the dual simplex
method helps a lot!
OR III: Dual Simplex Method 30 / 30 Ling-Chieh Kung (NTU IM)
