Math 484.1 midterm April 11, 2001 5 problems, 10 pts each Name

Solve transportation problems: 1.

| 1 | 2 | 3 | 1 | 2 | 3 | 1 | 2 | 3 |
|  |  |  |  |  |  |  |  |  | 10
|  |  |  |  |  |  |  |  |  |
| 0 | 3 | 2 | 0 | 1 | 2 | 1 | 2 | 1 |
|  |  |  |  |  |  |  |  |  | 20
|  |  |  |  |  |  |  |  |  |
| 2 | 1 | 0 | 1 | 2 | 1 | 2 | 1 | 1 |
|  |  |  |  |  |  |  |  |  | 12
|  |  |  |  |  |  |  |  |  |
| 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 1 |
|  |  |  |  |  |  |  |  |  | 8
|  |  |  |  |  |  |  |  |  |
| 0 | 0 | 0 | 14 | 1 | 2 | 3 | 14 | 16 |

2.

| 1 | 2 | 3 | 1 | 2 | 3 | 1 | 2 | 3 |
|  |  |  |  |  |  |  |  |  | 10
|  |  |  |  |  |  |  |  |  |
| 0 | 3 | 2 | 0 | 1 | 2 | 1 | 2 | 1 |
|  |  |  |  |  |  |  |  |  | 20
|  |  |  |  |  |  |  |  |  |
| 2 | 1 | 0 | 1 | 2 | 1 | 2 | 1 | 1 |
|  |  |  |  |  |  |  |  |  | 12
|  |  |  |  |  |  |  |  |  |
| 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 1 |
|  |  |  |  |  |  |  |  |  | 8
|  |  |  |  |  |  |  |  |  |
| 2 | 3 | 4 | 5 | 1 | 19 | 0 | 0 | 16 |

3.

| 1 | 2 | 3 | 1 | 2 | 3 | 1 | 2 | 3 |
|  |  |  |  |  |  |  |  |  | 0
|  |  |  |  |  |  |  |  |  |
| 0 | 3 | 2 | 0 | 1 | 2 | 1 | 2 | 1 |
|  |  |  |  |  |  |  |  |  | 30
|  |  |  |  |  |  |  |  |  |
| 2 | 1 | 0 | 1 | 2 | 1 | 2 | 1 | 1 |
|  |  |  |  |  |  |  |  |  | 12
|  |  |  |  |  |  |  |  |  |
| 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 1 |
|  |  |  |  |  |  |  |  |  | 8
|  |  |  |  |  |  |  |  |  |
| 2 | 3 | 4 | 5 | 1 | 2 | 3 | 14 | 16 |

Solve the assignment problems: 4.

| 1  | 2  | 3  | 1  | 2  |
|  |  |  |  |  |
|  |  |  |  |  |
| 3  | 1  | 2  | 1  | 0  |
|  |  |  |  |  |
|  |  |  |  |  |
| 0  | 0  | 3  | 2  | 1  |
|  |  |  |  |  |
|  |  |  |  |  |
| 0  | 0  | 2  | 1  | 1  |
|  |  |  |  |  |
|  |  |  |  |  |
| 1  | 3  | 3  | 1  | 0  |
|  |  |  |  |  |
|  |  |  |  |  |

5.

| 1  | 2  | 0  | 1  | 2  |
|  |  |  |  |  |
|  |  |  |  |  |
| 0  | 1  | 2  | 1  | 0  |
|  |  |  |  |  |
|  |  |  |  |  |
| 0  | 1  | 0  | 2  | 1  |
|  |  |  |  |  |
|  |  |  |  |  |
| 2  | 2  | 0  | 1  | 1  |
|  |  |  |  |  |
|  |  |  |  |  |
| 0  | 0  | 3  | 1  | 2  |
|  |  |  |  |  |
|  |  |  |  |  |

Answer:

5. 0  0  0  1  0 | 1  | 2  | 0  | 1  | 2  |

0 | (1) | (2) | 0 | 1 | (2) |
|  |  |  |  |  |
| 0  | 1  | 2  | 1  | 0  |
0 | 0 | (1) | (2) | (0) | 1 |
|  |  |  |  |  |
| 0  | 1  | 0  | 2  | 1  |
0 | 1 | (1) | 0 | (1) | (1) |
|  |  |  |  |  |
| 2  | 2  | 0  | 1  | 1  |
0 | (2) | (2) | 1 | (0) | (1) |
|  |  |  |  |  |
| 0  | 0  | 3  | 1  | 2  |
0 | 0 | 1 | (3) | (0) | (2) |
| | | | | |

min=1.

By the way, in this case instead of computing w_{i,j} and cheking that they are ≥ 0, we can just check that the nonzero flow at each column is placed at positions with minimal cost.