Matrix minimum method

The matrix minimum method (or ascending index method , ranking method ) is an opening method from Operations Research for solving transport problems . The name is derived from the consideration of the cost matrix, in which the respective minimum is used for the next iteration of the algorithm .

The matrix minimum method always provides a permissible solution (including the initial or basic solution ) for the underlying transport problem , which, however, is not necessarily optimal.

algorithm

Establishing the cost matrix

The aim in solving the transport problem is to transport goods that are offered in large quantities at locations as inexpensively as possible to the places of demand where the quantities are required. The sum of the units offered corresponds to the sum of the units requested in the classic transport system. ${\displaystyle m}$ ${\displaystyle (A_{1},A_{2},\dotsc ,A_{m})}$ ${\displaystyle a_{i}{\text{ }}(i=1,\dotsc ,m)}$ ${\displaystyle n}$ ${\displaystyle (B_{1},B_{2},\dotsc ,B_{n})}$ ${\displaystyle b_{i}\ (i=1,\dotsc ,n)}$

A matrix C can be created from the information on the transport problem, which shows the costs between the locations and in monetary units (MU) per unit transported. In addition, the supply and demand quantities can be included in this so-called cost matrix. ${\displaystyle c_{ij}}$ ${\displaystyle A_{i}{\text{ }}(i=1,\dotsc ,m)}$ ${\displaystyle B_{j}\ (j=1,\dotsc ,n)}$

${\displaystyle {\begin{array}{c|cccccc|c}&B_{1}&B_{2}&\dots &B_{j}&\dots &B_{n}&{\text{Angebot}}\\\hline A_{1}&c_{11}&c_{12}&\dots &c_{1j}&\dots &c_{1n}&a_{1}\\A_{2}&c_{21}&c_{22}&\dots &c_{2j}&\dots &c_{2n}&a_{2}\\\vdots &\vdots &\vdots &&\vdots &&\vdots &\vdots \\A_{i}&c_{i1}&c_{i2}&\dots &c_{ij}&\dots &c_{in}&a_{i}\\\vdots &\vdots &\vdots &&\vdots &&\vdots &\vdots \\A_{m}&c_{m1}&c_{m2}&\dots &c_{mj}&\dots &c_{mn}&a_{m}\\\hline {\text{Nachfrage}}&b_{1}&b_{2}&\dots &b_{j}&\dots &b_{n}&{\text{Summe}}\\\end{array}}}$

The 1st iteration

The following steps to create the cost matrix are:

1. Find the lowest cost in the cost matrix and . ${\displaystyle c_{uv}=\min(c_{ij})}$ ${\displaystyle (i=1,\dotsc ,m}$ ${\displaystyle j=1,\dotsc ,n)}$
2. Determination of the maximum possible transport quantity in this way. ${\displaystyle x_{uv}=\min(a_{u},b_{v})}$
3. Subtraction of the determined transport quantity in the supply of the u-row and in the demand of the v-column. Moving units from place to place is now part of the solution. ${\displaystyle x_{uv}}$ ${\displaystyle A_{u}}$ ${\displaystyle B_{v}}$
4. Deletion of a row or column as soon as the supply has been exhausted or the demand has been satisfied.
5. Creation of the new cost matrix . ${\displaystyle C_{1}}$

Note on step 1: If there is more than one element, the choice of the matrix element from this set over which the iteration is carried out is basically free. In order to reach a solution more quickly using the algorithm, it often makes sense to carry out the iteration where the maximum possible transport quantity is greatest. ${\displaystyle \min(c_{ij})}$

The further iterations

The further iterations take the last created new cost matrix as a basis. The h-th iteration is based on the cost matrix . The iteration steps themselves are the same as for the first iteration. If the cost matrix reaches the dimension , i.e. there are neither columns nor rows left, the algorithm has reached its termination criterion and the basic solution has been found. ${\displaystyle C_{h-1}}$ ${\displaystyle (0\times 0)}$

example

Creation of the cost matrix

The matrix minimum method is to be explained using the following example.

Starting from four supply locations up to the supply quantities: ${\displaystyle A_{1}}$ ${\displaystyle A_{4}}$

• ${\displaystyle a_{1}=10}$
• ${\displaystyle a_{2}=8}$
• ${\displaystyle a_{3}=14}$
• ${\displaystyle a_{4}=12}$

and four places of demand up to with the demand quantities: ${\displaystyle B_{1}}$ ${\displaystyle B_{4}}$

• ${\displaystyle b_{1}=18}$
• ${\displaystyle b_{2}=7}$
• ${\displaystyle b_{3}=9}$
• ${\displaystyle b_{4}=10}$

as well as the information on the respective transport costs, the following cost matrix C is created:

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

The 1st iteration

A basic solution is now obtained from this cost matrix in several steps. In the first iteration, the following happens:

1. Find the lowest cost in the cost matrix . Here is . ${\displaystyle c_{uv}=\min(c_{ij})}$ ${\displaystyle (i,j=1,\dotsc ,4)}$ ${\displaystyle \min(c_{ij})=c_{22}=1}$
2. Determination of the maximum possible transport quantity in this way. So in the example . ${\displaystyle x_{uv}=\min(a_{u},b_{v})}$ ${\displaystyle \min(a_{2},b_{2})=\min(8,7)=7}$
3. Subtraction of the determined transport quantity in the supply of the u-row and in the demand of the v-column. So it is new that and is. The transport of 7 units from site to site is now part of the solution. ${\displaystyle a_{2}=8-7=1}$ ${\displaystyle b_{2}=7-7=0}$ ${\displaystyle A_{2}}$ ${\displaystyle B_{2}}$
4. Deletion of a row or column as soon as the supply has been exhausted or the demand has been satisfied. The local demand is now satisfied. The second column is therefore deleted. ${\displaystyle b_{2}=0}$ ${\displaystyle B_{2}}$
5. Creation of the new cost matrix . ${\displaystyle C_{1}}$

