《数学建模》课程参考文献：《Optimization Modeling with LINGO》书籍PDF电子书（Sixth Edition，Lindo Systems,Inc.）

13WhatisOptimization?Chapter11.8.1The"SnakeEyes"ConditionAlternate optima may exist only if some row in the solution report has zeroes in both the second andthird columns of the report, a configuration that some applied statisticians call "snake eyes"That is,alternate optima may exist only if some variable has both zero value and zero reduced cost, or someconstraint has both zero slack and zero dual price.Mathematicians, with no intent of moral judgment,refertosuchsolutionsasdegenerate.If there are alternate optima, you may find your computer gives a different solution from that inthe text. However, you should always get the same objective function value.There are, in fact, two ways in which multiple optimal solutions can occur.For the example inFigure 1.9, the two optimal solution reports differ only in the values of the so-called primal variables(i.e., our original decision variables A, C)and the slack variables in the constraint. There can also besituations where there are multiple optimal solutions in which only the dual variables differ.Considerthis variation of the Enginola problemin which the capacity of the Cosmo line has been reduced to 30.Theformulationis:MAX=20*A+30*C;A< 60;Inote that < and <- are equivalent;!in LINGO;C < 30;A + 2 *C<120;The corresponding graph of this problem appears in Figure 1.10. An optimal solution is:0Optimal solution found at step:2100.000Objective value:ValueVariableReduced CostA60.000000.0000000c30.000000.0000000Rowslack or SurplusDual Price1232100.0001.0000000.000000020.000000.000000030.0000040.00000000.0000000Again, notice the"snake eyes" in the solution (i.e., the pair of zeroes in a row of the solutionreport).This suggests the capacity of the Cosmo line(the RHS of row3)couldbe changed withoutchanging the objective value.Figure 1.10 illustrates the situation.Three constraints pass through thepoint A=60, C=30. Any two of the constraints determine the point. In fact, the constraintA+2C≤120 is mathematically redundant (i.e., it could be dropped without changing the feasibleregion)

What is Optimization? Chapter 1 13 1.8.1 The “Snake Eyes” Condition Alternate optima may exist only if some row in the solution report has zeroes in both the second and third columns of the report, a configuration that some applied statisticians call “snake eyes”. That is, alternate optima may exist only if some variable has both zero value and zero reduced cost, or some constraint has both zero slack and zero dual price. Mathematicians, with no intent of moral judgment, refer to such solutions as degenerate. If there are alternate optima, you may find your computer gives a different solution from that in the text. However, you should always get the same objective function value. There are, in fact, two ways in which multiple optimal solutions can occur. For the example in Figure 1.9, the two optimal solution reports differ only in the values of the so-called primal variables (i.e., our original decision variables A, C) and the slack variables in the constraint. There can also be situations where there are multiple optimal solutions in which only the dual variables differ. Consider this variation of the Enginola problem in which the capacity of the Cosmo line has been reduced to 30. The formulation is: MAX = 20 * A + 30 * C; A < 60; !note that < and <= are equivalent; !in LINGO; C < 30; A + 2 * C < 120; The corresponding graph of this problem appears in Figure 1.10. An optimal solution is: Optimal solution found at step: 0 Objective value: 2100.000 Variable Value Reduced Cost A 60.00000 0.0000000 C 30.00000 0.0000000 Row Slack or Surplus Dual Price 1 2100.000 1.000000 2 0.0000000 20.00000 3 0.0000000 30.00000 4 0.0000000 0.0000000 Again, notice the “snake eyes” in the solution (i.e., the pair of zeroes in a row of the solution report). This suggests the capacity of the Cosmo line (the RHS of row 3) could be changed without changing the objective value. Figure 1.10 illustrates the situation. Three constraints pass through the point A = 60, C = 30. Any two of the constraints determine the point. In fact, the constraint A + 2C d 120 is mathematically redundant (i.e., it could be dropped without changing the feasible region)

14Chapter1WhatisOptimization?Figure1.10AlternateSolutions inDualVariablesA≤60807020A+30C=2100c60Sm 50040s/C≤303020/A+2C≤12010FY0406010203050708090100110120AstrosIf you decrease the RHS of row 3 very slightly, you will get essentially the following solution:0Optimal solution foundatstep:2100.000Objective value:ValueReduced CostVariableA60.000000.0000000c30.000000.0000000RowSlack orsSurplusDual Price12100.0001.00000020.00000005.00000030.00000000.0000000415.000000.0000000Noticethis solution differsfrom theprevious one only in thedual values.We can now state the following rule: If a solution report has the"snake eyes"feature (i.e.,a pairof zeroes in any row of the report),then there maybe an alternate optimal solution thatdiffers either inthe primal variables, the dual variables, or in both. If all the constraints are inequality constraints, then"snake eyes", in fact, implies there is an alternate optimal solution. If one or more constraints areequality constraints,however,then thefollowing example illustrates that“snakeeyes"does not implytherehastobeanalternateoptimal solution:MAX =20*A;A<=60;C=30;

