Cycle method

The cycle method or stepping stone method is a numerical method with which one can solve a standard transport problem (given the initial basic solution ) .

There is a certain number of providers and a certain number of recipients for a good . In the standard case, the total amount requested is equal to the total offered. There are costs for the transport of a unit between and . The problem is to determine the quantity delivered from to in such a way that the overall transport costs are minimized. ${\displaystyle n}$ ${\displaystyle A_{i}}$ ${\displaystyle (i=1,\dotsc ,n)}$ ${\displaystyle m}$ ${\displaystyle B_{j}}$ ${\displaystyle (j=1,\dotsc ,m)}$ ${\displaystyle x_{ij}}$ ${\displaystyle A_{i}}$ ${\displaystyle B_{j}}$ ${\displaystyle c_{ij}}$ ${\displaystyle A_{i}}$ ${\displaystyle B_{j}}$ ${\displaystyle x_{ij}}$

Since this is an improvement of method is, first, for having an opening procedure (. As the matrix minimum procedure , the north-west corner method , the row or column order method , the row-column succession , the bird's approximation method or the Russell' the approximation method ) determines a permissible initial basic solution . Variables of the basic solution that were set to zero a priori in the opening procedure are the non-basic variables, the rest are the basic variables of the underlying system of equations. The stepping stone method then iteratively reduces the total costs by replacing a non-basic variable with a basic variable. If no further improvement can be achieved, an optimal solution has been found. ${\displaystyle x\in \mathbb {R} ^{mn}}$

history

Abraham Charnes and William W. Cooper are considered to be the originators of the cycle method .

Procedure

The optimization process is carried out iteratively. In each step, all non-basic variables are checked with regard to the cost reduction potential. For each non-basic variable it is analyzed how the total costs would change if a unit of the good were to be transported from to . For this purpose, an elementary circle is determined for the cell of each non- basic variable together with the cells of the basic variable. The cells to form an elementary circle if two consecutive cells and lie in the same row or column of the tableau and there are at most two cells of the elementary circle in each column and row. Let us now determine the cells of the basic variable which, together with the cell of the non- basic variable, describe an elementary circle. Then the total costs can be improved by each additional unit transported from to . If it is positive, this would lead to an increase in the total costs, if it is zero, the total costs would not change. In order to arrive at the optimal solution with as few iterations as possible, the non- basic variable with the most negative is therefore included as the new basic variable and replaced with the smallest basic variable in terms of value , the cost of which was included in the determination of with a negative factor. The non- base variable becomes the new base variable with the value of and becomes the new non- base variable with the value zero. So that the new basic solution remains permissible, the remaining basic variables of the elementary circle are increased by the value of the original basic variable or reduced (if the associated costs were included in the determination of with a negative factor). All other variables remain unchanged. The process is repeated until all (to be determined anew in each iteration) are greater than or equal to zero, i.e. the total costs can no longer be reduced and the solution is therefore optimal. ${\displaystyle x_{ij}}$ ${\displaystyle A_{i}}$ ${\displaystyle B_{j}}$ ${\displaystyle (i,j)}$ ${\displaystyle x_{ij}}$ ${\displaystyle z_{1}}$ ${\displaystyle z_{k}}$ ${\displaystyle (k\geq 5)}$ ${\displaystyle z_{1}=z_{k}}$ ${\displaystyle z_{i}}$ ${\displaystyle z_{i+1}}$ ${\displaystyle (i,o),(p,o),(p,q),\cdots ,(v,j)}$ ${\displaystyle (i,j)}$ ${\displaystyle x_{ij}}$ ${\displaystyle k_{ij}:=c_{ij}-c_{io}+c_{po}-c_{pq}+\cdots -c_{vj}}$ ${\displaystyle A_{i}}$ ${\displaystyle B_{j}}$ ${\displaystyle k_{ij}}$ ${\displaystyle k_{ij}}$ ${\displaystyle x_{ij}}$ ${\displaystyle k_{ij}}$ ${\displaystyle x_{ab}}$ ${\displaystyle k_{ij}}$ ${\displaystyle x_{ij}}$ ${\displaystyle x_{ab}}$ ${\displaystyle x_{ab}}$ ${\displaystyle x_{ab}}$ ${\displaystyle k_{ij}}$ ${\displaystyle x_{kl}}$ ${\displaystyle k_{ij}}$

example

There is the following transport problem, summarized in a table, whereby there are two offers and and three requests for requests , and and here denotes the quantity delivered by to . ${\displaystyle A_{1}}$ ${\displaystyle A_{2}}$ ${\displaystyle B_{1}}$ ${\displaystyle B_{2}}$ ${\displaystyle B_{3}}$ ${\displaystyle x_{ij}}$ ${\displaystyle i}$ ${\displaystyle j}$

${\displaystyle {\begin{array}{c|ccc|c}&B_{1}&B_{2}&B_{3}\\\hline A_{1}&x_{11}&x_{12}&x_{13}&12\\A_{2}&x_{21}&x_{22}&x_{23}&8\\\hline &4&10&6&20\end{array}}}$

The costs involved in transporting a unit from to are shown in the table below. ${\displaystyle c_{ij}}$ ${\displaystyle i}$ ${\displaystyle j}$

${\displaystyle {\begin{array}{c|ccc|c}c_{ij}&B_{1}&B_{2}&B_{3}\\\hline A_{1}&7&4&3&12\\A_{2}&5&5&6&8\\\hline &4&10&6&20\end{array}}}$

