Topic 3 TRANSPORTATION PROBLEMS NOTES

3.1 Introduction
Distribution problems are a special type of linear programming problems. There are two main
types of distribution problems: the transportation problem and the assignment problem. The
transportation problem deals with distributing a product from a number of sources/ Supply (
factory, warehouses, seller’s premises) to a number of destinations/ demand ( warehouses ,
outlets, customers, godowns) Typically, each source is supply limited, each destination has a
known demand and the shipping costs between sources and destinations are given.
The objective is to find the cheapest shipping schedule that satisfies demand without violating
supply constraints.
The assignment problem deals with finding the best one-to-one match for each of a given
number of ‘candidates’ to a number of positions e.g. assigning teachers to classes or workers to
machines. Different benefits or costs are involved in each matchand the goal is to maximize the
total reward or minimize the total expense.
3.2 Characteristics and assumptions of the transportation problem
The following are the characteristics and assumptions of the transportation problem: -
1. The Sources are limited in terms how much they can supply. A limited quantity of
one commodity such as cement, oil or oranges is available at certain sources or origins such as
factories, refineries or groves.
2. The destination are assumed to be knowing their demand. There is a demand for the
commodity at several destinations such as warehouses, distribution centers or stores.
3. The quantities of demand and supply are constant at one given time. The quantities of
supply at each source and the demand or requirements at each destinations are constants.
4. The shipping cost from each source to each destination are assumed to be constant
The per unit costs of transporting the commodity from each source to each destination are
assumed to be constant
5. It is assumed that no shipments are allowed between sources or between
destinations. Allowing such transshipments would require special adjustments in the model.
6. All supply ,demand quantitie and costss are given in whole
numbers.
The problem is to determine how many units should be shipped from each source to each
destination so that all demands are satisfied at the minimum total shipping cost.

3.3 Presentation of transportation problems

Transportation problems can be presented as linear programming problems or in tabular form.
Presentation as linear programming problems
Any transportation problem can be presented in the form of a linear programming problem with
an objective function and the constraints. Although all transportation problems can be
represented as LP problems, it is not efficient in most cases to do so.
Any medium or large transportation problem becomes a huge LP model with many variables and
constraints thus the simplex method becomes unsuitable for solving transportation problems.
1
Zetech Digital School
Operations Research
Because of the special nature of the problem, a more efficient method called ‘transportation
method’ is used to obtain the optimal solution.

2
Zetech Digital School
Operations Research
The method is an algorithmic (repetitive) procedure, which progresses through a series of
feasible solutions that are successively improved until an optimal transportation schedule is
obtained.
Presentation in a tabular form.
The general transportation problem of a company with m-factories (capacity centers or source of
supply) and n-warehouses (requirement centers) can be presented in the following table:-

Where:-
i = index of origins (factory): i = 1,2,…..,m.
j = index for destinations (warehouse) j = 1,2,…..,n.
Xij = number of units shipped from origin i to destination j.
Cij = cost per unit of shipping from origin i to destination j.
Si = supply or capacity in units at origin i.
dj = demand in units at destination j.

The problem of the company is to distribute the available product to different warehouses in such
a way so as to minimize the total transportation cost for all possible factory shipping patterns.
Example
XYZ Cement Company has two processing plants, one in town A, with a supply capacity of 100
tonnes a day, and one in Town B with a supply capacity of 110 tonnes a day. XYZ company has
three warehouses; R, S and T. The warehouses need, if possible, 80, 120 and 60 tonnes of cement
each day, respectively, to meet their distribution demands. The transportation cost from each
warehouse are given below:

3
Zetech Digital School
Operations Research
FROM TO Cost per Tonne
A R 1
A S 2
A T 3
B R 4
B S 1
B T 5

Required:
i. Formulate the above problem as a Linear programming problem.
ii. Present the problem in a tabular form.
Solution
i. Presentation as a Linear Programming problem.
The objective function can be presented as:-
Minimize Z = 1xAR + 2xAS + 3xAT + 4xBR + 1xBS + 5xBT
Subject to:
xAR + xAS + xAT = 100
xBR + xBS + xBT = 110
xAR + xBR ≤ 80
xAS + xBS ≤ 120
xAT + xBT ≤ 60
ii. The above transportation problem can be presented in tabular form as shown below.
To
Warehouse R S T Supply
From Plant
1 2 3
A XAR XAS XAT SA=100
4 1 5
B XBR XBS XBT SB=110
260
Demand DR=80 DS=120 DT=60
260