The new cost matrix looks like this: ${\displaystyle C_{1}}$

${\displaystyle {\begin{array}{c|ccc|c}&B_{1}&B_{3}&B_{4}&{\text{Angebot}}\\\hline A_{1}&4&2&3&10\\A_{2}&8&7&5&1\\A_{3}&3&2&4&14\\A_{4}&7&4&2&12\\\hline {\text{Nachfrage}}&18&9&10&37\\\end{array}}}$

The further iterations

The example can now be continued through to the end. Iteration over several elements is already possible in the second step, there is. At this point, the choice of the next element from this set is basically free. In the following, however, it is used because this is where the maximum transport quantity is greatest. ${\displaystyle \min(c_{ij})=c_{13}=c_{33}=c_{44}=2}$ ${\displaystyle c_{44}}$

There is no single calculation of the iterations here. The further cost matrices and solution components shown below are intended to ensure the traceability of the example.

The 2nd iteration

Transporting 10 units from site to site becomes part of the solution. Is as follows: ${\displaystyle A_{4}}$ ${\displaystyle B_{4}}$ ${\displaystyle C_{2}}$

${\displaystyle {\begin{array}{c|cc|c}&B_{1}&B_{3}&{\text{Angebot}}\\\hline A_{1}&4&2&10\\A_{2}&8&7&1\\A_{3}&3&2&14\\A_{4}&7&4&2\\\hline {\text{Nachfrage}}&18&9&27\\\end{array}}}$

The 3rd iteration

The transport of 9 units from site to site becomes part of the solution. Is as follows: ${\displaystyle A_{1}}$ ${\displaystyle B_{3}}$ ${\displaystyle C_{3}}$

${\displaystyle {\begin{array}{c|c|c}&B_{1}&{\text{Angebot}}\\\hline A_{1}&4&1\\A_{2}&8&1\\A_{3}&3&14\\A_{4}&7&2\\\hline {\text{Nachfrage}}&18&18\\\end{array}}}$

The 4th iteration

The transport of 14 units from site to site becomes part of the solution. Is as follows: ${\displaystyle A_{3}}$ ${\displaystyle B_{1}}$ ${\displaystyle C_{4}}$

${\displaystyle {\begin{array}{c|c|c}&B_{1}&{\text{Angebot}}\\\hline A_{1}&4&1\\A_{2}&8&1\\A_{4}&7&2\\\hline {\text{Nachfrage}}&4&4\\\end{array}}}$

The 5th iteration

Transporting 1 unit from site to site becomes part of the solution. Is as follows: ${\displaystyle A_{1}}$ ${\displaystyle B_{1}}$ ${\displaystyle C_{5}}$

${\displaystyle {\begin{array}{c|c|c}&B_{1}&{\text{Angebot}}\\\hline A_{2}&8&1\\A_{4}&7&2\\\hline {\text{Nachfrage}}&3&3\\\end{array}}}$

The 6th iteration

The transport of 2 units from site to site becomes part of the solution. Is as follows: ${\displaystyle A_{4}}$ ${\displaystyle B_{1}}$ ${\displaystyle C_{6}}$

${\displaystyle {\begin{array}{c|c|c}&B_{1}&{\text{Angebot}}\\\hline A_{2}&8&1\\\hline {\text{Nachfrage}}&1&1\\\end{array}}}$

The 7th iteration

Transporting 1 unit from site to site becomes part of the solution. has the dimension with which the termination criterion of the algorithm is reached. ${\displaystyle A_{2}}$ ${\displaystyle B_{1}}$ ${\displaystyle C_{7}}$ ${\displaystyle (0\times 0)}$

Evaluation of results

With the matrix minimum method, a basic solution has now been found that can be summarized as follows:

Offer location	Place of demand	Transport quantity	price per unit	total price
A 2	B 2	7 units	1 GE	7 GE
A 4	B 4	10 units	2 GE	20 GE
A 1	B 3	9 units	2 GE	18 GE
A 3	B 1	14 units	3 GE	42 GE
A 1	B 1	1 units	4 GE	4 GE
A 4	B 1	2 units	7 GE	14 GE
A 2	B 1	1 units	8 GE	8 GE
total		44 units		113 GE

Whether this is also the optimal solution would have to be checked in the following using the MODI method , for example.

advantages

Due to the simple algorithm that only uses the transport costs as a selection criterion, the matrix minimum method is easy to apply and program. In addition, the complexity of the algorithm is comparatively low, which leads to short computing times for computer programs.

disadvantage

The matrix minimum method provides a valid basic solution for the transport problem, but not necessarily the optimal solution. This means that a subsequent improvement of the solution may be necessary, which sometimes increases the effort required to solve the problem considerably.

application

As an opening heuristic, the matrix minimum method generally makes sense when all that is required is any admissible solution for a transport problem. It is therefore often used to determine an initial solution before the solution is optimized using the MODI method or the cycle method (stepping stone method).

swell

1. ↑ W. Domschke. Transport: Fundamentals, linear transport and reloading problems 2007, pp. 106-108.