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

Version vom 23. Juni 2013, 09:46 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 Rome, Lisbon, Berlin and Moscow. 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:

Order of steps:
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 order is depending on the lowest costs it shows a good approximation to the optimal solution.

At first searching the cost minimal field gives Madrid /Lisbon with 15 per unit. The maximal quantity which you can place there is 60 restricted by the row. Then you are finishing the according column and place 15 to Istanbul/Lissabon. After that move on with the row, Istanbul/Moscow gets 25. There is only Peking remaining yet. Next you send 25 from Peking to Moscow, then 30 Peking/Berlin and at last step to complete supply= demand Pekings /Rome 45.

6. Frequency method by Habr:

The frequency method considers the interdependence of costs. In addition a modified matrix minimum method is part of this algorithm. In the most cases the results of frequency method are adequate solution and nearly optimal. The problem of this method is based on the time which you need to determine the modified matrix. You get this modified matrix by following this mathematical formulation.

k_ij= m*n*c_ij-n*∑ c_pj -m∑c_iq+∑∑c_pq

∑ c_pj from p=1 to m
∑c_iq from q=1 to n

∑∑c_pq combined by both, is adding all fields of the matrix
i = row ; j= column
m = number of rows; n= number of columns;

Example:
k₁₁= 3*4*20- 4*(20+30+40) -3*(20+15+25+60)+ (20+15+25+50+30+35+60+20+40+55+35+80) = 240-360-360+465= -15
k₂₁= 3*4*30- 4*(20+30+40) -3*( 30+35+60+20) +465= 30

The remaining k_ij are defined by using the mathematical formulation for every element.
Modified matrix of the costs

After that we have to use the matrix minimum method. That is why we add the highest possible quantity to the field with the lowest costs. So at first Moscow/ Istanbul with the costs of -330 gets 40. Then Istanbul can’t send quantity anymore. The next lowest element is Peking/Berlin. We store the possible 30. Berlin is finished now. Go on with Madrid/ Lisbon and store 60. Madrid is closed now. The remaining quantity has to be in the row of Peking to fulfil supply=demand.
Solution tableau