Math 484.  March 28, 2012.   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 -x4 1 -2 3 4 = x3 1 2 1 -3 = -x5 2 2 -3 0 --> min

Solution. First we write the LP in a standard tableau:

 x1 x2 x4 1 1 -2 -4 -6 = x3 -1 -2 -3 2 = x5 2 2 0 6 --> min

According to Simplex Method, Phase 1, we pivot on 1 and obtain

 x3 x2 x4 1 1 2 4 6 = x1 -1 -4 -7 -4 = x5 2 6 8 18 --> min

The second row is bad, so the LP is infeasible.

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

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

Solution. It is easy to check that all 3 equations  hold and that all xi are nonnegative. So the

proposed solution is feasible.   Let  yi be the dual  variable for xi. We are looking for the complementary optimal solution so

y3 = y4 = y7 = 0.

 x1=0 x2=0 x3=4 x4=5/2 x5=0 1 -y6 1 -2 1 -4 5 6 = x6=0 -y7=0 -1 2 -1 4 -5 0 = x7= 6 -y8 2 1 0 2 1 -5 = x8 = 0 1 2 0 1 -1 3 1 -> min =y1 =y2 =y3=0 =y4=0 =y5 ->maz

From y3-column, -y6+1 = 0, hence  y6=1.

From y4-column: 4y6 - 2y8 -1 = 0, hence y8 = 3/2.

From y1-column:  y1 = -y6 - 2y8+2 = -2. So there is no complementary solution hence the proposed solution is not optimal.

3-4. Solve transportation problems:

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

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

Solutions. 3.

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

is optimal  with min = 36.

4.

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

This is optimal because we use the minimal cost in every column; min = 40.

5. Solve job assignment problem

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

Solution.

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

is optimal because we used only the positions with the minimal cost in every column.

min = 6.