数据、模型与决策课后答案17.pdf

CD17 1 CD CHAPTER 17 SOLUTION CONCEPTS FOR LINEAR PROGRAMMING Review Questions 17 1 1 A corner point is a point that lies at a corner of the feasible region 17 1 2 The corner point with the best value of the objective function is the optimal solution 17 1 3 The simplex method has a way of quickly getting to the best corner point and detecting that this point is optimal so it stops without needing to evaluate the rest of the corner points 17 1 4 No It can have one optimal solution an infinite number of optimal solutions or no optimal solution 17 1 5 Yes and every point of the line segment between these two corner points will be an optimal solution 17 1 6 The constraints of a linear programming problem can be so restrictive that it is impossible for a solution to satisfy all of the constraints simultaneously 17 1 7 If some necessary constraint were not included in the linear programming model it is possible to have no limit on the best objective function value 17 2 1 The best corner point is always an optimal solution 17 2 2 The big advantage of searching for an optimal solution simply by finding the best corner point is that it tremendously reduces the number of solutions that need to be considered 17 2 3 When the simplex method is ready to move from the current corner point to the next one the adjacent corner points are candidates to be the next one 17 2 4 If none of the adjacent corner points are better than the current corner point then the current corner point is an optimal solution 17 2 5 If the simultaneous solution of a set of constraint boundary equations is feasible then that solution is a corner point 17 2 6 Two corner points are adjacent to each other if they share all but one of the same constraint boundaries 17 2 7 The simplex method examines corner points in an order such that each one is adjacent to the preceding one This greatly streamlines the algebra 17 2 8 A problem with 20 decision variable and 30 functional constraints might have more than a billion corner points CD17 2 17 2 9 The simplex method can solve problems that the enumeration of corner points method cannot because it is able to reach and identify the optimal corner point for a large problem after examining only a small fraction of all the corner points 17 3 1 The simplex method focuses solely on solutions that are corner points 17 3 2 Each iteration of the simplex method consists of a prescribed series of steps for moving from the current corner point to a new corner point 17 3 3 Management science algorithms typically are iterative algorithms 17 3 4 Whenever possible the initialization step of the simplex method chooses the origin 0 0 to be the initial corner point to be examined 17 3 5 When the simplex method finishes examining a corner point it then gathers information about the adjacent corner points It identifies the rates of improvement in the objective function along the edges that lead to the adjacent corner points 17 3 6 The optimality test consists simply of checking whether any of the edges give a positive rate of improvement in the objective function If none do then the current point is optimal 17 4 1 A problem with several thousand functional constraints and many thousand decision variables is not considered unusually large for a fast computer 17 4 2 The software package needs to help formulate input and modify the model In addition it should analyze solutions from the model and present results in the language of management 17 5 1 Narenda Karmarkar 17 5 2 Today the more powerful software packages include at least one interior point algorithm along with the simplex method 17 5 3 Interior point algorithms shoot through the interior of the feasible region toward an optimal solution instead of taking a less direct path around the boundary of the feasible region 17 5 4 The computer time per iteration for an interior point algorithm is many times longer than for the simplex method 17 5 5 For fairly small problems the number of iterations needed by an interior point algorithm and the simplex method tend to be somewhat comparable For large problems interior point algorithms do not need many more iterations while the simplex method does The reason for the large difference is the difference in the paths followed 17 5 6 The simplex method is very well suited for what if analysis while the interior point approach currently has limited capability in this area 17 5 7 The limited capability for performing what if analysis can be overcome by switching over to the simplex method 17 5 8 Switching over begins by identifying a corner point that is very close to the final trial solution CD17 3 Problems 17 1 Corner Point A1 A2 Profit 1 000A1 2 000A2 0 0 0 8 0 8 000 6 4 14 000 5 5 15 000 0 6 667 13 333 Optimal Solution A1 A2 5 5 and Profit 15 000 17 2 Corner Point TV PM Cost TV 2PM 0 9 18 4 3 12 8 3 14 Optimal Solution TV PM 4 3 and Cost 12 17 3 a d 1 2 3 4 5 6 7 8 9 10 11 ABCDEF Activity 1Activity 2 Unit Profit 30 20 UsedAvailable Resource A103 5 Resource B013 4 Resource C219 9 Resource D3421 21 Activity 1Activity 2Total Profit Number of Units33 150 Resource Used Per Unit CD17 4 b e Optimal Solution x1 x2 3 3 and Profit 150 Corner Points 0 0 4 5 0 3 3 1 667 4 and 0 4 c Corner Point x1 x2 Profit 30 x1 20 x2 0 0 0 4 5 0 135 3 3 150 1 667 4 130 0 4 80 Optimal Solution x1 x2 3 3 and Profit 150 17 4 a d 1 2 3 4 5 6 7 8 9 10 ABCDEF Activity 1Activity 2 Unit Profit 300 200 UsedAvailable Resource A5330 30 Resource B2321 21 Resource C015 6 Activity 1Activity 2Total Profit Number of Units35 1 900 Resource Used Per Unit CD17 5 b e Optimal Solution x1 x2 3 5 and Profit 1 900 Corner Points 0 0 6 0 3 5 1 5 6 and 0 6 c Corner Point x1 x2 Profit 300 x1 200 x2 0 0 0 6 0 1800 3 5 1900 1 5 6 1650 0 6 1200 Optimal Solution x1 x2 3 5 and Profit 1 900 CD17 6 17 5 a Objective Function Profit 400 x1 400 x2 Optimal Solution x1 x2 2 6 and Profit 3 200 Objective Function Profit 500 x1 300 x2 Optimal Solution x1 x2 4 3 and Profit 2 900 CD17 7 Objective Function Profit 300 x1 100 x2 Optimal Solution x1 x2 4 0 and Profit 1 200 Objective Function Profit 100 x1 500 x2 Optimal Solution x1 x2 0 6 and Profit 3 000 CD17 8 Objective Function Profit 100 x1 100 x2 Optimal Solution x1 x2 0 0 and Profit 0 b Objective Function Profit 400 x1 400 x2 Optimal Solution x1 x2 2 6 and Profit 3 200 Corner Point x1 x2 Profit 400 x1 400 x2 0 0 0 0 6 2 400 4 0 1 600 2 6 3 200 4 3 2 800 Objective Function Profit 500 x1 300 x2 Optimal Solution x1 x2 4 3 and Profit 2 900 Corner Point x1 x2 Profit 500 x1 300 x2 0 0 0 0 6 1 800 4 0 2 000 2 6 2 800 4 3 2 900 CD17 9 Objective Function Profit 300 x1 100 x2 Optimal Solution x1 x2 4 0 and Profit 1 200 Corner Point x1 x2 Profit 300 x1 100 x2 0 0 0 0 6 600 4 0 1 200 2 6 0 4 3 900 Objective Function Profit 100 x1 500 x2 Optimal Solution x1 x2 0 6 and Profit 3 000 Corner Point x1 x2 Profit 100 x1 500 x2 0 0 0 0 6 3 000 4 0 400 2 6 2 800 4 3 1 100 Objective Function Profit 100 x1 100 x2 Optimal Solution x1 x2 0 0 and Profit 0 Corner Point x1 x2 Profit 100 x1 100 x2 0 0 0 0 6 600 4 0 400 2 6 800 4 3 700 CD17 10 17 6 a True Example Maximize Profit x1 4x2 b True Example Maximize Profit x1 3x2 c False Example Maximize Profit x1 x2 CD17 11 17 7 a x1 6 x2 3 x1 3x2 6 b Unit Profit Product 1 Unit Profit Product 2 Objective Function Multiple Optimal Solutions 1 3 Profit x1 3x2 line segment between 0 2 3 3 0 1 Profit x2 line segment between 3 3 6 3 1 0 Profit x1 line segment between 6 3 6 0 0 1 Profit x2 line segment between 0 0 6 0 1 0 Profit x1 line segment between 0 0 0 2 c Objective Function Profit x1 5x2 Optimal Solution x1 x2 3 3 and Profit 12 Corner Point x1 x2 Profit x1 5x2 0 0 0 0 2 10 3 3 12 6 3 9 6 0 6 d Objective Function Profit x1 2x2 Optimal Solution x1 x2 0 2 and Profit 4 Corner Point x1 x2 Profit x1 2x2 0 0 0 0 2 4 3 3 3 6 3 0 6 0 6 CD17 12 17 8 a 1 2 3 4 5 6 7 8 9 10 11 ABCDEF Activity 1Activity 2 Unit Profit2030 million UsedAvailable Resource A5416 25 20 Resource B6930 30 Resource C2515 15 Total Profit Activity 1Activity 2 million Number of Units1 252 50100 Resource Used Per Unit Adjustable Cells FinalReducedObjectiveAllowableAllowable CellNameValueCostCoefficientIncreaseDecrease B 11 Number of Units Activity 11 2502008 C 11 Number of Units Activity 22 50030200 Constraints FinalShadowConstraintAllowableAllowable CellNameValuePriceR H SideIncreaseDecrease D 5Resource A Used16 250201E 303 75 D 6Resource B Used303 33333302 64713 D 7Resource C Used150151 66672 1429 b The sensitivity report indicates that the problem has other optimal solutions because the allowable increase of Activity 1 and the allowable decrease of Activity 2 are 0 An alternative optimal solution is shown below obtained by adjusting the unit profit for Activity 2 to 29 99 1 2 3 4 5 6 7 8 9 10 11 ABCDEF Activity 1Activity 2 Unit Profit2029 99 million UsedAvailable Resource A5420 20 Resource B6930 30 Resource C2512 85714 15 Total Profit Activity 1Activity 2 million Number of Units2 861 4399 99 Resource Used Per Unit c The other optimal solutions will be located on the line segment connecting the two optimal solutions found in parts a and b CD17 13 d Optimal Solution x1 x2 2 857 1 429 1 25 2 5 and all points on the connecting line Profit 100 million 17 9 a 1 2 3 4 5 6 7 8 9 10 ABCDEF Activity 1Activity 2 Unit Profit 500 300 UsedAvailable Resource A155300 300 Resource B106240 240 Resource C812300 450 Activity 1Activity 2Total Profit Number of Units1515 12 000 Resource Used Per Unit Adjustable Cells FinalReducedObjectiveAllowableAllowable CellNameValueCostCoefficientIncreaseDecrease B 10 Number of Units Activity 115 000 005004000 C 10 Number of Units Activity 215 000 003000133 3333 Constraints FinalShadowConstraintAllowableAllowable CellNameValuePriceR H SideIncreaseDecrease D 5Resource A Used30003006083 3333 D 6Resource B Used2405024042 857140 D 7Resource C Used30004501E 30150 CD17 14 b The sensitivity report indicates that the problem has other optimal solutions because the allowable decrease of Activity 1 and the allowable increase of Activity 2 are 0 An alternative optimal solution is shown below obtained by adjusting the profit for activity 2 to 300 01 1 2 3 4 5 6 7 8 9 10 ABCDEF Activity 1Activity 2 Unit Profit 500 300 01 UsedAvailable Resource A155216 6667 300 Resource B106240 240 Resource C812450 0 the objective increases as x1 increases so the optimal solution is x1 x2 5 5 0 If c2 0 slope of objective function line is c1 c2 If c1 c2 1 2 or equivalently c1 c2 1 2 then the optimal solution is x1 x2 0 1 If c1 c2 c1 c2 2 then the optimal solution is x1 x2 4 3 Note if c1 c2 1 2 or 2 then the optimal solution is at 4 3 and 0 1 or 5 5 0 respectively along with the connecting line Case 3 c2 0 i e c1 0 then the optimal solution is x1 x2 5 5 0 If c1 c2 0 i e c1 1 Benefit 21 20 1 Activity 1Activity 2Total Cost Number of Units00 0 Benefit Contribution per Unit Solver could not find a feasible solution c 12 1 2 x1 x2 17 12 a b 1 2 3 4 5 6 7 8 9 ABCDEF Activity 1Activity 2 Unit Profit9070 Available LevelMinimum Resource212 2 Activity 1Activity 2Total Profit Number of Units1090 Benefit Contribution per Unit Solver could not find a feasible solution CD17 17 c 12 2 2 x1 x2 1 1 17 13 a CD17 18 b Yes Optimal Solution x1 x2 0 10 and Profit 10 c No The objective function value is maximized by sliding the objective function line to the right This can be done forever so there is no optimal solution d No solutions exist that will make the profit arbitrarily large This usually occurs when a constraint is left out of the model CD17 19 e 1 2 3 4 5 6 7 8 9 ABCDEF Activity 1Activity 2 Unit Profit1 1 UsedAvailable Resource A 130 30 Resource B 310 30 Activity 1Activity 2Total Profit Number of Units000 Resource Used Per Unit The Solver message was that the Set Cell values do not converge There is no optimal solution because a better solution can always be found 17 14 a b No The objective function value is maximized by sliding the objective function line up This can be done forever so there is no optimal solution CD17 20 c Yes Optimal Solution x1 x2 10 0 and Profit 10 d No solutions exist that will make Z arbitrarily large This usually occurs when a constraint is left out of the model e 1 2 3 4 5 6 7 8 9 ABCDEF Activity 1Activity 2 Unit Profit 11 UsedAvailable Resource A2 10 20 Resource B1 20 20 Activity 1Activity 2Total Profit Number of Units000 Resource Used Per Unit The Solver message was that the Set Cell values do not converge There is no optimal solution because a better solution can always be found 17 15 a CD17 21 b Corner Point 0 0 x2 0 and x1 0 0 2 x1 0 and x2 2 1 2 x1 x2 3 and x1 2 2 1 x2 2 and x1 x2 3 0 2 x1 2 and x2 0 c Corner Points x1 x2 0 0 2 0 2 1 1 2 0 2 d Corner Point 0 0 0 2 and 2 0 are adjacent 0 2 0 0 and 1 2 are adjacent 1 2 0 2 and 2 1 are adjacent 2 1 2 0 and 1 2 are adjacent 2 0 0 0 and 2 1 are adjacent e Corner Points 0 0 and 0 2 share x1 0 0 2 and 1 2 share x2 2 1 2 and 2 1 share x1 x2 3 2 1 and 2 0 share x1 2 2 0 and 0 0 share x2 0 17 16 a Optimal Solution x1 x2 0 667 0 667 and Profit 6 000 Note corner points will be called A B C D E and F going clockwise from 0 1 b Corner Point A F and B are adjacent B A and C are adjacent C B and D are adjacent D C and E are adjacent E D and F are adjacent F E and A are adjacent CD17 22 17 17 a Optimal Solution x1 x2 2 2 and Profit 10 b Corner Point Corresponding Constraint Boundary Equations Corner Point Satisfies the Equations 0 3 x1 0 x1 2x2 6 0 0 0 2 3 6 2 2 x1 2x2 6 2x1 x2 6 2 2 2 6 2 2 2 6 3 0 2x1 x2 6 x2 0 2 3 0 6 0 0 0 0 x2 0 x1 0 0 0 0 0 c Corner Point x1 x2 Its Adjacent Corner Points 0 3 0 0 and 2 2 2 2 0 3 and 3 0 3 0 2 2 and 0 0 0 0 3 0 and 0 3 CD17 23 d Corner Point x1 x2 Profit 3x1 2x2 0 3 6 2 2 10 3 0 9 0 0 0 Optimal Solution x1 x2 2 2 and Profit 10 e Corner Point Profit 3x1 2x2 Next Step 0 0 0 Check points 3 0 and 0 3 0 3 3 0 6 9 Move to 3 0 Check point 2 2 2 2 10 Stop 2 2 is optimal the next corner point is 0 3 which has already been checked 17 18 a Optimal Solution x1 x2 2 2 and Profit 6 CD17 24 b Corner Point Corresponding Constraint Boundary Equations Corner Point Satisfies the Equations 0 2 667 x1 0 x1 3x2 8 0 0 0 3 2 667 8 2 2 x1 3x2 8 x1 x2 4 2 3 2 8 2 2 4 4 0 x1 x2 4 x2 0 4 4 0 0 0 0 x2 0 x1 0 0 0 0 0 c Corner Point x1 x2 Its Adjacent Corner Points 0 2 667 0 0 and 2 2 2 2 0 2 667 and 4 0 4 0 2 2 and 0 0 0 0 4 0 and 0 2 667 d Corner Point x1 x2 Profit x1 2x2 0 2 667 5 333 2 2 6 4 0 4 0 0 0 Optimal Solution x1 x2 2 2 and Profit 6 e Corner Point Profit x1 2x2 Next Step 0 0 0 Check points 0 2 667 and 4 0 0 2 667 4 0 5 333 4 Move to 0 2 667 Check point 2 2 2 2 6 Stop 2 2 is optimal the next corner point is 4 0 which has already been checked CD17 25 17 19 a Optimal Solution x1 x2 3 4 and Profit 17 b Corner Point Corresponding Constraint Boundary Equations Corner Point Satisfies the Equations 0 5 x1 0 x1 3x2 15 0 0 0 3 5 15 3 4 x1 3x2 15 2x1 x2 10 3 3 4 17 2 3 4 10 4 2 2x1 x2 10 x1 4 2 4 2 10 4 4 4 0 x1 4 x2 0 4 4 0 0 0 0 x2 0 x1 0 0 0 0 0 c Corner Point x1 x2 Its Adjacent Corner Points 0 5 0 0 and 3 4 3 4 0 5 and 4 2 4 2 3 4 and 4 0 4 0 4 2 and 0 0 0 0 4 0 and 0 5 CD17 26 d Corner Point x1 x2 Profit 3x1 2x2 0 5 10 3 4 17 4 2 16 4 0 12 0 0 0 Optimal Solution x1 x2 3 4 and Profit 17 e Corner Point Profit 3x1 2x2 Next Step 0 0 0 Check points 0 5 and 4 0 0 5 4 0 10 12 Move to 4 0 Check point 4 2 4 2 16 Move to 4 2 Check point 3 4 3 4 17 Move to 3 4 Stop 3 4 is optimal the next corner point is 0 5 which has already been checked CD17 27 17 20 Corner Point Profit 10 x1 20 x2 Next Step 0 0 0 Check 0 7 5 and 9 0 0 7 5 9 0 150 90 Move to 0 7 5 Check 3 9 3 9 210 Move to 3 9 Check 4 5 7 5 4 5 7 5 195 Stop 3 9 is optimal 17 21 Corner Point Profit 2x1 3x2 Next Step 0 0 0 Check 2 5 0 and 0 1 2 5 0 0 1 5 3 Move to 2 5 0 Check 3 333 3 333 3 333 3 333 16 667 Move to 3 333 3 333 Check 3 4 CD17 28 3 4 18 Move to 3 4 Check 0 6 2 8 0 6 2 8 9 6 Stop 3 4 is optimal 17 22 Corner Point Cost 15x1 20 x2 Next Step 2 4 110 Check 0 6 and 6 2 0 6 6 2 120 130 Stop 2 4 is optimal 17 23 CD17 29 Corner Point Cost 5x1 7x2 Next Step 12 6 102 Check 21 0 and 0 18 21 0 0 18 105 126 Stop 12 6 is optimal 17 24 a True see solution concept number 6 b False there can be an infinite number of optimal solutions such as the set of solutions along a line segment between two corner points c True if the objective function line is parallel to the constraint boundary line that connects the two 17 25 a If the feasible region is unbounded then there may be no optimal solution b An optimal solution may contain all points on a line segment between two corner points c If an adjacent corner point has an equal objective function value then all the points on the connecting line segment will also be optimal 17 26 a The problem may not have an optimal solution b The optimality test checks whether the current corner point is optimal The iterative step only moves to a new corner point c The simplex method only chooses the origin as the initial corner point when it is a feasible point d One of the adjacent points is likely to be better not necessarily optimal e The simplex method only identifies the rate of improvement not all the adjacent corner points CD17 30 17 27 a c 1 2 3 4 5 6 7 8 9 10 ABCDEF Activity 1Activity 2 Unit Profit21 million UsedAvailable Resource A3115 15 Resource B1210 10 Total Profit Activity 1Activity 2 million Number of Units4311 Resource Used Per Unit b Corner Point x1 x2 Profit 2x1 x2 0 0 0 5 0 10 4 3 11 0 5 5 Optimal Solution x1 x2 4 3 and Profit 11 million CD17 31 d Corner Point Profit 2x1 x2 Next Step 0 0 0 Check 5 0 and 0 5 5 0 0 5 10 5 Move to 5 0 Check 4 3 4 3 11 Move to 4 3 Stop 4 3 is optimal the next corner point is 0 5 which has already been checked CD17 32 17 28 a Corner Points 0 0 4 0 and 0 4 b Corner Point Profit 3x1 x2 Next Step 0 0 0 Check 4 0 and 0 4 4 0 0 4 12 4 Move to 4 0 Stop 4 0 is optimal the next corner point is 0 4 which has already been checked c 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ABCDE Interio