6 Sensitivity Analysis

In this section we study general questions involving the sensitivity of the solution to an LP
under changes to its input data. As it turns out LP solutions can be extremely sensitive to
such changes and this has very important practical consequences for the use of LP technology
in applications. Let us now look at a simple example to illustrate this fact.
Consider the scenario where we be believe the federal reserve board is set to decrease
the prime rate at its meeting the following morning. If this happens then bond yields will
go up. In this environment, you have calculated that for every dollar that you invest today
in bonds will give a return of a half percent tomorrow so, as a bond trader, you decide to
invest in lots of bonds today. But to do this you will need to borrow money on margin.
For the 24 hours that you intend to borrow the money you will need to place a reserve with
the exchange that is un-invested, and then you can borrow up to 100 times this reserve.
Regardless of how much you borrow, the exchange requires that you pay them back 10%
of your reserve tomorrow. To add an extra margin of safety you will limit the sum of your
reserve and one hundreth of what you borrow to be less than 200,000 dollars. Model the
problem of determining how much money should be put on reserve and how much money
should be borrowed to maximize your return on this 24 hour bond investment.
To model this problem, let R denote your reserve in $10,000 units and let B denote the
amount you borrow in the same units. Due to the way you must pay for the loan (i.e. it
depends on the reserve, not what you borrow), your goal is to

maximize 0.005B 0.1R .

Your borrowing constraint is

B  100R ,
and your safety constraint is
B
+ R  20 .
100
The full LP model is
maximize 0.005B 0.1R
subject to B 100R  0
0.01B + R  20
0  B, R .
We conjecture that the solution occurs at the intersection of the two nontrivial constraint
lines. We check this by applying the geometric duality theorem, i.e., we solve the system
✓ ◆ ✓ ◆ ✓ ◆
0.005 1 0.01
= y1 + y2
0.1 100 1

which gives (y1 , y2 ) = (0.003, 0.2). Since the solution is non-negative, the solution does
occur at the intersection of the two nontrivial constraint lines giving (B, R) = (1000, 10)

76
with dual solution (y1 , y2 ) = (0.003, 0.2) and optimal value 4, or equivalently a profit of
$40,000 on a $100,000 investment (the cost of the reserve).
But suppose that somehow your projections are wrong, and the Fed left rates alone and
bond yields dropped by half a percent rather than increase by half a percent. In this scenario
you would have lost $60, 000 on the $100,000 investment. That is, the di↵erence between
a rise of the interest rate by half a percent to a drop in the interest rate by half a percent
is one hundred thousand dollars. Clearly, this is a very risky investment opportunity. In
this environment the downside risks must be fully understood before an investment is made.
Doing this kind of analysis is called sensitivity analysis. We will look at some techniques for
sensitivity analysis in this section. All of our discussion will be motivated by examples.
In practice, performing sensitivity analysis on solutions to LPs is absolutely essential.
One should never report a solution to an LP without the accompanying sensitivity analysis.
This is because all of the numbers defining the LP are almost always subject to error. The
errors may be modeling errors, statistical errors, or data entry errors. Such errors can lead
to catastrophically bad optimal solutions to the LP. Sensitivity analysis techniques provide
tools for detecting and avoiding bad solutions.

6.1 Break-even Prices and Reduced Costs

The first type of sensitivity problem we consider concerns variations or perturbations to the
objective coefficients. For this we consider the following LP problem.
SILICON CHIP CORPORATION
A Silicon Valley firm specializes in making four types of silicon chips for personal computers.
Each chip must go through four stages of processing before completion. First the basic silicon
wafers are manufactured, second the wafers are laser etched with a micro circuit, next the
circuit is laminated onto the chip, and finally the chip is tested and packaged for shipping.
The production manager desires to maximize profits during the next month. During the next
30 days she has enough raw material to produce 4000 silicon wafers. Moreover, she has 600
hours of etching time, 900 hours of lamination time, and 700 hours of testing time. Taking
into account depreciated capital investment, maintenance costs, and the cost of labor, each
raw silicon wafer is worth $1, each hour of etching time costs $40, each hour of lamination
time costs $60, and each hour of inspection time costs $10. The production manager has
formulated her problem as a profit maximization linear program with the following initial
tableau:
x1 x2 x3 x4 x5 x6 x7 x8 b

raw wafers 100 100 100 100 1 0 0 0 4000

