Math 484.3.  November 4, 2015.   Midterm 2.
10 problems, 5 pts each.   Write your name here  Vaserstein

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.  The third row is bad, so the LP is infeasible.  (A).

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

 -1 -1 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 -1* 2 -3* -1 1 0 1* -1 2 3* -1 3 -1 4 -5 2 -1 -7 6 -1 -8 0 0

There are 4 choices. (E).

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 third row reads -3x1 - x2 ≥ 0, hence x1 = x2 = 0.  Now our problem is x3 ≥ 0,  -2x3 +1 ≥ 0,  3x3 -2    0, x3 <=1/2, x3>=2/3, Contradiction, hence  (A).

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

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

is (A) 0.2, (B)  -4,  (C) 2,   (D) 4.

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 + 9 ≥ 0,   x   ≥ 0,   -2x + 6 ≥ 0,   x + 1 -> max,

or   x ≥ 1 x ≤ 3,   x + 1 -> max.  So max =  4 at x = 3. . The row problem has the same optimal value. (D).

30. The optimal value for the linear program given by a standard row 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 row feasible with the 4th column being bad.   The row problem is unbounded, and the column problem is infeasible.  (E).

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   =   4

-1  -1     2    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,  -b -1 ≥ 0. So there are no complementary feasible solution of the column problem. (C).

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

2   t

t   0 .

For which  numbers t it has an optimal solution?

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

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

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

 1 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 to each of the first 2 columns. Here is the resulting cost matrix:

 1 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

 1 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

But this cannot be done!   Instead of looking for a big positive block, we use that min ≥ 1, so completing the job assignment by the entry 1 in r1&c1, we get an optimal solution with total cost 1.    For the original table, min = 2. (B).

35.  The optimal value  for the transportation problem

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

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

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

 0 0 2 0 1 0 8 0 0 0 1 0 1 0   6 0 8->2->1 done 1 0 0 5 1 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.

 0  6 0  1 2 0 1 0 1 8 done 0 0 0  1 0  1 0   6 0 8->2 done 1 0 0  5 1 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).