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 xij = 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 xij 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 = 6x11 + 8x12 + 8x13 + 5x14
+ 5x21 + 11x22 + 9x23 + 7x24
+ 8x31 + 9x32 + 7x33 + 13x34
subject to
Capacity constraints
x11 + x12 + x13 + x14 =
30
x21 + x22 + x23 + x24 =
40
x31 + x32 + x33 + x34 =
50
Requirement constraints
x11 + x21 + x31 = 35
x12 + x22 + x32 = 28
x13 + x23 + x33 = 32
x14 + x24 + x34 = 25
xij ≥ 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 cijxij
subject to
xij ≤ Si for i = 1,2, .....,
m (supply)
xij ≥ Dj for j = 1,2, .....,
n (demand)
xij ≥ 0
For a feasible solution to exist, it is necessary that total capacity
equals total requirements.
Total supply = total demand.
Or Σ ai = Σ
bj.