3. (25 min.) Consider the directed network at right: AD 6 1 a. Interpreting the values on the arcs as distances, find the shortest path from node 0 to node 5 by Dijkstra's algorithm (you can do it directly on the graph, as we did in class): b. Interpreting the values on the ares as costs per unit transported, if there is a supply of 3 units at node 0 and a demand of 4 units at node 3 (so ignore nodes 4 and 5 and the arcs involving them), formulate the resulting transshipment problem (make the table of costs, supplies, and demands): c. Find an initial solution to your problem in (b) by the Best Box Method (break ties by the Northwest Corner concept, and cross off columns first if there's a choice), and test it for optimality. What does the optimality test correspond to in general terms (explain how and why it works, including what the Aly's are and the idea behind how to find them)? Use the Transportation Simplex Method to find the optimal solution. d. Interpreting the values on the arcs as costs, and ignoring the directions of the arcs, find the Minimum Spanning Tree. e. Interpreting the values on the arcs as flow capacities, find the maximum flow through the system. 6 15 4. (6 min.) Suppose you accumulate 1 load of laundry every week, have a fixed cost of $4 every time you do your laundry and a variable cost of $2.50/load, and have a "holding" cost of ($2/load)/week for dirty laundry. How long should you wait to do your laundry to minimize your cost per week? What assumptions are you making? 2 3. (25 min.) Consider the directed network at right: AD 6 1 a. Interpreting the values on the arcs as distances, find the shortest path from node 0 to node 5 by Dijkstra's algorithm (you can do it directly on the graph, as we did in class): b. Interpreting the values on the ares as costs per unit transported, if there is a supply of 3 units at node 0 and a demand of 4 units at node 3 (so ignore nodes 4 and 5 and the arcs involving them), formulate the resulting transshipment problem (make the table of costs, supplies, and demands): c. Find an initial solution to your problem in (b) by the Best Box Method (break ties by the Northwest Corner concept, and cross off columns first if there's a choice), and test it for optimality. What does the optimality test correspond to in general terms (explain how and why it works, including what the Aly's are and the idea behind how to find them)? Use the Transportation Simplex Method to find the optimal solution. d. Interpreting the values on the arcs as costs, and ignoring the directions of the arcs, find the Minimum Spanning Tree. e. Interpreting the values on the arcs as flow capacities, find the maximum flow through the system. 6 15 4. (6 min.) Suppose you accumulate 1 load of laundry every week, have a fixed cost of $4 every time you do your laundry and a variable cost of $2.50/load, and have a "holding" cost of ($2/load)/week for dirty laundry. How long should you wait to do your laundry to minimize your cost per week? What assumptions are you making? 2