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


IB2070

2019

Mathematical Programming II


Question 1

Julia is considering 3 investment options as shown in Table 1. She should choose an investment level for each alternative (investments 1, 2 and 3) ranging from £0 to £20k. The invested amount for each option must be an exact multiple of £10k. Table 1 provides the annual returns from these investment options. For example, if Julia invests £20k in investment option 2, she will receive £21k at the end of the year and she will make £lk of profit from this option.

Table 1. Annual returns for investment opportunities


 

Currently, Julia does not have any available cash for this investment. However, she has £45k in a savings account and she is considering to withdraw her money by paying a penalty. She can either withdraw the full amount of £45k or £33k. If she withdraws all of her money (£45k), she has to pay £5k as a penalty to the bank. If she withdraws £33k, she has to pay £3k as a penalty to the bank. In both of these cases, she is not going to obtain any interest on the savings account.

(a) [80%] Julia wants to maximize her total profit obtained from these investment options. Solve the problem by using dynamic programming. Explain the stages and the states in your dynamic programming model, as well as the decisions to be made at each stage. In addition, formulate the dynamic programming function at each stage and construct the DP tables.

(b) [20%] Julia wants to explore the following option. Assume that she withdraws £33k from her bank account and after paying the £3k penalty, she decides to invest £20k in the investment option 1. What would be the optimal investment decisions on options 2 and 3? By using dynamic programming tables obtained in Part (a), find the optimal investment decisions for the remaining options.


Question 2

The University of Warwick plans to install a network to connect four new departments to the Computing Centre. The network diagram below shows all the possible ways of installing the network links. The number associated with each link represents the distance between the buildings. A missing link between two nodes implies that it is prohibitively expensive or physically impossible to connect the associated buildings.

 

  

(a) [10%] Project A proposes connections of all buildings, directly or indirectly, by a cable. What would be such a connection system of minimum total cable length? What is the minimum cable length?

(b) [40%] Project B suggests connections of all buildings by a coaxial cable system. In this case a separate cable must be laid from the Computing Centre to each of the four department buildings. Each of these separate cables may passthrough some other departments, for example, the cable to department 2 may pass through department 1. However, no departments may use another departments cable. What would be such a connection system of minimum total cable length? What is the minimum cable length?

(c) [50%] If all the link lengths in the network are: (i) doubled or (ii) increased by 1, then will your solution of optimal connection system in each of parts (a) and (b) above change in each of cases

(i) and (ii)? For each case, if your answer is "yes”,then provide the new solution. If your answer is "no”, then prove your answer for any general network.

Provide all the details of your working for all the three parts above. Full credits will not be obtained without full details.


Question 3

(a) [40%] Sheriff Bassam is up for re-election in Washington County. The funds available for the campaign are about $10,000. Although the re-election committee would like to launch the campaign in all five precincts of the county, limited funds dictate otherwise. The table given below lists the voting population and the amount of funds needed to launch an effective campaign in each precinct. A precinct can receive either all its allotted funds or none. Provide an optimization model to decide on how the funds should be allocated.


 

(b) The branch-and-bound algorithm has been used to solve the problem formulated in (a). Part of the corresponding branch-and-bound tree is presented below. The circled numbers are the values of the objective functions for the relaxation of the corresponding linear programming (LP) problems, and the vectors of five numbers are the corresponding LP solutions. Analyze the information presented in the tree and explain the following:

(1) [20%] Has a feasible or even an optimal solution been already found?

(2) [20%] What is the most precise interval containing the optimal value of the objective function?

(3) [20%] What is the possible maximal number of calls to Solver that is needed to accomplish the construction of the full branch-and-bound tree?