QBUS2310: Management Science
Assignment 1
Semester 2, 2021
This assignment consists of eight problems that require you to submit a written response and a coding
component.
(1) When a problem asks you to formulate you need to provide your mathematical formulation of
the LP with clear justification of variables, constraints and objective. You should submit your written
response as a PDF to GradeScope and match the page number with the questions that you answered.
You can find the detailed instructions on how to scan and submit your assignments on Canvas. If you
fail to match the page to the corresponding question, the marker will not be able to view your response
and thus you will be awarded 0 mark for the question.
(2) When a problem involves computation you must give the Python source code that produces
the result, the final numerical results and an interpretation of your numerical results. The Python code
and numerical results go into a Jupyter Notebook file Assignment1.ipynb. You should download the
file from Canvas and enter your code in the space provided. You should submit your code as a Jupyter
notebook file via Canvas. In addition, the final numerical results and your interpretation of the results
should appear in the PDF of your written response, described in (1).
Note: only problems 1 and 2 do not involve computation.
The assignment is due by Monday, the 20th of September, 5pm. Late assignments will not be
accepted unless a special consideration was granted.
The problems have unequal weight. Some are easy. Others, not so much.
i
QBUS2310 Assignment 1 Semester 2, 2021
1. (10 points) Formulate the following problem as LP: Given A ∈ Rm×n, b ∈ Rm,
minimize
m∑
i=1
max{0, aTi x+ bi}.
The variable is x ∈ Rn.
2. (10 points) Formulate the following problem as LP: Given p + 1 matrices A0, A1, . . . , Ap ∈ Rm×n,
find the vector x ∈ Rp that minimises
max
y : ∥y∥1=1
∥(A0 + x1A1 + · · ·+ xpAp)y∥1,
Hint: Note that the maximum is taken over all vectors y whose ℓ1 norm is equal to 1.
3. We consider an illumination system of m lamps, at positions l1, . . . , lm ∈ R2, illuminating n flat
patches.
(c) `∞-norm approximation: select α and β by minimizing
max
i=1,...,42
|yi − α− βti|.
Find the optimal values of α and β for each of the three optimization criteria. This yields
three linear func ions fls(t), f`1(t), f`∞(t). P ot the 42 data poi ts, and the hree functions
f . What do you observe?
Exercise 14. An illum nation problem. We consider an illum nation system of m a ps, at posi-
tions l1, . . . , lm ∈ R2, illuminating n flat patches.
lamp j lj
vi
vi+1
patch i
rij
θij
The patches are line segments; the ith patch is given by [vi, vi+1] where v1, . . . , vn+1 ∈ R2.
The variables in the problem are the lamp powers p1, . . . , pm, which can vary between 0
and 1.
The illumination at (the midpoint of) patch i is denoted Ii. We will use a simple model for
the illumination:
Ii =
m∑
j=1
aijpj , aij = r
−2
ij max{cos θij , 0}, (7)
where rij denotes the distance between lamp j and the midpoint of patch i, and θij denotes
the angle between the upward normal of patch i and the vector from the midpoint of patch
i to lamp j, as shown in the figure. This model takes into account “self-shading” (i.e., the
fact that a patch is illuminated only by lamps in the halfspace it faces) but not shading of
one patch caused by another. Of course we could use a more complex illumination model,
including shading and even reflections. This just changes the matrix relating the lamp powers
to the patch illumination levels.
The problem is to determine lamp powers that make the illumination levels close to a given
desired illumination level Ides, subject to the power limits 0 ≤ pi ≤ 1.
(a) Suppose we use the maximum deviation
φ(p) = max
k=1,...,n
|Ik − Ides|
as a measure for the deviation from the desired illumination level. Formulate the illu-
mination problem using this criterion as a linear programming problem.
(b) There are several suboptimal approaches based on weighted least-squares. We consider
two examples.
9
Figure 1: Illumination system
The patches are line segments; the i-th patch is given by [vi, vi+1] where v1, . . . , vn+1 ∈ R2. The
variables in the problem are the lamp powers p1, . . . , pm, which can vary between 0 and 1.
The illumination at (the midpoint of) patch i is denoted Ii. We will use a simple model for the
illumination:
Ii =
m∑
j=1
aijpj , aij = r
−2
ij max{cos θij , 0}, (1)
where rij denotes the distance between lamp j and the midpoint of patch i, and θij denotes the
angle between the upward normal of patch i and the vector from the midpoint of patch i to lamp j,
as shown in the figure. This model takes into account “self-shading” (i.e., the fact that a patch is
illuminated only by lamps in the halfspace it faces) but not shading of one patch caused by another.
Of course we could use a more complex illumination model, including shading and even reflections.
This just changes the matrix relating the lamp powers to the patch illumination levels.
The problem is to deter i powers that make the illumination leve s clo e t a given desired
illumination level Ides, subject to the power limits 0 ≤ pi ≤ 1.
(a) (8 points) Suppose we use the maximum deviation
ϕ(p) = max
k=1,...,n
|Ik − Ides|
as a measure for the deviation from the desired illumination level. Formulate the illumination
problem sing this crit rion as a linear programming problem.
(b) There are several suboptimal approaches based on weighted least-squares. We consider two
examples.
Page 1 of 4.
QBUS2310 Assignment 1 Semester 2, 2021
i. (2 points) Saturated least-squares. We can solve the least-squares problem
minimize
n∑
k=1
(Ik − Ides)2
ignoring the constraints. If the solution is not feasible, we saturate it, i.e., set pj := 0 if
pj ≤ 0 and pj := 1 if pj ≥ 1.
Download the Jupyter Notebook file Assignment1.ipynb from the unit Canvas site with
the problem data. (The elements of A are the coefficients aij in (1).) Compute a feasible p
using this first method, and calculate ϕ(p).
ii. (6 points) Weighted least-squares. We consider another least-squares problem:
minimize
n∑
k=1
(Ik − Ides)2 + µ
m∑
i=1
(pi − 0.5)2,
where µ ≥ 0 is used to attach a cost to a deviation of the powers from the value 0.5, which
lies in the middle of the power limits. For large enough µ, the solution of this problem will
satisfy 0 ≤ pi ≤ 1, i.e., be feasible for the original problem. Explain how you solve this
problem in Python. For the problem data provided in Assignment.ipynb, find the smallest
µ such that p becomes feasible, and calculate ϕ(p).
(c) (4 points) Using the same data as in part (b), solve the LP you derived in part (a). Compare
the solution with the solutions you obtained using the (weighted) least-squares methods of part
(b). Explain the differences in values of ϕ(p).
4. (10 points) Coolbike Industries manufactures boys and girls bicycles in both 20-inch and 26-inch
models. Each week it must produce at least 200 girl models and 200 boys models. The following
table gives the unit profit and the amount of time (in minutes) required for production and assembly
for each model. The production and assembly areas run two (eight-hour) shifts per day, five days per
Bicycle Unit profit Production (minutes) Assembly (minutes)
20-inch girls $27 12 6
20-inch boys $32 12 9
26-inch girls $38 9 12
26-inch boys $51 9 18
Table 1: Bicycle manufacturing data
week. This week there are 500 tires available for 20-inch models and 800 tires available for 26-inch
models. Formulate an LP and determine Coolbike’s optimal schedule for the week. What profit will
it realise for the week?
5. (10 points) One of the current diets that seems to produce substantial weight loss in some persons
is the high protein/low carbohydrate diet advocated by such authors as Atkins in his book, Diet
Revolution, and Eades and Eades in their book, Protein Power. Although many nutritionists are
concerned about the side effects of these diets, others feel the potential risks are outweighed (no pun
intended) by the weight loss.
The following table gives the grams of fat, carbohydrates, and protein as well as the calorie count
in four potential foods: steak (8 oz. portion), cheese (1 oz.), apples (1 medium), and whole milk (8
oz.). Jim Blount, a 45-year-old male, has done the calculations suggested in these books and has
determined that he should have a calorie intake of between 1800 and 2000 calories and protein intake
of at least 100 grams, but he should not consume more than 45 grams of carbohydrates daily. For
breakfast Jim had two eggs and three strips of bacon, one piece of buttered high protein toast, and
water. This breakfast contained 390 calories, 15 grams of carbohydrates, 20 grams of protein, and
29 grams of fat. Although these diets do not limit fat intake, Jim wishes to minimise his total fat
Page 2 of 4.
QBUS2310 Assignment 1 Semester 2, 2021
Calories Fat (grams) Protein (grams) Carbohydrates (grams)
Steak (8 oz.) 692 51 57 0
Cheese (1 oz.) 110 9 6 1
Apple 81 1 1 22
Milk 150 8 8 12
Table 2: Diet problem data
consumed by constructing a diet for lunch and dinner consisting of only the four foods listed in the
table. Formulate and solve an LP in order to recommend a diet.
6. (10 points) Gladstone and Associates is conducting a survey of 2000 investors for the financial ad-
vising firm of William and Ryde to determine satisfaction with their services. The investors are to
be divided into four groups:
• Group I: Large investors with William and Ryde
• Group II: Small investors with William and Ryde
• Group III: Large investors with other firms
• Group IV: Small investors with other firms
The groups are further subdivided into those that will be contacted by telephone and those that will
be visited in person. Due to the different times involved in soliciting information from the various
groups, the estimated cost of taking a survey depends on the group and method of survey collection.
These are detailed in the following table.
Group Telephone Personal
I $15 $35
II $12 $30
III $20 $50
IV $18 $40
Table 3: Survey costs
Formulate an LP to determine the number of investors that should be surveyed from each group by
telephone and in person to minimise Gladstone and Associates’ overall total estimated cost if:
• At least half of those surveyed invest with William and Ryde.
• At least one-fourth are surveyed in person.
• At least one-half of the large William and Ryde investors surveyed are contacted in person.
• At most 40% of those surveyed are small investors.
• At least 10% and no more than 50% of the investors surveyed are from each group.
• At most 25% of the small investors surveyed are contacted in person.
7. (10 points) Delta Venture Capital Group is considering whether to invest in Maytime Products, a
new company that is planning to compete in the small kitchen appliance market. Maytime has three
products in the design and test phase:
• a unique refrigerator/oven that can be programmed in the morning to cook food (like chicken)
but keeps the food refrigerated until the cooking process begins;
• a French fry maker that can make long thick French fries or small thin shoestring fries;
• a French toast maker that cooks French toast of any size evenly on the top and bottom simul-
taneously.
Page 3 of 4.
QBUS2310 Assignment 1 Semester 2, 2021
Delta’s primary concern is how much money it must invest with Maytime before it will show a profit.
The company will need an immediate initial investment of $2, 000, 000 to secure a plant and cover
overhead costs. This investment must be paid back with initial profits. The following table gives
the anticipated selling price, the variable cost per unit manufactured, and the initial demand for
each product obtained through market research. Delta would have to commit to the $2, 000, 000 and
then would like to minimise its total variable cost outlay until Maytime turns a profit (i.e., until
Maytime can cover the initial $2, 000, 000 investment with profits (=selling price - variable cost)
from its sales.) Maytime will initially produce no more than 15,000 units of any of the items but will
Product Selling price ($) Variable cost ($) Initial demand
Refrigerator/Oven 240 140 5000
French Fry Maker 85 50 4000
French Toast Maker 63 36 2300
Table 4: Maytime Products data
meet anticipated initial demand. Formulate an LP and determine what production quantities for
the products will minimise the total variable cost of the items produced while attaining a “profit”
of $2, 000, 000.
8. (10 points) California Oil Company (Caloco) produces two grades of unleaded gasoline (regular and
premium) from three raw crudes (Pacific, Gulf, and Middle East). The current octane rating, the
availability (in barrels), and the cost per barrel for a given production period are given in the following
table. For this period, Caloco has contracts calling for a minimum of 200,000 gallons of regular and
Crude Octane Availability (barrels) Cost ($/barrel)
Pacific 85 3000 14.28
Gulf 87 2000 15.12
Middle East 95 8000 19.74
Table 5: Caloco data
100,000 gallons of premium gasoline, and it has a refining capacity of 400,000 total gallons. (A barrel
is 42 gallons.) Caloco sells regular gasoline to retailers for $0.52 and premium gasoline for $0.60 per
gallon.
To be classified as “regular,” the refined gas must have an octane rating of 87 or more; premium
must have an octane rating of 91 or more. Assume that the octane rating of any mixture is the
weighted octane rating of its components.
Formulate an LP and solve for the optimal amount of each crude to blend into each gasoline during
this production period.
Page 4 of 4.

欢迎咨询51作业君