Transportation problem: Iterative optimization method 2

Basics

The itertaive optimization method is a way to find the optimal solution of the Transportation Problem. The Transportation Problem is a special kind of the Max Flow Problems. The basic objective is to find the optimal transportation classification of a transportation quantity. For the Transportation problem the following variables are important:

$a_{i}$ : supply quantity at location i (i=1, ... ,m)

$b_{j}$ : demand quantity at location j (j=1 , ... ,n)

$c_{ij}$ : transportation cost per unit from supply location i to demand location j

$x_{ij}$ : transportation quantity from i to j

Mathematical formulation of the problem

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Minimize K= \sum_{i} \sum_{j} c_{ij} x_{ij}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{j} x_{ij}=a_{i} \forall i

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{i} x_{ij}=b_{j} \forall j

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{ij}\geq 0 \forall i,j

A solution only exists, if Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{i} a_{i} = \sum_{j} b_{j}

Example

There are seven ways to find the initial solution of transportation problem:

1. North-West corner method

2. Simple row sequence or column-sequence methods

3. Row-column succession

4. Matrix-Minimum method

5. Cost difference method

6. Frequency method according to Habr

7. Modified North-West corner method

Before you can dispose the iterative optimization method you have to get the initial solution of the Transportation Matrix. Use one of these seven methods. For example in this Matrix we took the Simple row sequence method. On this basic we explain how to approach to get the optimal solution by using the iterative optimization method.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

figure 1:Starting solution with simple row sequence

First Step:

Determine the basis fields with Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): m+n-1

m: Matrix quantity of supply location

n: quantity of demand location

Basis fields are all fields which have a dedicated quantity.

In all these basis fields you have to put Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}*=0

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

figure 2:Matrix with determined basis fields

Second Step:

The target in this step is to put either $u_{i}=0$ or $v_{j}=0$.

Your choice is random one but the best way is to take that row or column which has the most basis fields.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

figure 3: matrix with one of the mulitplikator =0

If you decide to set the row or column with the most basis fields =0 you would take the first row or the third column. In this example was taken a random choice.

Third Step:

Calculate all the rest of $u_{i}$ and $v_{j}$. For this purpose use this formula:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}*=c_{ij}-u_{i}-v_{j}

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

figure 4:matrix with all defined multiplicators

Fourth Step:

Determine the rest of Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}*

by using this formula: 

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}*=c_{ij}-u_{i}-v_{j}

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

figure 5:matrix with all defined reduced costs Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}*

For example Amsterdam-Berlin:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}*=c_{ij}-u_{i}-v_{j}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}*=170-60-(-105)

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}*=215

Fifth Step:

Find the highest negative value of Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}* .

See figure 5. Here you can see -15 is the highest negative value of Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}*.

Sixth Step:

Your target is that all Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}*

have positive values 0 included. 

Take the Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}*

you got in step 5 and try to change quantities. Find a basis field in the same column and row and put the identical quantity away. An important detail is to put only quantities away from basis fields. To keep in mind supply and demand quantity don’t change. That’s why in every row and column changed quantities have to be the same.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

figure 6: matrix of first iteration

Seventh Step:

Create a new matrix and engraft the new quantities Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{ij}* . Go back to step one and determine the new basis fields, $u_{i},v_{j}$ and Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}* . Repeat this until every Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}*

is positive. That’s your optimal solution.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

figure 7: matrix of second iteration

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

figure 8:matrix with only one negative value of reduced cost

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

figure 9: matrix of third iteration

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

figure 10:optimal solution after third iteration

Summary

1. determine a initial solution

2. determine Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): m+n-1
basic fields an set Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}*=0 

3. set arbitrary $u_{i}$ or $v_{j}=0$

4. determine the missing multiplicators

5. determine the missing reduced costs (Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}*

) with the formula Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}*=c_{ij}-u_{i}-v_{j}

6. find the most negative cell in the matrix

7. add the amount of this allocation to other corners of the loop in order to restore
   feasibility

8. set up the new matrix and start again with step 2 until all Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}* \geq 0 

Sources

https://bisor.wiwi.uni-kl.de/orwiki/Transportproblem

Prof. Dr. Oliver Wendt, Operation Research script, TU Kaiserslautern, Sommersemester 2013