Deterministic methods in operation research- industrial engineering

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
11. Formulate an optimization model to decide how much of each kind of stones to produce to maximize
    total revenue.
12. Solve your model using the Excel solver.
13. Using a two-dimensional plot, solve your model graphically.
    Then, by modifying your two-dimensional plot, answer the following questions:
14. How much would it be worth to get another hour of crushing time?
15. How much would it be worth to get another hour of sifting time?
16. 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 x1 + 2×2 (1)
    s.t. x1 + αx2 ≤ 2 (2)
    (P) x2 ≥ x1 − 5 (3)
    x2 ≥ 0 (4)
17. Is this optimization model linear or nonlinear, continuous or mixed integer?
18. Plot the feasible region of this problem when α = 1 and the objective function.
19. For what value of α does (P) have multiple optimal solutions? Explain.
20. For what value of α does (P) have a unique solution? Explain.
21. For what value of α when (P) is unbounded? Explain.
22. If constraint x
    2
    1 + x
    2
    2 ≤ 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.
    3
23. min(x − 1)2 + (x − 2)2 + (x − 3)2 + (x − 4)2 + (x − 5)2 + (x − 6)2 + (x − 7)2
24. (x1 − 1)2 + (x1 + x2 − 2)2 + (x1 + x2 + x3 − 3)2 + (x1 + x2 + x3 + x4 − 4)2 ≥ 1
25. 
    
    
    y1
    (1+y2+y3+y4+y5) +
    y2
    (1+y3+y4+y5) +
    y3
    (1+y4+y5) +
    y4
    (1+y5) ≤ 1
    (1+y3+y4+y5)
    y1+y2 +
    y2+y3
    (1+y4+y5) +
    y3+y4
    (1+y5) ≤ 1
    y1+y2+y3
    (1+y4+y5) +
    y2+y3+y4 ≤ 1
    y1+y2+y3+y4
    (1+y5)
    (1+y5)
    ≤ 1
    4.
    
    x1 + y1 + z1 ≤ 3, x1 + y1 + z2 ≤ 4, x1 + y2 + z1 ≤ 4, x1 + y2 + z2 ≤ 5
    x2 + y1 + z1 ≤ 4, x2 + y1 + z2 ≤ 5, x2 + y2 + z1 ≤ 5, x2 + y2 + z2 ≤ 6
    5.
    max
    
    
    
    z1,1 + z2,1 + z3,1 + z4,1
    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