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

ESI6314: Deterministic Methods in Operations ResearchHW #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%