14 Chapter 1 What is Optimization? Figure 1.10 Alternate Solutions in Dual Variables 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 C A A + 2 C 120 30 60 20 A + 30 C = 2100 If you decrease the RHS of row 3 very slightly, you will get essentially the following solution: Optimal solution found at step: 0 Objective value: 2100.000 Variable Value Reduced Cost A 60.00000 0.0000000 C 30.00000 0.0000000 Row Slack or Surplus Dual Price 1 2100.000 1.000000 2 0.0000000 5.000000 3 0.0000000 0.0000000 4 0.0000000 15.00000 Notice this solution differs from the previous one only in the dual values. We can now state the following rule: If a solution report has the “snake eyes” feature (i.e., a pair of zeroes in any row of the report), then there may be an alternate optimal solution that differs either in the primal variables, the dual variables, or in both. If all the constraints are inequality constraints, then “snake eyes”, in fact, implies there is an alternate optimal solution. If one or more constraints are equality constraints, however, then the following example illustrates that “snake eyes” does not imply there has to be an alternate optimal solution: MAX = 20 * A; A <= 60; C = 30;

15WhatisOptimization?Chapter1The only solution is:0Optimal solution foundatstep:1200.000Objective value:ValueReduced CostVariableA60.0000000.0000000c30.0000000.0000000RowSlack orSurplusDual Price1231200.0001.0000000.000000020.000000.00000000.0000000If a solution report exhibits the"snake eyes"configuration, a natural question to ask is: can wedetermine fromthe solution reportalone whether the alternate optima are in the primal variables or thedual variables?Theansweris"no",as thefollowingtworelatedproblems illustrate.ProblemPProblemDY;MAX = X +MAX = X + Y;X+Y+Z<=1;Z <= 1;X+Y+X+2*Y<= 1;2*Z<=1;X +Bothproblemspossessmultipleoptimal solutions.Theonesthatcanbeidentifiedbythestandardsimplex solution methods are:Solution1ProblemDProblemPOBJECTIVE VALUEOBJECTIVEVALUE1)1)1.000000001.00000000VariableValueReduced CostVariableValueReduced Cost+x1.0000001.00000000000000.000000Y.NYN0.0000000.0000000.0000000.0000000.0000001.0000000.0000001.000000RowWSlackslackorDual PricesRoworDual PricesSurplusSurplus2)2)0.0000001.0000000.0000001.0000003)3)0.0000000.0000000.0000000.000000Solution2ProblemDProblemPOBJECTIVE VALUEOBJECTIVE VALUE1) 1)1.000000001.00000000VariableReduced CostVariableReduced CostValueValueXY.1.0000000.000000x0.0000000.0000000.0000001.00000041.0000000.000000220.0000000.0000000.0000001.000000SlackorslackorROWSurplusDualPricesROWSurplusDualprices2)2)1.0000000.0000000.0000000.0000003)0.0000001.0000003)1.0000000.000000

What is Optimization? Chapter 1 15 The only solution is: Optimal solution found at step: 0 Objective value: 1200.000 Variable Value Reduced Cost A 60.000000 0.0000000 C 30.000000 0.0000000 Row Slack or Surplus Dual Price 1 1200.000 1.000000 2 0.0000000 20.00000 3 0.0000000 0.0000000 If a solution report exhibits the “snake eyes” configuration, a natural question to ask is: can we determine from the solution report alone whether the alternate optima are in the primal variables or the dual variables? The answer is “no”, as the following two related problems illustrate. Problem D Problem P MAX = X + Y; MAX = X + Y; X + Y + Z <= 1; X + Y + Z <= 1; X + 2 * Y <= 1; X + 2 * Z <= 1; Both problems possess multiple optimal solutions. The ones that can be identified by the standard simplex solution methods are: Solution 1 Problem D Problem P OBJECTIVE VALUE OBJECTIVE VALUE 1) 1.00000000 1) 1.00000000 Variable Value Reduced Cost Variable Value Reduced Cost X 1.000000 0 000000 X 1.000000 0.000000 Y 0.000000 0.000000 Y 0.000000 0.000000 Z 0.000000 1.000000 Z 0.000000 1.000000 Row Slack or Surplus Dual Prices Row Slack or Surplus Dual Prices 2) 0.000000 1.000000 2) 0.000000 1.000000 3) 0.000000 0.000000 3) 0.000000 0.000000 Solution 2 Problem D Problem P OBJECTIVE VALUE OBJECTIVE VALUE 1) 1.00000000 1) 1.00000000 Variable Value Reduced Cost Variable Value Reduced Cost X 1.000000 0.000000 X 0.000000 0.000000 Y 0.000000 1.000000 Y 1.000000 0.000000 Z 0.000000 0.000000 Z 0.000000 1.000000 Row Slack or Surplus Dual Prices Row Slack or Surplus Dual Prices 2) 0.000000 0.000000 2) 0.000000 1.000000 3) 0.000000 1.000000 3) 1.000000 0.000000

