# Sensitivity Analysis and Dual Simplex Method

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.

Suppose we have an original problem:

``````max   2x1 + 3x2
s.t.   x1 +  x2 โค 4
x1 + 2x2 โค 6
x1, x2 โฅ 0``````

Using 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  |   2``````

Now, 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 โฅ 0``````

When 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.

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  |   2``````

The 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  |   2``````

from 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  |   6``````

So the new optimal solution is `(x1, x2, x3) = (0, 0, 6)` with objective value 48.

### 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 โฅ 0``````

Intuitively, 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 value``````

This 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):

#### 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 โฅ 0``````

By 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 value``````

Now 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/2``````

All 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.

1. What if we have multiple negative right-hand side value?
• Pick anyone you like.
2. 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