Activity 4a
A company has three warehouses A, B and C and four stores W, X, Y and Z. The warehouses
have altogether a surplus of 150 units of a given commodity as follows:
A 50
B 60
C 40
4
Zetech Digital School
Operations Research
The four stores need the following amounts: -
W 20
X 70
Y 50
Z 10
Cost in shillings of transporting one unit of commodity from various warehouses todifferent
stores is as follows:-

Store
W X Y Z supply
A 50X20 150X30 70 60 50-20=30-30=0
Warehouse B 80 70X40 90X20 10 60-40=20-20=0
C 15 87 79X30 81X10 40-30=10-10=0
demand 20- 70-30=40- 50- 10- 150
20=0 40=0 20=30- 10=0
30=0

Required:
i. Present the above transportation problem in a tabular form.
ii. Formulate the above problem as a Linear programming
problem.

3.4 Methods of solving the transportation Model

1. Complete enumeration
All possible solutions are generated and the total cost of each analyzed. It is a cumbersome and
time-consuming job.
2. Linear programming
Since the transportation problem is indeed an LP problem, it can be solved as such. However,
presentation of a large transportation problem in an LP format results in considerable
computational effort, significantly more than special transportation method.
5
Zetech Digital School
Operations Research
3. Transportation method
The transportation method provides a computationally efficient procedure for solving large
transportation problems. The method is an algorithmic (repetitive) procedure, which progresses
through a series of feasible solutions that are successively improved until an optimal
transportation schedule is obtained.

6
Zetech Digital School
Operations Research
3.6 Balancing the table
The use of the transportation solution technique requires that the problem be balanced i.e. the
total supply must equal total demand. If the table is not balanced it must first be balanced. The
causes of imbalance are excess supply and excess demand.
3.6.1 Excess Supply
The table [Link] below is an example of an unbalanced table, where the total supply of 300
exceeds the total demand of 260. There will be 40 unshipped units.
Unbalanced table (excess supply)

Destination
R S T Supply
Source
1 2 3
A 200

4 1 5
B 100

300
Demand 80 120 60
260

For excess supply, the table is balanced by adding an artificial destination column to ‘absorb’ the
excess supply (sometimes labeled a “dummy” destination). The amount in this dummy column
equals the excess supply.
Balanced table (excess supply)

7
Zetech Digital School
Operations Research
 Destination
R S T T Supply
Source
1 2 3 0
A 200

4 1 0 0
B 100

40 (Excess 300
Demand 80 120 60
supply) 300

The cost of “shipments” to the dummy is usually set at zero, as an unreal shipment implies no
real cost. In some cases, no shipment may still incur a cost, such as with idled production thus; a
penalty cost should be entered

Excess Demand
The XYZ cement company problem shown in the table below is an example of a transportation
problem with excess demand.

In case of excess demand, i.e. when the demand exceeds total supply, a dummy source row is
added to “meet” the extra demand. The per unit shipping costs for the dummy row are set to zero
as shown below: -

Once the table is balanced, an initial feasible solution is generated

8
Zetech Digital School
Operations Research
The Initial Feasible Solution The initial feasible solution can be found by using the following
methods:-
Northwest Corner Rule
21ST FEBRUARY
Steps:
a. Starting with the Northwest corner (Left, uppermost in the table) allocate the smallest amount
of either the row supply or the column demand.
b. Subtract from the row supply and from the column demand the amount allocated.
c. If the column demand is now zero, move to the cell next on the right; if the row supply is zero,
move down to the cell in the next row. If both are zero, move first to the next cell on the right,
then down one cell.
d. Once a cell is identified as per step (c), it becomes a northwest cell. Allocate to it an amount as
per step (a).
e. Repeat the above steps (a) – (d) until all the remaining supply and demand is gone.

The Northwest Corner rule can be used to solve the XYZ cement company problem. An amount
of 80 tonnes is allocated to cell AR, out of the 100 available in source A, meeting the demand of
destination R. The remaining supply of 20 tonnes at source A is then allocated to cells AS. The
capacity of row A has now been exhausted, but the demand of S has not yet been fully satisfied.
Therefore, 100 tonnes of the 110 tonnes supply of source B is allocated BS, in order to meet the
entire demand of destination S. Then, moving to the right in row B, the remaining supply of B
(10 tonnes) is allocated to cell BT. This exhausts the supply in row B but the destination T still
needs 50 units. Moving down column T, the remainder
(50 tonnes) is allocated to cell DT. The entire supply has been satisfied

