11.2-2.The sales manager for a publisher of college textbooks has six traveling salespeople to assign to three different regions of the country. She has decided that each region should be assigned at least one salesperson and that each individual salesperson should be restricted to one of the regions, but now she wants to determine how many salespeople should be assigned to the respective regions in order to maximize sales.The next table gives the estimated increase in sales (in appropriate units) in each region if it were allocated various numbers of salespeople:Region Salespersons1 2 3 1 35 21 28 2 48 42 41 3 70 56 63 4 897075(a)Use dynamic programming to solve this problem. Instead of using the usual tables, show your work graphically by constructing and filling in a network such as the one shown for Prob. 11.2-1. Proceed as in Prob. 11.2-1b by solving forfor each node (except the terminal node) and writing its value by thenode. Draw an arrowhead to show the optimal link (or links in case of a tie) to take out of each node. Finally, identify the resulting optimal path (or paths) through the network and the corresponding optimal solution (or solutions).(b) Use dynamic programming to solve this problem by constructing the usual tables for n = 3, n = 2, and n = 1.Solution: let the Sn=number of salesperson still available for allocation to remaining regions(n=1,2,3)Xn=number of salesperson allocation to region n s 1=6 1≤x 1≤s 1 s 2=6-x 1 1≤ x 2≤s 2 s 3=6-x 1-x 2 1≤ x 3=s 3s 2=s 1-x 1 s 3=s 2−x 2P(s i , x i )=the measure of performance maximize=∑P(s i ,x i )3i=1f n∗s n=max{ P(s n,x n)+ f n+1∗s n+1}f4∗s4=0S3F3X3128 1241 2363 3475 4f2s2 x21234f2x2 249491 36270702 484838484 1 or 3 59610597981052s1 x11234f1x1 6140132140138140 1 or 3So x1=1 , x2=1 or 3 , x3=4or 2 orx1=3 , x2=2 , x3=1Sales is 140.11.3-3.A college student has 7 days remaining before final examinations begin in her four courses, and she wants to allocate this study time as effectively as possible. She needs at least 1 day on each course, and she likes to concentrate on just one course each day, so she wants to allocate 1, 2, 3, or 4 days to each course. Having recently taken an OR course, she decides to use dynamic programming to make these allocations to maximize the total grade points to be obtained from the four courses. She estimates that the alternative allocations for each course would yield the number of grade points shown in the following table:Estimated Grade PointsCourseStudy Days 1 2 3 41 3 52 6 2 5 5 4 73 6 6 7 9 47989Solve this problem by dynamic programming.Solution:Let the s n =the number of day still available for allocation to remaining course(n=1,2,3,4) x n =the number of day allocation to course ns 1=7 1≤x 1≤s 1 s 2=7-x 1 1≤ x 2≤s 2 s 3=7-x 1−x 2 1≤ x 3≤s 3 s 4=7-x 1−x 2−x 3 1≤ x 4=s 4s 2=s 1-x 1 s 3=s 2−x 2 s 4=s 3−x 3P(s i , x i ) is the measure of performance Maximize = ∑P(s i ,x i )4i=1f n ∗s n =max{ P(s n ,x n )+ f n+1∗s n+1} f 5∗s 5=0 s 4f 4x 41 6 12 7 23 9 34 94 fs 3 x 3 1 2 3 4 f 3x 32 8 8 13 9 10 10 24 11 11 13 13 35 11131414143 or 4fs 2 x 2 1 2 3 4 f 2x 23 13 13 1 4151315 15181514181 619181617191s1 x11234f1x1 722232120232Sox1=2,x2=1,x3=3,x4=1The total grade point is 23.11.3-4.A political campaign is entering its final stage, and polls indicate a very close election. One of the candidates has enough funds left to purchase TV time for a total of five prime-time commercials on TV stations located in four different areas. Based on polling information, an estimate has been made of the number of additional votes that can be won in the different broadcasting areas depending upon the number of commercials run. These estimates are given in the following table in thousands of votes:AreaCommercials 1 2 3 40 0 0 0 01 4 6 5 32 7 8 9 73 9 10 11 124 12 11 10 145 15 12 9 16Use dynamic programming to determine how the five commercials should be distributed among the four areas in order to maximize the estimated number of votes won.Solution:Let the s n=the number of commercials still available for allocation to remaining area (n=1,2,3,4) x n=the number of commercials allocation to area ns1=5 0≤x1≤s1s2=5-x1 0≤x2≤s2s3=5-x1−x20≤x3≤s3s 4=5-x 1−x 2−x 3 0≤ x 4=s 4s 2=s 1-x 1 s 3=s 2−x 2 s 4=s 3−x 3P(s i , x i ) is the measure of performance Maximize = ∑P(s i ,x i )4i=1f n ∗s n =max{ P(s n ,x n )+ f n+1∗s n+1} f 5∗s 5=0 s 4f 4x 40 0 0 1 3 1 2 7 2 3 12 3 4 14 4 5 165fs 3 x 3 0 1 2 3 4 5 f 3x 30 0 0 0 1 3 5 5 1 2 7 8 9 9 2 3 12 12 12 11 12 0or1or2 4 14 17 16 14 10 17 1 5 1619211819921 2fs 2 x 2 0 1 2 3 4 5 f 2x 2 0 0 0 0 1 5 6 6 1 2 9 11 8 11 1 3 12 15 13 10 15 1 4 17 18 17 15 11 18 1 5 21 232019161223 1fs 1 x 1 0 1 2 3 4 5 f 1 x 1 5 23222220181523 0So x 1=0,x 2=1,x 3=1,x 4=3, the won number of votes is 23.11.3-5.A county chairwoman of a certain political party is making plans for an upcoming presidential election. She has received the services of six volunteer workers for precinct work, and she wants to assign them to four precincts in such a way as to maximize their effectiveness. She feels that it would be inefficient to assign a worker to more than one precinct, but she is willing to assign no workers to any one of the precincts if they can accomplish more in other precincts.The following table gives the estimated increase in the number of votes for the party's candidate in each precinct if it were allocated various numbers of workers:PrecinctWorkers 1 2 3 40 0 0 0 01 4 7 5 62 9 11 10 113 15 16 15 144 18 18 18 165 22 20 21 176 24 21 22 18This problem has several optimal solutions for how many of the six workers should be assigned to each of the four precincts to maximize the total estimated increase in the plurality of the party's candidate. Use dynamic programming to find all of them so the chairwoman can make the final selection based on other factors.Solution:let the s n=the number of workers still available for allocation to remaining precinct (n=1,2,3,4)x n=the number of workers allocation to precinct ns1=6 0≤x1≤s1s2=6-x1 0≤x2≤s2s3=6-x1−x20≤x3≤s3s4=6-x1−x2−x30≤x4=s4s 2=s 1-x 1 s 3=s 2−x 2 s 4=s 3−x 3P(s i , x i ) is the measure of performance Maximize = ∑P(s i ,x i )4i=1f n ∗s n =max{ P(s n ,x n )+ f n+1∗s n+1} f 5∗s 5=0 s 4f 4x 40 0 0 1 6 1 2 11 2 3 14 3 4 16 4 5 17 5 6 186fs 3 x 3 0 1 2 3 4 5 6 f 3x 30 0 0 0 1 6 5 6 0 2 11 11 10 11 0or1 3 14 16 16 15 16 1or2 4 16 19 21 21 18 21 2or3 5 17 21 24 26 24 21 26 3 6 18 22262929272229 3or4 fs 2 x 2 01 2 3 4 5 6 f 2x 2 0 0 0 0 1 6 7 7 1 2 11 13 11 13 1 3 16 18 17 16 18 1 4 21 23 22 22 18 23 1 5 26 28 27 27 24 20 28 1 6 2933323229262133 1fs 3 x 3 0 1 2 3 4 5 6 f 3 x 3 6 33 32323331292433 0or3So the optimal solutions followx 1=0,x2=1,x3=3,x4=2 orx1=3,x2=1,x3=1,x4=1 orx1=3,x2=1,x3=0,x4=2The total estimated increase in the plurality of the party's candidate is 33.。
![运筹学习题及答案1[宝典]](https://img.taocdn.com/s1/m/eabba216bfd5b9f3f90f76c66137ee06eff94ee6.png)
