Transportation problem: Construction of starting solution 1

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.