MATH5171 Assignment
Due date: 5 pm Sydney time on 20/November/2021 (Saturday)
Information of this Assignment
Your answers to this assignment must be submitted via Moodle before 5 pm Sydney time
on 20/November/2021.
Late submission for Assignment: A late penalty of 5% of the awarded mark will be applied
per day or part day any assignment is submitted more than 1 hour late. (Here, “late” in this
context means after any extensions granted for Special Consideration or Equitable Learning
Provisions.) Any assignment submitted 3 or more days late will be given zero.
Assignments must include a signed cover sheet (the school stamp is not needed) available
from the School of Mathematics and Statistics web site at :
http://www.maths.unsw.edu.au/sites/default/files/assignment.pdf
Marking of this Assignment
A full mark of 30 on this assignment is worth 10% of the total marks for MATH5171.
• For Questions 1 and 2, present your work as a self contained, well-written report
including the problem statement, solution summary, model formulation, definition of
problem variables and your computer output. State clearly the assumptions that you
make. Any Matlab files that you used to solve the assignment problems should be
either included in the appendix or submitted to Moodel.
• For Question 3, state clearly how you obtain the conic program reformulations, and
give reasons for all statements that you make.
1. Transportation problem (6 marks)
The company powerco has three electric power plants that supply the needs of four
cities. Each power plant can supply the following number of kilowatt-hours (kwh) of
electricity: power plant I – 30 million; power plant II – 55 million; power plant III –
40 million. The costs of sending 1 million kwh of electricity from plants to cities are
summarized in Table 1. The peak power demands in these cities are as follows (in
kwh): city I – 40 million; city II – 25 million; city III – 30 million; city IV – 30 million.
The company wish to minimize the total cost of sending the electricity from the three
electric power plants to the four cities, and to meet each city’s peak power demand.
1
City I City II City III City IV
Power Plant I $4 $3 $10 $12
Power Plant II $9 $6 $13 $7
Power Plant III $12 $9 $16 $6
Table 1: Costs of sending 1 million kwh of electricity from plants to cities
Formulate this as a linear programming problem and solve it using Matlab. Find out
an optimal solution, the associated minimal cost and interpret your results. Either
provide the Matlab code in the Appendix or submit the Matlab file to Moodle.
2. CCTV Surveillance Problem (14 marks)
During the past few months, the suburb Surrey has suffered from a series of break-ins
and thefts during the night. The city council of Surrey decides to install surveillance
cameras in this suburb to improve the security. These cameras can be directed and
pivot through 360◦. By installing a camera at the intersection of several streets, it is
possible to survey all adjoining streets. The map in the following Figure shows the
streets need to be covered by the closed circuit TV (CCTV) surveillance and the 49
possible locations where to install the cameras. Here, we interpret a street as the
arc in the map linking two possible locations of the cameras without having a third
possible location of the cameras in between (for example, the arc between location 22
to location 25 is one street, while the arc between location 25 to location 26 is another
street).
2
The costs of installing a new cameras at the possible locations 1− 49 are listed in the
following table 1:
Location Cost (1 new camera+installation fees)
Location 13 $ 1200
Location 41 $ 1200
other locations $ 800
The city council would like to minimize the total cost of installing cameras and make
sure every street can be surveyed by at least one camera.
(a) Formulate this CCTV surveillance problem as an integer programming problem
and solve it using Matlab. Find out where these cameras should be placed and
what are the corresponding total cost.
(b) Provide a report explaining the model and the results you obtain in part (a), to
the Mayor of the city council. Discuss the model and the associated assumptions
of the model in the report. Either provide the Matlab code in the Appendix of
the report or submit the Matlab file to Moodle together with the report.
3. Robust Markowitz portfolio optimization problem (10 marks)
The classical Markowitz portfolio optimization problem can be formulated as
(M) Maximize
x∈Rn r
Tx
subject to xTΣx ≤ γ
eTx = 1
x ≥ 0,
where e = (1, . . . , 1)T ∈ Rn and γ > 0. Here, r = (r1, . . . , rn)T ∈ Rn where each ri is
the expected return on investment i and Σ is the covariance matrix (and so, is positive
semidefinite). In practice, the data r is uncertain due to prediction/estimation error.
We assume that r belongs to an uncertainty set U given by
U = {r ∈ Rn : ‖r− r‖2 ≤ ρ}.
Here, ‖ · ‖2 is the Euclidean norm, r ∈ Rn is a given nominal return vector and ρ > 0
is a given constant scalar. The robust optimization approach then aims at finding the
worst case solution of problem (M), that is, solving the following robust optimization
problem
(RM) Maximize f(x)
subject to xTΣx ≤ γ
eTx = 1
x ≥ 0,
1The locations 13 and 41 link with two main roads connecting Surrey with other suburbs. Therefore,
higher quality of cameras are needed for these two locations.
3
where
f(x) = min{rTx : r ∈ U}.
Reformulate the problem (RM) as a conic linear program. Provide explanations for
the reformulations. [Hint: You may use the fact that min‖x‖2≤ρ a
Tx = −ρ‖a‖2 for all
a ∈ Rn. If you did use this fact, provide justification of it as well.]
4
学霸联盟