15.053
Thursday, February 28
• Sensitivity Analysis 2
– More on pricing out
– Effects on final tableaus
Handouts: Lecture Notes
1
Partial summary of last lecture
• The shadow price is the unit change in the optimal
objective value per unit change in the RHS.
• The shadow price for a “≥ 0” constraint is called the
reduced cost.
• Shadow prices usually but not always have
economic interpretations that are managerially
useful.
• Shadow prices are valid in an interval, which is
provided by the Excel Sensitivity Report.
• Reduced costs can be determined by pricing out
2
Running Example (from lecture 4)
• Sarah can sell bags consisting of 3
gadgets and 2 widgets for $2 each.
• She currently has 6000 gadgets and
2000 widgets.
• She can purchase bags with 3 gadgets
and 4 widgets for $3.
• Formulate Sarah’s problem as an LP
and solve it.
3
Shadow Prices can be found by
examining the initial and final tableaus!
4
The Initial Basic Feasible Solution
Apply the min
ratio rule
min
(6/3, 2/2).
The basic feasible solution is x1 = 0, x2 = 0, x3 = 6, x4 = 2
What is the entering variable? x2
What is the leaving variable? x4
5
The 2nd Tableau
The basic feasible solution is x1 = 0, x2 = 1, x3 = 3, x4 = 0, z = 2
What is the next entering variable? x1
What is the next leaving variable?
x3
6
The 3rd Tableau
The optimal basic feasible solution is
x1 = 1, x2 = 3, x3 = 0, x4 = 0, z = 3
7
Shadow Price
• The shadow price of a constraint is the
increase in the optimum objective value
per unit increase in the RHS coefficient,
all other data remaining equal.
• What is the shadow price for constraint
1, gadgets on hand?
• This is the value of an extra gadget on
hand.
8
Shadow price vs slack variable
Claim: increasing the 6 to a 7 is mathematically equivalent
to replacing “x3 ≥ 0” with “x3 ≥ -1”. This is also the
reduced cost for variable x3.
Reason 1. Permitting Sarah to have 7 thousand gadgets is
equivalent to giving her 6 thousand and letting her use 1
thousand more than she has (at no cost).
9
Shadow price vs slack variable
Claim: increasing the 6 to a 7 is mathematically equivalent
to replacing “x3 ≥ 0” with “x3 ≥ -1”. This is also the
reduced cost for variable x3.
Reason 2. Any solution to the original problem can be
transformed to a solution with RHS 7 by subtracting 1
from x3.
x1 = 0, x2 = 1, x3 = 3, x4 = 0 => x1 = 0, x2 = 1, x3 = 2, x4 = 0
10
Shadow price
vs slack variable
Looking at the
slack variable
in the final
tableau reveals
shadow prices.
What is the optimal solution if x3 ≥ 0?
What is the optimal solution if x3 ≥ -1?
What is the shadow price for constraint 1?
11
Quick Summary
• Connection between shadow prices and
reduced cost. If xj is the slack variable for a
constraint, then its reduced cost is the
negative of the shadow price for the
constraint.
• The reduced cost for a variable is its cost
coefficient in the final tableau
• To do with your partner: what is the shadow
price for the 2nd constraint (widgets on
hand)?
12
13
The cost row in
the final tableau
is obtained by
adding multiples
of original
constraints to the
original cost row.
14
How are
the reduced
costs in the
2nd tableau
below
obtained?
Take the initial
cost coefficients.
Then subtract 1/3
of constraint 1.
15
Next: subtract
½ of constraint
2 from these
costs.
16
How are
the reduced
costs in the
2nd tableau
below
obtained?
Subtract 1/3 of
constraint 1
and ½ of
constraint 2
from the initial
costs.
17
Implications of Reduced Costs
• Implication 1: increasing the cost
coefficient of a non-basic variable by Δ
leads to an increase of its reduced cost
by Δ.
18
What is the
effect of
adding Δ to
the cost
coefficient
for x3?
FACT: Adding Δ to
the cost coefficient in
an initial tableau also
adds Δ to the same
coefficient in
subsequent tableaus
19
What is the
effect of
adding Δ to
the cost
coefficient
for x2?
20
Subtract Δ
times row 3
from row 1 to
get it back in
canonical form.
How large can
Δ be?
Δ ≤ 1 for the
tableau to
remain optimal.
Bound on
changes in cost
coefficients.
21
Implications of Reduced Costs
• Implication 2: We can compute the
reduced cost of any variable if we know
the original column and if we know the
“prices” for each constraint.
22
Suppose that
we add
another
variable, say
x5. Should we
produce x5?
What is
?
23
= 3/2 - 2*1/3 – 1*1/2 = 1/3
FACT: We can
compute the
reduced cost of a
new variable. If
the reduced cost
is positive, it
should be entered
into the basis.
24
More on Pricing Out
• Every tableau has “prices.” These are
usually called simplex multipliers.
• The prices for the optimal tableau are
the shadow prices.
25
Simplex Multipliers
π1=1/3
π2= 1/2
FACT: x2 is a
basic variable
and so
26
A useful fact from linear algebra
• If column j in the initial tableau is a
linear combination of the other
columns, then it is the same linear
combination of the other columns in
the final tableau.
• e.g., if A.3 = A.2 + 2 A.1 , then
27
28
29
30
31
32
33
34
35
36
On varying the RHS
• Suppose one adds Δ to b1.
– This is equivalent to adding Δ times
the column corresponding to the first
slack variable
– One can compute the shadow price
and also the effect on
• This transformation also provides
upper and lower bounds on the interval
for which the shadow price is valid.
37
38
Summary of Lecture
•
•
•
•
•
Using tableaus to determine information
Shadow prices and simplex multipliers
Changes in cost coefficients
Linear relationships between columns in the
original tableau are preserved in the final
tableau.
• Determining upper and lower bounds on Δ so
that the shadow price remains valid.
39
Descargar

What is the shadow price for constraint 1?