QBUS2310: Management Science
Assignment 1
Due: Tuesday, 10th September 2024 Total marks:100
1. (a) (5’) Reformulate the following problem
min 2x1 + 3|x2 − 10|
s.t. |x1 + 2|+ |x2| ≤ 5
x1, x2 ∈ R
into a linear optimisation problem (LOP).
(b) (5’) If the “minimization” above is changed to “maximization”, can you refor-
mulate the problem into an LOP? Why?
2. (15’) BA Pte Ltd produces shoes and is opening a new franchise in City. The
company needs to hire workers. Assume each worker can only produce 50 pairs of
shoes per quarter, is paid $500 per quarter, and works three consecutive quarters
per year. The demand (in pairs of shoes) is 600 for the first quarter, 300 for the
second quarter, 800 for the third quarter, and 100 for the fourth quarter. Excessive
pairs of shoes may be carried over to the next quarter at a cost of $50 per quarter
per pair of shoes, and there will be no inventory at the end of quarter 4.
(a) (10’) Please formulate an LOP to minimize BA Pte Ltd’s long run average
costs.
(b) (5’) See the coding part.
3. (20’) Toyz is a discount toy store in Qbusfield Mall. During the winter and spring,
the store must build up its inventory to have enough stock for the Christmas season.
To purchase and build up its stock during the months when the revenue is low, the
store borrows money from a bank.
Following is the store’s projected revenue (revenue of last month) and liabilities (bills
of the coming month) schedule for July through December. For example, $20, 000
for July is the realized revenue from June and $50, 000 is the bill needed to pay in
July.
1
Month Projected Revenues ($) Liabilities ($)
July 20,000 50,000
August 30,000 60,000
September 40,000 50,000
October 50,000 60,000
November 80,000 50,000
December 100,000 30,000
At beginning of July, the store can take out a 6-month loan at 12% interest rate and
must be paid back at the beginning of next January. The store can not pay back
this loan early. The store can also borrow monthly loan at a rate of 4% interest per
month. The store wants to borrow enough money to meet its cash flow needs while
minimizing its interest cost.
(a) (10’) Formulate the LOP for this problem.
(b) (10’) See the coding part.
4. (15’) Consider the following optimization problem
max
500∑
i=1
cixi
s.t.
500∑
i=1
xi = 30
0 ≤ xi ≤ 1, i = 1, . . . , 500,
for some given parameters, c1, . . . , c500.
(a) (5’) Characterize the extreme points of the problem.
(b) (5’) What is the number of extreme points? Suppose a computer can explore
100 billion extreme points per second. How long would it take to explore all
the extreme points (in number of years)? Compare this with the age of the
universe, which is roughly 13.8 billions years.
(c) (5’) How to interpret the optimal objective value of this problem? What is the
optimal solution of this problem?
2
5. (25’) Consider the following optimization problem:
max x1 + x2 + x3
s.t. x1 + 2x2 + 2x3 ≤ 15
2x1 + x2 + 2x3 ≤ 15
2x1 + 2x2 + x3 ≤ 15
x1, x2, x3 ≥ 0.
(a) (10’) Write down the dual problem.
(b) (10’) Show that the optimal solution is x1 = x2 = x3 = 3.
(c) (5’) What are the shadow prices (dual variables) associated with the first three
constraints?
6. (15’) Consider a two-person zero-sum game with the following payoff matrix (of the
row player)
A =
 5 0 3 12 4 3 2
3 2 0 4
 .
(a) (10’) Formulate the LOPs to find optimal mixed strategies for the row player
and the column player, respectively.
(b) (5’) See the coding part.