5.

Transportation Problems
 The transportation problem is a special type of linear program that
arises in planning the distribution of goods and services from several
supply points to several demand locations.
- Transportation problem involve determining how to optimally
(minimum shipping cost) transport goods from the sources to
destinations.
- Usually we are given the capacity of goods at each source and the
requirements at each destination
- Typically the objective is to minimize total transportation and production
costs
- The transportation model can also be optimally solved by Linear
Programming.
 The LP Formulation
Warehouse
Factory A B C D Supply
1 4 7 7 1 100
2 12 3 8 8 200 Total
3 8 10 16 5 150 Supply
Demand 80 90 120 160 450
Total Demand 450
let x be the quantity shipped from factory i to warehouse j
i, j
minimize 4x1,A  7 x1,B  7 x1,C  1x1,D 
12x2,A  3x2,B  8x2,C  8x2,D 
8x3,A  10x3,B  16x3,C  5x3,D
 The LP Formulation
. Supply Constraints (rows)
subject to x1,A  x1,B  x1,C  x1,D 100
x2,A  x2,B  x2,C  x2,D 200
x3,A  x3,B  x3,C  x3,D 150
. Demand Constraints (columns)
subject to x1,A  x2,A  x3,A 80
x1,B  x2,B  x3,B 90
x1,C  x2,C  x3,C 120
x1,D  x2,D  x3,D 160
• Consider the case given below. There are sources (Albuquerque,
Boston and Cleveland) and there are destinations (Des Moines
Evansville and Fort Lauderdale) with costs, and constraints for
capacity and demand.
As a result, we can minimize the total project cost (normal costs plus
crashing costs) by minimizing the crashing costs. Thus, the linear
programming objective function becomes

This simply states that the

The maximum allowable
start time for the following
crash-time constraints follow
activity must be at least as
great as the finish time for
each immediate predecessor
with crashing applied.
Basic feasible solution can be obtained by three methods, they
are
•North - west corner method,
•Least - cost cell method,
•Vogel's Approximation Method, generally known as VAM.
After getting the basic feasible solution, do optimality test to
check whether the solution is optimal or not.
There are two methods of doing optimality test, they are
•Stepping Stone Method,
•Modified Distribution Method, generally known as MODI
method.
Initial Solution with NORTH-WEST corner method

Albuquerque Boston Cleveland Capacity

5 4 3 100
Des Moines

8 4 3
Evansville 300

Fort 9 7 5
300
Lauderdale
Demand 300 200 200 700
Step1 Start from the left hand side top corner or cell and make
allocations depending on the availability and requirement
constraint.
Step 2 By satisfying availability and requirement constraints fill
the other cells.

Z=1005 + 2008+1004+1007+2005=500+1600+400+700+1000=4200 $
 Initial Solution with LEAST COST method
 Identify the lowest cost cell in the given matrix. In this particular

example it is 3. Make allocations to this cell. After filling search for

lowest cost cell. Proceed this way until all allocations are made.

Z=3009+2004+1003+1003=2700+800+300+300=4100 $
Initial Solution with Vogel’s Approximation Method
(VAM)
• Step 1: For each row and column find the difference
between the two lowest unit shipping costs.
Step 2
Assign as many units as possible to the lowest-cost square in
the row and column selected.
 Step 3
Eliminate the column or row that has been satisfied.
Z= 1005+2004+1003+2009+1005=500+800+300+1800+500=3900 $
 STEPPING STONE METHOD of optimality test

Once, we get the basic feasible solution for a transportation

problem, the next duty is to test whether the solution we got is an
optimal solution or not?
•Steps to test unused squares;
•Select an unused square,
•Allocate +①unit to unused square and locate - ① and + ①
alternatively to corners of the selected closed path,
•Calculate the improvement index ,
•If improvement index is negative allocate as much as you can to
that unused square,
•Repeat the allocation till the improvement index is ≥0 for all unused
squares.
Application of the Method:
Since there is a decrease in the cost, we will allocate as much as we can to
Fort Lauderdale – Albuquerque. The amount is the minimum of the
numbers that we are assigning -① in the cycle.

Z=1005 + 1008+2004+1009+2005=500+800+800+900+1000=4000 $
The solution obtained may or may not be optimal. To check we return to first step to check the unused squares,

D to B IDB +DB-DA+AE-EB +4-5+8-4 +3

D to C IDC +DC-DA+FA-FC +3-5+9-5 +2
E to C IEC +EC-EA+FA-FC +3-8+9-5 -1
F to B IFB +FB-EB+EA-FA +7-4+8-9 +2

An improvement can be done by allocating to EC, since the minimum number in the
square is 100; we allocate 100 to EC square.
Z=1005 +
2009+2004+1003+1005=500+1800+800+300+500=3900 $

We
D towill
B check
I the+DB-DA+FA-FC+EC-EB
Improvement index in each +2
+4-5+9-5+3-4 cell again.
DB
D to C IDC +DC-DA+FA-FC +3-5+9-5 +2
E to A IEC +EA-FA+FC-EC +8-9+5-3 +1
F to B IFB +FB-EB+EC-FC +7-4+3-5 +1
In the table, no more negative improvement index, so the solution is optimal.
 Example
