Transportation problem: Construction of starting solution 1: Unterschied zwischen den Versionen

Version vom 7. Juni 2013, 18:22 Uhr

Transportation problem: Find an initial solution

Introduction

The transportation problem is a general problem for every company, especially in logistics, to get a balance between supply and demand quantity. That means, you have j locations which need the product x and i locations which could send it to each of these. The supply quantity is declared by the variable a_i, the quantity of demand by the variable b_j. A necessary condition for this is that the total supply is equal to the total demand. Furthermore the problem consists of an allocation of the quantity in a cost minimal way. That shows basically the theoretical problem.

Mathematical formulation of a general transportation problem

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

Minimize K=∑i ∑j c_ij*x_ij
∑j x_ij = a_i for every i
∑i x_ij = b_j for every j
x_ij ≥ 0 for every i,j
A solution only exists, if ∑i a_i = ∑j b_j

Example

There is a company named Physics Rules The World which has 4 manufacturing bases. They produce high technology light amplification of stimulated emission of radiation, short LASER in Rom, Lissabon, Berlin and Moskau. An important furnisher is placed in Madrid, Istanbul and Peking. The following cost matrix is depending on the distance between the place of supply and the place of demand. In addition there are a few possibilities to send the material like by truck, plane or train. That is why the shortest distance doesn’t have to be the possibility with the shortest costs.

In the following part we explain you the possibilities to find an initial solution.

    1. North-West corner method
    2. Simple row sequence
    3. Row-column succession
    4. Matrix-Minimum method
    5. Cost difference method
    6. Frequency method
    7. Modified North-West corner method 

3. Row-column succession:

Redline:
1. Allocate the cheapest field of the whole matrix the highest possible quantity.
2. The next cheapest field in row or column should get the remaining quantity.
3. Move forward till every demand is tiled.

Because of the redline is depending on the lowest costs it shows a good approximation to the optimal solution.