8Chapter1WhatisOptimization?1.5SensitivityAnalysis,ReducedCosts,andDualPricesRealistic LPs require large amounts of data.Accuratedata are expensive to collect,so we willgenerallybeforced to use data in which we have less than complete confidence.Atime-honored adagein data processing circles is“garbage in, garbage out"A user of a model should be concerned withhowtherecommendationsofthemodelarealteredbychangesintheinputdata.Sensitivityanalysisistheterm applied totheprocess of answering this question.Fortunately,an LP solutionreportprovidessupplemental information that is useful in sensitivity analysis. This information falls under twoheadings,reducedcostsanddualprices.Sensitivity analysis can reveal which pieces of information should be estimated most carefullyFor example,if it is blatantly obvious that a certain productis unprofitable, then little effort need beexpended in accurately estimating its costs.The first law of modeling is"do not waste time accuratelyestimating a parameter if a modest error in the parameter has little effect on the recommendeddecision".1.5.1ReducedCostsAssociated with each variable in any solution is a quantity known as the reduced cost. If the units ofthe objective function are dollars and the units of the variable aregallons, then theunits of the reducedcost are dollars per gallon. The reduced cost of a variable is the amount by which the profitcontribution of the variable must be improved (e.g-, by reducing its cost) before the variable inquestion wouldhaveapositive valuein an optimal solution.Obviously,avariable that already appearsin theoptimal solution will havea zero reduced cost.Itfollows that a second, correct interpretation of the reduced cost is that it is the rate at which theobjective function valuewill deteriorate ifavariable,currentlyat zero,is arbitrarilyforced to increasea small amount.Suppose the reduced cost of x is s2/gallon.This means,if theprofitability of x wereincreased by s2/gallon, then 1 unit of x (if 1 unit is a “small change") could be brought into thesolution without affecting the total profit.Clearly,the total profit would be reduced byS2 if x wereincreased by1.0 without altering its original profit contribution.1.5.2DualPricesAssociated with each constraint is a quantity known as the dual price.If the units of the objectivefunction are cruzeiros and the units of the constraint in question are kilograms, then the units of thedual price are cruzeiros per kilogram.The dual price of a constraint is the rate at which the objectivefunctionvalue will improve as the right-hand side or constant term of the constraint is increased asmall amount.Different optimization programs may use different sign conventions with regard to the dual prices.The LINGO computer program uses the convention that a positive dual price means increasing theright-hand side in question will improve the objective function value. On the other hand, a negativedual price means an increase in the right-hand side will cause the objective function value todeteriorate. A zero dual price means changing the right-hand side a small amount will have no effecton the solution valueIt follows that, under this convention, ≤constraints will have nonnegative dual prices,≥ constraints will have nonpositive dual prices,and =constraints can have dual prices of any signWhy?Understanding Dual Prices. It is instructive to analyze the dual prices in the solution to theEnginola problem.The dual price on the constraint A≤60 is 5/unit.At first, one might suspect thisquantity should be s20/unitbecause,if one more Astro is produced, the simple profit contribution of
8 Chapter 1 What is Optimization? 1.5 Sensitivity Analysis, Reduced Costs, and Dual Prices Realistic LPs require large amounts of data. Accurate data are expensive to collect, so we will generally be forced to use data in which we have less than complete confidence. A time-honored adage in data processing circles is “garbage in, garbage out”. A user of a model should be concerned with how the recommendations of the model are altered by changes in the input data. Sensitivity analysis is the term applied to the process of answering this question. Fortunately, an LP solution report provides supplemental information that is useful in sensitivity analysis. This information falls under two headings, reduced costs and dual prices. Sensitivity analysis can reveal which pieces of information should be estimated most carefully. For example, if it is blatantly obvious that a certain product is unprofitable, then little effort need be expended in accurately estimating its costs. The first law of modeling is "do not waste time accurately estimating a parameter if a modest error in the parameter has little effect on the recommended decision". 1.5.1 Reduced Costs Associated with each variable in any solution is a quantity known as the reduced cost. If the units of the objective function are dollars and the units of the variable are gallons, then the units of the reduced cost are dollars per gallon. The reduced cost of a variable is the amount by which the profit contribution of the variable must be improved (e.g., by reducing its cost) before the variable in question would have a positive value in an optimal solution. Obviously, a variable that already appears in the optimal solution will have a zero reduced cost. It follows that a second, correct interpretation of the reduced cost is that it is the rate at which the objective function value will deteriorate if a variable, currently at zero, is arbitrarily forced to increase a small amount. Suppose the reduced cost of x is $2/gallon. This means, if the profitability of x were increased by $2/gallon, then 1 unit of x (if 1 unit is a “small change”) could be brought into the solution without affecting the total profit. Clearly, the total profit would be reduced by $2 if x were increased by 1.0 without altering its original profit contribution. 1.5.2 Dual Prices Associated with each constraint is a quantity known as the dual price. If the units of the objective function are cruzeiros and the units of the constraint in question are kilograms, then the units of the dual price are cruzeiros per kilogram. The dual price of a constraint is the rate at which the objective function value will improve as the right-hand side or constant term of the constraint is increased a small amount. Different optimization programs may use different sign conventions with regard to the dual prices. The LINGO computer program uses the convention that a positive dual price means increasing the right-hand side in question will improve the objective function value. On the other hand, a negative dual price means an increase in the right-hand side will cause the objective function value to deteriorate. A zero dual price means changing the right-hand side a small amount will have no effect on the solution value. It follows that, under this convention, d constraints will have nonnegative dual prices, t constraints will have nonpositive dual prices, and = constraints can have dual prices of any sign. Why? Understanding Dual Prices. It is instructive to analyze the dual prices in the solution to the Enginola problem. The dual price on the constraint A d 60 is $5/unit. At first, one might suspect this quantity should be $20/unit because, if one more Astro is produced, the simple profit contribution of
WhatisOptimization?Chapter19this unit is s20. An additional Astro unit will require sacrifices elsewhere, however. Since all of thelabor supply is being used, producing more Astros would require the production of Cosmos to bereduced in order to free up labor.The labor tradeoff ratefor Astros and Cosmos is /..That is,producing one more Astro implies reducing Cosmo production by / of a unit.Thenet increase inprofits is $20-(1/2)* $30= $5, because Cosmos have a profit contribution of $30 per unit.Now,consider thedual priceof S15/hour on thelaborconstraint.If wehave1morehourof labor,it will be used solely to producemore Cosmos.One Cosmo has a profit contribution of s30/unit.Since1 hour of labor is only sufficientfor one half of a Cosmo, the value of the additional hour of labor is$15.1.6UnboundedFormulationsIf we forget to include the labor constraint and the constraint on the production of Cosmos, then anunlimited amountofprofitispossiblebyproducinga largenumber of Cosmos.This is illustrated hereMAX = 20 * A + 30 * C;A<=60;ThisgeneratesanerrorwindowwiththemessageUNBOUNDED SOLUTIONThere is nothing to prevent C from being infinitely large. The feasible region is illustrated inFigure 1.7. In larger problems, there are typically several unbounded variables and it is not as easy toidentifythemannerinwhichtheunboundedness arisesFigure1.7GraphofUnboundedFormulation70K6050c.040sUnbounded930s20100102060701101203040508090100Astros
What is Optimization? Chapter 1 9 this unit is $20. An additional Astro unit will require sacrifices elsewhere, however. Since all of the labor supply is being used, producing more Astros would require the production of Cosmos to be reduced in order to free up labor. The labor tradeoff rate for Astros and Cosmos is ½. That is, producing one more Astro implies reducing Cosmo production by ½ of a unit. The net increase in profits is $20 (1/2)* $30 = $5, because Cosmos have a profit contribution of $30 per unit. Now, consider the dual price of $15/hour on the labor constraint. If we have 1 more hour of labor, it will be used solely to produce more Cosmos. One Cosmo has a profit contribution of $30/unit. Since 1 hour of labor is only sufficient for one half of a Cosmo, the value of the additional hour of labor is $15. 1.6 Unbounded Formulations If we forget to include the labor constraint and the constraint on the production of Cosmos, then an unlimited amount of profit is possible by producing a large number of Cosmos. This is illustrated here: MAX = 20 * A + 30 * C; A <= 60; This generates an error window with the message: UNBOUNDED SOLUTION There is nothing to prevent C from being infinitely large. The feasible region is illustrated in Figure 1.7. In larger problems, there are typically several unbounded variables and it is not as easy to identify the manner in which the unboundedness arises. Figure 1.7 Graph of Unbounded Formulation 0 10 20 30 40 50 60 10 20 30 40 50 60 70 80 90 100 110 120 C o s m o s Astros 70 Unbounded
10Chapter1WhatisOptimization?1.7InfeasibleFormulationsAn example of an infeasibleformulation is obtained if theright-hand sideof thelabor constraintismade 190 and its direction is inadvertently reversed. In this case, the most labor that can be used is toproduce60Astros and 50Cosmos fora total labor consumption of 60+2×50=160hours.Theformulationand attempted solutionare:MAX=(20*A)+(30*C);A <= 60;C <= 50;A+2 *C>=190;A windowwith the error message:NO FEASIBLE SOLUTION.will print.Thereports windowwill generatethefollowing:VariableValueReduced CostAC60.000000.000000050.000000.0000000RowSlack or sSurplusDual Price1232700.0000.00000000.00000001.0000000.00000002.0000004-30.00000-1.000000This “"solution" is infeasible for the labor constraint by the amount of 30 person-hours(190 -(1 x60+2×50)).The dual prices in this casegive information helpful in determining how theinfeasibility arose. For example, the +1 associated with row 2 indicates that increasing its right-handsidebyone will decrease the infeasibility by1.The+2with row3means, if weallowed 1 more unit ofCosmoproduction,the infeasibilitywould decrease by2unitsbecauseeach Cosmo uses2hours oflabor.The-1 associated with row 4means that decreasing the right-hand side of the labor constraint by1wouldreducetheinfeasibilitybyl
10 Chapter 1 What is Optimization? 1.7 Infeasible Formulations An example of an infeasible formulation is obtained if the right-hand side of the labor constraint is made 190 and its direction is inadvertently reversed. In this case, the most labor that can be used is to produce 60 Astros and 50 Cosmos for a total labor consumption of 60 + 2 u 50 = 160 hours. The formulation and attempted solution are: MAX = (20 * A) + (30 * C); A <= 60; C <= 50; A + 2 * C >= 190; A window with the error message: NO FEASIBLE SOLUTION. will print. The reports window will generate the following: Variable Value Reduced Cost A 60.00000 0.0000000 C 50.00000 0.0000000 Row Slack or Surplus Dual Price 1 2700.000 0.0000000 2 0.0000000 1.000000 3 0.0000000 2.000000 4 -30.00000 -1.000000 This “solution” is infeasible for the labor constraint by the amount of 30 person-hours (190 - (1 u 60 + 2 u 50)). The dual prices in this case give information helpful in determining how the infeasibility arose. For example, the +1 associated with row 2 indicates that increasing its right-hand side by one will decrease the infeasibility by 1. The +2 with row 3 means, if we allowed 1 more unit of Cosmo production, the infeasibility would decrease by 2 units because each Cosmo uses 2 hours of labor. The -1 associated with row 4 means that decreasing the right-hand side of the labor constraint by 1 would reduce the infeasibility by 1
11WhatisOptimization?Chapter1Figure1.8 illustrates theconstraintsforthisformulation.Figure1.8 Graphof Infeasible Formulation1009080A+2C≥19070FC≤50C 60050sm40030s20A≤ 6010F05010203040607080901001100120Astros1.8MultipleOptimalSolutionsandDegeneracyFor a given formulation that has a bounded optimal solution, there will be a unique optimum objectivefunction value.However,there may be several different combinations of decision variable values (andassociated dual prices)that produce this unique optimal value.Such solutions are said to be degeneratein some sense. In the Enginola problem, for example, suppose the profit contribution of A happened tobeS15ratherthan$20.Theproblemandasolutionare:MAX=15*A+30*C;A<=60;C <= 50;A+2*C<=120;1Optimal solution found at step:Objective value:1800.000ValueVariableReduced CostA20.000000.0000000c50.000000.0000000RowDual PriceslackorSurplus11800.0001.000000240.000000.000000030.00000000.0000000415.000000.0000000
What is Optimization? Chapter 1 11 Figure 1.8 illustrates the constraints for this formulation. Figure 1.8 Graph of Infeasible Formulation Astros 0 10 20 30 40 50 60 10 20 30 40 50 60 70 80 90 100 110 120 C o s m o s 70 80 90 100 C A A + 2 C 190 50 60 1.8 Multiple Optimal Solutions and Degeneracy For a given formulation that has a bounded optimal solution, there will be a unique optimum objective function value. However, there may be several different combinations of decision variable values (and associated dual prices) that produce this unique optimal value. Such solutions are said to be degenerate in some sense. In the Enginola problem, for example, suppose the profit contribution of A happened to be $15 rather than $20. The problem and a solution are: MAX = 15 * A + 30 * C; A <= 60; C <= 50; A + 2 * C <= 120; Optimal solution found at step: 1 Objective value: 1800.000 Variable Value Reduced Cost A 20.00000 0.0000000 C 50.00000 0.0000000 Row Slack or Surplus Dual Price 1 1800.000 1.000000 2 40.00000 0.0000000 3 0.0000000 0.0000000 4 0.0000000 15.00000
12Chapter1WhatisOptimization?Figure1.9ModelwithAlternativeOptima70 60F50c0Sm030L15A+30C=1500S20上100609020304050708010011010120AstrosThe feasible region, as well as a "profit = 1500" line, are shown in Figure 1.9. Notice the linesA+2C=120and15A+30C=1500 areparallel.It shouldbeapparent that anyfeasiblepointontheline A +2C=120 is optimal.The particularly observant may havenoted in the solution report that the constraint, C≤50(i.e.,row 3), has both zero slack and a zero dual price.This suggests the production of Cosmos couldbedecreased a small amount without any effectontotal profits.Of course,there would havetobeacompensatory increase in the production of Astros. We conclude that there must be an alternateoptimum solution thatproduces more Astros, but fewer Cosmos.We can discoverthis solution byincreasing the profitabilityofAstros everso slightly.Observe:MAX=15.0001*A+30*C;A<= 60;C<=50;:A+2*C<=3120;1Optimal solution found at step:1800.006Objective value:VariableValueReduced CostA60.000000.0000000c30.000000.0000000RowDual Priceslack orSurplus121800.0061.000000.00000000.1000000E-03320.000000.000000040.000000015.00000As predicted, the profit is still about S180o.However, the production of Cosmos has beendecreased to30from50,whereas therehasbeen an increaseintheproductionofAstros to60from20
12 Chapter 1 What is Optimization? Figure 1.9 Model with Alternative Optima Astros 0 10 20 30 40 50 60 10 20 30 40 50 60 70 80 90 100 110 120 C o s m o s 15 A + 30 C = 1500 70 The feasible region, as well as a “profit = 1500” line, are shown in Figure 1.9. Notice the lines A + 2C = 120 and 15A + 30C = 1500 are parallel. It should be apparent that any feasible point on the line A + 2C = 120 is optimal. The particularly observant may have noted in the solution report that the constraint, C d 50 (i.e., row 3), has both zero slack and a zero dual price. This suggests the production of Cosmos could be decreased a small amount without any effect on total profits. Of course, there would have to be a compensatory increase in the production of Astros. We conclude that there must be an alternate optimum solution that produces more Astros, but fewer Cosmos. We can discover this solution by increasing the profitability of Astros ever so slightly. Observe: MAX = 15.0001 * A + 30 * C; A <= 60; C <= 50; A + 2 * C <= 120; Optimal solution found at step: 1 Objective value: 1800.006 Variable Value Reduced Cost A 60.00000 0.0000000 C 30.00000 0.0000000 Row Slack or Surplus Dual Price 1 1800.006 1.00000 2 0.0000000 0.1000000E-03 3 20.00000 0.0000000 4 0.0000000 15.00000 As predicted, the profit is still about $1800. However, the production of Cosmos has been decreased to 30 from 50, whereas there has been an increase in the production of Astros to 60 from 20