OR6205 DETERMINISTIC OPERATIONS RESEARCH Final Exam – Fall 2006 Instructor: Dr. E. Melachrinoudis Student: ______________________ Justify briefly your answer, where appropriate, and show all work! Problem 1 (20 points) A government analyst has identified five critical subsystems that are instrumental to the mission effectiveness of a new fighter aircraft that has been designed by the Aero-Astro aircraft company. It has been determined that the overall effectiveness of the aircraft is equal to the product of effectiveness (Eff) of the five subsystems. Only $100K are available for the subsystems. Although numerous bids have been received, Aero-Astro has identified two options (A and B) for each subsystem that meet the design specifications. The table below provides cost and effectiveness for each of the two options that are considered for the five critical subsystems. For example, if the company decides to use option B for the third subsystem (WPNS) it will pay $25K and the subsystem’s effectiveness will be .90. (a) Formulate a dynamic programming model that maximizes the overall effectiveness that can be obtained. Define stages, decision variables, state, state transformation, and recursive relationship. (b) Solve for the last two stages only. (c) Based on the information you obtained in part (b), (i) Which option should the company choose (A or B) for Radar and Navigation, if the budget for these two subsystems was $50K (ii) What is the minimum amount of money the company needs to buy these two subsystems, regardless of effectiveness Options Eff and Cost of the options for the five critical subsystems UHF Radio TACAN WPNS Radar Navigation A Eff = .95 .90 .95 .90 .95 Cost = 20k 15k 30k 40k 20k B Eff = .90 .85 .90 .85 .80 Cost = 15k 10k 25k 30k 10k Solution: (a) Stages: The subsystems, n = 1, 2, 3, 4, 5 Decision variables: The chosen option for each subsystem, Xn = A or B States: $K available for remaining subsystems, Sn, S1 = $100K State transformation: Recursive relationship: fn*(Sn) = max {eff(Xn).fn+1*(Sn–Cn(Xn))} (b) n = 5 f5(S5,X5) f5*(S5) X5* A B S5 < 10 - - - - 10 ≤ S5 < 20 - .80 .80 B 20 ≤ S5 .95 .80 .95 A n = 4 f4(S4,X4) f4*(S4) X4* A B S4 < 40 - - - - 40 ≤ S4 < 50 - (.85)(.80) = .68 .68 B 50 ≤ S4 (.90)(.80) = .72 (.85)(.95) = .8075 .8075 B (c) (i) f4*(50) = .8075 with X4* = B for radar f5*(50–30) = .95 with X5* = A for navigation (ii) S4 = $40K Sn Sn – Cn(Xn) Xn Xn=A,B Problem 2 (25 points) Consider the transportation problem having the following cost and requirements table: Destination Source 1 2 3 Supply 1 30 25 30 10 2 25 15 20 20 Demand 12 14 7 (a) Identify an initial basic feasible solution using the Northwest Corner method. (b) Solve using the transportation simplex algorithm. Write below the optimal solution you found (values of variables and objective function); also display the optimal solution in a network representation of the problem by displaying sources, destinations and arcs with (positive) flows. x11* = 10 x12* = 0 x13* = 0 x21* = 0 x22* = 14 x23* = 6 z* = 630 (c) Find a basic feasible solution using Vogel's approximation method. Is it optimal Solution: (a) Destination 1 2 3 Supply So ur ce 1 30 25 30 10 0 10 2 25 15 20 20 18 4 0 2 14 4 3 (D) 0 0 0 3 0 3 Demand 12 2 0 14 0 7 0 → Initial basic solution: x11 = 10, x21 = 2, x22 = 14, x23 = 4, x33 = 3, z = $640. (b) Iteration 1: Destination 1 2 3 Supply So ur ce 1 30 25 30 10 10 5 5 2 25 15 20 20 2 14 4 3 (D) 0 * 0 0 3 –5 5 3 Demand 12 14 7 For basic variables (ui + vj = cij): x11: u1 + v1 = 30 for u1 = 0, v1 = 30 x21: u2 + v1 = 25 u2 = –5 x22: u2 + v2 = 15 v2 = 20 x23: u2 + v3 = 20 v3 = 25 x33: u3 + v3 = 0 u3 = –25 For nonbasic variables (cij – ui – vj): x12: c12 – u1 – v2 = 25 – 0 – 20 = 5 > 0 x13: c13 – u1 – v3 = 30 – 0 – 25 = 5 > 0 x31: c31 – u3 – v1 = 0 – (–25) – 30 = –5 < 0 *** since this is negative, solution is not optimal! x32: c32 – u3 – v2 = 0 – (–25) – 20 = 5 > 0 → x31 enters the basis with value min (2, 3) = 2, x21 leaves the basis; donor cells: (2,1) and (3,3); recipient cells: (3,1) and (2,3). Iteration 2: Destination 1 2 3 Supply So ur ce 1 30 25 30 10 10 0 0 2 25 15 20 20 5 14 6 3 (D) 0 0 0 3 2 5 1 Demand 12 14 7 For basic variables (ui + vj = cij): x11: u1 + v1 = 30 for u1 = 0, v1 = 30 x22: u2 + v2 = 15 v2 = 25 x23: u2 + v3 = 20 u2 = –10 x31: u3 + v1 = 0 u3 = –30 x33: u3 + v3 = 0 v3 = 30 For nonbasic variables (cij – ui – vj): x12: c12 – u1 – v2 = 25 – 0 – 25 = 0 = 0 (multiple optimal solution – see below) x13: c13 – u1 – v3 = 30 – 0 – 30 = 0 = 0 (multiple optimal solution – see below) x21: c21 – u2 – v1 = 25 – (–10) – 30 = 5 > 0 x32: c32 – u3 – v2 = 0 – (–30) – 25 = 5 > 0 *** since all are positive, solution is optimal! → Optimal solution #1: x11* = 10, x22* = 14, x23* = 6, x31* = 2, x33* = 1, z* = $630. Network representation of the optimal solution is given as follows: → Since reduced costs are zero (c12 = c13 = 0), there are multiple optimal solutions: 1 2 3 S 1 2 3 S 1 30 25 * 30 10 30 25 30 10 10 0 0 9 1 2 25 15 20 20 25 15 20 20 5 14 6 13 7 3 (D) 0 0 0 3 0 0 0 3 2 5 1 3 D 12 14 7 12 14 7 → Optimal solution #2: x11* = 9, x12* = 1, x22* = 13, x23* = 7, x31* = 3, z* = $630. 1 2 3 1 2 3 Sources Destinations [10] [20] [3] [-12] [-14] [-7] 10 14 6 2 1 1 2 3 S 1 2 3 S 1 30 25 30 * 10 30 25 30 10 10 0 0 9 1 2 25 15 20 20 25 15 20 20 5 14 6 14 6 3 (D) 0 0 0 3 0 0 0 3 2 5 1 3 D 12 14 7 12 14 7 → Optimal solution #3: x11* = 9, x13* = 1, x22* = 14, x23* = 6, x31* = 3, z* = $630. (c) Destination 1 2 3 Supply Row difference So ur ce 1 30 25 30 10 0 5 5 0 9 1 2 25 15 20 20 6 0 5 5 5 14 6 3 (D) 0 0 0 3 0 0 3 dj 12 9 0 14 0 7 1 0 Column difference 25* 15 20 5 10* 10 5 10* → Solution: x11 = 9, x13 = 1, x22 = 14, x23 = 6, x31 = 3, z = $630, which is optimal (same as optimal solutio
n #3 given in part (b)). 1 2 3 Problem 3 (10 points) Three federally funded projects are to be assigned to three out of four candidate research labs. The costs of each possible placement are given in the table below. Use the Hungarian algorithm to determine the most economical allocation of projects and the associated cost. Find alternative optimal solutions if they exist. Existing research laboratories Project Sandy Lab Furmy Lab Xenonne Lab Liverly Lab Crygenic Cache Memory (CCM) 12 15 10 14 Pentium Oxide Depletion (POD) 8 10 6 9 Galactic Genome Mapping (GGM) 20 22 18 12 Solution: 12 15 10 14 2 5 0 4 0 3 0 4 8 10 6 9 2 4 0 3 0 2 0 3 20 22 18 12 8 10 6 0 6 8 6 0 0 0 0 0 0 0 0 0 0 0 2 2 → Four lines needed to cross all zeroes => Optimal solution! So, multiple optimal solutions are as follows, with z* = 30 (12+6+12+0=30 for optimal solution #1 and 10+8+12+0=30 for optimal solution #2): Optimal solution #1 Optimal solution #2 12 15 10 14 12 15 10 14 8 10 6 9 8 10 6 9 20 22 18 12 20 22 18 12 0 0 0 0 0 0 0 0 1 2 3 4 Problem 4 (7 points) For each statement below (1-10) fill-in the blank with a letter to indicate the most appropriate choice from alternatives (A-I) shown in the list below. An alternative (letter) may be the most appropriate choice to more than one statement (number). 1. The assignment problem is a special case of the B . 2. The maximum flow problem is a special case of the F . 3. We cannot solve the E, G by simplex. 4. The critical path of a project network is the I from start to finish. 5. The algorithms for solving the E are greedy in nature. 6. The transshipment problem is a generalization of the B . 7. The G, A is a discrete (having integer solutions) optimization problem. 8. A C problem is solved by dividing it into smaller sub-problems which are solved sequentially. 9. The basic solutions of the A are highly degenerate. 10. The best algorithm for solving the A is a simplex-based one in which we preserve primal and dual feasibility in each iteration and we strive for complementary slackness. A. Assignment problem B. Transportation problem C. Dynamic programming D. Maximum flow problem E. Minimum spanning tree problem F. Minimum cost network flow problem G. Generalized assignment problem H. Shortest path problem I. Longest path problem Problem 5 (23 points) Consider the directed network below: (a) Assuming that the numbers on the arcs are distances, use Dijstrar’s algorithm to find the shortest path(s) from node 1 to node 6. (b) Using the same numbers for arc capacities, (i) Find the arc flows that maximize flow from node 1 to node 6. (ii) Find a cut (e.g. a set of arcs) with total capacity equal to the maximum flow. (c) Refer to the original figure below, but now the numbers on the arcs represent unit costs of flow. In addition, nodes 1 and 2 are sources supplying 2 and 3 units, respectively, and nodes 5 and 6 are sinks requiring 3 and 2 units, respectively. Arcs (1,3) and (5,6) have a flow capacity of 3 and 2 units, respectively. Formulate a minimum cost network flow model by writing the objective function and the constraints. Solution: (a) n Solved nodes directly connected to unsolved nodes Closest connected unsolved node Total distance involved nth nearest node Minimum distance Last connection 1 1 2 1 2 1 (1,2) 2 1 2 4 3 3 1+7=8 4 3 (1,4)* 3 1 2 4 3 3 3 6 1+7=8 3+2=5 3 5 (4,3)* 4 2 4 3 5 6 5 1+8=9 3+9=12 5+3=8 5 8 (3,5)* 5 4 5 6 6 3+9=12 8+2=10 6 10 (5,6)* → Shortest path is 1 → 4→ 3 → 5 → 6, with a total distance of 10. 2 1 5 1 6 3 3 4 6 3 8 9 7 2 2 (b) (i) Iteration 1: One of several augmenting paths is 1 → 2 → 5 → 6, which has a residual capacity of min{1, 8, 2} = 1. By assigning a flow of 1 to this path, the resulting residual network is as follows: Iteration 2: Assign a flow of 1 to path 1 → 3 → 5 → 6. The resulting residual network is as follows: Iteration 3: Assign a flow of 3 to path 1 → 4 → 6. The resulting residual network is as follows: → There are no more augmenting paths, so the current flow pattern is optimal, with the maximum flow of 2+3=5. (ii) Cut = {(1,4),(5,6)}, with a total capacity of 2+3=5 (equal to the maximum flow). 2 1 5 0 6 3 3 4 6 3 7 9 7 2 1 1 1 1 0 0 0 0 0 0 2 1 5 0 5 3 3 4 6 2 7 9 7 2 0 1 1 2 1 0 0 0 0 1 2 1 5 0 5 3 0 4 6 2 7 6 7 2 0 1 1 2 1 0 0 3 3 1 (c) Min z = X12 + 6X13 + 3X14 + 7X23 + 2X43 + 8X25 + 3X35 + 9X46 + 2X56 subject to X12 + X13 + X14 = 2 (node 1) X12 + X23 + X25 = 3 (node 2) X13 X23 X43 + X35 = 0 (node 3) X14 + X43 + X46 = 0 (node 4) X25 X35 + X56 = 3 (node 5) X46 X56 = 2 (node 6) X13 ≤ 3, X56 ≤ 2, and all variables ≥ 0 Problem 6 (15 points) A project involves 7 activities (labeled A, B, …, G) with completion times and precedence relationships as shown in the table below. Activity Completion time (days) Predecessors A 3 – B 6 – C 2 D, E D 6 A, B E 8 B, F F 5 A G 3 B, C, F (a) Construct a network for the project. (b) Find the critical path and the associated project time by enumerating all possible paths. Solution: (a) (b) Path Length Start → A → F → G → Finish 3 + 5 + 3 = 11 Start → A → F → E → C → G → Finish 3 + 5 + 8 + 2 + 3 =21 Start → A → D → C → G → Finish 3 + 6 + 2 + 3 = 14 Start → B → D → C → G → Finish 6 + 6 + 2 + 3 =17 Start → B → E → C → G → Finish 6 + 8 + 2 + 3 =19 Start → B → G → Finish 6 + 3 = 9 F 3 6 A G E 8 5 3 6 D C 2 B Start Finish ← Critical path!