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

Version vom 1. Juli 2013, 10:02 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