Business Management
1.
(a) (2+2 = 4 pts) Find the value of the objective function and verify that the constrains are satisfied when 1. x1=O,x2=1,x3=1 = 0, X2 = 0, X3 = 1 State an assignment which optimises the objective function.
Solution. Let OPT(j, R) represent the smallest capacity of the knapsack to earn a total revenue of exactly R when selecting from objects from 1 to j. Let Vj represent value of the jth object and Wj the weight of the jth object. So now let us suppose we know all answers till j-1. Now for finding answer for j,R we have two choices-Do not take the jth object. In this case answer is same as answer of j- I,R Take the jth object. Now the answer will be Wj more than the ans for R-Vj since we want R as the revenue after taking this object of value Vj. Also note that if R l Vj we cannot take this object. So here is the final recurrence So if R i= Vj OPTU, R) = min(OPT(j – I, R), OPT(j – I, R – Vj) + Wj) otherwise if R i Vj OPTa R) = OPT(j – I, R) and OPT(l, 0) = 0 for all j = 0 to n. This is beacuse 0 value requires 0 capacity. and OPT(0, R) = infinite for all R i 0. This is because without selecting any element it’s impos-sible to generate a non 0 revenue. For practical purposes we will take infinite as a very large number like INTA, AXincpp.
2
(b) (2 + 2 + 2 = 6 pts) Now we formulate the TSP (covered in lecture) as a ILP problem. A salesman wishes to visit each of n — 1 other cities and return home at a minimal cost (there are n cities in total). He must visit each city exactly once and it costs cii to travel from city i to city j. You have to determine the most efficient (the least expensive) route. Assume that each city is connected to every other city. The constraints require that the salesman must enter and leave each city exactly once. To model this problem as an ILP instance, we introduce the following decision variables.
1 if the salesman goes from city i to city j and i j xid = _ 110 otherwise
i. What is being optimised in this problem? State the objective function. Solution. ii. State two constraints to enforce that the salesman enters and leaves each city exactly once. Solution. iii. Are these constraints sufficient to specify TSP as an ILP problem? Explain your answer with an example where the number of cities, n = 6. Solution.
