Row-column succession

The row-column succession is a heuristic method from Operations Research that provides a valid initial solution for the transport problem. The optimization algorithm of the transport problem starts from this solution. The costs are already taken into account when calculating the initial ( basic solution ).

algorithm

The algorithm begins by occupying the most cost-effective element of the transport cost matrix to the maximum. In the matrix, the supply is shown in the far right column and the demand in the bottom row. If, after selecting the first element, the line still has an excess supply, the next cheapest element in the line is selected. If the column still has a demand excess, then the next cheapest element in the column is used. This continues until there is no more excess.

Examples

${\displaystyle {\begin{array}{c|cccc|c}&B_{1}&B_{2}&B_{3}&B_{4}&{\text{Angebot}}\\\hline A_{1}&{\color {red}{\boldsymbol {4}}}_{4}^{(6)}&6&{\color {red}{\boldsymbol {2}}}_{6}^{(5)}&3&10\\A_{2}&8&{\color {red}{\boldsymbol {1}}}_{7}^{(1)}&7&{\color {red}{\boldsymbol {5}}}_{1}^{(2)}&8\\A_{3}&{\color {red}{\boldsymbol {3}}}_{14}^{(7)}&2&2&4&14\\A_{4}&7&8&{\color {red}{\boldsymbol {4}}}_{3}^{(4)}&{\color {red}{\boldsymbol {2}}}_{9}^{(3)}&12\\\hline {\text{Nachfrage}}&18&7&9&10&44\\\end{array}}}$

The cost of the initial solution is. ${\displaystyle K}$

${\displaystyle K=\underbrace {1\cdot 7} _{(1)}+\underbrace {5\cdot 1} _{(2)}+\underbrace {2\cdot 9} _{(3)}+\underbrace {4\cdot 3} _{(4)}+\underbrace {2\cdot 6} _{(5)}+\underbrace {4\cdot 4} _{(6)}+\underbrace {3\cdot 14} _{(7)}=112}$

Since after step 4 there are two items available with the same transportation costs, there are two solutions.

${\displaystyle {\begin{array}{c|cccc|c}&B_{1}&B_{2}&B_{3}&B_{4}&{\text{Angebot}}\\\hline A_{1}&{\color {red}{\boldsymbol {4}}}_{10}^{(7)}&6&2&3&10\\A_{2}&8&{\color {red}{\boldsymbol {1}}}_{7}^{(1)}&7&{\color {red}{\boldsymbol {5}}}_{1}^{(2)}&8\\A_{3}&{\color {red}{\boldsymbol {3}}}_{8}^{(6)}&2&{\color {red}{\boldsymbol {2}}}_{6}^{(5)}&4&14\\A_{4}&7&8&{\color {red}{\boldsymbol {4}}}_{3}^{(4)}&{\color {red}{\boldsymbol {2}}}_{9}^{(3)}&12\\\hline {\text{Nachfrage}}&18&7&9&10&44\\\end{array}}}$

The cost of the initial solution is ${\displaystyle K}$

${\displaystyle K=\underbrace {1\cdot 7} _{(1)}+\underbrace {5\cdot 1} _{(2)}+\underbrace {2\cdot 9} _{(3)}+\underbrace {4\cdot 3} _{(4)}+\underbrace {2\cdot 6} _{(5)}+\underbrace {4\cdot 1} _{(6)}0+\underbrace {3\cdot 8} _{(7)}=118}$.

Disadvantage of this procedure

At first there is still a very high degree of freedom. Allocations are possible for an assignment . However, this degree of freedom is restricted very quickly, so that in the end very unfavorable assignments have to be accepted because restrictions have already been fulfilled. ${\displaystyle m\times n}$

literature

• Heiner Müller-Merbach: Operations Research: Methods and Models of Optimal Planning , 1971, Franz Vahlen, p. 310.