etching 10 10 20 20 0 1 0 0 600
lamination 20 20 30 20 0 0 1 0 900
testing 20 10 30 30 0 0 0 1 700
2000 3000 5000 4000 0 0 0 0 0
where x1 , x2 , x3 , x4 represent the number of 100 chip batches of the four types of chips and

77
the objective row coefficients for these variables correspond to dollars profit per 100 chip
batch. After solving by the Simplex Algorithm, the final tableau is:

x1 x2 x3 x4 x5 x6 x7 x8 b

0.5 1 0 0 .015 0 0 .05 25

5 0 0 0 .05 1 0 .5 50
0 0 1 0 .02 0 .1 0 10
0.5 0 0 1 .015 0 .1 .05 5
1500 0 0 0 5 0 100 50 145, 000

Thus the optimal production schedule is (x1 , x2 , x3 , x4 ) = (0, 25, 10, 5). In this solution we
see that type 1 chip is not efficient to produce.
The first problem we address is to determine the sale price at which it is efficient to
produce type 1 chip. That is, what sale price p for which it is not efficient to produce type 1
chip below this sale price, but it is efficient to produce above this sale price? This is called
the breakeven sale price of type 1 chip. As a first step let us compute the current sale price
of type 1 chip. From the objective row we see that each 100 type 1 chip batch has a profit
of $2000. The cost of production of each 100 unit batch of type 1 chip is given by

chip cost + etching cost + lamination cost + inspection cost,

where

chip cost = no. chips ⇥ cost per chip = 100 ⇥ 1 = 100

etching cost = no. hours ⇥ cost per hour = 10 ⇥ 40 = 400
lamination cost = no. hours ⇥ cost per hour = 20 ⇥ 60 = 1200
inspection cost = no. hours ⇥ cost per hour = 20 ⇥ 10 = 200 .

Hence the costs per batch of 100 type 1 chips is $1900. Therefore, the sale price of each
batch of 100 type 1 chips is $2000 + $1900 = $3900, or equivalently, $39 per chip.
Since we do not produce type 1 chip in our optimal production mix, the breakeven sale
price must be greater than $39 per chip. Let ✓ denote the amount by which we need to
increase the current sale price of type 1 chip so that it enters the optimal production mix.
With this change to the sale price of type 1 chip the initial tableau for the LP becomes

x1 x2 x3 x4 x5 x6 x7 x8 b

raw wafers 100 100 100 100 1 0 0 0 4000

etching 10 10 20 20 0 1 0 0 600 .
lamination 20 20 30 20 0 0 1 0 900
testing 20 10 30 30 0 0 0 1 700
2000 + ✓ 3000 5000 4000 0 0 0 0 0

78
Next let us suppose that we repeat on this tableau all of the pivots that led to the previously
optimal tableau given above. What will the new tableau look like? That is, how does
✓ appear in this new tableau? This question is easily answered by recalling our general
observations on simplex pivoting as left multiplication of an augmented matrix by a sequence
of Gaussian elimination matrices.
Recall that given a problem in standard form,

P maximize cT x
subject to Ax  b, 0  x ,

the initial tableau is an augmented matrix whose block form is given by


A I b
(6.1) .
cT 0 0

Pivoting to an optimal tableau corresponds to left multiplication by a matrix of the form


R 0
G=
yT 1

where the nonsingular matrix R is called the record matrix and where the block form of G
is conformal with that of the initial tableau. Hence the optimal tableau has the form
  
R 0 A I b RA R Rb
(6.2) T T = T T T ,
y 1 c 0 0 (c A y) y bT y

where 0  y, AT y c, and the optimal value is bT y. Now changing the value of one (or
more) of the objective coefficients c corresponds to replacing c by a vector of the form c+ c.
The corresponding new initial tableau is

A I b
(6.3) T .
(c + c) 0 0

Performing the same simplex pivots on this tableau as before simply corresponds to left
multiplication by the matrix G given above. This yields the simplex tableau
 
RA R Rb RA R Rb
(6.4) T T = .
(c + c A y) yT T
b y T
c + (c A y) T T
y T
bT y

