### Math 484.2     November 6, 2008     Name: ______Patrick Johnson________________Midterm 2,      5 problems, 15 points each.

1. Solve linear programs where all xi >=0:

 x1 x2 2 -x5 1 2 3 4 = x3 1 -2 0 -1 = -x2 0 2 -3 0 → max

Solution: Pivot x2 to top, then combine into standard form.
Standard tableau is feasible, so pivot on the negative entry in the second column .

 x1 x2 1 x5 1 2 6 -4 = x3 -1 2 0 -1* = x2 0 -2 6 0 → min
 x1 x2 1 x2 5 -6 6 4 = x3 -1 2 0 -1 = x5 0 -2 6 0 → min
 x1 x2 1 5 -2* 6 = x3 -1 1 0 = x5 0 -2 6 → min
 x1 x2 1 5/2 -1/2 3 = x3 3/2 -1/2 3 = x5 -5 1 0 → min
[switch
x2 and x3
-- Kayla
Koda ]

First column is a bad column, so LP is unbounded
min → -∞ as x1 → +∞

2. Solve linear programs where all xi >=0:

 2x1 -x2 1 x5 1 -2 3 4 = x3 1 -2 0 -1 = -x4 0 2 -3 -2 → min

Solution: Rearrange tableaux into standard form. Standard tableaux is feasible with a bad column

 x1 x2 x5 1 2 2 4 3 = x3 -2 2 1 0 = x4 0 -2 -2 -3 → min
Second and third columns are bad columns
min → -∞ as x2 or x5 → +∞

3. Solve the following transportation problem

 2 5 3 2 1 2 1 2 1 9 1 2 3 1 1 0 1 3 1 8 2 2 1 3 1 1 3 0 2 9 0 1 3 1 2 1 2 3 1 8 6 1 6 1 6 1 6 1 6 dem\sup

Solution:

 0 1 1 1 1 0 1 0 1 0 2 (2) 5 (4) 3 (2) 2 (1) 1 4 2 (2) 1 3 2 (2) 1 2 9 5 3 0 1 (1) 2 (1) 3 (2) 1 (0) 1 (0) 0 1 1 3 3 (3) 1 4 8 7 4 0 2 (2) 2 (1) 1 6 3 (2) 1 2 1 (1) 3 (2) 0 1 2 (1) 9 8 2 0 0 6 1 1 3 (2) 1 1 2 (1) 1 (1) 2 (1) 3 (3) 1 (0) 8 2 1 6 1 6 1 62 1 63 1 62 dem\sup

All discrepancies are nonnegative,so solution is optimal
min. cost = 1⋅4 + 1⋅3 + 1⋅2 + 0⋅1 + 1⋅3 + 1⋅4 + 1⋅6 + 1⋅2 + 0⋅1 + 0⋅6 + 1⋅1 + 1⋅1 + 1⋅0
= 4 + 3 + 2 + 0 + 3 + 4 + 6 + 2 + 0 + 0 + 1 + 1 + 0
= 26

Maximum profit for corresponding dual problem:
= 0 + 1 +6 + 1 + 6 + 0 + 6 + 0 + 6 - 0 - 0 - 0 - 0
= 26

4. Solve the following transportation problem

 3 1 3 2 1 2 0 2 1 9 5 1 3 1 1 5 1 3 1 8 2 2 0 3 1 1 3 0 2 9 2 3 0 1 2 1 2 0 2 8 6 1 6 1 6 1 6 1 6 dem\sup

Solution:

 2 1 0 1 1 1 0 0 1 0 3 (1) 1 (0) 3 (3) 2 (1) 1 3 2 (1) 0 6 2 (2) 1 (0) 9 3 0 5 (3) 1 1 3 (3) 1 (0) 1 1 5 (4) 1 (1) 3 (3) 1 6 8 7 1 0 2 0 2 (1) 0 6 3 (2) 1 2 1 1 3 (3) 0 (1) 2 (1) 9 7 6 0 2 6 3 (2) 0 (0) 1 1 2 (1) 1 (0) 2 (2) 0 1 2 (1) 8 7 1 6 1 6 1 6 32 1 6 1 6 dem\sup

All discrepancies are nonnegative,so solution is optimal
min. cost = 1⋅3 + 0⋅6 + 1⋅1 + 1⋅1 + 1⋅6 + 2⋅0 + 0⋅6 + 1⋅2 + 1⋅1 + 2⋅6 + 1⋅1 + 0⋅1
= 3 + 0 + 1 + 1 + 6 + 0 + 0 + 2 + 1 + 12 + 1 + 0
= 27

Maximum profit for corresponding dual problem:
= 12 + 1 + 0 + 1 + 6 + 1 + 0 + 0 + 6 - 0 - 0 - 0 - 0
= 27

5. Solve the following job assignment problem

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

Solution:

 -2 -1 1* 2 3 4 2 -1 2 3 4* 1 2 -1 3 1* 5 3 5 1 3 4 0* 1 5 5 2 1 0*
 0* 2 0 3 1 1 2 1* 0 1 2 0* 2 2 4 1 3 2 0* 1 5 5 0 1 0*

The only zeroes in rows 2 and 4 are in the same column ⇒ Zero-sum is not possible
Sum of one is possible and therefore must be optimal

∴ minumum = 1 + 4 + 1 + 0 + 0 = 6