**Unformatted text preview:**

90-722: Man Sci I, Final Exam Solution (AFTERNOON), Spring 2018Question #1: (12 Points): Note: Only concise, precise, and neat answers will be given credit. Think before you write. For each pair of problems or concepts, state which is more general and how it generalizes the other, or you can express it the other way – which is a special case of the other and how so.Transportation Problem vs. Assignment ProblemInteger Programming vs. Linear ProgrammingNonlinear Programming vs. Linear ProgrammingGeneralized network flow vs. Standard network optimization problemSolutionThe assignment problem is the special case of a TP in which all the supplies and all of the demands are equal to 1.IP generalizes LP by allowing decision variables that are not continuous. LP is the special case of NLP in which the objective function and constraints can be written aslinear functions of the decision variables (and all variables are allowed to be continuous).Generalized network flow problems generalize standard network flow problems by allowing the amount that comes out of an arc to differ from the amount that goes into an arc (e.g., because of leaks, pilferage, spoilage, compounding, etc.)Question #2: (15 Points):a) For what range of values of the parameter in Cell C3 would the current optimal solution remain optimal?b) For what range of values of the parameter in Cell F7 would the nature of the solution remain the same?c) What is the most the decision maker (DM) should pay to obtain one more unit of the fourth resource? d) What is the most the DM should be willing to pay to obtain 20 more units of that resource?e) If the DM could produce a new product that uses one unit of each of the resources, what is the least revenue it would have to generate per unit in order for it to be optimal to beginmaking that product?Solutiona) 1 – 3.25b) 8 to infinity1c) $0.2777d) That cannot be determined from the given information because 20 exceeds the allowable increase over which we can know the given shadow price applies.e) The sum of the shadow prices for each resources is $0.296 + $0 + $0.537 + $0.277 = $1.11.The next few problems work extend the Rent-a-Dent problem from Ragsdale’s Chapter 3 that weworked in class. To remind you, I’ll paste the problem statement and Excel spreadsheet for the problem here. 2Question #3: (10 Points): Write the algebraic formulation of this LP.SolutionXij = number of cars shipped from location i to location jMIN 54 X13 + 17 X14 + 23 X15 + 30 X16 + 24 X23 + 18 X24 + 19 X25 + 31 X26 ST X13 + X14 + X15 + X16 = 16X23 + X24 + X25 + X26 = 185 X13 + X23 105 X14 + X24 105 X15 + X25 105 X16 + X26 10Xij 0Or Min Z=∑ijcijXijs.t.for i=1,2∑jXij≥ Si(equalityis OK )for j=3,4,5,6 5 ≤∑iXij≤ 103for all ij Xij≥ 0Question #4: (12 Points): Extend your formulation to (a) Impose a fixed cost of $10 for each source-destination pairing such that any cars are sent from source i to destination j and (b) Ensure that if any cars are sent between a pair of nodes then at least three are sent between those nodes.SolutionIntroduce binary auxiliary variables Yij that indicate whether any cars are shipped from source i to destination j, for i = 1, 2 and j = 3, 4, 5, 6Augment the objective function by adding to it $10 ∑i∑jYij,and add the constraintsFor all i, j: Xij ≤ M*YijXij ≥ 3 YijFor all i,j Yij is binaryQuestion #5: (24 Points): Using summation notation, give the full formulation for the extension of Problem #5 that considers two goals: (1) Keep the total cost – including fixed costs – to no more than $750 and (2) Hold down the number of source-destination pairs such that cars are shipped from source i to destination j to no more than 5. In particular, formulate a GP that lets the DM minimize the maximum percent deviation from these two goals. For any hard constraints, be very explicit about the ranges of summation. Solution: Use the usual notation for deviational variables and maximum % deviation variable Q. Let goal #1 be minimizing cost and goal #2 be minimizing the number of arcs used.Let the decision variables beXij = the (non-negative) number of cars shipped from source i to destination j,Let Yij be binary auxiliary variables that indicate whether any cars are shipped from source i to destination j, for i = 1, 2 and j = 3, 4, 5, 6.Introduce the notation that cij = cost per unit of shipping cards from source i to destination j,Si = # of cars at source i (S1 = 16, S2 = 18), and4Min Qs.t.d2+¿5d2−¿5;Q ≥¿d1+¿750;Q≥ ¿d1−¿750;Q≥ ¿Q≥ ¿+¿=750−¿−d1¿∑i=12∑j=36(cijXij+10Yij)+d1¿+¿=5−¿−d2¿∑i=12∑j=36Yij+d2¿For i = 1,2: ∑j=36Xij≥ SiFor j = 3,4,5, and 6: 5 ≤ ∑i=12Xij≤10For all i, j: Xij ≤ YijXij ≥ 3 YijFor all i,j, Xi ≥ 0 and Yij is binary +¿≥ 0−¿ ,d2¿+¿, d2¿−¿ ,d1¿Q , d1¿Question #6: (10 Points): Sketch what the shape of the efficient frontier for this problem would be on axes indicating attainment on the two goals. On your graph, put attainment on Goals #1 and #2 on the horizontal and vertical axes, respectively. Label the axes with the actual goal (not 5“Goal #1” and “Goal #2”). Put a smiley face in the corner that would be ideal. Label one side ofthe frontier “infeasible” and the other side “suboptimal”. Solution: Since the horizontal axis is cost (small #’s are good) and the vertical axis is arcs used sold (small numbers are good again) the smiley face goes in the lower left. The efficient frontier will slope downward and at an decreasing rate (convex). The “infeasible” label goes to the frontier’s lower left. The “suboptimal” label goes to its upper right. Question #7: (8 Points): Only concise, precise, neat and clear answers will receive credit. With regard to the Branch & Bound algorithm:a) Why is it useful to start with an initial solution that is feasible and pretty good?b) When and how does B&B create subproblems under a given problem (node) in the B&B tree?Solution:a) Starting with an initial solution that is feasible and pretty good reduces running time by allowing bounding to begin immediately.b) If the solution to a problem’s LP relaxation contains decision variables that are non-integervalued, select one and fork off two daughter subproblems that inherit all of the decision variables, constraints, and objective function of the parent problem plus one more constraint. Let Xi be one of the

View Full Document