9
Zetech Digital School
Operations Research
The least-cost (largest profit) method
The least-cost method yields not only an initial feasible solution but also one that is close to
optimal in small problems. The method is “heuristic” in nature.
Example
Use the least cost method to solve the following problem

Solution
The least cost method prescribes that the first allocation be made to the cell with the lowest cost
(the highest profit in a maximization case). If a dummy is added, start with one of the dummy
cells with a cost of zero. In this example, there is an additional consideration, since cells Ad and
CE both have the lowest cost of Sh. 1. Cell AD is selected first because more units can be
allocated to it (70) than to cell CE (50). Thus, an allocation of 70 is made to cell AD. The supply
of A is reduced to 30 and the demand at D is completely satisfied.
Next an allocation of 50 (maximum possible) is made to cell CE, reducing the supply of C to 70.
The next search yields BF and CF, which each have a cost of Sh.2. (BE is not considered
because E is satisfied already). Cell CF is filled in first, since a larger quantity (120 – 50 = 70)
can be placed there. Then, the remaining requirement of 30 for column f is allocated to cell BF
and source B’s Supply is reduced to 30.
Next, an allocation is made to cells with a cost of Sh.4, since assignment to the cells with a cost
of Sh.3 is not possible under the supply and demand constraints. The only cell with a cost of Sh.
4 to which an assignment can be made is AG. The maximum possible quantity of 30 is assigned
there. Finally, the remaining demand (30 in column G) is assigned to BG to complete the initial
solution. This is summarized in the table below.

10
Zetech Digital School
Operations Research
Activity 3b
1. Obtain the initial solution in the following transportation problem by
a. North-west corner method
b. Least cost method

2. Obtain an initial basic feasible solution to the following transportation problem

Testing for optimality

The purpose of the optimality test is to see if the proposed solution just generated can be
improved or not. The procedure for testing optimality is analogous to that of the simplex method.
A distinction is made between basic variables, those associated with the occupied cells and non-
basic variables, those associated with the empty cells. For each empty cell, the effect of changing
it to an occupied cell is examined.
If any of these changes are favourable, the solution is not optimal and a new solution must be
designed. Two procedures for calculating the effect of such a change are
 Stepping-stone method
 Modified Distribution (MODI)
In both cases, the solution to be checked for optimality must be nondegenerate i.e. the number of
occupied cells must be m + n – 1 where m is number of sources and n the number of
destinations.
The stepping stone procedure
1. Compute the cell evaluators for all empty cells. This is done by subtracting the total cost of the
losing cells from that of the gaining cells in the closed loop.
2. If all cell evaluators are nonnegative in a minimization case, then the solution is optimal.
Otherwise, an improvement or alternate solution in the case of 0 evaluators is possible.

11
Zetech Digital School
Operations Research
3. Generating an improved solution involves identifying the incoming cell (that cell with the
largest cost reduction potential for minimization problems) and transferring as much as possible
to it. Once this has been done, a new solution is generated by adjusting the quantities in all losing
and gaining cells along the loop.
4. The improved solution is then tested. If it is not optimal, another improvement is made.
Eventually, an optimal solution if one exists will be reached.
Rule for drawing each closed loop
When tracing a closed loop, start with the empty cell to be evaluated and when going clockwise,
draw an arrow from it to an occupied cell in the same column or row. Next, move vertically or
horizontally (but never diagonally) to another occupied cell stepping over unoccupied or
occupied cells if necessary without changing them.
Follow the same procedure to other occupied cells until returning to the original empty cell. At
each turn of the loop, plus or minus signs are alternately placed in the cells, starting with a + sign
in the empty cell. There must be exactly one cell with a + sign and exactly one cell with a – sign
in any row or column in which the loop turns. This restriction is imposed to ensure that the
requirements of supply and demand will not be violated when the units are shifted. An even
number of at least four cells must participate in a loop and the occupied cells can be visited once
and only once. In a nondegenerate problem, there is only one possible way of drawing the loop
for each empty cell. All cells that receive a + or -, except the first one, must be occupied.
Evaluation of cell AT

The cost effect of the changes arising from the decision to ship one unit to the empty cell AT is: -
In cells AT and BS, one unit is added, so the additional cost is 3+1 = 4. In cell BT and AS, one
unit is deleted, and the cost is reduced by 5+2 = 7. By executing this change, we simultaneously
increase the total cost by 4 and reduce the total cost by 7, that is we alter the total cost by 4 – 7 =
-3. This value of –3 is the cell evaluator of cell AT.
The minus sign indicates a possible cost reduction i.e. the solution tested is improvable and
therefore not optimal. The value of a cell evaluator is the sum of the per unit shipping costs in the
gaining cells less the sum of the per unit shipping costs in the loosing cells of the closed loop.

