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作业君