Optimization Methods in Management Science Sensitivity Analysis

Inspirational Quote “On a more serious note, there's going to be a lot more information and updates on here in the coming weeks and I think this will provide you with the opportunity to get to know who I really am.” ‡ Quote of the Day ‡ "A computer only knows what it's been programmed to know..., a mind can think up infinite possibilities." „ Carmen Sandiego Today’s Topic: Sensitivity Analysis Outline: ‡ Jessica is in trouble! ‡ Formulation ‡ Excel model ‡ Sensitivity Analysis ‡ Convexity ‡ Surprises- Guest Appearances! ‡ Our Problem „ A Recent Letter we received: I have been going through some tough times recently and am having a real problem with one of my cosmetic lines. The info for the line is on the next page. Recently though costs are changing based on market demand in addition to highly fluctuating resource costs. My problem is this we currently have an LP that we solve to find the optimal amount to produce of each product. However, every time a parameter changes, I am always forced to resolve the LP and this takes too long. I was hoping you guys could find a better way. Lately I have just been out of it. For example, Nick and I decided to split our Hummer in half, and now I need to buy a new one. Oh yeah, about the LP it seems to have been misplaced when I was moving out of my Malibu house. Please Help! - Jessica Problem Data: See dessertbeauty.com ‡ Jessica sells four types of lip gloss. The resources needed to produce one unit of each are known. Creamy(1) Juicy (2) Dreamy (3) Sunny (4) Raw material 2 3 4 7 Hours of labor 3 4 5 6 $4 $6 $7 $8 Sale price ‡ ‡ ‡ ‡ ‡ Exactly 950 total units must be produced. Customers demand that at least 400 units of product 4 be produced. Formulate an LP to maximize profit. Raw Materials Available <=4600 Labor Available <=5000 Task 1-Formulate the LP ‡ Remember the Three Parts! „ „ „ Decision variables Objective Constraints Don’t Forget Non Negativity. Isn't that my job, to remind them of things? Our LP ‡ Define: „ „ „ „ X1= X2= X3= X4= Amount Amount Amount Amount Max : of of of of Creamy Gloss produced Juicy Gloss produced Dreamy Gloss produced Sunny Gloss produced z = 4x 1 + 6x 2 + 7x 3 + 8x 4 subject to : x 1 + x 2 + x 3 + x 4 = 950 x 4 ≥ 400 2x 1 + 3x 2 + 4x 3 + 7x 4 ≤ 4600 3x 1 + 4x 2 + 5x 3 + 6x 4 ≤ 5000 x1, x 2 , x 3 , x 4 ≥ 0 Solving The Initial LP Which Method? „ Graphical „ Simplex „ Excel ‡ I Agree. Excel it is! ‡ Solving Using Excel ‡ Q: What does every great Magician Need? „ A: An Assistant! ‡ My assistant today is very shy so lets give him a warm welcome! ‡ He will be doing the Excel today! ‡ And here he is now! Our Results Decision Variables: Value x1 0 Objective Function: Total Profit: 6650 x2 400 x3 150 x4 400 Sensitivity Analysis ‡ What can go wrong with a model „ ‡ (eg. Not Kate Moss and Cocaine!) Hint Think of: „ In general: ‡ ‡ ‡ ‡ Based on market demand, prices can change Cost of resources and labor change constantly Amount of resources can change New products can be introduced Sensitivity Analysis ‡ The Big Question(s): „ How/when can I determine if my current solution (or basis) is still optimal given the change without having to resolve the LP? Why is resolving the LP so terrible? ‡ Hint: Think about real world LP’s ‡ M ic ro so ft E x c e l 1 1 .0 S e n sitivity R e p o rt W o rk sh e e t: [S e n sitivity L e c .x ls]Q u e stio n R e p o rt C re a te d : 2 /2 6 /2 0 0 6 7 :2 7 :5 0 P M How We Do This ‡ The Sensitivity Report „ Should it look like this? A d ju s tab le C ells C e ll $C$14 $D$14 $E$14 $F$14 Nam e V alu e x1 V alu e x2 V alu e x3 V alu e x4 F in a l V a lu e 0 400 150 400 Reduced G ra d ie n t -1 .0 0 0 0 0 5 4 8 4 0 0 0 F in a l V a lu e 950 400 4600 4750 L a g ra n g e M u ltip lie r C on strain ts C e ll $C$22 $C$23 $C$24 $C$25 Nam e F u n c tion F u n c tion F u n c tion F u n c tion 3 -2 1 0 VERY Common Error’s ‡ ‡ ‡ Forgetting to Check Assume Non-Negativity Forgetting to Check Assume Linear Model Forgetting That Chicken of the Sea is actually Tuna „ Its not? At Least it’s not turkey!!!! Last is for Jessica Only Under Solver “options” Check these three things before e-mailing your TA!!! The Correct Report Adjustable Cells Final Reduced Objective Allowable Allowable Name Value Cost Coefficient Increase Decrease x1 0 -1 4 1 1E+30 x2 400 0 6 2/3 0.5 x3 150 0 7 1 0.5 x4 400 0 8 2 1E+30 Constraints Final Shadow Constraint Allowable Allowable Name Value Price R.H. Side Increase Decrease Total 950 3 950 50 100 Product 4 400 -2 400 37.5 125 RM 4600 1 4600 250 150 Labor 4750 0 5000 1E+30 250 Before We Get Started ‡ Important Fact „ Jessica Simpson hates Ellen DeGeneres ‡ ‡ We will assume for all conditions derived that degeneracy is not present At the end of the lecture we will show how to modify the conditions when degeneracy is present. Type of Change 1: Changing the Cost Coefficient of a Basic Variable ‡ Problem 1: OJ and Jessica “Hi guys I was at the market and noticed the price of juice went up by 50 cents. That means if I raise the price of the juicy lip gloss by 50 cents I will make more money. Right?” Jessica Type of Change 1: Changing the Cost Coefficient of a Basic Variable ‡ Be careful!! The next steps applies only to basic variables. ‡ Steps to Take: „ Step 1: Check if the change of the objective coefficient is within the allowable range? „ Step 2: If so, the optimal basic feasible solution will not change. Calculate the change in profit. If not, wait till later in the lecture to help! Problem 1: Solutions ‡ Step 1: We want to increase x2 by .5. According to the report, the allowable increase is 66.6 cents. Thus we are within the allowable range. ‡ Step 2: Since we are within the allowable range the optimal solution and BFS remains the same. The change in cost is the additional revenue from x2 * current quantity of x2 „ „ „ Increase in profit = .5*x2=.5*400=$200 Total Profit = 4*0 +6.5*400+7*150+8*400=$6850 Is there an easier way? ‡ ‡ New Profit=Old Profit + Increase in Revenue Total Profit= 6650+200= $6850 Practice: Beat the Clock-2 min! ‡ ‡ In groups solve the following two Problems Problem A „ ‡ Suppose the price of x1 is increased by 60 cents. What is the new optimal solution and change in profit? Problem B „ Suppose the price of x3 is decreased by 60 cents. What is the new optimal solution and change in profit? ‡ Give any insights Practice Solutions ‡ Problem A „ „ ‡ Step 1: Allowable increase for x1 is 1. The increase is within the allowable range. Step 2: The current BFS remains optimal and the change in profit is 0*.6=0. Sorry Jessica!!! Problem B „ „ Step 1: Allowable decrease for x3 is .5. Thus the decrease is outside the allowable range. Step 2: We will have to wait till later in the lecture to determine the effect on profit. However we can comment on the directional change. Type of Change 2: Changing the Cost Coefficient of a Non-Basic Variable ‡ Problem 2: Cream or No Cream “Hello Class, I went to the store to buy some of my cream lip gloss and found out none of it was being produced because it wasn’t profitable. What should I charge to make them in the optimal mix? ~ Jessica(With help of Agent) Type of Change 2: Changing the Cost Coefficient of a Non-Basic Variable ‡ In order to answer this, we need to look at the “reduced costs” „ If the reduced cost of a non basic variable xi is – ri, it means that increasing the “cost” of the variable by ri will lead to an optimum basis that includes xi. „ Since the reduced cost of x1 is -1, we need to increase the price by at least $1 to a price of $5 before an optimal basis with x1 exists. „ What is the relationship between the reduced cost and the z row coefficient? ‡ This is a very common exam error!!!!!! Practice: Lighting Round ‡ ‡ ‡ Problem C: „ What property exists after we increase the price of the cream gloss to exactly $5. Problem D: „ What is the reduced cost of a basic variable? Explain! Problem E: (Assume max problem!) „ Here is an optimal simplex tableau: determine the reduced cost of variable c: Z 1 0 0 a 0 1 0 b 0 0 1 c 2 1 -2 d 1 0 1 RHS 8 1 4 Practice Solutions ‡ Problem C „ ‡ Problem D „ ‡ If we increase the price of cream by 1, then we are indifferent about pivoting it into the basis. Thus there exist multiple optimal solutions. Reduced costs for max problems are nonpositive. They tell us how much we need to increase the price of a product by before we start producing it. If we are already producing it (i.e., it is basic) it has a reduced cost of zero. Problem E „ The reduced cost of c is -2 ‡ Again remember this relationship!!!! Type of Change 3: Changing a Right Hand Side Coefficient ‡ Problem 3: Those Resources “Uggh! You won’t believe this. After seeing me on Newlyweds, MTV decided it would be profitable to make a reality show where instead of having 4600 of raw materials, I have only 4499 .What should I do (that is, what happens to the optimal solution now)? Jessica: Face it Hey you’re old news, ~ Jessica (From Cleaver Maui) Lindsey, Britney isn’t this fun, I love Maui and Paris are in, I’d much rather be on the beach with them. Type of Change 3: Changing a Right Hand Side Coefficient ‡ Steps To Take: „ Step 1: Determine if the right hand side change is within the allowable range using the sensitivity report „ Step 2: If so the optimal basis will NOT change, and we can use the shadow price of the constraint to determine the change in the optimal objective value. „ If we are outside the range, tell Jessica that Nick is dating Britney and she will forget all about it until later in the lecture. Shadow Prices ‡ Definition: „ ‡ The shadow price of the i-th constraint is the amount by which the optimal Z-Value of the LP is improved if the RHS is increased by one unit. VERY IMPORTANT: „ The Shadow Price of the i-th constraint is ONLY valid within the RHS range of the i-th constraint. Problem 3. Solution ‡ Step 1: „ ‡ Since a decrease of 101 is fully within the allowable decrease of 150, the optimal basis remains the same. (However, the values of the basic variables will change since the RHS changed.) Step 2: „ „ The shadow price of the raw materials constraint is 1. Thus the change in the optimal objective is 6650-1*101=6549. Practice: Bid For Time! ‡ Problem F: „ ‡ Problem G: „ ‡ What is the change in the objective function if the number of available labor hours changes to 4800? What if this number is 4700? What can you tell me about the shadow price of a “≥ constraint”? How about an “= constraint”? Problem H: „ What is the only fast food chain that has more stores in the US than McDonald’s? Practice Solutions ‡ Problem F „ Step 1: If the number is 4800, then the change is within the allowable decrease of 250, and the current basis remains optimal. „ Step 2: The shadow price of the labor constraint is zero. Why? Thus the change in the objective is 0 × 200 = 0. „ If the number if 4700, this is a decrease of 300 and we are outside the allowable range. Can you say anything about this case? Practice Solutions ‡ Problem G „ ‡ A “≥ constraint” for a maximization problem always has a nonpositive shadow price. Intuitively, if we increase the RHS, then we further restrict the feasible region, which can not make us better off! We can say nothing about the sign of an “= constraint”. It could be positive, negative, or 0. Problem H „ Subway-> Proof Type of Change 4: Purchasing Extra Resources ‡ Problem 4: Ashley and Raw Materials “Guys, My sister Ashley just lost her recording contract. I know, it’s shocking. Anyway, she needs a job; she is willing to work for 1 hour. She also said she could convert her unit of talent into a unit of raw material, whatever that means. What is the most I should pay for the unit of raw materials and for her? ~ Jessica Type of Change 4: Purchasing Extra Resources ‡ Solution „ Each increases is within the range. So, we can use the shadow prices to determine the change in objective if either change takes place. But we cannot assume that changing both is OK. „ The Raw Material SP is 1, corresponding to a revenue increase of $1 if we accept the offer. Thus to break even or profit we should pay no more then $1 for the unit „ The Labor SP is 0, resulting in no additional revenue if we hire Ashley. And you say our models don’t reflect reality!!! Practice: Deal or No Deal ‡ Problem I „ ‡ Suppose now that Raw Materials cost $5 per unit . Suppose Johnny Knoxville offers to sell you an addition unit for $.50 Should you take the deal? What is the break-even price? Problem J „ Same for labor as problem I Practice Solutions: ‡ Problem I „ The key is to interpret the shadow price as follows: ‡ ‡ If Jessica can buy one more unit at $4, then profits increase by $1 since the shadow price is 1. Thus Jessica could pay 4+1=5 and profits will increase by 1-1=0. Thus the most Jessica should pay is 5. Since 4.5 is less then 5, she should take the deal. Problem J „ The shadow price here is 0. We are not using all of the labor we are given. Additional labor is worthless, and we should not pay for it. Type of Change 5: A New Product ‡ Problem 5: Bunnies “Hey Yall, I just got the best idea for a new flavor of Lip Gloss called Bunny. It contains Tahitian Vanilla. To make some, 8 units of RM are needed and 7 hours of labor are needed. If I sell it for $7, will any be produced?~ Ice Cream For all! Jessica ‡ Steps To Take: „ „ Step 1: Determine if the right hand side change is within the allowable range using the sensitivity report. Step 2: Price out to calculate the reduced cost. Pricing Out ‡ Formula for reduced cost n cnew = cnew − ∑ ai ,new si i =1 ‡ ‡ ‡ If ⎯cnew is non negative then we produce Solution „ ⎯cnew = 7-(3)(1)+(2)(0)-(1)(8)-(0)(7)=-4 „ We do not produce! Problem K: Determine the amount that the price would have to increase before we produce . „ Solution: 11 Type of Change 6: Parametrics ‡ Problem 6: Raw Materials “Guys, what would a graph of the optimal objective value look like that used the amount of available raw materials as a parameter?~ Definitely Not Jessica Simpson ‡ ‡ Lets Solve this Problem on the Board! Problem L: „ Describe How this would look if we used the amount of sunny needed as the parameter? Type of Chance 6: Parametrics ‡ If we have no raw materials available what type of problem do we have? „ ‡ Infeasible, can’t produce any of sunny type. If we have 4600 raw materials what is the optimal objective value? How about 4599 or 4601 „ „ „ For 4600 z=$6650 (This was our initial LP) For 4561 z=$6650+1=$6651 (Each unit is worth 1 in this range since the shadow price is 1) By examining the allowable range we see between 4450 and 4850 for each additional unit the objective increases by 1. Type of Change 6: Parametrics ‡ Let’s review are we now? „ „ In Cambridge Our graph of raw materials vs. z looks like Type of Change 6: Parametrics ‡ Problem L: „ ‡ How do we determine the minimum amount of raw materials such that the problem is feasible? Solution: „ Solve the problem for rm=4449 and see the allowable decrease is 549, and the shadow price is 2. So there is a feasible solution with 3900 units. Next we resolve the problem for rm=3899.99 and there is no feasible solution. Type of Change 6: Parametrics ‡ Let’s review are we now? „ Our graph of raw materials vs. z looks like Type of Change 6: Parametric’s ‡ Problem M: „ ‡ How do we complete the graph Solution „ Solve the problem for rm=4850.0001 this gives us a shadow price of zero. What is the allowable increase for this range? ‡ Use Logic Not Math Type of Change 6: Parametric’s ‡ Let’s review are we now? „ Our graph of raw materials vs. z looks like Practice: Short Answer ‡ Problem : N „ ‡ Problem : O „ ‡ What type of function is our graph? Is it possible for an optimal BFS to have more then one shadow price correspond to a constraint? Problem : P „ A world record will be set today what is it? Practice: Short Answer ‡ Problem N: „ ‡ It is a piecewise linear concave graph Problem O: Yes it is. When an LP has multiple optimal solutions multiple shadow prices are possible. This occurred at the breakpoints of our graph „ ‡ Problem P: Mike will break the record for most hours of taught in a day. 3 hours of lecture, 2 hours of pod casts, 3 hours of recitation „ Trivia ‡ Question „ ‡ Answer: „ ‡ What talk show is Hillary Duff appearing on this week? The Ellen DeGeneres Show Did somebody say degeneracy? „ Up until now we have assumed all BFS’s were non degenerate. What happens if a basis is degenerate? Degeneracy Notes ‡ Three Oddities Occur When a BFS is degenerate „ Oddity 1: In the RANGE IN WHICH THE BASIS IS UNCHANGED at least one constraint will have a 0 AI or AD. This means that for at least one constraint, the SHADOW PRICE can tell us about the new z-value for either an increase or decrease in the RHS, but not both. „ Oddity 2: For a nonbasic variable to become positive, a nonbasic variable’s objective function coefficient may have to be improved by more than its REDUCED COST. Degeneracy Notes ‡ Three Oddities Occur When a BFS is degenerate „ Oddity 3: Increasing a variable’s objective function coefficient by more than its AI or decreasing it by more than its AD may leave the optimal solution the same. „ Remember when performing analysis, always ask first if the current BFS is degenerate. If so follow the rules on this slide Summary of Lecture ‡ Using Excel to determine information ‡ Shadow prices ‡ Determining upper and lower bounds so that the shadow price remains valid. Our LP ‡ Define: „ „ „ „ X1= X2= X3= X4= Amount Amount Amount Amount Max : of of of of Creamy Gloss produced Juicy Gloss produced Dreamy Gloss produced Sunny Gloss produced z = 4x 1 + 6x 2 + 7x 3 + 8x 4 subject to : x 1 + x 2 + x 3 + x 4 = 950 x 4 ≥ 400 2x 1 + 3x 2 + 4x 3 + 7x 4 ≤ 4600 3x 1 + 4x 2 + 5x 3 + 6x 4 ≤ 5000 x1, x 2 , x 3 , x 4 ≥ 0