12
Zetech Digital School
Operations Research
Evaluation of the cell DR (involving six cells)
A move of one unit to DR will result in the addition of one unit to AS and BT and the deletion of
one unit each from AR, BS and DT.

The value of the cell evaluator DR is 7 – 2 = 5. The plus sign indicates that a transfer to this cell
increases cost and is not favourable since it will increase the value of the objective function by 5.
By drawing the closed loops, all the empty cells of Table can be evaluated as shown below:-
Empty cell Cell evaluator

Empty Cell Cell Evaluator

AT -3
BR +4
DR +5
DS +4

Since one of the cell evaluators is negative, the existing solution is not optimal. The present
solution is therefore improvable. Two options exist for analyzing the cost of the above problem:

13
Zetech Digital School
Operations Research
1. Check empty cells until you find an improvable one and improve it. This option is less
efficient than the next.
2. Check all the empty cells and select for improvement the one with the largest improvement
potential. This second option is particularly efficient in large problems

Improving a Non-optimal Solution

Having discovered that a solution is not optimal, the next step is to find a better solution. The
following steps are followed:
1. Identify the “incoming” cell (the empty cell to be occupied). In a minimization case, the
incoming cell is located by identifying the most negative cell evaluator. In the example the
incoming cell is AT since it’s the only one with a negative cell evaluator.
2. Design an improved solution. An improvement is made by shifting as many units as possible
along the closed loop, into that empty cell. The quantity limit to this shifting process is reached
when one of the “losing” cells becomes empty.
Rule for shifting cells
Compare the number of units among all losing cells (-) in the loop of the most improvable empty
cell (AT in our case). Select the smallest number (10). Add this number to all cells with + sign
and subtract it from all cells with a – sign. The result is given in the table below:-

14
Zetech Digital School
Operations Research
 The solution compared to the original solution represents a reduction in cost of 30.

The maximization case

If the transportation problem involves maximization, the same method can be used. The only
difference is the test of optimality. A positive cell evaluator points to an improvement. An
optimal solution will show no positive cell evaluators. The stepping-stone method is efficient for
small-sized transportation problems. For larger problems, the MODI method is recommended.
Activity 3c
1. The following is a transportation problem with cost coefficients

TO 1 2 3 Supply
FROM
A 67X100 42 51X150 250-150=100-100=0
B 61 24X150 39X250 400-150=250-250=0
C 29X300 47 60 300-300=0
D 43 31 42X200 200-200=0
Demand 400- 150- 600- 1150
300=100- 150=0 250=350-
100=0 200=150-
150=0
(67X100)+(29X300)+(24X150)+(51X150)+(39X250)+(42x200)=
6700+8700+3600+7650+9750+8400=44800

Required:-
a. Find an initial solution using the least cost method.
b. Find the optimal solution using the stepping-stone method
2. Given a transportation problem with the following cost coefficients:

TO 1 2 3 4 Supply
FROM
A 1 5 3 4 100
B 4 2 2 4 60
C 3 1 2 4 120
Demand 70 50 100 60 280

a. Find an initial solution by the Northwest Corner Rule.

b. Find an optimal solution using the stepping stone method.

15
Zetech Digital School
Operations Research
The Modified Distribution Procedure (MODI)
MODI is based on the dual to the transportation problem. When the dual is solved, its solution
yields two types of variables: -

16
Zetech Digital School
Operations Research
 ui = implicit cost (or shadow price) of source i (value of one more unit at source i)
