Math 484.2.  April 15, 2015.   Midterm 2.
10 problems, 5 pts each.   Write your name here  Vaserstein

No electronics is allowed.   Write both answers and details. 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. By Simplex Method, Phase 1, the pivot entry is the third entry in the first column (since

1/(-1) > 2/(-1) :

 1 0 0 3 -1 0 -1 2 1* -1 -1 -1 -1 -2 -2 -2

pivot step

 1 1 1 + -1 -1 -2 + 1 1 1 + -1 -3 -3 -3

Now we pivot on the first -1 in the second column and obtain  an optimal  tableau  (C).

Remark. The first row in all 3 tableaux  above and the  third  row in the last tableau are redundant for the row program. The corresponding linear constraints  have the form   = * ≥  0.

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

 -1 0 2 1 -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.

 -1 0 2 1 -1 1 0 1* -1 2* 3* -1 3 -1 4 -5 2 1 -7 6 -1 -8 0 0

(D)

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

 -1 0 2 1 0 -1 3 -2 3 -1 4 5 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. Setting  x1 = x2 = 0,  and x3 = 1, we see that the problem is feasible. Setting x2 = x3, we get a bad column (i.e., the column problem is infeasible).  (B)

29. The optimal value for the linear program given by a standard tableau with the matrix

 -2 -3 2 0 -1 2 -1 -1 -2 3 1 0 6 1

is (A) 0.2, (B) 2/3, (C) 2.5,  (D) -1.

Solution.   We consider the column problem, with the variable at the left margin being x. Then

x ≥ 0,  2x -1 ≥ 0,  3x  -2  ≥ 0,    -2x + 3 ≥ 0,   x   ≥ 0,   -2x + 6 ≥ 0,   x + 1 -> max,

or   x ≥ 1 x ≤ 3/2,   x + 1 -> max.  So max =  2.5 at x = 1.5. The row problem has the same optimal value. (C).

30. The optimal value for the linear program given by a standard tableau with the matrix

 -2 -3 -4 1 1 1 2 3 1 1

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

Solution. The tableau is optimal.     (D).

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    2    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

------------------

0    1  -1    1   =   0

1  -1    0    1   =   0

-1    0    1   -2   =  0

-1  -1     2    0              .

So we get a feasible solution. For the dual variables   a, b, c at the left margin we obtain 3 linear equations by complementary slackness.

Here is the solution:

1     2    3      1

------------------

-1 |  0    1  -1     1 | =   0

-2 |  1   -1   0     1 | =   0

-3 |-1     0   1   -2 | =   0

1 | -1   -1   2     0 |

-------------

= 0   =0 = 0

So the correct answer is (B). The optimal value is 3.

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

-2   t

-1   0

has an optimal solution for

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

Solution.  Let  x be the dual variable for the first row. We get  1/2 ≤ x . -tx -> max.   This program has an optimal solution  (namely, x = 1/2) if and only if

t ≥ 0  (A).

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

 -1 -4 0 -6 2 -2 -2 -7 -4 1 3 2 -8 -5 1 1 -2 -2 2 1 -1 -1 -1 0 0

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

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

Solution.

 -1 -4* 0 -6 2 -2* -2* -7 -4 1 3 2 -8* -5 1 1 -2* -2 2 1 -1 -1 -1 0 0

(C)

34. The optimal value of the  job assignment problem

 2 2 3 1 2 2 3 1 3 2 1 1 3 3 2 2 4 2 1 2 4 1 2 2 0 0 3 1 1 0 1 2 1 1 1 1

is (A)  4, (B)  5,  (C)   6, (D) 7.

Solution.  We adjust the cost subtraction the least cost in each row from every cost in the row:

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

The cost is ≥ 0, and we have a zero in each row and column.  Phase 1 of Hungarian method is done.

Now we look for the zero total cost assignment, and here it is:

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

Total cost for the original matrix is 1+ 1 +2 +1 + 1= 6.    (C)

35.  The optimal value  for the transportation problem

 3 2 3 2 1 0 2 2 2 8 2 2 2 2 0 0 2 2 1 8 2 2 1 3 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.

 3 2 3 2 1 0 8 2 2 2 2 0 0 8 2 2 1 3 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.

 1 0 2 0 1 0 8 0 0 1 0 0 0 8 0 0 0 1 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 3 and 5 where there is no choice:

 1 0 2 0 1 0 8 0 0 1 0 06 0 8->2 0 0 05 1 1 1 5  done 6 1 6->1 1 6 done 1 demand\supply

We see (column 3) that we have to use positions with positive cost. We select the position with zero cost in column 1. After this, we have only one row left, so

we select all remaining position in this row.

 14 01 21 01 1 01 8 done 02 0 1 0 06 0 8->2 done 0 0 05 1 1 1 5  done 6 done 1 done 6->1 done 1 done 6 done 1 done demand\supply

The total  cost is 6. So  min 1 ≤ min ≤ 6 (we used that min is an integer).    For the original problem,     23 ≤ min ≤ 28.

We do not need to do Phase 2 of simplex method to conclude that the correct answer is (D).