Math 484.1 November 8, 2007   Midterm 2

5 problems, 15 pts each. By: Nathan Pish

1.       Solve linear program where all xi >= 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 x5 column.

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

Finally, we combine the x2 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 x1 = x2 = 0, x5 = 0, x3 = 3.

2.       Solve linear program where all xi >= 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 x1 = x2 = x5 = 0, x4 = 0, x3 = 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