In this chapter and the chapter that follows, we explore the special structure of network models. This chapter focuses on the problems of product distribution.

The **transportation problem** is a special type of linear
programming problem, where the objective is to minimize the cost of
distributing a product from a number of sources to a number of destinations.

The transportation problem deals with a special class of **linear programming
problems** in which the objective is to transport a homogeneous product manufactured at several plants (origins) to a
number of different destinations at a minimum total cost. The total
supply available at the origin and the total quantity demanded by the
destinations are given in the statement of the problem. The cost of
shipping a unit of goods from a known origin to a known destination
is also given. Our objective is to determine the optimal allocation
that results in minimum total shipping cost.

A firm has 3 factories - A, E, and K. There are four major warehouses situated at B, C, D, and M. Average daily product at A, E, K is 30, 40, and 50 units respectively. The average daily requirement of this product at B, C, D, and M is 35, 28, 32, 25 units respectively. The transportation cost (in Rs.) per unit of product from each factory to each warehouse is given below:

Warehouse | |||||
---|---|---|---|---|---|

Factory | B | C | D | M | Supply |

A | 6 | 8 | 8 | 5 | 30 |

E | 5 | 11 | 9 | 7 | 40 |

K | 8 | 9 | 7 | 13 | 50 |

Demand | 35 | 28 | 32 | 25 |

The problem is to determine a routing plan that minimizes total transportation costs.

Let x_{ij} = no. of units of a product transported from ith
factory(i = 1, 2, 3) to jth warehouse (j = 1, 2, 3, 4).

It should be noted that if in a particular solution the x_{ij} value is missing for a cell, this means that nothing is shipped between
factory and warehouse.

The problem can be formulated mathematically in the linear programming
form as

Minimize = 6x_{11} + 8x_{12} + 8x_{13} + 5x_{14}

+ 5x_{21} + 11x_{22} + 9x_{23} + 7x_{24
}+ 8x_{31} + 9x_{32} + 7x_{33} + 13x_{34}

subject to

Capacity constraints

x_{11} + x_{12} + x_{13} + x_{14} =
30

x_{21} + x_{22} + x_{23} + x_{24} =
40

x_{31} + x_{32} + x_{33} + x_{34} =
50

Requirement constraints

x_{11 }+ x_{21} + x_{31} = 35

x_{12} + x_{22} + x_{32} = 28

x_{13} + x_{23} + x_{33} = 32

x_{14 }+ x_{24} + x_{34 } = 25

x_{ij} ≥ 0

The above problem has 7 constraints and 12 variables.Since no. of
variables is very high, simplex method is not applicable. Therefore,
more efficient methods have been developed to solve *transportation problems*.

minimize c_{ij}x_{ij}

subject to

x_{ij} ≤ S_{i} for i = 1,2, .....,
m (supply)

x_{ij} ≥ D_{j} for j = 1,2, .....,
n (demand)

x_{ij} ≥ 0

For a feasible solution to exist, it is necessary that total capacity
equals total requirements.

Total supply = total demand.

Or Σ a_{i }= Σ
b_{j}.

- Only a single type of commodity is being shipped from an origin to a destination.
- Total supply is equal to the total demand.

S_{i}= D_{j} - S
_{i}(supply) and D_{j}(demand) are all positive integers.