MODI method

The modified distribution method ( MODI method ), also known as the potential method , uv method or transport algorithm, is a numerical method with which (given a given initial basic solution ) a standard transport problem can be optimally solved.

Procedure

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,...,n)}$ ${\displaystyle m}$ ${\displaystyle B_{j}}$ ${\displaystyle (j=1,...,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 method , a permissible initial basic solution is first determined using an opening method (e.g. the matrix minimum method , the north-west corner method or Vogel's approximation method ) . Variables of the basic solution, which were initially set to zero in the opening procedure, are the non- basic variables , the rest are the basic variables of the underlying system of equations. The MODI 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}}$

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 by which value the total costs would change if a unit of the good were to be transported from to . For this purpose, the cost change is also calculated for the cell of each non- basic variable, with the and iteratively calculated with the equation beforehand and exactly one or equal to zero being set and only corresponding costs of basic variables being used for the calculation. ${\displaystyle x_{ij}}$ ${\displaystyle k_{ij}}$ ${\displaystyle A_{i}}$ ${\displaystyle B_{j}}$ ${\displaystyle (i,j)}$ ${\displaystyle x_{ij}}$ ${\displaystyle k_{ij}=c_{ij}-u_{i}-v_{j}}$ ${\displaystyle u_{1},\cdots ,u_{m}}$ ${\displaystyle v_{1},\cdots ,v_{n}}$ ${\displaystyle u_{i}+v_{j}=c_{ij}}$ ${\displaystyle u_{i}}$ ${\displaystyle v_{j}}$ ${\displaystyle c_{ij}}$ ${\displaystyle x_{ij}}$

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 included as the new basic variable. For this purpose, an elementary circle is determined for the associated cell of the transport table together with the cells of the basic variables . 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 variables, which together with the cell describe an elementary circle. Now, as with the Stepping Stone method, the value is alternately subtracted from the first basic variable along the elementary circle and added to the next basic variable until the cell is reached. It is the smallest value of the basic variables, one of which is to be subtracted. This basic variable becomes a new non-basic variable and is replaced by with value in the new basic solution. 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 k_{ij}}$ ${\displaystyle k_{ij}}$ ${\displaystyle x_{ij}}$ ${\displaystyle k_{ij}}$ ${\displaystyle (i,j)}$ ${\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 x_{io}}$ ${\displaystyle h}$ ${\displaystyle x_{po}}$ ${\displaystyle (i,j)}$ ${\displaystyle h}$ ${\displaystyle h}$ ${\displaystyle x_{ij}}$ ${\displaystyle h}$ ${\displaystyle k_{ij}}$

Remarks

• If the total quantity demanded is less than the total quantity offered , the transport problem can be transformed into a standard transport model and thus also solved with the MODI method by introducing a fictitious demander who asks for the excess supply and has transport costs for all providers . ${\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 stepping stone method . The cost changes are determined with more computational effort (but identical values) than with the MODI 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}}$

example

There is the following transport problem, summarized in a table, in which the providers and the quantities offer 12 or 8 and three buyers , and the quantities 4, 10 and 6 are requested. In the table on the left, the denotes the quantity to be delivered from to . The table on the right contains the costs that arise for the transport of a unit from to . ${\displaystyle A_{1}}$ ${\displaystyle A_{2}}$ ${\displaystyle B_{1}}$ ${\displaystyle B_{2}}$ ${\displaystyle B_{3}}$ ${\displaystyle x_{ij}}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle c_{ij}}$ ${\displaystyle x_{ij}}$ ${\displaystyle i}$ ${\displaystyle j}$

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

The north-west corner procedure is used as the opening procedure . This results in the following, not yet optimal, initial solution:
${\displaystyle {\begin{array}{c|ccc}x_{ij}&4&10&6\\\hline 12&4&8&\\8&&2&6\\\end{array}}}$

To determine the and the costs of the basic variables are required: ${\displaystyle v_{j}}$ ${\displaystyle u_{i}}$
${\displaystyle {\begin{array}{c|ccc|c}c_{ij}&B_{1}&B_{2}&B_{3}&\\\hline A_{1}&7&4&&u_{1}\\A_{2}&&5&6&u_{2}\\\hline &v_{1}&v_{2}&v_{3}&\\\end{array}}}$