vj = implicit cost of destination j (value of one more unit at j)
The MODI procedure uses the values of ui and vj to find the cell evaluators. In an optimal
solution for transportation problem, the following two equations must hold; cij – ui –
(Equation 1)
Where cij is the per unit shipping cost between i and j and;
xij (cij – ui – vj ) = 0 (Equation 2)
Where xij is the quantity to be shipped between i and j.
These two conditions imply that when optimality is reached, one of the following two things may
occur: -
1. – ui – vj = 0, or cij = ui + vj, which means that an
allocation i to j will be made if and only if the actual cost of transportation cij is equal to
the sum of the implicit cost of source i plus the implicit cost of destination j. in such a
case, xij is called a basic variable i.e. cell ij is occupied.
2. If xij = 0, then one of the following two things can happen;
i. cij > ui + vj. In this case, an allocation i to j is not made, because the actual cost is larger than
the sum of the implied costs of the source i and the destination j. i. cij = ui + vj. In this case, the
nonbasic variable has the potential of being in the basis as an alternate optimal solution.
cij cannot be smaller than ui + vj without violating equation 1.
The concept of cell evaluators
Let Kij denote the cell evaluator, defined as:
Kij = cij – (ui + vj) = cij - ui - vj ( equation 3) The cell evaluator therefore is the difference
between the actual cost of shipping one unit from i to j, cij and the sum of the implicit costs of
source i and destination j.
The steps of modified distribution procedure (MODI) MODI requires a balanced transportation
table.
Step 1: Derive an initial solution.
Step 2: Use equation cij = ui + vj to compute all implicit costs of the occupied cells. Then,
compute the cell evaluators of all empty cells, using the equation Kij = cij - ui - vj. Test for
optimality as in the stepping-stone method.
Step 3: Identify an incoming cell and design an improved solution, as in the stepping-stone
method.
Step 4: Recycle the process until an optimal solution is found.
Example
Referring to the previous example of XYZ Company, the initial solution is shown in the

17
Zetech Digital School
Operations Research
 Destination
R S T Supply
Source
1 2 3
A 80 20 100

4 1 5
B 100 10 110

0 1 0
D(dummy) 50 50

Demand 80 120 60 260

Calculating the cell evaluators for all the empty cells and testing for optimality
Arbitrarily, a value of zero for u1 is chosen. The next question would be; what value must be
given to v1 so that the occupied cell AR, c11 = u1 + v1, or 1 = 0 + v1? v1 must take the value 1.
Again, what value must be given to v2 so that c12 = u1 + v2, or 2 = 0 + v2? v2 must be 2. Cell
AT can be skipped because it is unoccupied. What value must be given to u2 so that c22 = u2 +
v2, or 1 = u2 + 2? u2 = -1. In a similar manner v3 = 6 and u3 = -6.
All the row and column numbers are entered in the table as shown below in the new row vj and
new column ui

Computing the cell evaluators

For the empty cell BR, the cell evaluator according to the equation 3 is K21 = c21 – u2 – v1
= 4 + 1 –1 = 4. Similarly, the cell evaluators of the other empty cells are calculated and
summarized below:
Empty cell Cell evaluator Kij
BR c21 – u2 – v1 = 4 + 1 –1 = 4
AT c13 – u1 – v3 = 3 – 0 - 6 = -3
DR c31 – u3 – v1 = 0 + 6 – 1 = 5
18
Zetech Digital School
Operations Research
 DS c32 – u3 – v2 = 0 + 6 –2 = 4

Test for optimality

The optimality test is identical to that of the stepping stone method. An optimal solution requires
that all cells be nonnegative for minimization problems. Since the cell evaluator of AT is
negative, the solution is not optimal. An improved solution is thus called for.
Identifying the incoming cell and designing an improved solution
The incoming cell for a minimization case is located by identifying as in the stepping stone
method, the most negative cell evaluator. In this case, the incoming cell is AT. The improved
solution is obtained by shifting as many units as possible around a closed path into AT without
violating the demand and supply requirements. The improved solution is shown in the table
below:-

Recycling until optimality is achieved

All cell evaluators for the empty cells are computed by first recalculating the ui’s and
vj ’s. This is accomplished by using the equation cij = ui + vj for the occupied cells. The
cell evaluators for the empty cells off table are calculated as: -
Empty cell Cell evaluator
BR +4
BT +3
DR +2
DS +1
Since all the cell evaluators are positive, the solution in table is
optimal. This optimal solution therefore calls for a shipment of:
Tonnes From To Cost per Tonne Total
80 A R 1 80
19
Zetech Digital School
Operations Research
 10 A S 2 20
10 A T 3 30
110 B S 1 110
50 Dummy T 0 0
Total Cost 240

Economic interpretation of ui and vj

The variables ui and vj represent implicit costs associated with i sources and j destinations. ui is
the value of one unit of the product at source i. vj is the value of one unit of the product delivered
at destination j.
Activity 3d
Given a transportation problem with the following cost coefficients:

Destination 1 2 3 4 Supply
Sources
A 1 5 3 4 100
B 4 2 2 4 60
C 3 1 2 4 120
Demand 70 50 100 60 280

(b) Find an optimal solution by using MODI.

