Description
Problem 1 (20pts). Consider the following linear program:
maximize 3×1 + x2 + 4×3
subject to x1 + 3×2 + x3 ≤ 5
x1 + 2×2 + 2×3 ≤ 8
x1, x2, x3 ≥ 0
(a). What is the corresponding dual problem?
(b). Solve the dual problem graphically.
(c). Use complementarity conditions for the primal-dual pair to solve the primal problem.
Problem 2 (25pts). Consider the following table of food and corresponding nutritional values:
Protein, g Carbohydrates, g Calories Cost
Bread 4 7 130 3
Milk 6 10 120 4
Fish 20 0 150 8
Potato 1 30 70 2
The ideal intake for an adult is at least 30 grams of protein, 40 grams of carbohydrates, and 400
calories per day. The problem is to find the least costly way to achieve those amounts of nutrition
by using the four types of food shown in the table.
1
(a). Formulate this problem as a linear optimization problem (specify the meaning of each decision
variable and constraint).
(b). Solve it using MATLAB, find an optimal solution and the optimal value.
(c). Formulate the dual problem. Interpret the dual problem. (Hint: Suppose a pharmaceutical
company produces each of the nutrients in pill form and sells them each for a certain price.)
(d). Use MATLAB to solve the dual problem. Find an optimal solution and the optimal value.
Problem 3 (25pts).
Consider the max flow problem on the graph in figure 1 with the orange
node being the source node and the green node being the terminal node (the number on each edge
is its capacity, see the lecture slide 13). Do the following based on the lecture slides.
Figure 1: Max flow problem
(a). Formulate it as a linear program and solve it using MATLAB.
(b). Formulate the dual of this problem and solve it using MATLAB.
(c). Find the corresponding maximum flow and minimum cut of the graph.(Please draw the cut
on figure 1).
Problem 4 (15pts).
Use linear program duality to show that exactly one of the following systems
has a solution
1. Ax ≤ b
2. y
T A = 0, b
T y < 0, y ≥ 0
2
Hint: You can first show that they can’t both have solutions. Then you show that if the second
one is infeasible, the first one must be feasible.
Problem 5 (15pts).
Suppose M is a square matrix such that M = −MT
, for example,
M =
0 1 2
−1 0 −4
−2 4 0
Consider the following optimization problem:
minimize x cTx
subject to Mx ≥ −c
x ≥ 0
(a). Show that the dual problem of it is equivalent to the primal problem.
(b). Argue that the problem has optimal solution if and only if there is a feasible solution.
3
