Math 484.2  November 3, 2011.   Midterm 2.
5 problems, 15 pts each. \Write your name here ____________________________  and on the other side.

1. Solve the linear program where all xi ≥ 0:

 x1 x2 -2 -x5 1 2 3 4 = x3 - 1 2 1 -3 = -x2 2 2 3 0 --> max

Solution. We are going to change the tableau to make it standard. We pivot on -1 in  the first column:

 x1 x2 -2 -x5 1 2 3 4 = x3 - 1* 2 1 -3 = -x2 2 2 3 0 --> max

->

 -x2 x2 -2 -x5 -1 4 4 1 = x3 -1 2 1 -3 = x1 -2 4 5 -6 --> max

Now we combine the first two columns. permute and scale the last two columns, and scale the last row:

 x2 x5 1 5 -1 -8 = x3 3 3 -2 = x1 -6 -6 10 --> min

The first column is bad although we are in Phase 1 yet. Now we set

x= 0 and send    xto infinity. The objective function goes to -infinity and we are feasible for large  x.

So the LP is unbounded.

2. Check whether   x1 = 0, x2 =3.4, x3 =0, x4 = 5/2, x5 = 0, x6 =0, x7 =10,
x8 = 0 is an optimal solution for the LP written in a stanfdard tableau:

 x1 x2 x3 x4 x5 1 1 -2 3 1 5 6 = x6 -1 2 -3 4 -5 0 = x7 2 1 0 2 1 -5 = x8 2 0 1 1 3 -1 -> min

Solution. The first constraint does not hold, so the proposed "solution" is not feasible hence it is noit optimal.

Remark. x1 = 0, x2 =3.4, x3 =0, x4 = 0.8, x5 = 0, x6 =0, x7 =10,  x8 = 0 is an optimal.

3-4. Solve transportation problems:

 2 3 3 2 1 2 1 2 1 9 1 2 3 1 1 1 1 3 1 8 2 2 1 3 1 1 3 3 2 9 3 1 3 1 2 1 2 3 4 8 6 1 6 1 6 1 6 1 6 dem \ sup

Solution. The following basic feasible solution is optimal.

Optimal potentials are also given. The corresponding adjusted cost is ≥ 0. It is 0 at the selected positions.
The minimal total cost is  40.

 1 0 1 0 1 0 1 2 1 0 2 3 3 2 1    3 2 1 2 1      6 9 0 1    6 2 3 1 1 1 1    2 3 1 8 0 2 2 1     6 3 1     3 1 3 3 2 9 -1 3 1     1 3 1     1 2 1     1 2     4 3    1 4 8 6 1 6 1 6 1 6 1 6 dem \ sup

4.

 3 1 3 2 1 2 3 2 1 9 3 3 3 1 1 3 1 3 1 8 2 2 3 3 1 1 3 1 2 9 2 3 3 3 2 1 2 3 2 8 6 1 6 1 6 1 6 1 6 dem \ sup

Solution. Here is an optimal solution using the least cost 1:

 3 1    1 3 2 1     2 2 3 2 1    6 9 3 3 3     1 1   1 1 3 1    6 3 1 8 2 2 3      4 3 1   4 1 3 1       1 2 9 2    6 3 3    1 3 2 1    1 2 3 2 8 6 1 6 1 6 1 6 1 6 dem \ sup

min= 34.

5. Solve job assignment problem

 1 2 3 1 2 2 3 5 1 2 3 2 1 3 1 1 3 4 5 1 1 1 2 1 0

Solution.  We cannot use the least number in each column and get  4 but we can get min=5:

 1 2* 3 1 2 2 3 5 1* 2 3 2 1* 3 1 1* 3 4 5 1 1 1 2 1 0*