For practical purposes, the transport quantities are entered in the table and the corresponding costs are listed in each cell at the top left. The north-west corner method was used here as an initial solution. So it turns out

${\displaystyle {\begin{array}{c|ccc|c}&B_{1}&B_{2}&B_{3}\\\hline A_{1}&7/4&4/8&3/0&12\\A_{2}&5/0&5/2&6/6&8\\\hline &4&10&6&20\end{array}}}$

and you get a total cost of

${\displaystyle 4\cdot 7+8\cdot 4+0\cdot 3+0\cdot 5+2\cdot 5+6\cdot 6=106}$.

The content of cell 13 (which should mean: (A1 | B3)) is now increased by one as an experiment. You can see how the changes propagate in a circle.

${\displaystyle {\begin{array}{c|ccc|c}&B_{1}&B_{2}&B_{3}\\\hline A_{1}&7/4&4/\,{\mathit {-1}}\;8&3/\,{\mathit {+1}}\;\mathbf {0} &12\\A_{2}&5/0&5/\,{\mathit {+1}}\;2&6/\,{\mathit {-1}}\;6&8\\\hline &4&10&6&20\end{array}}}$

The costs per unit also change:

${\displaystyle dc_{13}=+3-4+5-6=-2.}$

So the costs would decrease by 2 euros if one unit were to be transported. ${\displaystyle A_{1}}$ ${\displaystyle B_{3}}$

An analysis of cell 21 shows:

${\displaystyle {\begin{array}{c|ccc|c}&B_{1}&B_{2}&B_{3}\\\hline A_{1}&7/\,{\mathit {-1}}\;4&4/\,{\mathit {+1}}\;8&3/0&12\\A_{2}&5/\,{\mathit {+1}}\;0&5/\,{\mathit {-1}}\;2&6/6&8\\\hline &4&10&6&20\end{array}}}$

The cost per unit will change

${\displaystyle dc_{21}=+5-5+4-7=-3}$.

So the costs would be reduced by 3 euros if one unit were to be transported. It can be seen that the latter change reduces costs more. As much as allowed is now transferred to cell 21, the signs of the ones indicating whether the amount is to be added or subtracted. ${\displaystyle A_{2}}$ ${\displaystyle B_{1}}$

${\displaystyle {\begin{array}{c|ccc|c}&B_{1}&B_{2}&B_{3}\\\hline A_{1}&7/2&4/10&3/0&12\\A_{2}&5/2&5/0&6/6&8\\\hline &4&10&6&20\end{array}}}$

A maximum of two units could only be transferred into cell 21, because otherwise cell 22 would have become negative. Cell 21 is now a basic variable, cell 22 a non-basic variable.

All non-base variables are now examined again. For cell 13 there is now the circle of cells 13 - 11 - 21 - 23, because cell 22 is a non-basic variable and cannot be changed simultaneously with cell 13. So cell 22 is skipped. You then get

${\displaystyle dc_{13}=3-7+5-6=-5}$

and

${\displaystyle dc_{22}=5-4+7-5>0}$.

Here the costs increase when changing cell 22. So cell 13 is changed. A maximum of two units can be transferred to cell 13 and you now get

${\displaystyle {\begin{array}{c|ccc|c}&B_{1}&B_{2}&B_{3}\\\hline A_{1}&7/0&4/10&3/2&12\\A_{2}&5/4&5/0&6/4&8\\\hline &4&10&6&20\end{array}}}$

All non-base variables are examined again. For cell 11, the result is the circle of cells 11-13-23-21, because cell 22 is a non-basic variable and is skipped. You then get

${\displaystyle dc_{11}=7-3+6-5>0}$.

The non-base variable in cell 22, however, generates

${\displaystyle dc_{22}=5-4+3-6=-2}$.

So cell 22 is changed. A maximum of four units can be transferred to cell 22 and one receives

${\displaystyle {\begin{array}{c|ccc|c}&B_{1}&B_{2}&B_{3}\\\hline A_{1}&7/0&4/6&3/6&12\\A_{2}&5/4&5/4&6/0&8\\\hline &4&10&6&20\end{array}}}$

A new iteration only results in cost increases, so the process is over. You get a total cost of

${\displaystyle 0\cdot 7+6\cdot 4+6\cdot 3+4\cdot 5+4\cdot 5+0\cdot 6=82}$

in contrast to 106 of the starting solution.

Remarks

• If the total quantity demanded is less than the total quantity offered , the transport problem can be transformed into a standard transport model by introducing a fictitious demander who asks for the excess supply and has transport costs for all providers and thus also solved with the stepping stone method . ${\displaystyle B_{m+1}}$ ${\displaystyle c_{i,m+1}=0}$ ${\displaystyle A_{i}}$
• If, in the optimal solution, a possible change in costs when including the variable is zero, this means that the value of the associated non-basic variable can be exchanged for that of a basic variable without the total costs changing and the optimal solution therefore not being clear. ${\displaystyle k_{ij}}$ ${\displaystyle x_{ij}}$
• A similar method for improving an initial basic solution and finding the optimal solution is the MODI method . The cost changes are determined with less computational effort (but identical values) than with the stepping stone method. ${\displaystyle k_{ij}}$
• If there are more than one negative , the associated non-basic variable that leads to a maximum improvement in the total cost can be selected instead of the largest in terms of amount, or one of them can be selected at random. ${\displaystyle k_{ij}}$

Individual evidence

1. ^ Theodor Ellinger: Operations Research: An Introduction , Edition 6, p. 79.