Due: Friday, February 3, 2012.

Let (P) be the standard form LP, min{c^Tx : Ax = b, x ≥ 0}. In class, we saw that if a problem of the form (P) has a feasible solution then it has a basic feasible solution. Construct a similar proof to show that if (P) has an optimal solution, it has a basic feasible solution that is optimal.
Assume it is known that the fractional linear program $cTx+g- min dTx+h subject to Ax ≥ b$
has an optimal value in the range [α,β]. In addition, assume that any x satisfying Ax ≥ b also satisfies d^Tx + h > 0. Develop a procedure that uses linear programming as a subroutine to find the optimal value of the fractional linear program, to within any desired tolerance. (Hint: Consider the problem of determining whether the optimal value is above or below a given threshold τ.)
What is the dual of the following linear programming problem? $min 3x1 - 5x2 + 8x3 s.t. x1 - x3 = 6 2x2 - x3 ≥ - 5 x1 + x2 ≤ 6 x2 ≤ 0, x3 ≥ 0.$
Use complementary slackness to show that x = (6,0,0) is optimal for this problem. Find two different dual optimal solutions.
Let A be a p × n matrix and B be a q × n matrix. Show that exactly one of the following systems has a solution:

System 1: Ax < 0, Bx = 0 for some x IRⁿ.
System 2: A^Tu + B^Tv = 0 for some u IR^p, v IR^q, with u ≥ 0 and u≠0.

John Mitchell

Amos Eaton 325

x6915.

Office hours: Tuesday 12noon – 2pm; Wednesday 2 – 4pm.