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 2x`_{1} + 3x_{2}
s.t. x_{1} + x_{2} โค 4
x_{1} + 2x_{2} โค 6
x_{1}, x_{2} โฅ 0

Using simplex method, we can get the optimal tableau for the original problem, the optimal solution is `x`

, the object value is 10._{1} = 2, x_{2} = 2

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

:_{3}

`max 2x`_{1} + 3x_{2} + 8x_{3}
s.t. x_{1} + x_{2} โค 4
x_{1} + 2x_{2} + x_{3} โค 6
x_{1}, x_{2}, x_{3} โฅ 0

When the decision variable set changes from `(x`

to _{1}, x_{2})`(x`

, the optimal solution _{1}, x_{2}, x_{3})`(x`

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._{1}^{*}, x_{2}^{*}, 0)

Recall from simplex method, the new variable `x`

is non-basis, we need to do is to increase it, until one of the basis variables _{3}`x`

or _{1}`x`

becomes 0. How to do this? We need to calculate the _{2}** reduced cost** of

`x`_{3}

. 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 | `(x` | `(s` |

New | `(x` | `(x` |

We start from the original’s optimal tableau, adding new column for `x`

with question marks, we want to calculate these values._{3}

```
0 0 ? 1 1 | 10
------------------------
1 0 ? 2 -1 | 2
0 1 ? -1 1 | 2
```

The constraint coefficients for non-basis variables is `A`

. If only consider column j, the formula reduced to _{B}^{-1} A_{N}`A`

:_{B}^{-1} A_{j}

`A`_{B}^{-1} A_{j} = โก 2 -1 โค โก 0 โค = โก -1 โค
โฃ -1 1 โฆ โฃ 1 โฆ โฃ 1 โฆ

The reduced cost for non-basis variables is `c`

, if only consider column j, the formula reduced to _{B}^{T} A_{B}^{-1} A_{N} - c_{N}^{T}`c`

:_{B}^{T} A_{B}^{-1} A_{j} - c_{j}^{T}

`c`_{B}^{T} A_{B}^{-1} A_{j} - c_{j}^{T} = [ 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 `(x`

with objective value 48._{1}, x_{2}, x_{3}) = (0, 0, 6)

## Add New Constraints

### Simplex Method Won’t Work

Recall our previous example, but now we want to add a new constraint.

`max 2x`_{1} + 3x_{2}
s.t. x_{1} + x_{2} โค 4
x_{1} + 2x_{2} โค 6
x_{1} โค 1 # new constraint
x_{1}, x_{2} โฅ 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 `s`

, which naturally should be a basis variable. Then our basis set _{3}`B = (x`

, and non-basis set is _{1}, x_{2}, s_{3})`N = (s`

. Then we can calculate the matrix representation, i.e _{1}, s_{2})`A`

, _{B}^{-1}`A`

, _{B}^{-1} A_{N}`A`

, _{B}^{-1} b`c`

, and _{B}^{T} A_{B}^{-1} A_{N} - c_{N}^{T}`c`

, and get a new tableau._{B}^{T} A_{B}^{-1} b

` 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 = (x`_{1}, x_{2}, s_{3})

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 4y`_{1} + 6y_{2}
s.t. y_{1} + y_{2} โฅ 2
y_{1} + 2y_{2} โฅ 3
y_{1}, y_{2} โฅ 0

- Step2: add new variable in the dual, which is equivalent to add new constraint in the primal

`min 4y`_{1} + 6y_{2} + y_{3}
s.t. y_{1} + y_{2} + y_{3} โฅ 2
y_{1} + 2y_{2} โฅ 3 # no y_{3} in this line, constraint coefficient is transposed
y_{1}, y_{2}, y_{3} โฅ 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 for a basis-a negative reduced cost variable.entering2. do the ratio test to find closest to zero for a basis-a RHS value variable.leaving3. 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 for a basis-a negative RHS value variable.leaving2. do the ratio test to find closest to zero for a basis-a reduced cost variable.entering3. 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 2x`_{1} + 3x_{2}
s.t. x_{1} + x_{2} โค 4
x_{1} + 2x_{2} โค 6
x_{1} โค 1 # new constraint
x_{1}, x_{2} โฅ 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. `s`

leaves the basis, and _{3}`s`

enters the basis. This is our new optimal solution _{1}`(x`

, with objective 19/2._{1}, x_{2}, s_{1}) = (1, 5/2, 1/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