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


IB2070

2020

Mathematical Programming II

 

[Question 1]

(a)   Show briefly that, in a directed acyclic graph, the nodes can be numbered in such a way that an

arc from node  to node  implies that  <  . (Hint: What special property will the node numbered 1 have? Then continue by induction.)

(b)   For the following directed acyclic network, number the nodes as described in part (a) above (e.g.,

~1) and apply the dynamic programming algorithm given in the lectures to find a shortest path from node  to node  . Provide all the details of every step.

 

(c)  VIA Travel Agency plans to organize six tours in three different countries C1, C2 and C3. They plan

to have at least one tour in C1 and at least one in C3. The travel agency would like to maximize the total benefit.  Depending on the  number of tours organized in a country, the  benefit can change. The agency measures the benefit on a 10-point scale and prepares the following table:

(15 marks)Solve the problem by using dynamic programming (DP). Explain the stages and the states in your DP model, as well as the decisions to  be made at each stage.  In addition, formulate the  DP function at each stage and construct the DP tables.

 

[Question 2]

ABC Company is considering four potential car stores for reaching five target regions. The following table provides the fixed preparation costs at each of the car stores and profit made by servicing one unit of product from each car store to each target region. The last row shows the demand in each region and partial supply is possible. In other words, the company does not need to satisfy all of the demand in a region. The capacities of the car stores 1, 2, 3 and 4 are 1000, 700,  1000 and 1200, respectively.

 

(a)  ABC Company wishes to maximize its profit in determining which stores to open and how to serveABC Company would like to open at most three stores. In addition, demand of a region can be served by only one car store.

the regions from each operated car store. Formulate the problem as an integer programming model. Explain the decision variables and the constraints.

(b)  Reformulate the problem with the following additional condition. If both regions 1 and 2 are

serviced by store 1, then the unit transportation profit from store 1 to regions 1 and 2 increases from 100 and 80 to 110 and 90, respectively.

  

[Question 3]

A road network connecting nine small villages is depicted below. The lengths of edges in the network correspond to the distances in kilometres.

(a)   A local council is planning to build a fire station in one of the villages. Time needed to reach a

village from the fire station in case of an accident should be as small as possible. Without doing any calculations but just by examining the graph, advise the council on where to build the station, assuming   that   the   travel   time   is   proportional   to   the   distance   travelled.   Explain   your recommendation.

(b)   Formulate the algorithm you  used to answer question  (a)  in a general form  (i.e., for such a

problem instead of a particular instance such as (a) above).

(c)   Ignore (a) and (b).  The council plans to connect all villages (directly or indirectly) by a new multi- channel telephone cable. Calculate the minimum  length of the cable  needed to connect the villages.