atar University, College of Engineering Advanced Operations Research, IENG 331 Spring 2017 Instructor: Dr. A.Sleptchenko Homework 26/05/2017 Contains 6 problems (120 points) 1. (20 points) Dual Problem Formulation Consider the following linear program (LP). x1 x2 max s.t. 2x1 3x2 4 x1 + x2 1 x1 , x2 0 (a) Plot the feasible region of the primal and show that the primal objective value goes to infinity. (b) Formulate the dual, plot the feasible region of the dual, and show that it is empty. 2. (20 points) Strong Duality Theorem Consider the following LP max x1 2x2 x3 s.t. x1 + x2 + x3 = 1 |x1 | 4 x1 , x2 , x3 0 (a) Convert this optimization problem into a symmetric 1 form linear program, and then write down the corresponding the dual LP. (b) Solve both LP's using a solver of your choice (c) Verify that primal and dual optimal solutions satisfy the Strong Duality Theorem. 3. (20 points) Duality and Sensitivity Analysis Consider the following LP max x1 2x2 s.t. x1 2x2 3 x1 + 2x2 4 x1 + 7x2 6 x1 , x2 0 1 A Linear Programs in symmetric form should look as follows: max cT x s.t. Ax b x 0. (a) Solve this problem using a solver of your choice and generate the sensitivity report. (b) Find the dual of the above LP. Read the shadow prices from the sensitivity report, and verify that it satisfies the dual LP and gives the same dual objective value as the primal. (c) Reproduce how the reduced costs are found by your solver (different solvers might give reduce costs with different signs) 4. (20 points) Shortest Path Problem Consider the following set of jobs, 2 machines and the objective to minimize the makespan: Job 1 2 3 4 5 6 7 8 9 10 Processing Time (days) 2 3 5 3 3 4 4 4 3 2 Release Time (days) 9 1 4 1 7 10 1 9 2 5 Due Date (days) 12 6 12 6 13 15 6 15 7 10 Weight 0.41 0.21 0.15 0.62 0.07 0.30 0.98 0.84 0.02 0.43 (a) Assuming that the machines are identical (P2 ||Cmax problem) Formulate and solve (using any solver) the corresponding MIP problem. (b) Assuming that the machines are usiform with speeds 1 and 2 (Q2 ||Cmax problem) Formulate and solve (using any solver) the corresponding MIP problem. 5. (20 points) Shortest Path Problem Consider the following graph. B 700 C 90 90 E 60 80 A 70 50 F 90 90 D 80 H 90 80 70 80 I 50 G 80 50 K 100 J (a) Construct the shortest path from A to K using the Dijkstra algorithm. (b) Compute the numbers of operations you had to do on each step. 6. (20 points) 0-1 Knapsack Problem Given the following data for the Unbounded Knapsack Problem. Value Weight Capacity Item1 $11 2kg 10kg Item2 $8 3kg Item3 $6 3kg Item4 $14 5kg Item5 $10 2kg Page 2 Item6 $10 4kg (a) Formulate the corresponding LP problem and solve it using a solver of your choice. (b) Solve the problem using the Dynamic Programming approach. (c) Compute the numbers of operations you had to do on each step of the DP algorithm. Page 3