Add to it . With and the cost of basic variables can now be represented by the formula , the value of compute: . With and now can calculate: . And can also now be calculated. With the and and from the above cost table, the formula can now be used to calculate the cost change that results from the transport of one unit via the non-base variables : ${\displaystyle v_{3}=0}$ ${\displaystyle v_{3}}$ ${\displaystyle c_{23}}$ ${\displaystyle x_{23}}$ ${\displaystyle c_{ij}=u_{i}+v_{j}}$ ${\displaystyle u_{2}}$ ${\displaystyle u_{2}=c_{23}-v_{3}=6-0=6}$ ${\displaystyle u_{2}}$ ${\displaystyle c_{22}}$ ${\displaystyle v_{2}}$ ${\displaystyle v_{2}=c_{22}-u_{2}=5-6=-1}$ ${\displaystyle u_{1}=4-(-1)=5}$ ${\displaystyle v_{1}=7-5=2}$ ${\displaystyle v_{j}}$ ${\displaystyle u_{i}}$ ${\displaystyle c_{ij}}$ ${\displaystyle k_{ij}=c_{ij}-u_{i}-v_{j}}$ ${\displaystyle x_{ij}}$
${\displaystyle {\begin{array}{c|ccc|c}&&&&u_{i}\\\hline &&&k_{13}&5\\&k_{21}&&&6\\\hline v_{j}&2&-1&0&\\\end{array}}}$

So is and . So with both there would be a cost reduction. Since the savings are greater, we choose this non-basic variable and determine the elementary circle for the cell . This is and . A maximum of two units can now be transported over, otherwise it would be negative: the two units are now alternately added or subtracted along the elementary circle. The basic variables and non- basic variables are : ${\displaystyle k_{13}=c_{13}-u_{1}-v_{3}=3-5-0=-2}$ ${\displaystyle k_{21}=c_{21}-u_{2}-v_{1}=5-6-2=-3}$ ${\displaystyle x_{ij}}$ ${\displaystyle x_{21}}$ ${\displaystyle (2,1)}$ ${\displaystyle (2,1),(2,2),(1,2)}$ ${\displaystyle (1,1)}$ ${\displaystyle x_{21}}$ ${\displaystyle x_{22}}$ ${\displaystyle x_{21}}$ ${\displaystyle x_{22}}$
${\displaystyle {\begin{array}{c|ccc}x_{ij}&4&10&6\\\hline 12&2&10&\\8&2&&6\\\end{array}}}$

Now you have to calculate again as above with the costs from the above table of the basic variables and by setting the others and with the formula : ${\displaystyle c_{ij}}$ ${\displaystyle v_{3}=0}$ ${\displaystyle v_{j}}$ ${\displaystyle u_{i}}$ ${\displaystyle c_{ij}=u_{i}+v_{j}}$
${\displaystyle {\begin{array}{c|ccc|c}c_{ij}&&&&u_{i}\\\hline &7&4&&8\\&5&&6&6\\\hline v_{j}&-1&-4&0&\\\end{array}}}$

With the , and the cost changes and can now be calculated again: and analogously . By transporting a unit over , a cost reduction can be achieved again. The elementary circle to the cell is: and . So again a maximum of two units (paths ) can be shifted along the elementary circle and the new basic solution is created: ${\displaystyle v_{j}}$ ${\displaystyle u_{i}}$ ${\displaystyle c_{ij}}$ ${\displaystyle k_{13}}$ ${\displaystyle k_{22}}$ ${\displaystyle k_{13}=c_{13}-u_{1}-v_{3}=3-8-0=-5}$ ${\displaystyle k_{22}=5+4-6=3}$ ${\displaystyle x_{13}}$ ${\displaystyle (1,3)}$ ${\displaystyle (1,3),(1,1),(2,1)}$ ${\displaystyle (2,3)}$ ${\displaystyle x_{13}=2}$
${\displaystyle {\begin{array}{c|ccc}x_{ij}&4&10&6\\\hline 12&&10&2\\8&4&&4\\\end{array}}}$

Now for the determination of and the and must be determined again. This is repeated until in one iteration all of them are not negative and thus an optimal solution, or if all are greater than zero, the optimal solution has been found. The result is the same solution as in the example for the stepping stone method . ${\displaystyle k_{11}}$ ${\displaystyle k_{22}}$ ${\displaystyle v_{j}}$ ${\displaystyle u_{i}}$ ${\displaystyle k_{ij}}$ ${\displaystyle k_{ij}}$