Previously, we mentioned that an sensitivity analysis tool called Shadow Price is helpful to evaluate the impact of change when right hand side value of a constraint is increased by 1. However in some cases, there might be new variables or new constraints added, the good news is you don’t have to solve the problem from scratch, a bit more simplex iteration is only required to get to the new optimal solution.
Add New Variables
Suppose we have an original problem:
max 2x1 + 3x2
s.t. x1 + x2 ≤ 4
x1 + 2x2 ≤ 6
x1, x2 ≥ 0Using simplex method, we can get the optimal tableau for the original problem, the optimal solution is x1 = 2, x2 = 2, the object value is 10.
0 0 1 1 | 10
--------------------
1 0 2 -1 | 2
0 1 -1 1 | 2Now, we want to add a new variable to the original problem, the new problem with one additional variable x3:
max 2x1 + 3x2 + 8x3
s.t. x1 + x2 ≤ 4
x1 + 2x2 + x3 ≤ 6
x1, x2, x3 ≥ 0When the decision variable set changes from (x1, x2) to (x1, x2, x3), the optimal solution (x1*, x2*, 0) is certainly feasible for the new problem. This optimal solution can become our initial searching point, from where we are going to find the new optimal solution.
Recall from simplex method, the new variable x3 is non-basis, we need to do is to increase it, until one of the basis variables x1 or x2 becomes 0. How to do this? We need to calculate the reduced cost of x3. Following the rules of simplex method, if it’s reduced cost is negative, then we enter it because this is a maximization problem.
| Basis set | Non-basis set | |
| Original | (x1, x2) | (s1, s2) |
| New | (x1, x2) | (x3, s1, s2) |
We start from the original’s optimal tableau, adding new column for x3 with question marks, we want to calculate these values.
0 0 ? 1 1 | 10
------------------------
1 0 ? 2 -1 | 2
0 1 ? -1 1 | 2The constraint coefficients for non-basis variables is AB-1 AN. If only consider column j, the formula reduced to AB-1 Aj:
AB-1 Aj = ⎡ 2 -1 ⎤ ⎡ 0 ⎤ = ⎡ -1 ⎤
⎣ -1 1 ⎦ ⎣ 1 ⎦ ⎣ 1 ⎦The reduced cost for non-basis variables is cBT AB-1 AN - cNT, if only consider column j, the formula reduced to cBT AB-1 Aj - cjT:
cBT AB-1 Aj - cjT = [ 2 3 ] ⎡ -1 ⎤ - 8 = -7
⎣ 1 ⎦Now we are able to complete the tableau:
0 0 -7 1 1 | 10
------------------------
1 0 -1 2 -1 | 2
0 1 1 -1 1 | 2from here on, we again use simplex method, do a few more iterations to solve the new problem.
0 7 0 -6 8 | 24 6 13 0 0 8 | 48
------------------------ ⟹ ------------------------
1 1 0 1 0 | 4 1 1 0 1 0 | 4
0 1 1 -1 1 | 2 1 2 1 0 1 | 6So the new optimal solution is (x1, x2, x3) = (0, 0, 6) with objective value 48.
Add New Constraints
Simplex Method Won’t Work
Recall our previous example, but now we want to add a new constraint.
max 2x1 + 3x2
s.t. x1 + x2 ≤ 4
x1 + 2x2 ≤ 6
x1 ≤ 1 # new constraint
x1, x2 ≥ 0Intuitively, we may plug in the original optimal solution into the new constraint. If it is feasible, the original optimal solution is also optimal for the new problem. If it is NOT feasible, we need to do something else.
Note the new constraint will introduce a new slack variable, say s3, which naturally should be a basis variable. Then our basis set B = (x1, x2, s3), and non-basis set is N = (s1, s2). Then we can calculate the matrix representation, i.e AB-1, AB-1 AN, AB-1 b, cBT AB-1 AN - cNT, and cBT AB-1 b, and get 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 # note the negative valueThis is where we are, after we add the new additional constraint into our original optimal solution. Unfortunately, we can not go further, this is an invalid simplex tableau, the right-hand side column contains a negative value, i.e -1. In other words, B = (x1, x2, s3) is infeasible, as we already know.
Dual Simplex Method
Linear programming duality can help us! Think about a primal-dual pair, a new constraint in primal means a new variable in the dual. So we may think about and solve the dual, instead of the primal. The new dual problem must be able to be solved because we know that’s just adding one variable. The general idea is:
- Step1: convert the original problem (the primal) to its dual
min 4y1 + 6y2
s.t. y1 + y2 ≥ 2
y1 + 2y2 ≥ 3
y1, y2 ≥ 0- Step2: add new variable in the dual, which is equivalent to add new constraint in the primal
min 4y1 + 6y2 + y3
s.t. y1 + y2 + y3 ≥ 2
y1 + 2y2 ≥ 3 # no y3 in this line, constraint coefficient is transposed
y1, y2, y3 ≥ 0- Step3: solve it then go back to primal.
Bearing the idea in mind, however we do not really need to work on the dual. We may use the Dual Simplex Method directly, i.e. do all dual simplex iterations in the primal’s tableau.
We can compare the (primal) simplex method (we have been using) and the dual simplex method (we are going to learn now):
| (Primal) Simplex Method |
| (for a maximum problem) 1. look for a negative reduced cost for a basis-entering variable. 2. do the ratio test to find a RHS value closest to zero for a basis-leaving variable. 3. go to step 1 to begin another iteration In this process, current primal solution is not optimal, but it is primal feasible. It must means your current solution gets you a dual solution that is infeasible. We are actually maintaining primal feasibility and fix the dual infeasibility. |
| Dual Simplex Method |
| (for a maximum problem) 1. look for a negative RHS value for a basis-leaving variable. 2. do the ratio test to find a reduced cost closest to zero for a basis-entering variable. 3. go to step 1 to begin another iteration In this process, we are actually maintaining dual feasibility and fix the primal infeasibility. |
Example
Let us see how to apply the dual simplex method on the previous example:
max 2x1 + 3x2
s.t. x1 + x2 ≤ 4
x1 + 2x2 ≤ 6
x1 ≤ 1 # new constraint
x1, x2 ≥ 0By adding a new constraint, we can get this tableau, as mentioned above.
0 0 1 1 0 | 10
-------------------------
1 0 2 -1 0 | 2
0 1 -1 1 0 | 2
0 0 -2 1 1 | -1 # note the negative valueNow we can use the dual simplex method to fix the primal infeasibility. In order to fix primal infeasibility, the pivot should be negative so that a row operation will do the fix.
0 0 1 1 0 | 10
---------------------------
1 0 2 -1 0 | 2
0 1 -1 1 0 | 2
0 0 [-2] 1 1 | -1 # -2 is pivot
row operation on row 3 ⟹
0 0 1 1 0 | 10
-----------------------------
1 0 2 -1 0 | 2
0 1 -1 1 0 | 2
0 0 1 -1/2 -1/2 | 1/2
row operation on row 0, 1, 2 ⟹
0 0 0 3/2 1/2 | 19/2
-----------------------------
1 0 0 0 1 | 1
0 1 0 1/2 -1/2 | 5/2
0 0 1 -1/2 -1/2 | 1/2All the right hand side values are positive. All the reduced costs are non negative. And then we’re done. s3 leaves the basis, and s1 enters the basis. This is our new optimal solution (x1, x2, s1) = (1, 5/2, 1/2), with objective 19/2.
- What if we have multiple negative right-hand side value?
- Pick anyone you like.
- What if we have multiple negative numbers in the row that corresponds to the right-hand side value we just picked?
- Pick the one that will maintain dual feasibility, i.e. making reduce costs non-negative.
My Certificate
For more on Sensitivity Analysis and Dual Simplex Method, please refer to the wonderful course here https://www.coursera.org/learn/operations-research-theory
Related Quick Recap
I am Kesler Zhu, thank you for visiting my website. Check out more course reviews at https://KZHU.ai
Don't forget to sign up newsletter, don't miss any chance to learn.
Or share what you've learned with friends!
Tweet
