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