The following table shows the weights for assigning rows i to columns j in a maximum total weight assignment problem.

j = 4 5 6 i = 1 25 13 22 2 21 14 19 3 20 25 29

(a) Formulate the model as a linear assignment model.

(b) Construct the starting dual solution and equality subgraph of Hungarian Algorithm 10D for the given weights.

(c) Make a starting assignment of (2 to 4) and

(3, 6). Then explain why this solution is complementary with the dual of part (a).

(d) Beginning from the solution of

(c) complete Hungarian Algorithm 10D to identify an optimal assignment. Detail the labeling to grow the assignment and/or associated label trees at each step, as well as computations to change duals. Also verify at each dual change that no assignment of tree-labeled edges are dropped in the equality subgraph as the dual is updated.

(e) Show the optimal primal and dual solutions, and demonstrate that they are complementary.

(f) Compute bound 10.49 on the Algorithm 10D computational effort for this instance and compare to the number of steps in your solution of part (c).