TRANSPORTATION MODEL

A. INTRODUCTION

 This is a special case of Linear programming problem

 Transportation model deals with the determination of minimum – cost plan for transporting
a single commodity from a number of sources (e.g. factories) to a number of destinations
(e.g. warehouses)
 The model can be extended in a direct manner to cover practical situations in the areas of
inventory control, employment scheduling, personnel assignments, cash flow, scheduling
dam reservoir levels, etc
 Although the model is typically a linear programming model that can be solved by normal
simplex method, its special structure allows the development of a solution procedure,
known as the transportation technique that is computationally more efficient.
 The data of the model include:
- Level of supply at each source and amount of demand at each destination
- The unit transportation cost of the commodity from each source to each destination
- Since there is only one commodity, a destination can receive its demand from one or
more sources

Assumption:
 The transportation cost on a given route is directly proportional to the number of units
transported.

Note:
 We have m sources and n destinations
 A source or a destination is represented by a node
 When the total supply equals the total demand, the resulting formulation is called a
balanced transportation model

B. LP FORMULATION
m n
Minimize Z   Cij X ij
ii 1 j 1
m
Subject to X
j 1
ij  Si (sup ply, Si , at source i)

X
i 1
ij  d j (demand , d j , at destination j )

X ij  0
m n
Assumption :  Si   d j
i 1 j 1

C. SOLUTION METHODS

1
The initial solution to a transportation problem can be obtained using any one of the following
methods:

 Northwest Corner method

 Least –Cost method
 Vogel Approximation Method
 Simplex method – cumbersome (by virtue of it being an LP model)

Northwest corner method

 Start at the north-west corner (upper left hand corner) of the tableau and allocate as much as
possible to without violations the supply or demand constraints
 This will exhaust the supply at source 1 and/or the demand for destination 1. As a result, no
more units can be allocated to the exhausted row or column, and it is eliminated.
 Next allocate as much as possible to the adjacent cell in the row or column that has not been
eliminated. If both row and column are exhausted, move diagonally to the next cell.
 Continue in the same manner until all supply has been exhausted and demand requirements
have been met.

Least cost method:

 Select the Xij variable (cell) with the minimum unit transportation cost (Cij) and allocate as
much as possible.
 From the remaining cells that are feasible (i.e. have not been filled or their row or column
eliminated), select the minimum Cij value and allocate as much as possible.
 Continue this process until all the supply and demand requirements are satisfied.

Vogel’s Approximation Method:

 Calculate the penalty cost for each row and column. The penalty costs for each row I are
computed and subtracting the smallest Cij value in the row from the next smallest Cij value
in the same row. Column penalty costs are obtained in the same way, by subtracting the
smallest Cij value in each column from the next smallest column Cij value. These costs are
the penalty for not selecting the minimum cell cost.
 Select the row or column with the greatest penalty cost (breaking any ties arbitrarily).
Allocate as much as possible to the cell with the minimum Cij value in the selected row or
column
 Adjust the supply and requirements to reflect the allocation(s) already made. Eliminate any
rows and columns in which supply and demand have been exhausted.
 If all supply and demand requirements have not been satisfied, go, to the first step and
recalculate new penalty costs. If all row and column values have been satisfied the initial
solution has been obtained.

Determining an optimal solution:

There are two methods:
 Stepping stone
 Modified distribution method

2
Stepping stone method:
This is the process of evaluating the non-basic variables to determine if improvement is possible
and then reallocating units. It derives its name from the fact that a closed loop of occupied cells
is used to evaluate each empty cell (non-basic variable)

Important conditions regarding the construction of stepping stone paths:

 The direction taken, either clockwise or anticlockwise, is immaterial in determining the

closed path. The same path will result regardless of direction
 There is only one unique closed path for each empty cell
 The path must follow only (change direction at) occupied cells; the exception being the
non basic variable being evaluated
 However, both empty and occupied cells can be skipped over in the construction of a
closed path
 A path can cross over itself
 Exactly one addition and one subtraction must appear in each row and column on the
path. The purpose of the path is to maintain the supply and demand constraints while
allocating units to an empty cell.

Modified Distribution Method (MODI)

In the MODI method, a value, Ui is determined for each row (i) and a value, Vj is defined for
each column (j) in the transportation tableau. For each basic variable, (i.e., occupied cell), Xij the
following relationship exists:

Ui+Vj=Cij, where Cij is the unit cost of transportation

