Linear Programs problems

Nov 2, 2016, #34. Solve the job assignment problem

1 0 3 1 0 2 0 1 0 2 1 1 3 0 2 2 0 2 0 2 1 1 2 2 0 0 3 1 0 2 1 0 1 0 1 0 Solution. The cost is ≥ 0, and there is a zero jn each row and column. So Phase 1 of Hungarian method is done.

However we cannot place the flow at positions with the zero cost because the big (5 by 2) positive block in the rows 1-5, columns 4, 6. We destroy the block subtracting 1 from each of 5 first rows and adding 1 to columns 1,2,3,5. Here is the resulting adjusted cost matrix:

1 0 3 0 0 1 0 1 0 1 1 0 3 0 2 1 0 1 0 2 1 0 2 1 0 0 3 0 0 1 2 1 2 0 2 0 Now we find a zero cost assignment:

1 0 3 0* 0 1 0 1 0* 1 1 0 3 0* 2 1 0 1 0* 2 1 0 2 1 0 0 3 0 0* 1 2 1 2 0 2 0*

We get an optimal solution with total cost 0.

For the he original problem, min = 1.

April 30, 2016. #34. Solve the job assignment problem

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

Solution. The cost is ≥ 0, and there is a zero in each row and column. So Phase 1 of Hungarian method is done.

However we cannot place the flow at positions with the zero cost because the big (3 by 4)

positive block in the northeast corner. We destroy the block subtracting 1 from each of 3 first rows and adding 1 from each of the first 2 columns. Here is the resulting adjusted cost matrix:

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

Now we try to choose zeros starting with rows and

columns with single zeros,

c7, c6, r7, r4, r3, r1:

0* 0 2 0 1 1 0 1 2 1 0* 1 3 0* 1 1 3 1 2 3 0* 1 2 2 1 1 3 1 0 0* 2 3 1 0* 1 1

We get an optimal solution with total cost 0.

For the he original problem, min = 1.

(