Reference no: EM133011220

Question 1: Cerlinde Kaltenbrunner wants to pack food for her next expedition, which is going to he three weeks long. She wants to pack n combination of foods A, B, C, D, E so that she has at least 5000 calories per day. and 50-65 % of those calories come as carbohydrates. 20-35 % as fat, and 15-20 % as proteins. The following table shows the calories as carbohydrates, fat and proteins per 1 kg of the different foods A, B, C, D, E. Write a linear program that will help her to decide how much of each food to pack in order to minimize the weight of the food that she is going to carry (You do not need to solve the linear program).

Question 2. (a) Draw the feasible region of the following system of linear constraints:

-4.r1 ? 0
211 + ra 5 7
- .r2 > -2
.r1 - 3.r5 < 0
-xi 4- 2.r2 < 4

(h) What are the vertices of the feasible region? For each vertex. list the two constraints that define that vertex.

(c) Which vertex maximizes the value of the function r -4 2r2? Now suppose that we wanted to find this vertex using the simplex algorithm starting from the vertex (.Q. .r2) = (0.0). In other words we start at (0.0) and each time we move to a neighbouring vertex that increases the value of ri 4- 2x2. List the two possible paths that the algorithm can take starting from (x/. x2) = (0.0) and finishing at the optimal vertex. For each path. explain how the linear constraints that define the vertices on the path change as we move from one vertex to the next vertex.

Question 3. Consider the following linear program.

max -3x1 - 2x2 - 7x3
s.t.   x1+x2 =5
        x1- x3 ≤3
       2x2 + 2x3 ≥ 4
           x2 ≤ 0

(a) Write the dual of the above linear program.

(b) Use solution (-2,5, -1) to the dual program to show that x1 = 5, x2 = 0, x3 = 2 is an optimal solution for the primal linear program. You are not allowed to use the weak or strong duality theorems: instead you have to deduce the correct upper bound by combining the constraints using the dual solution (as in the proof of the weak duality theorem).

Question 4. Given a flow network G(V, E), for every edge (u, v),
• l(u, v) is the lower bound on flow from node u to node v;
• c(a,v) is the upper bound on flow from node u to node v;
• c(u,v) is the expense for sending a unit of flow on (u. v).
Formulate a linear program and show that if it has an optimal solution, the optimal solution corresponds to a flow that satisfies lower bounds and upper bounds on all edges and minimizes the total expense. The total expense is the sum of expenses on all edges.

Question 5. (a) Write a linear program to solve the following problem: Given an undirected graph C as an input, we want to assign lasmcgative numbers to the edges of the graph so that the following two conditions hold simultaneously:
• For every vertex, the sum of the numbers on the edges incident to it is at most 1.
• The total sum of the numbers on all the edges is maximized.

(b) If we also require that the numbers assigned to edges are integers, then what does the above problem correspond to?

(c) Write the dual of the linear program from (a). If we again require that the deci¬sion variables in the dual program are integers. then what does the dual problem correspond to?

Question 6.Consider the following variant of the Rock-paper-sciasors game. Alice and Bob each can form one of the n shapes with an outstretched hand. There is an n x n matrix A = [aij]1≤i,j≤n that determines who wins the game. If Alice (onus the i-th shape and Bob forms the j-th shape, then the value of aij ∈ (0.1) tells us who wins (there are no ties): Here aij = I means Alice wins, and aij = 0 means Bob wins.

(a) Suppose that Alice has a strategy: She forms the 1-st shape with probability p1, the 2-1s1 shape with probability p2, etc. Obviously p1....Pn ∈ (0.1 and they add up to one. Bob also has a strategy according to which he forms the 1-st shape with probability the 2-nd shape with probability q2. etc. If they play according to these strategies, what is the formula for the probability that Alice wins?

(b) Alice wants to maximize the probability that she wins, and Bob wants to minimize the probability that Alice wins (thus maximize the probability that he wins). Consider now two scenarios: In the first scenario Alice chooses her strategy (i.e. pi's) first, and then announces it to Bob, and then Bob chooses his best strategy knowing Alice's strategy. In the second scenario first Bob chooses his strategy (i.e. q,'s) first and announces it to Alice. and then Alice chooses her best strategy knowing Bob's strategy. Use strong duality theorem to prove that in both scenarios Alice ends up with the same probability of winning (and consequently Bob too). In other words, prove that max min Pr(Alice wins) = min max PriAlice wins].