Exercises · Transportation and assignment¶
Exercises · Chapter 7 · each solution opens with a click · Chapter 7: Transportation and assignment · Exercises, volume 3 (PDF)
Rules used in these exercises
The definitions and the results of the chapter «Transportation and assignment». The origins are \(1,2,\dots,m\) with supplies \(a_i\), the destinations \(m+1,m+2,\dots,m+n\) with demands \(d_j\), and the cells \((i,j)\) are taken in row–column order.
-
(F1) Model. \(\min \sum_{i}\sum_{j} c_{ij}x_{ij}\) with row sums \(a_i\), column sums \(d_j\) and \(\vet{x} \ge \vet{0}\); feasible if and only if \(\sum_i a_i=\sum_j d_j\). An excess of supply goes to a dummy destination with costs \(0\).
-
(F2) Bases. A basis is a set of \(m+n-1\) cells forming a spanning tree of the bipartite network (no closed path alternating rows and columns). Its basic solution is found leaf by leaf; it is degenerate if a basic cell has value \(0\).
-
(F3) Initial solutions. North-west corner: the active cell with the smallest row and column. Minimum cost: the cheapest active cell, the smallest \(i\) and then \(j\) on ties. The amount is \(\min\{\bar{a}_i,\bar{d}_j\}\); if \(\bar{a}_i=0\) and another row is active, the row is crossed out, otherwise the column.
-
(F4) Potential method. \(\pi_i-\pi_j=c_{ij}\) on the basic cells, \(\pi_{m+n}=0\); \(\bar{c}_{ij}=c_{ij}-\pi_i+\pi_j\). Optimal if \(\bar{c} \ge 0\), unique if \(\bar{c}_{ij}>0\) outside the basis. Otherwise the most negative \(\bar{c}_e\) enters (ties: smallest \(i\), then \(j\)); the cycle starts at \(e\) along its row with signs \(+,-,+,\dots\); \(\theta\) is the minimum on the cells \(-\), and the first of them with \(\bar{x}=\theta\) in row–column order leaves; the cost changes by \(\theta\,\bar{c}_e\).
-
(F5) Hungarian algorithm. Subtract the row minima (\(\pi_i\)) and then the column minima (\(-\pi_j\)). Find a maximum set of independent zeros (row by row, alternating paths, columns in increasing order); if it has \(n\) zeros, stop. Otherwise the lines are the rows not reached and the columns reached by alternating paths from the unmatched rows; \(\delta\) is the minimum uncovered entry, subtracted from the uncovered entries and added to those covered twice (\(\pi_i \mathrel{+}=\delta\) on uncovered rows, \(\pi_j \mathrel{+}=\delta\) on covered columns). The dual value \(\sum_i\pi_i-\sum_j\pi_j\) grows by \(\delta\,(n-k)\) with \(k\) lines.
Exercise 7.1: Initial basic feasible solutions
Exercise
Three plants \(1,2,3\) supply \(a_1=30\), \(a_2=40\), \(a_3=20\) units of a product, and three customers \(4,5,6\) demand \(d_4=15\), \(d_5=25\), \(d_6=40\) units. Every demand must be met, and every plant ships at most its supply. The unit shipping costs are:
Questions
-
Is the instance balanced? Add a dummy destination as in (F1) and write the transportation tableau.
-
Build an initial basic feasible solution with the north-west corner rule: list the steps, write the solution in the tableau and compute its cost.
-
Build an initial basic feasible solution with the minimum cost rule, and compare the two costs.
-
Check that both solutions have \(m+n-1\) basic cells forming a spanning tree. How much supply does each plant leave unused in the two solutions?
Solution
We use the rules (F1)–(F5) of the box at the beginning of these exercises.
-
The total supply is \(30+40+20=90\) and the total demand is \(15+25+40=80\): the instance is not balanced, with an excess of \(10\) units. We add the dummy destination \(7\) with demand \(d_{7}=10\) and costs \(c_{17}=c_{27}=c_{37}=0\):
\[ \begin{array}{c|cccc|c} \hline {c_{ij}} & {4} & {5} & {6} & {7} & {a_i} \\ \hline {1} & {7} & {4} & {7} & {0} & {30} \\ {2} & {1} & {6} & {8} & {0} & {40} \\ {3} & {9} & {9} & {6} & {0} & {20} \\ \hline {d_j} & {15} & {25} & {40} & {10} & {90} \\ \hline \end{array} \] -
The steps of the north-west corner rule are
step cell amount crossed out \(1\) \((1,4)\) \(15\) column \(4\) \(2\) \((1,5)\) \(15\) row \(1\) \(3\) \((2,5)\) \(10\) column \(5\) \(4\) \((2,6)\) \(30\) row \(2\) \(5\) \((3,6)\) \(10\) column \(6\) \(6\) \((3,7)\) \(10\) row \(3\), column \(7\) and the solution is
\(\bar{x}_{ij}\) \(4\) \(5\) \(6\) \(7\) \(a_i\) \(1\) \(15\) \(15\) \(30\) \(2\) \(10\) \(30\) \(40\) \(3\) \(10\) \(10\) \(20\) \(d_j\) \(15\) \(25\) \(40\) \(10\) Its cost is \(7 \cdot 15+4 \cdot 15+6 \cdot 10+8 \cdot 30+6 \cdot 10+0 \cdot 10=525\).
-
The steps of the minimum cost rule are
step cell amount crossed out \(1\) \((1,7)\) \(10\) column \(7\) \(2\) \((2,4)\) \(15\) column \(4\) \(3\) \((1,5)\) \(20\) row \(1\) \(4\) \((2,5)\) \(5\) column \(5\) \(5\) \((3,6)\) \(20\) row \(3\) \(6\) \((2,6)\) \(20\) row \(2\), column \(6\) At step \(1\) the three dummy cells cost \(0\), and the rule takes \((1,7)\), the smallest row. The solution is
\(\bar{x}_{ij}\) \(4\) \(5\) \(6\) \(7\) \(a_i\) \(1\) \(20\) \(10\) \(30\) \(2\) \(15\) \(5\) \(20\) \(40\) \(3\) \(20\) \(20\) \(d_j\) \(15\) \(25\) \(40\) \(10\) Its cost is \(4 \cdot 20+0 \cdot 10+1 \cdot 15+6 \cdot 5+8 \cdot 20+6 \cdot 20=405\), lower than the \(525\) of the north-west corner rule.
-
Each rule makes \(m+n-1=3+4-1=6\) steps, one cell per step; the cells form a spanning tree because the crossed line of each step contains no later cell. The flow on the dummy column is the unused supply: with the north-west corner rule plant \(1\) keeps \(0\), plant \(2\) keeps \(0\) and plant \(3\) keeps \(10\); with the minimum cost rule plant \(1\) keeps \(10\), plant \(2\) keeps \(0\) and plant \(3\) keeps \(0\).
With the dummy destination \(7\) (\(d_{7}=10\), zero costs) the north-west corner rule costs \(525\) and the minimum cost rule \(405\).
Exercise 7.2: The potential method
Exercise
We consider the transportation instance with origins \(1,2,3\), destinations \(4,5,6,7\), and the costs, supplies and demands of the tableau:
Questions
-
Build the initial basic feasible solution with the north-west corner rule and compute its cost.
-
Compute the potentials of its basis (\(\pi_7=0\)) and the reduced costs. Is the solution optimal?
-
Run the potential method until the optimal solution, with the rules of (F4).
-
Write the optimal potentials and check that the value of the dual model equals the optimal cost. Is the optimal solution unique?
Solution
We use the rules (F1)–(F5) of the box at the beginning of these exercises.
-
The north-west corner rule gives
step cell amount crossed out \(1\) \((1,4)\) \(15\) column \(4\) \(2\) \((1,5)\) \(5\) column \(5\) \(3\) \((1,6)\) \(10\) row \(1\) \(4\) \((2,6)\) \(15\) row \(2\) \(5\) \((3,6)\) \(20\) column \(6\) \(6\) \((3,7)\) \(5\) row \(3\), column \(7\) \(\bar{x}_{ij}\) \(4\) \(5\) \(6\) \(7\) \(a_i\) \(1\) \(15\) \(5\) \(10\) \(30\) \(2\) \(15\) \(15\) \(3\) \(20\) \(5\) \(25\) \(d_j\) \(15\) \(5\) \(45\) \(5\) with cost \(4 \cdot 15+6 \cdot 5+8 \cdot 10+7 \cdot 15+3 \cdot 20+2 \cdot 5=345\).
-
From \(\pi_7=0\) along the basic cells: \(\pi_{1}=7,\ \pi_{2}=6,\ \pi_{3}=2,\ \pi_{4}=3,\ \pi_{5}=1,\ \pi_{6}=-1,\ \pi_{7}=0\). The reduced costs of the non-basic cells are in the first tableau of the next answer; \(\bar{c}_{25}=-3\) and \(\bar{c}_{24}=-1\) are negative, so the solution is not optimal.
-
The tableaux contain the amounts of the basic cells (blue, bold) and the reduced costs of the other cells; the potentials are on the margins.
Iteration 1
Potentials: \(\pi_{1}=7,\ \pi_{2}=6,\ \pi_{3}=2,\ \pi_{4}=3,\ \pi_{5}=1,\ \pi_{6}=-1,\ \pi_{7}=0\).\(4\) \(5\) \(6\) \(7\) \(\pi_i\) \(1\) \(\mathbf{15}\) \(\mathbf{5}\,\ominus\) \(\mathbf{10}\,\oplus\) \(1\) \(7\) \(2\) \(-1\) \(-3\,\oplus\) \(\mathbf{15}\,\ominus\) \(1\) \(6\) \(3\) \(9\) \(6\) \(\mathbf{20}\) \(\mathbf{5}\) \(2\) \(\pi_j\) \(3\) \(1\) \(-1\) \(0\) -
The negative reduced costs are \(\bar{c}_{25}=-3\), \(\bar{c}_{24}=-1\); the cell \((2,5)\) enters the basis.
-
The cycle is \(\,(2,5)^{+},\ (2,6)^{-},\ (1,6)^{+},\ (1,5)^{-}\).
-
The cells with sign \(-\) have \(\bar{x}_{26}=15\) and \(\bar{x}_{15}=5\): \(\theta=5\), and the cell \((1,5)\) leaves the basis.
-
The cost goes from \(345\) to \(345+5\cdot(-3)=330\).
Iteration 2
Potentials: \(\pi_{1}=7,\ \pi_{2}=6,\ \pi_{3}=2,\ \pi_{4}=3,\ \pi_{5}=4,\ \pi_{6}=-1,\ \pi_{7}=0\).\(4\) \(5\) \(6\) \(7\) \(\pi_i\) \(1\) \(\mathbf{15}\,\ominus\) \(3\) \(\mathbf{15}\,\oplus\) \(1\) \(7\) \(2\) \(-1\,\oplus\) \(\mathbf{5}\) \(\mathbf{10}\,\ominus\) \(1\) \(6\) \(3\) \(9\) \(9\) \(\mathbf{20}\) \(\mathbf{5}\) \(2\) \(\pi_j\) \(3\) \(4\) \(-1\) \(0\) -
The only negative reduced cost is \(\bar{c}_{24}=-1\): the cell \((2,4)\) enters the basis.
-
The cycle is \(\,(2,4)^{+},\ (2,6)^{-},\ (1,6)^{+},\ (1,4)^{-}\).
-
The cells with sign \(-\) have \(\bar{x}_{26}=10\) and \(\bar{x}_{14}=15\): \(\theta=10\), and the cell \((2,6)\) leaves the basis.
-
The cost goes from \(330\) to \(330+10\cdot(-1)=320\).
Iteration 3
Potentials: \(\pi_{1}=7,\ \pi_{2}=5,\ \pi_{3}=2,\ \pi_{4}=3,\ \pi_{5}=3,\ \pi_{6}=-1,\ \pi_{7}=0\).\(4\) \(5\) \(6\) \(7\) \(\pi_i\) \(1\) \(\mathbf{5}\) \(2\) \(\mathbf{25}\) \(1\) \(7\) \(2\) \(\mathbf{10}\) \(\mathbf{5}\) \(1\) \(2\) \(5\) \(3\) \(9\) \(8\) \(\mathbf{20}\) \(\mathbf{5}\) \(2\) \(\pi_j\) \(3\) \(3\) \(-1\) \(0\) - All the reduced costs are non-negative: the basic feasible solution is optimal, with cost \(z=320\).
-
-
The optimal potentials are \(\pi_{1}=7,\ \pi_{2}=5,\ \pi_{3}=2,\ \pi_{4}=3,\ \pi_{5}=3,\ \pi_{6}=-1,\ \pi_{7}=0\), and the dual value is
\[ \sum_{i} a_i\pi_i-\sum_{j} d_j\pi_j=335-15=320, \]equal to the optimal cost. Every non-basic cell has \(\bar{c}_{ij}>0\), so the optimal solution is unique.
From the north-west corner (cost \(345\)) the potential method makes \(2\) pivots and reaches the unique optimum \(\tilde{x}_{14}=5\), \(\tilde{x}_{16}=25\), \(\tilde{x}_{24}=10\), \(\tilde{x}_{25}=5\), \(\tilde{x}_{36}=20\), \(\tilde{x}_{37}=5\), with cost \(320\).
Exercise 7.3: Degeneracy
Exercise
We consider the transportation instance with origins \(1,2,3\) and destinations \(4,5,6\):
Questions
-
Build the north-west corner solution. At which step are a row and a column exhausted at the same time? Which basic cell has value \(0\), and why must it stay in the basis?
-
Run the potential method from this solution, with the rules of (F4).
-
Which pivot is degenerate, and what changes in it? Give the optimal solution and its cost.
Solution
We use the rules (F1)–(F5) of the box at the beginning of these exercises.
-
The north-west corner rule gives
step cell amount crossed out \(1\) \((1,4)\) \(10\) column \(4\) \(2\) \((1,5)\) \(10\) row \(1\) \(3\) \((2,5)\) \(0\) column \(5\) \(4\) \((2,6)\) \(10\) row \(2\) \(5\) \((3,6)\) \(25\) row \(3\), column \(6\) At step \(2\) the cell \((1,5)\) exhausts both row \(1\) and column \(5\). Only the row is crossed out, and the next cell \((2,5)\) of column \(5\) gets the amount \(0\):
\(\bar{x}_{ij}\) \(4\) \(5\) \(6\) \(a_i\) \(1\) \(10\) \(10\) \(20\) \(2\) \(0\) \(10\) \(10\) \(3\) \(25\) \(25\) \(d_j\) \(10\) \(10\) \(35\) The solution, of cost \(310\), is degenerate. The basis needs \(m+n-1=5\) cells: without \((2,5)\) the other cells do not span the \(6\) nodes, and the potentials cannot be computed.
-
Iteration 1
Potentials: \(\pi_{1}=1,\ \pi_{2}=1,\ \pi_{3}=8,\ \pi_{4}=-6,\ \pi_{5}=-2,\ \pi_{6}=0\).\(4\) \(5\) \(6\) \(\pi_i\) \(1\) \(\mathbf{10}\,\ominus\) \(\mathbf{10}\,\oplus\) \(6\) \(1\) \(2\) \(-2\) \(\mathbf{0}\,\ominus\) \(\mathbf{10}\,\oplus\) \(1\) \(3\) \(-8\,\oplus\) \(-3\) \(\mathbf{25}\,\ominus\) \(8\) \(\pi_j\) \(-6\) \(-2\) \(0\) -
The negative reduced costs are \(\bar{c}_{34}=-8\), \(\bar{c}_{35}=-3\), \(\bar{c}_{24}=-2\); the cell \((3,4)\) enters the basis.
-
The cycle is \(\,(3,4)^{+},\ (3,6)^{-},\ (2,6)^{+},\ (2,5)^{-},\ (1,5)^{+},\ (1,4)^{-}\).
-
The cells with sign \(-\) have \(\bar{x}_{36}=25\), \(\bar{x}_{25}=0\) and \(\bar{x}_{14}=10\): \(\theta=0\), and the cell \((2,5)\) leaves the basis.
-
The pivot is degenerate: the solution and its cost \(z=310\) do not change, only the basis does.
Iteration 2
Potentials: \(\pi_{1}=9,\ \pi_{2}=1,\ \pi_{3}=8,\ \pi_{4}=2,\ \pi_{5}=6,\ \pi_{6}=0\).\(4\) \(5\) \(6\) \(\pi_i\) \(1\) \(\mathbf{10}\,\ominus\) \(\mathbf{10}\) \(-2\,\oplus\) \(9\) \(2\) \(6\) \(8\) \(\mathbf{10}\) \(1\) \(3\) \(\mathbf{0}\,\oplus\) \(5\) \(\mathbf{25}\,\ominus\) \(8\) \(\pi_j\) \(2\) \(6\) \(0\) -
The only negative reduced cost is \(\bar{c}_{16}=-2\): the cell \((1,6)\) enters the basis.
-
The cycle is \(\,(1,6)^{+},\ (1,4)^{-},\ (3,4)^{+},\ (3,6)^{-}\).
-
The cells with sign \(-\) have \(\bar{x}_{14}=10\) and \(\bar{x}_{36}=25\): \(\theta=10\), and the cell \((1,4)\) leaves the basis.
-
The cost goes from \(310\) to \(310+10\cdot(-2)=290\).
Iteration 3
Potentials: \(\pi_{1}=7,\ \pi_{2}=1,\ \pi_{3}=8,\ \pi_{4}=2,\ \pi_{5}=4,\ \pi_{6}=0\).\(4\) \(5\) \(6\) \(\pi_i\) \(1\) \(2\) \(\mathbf{10}\) \(\mathbf{10}\) \(7\) \(2\) \(6\) \(6\) \(\mathbf{10}\) \(1\) \(3\) \(\mathbf{10}\) \(3\) \(\mathbf{15}\) \(8\) \(\pi_j\) \(2\) \(4\) \(0\) - All the reduced costs are non-negative: the basic feasible solution is optimal, with cost \(z=290\).
-
-
The first pivot has \(\theta=0\): the cell \((3,4)\) enters with value \(0\) and \((2,5)\) leaves; the solution and its cost do not change, but the new potentials show a negative reduced cost. The optimal solution is \(\tilde{x}_{15}=10\), \(\tilde{x}_{16}=10\), \(\tilde{x}_{26}=10\), \(\tilde{x}_{34}=10\), \(\tilde{x}_{36}=15\), with cost \(290\), and it is unique, since every non-basic cell has \(\bar{c}_{ij}>0\).
The north-west corner solution is degenerate (the basic cell \((2,5)\) has value \(0\)); the first pivot has \(\theta=0\), the second pivot reaches the optimum, of cost \(290\).
Exercise 7.4: The Hungarian algorithm
Exercise
Five workers \(1,2,3,4,5\) must be assigned to five jobs \(6,7,8,9,10\), one job each, at minimum total cost. The costs are:
Questions
-
Reduce the rows and then the columns of the matrix. Which potentials do the reductions give, and which lower bound on the optimal cost?
-
Run the Hungarian algorithm: at each iteration give a maximum set of independent zeros, the lines of (F5) and the adjustment \(\delta\).
-
Give the optimal assignment and its cost, and check that the final potentials are an optimal dual solution.
Solution
We use the rules (F1)–(F5) of the box at the beginning of these exercises.
-
The row minima are \(3,7,1,2,1\), so \(\pi_{1}=3\), \(\pi_{2}=7\), \(\pi_{3}=1\), \(\pi_{4}=2\), \(\pi_{5}=1\):
\[ \begin{array}{c|ccccc} \hline {c_{ij}-\pi_i} & {6} & {7} & {8} & {9} & {10} \\ \hline {1} & {3} & {7} & {7} & {2} & {0} \\ {2} & {4} & {5} & {2} & {0} & {0} \\ {3} & {7} & {0} & {11} & {5} & {10} \\ {4} & {10} & {5} & {8} & {6} & {0} \\ {5} & {2} & {3} & {10} & {5} & {0} \\ \hline \end{array} \]The column minima are then \(2,0,2,0,0\), so \(\pi_{6}=-2\) and \(\pi_{8}=-2\), and the other \(\pi_j\) are \(0\). The dual value \(\sum_i\pi_i-\sum_j\pi_j=18\) is a lower bound on the cost of every assignment.
-
In each matrix the independent zeros are boxed, the lines blue and the cell of \(\delta\) red; the potentials are on the margins.
Iteration 1\(\bar{c}_{ij}\) \(6\) \(7\) \(8\) \(9\) \(10\) \(\pi_i\) \(1\) \(1\) \(7\) \(5\) \(2\) \(\boxed{0}\) \(3\) \(2\) \(2\) \(5\) \(\boxed{0}\) \(0\) \(0\) \(7\) \(3\) \(5\) \(\boxed{0}\) \(9\) \(5\) \(10\) \(1\) \(4\) \(8\) \(5\) \(6\) \(6\) \(0\) \(2\) \(5\) \(\boxed{0}\) \(3\) \(8\) \(5\) \(0\) \(1\) \(\pi_j\) \(-2\) \(0\) \(-2\) \(0\) \(0\) -
A maximum set of independent zeros (boxed) has \(4\) elements: \((1,10)\), \((2,8)\), \((3,7)\), \((5,6)\).
-
The \(4<5\) lines (blue) are the rows \(2\), \(3\) and \(5\) and the column \(10\).
-
The minimum uncovered entry is \(\delta=1\), in the cell \((1,6)\) (red). We subtract it from the uncovered entries and add it to the entries covered twice: \(\pi_i\) grows by \(1\) for the uncovered rows \(1\) and \(4\) and \(\pi_j\) grows by \(1\) for the covered column \(10\). The dual value grows by \(1\cdot(5-4)=1\).
Iteration 2
\(\bar{c}_{ij}\) \(6\) \(7\) \(8\) \(9\) \(10\) \(\pi_i\) \(1\) \(\boxed{0}\) \(6\) \(4\) \(1\) \(0\) \(4\) \(2\) \(2\) \(5\) \(\boxed{0}\) \(0\) \(1\) \(7\) \(3\) \(5\) \(\boxed{0}\) \(9\) \(5\) \(11\) \(1\) \(4\) \(7\) \(4\) \(5\) \(5\) \(\boxed{0}\) \(3\) \(5\) \(0\) \(3\) \(8\) \(5\) \(1\) \(1\) \(\pi_j\) \(-2\) \(0\) \(-2\) \(0\) \(1\) -
A maximum set of independent zeros (boxed) has \(4\) elements: \((1,6)\), \((2,8)\), \((3,7)\), \((4,10)\).
-
The \(4<5\) lines (blue) are the rows \(2\) and \(3\) and the columns \(6\) and \(10\).
-
The minimum uncovered entry is \(\delta=1\), in the cell \((1,9)\) (red). We subtract it from the uncovered entries and add it to the entries covered twice: \(\pi_i\) grows by \(1\) for the uncovered rows \(1\), \(4\) and \(5\) and \(\pi_j\) grows by \(1\) for the covered columns \(6\) and \(10\). The dual value grows by \(1\cdot(5-4)=1\).
Iteration 3
\(\bar{c}_{ij}\) \(6\) \(7\) \(8\) \(9\) \(10\) \(\pi_i\) \(1\) \(0\) \(5\) \(3\) \(\boxed{0}\) \(0\) \(5\) \(2\) \(3\) \(5\) \(\boxed{0}\) \(0\) \(2\) \(7\) \(3\) \(6\) \(\boxed{0}\) \(9\) \(5\) \(12\) \(1\) \(4\) \(7\) \(3\) \(4\) \(4\) \(\boxed{0}\) \(4\) \(5\) \(\boxed{0}\) \(2\) \(7\) \(4\) \(1\) \(2\) \(\pi_j\) \(-1\) \(0\) \(-2\) \(0\) \(2\) -
A maximum set of independent zeros (boxed) has \(5\) elements: \((1,9)\), \((2,8)\), \((3,7)\), \((4,10)\), \((5,6)\).
-
They form an assignment of zero reduced cost: the algorithm stops, and the assignment is optimal.
-
-
The optimal assignment is \(1 \to 9\), \(2 \to 8\), \(3 \to 7\), \(4 \to 10\), \(5 \to 6\), with cost \(5+9+1+2+3=20\). The final potentials give \(\sum_i\pi_i-\sum_j\pi_j=19-(-1)=20\), equal to the cost; all the reduced costs are non-negative, so the potentials are dual feasible and both solutions are optimal. The optimum is unique, as the enumeration of the \(120\) assignments confirms.
The reductions give the bound \(18\); two adjustments, with \(\delta=1\) and \(\delta=1\), lead to the optimal assignment \(1 \to 9\), \(2 \to 8\), \(3 \to 7\), \(4 \to 10\), \(5 \to 6\), of cost \(20\).
Exercise 7.5: Bases, cycles and the minimum cost rule
Exercise
We consider the transportation instance with origins \(1,2,3\) and destinations \(4,5,6\):
and the three sets of cells
Questions
-
Which of \(T_1\), \(T_2\), \(T_3\) are bases? For each basis compute its basic solution and say whether it is feasible.
-
Prove that adding a constant \(k\) to all the costs of row \(i\) adds \(k\,a_i\) to the cost of every feasible solution, so that the optimal solutions do not change. What happens adding \(k\) to a column \(j\)?
-
Build the minimum cost solution and decide with the potentials whether it is optimal. Is the minimum cost rule always optimal?
Solution
We use the rules (F1)–(F5) of the box at the beginning of these exercises.
-
Each set has \(m+n-1=5\) cells, so it is a basis exactly when it contains no cycle (F2).
-
\(T_1\) has no cycle: it is a spanning tree. Leaf by leaf, leaf \(1\) gives \(x_{14}=30\), leaf \(4\) gives \(x_{24}=5\), leaf \(2\) gives \(x_{26}=15\), leaf \(5\) gives \(x_{35}=10\), leaf \(3\) gives \(x_{36}=5\): the basic solution is feasible.
-
\(T_2\) has no cycle: it is a spanning tree. Leaf by leaf, leaf \(1\) gives \(x_{16}=30\), leaf \(4\) gives \(x_{24}=35\), leaf \(2\) gives \(x_{26}=-15\), leaf \(5\) gives \(x_{35}=10\), leaf \(3\) gives \(x_{36}=5\): the value \(-15\) is negative, and the basic solution is not feasible.
-
\(T_3\) contains the cells \((2,5)\), \((3,5)\), \((3,6)\), \((2,6)\), which form the cycle \(2,5,3,6,2\) alternating rows and columns: their columns are linearly dependent, and \(T_3\) is not a basis.
-
-
Let \(c'_{ij}=c_{ij}+k\) for every \(j\) and \(c'_{hj}=c_{hj}\) for \(h \neq i\). For every feasible \(\vet{x}\)
\[ \sum_{h}\sum_{j} c'_{hj}x_{hj}=\sum_{h}\sum_{j} c_{hj}x_{hj}+k\sum_{j} x_{ij}=\sum_{h}\sum_{j} c_{hj}x_{hj}+k\,a_i , \]because row \(i\) of a feasible solution adds up to \(a_i\). All the costs change by the same constant, so the order of the feasible solutions, and the optimal ones, do not change. In the same way, adding \(k\) to column \(j\) adds \(k\,d_j\) to every cost. In the potential method this is a change of \(\pi_i\) by \(k\) (or of \(\pi_j\) by \(-k\)), up to the normalization, and the reduced costs do not change.
-
The minimum cost rule gives
step cell amount crossed out \(1\) \((1,6)\) \(20\) column \(6\) \(2\) \((3,5)\) \(10\) column \(5\) \(3\) \((1,4)\) \(10\) row \(1\) \(4\) \((2,4)\) \(20\) row \(2\) \(5\) \((3,4)\) \(5\) row \(3\), column \(4\) \(\bar{x}_{ij}\) \(4\) \(5\) \(6\) \(a_i\) \(1\) \(10\) \(20\) \(30\) \(2\) \(20\) \(20\) \(3\) \(5\) \(10\) \(15\) \(d_j\) \(35\) \(10\) \(20\) with cost \(175\). Its potentials and reduced costs are
\(4\) \(5\) \(6\) \(\pi_i\) \(1\) \(\mathbf{10}\,\oplus\) \(10\) \(\mathbf{20}\,\ominus\) \(1\) \(2\) \(\mathbf{20}\) \(12\) \(2\) \(3\) \(3\) \(\mathbf{5}\,\ominus\) \(\mathbf{10}\) \(-7\,\oplus\) \(8\) \(\pi_j\) \(-1\) \(7\) \(0\) -
The only negative reduced cost is \(\bar{c}_{36}=-7\): the cell \((3,6)\) enters the basis.
-
The cycle is \(\,(3,6)^{+},\ (3,4)^{-},\ (1,4)^{+},\ (1,6)^{-}\).
-
The cells with sign \(-\) have \(\bar{x}_{34}=5\) and \(\bar{x}_{16}=20\): \(\theta=5\), and the cell \((3,4)\) leaves the basis.
-
The cost goes from \(175\) to \(175+5\cdot(-7)=140\).
The solution is not optimal: one pivot gives the optimum, of cost \(140\). The minimum cost rule looks at one cell at a time and is not always optimal; this instance is a counterexample.
-
\(T_1\) is a basis with a feasible basic solution, \(T_2\) a basis with a negative value, \(T_3\) contains a cycle. The minimum cost solution (cost \(175\)) is not optimal: the optimum is \(140\).
Exercise 7.6: An assignment of maximum profit
Exercise
Four salespeople \(1,2,3,4\) must be assigned to four regions \(5,6,7,8\), one region each. The expected profits \(p_{ij}\) are:
We look for an assignment of maximum total profit.
Questions
-
Turn the problem into an assignment problem of minimum cost with non-negative costs.
-
Solve it with the Hungarian algorithm.
-
Give the assignment of maximum profit and its profit.
Solution
We use the rules (F1)–(F5) of the box at the beginning of these exercises.
-
The largest profit is \(p_{\max}=9\). With \(c_{ij}=9-p_{ij}\) every assignment costs \(4 \cdot 9\) minus its profit, so minimizing the cost maximizes the profit:
\[ \begin{array}{c|cccc} \hline {c_{ij}} & {5} & {6} & {7} & {8} \\ \hline {1} & {0} & {5} & {4} & {8} \\ {2} & {1} & {4} & {6} & {6} \\ {3} & {7} & {8} & {8} & {8} \\ {4} & {7} & {7} & {3} & {1} \\ \hline \end{array} \] -
The row minima are \(0,1,7,1\) and then the column minima \(0,1,1,0\):
Iteration 1\(\bar{c}_{ij}\) \(5\) \(6\) \(7\) \(8\) \(\pi_i\) \(1\) \(\boxed{0}\) \(4\) \(3\) \(8\) \(0\) \(2\) \(0\) \(2\) \(4\) \(5\) \(1\) \(3\) \(0\) \(\boxed{0}\) \(0\) \(1\) \(7\) \(4\) \(6\) \(5\) \(1\) \(\boxed{0}\) \(1\) \(\pi_j\) \(0\) \(-1\) \(-1\) \(0\) -
A maximum set of independent zeros (boxed) has \(3\) elements: \((1,5)\), \((3,6)\), \((4,8)\).
-
The \(3<4\) lines (blue) are the rows \(3\) and \(4\) and the column \(5\).
-
The minimum uncovered entry is \(\delta=2\), in the cell \((2,6)\) (red). We subtract it from the uncovered entries and add it to the entries covered twice: \(\pi_i\) grows by \(2\) for the uncovered rows \(1\) and \(2\) and \(\pi_j\) grows by \(2\) for the covered column \(5\). The dual value grows by \(2\cdot(4-3)=2\).
Iteration 2
\(\bar{c}_{ij}\) \(5\) \(6\) \(7\) \(8\) \(\pi_i\) \(1\) \(\boxed{0}\) \(2\) \(1\) \(6\) \(2\) \(2\) \(0\) \(\boxed{0}\) \(2\) \(3\) \(3\) \(3\) \(2\) \(0\) \(\boxed{0}\) \(1\) \(7\) \(4\) \(8\) \(5\) \(1\) \(\boxed{0}\) \(1\) \(\pi_j\) \(2\) \(-1\) \(-1\) \(0\) -
A maximum set of independent zeros (boxed) has \(4\) elements: \((1,5)\), \((2,6)\), \((3,7)\), \((4,8)\).
-
They form an assignment of zero reduced cost: the algorithm stops, and the assignment is optimal.
-
-
The optimal assignment is \(1 \to 5\), \(2 \to 6\), \(3 \to 7\), \(4 \to 8\), with cost \(13\) and profit
\[ 9+5+1+8=23=4 \cdot 9-13. \]The enumeration of the \(24\) assignments confirms that it is the unique optimum.
With \(c_{ij}=9-p_{ij}\) the Hungarian algorithm gives \(1 \to 5\), \(2 \to 6\), \(3 \to 7\), \(4 \to 8\), with profit \(23\).