A company has three factories X, Y, and Z and three warehouses A, B, and C. It
is required to schedule factory production and shipments from factories to
warehouses in such a manner so as to minimize total cost of shipment and
production. Unit variable manufacturing cost (UVMC) and factory capacities and
warehouse requirements are given below:
From / To A B C Capacity
10 4 11
70
X
12 5 8
50
Y
9 7 6
30
Z
Demand 40 50 60 150

a) Load the table with North-west method.

b) Load the table with least cost method.
c) Load the table with Vogel’s approximation method, (VAM).
d) Solve the question by stepping stone algorithm.
 Example
The demand and capacity are given.

From / To Sarajevo Travnik Bihac Capacity

5 7 15
Mostar 120

4 2 8
Zenica 200

6 3 10
Tuzla 150

Demand 210 160 100 470

a) Load the table with North-west method.
b) Load the table with least cost method.
c) Load the table with Vogel’s approximation method, (VAM).
d) Solve the question by stepping stone algorithm.
 Assignment Model

• Allocating one person to one job and minimizing

the time or cost of problem is solved by
ASSIGNMENT MODEL.

• The assignment problem refers to the class of LP

problems that involve determining the most
efficient assignment of resources to tasks

• The objective is most often to minimize total costs

or total time to perform the tasks at hand
 In operation research, an assignment problem is a type of linear
programming problem that involves assigning a number of jobs
to a number of people or facilities in a way that minimizes cost
or time:
 Goal: Minimize the cost or time of completing jobs
 Constraints: Each job must be assigned to one person or
facility, and each person or facility must be assigned to one job
 Applications: Can be used to solve problems like assigning
machines to jobs, salesmen to sales territories, and the traveling
salesman problem
 The Hungarian method is an efficient algorithm for solving
assignment problems. It involves:
 Subtracting the smallest element from each row and column in
a matrix
 Assigning zeros
 Performing an optimal test
Consider the following assignment case;

Three repair person Adams, Brown and Cooper are tried to be assigned to repair a radio(1), a tooster oven (2) and a broken coffee
table(3) by the owner of the repair shop. The owner of the shop try to minimize the cost of assignment.

PROJECT($) PROJECT ASSIGNMENT

PERSON 1 2 3 1 2 3 Labor Cost Total Cost
Adams 11 14 6 Adams Brown Cooper 11+10+7 28
Brown 8 10 11 Adams Cooper Brown 11+12+11 34
Cooper 9 12 7 Brown Adams Cooper 8+14+7 29
Brown Cooper Adams 8+12+6 26
Cooper Adams Brown 9+14+11 34
Cooper Brown Adams 9+10+6 25

There are n!=4!=432 1=24 number of solutions. If there is 5 assignment

there will be 5!=120 different combinations.Therefore , instead of writing all the
combinations, an algorithm (Hungarian Method) will be used to find the
solution.
 Hungarian Method
• The Hungarian method is an efficient method of finding the
optimal solution to an assignment problem without having
to make direct comparisons of every option
• It operates on the principle of matrix reduction
• By subtracting and adding appropriate numbers in the cost
table or matrix, we can reduce the problem to a matrix of
opportunity costs
• Opportunity costs show the relative penalty associated with
assigning any person to a project as opposed to making the
best assignment
• We want to make assignment so that the opportunity cost
for each assignment is zero
• There are five steps to find the optimum result.

Step1. Subtract the smallest element in each row from the other elements of the row.

PROJECT PROJECT
PERSON 1 2 3 1 2 3
Adams 11 14 6 ...subtract 6  5 8 0
Brown 8 10 11 ...subtract 8  0 2 3
Cooper 9 12 7 ...subtract 7  2 5 0
Step3. Draw minimum number of lines to cover the zeros. If the lines drawn are equal to the number of rows or columns
(because of square matrix), we can make assignment.

PROJECT
1 2 3
5 6 0
Number of lines is 2 which is less than number of rows or column. So solution is not
0 0 3
optimum.
2 3 0
Step4. If the lines drawn are less than the number of rows or columns,
then we cannot make assignment. Hence the following procedure is to be
followed:
- The cells covered by the lines are known as Covered cells.
- The cells, which are not covered by lines, are known as uncovered
cells.
- The cells at the intersection of horizontal line and vertical lines are
known as Crossed cells.

(a) Identify the smallest element in the uncovered cells.

(i) Subtract this element from the elements of all other uncovered
cells.
(ii) Add this element to the elements of the crossed cells.
(iii) Do not alter the elements of covered cells.