That is, we just add c to the objective row in the old optimal tableau. Observe that
this matrix may or may not be a simplex tableau since some of the basic variable cost row
coefficients in c AT y (which are zero) may be non-zero in c + (c AT y). To completely
determine the e↵ect of the perturbation c one must first use Gaussian elimination to return
the basic variabl coefficients in c + (c AT y) to zero. After returning (6.4) to a simplex
tableau, the resulting tableau is optimal if it is dual feasible, that is, if all of the objective

79
row coefficients are non-positive. These non-positivity conditions place restrictions on how
large the entries of c can be before one must pivot to obtain the new optimal tableau.
Let us apply these observations to the Silicon Chip Corp. problem and the question of
determining the breakeven sale price of type 1 chip. In this case the expression c takes the
form c = ✓e1 , where e1 is the first unit coordinate vector. Plugging this into (6.4) gives
0 1 0 1 0 1
1500 ✓ ✓ 1500
B 0 C B 0 C B 0 C
(c AT y) + c = B @
C+B C=B
A @ 0 A @
C.
A
0 0
0 0 0

Therefore, the perturbed tableau (6.4) remains optimal if and only if ✓  1500. That is,
as soon as ✓ increases beyond 1500, type 1 chip enters the optimal production mix, and for
✓ = 1500 we obtain multiple optimal solutions where type 1 chip may be in the optimal
production mix if we so choose. The number 1500 appearing in the optimal objective row is
called the reduced cost for type 1 chip. In general, the negative of the objective row coefficient
for decision variables in the optimal tableau are the reduced costs of these variables. The
reduced cost of a decision variable is the precise amount by which one must increase its
objective row coefficient in order for it to be included in the optimal solution. Therefore, for
nonbasic variables one can compute breakeven sale prices by simply reading o↵ the reduced
costs from the optimal tableau. In the case of the type 1 chip in the Silicon Chip Corp.
problem above, this gives a breakeven sale price of

breakeven price = current price + reduced cost

= $39 + $15 = $54 .

With the long winded derivation of breakeven prices behind us, let us now consider a
more intuitive and simpler explanation. One way to determine the breakeven sale price,
is to determine by how much our profit is reduced if we produce one batch of these chips.
Recall that the objective row coefficients in the optimal tableau correspond to the following
expression for the objective variable z:

z = 145000 1500x1 5x5 100x7 50x8 .

Hence, if we make one batch of type 1 chip, we reduce our optimal value by $1500. Thus, to
recoup this loss we must charge $1500 more for these chips yielding a breakeven sale price
of $39 + $15 = $54 per chip.

6.2 Range Analysis for Objective Coefficients

Range analysis is a tool for understanding the e↵ects of both objective coefficient variations
as well as resource availability variations. In this section we examine objective coefficient
variations. In the previous section we studied the idea of break-even sale prices. These prices
are associated with activities that do not play a role in the currently optimal production

80
schedule. In computing a breakeven price one needs to determine the change in the asso-
ciated objective coefficient that make it efficient to introduce this activity into the optimal
production mix, or equivalently, to determine the smallest change in the objective coefficient
of this currently nonbasic decision variable that requires one to bring it into the basis in
order to maintain optimality. A related question that can be asked of any of the objective
coefficients is what is the range of variation of a given objective coefficient that preserves the
current basis as optimal? The answer to this question is an interval, possibly unbounded, on
the real line within which a given objective coefficient can vary but these variations do not
e↵ect the currently optimal basis.
For example, consider the objective coefficient on type 1 chip analyzed in the previous
section. The range on this objective coefficient is ( 1, 3500] since within this range one need
not change the basis to preserve optimality. Note that for any nonbasic decision variable xi
the range at optimality is given by ( 1, ci + ri ] where ri is the reduced cost of this decision
variable in the optimal tableau.
How does one compute the range of a basic decision variable? That is, if an activity is
currently optimal, what is the range of variations in its objective coefficient within which
the optimal basis does not change. The answer to this question is again easily derived by
considering the e↵ect of an arbitrary perturbation to the objective vector c. For this we again
consider the perturbation c to c and the associated initial tableau (6.3). This tableau yields
the perturbed optimal tableau (6.4). When computing the range for the objective coefficient
of a optimal basic variable xi one sets c = ✓ei .
For example, in the Silicon Chip Corp. problem the decision variable x3 associated with
type 3 chips is in the optimal basis. For what range of variations in c3 = 5000 does the
current optimal basis {x2 , x3 , x4 , x6 } remain optimal? Setting c = ✓e3 in (6.4) we get the
perturbed tableau
x1 x2 x3 x4 x5 x6 x7 x8 b
0.5 1 0 0 .015 0 0 .05 25
5 0 0 0 .05 1 0 .5 50
.
0 0 1 0 .02 0 .1 0 10
0.5 0 0 1 .015 0 .1 .05 5
1500 0 ✓ 0 5 0 100 50 145, 000
This augmented matrix is no longer a simplex tableau since the objective row coefficient of
one of the basic variables, namely x3 , is not zero. To convert this to a proper simplex tableau
we must eliminate ✓ from the objective row entry under x3 . Multiplying the fourth row by
✓ and adding to the objective row gives the tableau
x1 x2 x3 x4 x5 x6 x7 x8 b
0.5 1 0 0 .015 0 0 .05 25
5 0 0 0 .05 1 0 .5 50
.
0 0 1 0 .02 0 .1 0 10
0.5 0 0 1 .015 0 .1 .05 5
1500 0 0 0 5 + 0.02✓ 0 100 0.1✓ 50 145, 000 10✓

