Math 484.2  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

-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

 

1

-1

-8

= x3

1

3

 -2

= x1

-2

-6

 10

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

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

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 bwecause the minimal cost in each column is used.

Optimal potentials are also given. The corresponding adjuasted cost is ≥ 0.
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

3

   2

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

3

1

1

3

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*