Math 484.2  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  and a row by -1.
standard  feasible tableau:
 x2 x3 1 2 -4* 7 = x1 -6 8 31 = x4 1 -3 6 -> min
pivot step according to Phase 2 of simplex method
 x2 x1 1 1/2 -1/4 7/4 = x3 -2* -2 45 = x4 -1/2 3/4 3/4 -> min
pivot step according to Phase 2 of simplex method
 x4 x1 1 -1/4 -3/4 13 = x3 -1/2 -1 45/2 = x2 1/4 5/4 -21/2 -> min
The tableau is optimal, so  min = -21/2=-10.5 at  x1=0, x2= 45/2, x3=13,  x4= 0.

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  and multiply a column by -1
 x2 -x1 1 -2* 4 -11 = x1 -6 8 -31 =  x4 -1 3 -6 -> min
pivot step
 x1 -x1 1 -1/2 2 -11/2 = x2 3 -4 2 = x4 1/2 1 -1/2 -> min
combine the first two columns.  standard tableau:

 x1 1 -5/2 -11/2 = x2 7 2 =x4 -1/2 -1/2 -> min
x2-row is bad,  so the program is infeasible.

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 11 = x1 6 -8 31 = -x1 1 -3 6 -> max
add the first row from the second row and multiply the third row by -1
 x2 x3 1 2 -4 11 = x1 8 -12* 42 = 0 -1 3 -6 -> min
pivot on -12 and drop the second column to obtain standard tableau
 x2 1 -2/3 -3 = x1 2/3 7/2 = x3 1 9/2 -> min
The  x1-row is bad, so the program is infeasible.

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

combine the first and the last column  to obtain standard tableau
 x3 x2 1 -3* 2 3 = x1 5 6 7 =x4 -3 1 2 -> min
pivot step according to Phase 2 of simplex method
 x2 1 2/3 1 28/3 12 -1 -> min
(irrelevant entries are not shown). Now  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   columns, and multiply a column and a row 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 1 of simplex method
 x4 x3 1 4/3 2/3 = x1 1/6 4/3 7/6 = x2 -5/3 -> min
This is a feasible tableau with  x3-column bad, so the program is unbounded.