81
For this tableau to remain optimal it must be both primal and dual feasible. Obviously
primal feasibility is not an issue, but dual feasibility is due to the presence of ✓ in the
objective row. For dual feasibility to be preserved the entries in the objective row must
remain nonpositive; otherwise, a primal simplex pivot must be taken which will alter the
currently optimal basis. That is, to preserve the current basis as optimal, we must have

5 + 0.02✓  0, or equivalently, ✓  250

.
100 0.1✓  0, or equivalently, 1000  ✓

Thus, the range of ✓ that preserves the current basis as optimal is

1000  ✓  250,

and the corresponding range for c3 that preserves the current basis as optimal is

4000  c3  5250.

Similarly, we can consider the range of the objective coefficient for type 4 chips. For this
we simply multiply the fourth row by ✓ and add it to the objective row to get the new
objective row

1500 0.5✓ 0 0 0 5 0.015✓ 0 100 + 0.1✓ 50 0.05✓ | 145, 000 5✓ .

Again, to preserve dual feasibility we must have

1500 0.5✓  0, or equivalently, 3000  ✓

5 0.015✓  0, or equivalently, 333.3̄  ✓
.
100 + 0.1✓  0, or equivalently, ✓  1000
50 0.05✓  0, or equivalently, 1000  ✓

Thus, the range of ✓ that preserves the current basis as optimal is

333.3̄  ✓  1000,

and the corresponding range for c4 that preserves the current basis as optimal is

3666.6̄  c4  5000.

6.3 Resource Variations, Marginal Values, and Range Analysis

We now consider questions concerning the e↵ect of resource variations on the optimal solu-
tion. We begin with a concrete instance of such a problem in the case of the Silicon Chip
Corp. problem above.
Suppose we wish to purchase more silicon wafers this month. Before doing so, we need
to answer three obvious questions.

82
 a) How many should we purchase?
b) What is the most that we should pay for them?
c) After the purchase, what is the new optimal production schedule?
The technique we develop for answering these questions is similar to the technique used to
determine objective coefficient ranges.. We begin by introducing a variable ✓ for the number
of silicon wafers that will be purchased, and then determine how this variable appears in the
tableau after using the same simplex pivots encoded in the matrix G given above. In this
case the new initial tableau looks like
x1 x2 x3 x4 x5 x6 x7 x8 b

raw wafers 100 100 100 100 1 0 0 0 4000 + ✓

etching 10 10 20 20 0 1 0 0 600 .
lamination 20 20 30 20 0 0 1 0 900
testing 20 10 30 30 0 0 0 1 700
2000 3000 5000 4000 0 0 0 0 0
In the general case, we are discussing perturbations, or variations, to the resource vector
b in the LP P in standard form given above. If we let b denote this variation, then the
associated initial tableau is 
A I b+ b
.
cT 0 0
Again, multiplying on the left by the matrix G gives

