Math 484.1  October 23, 2003.   Name:______L. Vaserstein__________________________

Midterm 2,  5 problems, 15 points each.

Solve linear programs where all  xi >= 0:

1.
 -2 x2 3 -x3 1 2 3 4 = x1 5 6 7 8 = x4 0 1 2 3 -> min

combine two columns with constants on top  together  and multiply a column by -1.
standard  feasible tableau:
 x2 x3 1 2 -4 7 = x1 6 -8* 11 = x4 1 -3 6 -> min
pivot step according to Phase 2 of simplex method
 x2 x4 1 -1* 1/2 3/2 = x1 3/4 -1/8 11/8 = x3 -5/4 3/8 15/8 -> min
pivot step according to Phase 2 of simplex method
 x1 x4 1 -1 1/2 3/2 = x2 -3/4 1/4 5/2 = x3 5/4 -1/4 0 -> min
The x4-column is bad, so the program is unbounded.

2.
 -2 x2 3 -x1 1 2 3 4 = x1 5 6 7 8 = x4 0 1 2 3 -> min

combine two columns with constants on top  together
 x2 -x1 1 2* 4 7 = x1 6 8 11 = x4 1 3 6 -> min
pivot step
 x1 -x1 1 1/2 -2 -7/2 = x2 3 -4 -10 = x4 1/2 1 5/2 -> min
combine the first two columns.  standard tableau:

 x1 1 5/2 -7/2 = x2 7 -10 = x4 -1/2 5/2 -> min
x1-column is bad,. As x1-> infinity, the objective function  -> -infinity,    while   x2 and  x4 become positive.
The program is unbounded.

3.
 -2 x2 3 -x3 1 2 3 4 = x1 5 6 7 8 = x1 0 1 2 3 -> max

combine two columns with constants on top  together  and multiply a column by -1.
 x2 x3 1 2 -4 7 = x1 6 -8 11 = x1 1 -3 6 -> max
subtract the first row from the second row and multiply the third row by -1
 x2 x3 1 2 -4 7 = x1 4 -4* 4 = 0 -1 3 -6 -> min
pivot on -4 and drop the second column to obtain standard tableau
 x2 1 -2 3 = x1 1 1 =x3 2 -3 -> min
This is an optimal tableau, so min = -3  at  x1 = 3, x2 = 0, x3= 1. For the origional maximization program,
max = 3  at  x1 = 3, x2 = 0, x3= 1. (The optimal solution is unique.)

4.
 x3 x2 3 -x3 1 2 3 4 = x1 5 6 7 8 = x4 0 1 2 3 -> min

combine the first and the last column and scale the third column to obtain standard tableau
 x3 x2 1 -3* 2 9 = x1 -3 6 21 = x4 -3 1 6 -> min
pivot step according to Phase 2 of simplex method
 x1 x2 1 -1/3 2/3 3 = x3 1 4 12 = x4 1 -1 -3 -> min
x2-column is bad,  so the program is unbounded.

5.
 0 x2 1 -x3 1 2 3 4 = x1 5 6 7 8 = x4 0 1 2 3 -> min

drop the first column, switch two columns, and multiply a column by -1 to obtain standard tableau
 x2 x3 1 2 -4* 3 = x1 6 -8 7 = x4 1 -3 2 -> min
pivot step according to Phase 2 of simplex method
 x2 x1 1 1/2 -1/4 3/4 =x3 2 2 1 = x4 -1/2 3/4 -1/4 -> min
x2-column is bad,  so the program is unbounded.