8jJUrTR5xXP3Vw
CO 250 Spring 2023: Assignment 2 solutions
A2-1. The candle factory
(a) Decision variables: We need to decide how many boxes of candles to produce in each
week; let us write Xi for the number of boxes of candles produced in week i, i =
1, 2, . . . , n. It is also a good idea to keep track of the number of boxes of candles in
storage; let us write Yi for the number of boxes of candles in storage by the end of week
i, i = 1, 2, . . . , n.
These variables are nonnegative (it doesn’t make sense to produce or store a negative
amount of boxes), but they are allowed to be fractional numbers.
We make the assumption that all order are fulfilled (either from fresh production or
from storage) by the end of the week; this is also the time inventory is updated.
Objective function: Our goal is to maximize the profit. We assume that exactly di
boxes of candles are sold in week i; our total revenue then is r
∑n
i=1 di (note that this
does not depend on any of the decision variables). There are two types of cost: first, the
cost for producing candles, which is piXi during week i and hence
∑n
i=1 piXi in total;
second, the cost for storing candles, which incurs a cost of sYi in week i and hence a
total cost of s
∑n
i=1 Yi.
Our objective function becomes
r
n∑
i=1
di −
n∑
i=1
piXi − s
n∑
i=1
Yi,
and our goal is to maximize this quantity.
Constraints: First, we require nonnegativity constraints on all decision variables, Xi ≥ 0
for all i = 1, 2, . . . , n, and Yi ≥ 0 for all i = 1, 2, . . . , n.
We also require balance equations: the number of boxes we store at the end of week i
should be equal to the number of boxes we store at the end of week i− 1, increased or
decreased by the over- or underproduction during week i:
Xi + Yi−1 = di + Yi for i = 1, 2, . . . , n.
We need to be a bit careful about the constraint indexed by i = 1, as Y0 is not defined
yet. The easiest way around this is to introduce a new decision variable, Y0, and force
its value to be equal to 0; the interpretation is that we start with an empty warehouse.
Here is the final Linear Program:
max r
∑n
i=1 di −
∑n
i=1 piXi − s
∑n
i=1 Yi
subject to Xi + Yi−1 = di + Yi for i = 1, 2, . . . , n
Y0 = 0
Xi ≥ 0 for i = 1, 2, . . . , n
Yi ≥ 0 for i = 1, 2, . . . , n
8jJUrTR5xXP3Vw
(b) The new constraint can be formulated as
|Yi − Yi−1| ≤ D for i = 1, 2, . . . , n.
This, however, is not a linear constraint. We can reformulate these n constraints as 2n
linear constraints, as follows:
−D ≤ Yi − Yi−1 ≤ D for i = 1, 2, . . . , n.
(This is a convenient shorthand for Yi − Yi−1 ≤ D and Yi − Yi−1 ≥ −D for all i.)
We can modify the Linear Program from part (a) by adding these 2n constraints to its
formulation.
A2-2. Serial bonds
(a) We will assume that all investments are settled at the start of the year: midnight on
January 1, starting on January of year 1. We do not care about the order in which
investments and repayments are settled, only in the result after all investments have
been settled.
Decision variables: We need to decide how many contracts of each type to take out in
each year; let us write Xi,t for the number of contracts of type i taken out in year t.
It will be convenient (to compute cashflow) to allow t to be negative as well. So, we
introduce variables
X1,−1, X1,0, . . . , X1,10, X2,−3, X2,−3, . . . , X2,10, X3,−4, X3,−3, . . . , X3,10.
We also need to keep track of the amount of cash that we have available at the start of
year t; let us write Zt, t = 1, 2, . . . , 10 for this quantity.
All variables are allowed to be fractional, but required to be nonnegative.
Objective function: We are interested in maximizing the amount of cash at the start of
year 10. This is simply the variable Z10, and our goal is to maximize this quantity.
Constraints: We need to balance our cashflow between subsequent terms. One way to
do this, is to express the amount of cash that we have available in the next term. This
is the amount of cash we had in the previous term (with 2% interest added), plus the
payoffs of all of the contracts that we have already entered into, minus the cost of the
new contracts we’re entering into.
That is, for all t = 1, . . . , 9:
Zt+1 = 1.02Zt − 95X1,t+1 − 85X2,t+1 − 80X3,t+1
+ 50(X1,t +X1,t−1)
+ 25(X2,t +X2,t−1 +X2,t−2 +X2,t−3)
+ 20(X3,t +X3,t−1 +X3,t−2 +X3,t−3 +X3,t−4),
8jJUrTR5xXP3Vw
while for t = 0:
Z1 =M − 95X1,1 − 85X2,1 − 80X3,1.
We require all decision variables to be nonnegative:
X1,t ≥ 0 for t = −1, 0, . . . , 10
X2,t ≥ 0 for t = −3,−2, . . . , 10
X3,t ≥ 0 for t = −4,−3, . . . , 10
Zt ≥ 0 for t = 1, 2, . . . , 10.
Finally, we are now allowed to invest in some of the bonds in later years:
X1,9 = 0, X1,10 = 0,
X2,7 = 0, X2,8 = 0, X2,9 = 0, X2,10 = 0,
X3,6 = 0, X3,7 = 0, X3,8 = 0, X3,9 = 0, X3,10 = 0.
The final LP formulation becomes:
max Z10
subject to Z1 =M − 95X1,1 − 85X2,1 − 80X3,1
Zt+1
= 1.02Zt − 95X1,t+1 − 85X2,t+1 − 80X3,t+1
+50(X1,t +X1,t−1)
+25(X2,t +X2,t−1 +X2,t−2 +X2,t−3)
+20(X3,t +X3,t−1 +X3,t−2 +X3,t−3 +X3,t−4) for t = 1, 2, . . . , 10
X1,9 = 0, X1,10 = 0
X2,7 = 0, X2,8 = 0, X2,9 = 0, X2,10 = 0
X3,6 = 0, X3,7 = 0, X3,8 = 0, X3,9 = 0, X3,10 = 0
X1,t ≥ 0 for t = −1, 0, . . . , 10
X2,t ≥ 0 for t = −3,−2, . . . , 10
X3,t ≥ 0 for t = −4,−3, . . . , 10
Zt ≥ 0 for t = 1, 2, . . . , 10.
(b) The option to loan up to $M in year 3 (and pay it back with interest in year 8) requires
us to make an addition decision: how much do we loan? Let’s call this quantity L.
Clearly, we need to add the constraints
0 ≤ L ≤M.
The quantity L changes the cash flow in two different years: year 3 and year 8. In year
3, we have an additional L cash available (we assume that we can use it immediately to
invest in bonds), so for t = 2, the constraint starting “Zt+1 = . . .” should be replaced
8jJUrTR5xXP3Vw
by
Zt+1 = 1.02Zt + L− 95X1,t+1 − 85X2,t+1 − 80X3,t+1
+ 50(X1,t +X1,t−1)
+ 25(X2,t +X2,t−1 +X2,t−2 +X2,t−3)
+ 20(X3,t +X3,t−1 +X3,t−2 +X3,t−3 +X3,t−4),
Similarly, in year 8 we will have less money available to invest, so for t = 7, the constraint
starting “Zt+1 = . . .” should be replaced by
Zt+1 = 1.02Zt − 1.1L− 95X1,t+1 − 85X2,t+1 − 80X3,t+1
+ 50(X1,t +X1,t−1)
+ 25(X2,t +X2,t−1 +X2,t−2 +X2,t−3)
+ 20(X3,t +X3,t−1 +X3,t−2 +X3,t−3 +X3,t−4),
(c) You’d expect Dilmohan to take out the loan. When he takes out the loan and does not
do anything with it (simply letting it accrue interest), he will make an additional
(1.02)5M − 1.1M ≈ (1.14− 1.1)M = 0.04M,
and he can potentially get a better performance by investing the loan wisely. So he will
make additional profit by taking out the loan.
A2-3. The orange juice plant
(a) Decision variables: We are interested in the amount of source juice 1, 2, and 3 that we
need, as well as the amount of vitamin C that we want to blend in. Let us write X1, X2,
X3, and Z for these quantities (in litres). These quantities should all be nonnegative.
Objective function: The profit that our company makes is its income, from which we
subtract the total cost. The income is $10000, as the fast food chain buys 10000 litres
at a $1 per litre. The cost, on the other hand, depends on the variables defined above:
we pay 0.5X1 +0.1X2 +0.8X3 dollar for the source juices, and an additional CZ dollar
for the pure vitamin C (note that C is a parameter of the problem, and not a decision
variable!).
Therefore, the objective function is
10000− 0.5X1 − 0.1X2 − 0.8X3 − CZ,
and our goals is to maximize this function.
Constraints: We are required to produce 10000 litres of the final product, so we need
X1 +X2 +X3 + Z = 10000.
The final product is required to have at least 5% (by volume) of pulp; this is 500 litres.
The total amount of pulp in the mixed product is 0.06X1 + 0.06X2 + 0.03X3, which
should be at least 500.
0.06X1 + 0.06X2 + 0.03X3 ≥ 500.
8jJUrTR5xXP3Vw
The final product is required to have at least 0.03% (by volume) of vitamin C; this is 3
litres. The total amount of vitamin C in the mixed product is 0.0004X1 + 0.0002X2 +
0.0008X3 + Z, which should be at least 3, so
0.0004X1 + 0.0002X2 + 0.0008X3 + Z ≥ 3.
Similarly, the total amount of vitamin C in the mixed product should be at most 7
litres, so
0.0004X1 + 0.0002X2 + 0.0008X3 + Z ≤ 7.
Our complete Linear Program is
max − 0.5 X1 − 0.1 X2 − 0.8 X2 − C Z + 10000
s.t X1 + X2 + X3 + Z = 10000
0.06 X1 + 0.06 X2 + 0.03 X3 ≥ 500
4 X1 + 2 X2 + 8 X3 + 10000 Z ≥ 30000
4 X1 + 2 X2 + 8 X3 + 10000 Z ≤ 70000
X1 X2 X3 Z ≥ 0
(Here, we scaled both sides of the third and fourth constraint by 10000 for ease of
readibility.)
(b) For this part, we would like to use as objective function max{X1, X2, X3}, which is not
a linear function. We can work our way around this by introducing a new variable, B,
which behaves as the maximum.
To the formulation obtained in part (a), we add the additional constraints
X1 ≤ B, X2 ≤ B, X3 ≤ B,
and we replace the objective function by B.
In any optimal solution (X∗1 , X
∗
2 , X
∗
3 , Z
∗, B∗), we must have B∗ = max{X∗1 , X∗2 , X∗3}:
the inequality ≥ clearly holds because of the additional constraints, and if this inequal-
ity were strict, then a better solution would be (X∗1 , X
∗
2 , X
∗
3 , Z
∗,max{X∗1 , X∗2 , X∗3}),
contradicting optimality of B∗.
(c) We see that the profit linearly decreases as a function of C at first, and then becomes
constant.
When the price of vitamin C is very low (or zero), in order to fulfill the order, it suffices
to take the cheapest source juice (Source 2), which already has the right amount of pulp,
and then add vitamin C until the level of vitamin C is according to specification. Our
optimal solution is expected to be a certain combination of Source 2 juice and vitamin
C; the fraction of vitamin C does not depend on C, so the profit depends linearly on C
as long as C is small.
8jJUrTR5xXP3Vw
When the price of vitamin C is very high, it becomes more profitable to use one of the
higher-priced source juices to increase the level of vitamin C in the final product (in this
case, we would use Source 3, as the amount of vitamin C per dollar is highest). As the
optimal solution does not use any vitamin C anymore, the objective function becomes
constant when C reaches a certain level.