RA R Rb + R b
.
(c AT y)T yT yT b yT b
This time the terms R b and y T b encode the complete change to the optimal tableau by
introducing the perturbation b. Clearly this new tableau is dual feasible and so it remains
optimal as long as it remains primal feasible. That is, the new tableau is optimal as long as
0  Rb + R b, or equivalently,
(6.5) Rb  R b .
These inequalities place restrictions on the values b may take and still preserve the opti-
mality of the tableau. If (6.5) holds, then the new optimal value is y T b + y T b. That is, the
rate of change in the optimal value is given by the vector y, the solution to the dual LP.
In the case of the Silicon Chip Corp. problem where we are interested in varying the
number of silicon wafers available, we have b = ✓e1 and the matrix R and vector y are
given by 2 3 0 1
.015 0 0 .05 5
6 .05 1 0 .5 7 B C
R=6 7 and y = B 0 C .
4 .02 0 .1 0 5 @ 100 A
.015 0 .1 .05 50

83
Therefore, the inequality (6.5) takes the form
0 1 0 1
25 0.015
B 50 C B C
B C  ✓ B 0.05 C ,
@ 10 A @ 0.02 A
5 0.015

or equivalently,
25  .015✓ implies ✓ 5000/3
50  .05✓ implies ✓  1000
10  .02✓ implies ✓  500
5  .015✓ implies ✓ 1000/3 ,
which reduces to the simple inequality
1000
 ✓  500.
3
This is the interval on which we may vary ✓ and not change the optimal basis. This interval
is called the range of the raw chip resource in the optimal solution. If the variation ✓ stays
within this interval, then the optimal solution is given by
0 1 0 1
x2 25 + .015✓
B x6 C B C
B C = Rb + R b = B 50 .05✓ C
@ x3 A @ 10 .02✓ A
x4 5 + .015✓

with optimal value

y T b + y T b = 145000 + 5✓.
Observe from the expression for the optimal value that the profit increases by $5 for
every new silicon wafer that we get (up to 500 wafers). That is, if we pay less than $5 over
current costs for new wafers, then our profit increases. The dual value 5 is called the shadow
price, or marginal value, for the raw silicon wafer resource. It represents the increased value
of this resource due to the production process. It tells us the rate at which the optimal value
increases due to increases in this resource. For example, we know that we currently pay $1
per wafer. If another vendor o↵ers wafers to us for $2.50 per wafer, then we should buy
them since our unit increase in profit with this purchase price is $5 $1.5 = $3.5 since $2.5
is $1.5 greater than the $1 we now pay. So in answer to the questions we started out this
discussion with, it seems that we should purchase 500 raw wafers at a purchase price of no
more than $5 + $1 = $6 dollars per wafer. With this purchase the new optimal production
schedule is 0 1 0 1 0 1
x1 0 0
B x2 C B 25 + .015✓ C B 32.5 C
B C=B C = B C
@ x3 A @ 10 .02✓ A @ 0 A .
x4 5 + .015✓ ✓=500
12.5

84
 Is this all of the wafers we should purchase? The answer to this question is not imme-
diately obvious. This is because all we know about the range of values 1000 3
 ✓  500 is
that if we move ✓ beyond these range boundaries, then the optimal basis will change. In
particular, moving ✓ above 500 will introduce a negative entry in the third row of the simplex
tableau. But the tableau will remain dual feasible. Hence to determine then new optimal
solution for ✓ above 500 we must perform a dual simplex pivot in the third row. We can
formally perform this pivot with the variable ✓ staying in the tableau:

x1 x2 x3 x4 x5 x6 x7 x8 b
0.5 1 0 0 .015 0 0 .05 25 + .015✓
5 0 0 0 .05 1 0 .5 50 .05✓
0 0 1 0 .02 0 .1 0 10 .02✓
0.5 0 0 1 .015 0 .1 .05 5 + .015✓
1500 0 0 0 5 0 100 50 145, 000 5✓
.
0.5 1 .75 0 0 0 .075 .05 32.5
5 0 2.5 0 0 1 .25 .5 25
0 0 50 0 1 0 5 0 500 + ✓
0.5 0 .75 1 0 0 .025 .05 12.5
1500 0 250 0 0 0 125 50 147500

