Research and operations

1405-324: Homework No. 1 Question 1. Consider the following map network, where the number on each arc is the length of time it takes to drive between the two cities. Consider the problem of finding the shortest path through this network from B to E 2 hours 3 hours 3 hours x hours 1 hour 1 hour 2 hours B E y hours 3 hours 3 hours z hours 2. What are the stages and states for the dynamic programming formulation of this problem? b. Use dynamic programming to solve this problem. However, instead of using the usual tables show your work graphically. In particular, fill in the values of the various fi (5) under the corresponding nodes. c. Use dynamic programming to solve this problem by constructing the usual tables X=1.5,Y=2,Z=2 Question 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: X=35.Y=42.Z=79 3 32 46 X 54 78 99 Salespersons Region 2 24 2 3 63 70 4 78 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. Proceed by solving for fi(s) for each node. b. Use dynamic programming to solve this problem by constructing the usual tables. Question 3. Consider the following linear programming problem. Maximize 2 = 15x, + x2 Subject to X: + 2x, Sh 3x2 + x2 51 and X; 0,X2 20 Use dynamic programming to solve this problem. t=15,h=18, I=24