Math 484.1 November 8, 2007 Midterm 2

5 problems, 15 pts each. By: Nathan Pish

1. Solve linear program where all x_i >= 0

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

First, we make the tableaux standard.

x1	x2	x5	1
1	2	-4	3	= x3
-1	-2	-1 ^*	0	= x2
0	2	0	-3	àmin

Then, we pivot on the -1 in the x₅ column.

x1	x2	x2	1
-3	-6	4	3	= x3
-1	-2	-1	0	= x5
0	2	0	-3	àmin

Finally, we combine the x₂ columns.

x1	x2	1
-3	-2	3	= x3
-1	-3	0	= x5
0	2	-3	àmin

We get an optimal tableaux with min = -3 at x₁ = x₂ = 0, x₅ = 0, x₃ = 3.

2. Solve linear program where all x_i >= 0

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

First, we need to make a standard tableaux.

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

This is an optimal tableaux with min = 3 à max = -3 at x₁ = x₂ = x₅ = 0, x₄ = 0, x₃ = 3.

3. Solve transportation problem.

This can be solved in phase 1.

^potentials	1	1	0	1	0	0	1	-1	1
0	^2 (1)	^4 (3)	^3 (3)	^2 (1)	^1 (1)	^2 (2)	^1 6	^2 (3)	^1 3	9
0	^1 6	^2 (1)	^3 (3)	^1 1	^1 (1)	^0 1	^1 (0)	^3 (4)	^1 0	8
-1	^2 (2)	^2 (2)	^1 (0)	^3 (1)	^1 6	^1 (0)	^3 (1)	^0 1	^2 2	9
0	^2 (1)	^1 1	^0 6	^1 (0)	^2 (2)	^1 (1)	^2 (1)	^3 (4)	^1 1	8
	6	1	6	1	6	1	6	1	6

Min = 28

4. Solve transportation problem.

This can also be solved in phase 1.

^potentials	0	1	1	0	1	0	1	1	1
0	^3 (3)	^1 1	^3 (2)	^2 (2)	^1 4	^2 (2)	^4 (3)	^2 (1)	^1 4	9
0	^0 6	^1 (0)	^3 (2)	^1 (1)	^1 (0)	^5 (5)	^1 2	^3 (2)	^1 (0)	8
0	^2 (2)	^2 (1)	^1 6	^3 (3)	^1 2	^1 (0)	^3 (1)	^1 1	^2 (1)	9
-1	^2 (1)	^3 (1)	^2 (0)	^1 1	^2 (0)	^1 1	^2 4	^3 (1)	^2 2	8
	6	1	6	1	6	1	6	1	6

Min = 34

5. Solve job assignment problem.

1^*	2	3	4	2
2	3	4	1^*	2
3	1^*	5	3	1
1	3	4	3	1^*
5	5	2^*	1	3

We start by subtracting 1 from every row.

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

Now, we subtract 1 from the third column

0^*	1	1	3	1
1	2	2	0^*	1
2	0^*	3	2	0
0	2	2	2	0^*
4	4	0^*	0	2

The zeros are marked in this last table, and we get the min by adding the original values together. Min = 6