数据、模型与决策(运筹学)课后习题和案例答案017s.doc

数据、模型与决策(运筹学)课后习题和案例答案017s 作者： 日期：2 个人收集整理 勿做商业用途CD SUPPLEMENT TO CHAPTER 17MORE ABOUT THE SIMPLEX METHODReview Questions17s。1-1No.17s.12The adjacent corner points that are better than the current corner point are candidates to be the next one.17s。1-3The best adjacent corner point criteria and best rate of improvement criteria.17s.1-4The simplex method starts by selecting some corner point as the initial corner point.17s。1-5If none of the adjacent corner points are better (as measured by the value of the objective function) than the current corner point， then the current corner point is an optimal solution。17s。1-6Choose the best adjacent corner point.17s.1-7Choose the next corner point by picking the adjacent corner point has the lowest objective function value rather than highest when getting started. There may only be one adjacent corner point if the feasible region is unbounded。17s。2-1It is analagous to standing in the middle of a room and looking toward one corner where two walls and the floor meet.17s。22There are three (at most) adjacent corner points.17s。2-3Yes。17s。2-4With three decision variables， the constraint boundaries are planes.17s.2-5A system of n variables and n equations must be solved。17s.3-1The name derives from the fact that the slack variable for a constraint represents the slack （gap） between the two sides of the inequality。17s。32A nonnegative slack variable implies that the left-hand side is not larger than the righthand side。17s。33For the Wyndor problem， the slack variables represent unused production times in the various plants.17s.34It is much simpler for an algebraic procedure to deal with equations than with inequalities. 17s。3-5A nonbasic variable has a value of zero。17s.3-6A basic feasible solution is simply a corner point that has been augmented by including the values of the slack variables。17s。37A surplus variable gives the amount by which the lefthand side of a constraint exceeds the righthand side。17s.4-1(1) Determine the entering basic variable; (2）determine the leaving basic variable; （3)Solve for the new basic feasible solution17s。42The entering basic variable is the current nonbasic variable that should become a basic variable for the next basic feasible solution. Among the nonbasic variables with a negative coefficient in equation 0, choose the one whose coefficient has the largest absolute value to be the entering basic variable。17s。43The leaving basic variable is the current basic variable that should become a nonbasic variable for the next basic feasible solution. For each equation that has a strictly positive coefficient （neither zero nor negative) for the entering basic variable, take the ratio of the righthand side to this coefficient. Identify the equation that has the minimum ratio, and select the basic variable in this equation to be the leaving basic variable.17s.44The initialization step sets up to start the iterations and finds the initial basic feasible solution.17s.45Examine the current equation 0。 If none of the nonbasic variables have a negative coefficient, then the current basic feasible solution is optimal。17s。4-6（1） Equation 0 does not contain any basic variables; (2） each of the other equations contains exactly one basic variable； (3） an equations one basic variable has a coefficient of 1; （4) an equations one basic variable does not appear inn any other equation。17s。4-7The tabular form performs exactly the same steps as the algebraic form, but records the information more compactly。Problems17s.1Getting Started： Select （0， 0) as the initial corner point.Checking for Optimality: Both （0， 3) and （3, 0） have better objective function values (Z = 6 and 9， respectively）, so （0, 0） is not optimal。Moving On: （3, 0） is the best adjacent corner point， so move to (3, 0).Checking for Optimality： （2， 2) has a better objective function value （Z = 10), so (3， 0) is not optimal。Moving On： Move from (3, 0） to （2， 2).Checking for Optimality: （0， 3) has lower objective function values （Z = 6)， so (2, 2） is optimal.个人收集整理，勿做商业用途文档为个人收集整理,来源于网络17s。2Getting Started： Select （0, 0) as the initial corner point.Checking for Optimality： Both （0, 2。667) and （4, 0) have better objective function values (Z = 5.333 and 4， respectively）, so （0, 0） is not optimal。Moving On： (0, 2。667) is the best adjacent corner point, so move to (0， 2。667).Checking for Optimality: （2, 2) has a better objective function value （Z = 6), so （0, 2。667) is not optimal.Moving On: Move from (0， 2。667） to （2， 2).Checking for Optimality： （4, 0） has a lower objective function values （Z = 4）， so (2, 2） is optimal.文档为个人收集整理，来源于网络个人收集整理，勿做商业用途17s。3Getting Started： Select （0， 0） as the initial corner point。Checking for Optimality： Both (0， 5) and (4， 0） have better objective function values （Z = 10 and 12, respectively）， so (0, 0) is not optimal.Moving On： (4， 0） is the best adjacent corner point， so move to (4, 0).Checking for Optimality: (4， 2) has a better objective function value (Z = 16）, so (4， 0) is not optimal.Moving On: Move from （4， 0) to (4， 2).Checking for Optimality： （3， 4） has a better objective function value （Z = 17）， so (4, 2） is not optimal。Moving On: Move from （4， 2） to （3， 4）。Checking for Optimality: （0， 5) has a lower objective function values (Z = 10), so (3, 4） is optimal。本文为互联网收集,请勿用作商业用途文档为个人收集整理，来源于网络17s。4a）Getting Started: Select （0, 0) as the initial corner point.Checking for Optimality： Both （2, 0） and （0， 5） have better objective function values (Z = 4 and 5， respectively）， so (0, 0) is not optimal。Moving On： （0, 5) is the best adjacent corner point， so move to （0， 5）。Checking for Optimality： (2, 5） has a better objective function value （Z = 9), so （0, 5) is not optimal。Moving On： Move from (0， 5) to （2， 5）. Checking for Optimality: (2, 0) has a lower objective function values (Z = 4）， so (2, 5) is optimal.文档为个人收集整理，来源于网络本文为互联网收集，请勿用作商业用途b)Getting Started: Select （0， 0) as the initial corner point。Checking for Optimality: Moving toward either (2， 0） or （0， 5） improves the objective function value， so （0, 0） is not optimal。Moving On: Moving toward （2, 0） improves the objective function faster than moving toward （0， 5） (a rate of 2 vs。 a rate of 1）, so move to （2, 0）.Checking for Optimality： Moving toward （2， 5） improves the objective function value， so （2， 0) is not optimal.Moving On： Move from （2， 0） to (2, 5)。 Checking for Optimality： Moving toward （0, 5） lowers the objective function values, so （2, 5） is optimal。本文为互联网收集，请勿用作商业用途本文为互联网收集，请勿用作商业用途17s.5a）b)The eight corner points are （x1， x2, x3) = （0, 0, 0）， （0， 0, 1), (0， 1， 0), (0, 1， 1), (1, 0, 0), (1, 0， 1）， (1， 1, 0), and (1, 1， 1）。c)Objective Function： Profit = x1 + 2x2 + 3x3 Optimal Solution: （x1， x2, x3) = (1, 1， 1) and Profit = 6。Corner Point （x1， x2, x3）Profit = x1 + 2x2 + 3x3(0， 0， 0)0（0， 0， 1)3（0， 1， 0)2（0, 1， 1）5（1， 0, 0）1(1， 0， 1）4（1, 1, 0)3(1， 1， 1）6d）The simplex method would start at (0， 0， 0）, move to the best adjacent corner point at （0， 0， 1）， then to (0, 1, 1）, and finally to the optimal solution at （1， 1， 1).17s.6a）b)The ten corner points are (x1， x2, x3） = （0, 0, 0)， (2， 0, 0)， （2， 2, 0)， (1, 3， 0), (0, 3， 0）， (0， 0， 2）, (2, 0, 2）， (2， 2， 2）, （1， 3, 2）, （0， 3， 2)c)Objective Function: Profit = 2x1 + x2 x3 Optimal Solution： (x1， x2, x3) = (2， 2, 0) and Profit = 6.Corner Point （x1， x2, x3）Profit = 2x1 + x2 x3（0, 0， 0)0(2, 0, 0)4（2， 2, 0)6（1, 3, 0）5（0, 3， 0）3(0, 0， 2)2（2, 0， 2)2(2, 2, 2）4（1, 3， 2)3(0， 3, 2)1d)The simplex method would start at （0， 0， 0）， move to the best adjacent corner point at （2, 0， 0）, and then to the optimal solution at (2， 2, 0).17s.7a)s1 = 10 x2s2 = 20 2x1 x2b）s1 0 and s2 0.c）x2 + s1 = 102x1 + x2 + s2 = 20d)Values of the slack variables at （x1, x2) = (10, 0) are s1 = 10 and s2 = 0.The equations for the constraint boundary lines on which （10, 0) lies arex2 = 02x1 + x2 = 20The corresponding basic feasible solution is (x1， x2， s1, s2） = (10， 0， 10, 0)。The basic variables are x1 and s1； the nonbasic variables are x2 and s2.17s。8a)25x1 + 40x2 + 50x3 500。b)s 0.c)s = 0。17s.9a）Objective Function： Profit = 2x1 + x2 Optimal Solution： （x1， x2) = (4， 3) and Profit = 11Corner Point (x1, x2)Profit = 2x1 + x2（0， 0)0(5, 0）10（4， 3）11(0， 5)5b)The graphical simplex method would start at (0, 0)， move to the best adjacent corner point at (5, 0)， and finally move to the optimal solution at (4, 3)。c）3x1 + 2x2 + s1 = 15x1 + 2x2 + s2 = 10d）Basic Feasible Solution （x1， x2， s1, s2)Basic VariablesNonbasic Variables（0， 0， 15， 10)s1, s2x1， x2(5， 0, 0, 5)x1, s2x2， s1（4, 3, 0, 0）x1, x2s1， s2(0， 5， 5, 0)x2, s1x1, s2e)The graphical simplex method would start at (0， 0, 15, 10), move to the best adjacent corner point at (5， 0, 0， 5), and finally move to the optimal solution at （4, 3， 0, 0）.17s。10a）s1 = 2x1 + 3x2 21.s2 = 5x1 + 3x2 30。b)s1 0 and s2 0.c）2x1 + 3x2 s1 = 21.5x1 + 3x2 s2 = 30。d）Values of the surplus variables at （x1, x2) = (3, 5） are s1 = 0 and s2 = 0.The equations for the constraint boundary lines on which (3， 5） lies are2x1 + 3x2 = 215x1 + 3x2 = 30The corresponding basic feasible solution is （x1, x2， s1， s2) = （3, 5， 0， 0)。The basic variables are x1 and x2； the nonbasic variables are s1 and s2。17s。11a)20x1 + 10x2 100。b）s 0。c)s = 0.17s.12a）Getting Started： Select （16， 0) as the initial corner point. (Cost = 32。）Checking for Optimality: Both （15， 0） and （0， 24） have better objective function values (Cost = 30 and 24, respectively), so (16, 0) is not optimal.Moving On: (0, 24) is the best adjacent corner point， so move to （0， 24)。 (Cost = 24.）Checking for Optimality: （0, 20) has a better objective function value (Cost = 20)， so (0,24) is not optimal.Moving On: Move from （0， 24） to (0， 20）。 （Cost = 20。) Checking for Optimality: (7。5， 7.5) has a higher objective function values (Cost = 22.5), so （0， 20) is optimal。 (Cost = 20）。本文为互联网收集，请勿用作商业用途本文为互联网收集,请勿用作商业用途b)Getting Started: Select (16, 0) as the initial corner point. （Cost = 32。）Checking for Optimality: Moving toward either (15, 0) or (0， 24） improve the objective function value， so (16， 0) is not optimal.Moving On: Moving toward （15, 0） improves the objective function at a faster rate (2 per unit) than moving toward （0， 24） (rate = 1/3）， so move to （15, 0)。 (Cost = 30。)Checking for Optimality: Moving toward （7.5, 7.5) improves the objective function value， so (15， 0） is not optimal.Moving On: Move from (15， 0) to (7.5， 7.5).Checking for Optimality: Moving toward （0， 20) improves the objective function value, so （7。5， 7。5) is not optimal。Moving On： Move from （7.5, 7.5) to (0， 20)。 (Cost = 20。） Checking for Optimality: Moving toward (0, 24) increases the objective function value, so （0, 20) is optimal. (Cost = 20。)个人收集整理,勿做商业用途本文为互联网收集，请勿用作商业用途c）Sequence of basic feasible solutions （x1， x2, s1, s2, s3）： （16， 0， 20， 0, 1）, (0, 24, 12, 0， 9)， (0， 20， 0， 8, 5）.17s.13a)Getting Started： Select （0， 0) as the initial corner point。 （Profit = 0.）Checking for Optimality： Both （7， 0) and (0, 2） have better objective function values （Profit = 7 and 6, respectively), so （0, 0） is not optimal。Moving On： （7, 0） is the best adjacent corner point， so move to (7, 0）。 （Profit = 7。）Checking for Optimality: (7, 2） has a better objective function value (Profit = 13), so (7， 0) is not optimal.Moving On： Move from （7, 0) to (7， 2）。 （Profit = 13.)Checking for Optimality： （0， 2） has a lower objective function value (Profit = 6), so （7， 2) is optimal. (Profit = 13.)文档为个人收集整理,来源于网络个人收集整理，勿做商业用途b）Getting Started： Select (0， 0) as the initial corner point。 （Profit = 0.)Checking for Optimality: Moving toward either （7, 0） and (0， 2) improves the objective function value, so (0, 0） is not optimal.Moving On: Moving toward (0， 2) improves the objective function value faster than moving toward （7， 0） （rate = 3 toward （0， 2） and 1 toward （7, 0）， so move to (0, 2）. (Profit = 6。)Checking for Optimality： Moving toward (7, 2） improves the objective function value， so （0， 2） is not optimal.Moving On: Move from （0， 2) to (7, 2）. (Profit = 13.)Checking for Optimality: Moving toward (7, 2） decreases the objective function value， so (7， 2） is optimal. （Profit = 13。）本文为互联网收集,请勿用作商业用途个人收集整理，勿做商业用途c)x1 + s1 = 7x2 + s2 = 2d）Geometric ProgressionAlgebraic ProgressionIterationCorner PointCBENonbasicVariablesBasicVariablesBasicFeasibleSolution(x1, x2, s1, s2)0（0， 0)3， 4x1, x2s1, s2(0， 0， 7， 2）1(0， 2）2， 3x1， s2x2, s1(0， 2， 7, 0)2（7， 2）1, 2s1， s2x1， x2（7， 2, 0, 0）e)Iteration 0：0）Z1x13x2+0s1+0s2= 01)+1x1+0x2+1s1+0s2= 72)+0x1+1x2+0s1+1s2= 2x1 0, x2 0, s1 0, s2 0。Iteration 1：0)Z1x1+0x2+0s1+3s2= 61)+1x1+0x2+1s1+0s2= 72）+0x1+1x2+0s1+1s2= 2x1 0, x2 0, s1 0， s2 0.Iteration 2：0）Z+0x1+0x2+1s1+3s2= 131)+1x1+0x2+1s1+0s2= 72)+0x1+1x2+0s1+1s2= 2x1 0, x2 0， s1 0, s2 0.17s.14a）Getting Started: Select （0， 0） as the initial corner point. (Profit = 0.）Checking for Optimality: Both （2， 0） and (0, 2） have better objective function values （Profit = 2 and 4, respectively)， so （0, 0) is not optimal.Moving On： （0， 2） is the best adjacent corner point， so move to (0， 2）. (Profit = 4.)Checking for Optimality: （1， 2) has a better objective function value （Profit = 5）, so （2， 0) is not optimal.Moving On: Move from (2， 0） to (1, 2)。 （Profit = 5.）Checking for Optimality: (2， 1) has a lower objective function value （Profit = 4）， so (1， 2） is optimal. (Profit = 5.)个人收集整理,勿做商业用途本文为互联网收集，请勿用作商业用途b）Getting Started： Select (0, 0) as the initial corner point。 （Profit = 0.）Checking for Optimality： Moving toward either （2， 0） and (0， 2) improves the objective function value， so （0, 0） is not optimal.Moving On: Moving toward (0, 2） improves the objective function value faster than moving toward （2, 0） （rate = 2 toward （0， 2） and 1 toward （2， 0）)， so move to （0, 2)。 (Profit = 4。)Checking for Optimality： Moving toward （1, 2） improves the objective function value, so （0， 2） is not optimal。Moving On: Move from (0, 2） to （1, 2). (Profit = 5。）Checking for Optimality: Moving toward (2，