Degeneracy
A transportation problem has m supply constraints and n demand constraints. It should then have
m + n – 1 active variables (occupied cells) in every basic feasible solution as well as in the
optimal solution. Whenever the number of occupied cells is less than m + n – 1 the solution is
degenerate. Degeneracy can develop in one of two ways. First, it can
appear in the initial assignment, if the supply equals demand for any cell in which an assignment
is to be made. Secondly, it can develop during the improvement of solutions. If the quantities of
two or more losing cells of a non-degenerate solution are the same, they will become empty
simultaneously when an incoming variable is introduced. The resultant solution will then be
degenerate.
How to resolve Degeneracy
Degeneracy in the very first assignment
An extremely small amount, designated by E, (almost zero) of the commodity to be shipped is
allocated to one or more of the empty cells of the first solution to bring the number of occupied
cells to m + n – 1. In a minimization problem, E is allocated to the empty cell with the lowest
cost and that still allows the optimality check while in a maximization problem, to the cell with
the highest profit coefficient. The problem is then solved as if it were nondegenerate.

20
Zetech Digital School
Operations Research
 TO
R S Supply
DFROM
3 3
A 50

4 6
B 30

Demand 50 30 80

The above table is a minimization problem with cost data in which degeneracy will develop
when the initial solution is generated by the Northwest corner rule. The solution cannot be
checked for optimality since the test requires m + n –1 occupied cells i.e. 2 + 2 – 1 = 3. The
requirement can be met by adding the quantity E to the lowcost cell AS. It is then possible to test
for optimality, where upon it will be found that the solution is not optimal

TO
R S Supply
FROM
3 3
A 50 E 50

4 6
B 30 30

Demand 50 30 80

One improvement gives the solution shown in table [Link], which is both optimal and
nondegenerate

TO
R S Supply
FROM
3 3
A 20 30 50
4 6
B 30 30 30

Demand 50 30 80

21
Zetech Digital School
Operations Research
Degeneracy in intermediate solution stages
In this case, E is assigned to one or more of the newly vacated cells.
Example
Table [Link] contains an initial solution for a minimization problem with cost data. It is not
optimal and AT is in the incoming cell
Table [Link]: Initial Solution

Destination R S T Supply
Source
5 4 2
A 50 20 70
6 3 2
B 30 20 50
1 5 1
C 10 10

Demand 50 50 30 130

Table [Link] shows the first improved solution. The solution is degenerate. In order totest
optimality, E is added to cell BT (the newly vacated cell with the lowest coefficient).The
solution is not optimal and hence a second improved solution, table [Link] is derived.

The second improved solution is still degenerate, but on checking, turns out to be optimal. To
interpret the final solution, the value E is ignored. The total cost is sh. 420.

22
Zetech Digital School
Operations Research
THE ASSIGNMENT PROBLEM
The assignment problem deals with finding the best one-to-one match for each of a given
number of ‘candidates’ to a number of positions e.g. assigning teachers to classes or workers to
machines. Different benefits or costs are involved in each match and the goal is to maximize the
total reward or minimize the total expense.
Characteristics of the Assignment problem
1. The objects under consideration such as service teams, jobs, employees or projects are finite in
number.
2. The objects have to be assigned on a one-to-one basis to other objects.
3. The results of each assignment can be expressed in terms of payoffs such as costs or profits.
4. The aim is to assign all objects (if possible) in such a way that the total cost is minimized (or
the total profit is maximized).
Presentation of the assignment problem
Presentation in Tabular form.
The assignment problem is usually arranged in a tabular form. The assignment table is similar to
the transportation table. The assignment problem is considered as a special transportation
problem in which the supply at each and the demand at each destination are always one unit.
Assignment problems can be balanced or not. In a balanced case, the number of objects to be
assigned equals the number of objects to which they are assigned. Unbalanced problems can be
balanced by adding a dummy with zero cost coefficients.
Presentation as a Linear Programming problem.
The assignment problem can be presented as a Linear Programming problem. The objective
function expresses the total cost or profit of the assignment. The constraints arethe supply and
demand constraints.
Example
The management of a utility company wants to assign three service teams to three geographical
zones, one team to each zone. Because of each teams differing familiarity with each zone, there

23
Zetech Digital School
Operations Research
are differences in the efficiency of each team, a fact that is reflected in the different service costs
(in thousand shillings) as shown in the table below

ZONE Z1 Z2 Z3
Service Team
S1 20 15 31
S2 17 16 33
S3 18 19 27