Thus, Cij* = Cij – Ui - Vj

When Cij* <= 0, we have a non optimal solution. The negative Cij* is a candidate for the
entering non-basic variable.

Alternatively, compute a shadow cost for each cell. This is given by:

Shadow cost =Ui + Vj +Cij

For a filled cell, the shadow cost is zero. This means, 0 = Ui + Vj +Cij or Cij= - (Vj +Cij). Thus,
when we have a negative shadow cost for the unfilled cell, the solution is not optimal.

D. PROBLEM VARIATIONS

The following problem variations can be handled, with slight adaptations, by the transportation
simplex method

3
Total supply not equal to total demand
 Introduce a dummy origin or destination
 If  Si   d i , introduce a dummy destination with demand=the excess of supply over
demand
 If  di   si , introduce a dummy origin with supply=the excess of demand over
supply
 Assign cost coefficients of zero

Maximization problem
Transportation simplex method can also be used to solve maximization problems

The only modification involves the selection of incoming cells. Instead of picking the cell with
the smallest or most negative eij, we pick the cell for which eij is largest i.e. pick the cell that
will cause the largest increase per unit in the objective function. If eij eij  0 for all unoccupied
cells, we stop, the maximization solution has been reached.

Unacceptable routes

Infeasible arcs must carry an extremely high cost, denoted by M, to keep them out of the
solution.

E. EXERCISES

Question 1.
A product is produced at three plants and shipped to three warehouses (the transportation costs
per unit are shown in the following table)

Warehouse
Plant W1 W2 W3 Plant Capacity
P1 100 200 24 300
P2 10 200 300 500
P3 100 18 10 100
Warehouse 200 400 300
Demand

(a) Show a network representation of the problem

(b) Develop a linear programming model for minimizing transportation costs; solve this
model to determine the minimum-cost solution
(c) Suppose that the entries in the table represent profit per unit produced at plant i and sold
to warehouse j. How does the model formulation change from that in part (b)?

Question 2

The Ace Manufacturing Company has orders for three similar products:

4
 Product Orders (units)
A 2000
B 500
C 1200

Three machines are available for the manufacturing operations. All three machines can produce
all the products at the same production rate. However, due to varying defect percentages of each
product on each machine, the unit costs of the products vary depending on the machine used.
Machine capacities for the next week, and the unit costs, are as follows:

Machine Capacity (units)

1 1500
2 1500
3 100

Product
Machine A B C
1 $1.00 $1.20 $0.90
2 $1.30 $1.40 $1.20
3 $1.10 $1.00 $1.20

Use the transportation model to develop the minimum-cost production schedule for the products
and machines. Show the linear programming formulation.

ASSIGNMENT PROBLEM
A. INTRODUCTION

The assignment problem arises in a variety of decision-making situations. Typical assignment

problems involve:

 Assigning jobs to machines

 Agents to tasks
 Sales personnel to sales territories
 Contracts to bidders.

Features and objective

 There are an equal number of sources and destinations
 Each source supply and destination demand equal one, consequently the quantity allocated
or assigned, must be either zero or one.
 Specifically we look for the set of assignments that will optimize a stated objective such as
minimize cost, minimize time, or maximize profits.

5
Linear programming formulation
 The general linear programming formulation of an assignment problem with m sources and
n destinations is:

m n
Minimize Z   Cij X ij
ii 1 j 1
m
Subject to X
j 1
ij 1

X
i 1
ij 1

X ij  0

B. SOLUTION PROCEDURE (HUNGARIAN METHOD)

 Develop the opportunity cost table through row and column reduction
 Draw the minimum number of horizontal and/or vertical lines necessary to cross out all
zeros. If the number of lines satisfy the condition m=n, the optimal assignment has been
determined if not, perform step 3.
 Subtract the minimum uncrossed value from all uncrossed cell values and add this amount to
all values at the intersection of lines.
 Repeat the test for m=n unique assignments

C. PROBLEM VARIATIONS
 Total number of agents (supply) not equal to the total number of tasks (demand)
 A maximization objective function
 Unacceptable assignments

D. EXERCISES

Question 1.
Machine j
Operator i 1 2 3

1 7 3 5
2 8 9 2
3 9 6 8

Find the operator – machine assignments that will minimize costs.

Question 2.

6
 Machine
Operator 1 2 3 4

1 10 15 16 18
2 14 13 16 10
3 11 9 8 18
4 13 13 11 9

Find the operator – machine assignments that will minimize costs.