## 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