Required:
i. Formulate the above problem as a Linear programming problem.
ii. Present the above assignment problem in a tabular form.
Solution
Formulating as a Linear Programming problem.
The objective function expresses the total cost or profit of the assignment. The constraints are the
supply and demand constraints.
Minimize Z = 20 x11 + 15x12 + 31x13 + 17x21 + 16x22 + 33x23 + 18x31 + 19x32 + 27x33
Subject to
Supply constraints
X11 + X12 + X13 = 1
X21 + X22 + X23 = 1
X31 + X32 + X33 = 1
And demand constraints
X11 + X21 + X31 = 1
X12 + X22 + X32 = 1
X13 + X23 + X33 = 1

Presentation in tabular form

ZONE Z1 Z2 Z3 Supply
Service
Team
S1 20 15 31 1
S2 17 16 33 1
S3 18 19 27 1
24
Zetech Digital School
Operations Research
 Demand 1 1 1

Methods for solving assignment problems

Complete enumeration
The assignment problem is usually a balanced problem with n items to be assigned to n objects.
As such there are n! different solutions to the problem. One way to find the optimal solution is to
list and compare all n! solutions. However, it is often impractical because the number of
solutions for even a relatively small problem isunmanageably large.
The simplex method
The simplex method can be used, but it is rather inefficient for solving the assignment problem.
The transportation Model
Any assignment problem can be solved by the transportation method since the assignment
problem is a special case of the transportation problem. However, there are more efficient
methods.
“Near-Optimal” methods
Various computational methods are available for arriving at a near-optimal solution in a way.
These are mainly heuristic in nature.
The Hungarian method
The Hungarian method is the most efficient way of solving large assignment problems. The
procedure is based on the following theorem:-
“ If one subtracts (or adds) a constant number from all entries in any row or column of the
assignment matrix, then the total cost of each of the n! possible assignment is reduced (or
increased) by the constant number subtracted (or added).
The Hungarian method

Start

Arrange problem as a table

Convert to minimization; Substract

Is is a
52 all entries from largest entry in the
maximization
table
Zetech Digital School
problem
Operations Research
 Is it Add dummies to balance problem
Balanced

Build total opportunity

cost table

Improvable solution: Identify smallest

Can all zeros in uncovered entry. Subtract it from all
table cells without lines
be covered by fewer Add it to all cells with intersecting
than n lines? N= no. lines. Cells with one line remain
of rows ( or unchanged. Result = improved
solution.
columns)

Identify optimal solutions by making

assignments to zero-valued cells in
one-toone

Calculate cost or profit of

assignments by

Example Stop

Refer to the utility company problem. Since the problem is a minimization problem and it is
balanced, then the first step is to build the total–opportunity –cost table.
3.13.1 Building a balanced “total opportunity cost” matrix
This step involves the transformation of cost matrix to a total-opportunity-cost matrix. It involves
two operations. First, the element with the lowest value (including zero and negative numbers) in

53
Zetech Digital School
Operations Research
each row is subtracted from all the other elements in that row. All negative numbers disappear in
this step.
First operation for the improved matrix
Zone Z1 Z2 Z3 Z1 Z2 Z3
Team
31-
S1 20-15=5 15-15=0 15=16 5 0 16
33-
S2 17-16=1 16-16=0 16=17 1 0 17
S3 18-18=0 19-18=1 27-18=9 0 1 9

Secondly, the smallest element (including zero) in each column of the new matrix is subtracted
from all the elements of that column. The result is the total opportunity cost matrix.

Zone Z1 Z2 Z3 Z1 Z2 Z3
Team
S1 5-0=5 0-0=0 16-9=7 5 0 7
S2 1-0=1 0-0=0 17-9=8 1 0 8
S3 0-0=0 1-0=1 9-9=0 0 1 0

The optimality Test

Since all entries in the total opportunity cost matrix are nonnegative, the minimumNvalue of the
objective function cannot be negative, no matter what assignments are made. If a feasible
assignment with a total opportunity cost of zero is found, this assignment must have the lowest
possible cost. The lowest possible cost can be achieved if all the values in the cells where
assignments are made are zeros.
The following procedure can be used: -
1. Draw the minimum necessary number of straight lines, horizontally and vertically, so that all
zeros in the matrix are covered. Draw the lines by trial and error method but always try to cover
two or more zeros with one line.
2. Count the number of these lines. If it equals n (the number of rows and columns) an optimal
assignment can be made. If it is smaller than n, an improvement is possible. The table has four
“zero” cells. It is possible to cover all the zeros with two lines, one through row S3 and the other
through column Z2.
Zone Z1 Z2 Z3
Team
S1 5 0 7
S2 1 0 8
S3 0 1 0
According to the optimality test, since only two lines are needed to cover all the zeros, an
optimal assignment cannot be made at this stage and an improved solution is possible.
Improve the total – opportunity-cost matrix
An improved total-opportunity-cost matrix is derived by the following three operations:
1. Find the smallest entry in the uncovered cells (cells with no lines through them)and subtract it
from all entries in the uncovered cells. In our example, the lowest entry is 1 (Cell S2Z1).
2. Add the same smallest entry to those cells in which the lines intersect (cells with two lines
through them) i.e. S3Z2
3. Cells with one line through them, such as S1Z2 are transferred unchanged to the improved
table.

