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

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

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

Solution: Pivot x₂ 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 x_i >=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   6 2 1   6 3 1   6 2 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 3 2 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