Name:

MATP6640/DSES6770
Linear Programming
Spring 2008

Midterm Exam, Thursday, April 3, 2008.

Please do all three problems. Show all work. No books or calculators allowed. You may use any result from class, the homeworks, or the texts, except where stated. You may use one sheet of handwritten notes. The exam lasts 110 minutes.

 Q1 /40 Q2 /30 Q3 /30 Total /100

Throughout, the standard primal-dual LP pair is

where A is m × n and the vectors are dimensioned appropriately.

1. (40 points)
1. (20 points) Use complementary slackness to show that y = (10, 5) solves the linear program

(Hint: 2.5 × 10 + 4.33 × 5 = 46.65.)

2. (20 points) The problem in part (1a) is a relaxation of the true problem,

Show that y = (10, 5) is not feasible in the true problem. Give a valid linear constraint that is violated by y = (10, 5) and that could be added to (D4).

2. (30 points)
Two systems of equations are:
where e is the n-vector of ones and t is a scalar.
1. (10 points) Show that exactly one of the two systems has a solution.
2. (10 points) Assume (P) and (D) are both feasible. Show that if (I) is consistent then (P) has an unbounded set of optimal solutions.
3. (10 points) Assume (D) is feasible. Show that if (II) is consistent then (D) has a strictly feasible solution.