Transportation problem: Iterative optimization method 2: Unterschied zwischen den Versionen

Version vom 1. Juli 2013, 10:22 Uhr

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:

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

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

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

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

Mathematical formulation of this 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.

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

figure 2:Matrix with determined basis fields

Second Step:

The target in this step is to put either ${\displaystyle u_{i}}$=0 or ${\displaystyle 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.

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 ${\displaystyle u_{i}}$ and ${\displaystyle 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}

figure 4:

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}

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}*.