Solving the Transportation Problem with Excel VBA

In the general case, the transportation problem can be formulated as follows: in mm supply points A₁,…,A_m there is a homogeneous commodity with quantities a₁,…,a_m units, respectively. This commodity must be delivered to consumers B₁,…,B_n with demands b₁,…,b_n. The cost of transporting one unit from supply point i (i=1,…,m) to destination j (j=1,…,n) is c_ij. It is required to construct a shipping plan that fully satisfies consumer demand while minimizing the total transportation cost.

Mathematically, the transportation problem can be written as:

Thus, given the system of constraints with and the linear objective, the task is to find among all solutions a non-negative solution that minimizes if the total supply equals the total demand:

If either of the following holds:

then the model is called open (unbalanced).

To make an open transportation problem solvable, it should be transformed into a closed one:

• If

introduce a dummy destination B_n+1 (i.e., add an extra column). The demand of the dummy consumer is  .

The transportation costs to the dummy destination are taken equal (usually zero, if no storage cost is specified), i.e .

• If

introduce a dummy supplier A_m+1 (i.e., add an extra row). The supply of the dummy supplier is

 .

The transportation costs from the dummy supplier are taken equal (usually zero, if no penalty costs for under-delivery are specified), i.e.,

.

When transforming an open problem into a closed one, the objective function does not change, since all terms corresponding to the additional (dummy) shipments are zero.