Math 484.001. March 30, 2016.   Midterm 2.  
10 problems, 5 pts each.   Write your name here  Vaserstein

No electronics is allowed.   Write both answers and details (show work). 

Write only answers on scantron. Return this page and the scantron. 

If you do not like any given answers, explain why here and choose (E) at scantron.

Do not talk with other students in class even after finishing your papers.


26. The linear program given by a standard row tableau with the matrix

  1

  0

  0

-3

-1

  0

-1

  2

-1

-1

-1

  1   

-1

-2

-2

-2


(A) is infeasible, (B) is unbounded, (C) has an optimal solution.


Solution.   According  to the simplex method, we  pivot on 1 in the first row.

The second row becomes bad.  (A).



27. The linear program given by a standard row tableau with the matrix

-1

-2

 2

-3

-1

 1

 0

 1

-1

 2

 3

-1

 3

-1

 4

-5

 2

-1

-7

 6

-1

-8

 0

 0

The number of choices for the pivot entry consistent with the simplex method is


(A) 0, (B) 1, (C)2,  (D) 3.


Solution.  There are no bad rows and the tableau is not row-feasible.

We consider positive entries in the second row, they give possible pivot columns.


-1

-2*

 2

-3*

-1

 1

 0

 1

-1

 2

 3*

-1

 3

-1

 4

-5

 2

-1

-7

 6

-1

-8

 0

 0


There are 3 choices. (D).





28. The linear program given by a standard row tableau with the matrix

-1

0

2

1

0

-1

3

-2

-3

1

0

0

7

-6

-1

-8


(A) is infeasible, (B) is unbounded, (C) has an optimal solution.


Solution. Let  x1, x2, x3 be the variables on top.   The x3-column is bad so the column problem is infeasible.


 Setting x1 = 0 and x2 = x3 = 1, we have a feasible solution for the row problem. (B).

                


29. The optimal value for

(3t + 2)x + (3-t)y -> min, 0 ≤ x ≤ 1,  0 ≤ y ≤ 1

as a function of the parameter t  has slopes

(A) 0, (B) 1, 2, (C) 3, 0,  -1. (D) -1, 2,  3.


Solution.  min = min(0, 3 - t, 3t+2, 2t + 5) = min (3t + 2, 0, 3 - t) =

3t+ 2 when t ≤  -2/3,

0 when -2/3  ≤ t ≤ 3,

3 - t  when t ≥ 3.

(C).



30.    The optimal value for

x + y -> min, x ≥ t, y ≥ 2t. x ≥ 0

as a function of the parameter t  has slopes

(A) 0, (B) 2, 3, (C) 3, 0,  -1. (D) -1, 1.


Solution. 

When  t ≤ 0, min = 2t  at  x = 0, y = 2t. When  t ≥ 0, min = 3t  at x = t, y = 2t.

(B).




31. A linear program is given a standard row tableau with the matrix

 0    1  -1    1

 1   -1   0    1

-1    0   1    2

 1  -1    0    0 .

Setting the variables on the top to be  1, 2, and 3, we obtain

(A) an infeasible solution, (B) an optimal solution, (C) a feasible solution which is not optimal.


Solution.   Here are the values for all 6 variables in the row problem:


          1      2      3       1

          ———————

 -a    0    1  -1     1   =   0

-b     1  -1    0     1   =   0

—c  -1    0    1     2   =   4

  1    1  -1     0     0   -> min    .

      =0    =0     =0     =0


So we get a feasible solution. Now we look for a complementary feasible solution of the column problem.

 For the dual variables   a, b, c at the left margin we obtain 3 linear equations by complementary slackness:

c = 0 (the c-row),  -b +1  =  0, (the first column),  -a + b -1 = 0 (the second column). hence   a  = c =  0 and  b = 1.

Plugging this into the last column, we get =1 = 0.

Thus, there are no complementary feasible solution hence  we obtain a feasible solution for the row program which os not optimal. 

(C).