(b) Once again cover all the zeros by minimum number of horizontal
and vertical lines.
(c) Once the lines drawn are equal to the number of rows or columns,
assignment can be made.
Step 1: Create a Cost Matrix:
Formulate a cost matrix representing the costs or benefits associated with each
task-agent pair. Ensure that the matrix is square.
Step 2: Subtract Row and Column Minima:
For each row, find the minimum element and subtract it from every element in
that row. Next, do the same for each column. This step is aimed at creating as
many zeros as possible in the matrix.
Step 3: Cover Zeros with Minimum Number of Lines:
Cover the zeros with the minimum number of horizontal and vertical lines. If
the number of lines is equal to the matrix size, an optimal solution has been
reached. If not, proceed to the next step.
Step 4: Identify the Smallest Uncovered Element:
Identify the smallest element that is not covered by any line. This element is
referred to as the minimum uncovered element (MUE).
Step 5: Adjust Matrix Elements:
Subtract the MUE from the uncovered elements and add it to the elements that
are at the intersection of two lines. This step modifies the matrix to continue the
process of finding zeros and covering lines.
Step 6: Repeat Until Optimality is Achieved:
Repeat steps 3 to 5 until an optimal assignment is achieved, which is when the
number of lines covering zeros equals the matrix size.
 Example

There are 3 jobs A, B, and C and three machines X, Y, and Z.

All the jobs can be processed on all machines. The time
required for processing job on a machine is given below in
the form of matrix. Make allocation to minimize the total
processing time.

Machines (time in hours)

X Y Z
A 11 16 21
Jobs
B 20 13 17
C 13 15 12
 Example 1: Powerco Formulation
 Powerco has three electric power plants that supply the
electric needs of four cities.
 The associated supply of each plant and demand of each
city is given in the table 1.
 The cost of sending 1 million kwh of electricity from a
plant to a city depends on the distance the electricity must
travel.
 Example 1: Solution

 Decision Variables
✦ Powerco must determine how much power is sent from
each plant to each city so xij = Amount of electricity
produced at plant i and sent to city j
 x14 = Amount of electricity produced at plant 1 and
sent to city 4
 Constraints
✦ A supply constraint ensures that the total quality
produced does not exceed plant capacity. Each plant is a
supply point.
✦ A demand constraint ensures that a location receives its
demand. Each city is a demand point.
✦ Since a negative amount of electricity can not be shipped
all xij’s must be non negative
 Ex. 1 - continued
 A transportation problem is specified by the supply, the
demand, and the shipping costs. Relevant data can be
summarized in a transportation tableau.
From To

City 1 City 2 City 3 City 4 Supply (Million

kwh)
Plant 1 $8 $6 $10 $9 35

Plant 2 $9 $12 $13 $7 50

Plant 3 $14 $9 $16 $5 40

Demand (Million 45 20 30 30
kwh)
 Ex. 1 – Solution continued
 LP Formulation of Powerco’s Problem
Min Z = 8x11+6x12+10x13+9x14+9x21+12x22+13x23+7x24
+14x31+9x32+16x33+5x34

S.T.: x11+x12+x13+x14 <= 35 (Supply Constraints)

x21+x22+x23+x24 <= 50
x31+x32+x33+x34 <= 40

x11+x21+x31 >= 45 (Demand Constraints)

x12+x22+x32 >= 20
x13+x23+x33 >= 30
x14+x24+x34 >= 30
xij >= 0 (i= 1,2,3; j= 1,2,3,4)
3.4. Assignment problems
 Example 4: Machine Assignment Problem
 Machineco has four jobs to be completed.
 Each machine must be assigned to complete one job.
 The time required to setup each machine for completing
each job is shown.
Time (Hours)

Job1 Job2 Job3 Job4

Machine 1 14 5 8 7

Machine 2 2 12 6 5

Machine 3 7 8 3 9

Machine 4 2 4 6 10

 Machineco wants to minimize the total setup time needed

to complete the four jobs.
 Exercise 4: Solution

 Machineco must determine which machine should be

assigned to each job.
 i,j=1,2,3,4
 xij=1 (if machine i is assigned to meet the demands of job j)
 xij=0 (if machine i is not assigned to meet the demands of job j)
min Z 14 X 11  5 X 12  8 X 13  7 X 14  2 X 21  12 X 22  6 X 23  5 X 24
 7 X 31  8 X 32  3 X 33  9 X 34  2 X 41  X 42  6 X 43  10 X 44
s.t. X 11  X 12  X 13  X 14 1 ( Machine constraints)
X 21  X 22  X 23  X 24 1
X 31  X 32  X 33  X 34 1
X 41  X 42  X 43  X 44 1
X 11  X 21  X 31  X 41 1 (Job constraints)
X 12  X 22  X 32  X 42 1
X 13  X 23  X 33  X 43 1
X 14  X 24  X 34  X 44 1
Xij 0orXij 1
 Ex. 4 – Solution continued
 In general an assignment problem is balanced
transportation problem in which all supplies and demands
are equal to 1.
 The assignment problem’s matrix of costs is its cost
matrix.
 All the supplies and demands for this problem are integers
which implies that the optimal solution must be integers.
 Using the minimum cost method a highly degenerate bfs is
obtained.