16Chapter1WhatisOptimization?Noticethat:·SolutionIisexactlythesameforbothproblems·ProblemDhasmultipleoptimalsolutionsinthedualvariables(only);while·ProblemPhasmultipleoptimalsolutionsintheprimalvariables(only)Thus, one cannot determine from the solution report alone thekind of alternate optima that mightexist.You cangenerateSolutionI bysetting theRHSof row3and the coefficient of Xintheobjectiveto slightly larger than 1 (e.g., 1.001).Likewise, Solution 2 is generated by setting the RHS of row 3and the coefficient of X in the objective to slightly less than 1 (e.g., 0.9999).Some authors refer to a problem that has multiple solutions to the primal variables as dualdegenerate and a problem with multiple solutions in the dual variables as primal degenerate.Otherauthors saya problemhas multipleoptima only if therearemultiple optimal solutions fortheprimalvariables.1.8.2DegeneracyandRedundantConstraintsIn small examples, degeneracy usually means there are redundant constraints. In general, however,especially in large problems, degeneracy does not imply there are redundant constraints. The constraintsetbelow and thecorrespondingFigure1.11 illustrate:2x-y≤12x-z≤12y-x≤12y - z≤12z -x≤12z -y≤1

16 Chapter 1 What is Optimization? Notice that: x Solution 1 is exactly the same for both problems; x Problem D has multiple optimal solutions in the dual variables (only); while x Problem P has multiple optimal solutions in the primal variables (only). Thus, one cannot determine from the solution report alone the kind of alternate optima that might exist. You can generate Solution 1 by setting the RHS of row 3 and the coefficient of X in the objective to slightly larger than 1 (e.g., 1.001). Likewise, Solution 2 is generated by setting the RHS of row 3 and the coefficient of X in the objective to slightly less than 1 (e.g., 0.9999). Some authors refer to a problem that has multiple solutions to the primal variables as dual degenerate and a problem with multiple solutions in the dual variables as primal degenerate. Other authors say a problem has multiple optima only if there are multiple optimal solutions for the primal variables. 1.8.2 Degeneracy and Redundant Constraints In small examples, degeneracy usually means there are redundant constraints. In general, however, especially in large problems, degeneracy does not imply there are redundant constraints. The constraint set below and the corresponding Figure 1.11 illustrate: 2x  y d 1 2x  z d 1 2y  x d 1 2y  z d 1 2z  x d 1 2z  y d 1

17WhatisOptimization?Chapter1Figure1.11Degeneracybut NoRedundancyY2Y-X ≤X2Z-x≤1ZTheseconstraints definea conewith apex orpointatx=y=z=1,having sixsides.Thepointx=y= z-1 is degenerate because it has more than three constraints passing through it. Nevertheless,none of the constraints are redundant. Notice the point x=0.6, y=0, z=0.5 violates the firstconstraint, but satisfies all the others.Therefore, the first constraint is nonredundant.By trying all sixpermutations of0.6, 0,0.5,youcanverifyeach ofthe sixconstraints arenonredundant.1.9Nonlinear Models and Global OptimizationThroughout this text the emphasis is on formulating linear programs.Historically nonlinear modelswereto be avoided,if possible,for two reasons:a)they takemuch longerto solve,and b)once“"solved"traditional solvers could only guarantee that you had a locally optimal solution.A solution isa local optimum if there is no better solution nearby,although there might be a much better solutionsome distance away.Traditional nonlinear solvers are like myopic mountain climbers, they can getyou to the top of the nearest peak, but they may not see and get you to the highest peak in themountain range.VersionsofLINGOfromLINGO8onwardhaveaglobal solveroption.Ifyoucheck the global solver option, then you are guaranteed to get a global optimum, if you let the solverrunlongenough.Toillustrate,supposeourproblemis:Min=@sin(x)+.5*@abs(x-9.5);x <= 12;

What is Optimization? Chapter 1 17 Figure 1.11 Degeneracy but No Redundancy Y X Z 2Y - X 1 2 Z - X 1 These constraints define a cone with apex or point at x = y = z = 1, having six sides. The point x = y = z = 1 is degenerate because it has more than three constraints passing through it. Nevertheless, none of the constraints are redundant. Notice the point x = 0.6, y = 0, z = 0.5 violates the first constraint, but satisfies all the others. Therefore, the first constraint is nonredundant. By trying all six permutations of 0.6, 0, 0.5, you can verify each of the six constraints are nonredundant. 1.9 Nonlinear Models and Global Optimization Throughout this text the emphasis is on formulating linear programs. Historically nonlinear models were to be avoided, if possible, for two reasons: a) they take much longer to solve, and b) once “solved” traditional solvers could only guarantee that you had a locally optimal solution. A solution is a local optimum if there is no better solution nearby, although there might be a much better solution some distance away. Traditional nonlinear solvers are like myopic mountain climbers, they can get you to the top of the nearest peak, but they may not see and get you to the highest peak in the mountain range. Versions of LINGO from LINGO 8 onward have a global solver option. If you check the global solver option, then you are guaranteed to get a global optimum, if you let the solver run long enough. To illustrate, suppose our problem is: Min = @sin(x) + .5*@abs(x-9.5); x <= 12;