Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MATH5171 Assignment

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.

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).

The costs of installing a new cameras at the possible locations 1 − 49 are listed in the following table 1:

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

where e = (1, . . . , 1)^T ∈ Rⁿ and γ > 0. Here, r = (r1, . . . , rn)^T ∈ Rⁿ 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 given by

Here, is the Euclidean norm,  ∈ Rⁿ 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

where

Reformulate the problem (RM) as a conic linear program. Provide explanations for the reformulations. [Hint: You may use the fact that for all a ∈ Rⁿ. If you did use this fact, provide justification of it as well.]