Sensitivity Analysis

Report
Operation Research (OR)
RG753
Sensitivity Analysis
October 15, 22, 29
FA L L 2 0 1 4
DE PA RTMENT OF RS & G I SC
I N STITUTE OF S PACE T ECHN OLOGY
Why we need Sensitivity Analysis?
•
Most of the parameter values used in the original model are just estimates of future
conditions
•
Therefore, their effect on the optimal solution needs to be investigated
•
Sensitivity analysis is concerned with how changes in an LP’s parameters affect the optimal
solution
A Graphical Introduction to Sensitivity Analysis
Book=Winston
•
Let c1 be the contribution to profit by each soldier (x1). For what values of c1 does the current
basis remain optimal?
•
Currently, c1 = 3, and each isoprofit line has the form 3x1+2x2 = constant, or
x2 = -(3/2) x1+constant/2
•
Each isoprofit line has a slope of -3/2
— From Figure 1, we see that if a change in c1 causes the isoprofit
lines to be flatter than the carpentry constraint
— Then the optimal solution will change from the current optimal
solution (point B) to a new optimal solution (point A)
— If the profit for each soldier is c1, the slope of each isoprofit line will
be - c1/2
— Because the slope of the carpentry constraint is -1, the isoprofit
lines will be flatter than the carpentry constraint if - c1/2 > -1 or c1<
2,
— The current basis will no longer be optimal
— The new optimal solution will be (0, 80), point A in Figure 1
— Similarly, If the isoprofit lines are steeper than the finishing
constraint, then the optimal solution will change from point B to
point C
Summary:
• if all other parameters remain unchanged
— The slope of the finishing constraint is -2.
• the current basis remains optimal for
2 ≤ c1 ≤ 4
— If - c1/2 < -2 or c1> 4, then the current basis is no longer optimal
and point C, (40, 20), will be optimal
• Giapetto should still manufacture 20 soldiers and 60
trains
• But the profit will change
Effect of a Change in a Right-Hand Side on the
LP’s Optimal Solution
•
A graphical analysis can also be used to determine whether a change in the right-hand side
of a constraint will make the current basis no longer optimal
•
In current optimal solution, the carpentry and finishing constraints are binding
•
Let b1 be the number of available finishing hours
•
Currently, b1 =100, for what values of b1 does the current basis remain optimal?
•
Any change in b1 will shift the finishing constraint parallel to its current position
•
If we change the value of b1, then as long as the point where the finishing and carpentry
constraints are binding remains feasible, the optimal solution will still occur where the
finishing and carpentry constraints intersect.
•
if b1 > 120, then the point where the finishing and
carpentry constraints are both binding will lie on the
portion of the carpentry constraint below point D
•
In this region, x1 > 40, and the demand constraint for
soldiers is not satisfied
•
Thus, for b1>120, the current basis will no longer be
optimal
•
Similarly, if b1< 80, then the carpentry and finishing
constraints will be binding at an infeasible point having
x1< 0, and the current basis will no longer be optimal
• Thus (if all other parameters remain unchanged), the current
basis remains optimal if 80 ≤ b1 ≤ 120
• Although, the current basis remains optimal, the value of the
decision variables and the objective function value change.
•
Consider a constraint with positive slack (or positive excess) in an LP’s optimal solution; if we
change the right-hand side of this constraint in the range where the current basis remains
optimal, then the optimal solution to the LP is unchanged
Check Winston Book to understand the above comment!!!
Shadow Price of a constraint
•
How a change in a constraint’s right-hand side changes the LP’s optimal z-value?
•
Shadow price for the ith constraint of an LP is the amount by which the optimal z-value is
improved—increased in a max problem and decreased in a min problem— if the right-hand
side of the ith constraint is increased by 1
•
This definition applies only if the change in the right-hand side of Constraint i leaves the
current basis optimal
•
Whenever the slack or excess variable for a constraint is positive in an LP’s optimal solution,
the constraint will have a zero shadow price (please check Winston Book)
Shadow price of constraint 2 = 1
The Computer and Sensitivity Analysis
•
Graphically we can do this analysis for 2-decision variables
•
Hand calculations are tedious
•
Now we will discuss the interpretation of the sensitivity analysis information on the LINDO
output
•
To obtain a sensitivity report in LINDO, select ‘Yes’ when asked (after solving LP)
Objective Function Coefficient Ranges
•
Gives the range of values for an objective function coefficient for which the current basis
remains optimal
•
For each objective function coefficient, this range is given in the OBJECTIVE COEFFICIENT
RANGES portion of the LINDO output
•
The ALLOWABLE INCREASE (AI) section indicates the amount by which an objective function
coefficient can be increased with the current basis remaining optimal
•
Similarly, the ALLOWABLE DECREASE (AD) section indicates the amount by which an
objective function coefficient can be decreased with the current basis remaining optimal
•
If ci remains in its allowable range then the values of the decision variables remain
unchanged, although the optimal z-value may change
Reduced Costs and Sensitivity Analysis
•
The REDUCED COST portion of the LINDO output gives us information about how changing
the objective function coefficient for a nonbasic variable will change the LP’s optimal
solution
•
For any nonbasic variable xk, the reduced cost is the amount by which the objective function
coefficient of xk must be improved before the LP will have an optimal solution in which xk is a
basic variable.
•
If the objective function coefficient of a nonbasic variable xk is improved by its reduced cost
(increase in Max and decrease in Min LPs), then the LP will have alternative optimal
solutions—
◦ at least one in which xk is a basic variable, and
◦ at least one in which xk is not a basic variable
•
If the objective function coefficient of a nonbasic variable xk is improved by more than its
reduced cost, then any optimal solution to the LP will have xk as a basic variable and xk > 0
Refer Ex-1
•
Optimal bfs has Basic variables x2, x3, x4, and s4
•
x1 = nonbasic with $1 reduced cost
•
This implies that if we increase x1’s objective function coefficient (in this case, the sales price
per unit of x1) by exactly $1, then there will be alternative optimal solutions, at least one of
which will have x1 as a basic variable
•
If we increase x1’s objective function coefficient by more than $1, then any optimal solution
to the LP will have x1 as a basic variable
•
Thus, the reduced cost for x1 is the amount by which x1 “misses the optimal basis”
•
We must keep a close watch on x1’s sales price, because a slight increase will change the LP’s
optimal solution
Right-Hand Side Ranges
•
Range of values for a right-hand side within which the current basis remains optimal
•
This information is given in the RIGHTHAND SIDE RANGES section of the LINDO output
•
Consider the first constraint in Example 1. Currently, the right-hand side of this constraint (call it b1) is 950
•
The current basis remains optimal if b1 is decreased by up to 100 (the allowable decrease, or AD, for b1) or
increased by up to 50 (the allowable increase, or AI, for b1)
•
Thus, the current basis remains optimal if
850 =950 - 100 ≤ b1 ≤ 950 + 50 = 1,000
•
We call this the allowable range for b1
•
LINDO output does not provide sufficient information to determine the new values of the decision
variables
•
LINDO output does allow us to determine the LP’s new optimal z-value using
Shadow Prices and Dual Prices
•
Shadow price of an LP’s ith constraint is the amount by which the optimal z-value of the LP is
improved if the right-hand side is increased by one unit (assuming this change leaves the
current basis optimal)
•
If, after a change in a constraint’s right-hand side, the current basis is no longer optimal, then
the shadow prices of all constraints may change
•
The shadow price for each constraint is found in the DUAL PRICES section of the LINDO
output
•
If we increase the right-hand side of the ith constraint by an amount bi (decrease means this
value is <0)
— And the new right-hand side value for Constraint i remains within the allowable range for the righthand side given in the RIGHTHAND SIDE RANGES section of the output,
— then formulas (1) and (2) may be used to determine the optimal z-value after a right-hand side is
changed.
Interpretation to the Shadow Price
Refer Example 1 (assuming that we are within the allowable range where the current basis remains
optimal)
•
The shadow price of $3 for Constraint 1 in Example 1 implies that each one-unit increase in total
demand will increase sales revenues by $3
•
The shadow price of $2 for Constraint 2 implies that each unit increase in the requirement for
product 4 will decrease revenue by $2
•
The shadow price of $1 for Constraint 3 implies that an additional unit of raw material given to
Winco (for no cost) increases total revenue by $1.
•
Finally, the shadow price of $0 for Constraint 4 implies that an additional unit of labor given to
Winco (at no cost) will not increase total revenue.
•
This is reasonable; at present, 250 of the available 5,000 labor hours are not being used, so why
should we expect additional labor to raise revenues?
Signs of Shadow Prices
•
A ≥ constraint will always have a non-positive shadow price;
•
a ≤ constraint will always have a nonnegative shadow price;
•
and an = constraint may have a positive, negative, or zero shadow price
•
Adding something in ≥ constraint will eliminate points to an LP’s feasible region
—
•
Adding something in ≤ constraint will add points from an LP’s feasible region
—
•
Thus, the optimal z-value must decrease or stay the same, implying that the shadow price of this
constraint must be non-positive
Thus, the optimal z-value must increase or stay the same, implying that the shadow price of this
constraint must be nonnegative
Same for Min LP
Sensitivity Analysis and Slack and Excess Variables
•
Any constraint whose slack or excess variable is > 0 will have a zero shadow price
•
Any constraint with a nonzero shadow price must be binding (have slack or excess equal to 0)
Example 1
•
The Labor constraint has positive slack, so its shadow price must be 0.
•
This is reasonable, because slack 250 for this constraint indicates that 250 hours of currently
available labor are unused at present. Thus, an extra hour of labor would not increase revenues.
•
The raw material constraint has a nonzero shadow price, it must have slack 0.
•
This is reasonable; the nonzero shadow price means that additional raw material will increase
revenue. This can be the case only if all currently available raw material is now being used.
Continue….
•
For constraints with nonzero slack or excess, the value of the slack or excess variable is related to the
ALLOWABLE INCREASE and ALLOWABLE DECREASE sections of the RIGHTHAND SIDE RANGES portion
of the LINDO output. This relationship is detailed in Table 4.
•
For any constraint having positive slack or excess, the optimal z-value and values of the decision
variables remain unchanged within the right-hand side’s allowable range
•
See Example 1 to verify
Degeneracy and Sensitivity Analysis
•
A bfs is degenerate if at least one basic variable in the optimal solution = 0
•
For an LP with m constraints, if the LINDO output indicates that less than m variables are
positive, then the optimal solution is a degenerate bfs
•
When the optimal solution to an LP is degenerate, caution must be used when interpreting
the LINDO output
•
Read page 240 of Winston book for further clarification
Reading Assignment
•
Please read from Winston’s book “Managerial Use of Shadow Prices”
Quiz2- (Q3.4-12 of Text Book)
The Fagersta Steelworks currently is working two mines to obtain its iron ore. This iron ore is shipped
to either of two storage facilities. When needed, it then is shipped on to the company’s steel plant.
The diagram below depicts this distribution network, where M1 and M2 are the two mines, S1 and S2
are the two storage facilities, and P is the steel plant. The diagram also shows the monthly amounts
produced at the mines and needed at the plant, as well as the shipping cost and the maximum amount
that can be shipped per month through each shipping lane.
•
Management now wants to determine the most economical plan for shipping the iron ore from
the mines through the distribution network to the steel plant.
a) Formulate a linear programming model for this problem.
b) Bonus: Solve this problem using LINDO
Range of Optimality and 100% Rule
•
Consider the following linear program:
Min 6x1 + 9x2
s.t.
x1 + 2x2 < 8
10x1 + 7.5x2 > 30
x2 > 2
x1, x2 > 0
($ cost)
Solution
OBJECTIVE FUNCTION VALUE = 27.000
Variable
x1
x2
Constraint
1
2
3
Value
1.500
2.000
Slack/Surplus
2.500
0.000
0.000
Reduced Cost
0.000
0.000
Dual Price
0.000
-0.600
-4.500
•
(continued)
OBJECTIVE COEFFICIENT RANGES
Variable
Lower Limit
Current Value
Upper Limit
x1
0.000
6.000
12.000
x2
4.500
9.000
No Limit
RIGHTHAND SIDE RANGES
Constraint Lower Limit Current Value
Upper Limit
1
5.500
8.000
No Limit
2
15.000
30.000
55.000
3
0.000
2.000
4.000
Question???
•
If simultaneously the cost of x1 was raised to $7.5 and the cost of x2 was reduced to $6,
would the current solution remain optimal?
Answer
If c1 = 7.5, the amount c1 changed is 7.5 - 6 = 1.5. The maximum allowable increase is 12 - 6 =
6, so this is a 1.5/6 = 25% change. If c2 = 6, the amount that c2 changed is 9 - 6 = 3. The
maximum allowable decrease is 9 - 4.5 = 4.5, so this is a 3/4.5 = 66.7% change. The sum of
the change percentages is 25% + 66.7% = 91.7%. Since this does not exceed 100% the
optimal solution would not change.
Summary
Optimization vs. Sensitivity Analysis
•
Optimization seeks to answer the question “What is Best?”
•
Sensitivity Analysis is to answer “What If?” question
Sensitivity Analysis
•
What if analysis
•
Uncertainty analysis
•
Tolerance analysis
•
Post-optimality analysis
•
Allowable increase and decrease
Why Sensitivity Analysis?
•
Models can only capture few aspects of reality
•
There are unavoidable presence of uncertainties
•
Decision making is always hard in unpredictable environment
•
How to cope with uncertainties?
How to cope with uncertainties?
•
Investigate the effect of changing the parameter values used in the model
•
Identify which parameters have the greatest impact on the model out
•
Do further analysis and evaluation of those parameters
Methodology
1.
Start with a “base case”
2.
Make a slight change in the value of that parameter while holding other parameters
unchanged
3.
Determine the limits of uncertainty for input parameter (± or % change)
Benefits
•
Beneficial in determining the direction of future data collection activities
•
Relatively sensitive data would require more attention (determine more accurately) as
compared to the data which is relatively less sensitive
•
Helps in making good decisions
Sensitivity Analysis and Duality
Concept of Duality
•
Every linear programming problem has associated with it another linear programming
problem called the Dual
•
The original problem is called the Primal
•
If the primal is a Max problem, then the dual will be a Min problem, and vice versa
•
Knowledge of duality will also provide additional insights into sensitivity analysis
Duality Theory
•
Assumption: The primal linear programming problem is in our standard form (but with no
restriction that the bi values need to be positive)
•
Consider a max problem in which all variables are required to be nonnegative and all
constraints are ≤ constraints (called a normal max problem).
•
The dual problem uses exactly the same parameters as the primal problem, but in different
locations
(A)
(B)
1.
The parameters for a constraint in either problem are the coefficients of a variable in the other
problem
2.
The coefficients for the objective function of either problem are the right sides for the other
problem
•
The ith dual constraint corresponds to the ith primal variable xi .In a similar fashion, dual variable yi
is associated with the ith primal constraint
1.
A min problem such as (B) that has all constraints and all variables nonnegative is called a normal
min problem
2.
If the primal is a normal min problem such as (B), then we define the dual of (B) to be (A)
Interpreting the Dual of a Max Problem
Suppose an entrepreneur wants to purchase all of Dakota’s resources. Then the entrepreneur
must determine the price he or she is willing to pay for a unit of each of Dakota’s resources. With
this in mind, we define;
•
The resource prices y1, y2, and y3 should be determined by solving the Dakota dual (20)
•
The total price that should be paid for these resources is 48y1+20y2+8y3
•
The objective function for the Dakota dual is min w = 48y1+20y2+8y3
•
In setting resource prices, what constraints does the entrepreneur face?
─
•
Resource prices must be set high enough to induce Dakota to sell
For example, the entrepreneur must offer Dakota at least $60 for a combination of resources
that includes
─
8 board feet of lumber, 4 finishing hours, and 2 carpentry hours
•
because Dakota could, if it desires, use these resources to produce a desk that can be sold
for $60
•
The entrepreneur is offering 8y1+4y2+2y3 for the resources used to produce a desk, so he or
she must choose y1, y2, and y3 to satisfy
8y1+4y2+2y3 ≥ 60
•
Similar reasoning shows that at least $30 must be paid for the resources used to produce a
table and $20 for a chair
•
Solution to the dual of the Dakota problem does yield prices for lumber, finishing hours, and
carpentry hours
•
In summary, when the primal is a normal max problem, the dual variables are related to the
value of the resources available to the decision maker
•
For this reason, the dual variables are often referred to as resource shadow prices
Shadow Prices
•
The shadow price of the ith constraint of a linear programming problem is the amount by
which the optimal z-value is improved if the right-hand side is increased by 1
•
The shadow price of the ith constraint is the DUAL PRICE for row i +1 in the LINDO output
Home assignment
•
Read “Interpreting the Dual of a Min Problem” --- page 303 of Winston
•
Read “Duality and Sensitivity Analysis” page 323 of Winston

similar documents