[SOLVED] Isye/cs635 – problem set #4

1 Malfoy Catering
Lucius and Narcissa Malfoy didn’t get to be rich, pureblood, dark wizards without lots of galleons.
Their family made their money in the Wizard catering business. As part of the business, their son
Draco is responsible for ensuring that they have enough clean napkins to meet demand over a period
of n days. The number dj of napkins required on the jth day is known in advance. To satisfy this
requirement, Draco can either buy new napkins for α galleons each, or he can have the napkins laundered. The laundry provides both fast and slow magical cleaning services, In fast service, napkins
are returned q days later for a cost of β galleons per napkin, and in slow service, napkins are returned
p days laters at a cost of γ dollars per napkin. Natrually, p > q, and α > β > γ. Suppose that Draco
must plan for a period of n = 10 days, and the number of required napkins is given as
set T /1*10/ ;
parameter d(T) / 1 50, 2 60, 3 80, 4 70, 5 50, 6 60, 7 90, 8 80, 9 50,
10 100 / ;
Finally, for Draco’s instance, we have p = 4, q = 2, α = 200, β = 75, and γ = 25.
1.1 Problem
Formulate Draco’s problem as a min cost network flow problem and solve it using GAMS. In order to
get full credit, you must model the problem as a min-cost network flow problem. Hint: Your network
should have 22 nodes in it for Draco’s instance. After solving the instance, you should display the
following information, using GAMS parameters named as specified.
Display Item GAMS Parameter Name
Minimum cost required to meet demand Cost
Number of equations in your GAMS model NumEqu
Total number of napkins purchased NumBought
2 Least “Squares.”
2.1 Dynamic Sets Background
This problem is also designed to test our ability to use dynamic sets. We will use the sets
Problem 2 Page 1
ISyE/CS635 Problem Set #4
sets
ALLI /c1*c400/
ALLJ /x1*x100/
;
sets
I(ALLI) /c1*c6/
J(ALLJ) /x1*x4/
;
You only need to declare your equations once. You will re-define the equations for the second
model by dynamically adjusting the sets I and J to include all of the elements from ALLI and ALLJ
for the second part of the problem. Remember, when writing your equations, you declare them over
the full domain (larger set), but you define them (write them) only for those elements you want—the
subset. All of this problem can be done in a single GAMS file.
2.2 The Small Problem
The set of six equations in four variables (1)—(6) does not have a unique solution.1
8×1 − 2×2 + 4×3 − 9×4 = 17 (1)
x1 + 6×2 − x3 − 5×4 = −16 (2)
x1 − x2 + x3 = 7 (3)
x1 + 2×2 − 7×3 + 4×4 = −15 (4)
x3 − x4 = 6 (5)
x1 + x3 − x4 = 0 (6)
For each equation i, and values of variables x = (x1, x2, x3, x4), let ei be the absolute difference
(error) between the left hand side and the right hand side. For example, for i = 2 and x = (−5, 3, 1, 4),
the error is
e2 = |(1)(−5) + 6(3) − (1)(1) − 5(4) − (−16)| = |8| = 8.
2.1 Problem
Write a linear programming instance that will minimize the total absolute error:
e1 + e2 + e3 + e4 + e5 + e6.
Solve this instance with GAMS. Display both the (minimum) total absolute deviation (in a parameter
named TotalDevSmall and the values of x that achieve this, in a parameter named xValSmall(ALLJ).
For example, your code may look like this:
parameters
TotalDevSmall,
xValSmall(ALLJ)
;
TotalDevSmall = ztotdev.L ;
1Most six equations with four variables don’t.
Problem 2 Page 2
ISyE/CS635 Problem Set #4 Prof Michael Ferris
xValSmall(J) = x.L(J);
display TotalDevSmall;
display xValSmall;
2.2 Problem
For the same instance, write a linear programming instance that will minimize the maximum error
in any one equation. Namely find values of x that will
min max{e1, e2, e3, e4, e5, e6}.
Create your instance in GAMS and solve it. What is the minimum max-error that can be achieved?
Display this value in a parameter called MinMaxDevSmall. For example, your code may look like
this:
parameters
MinMaxDevSmall
;
MinMaxDevSmall = zminmax.L;
display MinMaxDevSmall;
2.3 General Least “Squares.”
Let J = {1, 2, . . . , |J|}. For each j ∈ J you have a decision variable xj . You are given a set of equations
containing these decision variables as follows:
X
j∈J
aijxj = bi ∀i ∈ I
Define the absolute error of each equation i ∈ I as the quantity
ei(x) =X
j∈J
(aijxj ) − bi∀i ∈ I.
2.3 Problem
Write a linear program to solve the following optimization problem:
min
x∈R|J|
X
i∈I
ei(x).
Using the GAMS code below to create an instance with |N| = 100, |M| = 400 create and solve this
large random instance. Note the use of yes make the sets I and J contain all of the elements in
ALLI and ALLJ. Be sure to also include the option seed=666 line so that all of us create the same
random instance.
* Reset sets
I(ALLI) = yes;
J(ALLJ) = yes;
option seed = 666 ;
A(I,J) = uniform(-10,10) ;
b(I) = uniform(-100,100) ;
Problem 2 Page 3
ISyE/CS635 Problem Set #4 Prof Michael Ferris
Solve your instance and display the final total deviation in a parameter named TotalDevBig.
For example,
parameters TotalDevBig ;
TotalDevBig = ztotdev.L ;
display TotalDevBig;
2.4 Problem
Solve the same instance from Problem 2.3, but in this case to minimize the maximum error:
min
x∈R|J|
max
i∈I
ei(x)
Solve your instance and display the final minimum maximum deviation in a parameter named
MinMaxDevBig. For example,
parameters MinMaxDevBig;
MinMaxDevBig = zminmax.L;
display MinMaxDevBig;
3 Broom Rental
Oliver Wood retired from his career as keeper at Puddlemere United to start the Wood Broom Rental
Company WBC,
2 and he needs your help. There is a fleet of 94 brooms that are distributed among 10
different locations. The (x, y) coordinates of each broom rental agency (in a grid based on kilometers3
is given in Table 1, as are the number of brooms currently in each location and the number of brooms
required for tomorrow’s rentals. The cost of transporting a broom from one location to another is 0.5
galleon/km. Naturally brooms travel “as the crow flies,” so distances between agencies are Euclidean
distances.
Place x y Required Current
Coor. Coor. Brooms Brooms
Hogwarts 0 0 10 8
Godric’s Hollow 20 20 6 13
Little Whinging 18 10 8 4
Shell Cottage 30 12 11 8
The Leaky Cauldron 35 0 9 12
Ollivander’s 33 25 7 2
Zonko’s Joke Shop 5 27 15 14
Dervish and Banges 5 10 7 11
Little Hangleton 11 0 9 15
Weasley’s Wizard Wheezes 2 15 12 7
Table 1: Information About WBC
3.1 Problem
Write a linear program in GAMS that will determine the movement of all brooms to establish the
required number of brooms at all agencies in a minimum cost manner. Ensure your linear program is
2
In the Wizarding World, brooms may be rented and used, much like cars, in our normal Muggle world.
3Wizards use the metric system
Problem 3 Page 4
ISyE/CS635 Problem Set #4
in the form of a minimum cost network flow problem, and set up the GAMS file to use the appropriate
CPLEX options so it solves as such.
Wood would like to know two things. First, he would like to know the minimum broom tranportation cost (in a GAMS parameter transportCost), as follows:
parameter transportCost ;
transportCost = cost.L;
display transportCost;
Second, according to the optimal transportation plan, he would like to know the set of all locations requiring extra brooms that do not receive any brooms from their closest location (in a set
not from closest).
set not_from_closest(P);
option not_from_closest:0:0:1;
display not_from_closest;
hints:
• Be sure to put quotation marks around elements of sets when defining them if there are spaces
in the element names.
• GAMS has functions sqrt and sqr that may be useful.
• The second part will require a little bit of GAMS coding trickery.
4 Untied Airlines
Prof. Wright hates flying United airlines through O’Hare (ORD). This is a problem, as he is a soughtafter lecturer who frequently must make trips from his home base in Madison (MSN) to San Francisco
(SFO), Houston (IAH), Washington DC (DCA), and Orlando (MCO). If Prof. Wright flies United, he
must travel through ORD, if he travels Delta he can choose to go via Detriot (DTW) or Minneapolis
(MSP).
The travel times between various locations in minutes are:
MSN.ORD 22, MSN.DTW 65, MSN.MSP 46,
MSP.SFO 213, MSP.IAH 139, MSP.DCA 125, MSP.MCO 176,
ORD.SFO 247, ORD.IAH 124, ORD.DCA 82, ORD.MCO 135,
DTW.SFO 280, DTW.IAH 147, DTW.DCA 53, DTW.MCO 130
Delay times at ORD are approximately uniformly distributed between 0 and 3 hours, at DTW the
delay time are are between 0 and 1.5 hours and between 0 and 2 hours at MSP.
We will assume that Prof. Wright makes 3 trips to each location every year. Prof. Wright is a
notorious cheapskate, and lives for frequent flyer miles. So he would like to only fly one airline.
4.1 Problem
Should Prof. Wright switch to Delta? Justify your answer with a mathematical model and explain
what your model does to deal with the uncertainty.
4.2 Problem
What if you add a constraint that he must always use the same hub?
4.3 Problem
What if he forgoes frequent flyer miles – which route should he then use for which flight?
Problem 4 Page 5