Observe that for ✓ > 500 we have pivoted to an optimal tableau with the slack for raw silicon
wafers basic. Hence we cannot use any more wafers and their shadow price has fallen to zero.
The new optimal solution is 0 1 0 1
x1 0
B x2 C B 32.5 C
B C B C
@ x3 A = @ 0 A ,
x4 12.5
and this solution persists regardless of how many more raw silicon wafers we get. The final
conclusion is that we should only buy 500 raw wafers at a price less than 6 per wafer.
Let us briefly review the range analysis for the right hand side coefficients. In the range
analysis for a right hand side coefficient the goal is to determine the range of variation in
a particular right hand side coefficient bi within which the optimal basis does not change.
In this regard it is very similar to objective coefficient range analysis, but in this case we
add ✓ times the column associated with the slack variable si (or xn+i ) to the right hand side
coefficients in the optimal tableau and then determine the variations in ✓ that preserve the
primal feasibility of this tableau.
In the discussion above we computed the range for b1 , or the raw wafer resource. Let us
now do a range analysis on b2 the etching time resource. Note that this resource is slack in
the optimal tableau since it is in the basis. Regardless, the new right hand side resulting

85
from the perturbation b = ✓e2 to b is
0 1
25
B 50 + ✓ C
Rb + R b = B
@ 10 A .
C

To preserve primal feasibility we only require 0  50+✓, or equivalently, 50  ✓. Therefore,

the range for b2 is
[550, +1) .
The upper bound of +1 make sense since etching time is already slack so any more etching
time won’t make any di↵erence. The lower bound of 550 implies that if etching time drops
to 550 or less, then this constraint will be binding in the optimal tableau.
Similarly, we can compute the range for the lamination and testing time resources. For
example, to compute the range of the lamination time resource we simply add ✓ times the
x7 column to the optimal right hand side to get
0 1
25
B 50 C
Rb + R b = B C
@ 10 + 0.1✓ A .
5 0.1✓

To preserve primal feasibility we must have

0  10 + 0.1✓, or equivalently, 100  ✓

.
0  5 0.1✓, or equivalently, ✓  50

Therefore, the range on b3 is

800  b3  950 .

6.4 Pricing Out New Products

Next we consider the problem of adding a new product to our product line. In the context
of the Silicon Chip Corp. problem, we consider a new chip that requires ten hours each of
etching, lamination, and testing time per 100 chip batch. If it can be sold for $ 33.10 per
chip, we would like to know the answer to the following two questions:
(a) Is it efficient to produce?

(b) If it efficient to produce, what is the new production schedule?

We analyze this problem in the same way that we analyzed the two previous problems. That
is, we first determine how this new chip e↵ects the original initial tableau, and then see how
the original pivoting process e↵ects the new initial tableau by multiplying this new tableau
on the left by the matrix G.

86
 In the context of a new product, the original initial tableau is altered by the addition of
a new column: 
anew A I b
.
cnew cT 0 0
Again, multiplying on the left by the matrix G gives

Ranew RA R Rb
(6.6) .
cnew aTnew y (c AT y)T yT yT b

The expression (cnew aTnew y) determines whether this new tableau is optimal or not. The
act of forming this expression is called pricing out the new product. If this number is non-
positive, then the new product does not price out, and we do not produce it since in this
case the new tableau is optimal with the new product nonbasic. If, on the other hand,
(cnew aTnew y) > 0, then we say that the new product does price out and it should be
introduced into the optimal production mix. The new optimal production mix is found by
applying the standard primal simplex algorithm to the tableau (6.6) since this tableau is
primal feasible but not dual feasible.
Let us return to the Silicon Chip Corp. problem and the new chip under consideration.
In this case we have 0 1
100
B 10 C
anew = B C
@ 10 A .
10
We also need to compute cnew . The stated sale price or revenue for each 100 chip batch of
the new chip is $3310. We need to subtract from this number the cost of producing each
100 chip batch. Recall from the Silicon Chip Corp. problem statement that each raw silicon
wafer is worth $1, each hour of etching time costs $40, each hour of lamination time costs
$60, and each hour of inspection time costs $10. Therefore, the cost of producing each 100
chip batch of these new chips is
100 (cost of the raw wafers)
+10 ⇥ 40 (cost of etching time)
+10 ⇥ 60 (cost of lamination time)
+10 ⇥ 10 (cost of testing time)
—–
1200 (total cost) .

Hence the profit on each 100 chip batch of these new chips is $3310 $1200 = $2110, or
$21.10 per chip, and so cnew = 2110. Pricing out the new chip gives
0 1T 0 1
100 5
B 10 C B 0 C
cnew aTnew y = 2110 B C B C
@ 10 A @ 100 A = 2110 2000 = 110 ,
10 50

87
which is positive, and so this chip prices out. The new column in the tableau associated
with this chip is 0 1
1
✓ ◆ B 0 C
Ranew B C
T =BB 1
C .
C
cnew anew y @ 1 A
110
Pivoting on the new tableau yields

