Math 484.1.  November 3, 2011.   Midterm 2.  
5 problems, 15 pts each. \Write your name here ____________________________  and on the other side.
Write down how you got your answer.


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

x1

x2

-2

-x4

 

 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 the second 1 in the first column:

 

x1

x2

-2

-x4

 

 1

-2

3

 4

= x3

 1*

2

1

 -3

= -x2

 2

2

-3

 0

--> max


-x2

x2

-2

-x4

 

 1

-4

2

 7

= x3

 1

-2

-1

 3

= x1

 2

-2

-5

 6

--> max

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

x2

x4

1

 

-5

-7

 -4

= x3

-3

-3

 2

= x1

4

6

 -10

--> min

The first row is bad  so our LP is infeasible.

This is also clear from the the difference of the first two rows of the original tableau..

 

2. Check whether   x1 = 0, x2 =0, x3 =4/ 3, 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

3

-4

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. Let yi be the variable dual to xi. For the complementary solution, y3=y4=y7 = 0. So we obtain the following system of linear equations for the dual variables:

 

-y6
1
-2
3
-4
5
-y8 2 1 0 2 1
1 2 0 1 -1 3
= y1 y2 0 0 y5

 

The third equation gives y6 = 1/3. Then the fourth equation, 4y6-2y8-1=0, gives y8= 1/6. Then we obtain positive values for

y1, y2, and y5. By the complementary slacknes , the given solution for the row LP is optimal (and so is the complementary solution for the column LP).


3-4. Solve transportation problems:

2

1

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

1

2

9

1

1

1

1

2

1

2

3

4

8

6

1

6

1

6

1

6

1

6

dem \ sup

3. Solution. We place the whole flow at positions with the minimal cost 1, so the solution is optimal:




3


6

9
2








6

8


5


3



1


9
4

 1 1 1


1




8

6

1

6

1

6

1

6

1

6

dem \ sup

The minimal total cost is 34.



4. Solve transportation problems:

3

1 

3

2

1

2

1

2

1

9

1

1

3

1

1

1

1

3

1

8

2

2

1

3

1

1

3

1

2

9

2

3

1

1

2

1

2

1

2

8

6

1

6

1

6

1

6

1

6

dem \ sup


4. Solution.  Here is an optimal basic solution and optimal potentials. The corresponding adjuasted cost is ≥ 0.
The minimal total cost is  36.



 1
 1
 0
 0
 0
 0
 1
 0
 1
0

3

1 

   1

3

2

1

2

1

    6

2

1

    2

9
0

1

    6

1

3

1

1

1

1

3

1

    2

8
-1

2

2

1

    2

3

1

    6

1

    1

3

1

2

9
-1

2

3

1

    4

1

    1

2

1

2

1

    1

2

    2

8

6

1

6

1

6

1

6

1

6

dem \ sup



5. Solve job assignment problem

1

2

3

4

2

2

3

0

1

2

3

2

1

3

1

1

3

0

5

1

1

5

2

1

0

Solution. We adjust the cost by columns, keeping it non-negative and creationg 0 in each column:

0*

0

3

3

2

1

1

0

0 *

2

2

0*

1

2

1

0

1

0 *

4

1

0

3

2

0

0 *

Now we have a solution (marked by *) with the zero cost, so it is optimal. The optimal value for the original problem is 4.