In those problems where the first improvement does not yield an optimal solution, the solution is
improved until an optimal solution is achieved
Make an optimal assignment
An optimal assignment should be made to cells with a zero entry, maintaining the one-toone
requirement. If only one solution exists, a fast procedure for finding it is to locate a row or
column with only one zero in it and make that assignment. Then drop that row and column and
repeat the procedure. If the solution is not unique, there will be two or more zeros in a column or
row to choose from. The choice is the arbitrary.
The optimal assignment in our example would be, S1 to Z2, S2 to Z1 and S3 to Z3. The total
cost in this case is 15 + 17 + 27 = 59 (thousand shillings).
Activity 3f
1. The cost of assigning jobs A, B and C n machines M, N, O and P is shown
Machine M N O P
JOB
 A 6 7 5 9
B 8 5 6 7
C 10 8 6 6
Required
a. Formulate as a Linear programming problem.
b. Use the Hungarian method to find the least cost assignment.

2. Four jobs are to be allocated to four machines in accordance with the information
given below, which relate to the time each machine would take to complete each
job.

Machine Time in Minutes

1 2 3 4
A 10 28 20 13
B 16 30 7 28
Jobs
C 33 22 21 17
D 21 29 27 12

Find out the allocation of time to four machines, which minimizes total running time.

The maximization case

In maximization cases, a convenient solution or procedure involves transforming the problem
into a minimization problem (an opportunity loss table) by the following procedure: -
1. Find the largest profit coefficient in the entire table.
2. Subtract each entry in the original table from the largest profit coefficient
Example
Maximize
R S T
A 8 6 10
B 11 9 6
C 4 7 5

Solution
Minimize (after transformation)

R S T R S T
11-
A 11-8=3 11-6=5 10=1 3 5 1
0 2 5
B 11-11=0 11-9=2 11-6=5
 C 11-4=7 11-7=4 11-5=6 7 4 6

Once the transformed table is constructed, the Hungarian method can then be employed to solve
the problem. Once a solution is obtained, the total profit can be computed using the original
profit coefficients in the original table.
Activity 3g
A company has four plants, each of which can manufacture any one of the four products.
Production costs differ from one plant to another, as do the costs of raw material. Given
the profit data below, assign the products to plants for maximum profit.

Products -Profits in 000's

A B C D
1 1 8 4 1
2 5 7 66 5
Plant
3 3 5 4 2
4 3 1 6 3

3.7 Vogel’s Approximation Method

Definition: The Vogel’s Approximation Method or VAM is an iterative procedure calculated
to find out the initial feasible solution of the transportation problem. Like Least cost Method,
here also the shipping cost is taken into consideration, but in a relative sense. The following is
the flow chart showing the steps involved in solving the transportation problem using the
Vogel’s Approximation Method:
 The concept of Vogel’s Approximation Method can be well understood through an illustration
given below:

1. First of all the difference between two least cost cells are calculated for each row and
column, which can be seen in the iteration given for each row and column. Then the largest
difference is selected, which is 4 in this case. So, allocate 20 units to cell BD, since the minimum cost
is to be chosen for the allocation. Now, only 20 units are left with the source B.

2. Column D is deleted, again the difference between the least cost cells is calculated for
each row and column, as seen in the iteration below. The largest difference value comes to be 3,
so allocate 35 units to cell AF and 15 units to the cell AE. With this, the Supply and demand of
source A and origin F gets saturated, so delete both the row A and Column

F.
3. Now, single column E is left, since no difference can be found out, so allocate 60 units to
the cell CE and 20 units to cell BE, as only 20 units are left with source B. Hence the demand

and supply are completely met.

Now the total cost can be computed, by multiplying the units assigned to each cell with the cost
concerned. Therefore,

Total Cost = 20*3 + 35*1 + 15*4 + 60*4 + 20*8 = Rs 555

Note: Vogel’s Approximation Method is also called as Penalty Method because the difference
costs chosen are nothing but the penalties of not choosing the least cost routes.
on-zero components of x and y, respectively.

150
1501
50
Zetech Digital School