Math 484.  March 28, 2012.   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

= -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 ios 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.