Transportation Problem: Linear Programming

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.

The transportation (or distribution) problem is significant for most commercial organizations that operate several plants and hold inventory in regional warehouses.

Mathematical Representation of Transportation Problem

example 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:

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.

Transportation Problem Linear Programming

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.

General Mathematical Model

minimize sigmasigmacijxij

subject to

sigmaxij ≤ Si  for i = 1,2, ....., m (supply)

sigmaxij ≥ 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.

If total supply = total demand then it is a balanced transportation problem. There will be (m + n 1) basic independent variables out of (m x n) variables.

Assumptions in Transportation Problem

  • Only a single type of commodity is being shipped from an origin to a destination.
  • Total supply is equal to the total demand.
    sigma Si =sigma Dj
  • Si (supply) and Dj (demand) are all positive integers.

Share This Article