xnew x1 x2 x3 x4 x5 x6 x7 x8 b
1 0.5 1 0 0 .015 0 0 .05 25
0 5 0 0 0 .05 1 0 .5 50
1 0 0 1 0 .02 0 .1 0 10
1 0.5 0 0 1 .015 0 .1 .05 5
110 1500 0 0 0 5 0 100 50 145, 000 .
0 0 1 0 1 0 0 .1 .1 20
0 5 0 0 0 .05 1 0 .5 50
0 .5 0 1 1 .005 0 0 .05 15
1 0.5 0 0 1 .015 0 .1 .05 5
0 1555 0 0 110 6.65 0 88.9 55.5 145550

The new optimal solution is 0 1 0 1

xnew 5
B x1 C B 0 C
B C B C
B x2 C=B 20 C .
B C B C
@ x3 A @ 15 A
x4 0

6.5 Fundamental Theorem on Sensitivity Analysis

The purpose of this section is to state and prove a theorem that captures much of the flavor
of the results on sensitivity analysis that we have seen in this section. While there are many
possible results one might choose to present, the theorem we give is a stepping stone to the
more advanced theory of Lagrangian duality. This result focuses on variations in resource
availability. We presented this result in Section 1 of these notes on 2-dimensional LPs.
Let A 2 Rm⇥n , b 2 Rm , and c 2 Rn . This data defines an LP in standard form by

P maximize cT x
subject to Ax  b, 0  x .

We associate P the optimal value function V : Rm 7! R [ {±1} defined by

V (u) = maximize cT x
subject to Ax  b + u, 0  x

88
for all u 2 Rm . Let
F(u) = {x 2 Rn | Ax  b + u, 0  x }
denote the feasible region for the LP associated with value V (u). If F(u) = ; for some
u 2 Rm , we define V (u) = 1.

Theorem 6.1 (Fundamental Theorem on Sensitivity Analysis) If P is primal non-

degenerate, i.e. the optimal value is finite and no basic variable in any optimal tableau takes
the value zero, then the dual solution y ⇤ is unique and there is an ✏ > 0 such that

V (u) = bT y ⇤ + uT y ⇤ whenever |ui |  ✏, i = 1, . . . , m .

Thus, in particular, the optimal value function V is di↵erentiable at u = 0 with rV (0) = y ⇤ .

Proof: Let 
RA R Rb
(c AT y ⇤ ) T (y ⇤ )T bT y ⇤
be any optimal tableau for P. Primal nondegeneracy implies that every component of the
vector Rb is strictly positive. If there is another dual optimal solution ỹ associated with
another tableau, then we can pivot to it using simplex pivots. All of these simplex pivots
must be degenerate since the optimal value cannot change. But degenerate pivots can only
be performed if the tableau is degenerate, i.e. there is an index i such that (Rb)i = 0.
But then the basic variable associated with (Rb)i must take the value zero contradicting the
hypothesis that Rb is a strictly positive vector. Hence the only possible optimal tableau is the
one given. The only other way to have multiple dual solutions is if there is an unbounded ray
of optimal solutions emanating from the optimal solution identified by the unique optimal
tableau. For this to occur, there must be a row in the optimal tableau such that any positive
multiple of that row can be added to the objective row without changing the optimal value.
Again, this can only occur if some (Rb)i is zero leading to the same contradiction. Therefore,
primal nondegeneracy implies the uniqueness of the dual solution y ⇤ .
Next let 0 < < min{(Rb)i | i = 1, . . . , m} . Due to the continuity of the mapping
u ! Ru, there is an ✏ > 0 such that |(Ru)i |  i = 1, . . . m whenever |uj |  ✏ j = 1, . . . , n.
Hence, if we perturb b by u, then

R(b + u) = Rb + Ru Rb e>0

whenever |uj |  ✏ j = 1, . . . , n, where e is the vector of all ones. Therefore, if we perturb b

by u in the optimal tableau with |uj |  ✏ j = 1, . . . , n , we get the tableau

RA R Rb + Ru
(c AT y ⇤ )T (y ⇤ )T bT y ⇤ bT u

which is still both primal and dual feasible, hence optimal with optimal value V (u) =
bT y ⇤ + bT u proving the theorem. ⌅

89