CS69011-Assignment 4 Solved

Task 1 

Consider that an army has located its units in 𝑛 locations and has to supply soldiers to 𝑚 battlegrounds. The cost of supplying one soldier to from unit 𝑖 to battleground 𝑗, is 𝑐&’. Also, there is a demand of at least 𝑑’ soldiers in battleground 𝑗, and there is an upper bound of 𝑢& on the total number of soldiers who can be accommodated at unit location 𝑖. The task is to find the optimal fraction of demand for soldiers 𝑑’ to be met by the unit location 𝑖, denoted as 𝑥&’. This can be obtained by solving the linear program:

                                                                       ./0 𝑥&’             

& 

                                                                          𝑠𝑢𝑏. 𝑡𝑜. 1          𝑑’𝑥&’  , … , 𝑛             

’45

6

                                                                          1         𝑥&’  , … , 𝑚   

&45

𝑥&’ ∈ [0,1]                                           ∀𝑖, 𝑗

Here, the objective function measures total cost of transporting all soldiers. Note that, 𝑑’ ∗ 𝑥&’ are the number of soldiers supplied from location 𝑖 to battleground 𝑗. The first set of constraints ensures that not more than 𝑢& soldiers are supplied from location 𝑖, and the second set of constraints ensure that at least 𝑑’ soldiers are supplied to battleground 𝑗.

 

Input: 

The input file format is:

<value of n <value of m 

<vector of 𝑢& (n numbers in one line) <vector of 𝑑’ (m numbers in one line) 

<first row of cost matrix 𝑐&’ (m numbers in one line) 

… 

<last (nth) row of cost matrix 𝑐&’ (m numbers in one line) 

 

Output: 

Print input data: values of n and m, u vector, d vector, and c matrix.

Print the matrix of optimal allocation of soldiers from unit location I to battleground j: 𝑑’ ∗ 𝑥&’

 

 

Task 2: 

Consider the problem of locating army units in at most 𝑛 locations (facility points) for servicing the needs of 𝑚battle grounds (demand points). Each facility point 𝑖 has a cost of 𝑐&’ of supplying the demand point 𝑗, this could be the cost of transporting one soldier to from unit location 𝑖 to battleground 𝑗. Each battleground 𝑗 has a demand for 𝑑’ soldiers, assumed to be known. Moreover, each facility 𝑖 has an initial fixed cost of 𝑓& of setting up, and an upper bound 𝑢& on the demand for number of soldiers which can be accommodated. Let us say we want to open 𝑘 of the 𝑛 facilities. The problem is to find out the optimal fraction 𝑥&’ of the soldiers 𝑑’ which will be supplied by facility location 𝑖 to battleground 𝑗. Additionally, we must find out which of the 𝑛 locations should be used to set up unit facilities, maximum number of them being 𝑘. This can be solved using a mixed integer linear programming problem. Let 𝑦& be a binary integer variable denoting whether facility location 𝑖 should be opened (𝑦& = 1) or not (𝑦& = 0). The optimization problem becomes:

                                                                                 6       3                                                 6

                                                                    min./0      1 1 𝑐&’ ∗ 𝑑’ ∗ 𝑥&’ + 1 𝑓& ∗ 𝑦&           

                                                                                &                                     &45

                                                                        𝑠𝑢𝑏. 𝑡𝑜. 1                        𝑑’𝑥&’ ≤ 𝑢&𝑦&                                                                                                                                            ∀𝑖 = 1, … , 𝑛          

’45

  𝑥&’  , … , 𝑚            

1 𝑦& ≤ k   

&45

𝑥&’ ∈ [0,1]                                             ∀𝑖, 𝑗       

𝑦& 𝑖

 

 Here, the objective function measures total cost of transporting all soldiers (first term) and the total setup cost of all open facilities (second term). Note that, 𝑑’ ∗ 𝑥&’ are the number of soldiers supplied from location 𝑖 to battleground 𝑗. If location 𝑖 is not open (𝑦& = 0) the upper bound is 0, otherwise it is 𝑢&. The first set of constraints ensures that not more than 𝑢& soldiers are supplied from location 𝑖, and the second set of constraints ensure that at least 𝑑’ soldiers are supplied to battleground 𝑗. Here, 𝑦& are integral binary variables.

 

Input: 

The input file format is:

<value of n <value of m 

<vector of 𝑢& (n numbers in one line) 

<vector of 𝑓& (n numbers in one line) 

<vector of 𝑑’ (m numbers in one line) 

<first row of cost matrix 𝑐&’ (m numbers in one line) 

… 

<last (nth) row of cost matrix 𝑐&’ (m numbers in one line) 

 

Output: 

Print input data: values of n and m, u vector, f vector, d vector, and c matrix.

Print the list of opened facilities: y vector.

Print the matrix of optimal allocation of soldiers from unit location I to battleground j: 𝑑’ ∗ 𝑥&’