32. A linear program   given a standard  row  tableau with the matrix


1       t

t-1   0 


has an optimal solution  for

(A) t ≥ 0,  (B) all t, (C) t ≤ 0. (D) t ≥ 1.


Solution.  If t   1, the tableau is optimal. If  0    t < 1,   the tableau is feasible with a bad column. If  t < 0, pivoting on 1 produces a feasible tableau with a bad column. (D)


33. A linear program given by a standard row tableau with the matrix

 

-4

-2

 0

-6

 2

-2

-2

-7

-4

 1

 3

 2

-8

-4

 1

 1

-2

-2

  2

 -1

 -1

 -1

-1

  -1

 0


How many choices for the first   pivot entry which are consistent with Simplex Method?

(A) 0, (B) 3, (C)  4,  (D)  6.


Solution.

 

-4*

-2

 0

-6

 2

-2*

-2

-7

-4*

 1

 3

 2

-8

-4*

 1

 1

-2

-2

  2

 -1

 -1

 -1

-1

  -1

 0


(C) .


                                                           

34. The optimal value of the  job assignment problem

0

0

3

1

2

2

0

1

3

2

1

1

3

0

2

2

4

2

1

2

0

1

2

2

0

0

3

1

0

0

1

2

1

0

1

1

is (A)  1, (B)  2,  (C)  3, (D) 4.

Solution.  The cost is  ≥ 0, and there is a zero in each row and column. However we cannot place the flow at positions with the zero cost because the big (3 by 4)

positive block in the northeast corner. We destroy the block  subtracting 1 from each of 3 first rows and adding 1 from each of the first 2 columns. Here is the resulting adjusted cost matrix:

0

0

2

0

1

1

0

1

2

1

0

1

3

0

1

1

3

1

2

3

0

1

2

2

1

1

3

1

0

0

2

3

1

0

1

1

Now we try to choose zeros starting with rows and columns with single zeros, 

c7, c6, r7, r4, r3,  r1:

0*

0

2

0

1

1

0

1

2

1

0*

1

3

0*

1

1

3

1

2

3

0*

1

2

2

1

1

3

1

0

0*

2

3

1

0*

1

1

We get an optimal solution with total cost 0.    

In the original table, min = 1. (A).



35.  The optimal value  for the transportation problem

2

2

3

2

1

0

2

2

2

8

2

2

1

3

0

0

2

2

1

8

3

2

1

2

1

1

0

1

2

5

2

3

0

1

2

1

2

1

2

0

6

1

6

1

6

1

0

0

0

demand\supply

 is (A) ≤22, (B) ≥ 29 , (C) the problem is infeasible, (D) lies in the interval    23 ≤ min ≤ 28.


Solution. The balance condition: 21 = 21. The flow in the last 3 columns and the last row is 0, so the cost is 0 in these line, hence we cross out them. 


2

2

3

2

1

0

8

2

2

1

3

0

0

8

3

2

1

2

1

1

5

6

1

6

1

6

1

demand\supply


Now we subtract 2, 2,  1, 2 from the cost in the first 4 columns (Phase 1 of Hungarian method), the total cost is reduced by  12 + 2 +  6 + 2 = 22.


0

0

2

0

1

0

8

0

0

0

1

0

0

8

1

0

0

0

1

1

5

6

1

6

1

6

1

demand\supply


Now we try to place the flow at positions with the zero cost. We start with the columns 5 where there is no choice:

0

0

2

0

1

0

8

0 

0

0 2

1 

0  6

0

8->2->1 done

1

0

0 4

01

1

1

5  done

6

1

6  done

1 done

6 done

1

demand\supply


After this, we have only one row left, so  we select all remaining position in this row.


00 6

0 1

2

0

1

0 1

8 done

0

0

0 2

1 

0  6

0

8->2 done

1

0

0 4

01

1

1

5  done

6 done

1 done

6 done

1 done

6 done

1 done

demand\supply


The total  cost is 0 = min   For the original problem,     min= 22.   (A).