# ESI 6314-Deterministic Methods in Operation Research Q&As- University of Illinois .

ESI6314: Deterministic Methods in Operations Research HW #2 Guideline: • This homework should be submitted using the E-learning assignment section. • All submitted assignments should be neat, organized and legible (hand-written answers are fine). • Different problems should be answered on different sheets of paper. • Please submit all answers as a single pdf file. Try to avoid pencil answers which are pretty light. • For each modeling problem given in this homework (if any), you should describe in this order (1) the data, (2) the variables, (3) the IVRs, (4) the constraints and (5) the objective of the model. All mathematical objects (data, variables, IVRs, constraints and objectives) should be expressed using mathematical symbols and should be explained in words as well. • For Excel questions, you should include in your pdf a screen shot of the spreadsheet together with a brief summary of the formulas you used in the sheet. Moreover, the solution of the model should be presented in the text. • Provide justifications for your answers and show relevant supporting work. All questions of these assignments can be answered using the concepts described in the lectures and covered in the slides. If you wish to get additional descriptions of some of the slides topics, please refer to Chapter 1 and Sections 2.1-2.3 of Rardin’s book. Question 1 [20 points] Read the description of the following optimization problem. Consider then the components of these problems that are itemized. For each of these components, identify whether it belongs to the data, the variables, the constraints or the objectives. Explain why? United flies over 2500 domestic flight legs each day. To this end, it uses about 500 aircrafts for 10 different fleets. United must therefore decides how to assign aircrafts and crews to flight legs in the best way possible. The aim is to produce such an assignment that will then be repeated identically each week day (weekend schedules are treated differently). Two opposing considerations come into play when evaluating a flight leg to aircraft assignment. If the aircraft assigned to a flight leg is too small, it will not be able to accommodate all of the customers’ demand, which will result in revenue loss for United. If the aircraft assigned to a flight leg is too large, then United will lose the revenue that could have been obtained from the unoccupied seats. Further, it will also incur loss from using a larger than necessary aircraft, which is more expensive to operate. Meanwhile, United needs to assign a group of crew members to a set of scheduled flights such that all the scheduled flights are covered. The max crew duty is 14 hours out of a 24-hour day. United’s primary objective in this problem is therefore to maximize profit, which is computed as the difference between ticket sales revenue and the sum of operating costs (including crew cost, fuel cost and landing fees). 1. The number of customers traveling on a flight leg (e.g., flight leg from IAH to ORD in the slides). 2. The group of crew members assigned to a specific flight leg from MCO to IAH. 3. If the first flight leg assigned to aircraft 1 lands in Houston, the next flight leg assigned to aircraft 1 must take off from Detroit. 4. The max crew duty is 14 hours out of a 24-hour day. 5. United tries to maximize profit. 6. The operating cost of a plane includes crew cost, fuel costs and landing fees. 7. Is Houston assigned as the Hub for all fleets? 1 8. Each pilot could not fly five consecutive days. 9. Is it needed to purchase additional aircrafts to meet customer demands? 10. Airline ticket price for the Origin-Destination pair MCO to ATL. Question 2 [20 points] A landscaping supply company produces decorative stones. A ton of coarse stones requires 2 hours of crushing, 5 hours of sifting, and 8 hours of drying. A ton of fine stones requires 6 hours of crushing, 3 hours of sifting, and 2 hours of drying. The coarse stones sell for $400 per ton. The fine stones sell for $500 per ton. In a work week, the plant is capable of 36 hours of crushing, 30 hours of sifting, and 40 hours of drying. Based on the demand forecast, the quantity of coarse stones produced should be at least twice the quantity of fine stones produced. First 1. Formulate an optimization model to decide how much of each kind of stones to produce to maximize total revenue. 2. Solve your model using the Excel solver. 3. Using a two-dimensional plot, solve your model graphically. Then, by modifying your two-dimensional plot, answer the following questions: 4. How much would it be worth to get another hour of crushing time? 5. How much would it be worth to get another hour of sifting time? 6. Could you find the range of the prices for the fine stones such that in the optimal solution, the quantity of coarse stones produced is exactly twice the quantity of fine stones produced. Question 3 [20 points] Consider the following optimization model where the decision variables are x1 and x2 and where α is a parameter (fixed value) of the problem. , i.e., it is not a decision variable: max s.t. (P) x1 + 2×2 x1 + αx2 ≤ 2 x2 ≥ x1 − 5 x2 ≥ 0 (1) (2) (3) (4) 1. Is this optimization model linear or nonlinear, continuous or mixed integer? 2. Plot the feasible region of this problem when α = 1 and the objective function. 3. For what value of α does (P) have multiple optimal solutions? Explain. 4. For what value of α does (P) have a unique solution? Explain. 5. For what value of α when (P) is unbounded? Explain. 6. If constraint x21 + x22 ≤ 1 is added, could you find the range of α values such that the problem is still feasible? 2 Question 4 [20 points] Find the local/global minima and maxima for the following function. You are expected to draw an approximate function curve and point out the local/global minima and maxima in the graph. You do not need to provide the exact solution for each local/global minima or maxima. f (x) = 3x + 2(x + 2)2 + 3(x − 3)3 − (x − 4)4 , where − 5 ≤ x ≤ 1 or 0 ≤ x ≤ 6. Question 5 [20 points] Write each of the following as compactly as possible using summation and enumeration symbols. 1. min(x − 1)2 + (x − 2)2 + (x − 3)2 + (x − 4)2 + (x − 5)2 + (x − 6)2 + (x − 7)2 2. (x1 − 1)2 + (x1 + x2 − 2)2 + (x1 + x2 + x3 − 3)2 + (x1 + x2 + x3 + x4 − 4)2 ≥ 1 3. 4. 5. max y1 y2 y3 (1+y2 +y3 +y4 +y5 ) + (1+y3 +y4 +y5 ) + (1+y4 +y5 ) y2 +y3 y1 +y2 y3 +y4 (1+y3 +y4 +y5 ) + (1+y4 +y5 ) + (1+y5 ) ≤ 1 y2 +y3 +y4 y1 +y2 +y3 (1+y4 +y5 ) + (1+y5 ) ≤ 1 y1 +y2 +y3 +y4 ≤1 (1+y5 ) x1 + y1 + z1 ≤ 3, x2 + y1 + z1 ≤ 4, x1 + y1 + z2 ≤ 4, x2 + y1 + z2 ≤ 5, z1,1 + z2,1 + z3,1 + z4,1 + y4 (1+y5 ) ≤1 x1 + y2 + z1 ≤ 4, x1 + y2 + z2 ≤ 5 x2 + y2 + z1 ≤ 5, x2 + y2 + z2 ≤ 6 z1,1 ≤ 2 z1,1 + z1,2 + z2,1 ≤ 3 z1,1 + z1,2 + z2,1 + z1,3 + z2,2 + z3,1 ≤ 4 z1,1 + z1,2 + z2,1 + z1,3 + z2,2 + z3,1 + z1,4 + z2,3 + z3,2 + z4,1 ≤ 5 z1,1 ≥ 0, z1,2 ≥ 0, z2,1 ≥ 0, z1,3 ≥ 0, z2,2 ≥ 0, z3,1 ≥ 0, z1,4 ≥ 0, z2,3 ≥ 0, z3,2 ≥ 0, z4,1 ≥ 0 3 AutoSave OFF Ô o su u = wanswer_1 Home Insert Draw Design Layout References Mailings Review View Tell me Share o Comments X Times New… v 12 v AŤ Аа у v 21 AaBbCcDdEe AaBbCcDdEe Aa BbCcDc AaBbCcDdEt AaBb AaBb CcDdEG Paste B I U Normal vab x ev Av No Spacing Title Heading 1 A Subtitle Heading 2 Х Dictate Sensitivity V V Styles Pane v 1. For each of these components, identify whether it belongs to the data, the variables, the constraints, or the objectives. Explain why? The number of customers traveling on a flight leg (e.g., flight leg from IAH to ORD in the slides). – Variable, because number of customers(Number of tickets) will be counted in the making objective function. The group of crew members assigned to a specific flight leg from MCO to IAH. – Constraint, as the group is fixed . If the first flight leg assigned to aircraft 1 lands in Houston, the next flight leg assigned to aircraft 1 must take off from

Detroit. – Data as it is giving counting of flight The max crew duty is 14 hours out of a 24-hour day. Data, as it will be used in the cost estimation as coefficient of variable . United tries to maximize profit. – Objective, as the statement shows the goal of United. The operating cost of a plane includes crew cost, fuel costs and landing fees. – Data Is Houston assigned as the Hub for all fleets? Yes Each pilot could not fly five consecutive days. – Constraint because restriction on the flying days. . Is it needed to purchase additional aircrafts to meet customer demands? – No T Airline ticket price for the Origin-Destination pair MCO to ATL – Data . 2. Using Excel 1. Objective function 400x+500) Constraints 2x+6y =0 Page 1 of 13 544 words F English (United Kingdom) Focus ES ji! – 89%