Optimal assignment problem (Hungarian method)

The weights of the edges of the complete bipartite graph $K_{5,5}=(X, Y, E)$ are

Find a perfect matching of minimum weight in the bipartite graph. Here $X=\left\{ x_{i}: i=1,2,3,4,5\right\}$ and $Y=\left\{ y_{i}: i=1,2,3,4,5\right\}$.

The weights of the edges of the complete bipartite graph $K_{5,5}=(X, Y, E)$ are

Find a perfect matching of maximum weight in the bipartite graph. Here $X=\left\{ x_{i}: i=1,2,3,4,5\right\}$ and $Y=\left\{ y_{i}: i=1,2,3,4,5\right\}$.

The weights of the edges of the complete bipartite graph $K_{5,5}=(X, Y, E)$ are

Find a perfect matching of minimum weight in the bipartite graph. Here $X=\left\{ x_{i}: i=1,2,3,4,5\right\}$ and $Y=\left\{ y_{i}: i=1,2,3,4,5\right\}$.

Four candidates $A, B, C$, and $D$ were tested by a firm to fill three different types of jobs classified as $P, Q$, and $R. A$ scored 10,9, and 4 points, respectively, for these jobs. $B$ scored 10,6, and 8 points; $C$ scored 9,10, and 10 points; and $D$ scored 8,9, and 8 points. Based on these scores, the firm has to hire three of them such that the sum of the scores of those who were selected is a maximum. Show that the firm cannot come to an equitable decision about hiring these four candidates at this stage.

Show that the optimal assignment problem can be interpreted as a two-matroid intersection problem.

Using the optimal assignment method, obtain a lower bound for an optimal Hamiltonian cycle in the network shown in Fig. 7-11.

Solve the following optimal (minimization) assignment problem:

Solve the following optimal (minimization) assignment problem:

Solve the following optimal (maximization) assignment problem: