DAYANANDA SAGAR COLLEGE OF ENGINEERING

(An Autonomous Institute Affiliated to VTU, Belagavi)

Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Course Material

COURSE Probability Theory and Optimization

COURSE CODE 22MAT41D

MODULE III

MODULE Optimization
NAME
STAFF Dr. Rose Bindu Joseph P
INCHARGE
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Introduction
Transportation problem is a special kind of Linear Programming Problem (LPP) in which goods
are transported from a set of sources to a set of destinations subject to the supply and demand of the
sources and destination respectively such that the total cost of transportation is minimized. It is also
sometimes called as Hitchcock problem.

Types of Transportation problems:

Balanced: When both supplies and demands are equal then the problem is said to be a balanced
transportation problem.

Unbalanced: When the supply and demand are not equal then it is said to be an unbalanced
transportation problem. In this type of problem, either a dummy row or a dummy column is added
according to the requirement to make it a balanced problem. Then it can be solved similar to the
balanced problem.

Methods to Solve:
To find the initial basic feasible solution there are three methods:
1. NorthWest Corner Cell Method.
2. Least Call Cell Method.
3. Vogel’s Approximation Method (VAM).

Basic structure of transportation problem:

In the above table D1, D2, D3 and D4 are the destinations where the products/goods are to be
1
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

delivered from different sources S1, S2, S3 and S4. Si is the supply from the source Oi. dj is the
demand of the destination Dj. Cij is the cost when the product is delivered from source Si to
destination Dj.

Northwest Corner Method

We begin in the upper left corner of the transportation tableau and set x11 as large as possible (clearly,
x11 can be no larger than the smaller of s1 and d1).
• If x11=s1, cross out the first row of the tableau. Also change d1 tod1-s1.
• If x11=d1, cross out the first column of the tableau. Change s1 tos1-d1.
• If x11=s1=d1, cross out either row 1 or column 1 (but not both!).
o If you cross out row, change d1 to 0.
o If you cross out column, change s1 to 0.
Continue applying this procedure to the most northwest cell in the tableau that does not lie in a
crossed out row or column.
Eventually, you will come to a point where there is only one cell that can be assigned a value. Assign
this cell a value equal to its row or column demand, and cross out both the cell’s row or column. A bfs
has now been obtained

2
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Explanation: Given three sources O1, O2 and O3 and four destinations D1, D2, D3 and D4. For the
sources O1, O2 and O3, the supply is 300, 400 and 500 respectively. The
destinations D1, D2, D3 and D4 have demands 250, 350, 400 and 200 respectively.
Solution: According to North West Corner method, (O1, D1) has to be the starting point i.e. the north-
west corner of the table. Each and every value in the cell is considered as the cost per transportation.
Compare the demand for column D1 and supply from the source O1 and allocate the minimum of two
to the cell (O1, D1) as shown in the figure.
The demand for Column D1 is completed so the entire column D1 will be canceled. The supply from
the source O1 remains 300 – 250 = 50.

Now from the remaining table i.e. excluding column D1, check the north-west corner i.e. (O1, D2) and
allocate the minimum among the supply for the respective column and the rows. The supply
from O1 is 50 which is less than the demand for D2 (i.e. 350), so allocate 50 to the cell (O1, D2).
Since the supply from row O1 is completed cancel the row O1. The demand for
column D2 remain 350 – 50 = 300.

3
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

From the remaining table the north-west corner cell is (O2, D2). The minimum among the supply from
source O2 (i.e 400) and demand for column D2 (i.e 300) is 300, so allocate 300 to the cell (O2, D2).
The demand for the column D2 is completed so cancel the column and the remaining supply from
source O2 is 400 – 300 = 100.

Now from remaining table find the north-west corner i.e. (O2, D3) and compare the O2 supply (i.e.
100) and the demand for D2 (i.e. 400) and allocate the smaller (i.e. 100) to the cell (O2, D2). The
supply from O2 is completed so cancel the row O2. The remaining demand for
column D3 remains 400 – 100 = 300.

Proceeding in the same way, the final values of the cells will be:

4
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Note: In the last remaining cell the demand for the respective columns and rows are equal which was
cell (O3, D4). In this case, the supply from O3 and the demand for D4 was 200 which was allocated to
this cell. At last, nothing remained for any row or column.
Now just multiply the allocated value with the respective cell value (i.e. the cost) and add all of them
to get the basic solution i.e. (250 * 3) + (50 * 1) + (300 * 6) + (100 * 5) + (300 * 3) + (200 * 2) = 4400

Least Cost Cell Method

The least-cost method finds a better starting solution by targeting the cheapest routes. It assigns as
much as possible to the cell with the smallest unit cost (ties are broken arbitrarily). Next, the satisfied
row or column is crossed out and the
amounts of supply and demand are adjusted accordingly. If both a row and a column are satisfied
simultaneously, only one is crossed out, the same as in the northwest-corner method. Next, select the
uncrossed-out cell with the smallest unit cost and repeat the process until exactly one row or column is
left uncrossed out.

5
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Solution: According to the Least Cost Cell method, the least cost among all the cells in the table has to
be found which is 1 (i.e. cell (O1, D2)).
Now check the supply from the row O1 and demand for column D2 and allocate the smaller value to
the cell. The smaller value is 300 so allocate this to the cell. The supply from O1 is completed so
cancel this row and the remaining demand for the column D2 is 350 – 300 = 50.

Now find the cell with the least cost among the remaining cells. There are two cells with the least cost
i.e. (O2, D1) and (O3, D4) with cost 2. Lets select (O2, D1). Now find the demand and supply for the
respective cell and allocate the minimum among them to the cell and cancel the row or column whose
supply or demand becomes 0 after allocation.

Now the cell with the least cost is (O3, D4) with cost 2. Allocate this cell with 200 as the demand is
smaller than the supply. So the column gets cancelled.
6
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

There are two cells among the unallocated cells that have the least cost. Choose any at random
say (O3, D2). Allocate this cell with a minimum among the supply from the respective row and the
demand of the respective column. Cancel the row or column with zero value.

Now the cell with the least cost is (O3, D3). Allocate the minimum of supply and demand and cancel
the row or column with zero value.

7
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

The only remaining cell is (O2, D3) with cost 5 and its supply is 150 and demand is 150 i.e. demand
and supply both are equal. Allocate it to this cell.

Now just multiply the cost of the cell with their respective allocated values and add all of them to get
the basic solution i.e. (300 * 1) + (250 * 2) + (150 * 5) + (50 * 3) + (250 * 3) + (200 * 2) = 2850

8
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Vogel’s Approximation Method

Vogel’s Method Begin by computing for each row and column a penalty equal to the difference
between the two smallest costs in the row and column. Next find the row or column with the largest
penalty. Choose as the first basic variable the variable in this row or column that has the smallest cost.
As described in the NWC method, make this variable as large as possible, cross out row or column,
and change the supply or demand associated with the basic variable (See Northwest Corner Method for
the details!). Now recomputed new penalties (using only cells that do not lie in a crossed out row or
column), and repeat the procedure until only one uncrossed cell remains. Set this variable equal to the
supply or demand associated with the variable, and cross out the variable’s row and column

Solution:
• For each row find the least value and then the second least value and take the absolute difference of
these two least values and write it in the corresponding row difference as shown in the image
below. In row O1, 1 is the least value and 3 is the second least value and their absolute difference
is 2. Similarly, for row O2 and O3, the absolute differences are 3 and 1 respectively.
• For each column find the least value and then the second least value and take the absolute
difference of these two least values then write it in the corresponding column difference as shown
in the figure. In column D1, 2 is the least value and 3 is the second least value and their absolute
difference is 1. Similarly, for column D2, D3 and D3, the absolute differences

9
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

are 2, 2 and 2 respectively.

• These value of row difference and column difference are also called as penalty. Now select the
maximum penalty. The maximum penalty is 3 i.e. row O2. Now find the cell with the least cost in
row O2 and allocate the minimum among the supply of the respective row and the demand of the
respective column. Demand is smaller than the supply so allocate the column’s demand i.e. 250 to
the cell. Then cancel the column D1.

• From the remaining cells, find out the row difference and column difference.

10
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

• Again select the maximum penalty which is 3 corresponding to row O1. The least-cost cell in
row O1 is (O1, D2) with cost 1. Allocate the minimum among supply and demand from the
respective row and column to the cell. Cancel the row or column with zero value.

• Now find the row difference and column difference from the remaining cells.

• Now select the maximum penalty which is 7 corresponding to column D4. The least cost cell in
column D4 is (O3, D4) with cost 2. The demand is smaller than the supply for cell (O3, D4).

11
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Allocate 200 to the cell and cancel the column.

• Find the row difference and the column difference from the remaining cells.

12
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

• Now the maximum penalty is 3 corresponding to the column D2. The cell with the least value
in D2 is (O3, D2). Allocate the minimum of supply and demand and cancel the column.

• Now there is only one column so select the cell with the least cost and allocate the value.

13
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

• Now there is only one cell so allocate the remaining demand or supply to the cell

• No balance remains. So multiply the allocated value of the cells with their corresponding cell cost
and add all to get the final cost i.e. (300 * 1) + (250 * 2) + (50 * 3) + (250 * 3) + (200 * 2) + (150 *
5) = 2850

14
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

MODI Method – UV Method

There are two phases to solve the transportation problem. In the first phase, the initial basic feasible
solution has to be found and the second phase involves optimization of the initial basic feasible
solution that was obtained in the first phase. There are three methods for finding an initial basic
feasible solution,
This article will discuss how to optimize the initial basic feasible solution through an explained
example. Consider the below transportation problem.

Solution:
Step 1: Check whether the problem is balanced or not.
If the total sum of all the supply from sources O1, O2, and O3 is equal to the total sum of all the
demands for destinations D1, D2, D3 and D4 then the transportation problem is a balanced
transportation problem.

Note: If the problem is not unbalanced then the concept of a dummy row or a dummy column to
transform the unbalanced problem to balanced can be followed as discussed in this article.
15
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Step 2: Finding the initial basic feasible solution.

Any of the three aforementioned methods can be used to find the initial basic feasible solution.
Here, NorthWest Corner Method will be used. And according to the NorthWest Corner Method this is
the final initial basic feasible solution:

Now, the total cost of transportation will be (200 * 3) + (50 * 1) + (250 * 6) + (100 * 5) + (250 * 3) +
(150 * 2) = 3700.
Step 3: U-V method to optimize the initial basic feasible solution.
The following is the initial basic feasible solution:

16
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

– For U-V method the values ui and vj have to be found for the rows and the columns respectively. As
there are three rows so three ui values have to be found i.e. u1 for the first row, u2 for the second row
and u3 for the third row.
Similarly, for four columns four vj values have to be found i.e. v1, v2, v3 and v4. Check the image
below:

There is a separate formula to find ui and vj,

ui + vj = Cij where Cij is the cost value only for the allocated cell. Read more about it here.
Before applying the above formula we need to check whether m + n – 1 is equal to the total number
of allocated cells or not where m is the total number of rows and n is the total number of columns.
In this case m = 3, n = 4 and total number of allocated cells is 6 so m + n – 1 = 6. The case when m + n
– 1 is not equal to the total number of allocated cells will be discussed in the later posts.
Now to find the value for u and v we assign any of the three u or any of the four v as 0. Let we
assign u1 = 0 in this case. Then using the above formula we will get v1 = 3 as u1 + v1 = 3 (i.e. C11)
and v2 = 1 as u1 + v2 = 1 (i.e. C12). Similarly, we have got the value for v2 = 1 so we get the value
for u2 = 5 which implies v3 = 0. From the value of v3 = 0 we get u3 = 3 which implies v4 = -1. See the
image below:

17
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Now, compute penalties using the formula Pij = ui + vj – Cij only for unallocated cells. We have two
unallocated cells in the first row, two in the second row and two in the third row. Lets compute this
one by one.
1. For C13, P13 = 0 + 0 – 7 = -7 (here C13 = 7, u1 = 0 and v3 = 0)
2. For C14, P14 = 0 + (-1) -4 = -5
3. For C21, P21 = 5 + 3 – 2 = 6
4. For C24, P24 = 5 + (-1) – 9 = -5
5. For C31, P31 = 3 + 3 – 8 = -2
6. For C32, P32 = 3 + 1 – 3 = 1
The Rule: If we get all the penalties value as zero or negative values that mean the optimality is
reached and this answer is the final answer. But if we get any positive value means we need to proceed
with the sum in the next step.
Now find the maximum positive penalty. Here the maximum value is 6 which corresponds to C21 cell.
Now this cell is new basic cell. This cell will also be included in the solution.

18
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

The rule for drawing closed-path or loop. Starting from the new basic cell draw a closed-path in
such a way that the right angle turn is done only at the allocated cell or at the new basic cell. See the

below images:

Assign alternate plus-minus sign to all the cells with right angle turn (or the corner) in the loop with
plus sign assigned at the new basic cell.

19
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Consider the cells with a negative sign. Compare the allocated value (i.e. 200 and 250 in this case) and
select the minimum (i.e. select 200 in this case). Now subtract 200 from the cells with a minus sign
and add 200 to the cells with a plus sign. And draw a new iteration. The work of the loop is over and
the new solution looks as shown below.

Check the total number of allocated cells is equal to (m + n – 1). Again find u values and v values
using the formula ui + vj = Cij where Cij is the cost value only for allocated cell. Assign u1 = 0 then we
get v2 = 1. Similarly, we will get following values for ui and vj.

20
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Find the penalties for all the unallocated cells using the formula Pij = ui + vj – Cij.
1. For C11, P11 = 0 + (-3) – 3 = -6
2. For C13, P13 = 0 + 0 – 7 = -7
3. For C14, P14 = 0 + (-1) – 4 = -5
4. For C24, P24 = 5 + (-1) – 9 = -5
5. For C31, P31 = 0 + (-3) – 8 = -11
6. For C32, P32 = 3 + 1 – 3 = 1
There is one positive value i.e. 1 for C32. Now this cell becomes new basic cell.

Now draw a loop starting from the new basic cell. Assign alternate plus and minus sign with new basic
cell assigned as a plus sign.

21
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Select the minimum value from allocated values to the cell with a minus sign. Subtract this value from
the cell with a minus sign and add to the cell with a plus sign. Now the solution looks as shown in the
image below:

Check if the total number of allocated cells is equal to (m + n – 1). Find u and v values as above.

Now again find the penalties for the unallocated cells as above.
22
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

1. For P11 = 0 + (-2) – 3 = -5

2. For P13 = 0 + 1 – 7 = -6
3. For P14= 0 + 0 – 4 = -4
4. For P22= 4 + 1 – 6 = -1
5. For P24= 4 + 0 – 9 = -5
6. For P31= 2 + (-2) – 8 = -8
All the penalty values are negative values. So the optimality is reached.
Now, find the total cost i.e. (250 * 1) + (200 * 2) + (150 * 5) + (50 * 3) + (200 * 3) + (150 * 2) = 2450

23
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

ASSIGNMENT PROBLEM

The assignment problem is a special case of transportation problem in which the objective is to assign
‘m’ jobs or workers to ‘n’ machines such that the cost incurred is minimized.
JOBS

1 2 -------- n

1 C11 C12 ---------------- C1n

2 C21 C22 ---------------- C2n

- - -
--
- - -
WORKERS --

-- - - -

Cn1 Cn2 -------------- Cmn

n

The element Cij represents the cost of assigning worker I to job (I,j= 1,2,---n). There is no loss in
generality in assuming that the number of workers always equals the number of jobs because
we can always add fictitious (untrue or fabricated) workers or fictitious jobs to effect this result.

The assignment model is actually a special case of the transportation model in which the
workers represent the sources and the jobs represent the destinations.

The supply amount at each source and the demand amount at each destination exactly equal 1.

24
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

The cost of transporting workers I to job j is Cij .

The assignment model can be solved directly as a regular transportation model.

The fact that all the supply and demand amounts equal 1 has led to the development of a
simple solution algorithm called the Hungarian method.

Difference between transportation and Assignment problems

Sl. No. Transportation Assignment
1 This problem contains specific demand and The demand and availability in
requirement in columns and rows each column or row is one
2 Total demand must be equal to the total It is a square matrix. The no of
availability rows must be equal to the no
of columns.
3 The optimal solution involves the following The optimal solutions involves
conditions M+N-1 one assignment in each row
M rows and each column
N columns

4 There is no restriction in the number of allotments There should be only one

in any row or column allotment in each row and
each column
5 It is a problem of allocating multiple resources to It is a problem of allocation
multiple markets resources to job j

25
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Assignment Algorithm (Hungarian Method)

Step I :- Create Zero elements in the cost matrix by subtract the smallest element in each row
column for the corresponding row and column.

Step II:- Drop the least number of horizontal and vertical lines so as to cover all zeros if the no
of there lines are ‘N’
i) If N = n (n=order of the square matrix) then an optimum assignment has been
obtained
ii) If N<n proceeds to step III

Step III :- determine the smallest cost cell from among the uncrossed cells subtract. This cost
from all the uncrossed cells and add the same to all those cells laying in the intersection of
horizontal and vertical lines.

Step IV:- repeat steps II and III until N=n.

Step V:- examine the rows (column) successively until a row (column) with are zero is found
enclose the zero in a square (0) and cancel out (0) any other zeros laying in the column (row) of
the Matrix. Continue in this way until all the rim requirements are satisfied i.e N=n.

Step VI:- repeat step 5 successively one of the following arises.

i) No unmarked zero is left
ii) If more then one unmarked zeros in one column or row.

26
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

In case i) the algorithm stops

ii)Encircle one of the unmarked zeros arbitrary and mark a cross in the cells of
remaining zeroes in it’s row and column. Repeat the process until no unmarked zero
is left in the cost matrix.

Step VII) we now have exactly one encircled zero in each row and each column of the cost
matrix. The assignment schedule corresponding to there zeros is the optimum (maximal)
assignment.

Note: the above procedure for assignment is Hungarian assignment method

Problem 1.
Three jobs A B C are to be assigned to three machines x Y Z. The processing costs are as given in
the matrix shown below. Find the allocation which will minimize the overall processing cost.

Machines
X Y Z
Jobs A 19 28 31
B 11 17 16
C 12 15 13

Solution:
Step 1: create zero in each row or column by subtracting by selecting least number in each row
and column

27
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Row Minimization
0 9 12
0 6 5
0 3 1
Column Minimization
0 6 11
0 3 4
0 0 0
Now draw Horizontal and vertical lines
0 6 11
0 3 4
0 0 0

Here, no of horizontal lines is one and vertical line is one

The order of matrix is 3 x 3, therefore, N≠ n

Now, in the uncrossed cell the least cost is selected and subtracted for the remaining uncrossed
cell by the least value and for the intersection of the horizontal line and vertical line the least
value should be added and the resulting matrix.
0 3 8
0 0 1
3 0 0

28
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

The above matrix has two horizontal line and one vertical line which satisfies our condition N= n
{0} 3 8
0 {0} 1
3 0 {0}

The assignment are A X = 19

B Y = 17
C Z = 13
49

Problem 2

A typical assignment problem, presented in the classic manner, is shown in Fig. Here there are
five machines to be assigned to five jobs. The numbers in the matrix indicate the cost of doing
each job with each machine. Jobs with costs of M are disallowed assignments. The problem is
to find the minimum cost matching of machines to jobs.

29
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Fig 1 Matrix model of the assignment problem.

The network model is in shown in Fig.2. It is very similar to the transportation model except the
external flows are all +1 or -1. The only relevant parameter for the assignment model is arc cost
(not shown in the figure for clarity) ; all other parameters should be set to default values. The
assignment network also has the bipartite structure.

Figure 2. Network model of the assignment problem.

M 8 6 12 1
15 12 7 M 10
10 M 5 14 M
12 M 12 16 15
18 17 14 M 13

This is the given problem, using Hungarian method we solve the problem

Row minimization
M 7 5 11 0
8 5 0 M 3
5 M 0 9 M
0 M 0 4 3
5 4 1 M 0

30
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Column minimization

M 3 5 7 0
8 1 0 M 3
5 M 0 5 M
0 M 0 0 3
5 0 1 M 0

N≠n, 4≠5 so select least value in

M 3 5 7 0
The uncrossed cell and subtract
8 1 0 M 3
5 M 0 5 M
0 M 0 0 3

5 0 1 M 0

M 2 5 6 0
7 0 0 M 3
4 M 0 4 M
0 M 1 0 3
2 0 1 M 0
N≠n, 4≠5 so select least value in The uncrossed cell
and subtract
M 2 5 2 [0]
3 0 [0] M 3
0 M 0 [0] M
[0] M 1 0 3
2 [0] 1 M 0

31
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

M 2 5 2 0
3 0 0 M 3
0 M 0 0 M
0 M 1 0 3
2 0 1 M 0

N=n and the assignment can be done

The solution to the assignment problem as shown in Fig. 3 has a total flow of 1 in every column
and row, and is the assignment that minimizes total cost.

Figure 3. Solution to the assignment Problem

32
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Problem 3.
Four different jobs can be done on four different machines and take down time costs
are prohibitively high for change overs. The matrix below gives the cost in rupees of
producing job
on machine j;
Jobs Machine
M1 M2 M3 M4
J1 5 7 11 6
J2 8 5 9 6
J3 4 7 10 7
J4 10 4 8 3

How the jobs should be assigned to the various machines so that the total cost is minimized.

Row minimization
0 2 6 1
3 0 4 1
0 3 6 3
7 1 5 0
Column minimization
0 2 2 1
3 0 0 1
0 3 2 3
7 1 1 0

33
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Draw the horizontal and vertical lines which covers max no of zeros
0 2 2 1
3 0 0 1
0 3 2 3
7 1 1 0
N≠n 3≠4
The least value is 1, the resulting table
0 1 1 1
4 0 0 2
0 2 1 3
7 0 0 0
N≠n
3≠4
The least value is 1, the resulting table
0 0 0 0
5 0 0 2
0 1 0 2
8 0 0 0
N=n

34
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

4=4 the assignment can be made for the above optimal table

0 0 0 [0]
5 [0] 0 2
[0] 1 0 2
8 0 [0] 0

J1 ----------M4 = 6
J2----------M2 = 5
J3----------M1 = 4
J4----------M3 = 8
23

Alternate solution

[0] 0 0 0
5 [0] 0 2
0 1 [0] 2
8 0 0 [0]

J1 ----------M1 = 5
J2----------M2 = 5
J3----------M3 = 10
J4----------M4 = 3
23
35
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Problem 4
A company has 5 jobs tobe done the following matrix shows the return in Rs. of assigning ith
machine (i=1,2,3,---5) to the jth job (j=1,2,3,----n). Assign the 5 jobs to the 5 machines so as to
maximize the expected profit.
JOB
1 2 3 4 5
1 5 11 10 12 4
2 2 4 6 3 5
Machine 3 3 12 5 14 6
4 6 14 4 11 7
5 7 9 8 12 8

Since, the given problem is maximum

Step 1: to convert the problem to a minimum by multiply all elements Cij Of the assignment
matrix by -1
Then the given problem will in the form as shown below

JOB
1 2 3 4 5
1 -5 -11 -10 -12 -4
2 -2 -4 -6 -3 -5
Machine 3 -3 -12 -5 -14 -6
4 -6 -14 -4 -11 -7
5 -7 -9 -8 -12 -8

36
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Step2: select the most –ve and subtract with other elements of the matrix minz= - (-maxZ) In
the matrix the most –ve value is -14. Using this value the matrix is subtracted and the
resulting is the minimization matrix. This can be used for finding the optimal assignment table
using usual procedure to solve the problem.

JOB
1 2 3 4 5
1 9 3 4 2 10
2 12 10 8 11 9
Machine 3 11 2 9 0 8
4 8 0 10 3 7
5 7 5 6 2 6
Example
C11= -5 – (-14) = 9 and continued for all other element
Step 3:- Using the above table i.e. minZ matrix table and all cost elements non-ve. The
Hungarian method can be applied to find the optimal assignment problem.

Row minimization
7 1 2 0 8
4 2 0 3 1
11 2 9 0 8
8 0 10 3 7
5 3 4 0 4

37
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Column minimization
3 1 2 0 7
0 2 0 3 0
7 2 9 0 7
4 0 10 3 6
1 3 4 0 3

N=3, n=5x5
N≠n, select the minimum value from the uncrossed cell and subtract for all the elements of
uncrossed cell and add for the intersection of horizontal and vertical.

2 1 1 0 6
0 3 0 4 0
6 2 8 0 6
3 0 9 3 5
0 3 3 0 2

N=4 n=5x5
N≠n
The least value in the uncrossed cell is 1 again and subtracts using this value for all other
elements and add for intersection of horizontal and vertical

2 1 0 0 5
1 4 0 5 0
6 2 7 0 5
3 0 8 3 4

38
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

0 3 2 0 1
N=n, for assignment the optimal table is obtained

2 1 [0] 0 5
1 4 0 5 [0]
6 2 7 [0] 5
3 [0] 8 3 4
[0] 3 2 0 1

Now the assignment is

1-----------3 = 10
2-----------5 = 5
3-----------4 = 14
4-----------2 = 14
5-----------1 = 7
50

39
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Problem 5
A marketing manager has 5 elements and there are 5 sales districts. Considering the capabilities
of the salesmen and the nature of districts, the estimates made by the marketing manager for
the sales per month (in 1000 rupees) for each salesman in each district would be as follows.

A B C D E
1 32 38 40 28 40
2 40 24 28 21 36
3 41 27 33 30 37
4 22 38 41 36 36
5 29 33 40 35 39
Find the assignment of salesmen to the districts that will result in the maximum sale.

Solution:
The given problem is profit matrix. To maximize the profit, first we must convert it
minimization. To convert to minimization we must select the maximum value of the matrix i.e.,
41. This value is subtracted for all other elements in the matrix and the resulting matrix is
minimization.

A B C D E
1 9 3 1 13 1
2 1 17 13 20 5
3 0 14 8 11 4
4 19 3 0 5 5
5 12 8 1 6 2

Using above table we can solve the given problem by the Hungarian method.

40
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Row minimization
8 2 0 12 0
0 16 12 19 4
0 14 8 11 4
19 3 0 5 5
11 7 0 5 1

Column minimization
8 0 0 7 0
0 14 12 14 4
0 12 8 6 4
19 1 0 0 5
11 5 0 0 1

Drawing the horizontal and vertical lines

N=4 n5x5
N≠n, now select the least value in the uncrossed cell and subtract to all the uncrossed cell and
add to the intersection of horizontal and vertical line. The least value is 4

8 0 0 7 0
0 10 8 10 0
0 8 4 2 0
19 1 0 0 5
11 5 0 0 1

N=n, it satisfies our condition and now we can assign the workers to jobs using above table
41
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

8 [0] 0 7 0
[0] 10 8 10 0
0 8 4 2 [0]
19 1 [0] 0 5
11 5 0 [0] 1

1---------B = 38
2---------A = 40
3---------E = 37
4---------C = 41
5---------D = 35
191

Problem 6
A company has four territories open and four salesmen available for assignment. The territories
are not equally rich in their sales potential; it is estimated that a typical salesman operating in
each territory would bring in the following annual sales:
Territory : I II III IV
Annual Sales (Rs) 60,000 50,000 40,000 30,000
Four salesmen are also considered to differ in chair ability: it is estimated that, working under
the same conditions, their yearly sales would be proportionately as follow:
Salesmen: A B C D
Proportion: 7 5 5 4

If the criterion is maximum expected total sales, then including answer is to assign the best
salesman to the richest territory, the next best salesman to the second richest, and so on,
42
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

verifythis answer by the assignment technique.

Solution:
Step 1 to construct the effectiveness of the matrix
By taking Rs. 10000/- as one unit and the sales proportion and the maximum sales matrix is
obtained as follows:

Sales in 10 thousand of rupees

Sales Proportion 6 5 4 3
I II III IV
7 A 42 35 28 21
5 B 30 25 20 15
5 C 30 25 20 15
4 D 24 20 16 12
To find the value of c11= sales proportion X sales of territory
= 7X6=42
In the same it is continued for the remaining cells
Step 2: to convert the maximum sales matrix to minimum sales matrix
By simply multiplying each element of given matrix by -1. Thus resulting matrix becomes:

I II III IV
A -42 -35 -28 -21
B -30 -25 -20 -15
C -30 -25 -20 -15
D -24 -20 -16 -12

Step 3: select the most negative in the matrix i.e. is -42. With this element subtract all the
elements in the matrix. The resulting is minimization table
43
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

I II III IV
A 0 7 14 21
B 12 17 22 27
C 12 17 22 27
D 18 22 26 30

Now, using the above table we can apply the Hungarian method to find the assignment for the
given problem and the value should be taken from the original table since, it is a maximization
problem

Row minimization
0 7 14 21
0 5 10 15
0 5 10 15
0 4 8 12
Column minimization
0 3 6 9
0 1 2 3
0 1 2 3
0 0 0 0
Draw horizontal and vertical lines
0 3 6 9
0 1 2 3
0 1 2 3
0 0 0 0

44
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

N≠n, 2≠4 so select the least value of the uncrossed cell and subtract
The least value is 1

0 2 5 8
0 0 1 2
0 0 1 2
0 0 0 0

N≠n, 3≠4 so select the least value of the uncrossed cell and subtract
The least value is 1

0 2 4 7
0 0 0 1
0 0 0 1
0 0 0 0

N=n, 4=4, the assignment of the given problem

[0] 2 4 7
0 [0] 0 1
0 0 [0] 1
0 0 0 [0]

A--------I
B-------II
C-------III
D------IV

45
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Problem 7:
Alpha Corporation has four plants each of which can manufacture any one of four products
production costs differ from one plant to another as do sales revenue. Given the revenue and
cost data below, obtain which product each plant should produce to maximize profit.

Sales revenue (Rs. 000s Product)

Plant 1 2 3 4
A 50 68 49 62
B 60 70 51 74
C 55 67 53 70
D 58 65 54 69

Production costs (Rs. 000s Product)

Plant 1 2 3 4
A 49 60 45 61
B 55 63 45 69
C 52 62 49 68
D 55 64 48 66

Solution:
Now, we have found the profit matrix by using sales revenue and production cost.
Profit = sales - cost
Profit matrix
1 2 3 4
A 1 8 4 1

46
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

B 5 7 6 5
C 3 5 4 2
D 3 1 6 3

Now we find the minimization matrix, by selecting the highest profit in the profit matrix i.e. 8 is subtract
all the elements in the matrix and resulting will be the minimization matrix of the given
problem.
7 0 4 7
3 1 2 3
5 3 4 6
5 7 2 5

Using Hungarian method

Row minimization
7 0 4 7
2 0 1 2
2 0 1 3
3 5 0 3

Column minimization
5 0 4 5
0 0 1 0
0 0 1 1
1 5 0 1

Draw the horizontal and vertical lines

5 0 4 5

47
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

0 0 1 0
0 0 1 1
1 5 0 1

N=n, the assignment can be done for the above table

5 [0] 4 5
0 0 1 [0]
[0] 0 1 1
1 5 [0] 1

A---------2
B---------4
C--------1
D--------3

Problem 8
An air-line operates seven days a week has time-table shown below. Crews must have a
minimum layover (rest) time of 5 hrs, between flights. Obtain the pair of flights that
minimimizes layover time away from home. For any given pair the crews will e based at the city
that result in the smaller layover.
Delhi - Jaipur Jaipur-Delhi
Flight No. Depart Arrive Flight No. Depart Arrive
1 7.00 AM 8.00 AM 101 8.00 AM 9.15 AM
2 8.00 AM 9.00 AM 102 8.30 AM 9.45 AM
3 1.30 PM 2.30 P.M 103 12.00 NOON 1.15 PM
4 6.30AM 7.30 PM 104 5.30 PM 6.45 PM

48
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

for each pair, mention the town where the crews should be based.

SOLUTION:Step1 construct the table for layour times between flights when crew is based at Delhi, for
simplicity consider 15 minutes = 1unit.

Table 1: layover times when crew based at Delhi

Flights 101 102 103 104

1 96 98 112 38
2 92 94 108 34
3 70 72 86 108
4 50 52 66 88

Since, the crew must have a minimum layover of 5 hrs between flights
The layover time between flights 1 and 101 will be 24 hrs (96 units)from 8.00 AM to 8.00 AM
next day i.e flight 1 arrives jaipur at 8.00 am and leaves the jaipur 8.00 am next day because of
minimum layover is 5 hrs between flights and other flights is there in between so flight will be
there next day only.
Flight 1 to 102 will be (98units) 8.00 am arrives jaipur leaves jaipur 8.30 am next day= 24
hrs+30 minutes
Flight 1 to 103 will be (112 units) 8.00 am arrives jaipur leaves jaipur 12.00 noon next day= 24
hrs +4 hrs =112 units
Flight 1 to 104 will be (38 units)8.00 am arrives jaipur leaves jaipur 5.30 pm on the same day =
9 hrs +30 min = 38 mins

The layover time between Flight 2 to 101 will be (9.00 am arrival and depart from jaipur 8.00
am next day) =23 hrs = 92 units
Flight 2 to 102 will be (9.00 am arrives jaipur and depart from jaipur 8.30 am next day) = 23 hrs
+30 minutes = 94 units

49
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Flight 2 to 103 will be (9.00 am arrives jaipur and depart from jaipur 12.00 noon next day) = 24
hrs +3 hrs = 108 units
Flight 2 to 104 will be (9.00 am arrives jaipur and depart from jaipur 5.30 pm same day) = 8 hrs
+30 minutes= 34 units

The layover time between Flight 3 to 101 will be (2.30 pm arrival and depart from jaipur 8.00
am next day) =17 hrs + 30 minutes = 70 units
Flight 3 to 102 will be (2.30 pm arrives jaipur and depart from jaipur 8.30 am next day) = 18hrs
= 72 units
Flight 3 to 103 will be (2.30 pm arrives jaipur and depart from jaipur 12.00 noon next day) =
21hrs + 30 minutes = 86 units
Flight 3 to 104 will be (2.30 pm arrives jaipur and depart from jaipur 5.30 pm next day) =
24hrs+3hrs= 108 units

The layover time between Flight 4 to 101 will be (7.30 pm arrival and depart from jaipur 8.00
am next day) =12 hrs +30 minutes = 50 units
Flight 4 to 102 will be (7.30 pm arrives jaipur and depart from jaipur 8.30 am next day) = 13hrs
= 52 units
Flight 4 to 103 will be (7.30 pm arrives jaipur and depart from jaipur 12.00 noon next day) =
16hrs + 30 minutes = 66 units
Flight 4 to 104 will be (7.30 pm arrives jaipur and depart from jaipur 5.30 pm next day) =
22hrs= 88 units

50
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Table 2: layover times when crew based at jaipur

Flights 101 102 103 104

1 87 85 71 49
2 91 89 75 53
3 113 111 97 75
4 37 35 21 95

Arrival and depart when crew is based in jaipur

Flight No. Arrive(delhi) Flight No. Depart (Delhi)

101 9.15 AM 1 7.00 AM
102 9.45 AM 2 8.00 AM
103 1.15 PM 3 1.30 PM
104 6.45 PM 4 6.30AM

Since, the crew must have a minimum layover of 5 hrs between flights
The layover time between flights 101 and 1 will be 21 hrs+ 45 minutes (87 units) from 9.15 AM
to 7.00 AM next day by flight no 1 i.e flight 101 arrives Delhi at 9.15 am and leaves the Delhi
7.00 am next day by flight no 1 because of minimum layover is 5 hrs between flights and no
other flights is there in between so flight will there next day only.
Flight 101 to 2 will be (91 units) 9.15 am arrives Delhi leaves Delhi 8.00 am next day= 22 hrs+45
minutes
Flight 101 to 3 will be (113 units) 9.15 am arrives Delhi leaves Delhi 1.30 pm next day= 28 hrs
+15 minutes = 113 units
Flight 101 to 4 will be (38 units) 9.15 am arrives Delhi leaves Delhi 6.30 pm on the same day = 9
hrs +15 min = 37 mins

51
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

The layover time between Flight 102 to 1 will be (9.45 am arrival and depart from Delhi 7.00 am
next day) =21 hrs+15 minutes = 85 units
Flight 102 to 2 will be (9.45 am arrives Delhi and depart from Delhi 8.00 am next day) = 22hrs +
15 minutes = 89 units
Flight 102 to 3 will be (9.45 am arrives Delhi and depart from Delhi 1.30 pm next day) = 27 hrs
+45 minutes = 111 units
Flight 102 to 4 will be (9.45 am arrives Delhi and depart from Delhi 6.30 pm same day) = 8 hrs
+45 minutes= 35 units
The layover time between Flight 103 to 1 will be (1.15 pm arrival and depart from Delhi 7.00 am
next day) =17hrs + 45 minutes = 71 units
Flight 103 to 2 will be (1.15 pm arrives Delhi and depart from Delhi 8.00 am next day) = 18hrs +
45 minutes = 75 units
Flight 103 to 3 will be (1.15 pm arrives Delhi and depart from Delhi 1.30 pm next day) = 24 hrs
+15 minutes = 97 units
Flight 103 to 4 will be (1.15 pm arrives Delhi and depart from Delhi 6.30 pm same day) = 5 hrs +
15 minutes= 21 units

The layover time between Flight 104 to 1 will be (6.45 pm arrival and depart from Delhi 7.00 am
next day) =12hrs + 15 minutes = 49 units
Flight 104 to 2 will be (6.45 pm arrives Delhi and depart from Delhi 8.00 am next day) = 13hrs +
15 minutes = 53 units
Flight 104 to 3 will be (6.45 pm arrives Delhi and depart from Delhi 1.30 pm next day) =18 hrs
+45 minutes = 75 units
Flight 104 to 4 will be (6.45 pm arrives Delhi and depart from Delhi 6.30 pm same day) = 23 hrs
+ 45 minutes= 95 units

Step 3:construct the table for minimum layover times between flights with the help of Table 1
and Table 2 layover times marked * denote that the crew is based at jaipur.
Table 3:
52
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Flights 101 102 103 104

1 87* 85* 71* 38
2 91* 89* 75 34
3 70 72 86 75
4 37* 35* 21* 88

Using Hungarian method we solve the above table and the assignment are as shown in the
table

0 0 [0] 0
12 8 8 [0]
[0] 0 28 50
4 [0] 0 100

The optimal assignments are

Flight 1-103
Flight 2-104
Flight 3-101
Flight 4-102

53
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Unbalanced Assignment Problem

If the cost matrix of an assignment problem is not a square matrix (number of sources is not
equal to the number of destinations),
The assignment problem is called an unbalanced assignment problem.
In such cases, fictitious rows and columns are added in the matrix so as to form a square matrix.
Then the usual assignment algorithm can be applied to this resulting balanced problem.

Problem 1:
A company is faced with the problem of assigning six different machines to five different jobs.
The costs are estimated as follows (in hundreds of rupees):
Jobs
1 2 3 4 5
1 2.5 5.0 1.0 6 1.0
2 2.0 5.0 1.5 7 3.0
Machines 3 3.0 6.5 2.0 9 4.5
4 3.5 7.0 2.0 9 4.5
5 4.0 7.0 3.0 9 6.0
6 6.0 9.0 5.0 10 6.0
Solve the problem assuming that the objective is to minimize the total cost.

Solution:
The matrix is 6x5, and then given problem is unbalanced assignment problem. So we introduce
fictitious job i.e Job 6 in the cost matrix in order to get the balanced assignment problem. The
costs corresponding to such column are always taken as zero.

54
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Jobs
1 2 3 4 5 6
1 2.5 5.0 1.0 6 1.0 0
2 2.0 5.0 1.5 7 3.0 0
Machines 3 3.0 6.5 2.0 9 4.5 0
4 3.5 7.0 2.0 9 4.5 0
5 4.0 7.0 3.0 9 6.0 0
6 6.0 9.0 5.0 10 6.0 0

Then, the problem can be solved by usual manner by Hungarian method.

Row Minimization
2.5 5.0 1.0 6 1.0 0
2.0 5.0 1.5 7 3.0 0
3.0 6.5 2.0 9 4.5 0
3.5 7.0 2.0 9 4.5 0
4.0 7.0 3.0 9 6.0 0
6.0 9.0 5.0 10 6.0 0
Row minimization remains as same as original problem

Column minimization
0.5 0 0 0 0 0
0 0 0.5 1 2.0 0
1.0 1.5 1.0 3 3.5 0
1.5 2.0 1.0 3 3.5 0
2.0 2.0 2.0 3 5.0 0

55
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

4.0 4.0 4.0 4 5.0 0

N=3, n=5x5, N≠n, so the least value in the uncrossed value is 1.0 and with this value all the
uncrossed cell is subtracted and the resulting matrix

0.5 0 0 0 0 1
0 0 0.5 1 2.0 1
0 0.5 0 2 3.5 1
0.5 1.0 0 2 3.5 1
1.0 1.0 1.0 2 5.0 0
3.0 3.0 3.0 3 5.0 0

N=5, n=6x6, N≠n

The least value in the uncrossed cell is 1 and using this value it is subtracted to the entire
uncrossed cell and for the intersection of horizontal and vertical lines it is added and the
resulting matrix is given below.

0.5 0 0 0 0 2
0 0 0.5 1 2.0 2
0 0.5 0 2 3.5 2
0.5 1.0 0 2 3.5 2
0 0 0 1 5.0 0
2.0 2.0 2.0 2 5.0 0

56
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

N=5, n=6, N≠n, the least value is 1 and using this it is subtracted to the uncrossed cell of the
above matrix and the resulting is shown below.

0.5 0 0 0 0 2
0 0 0.5 0 1.0 2
0 0.5 0 1 2.5 2
0.5 1.0 0 1 2.5 2
0 0 0 0 4.0 0
2.0 2.0 2.0 1 4.0 0

The table satisfies N=n and the optimal assignment table is obtained and using the matrix the
assignment can be done.

0.5 0 0 0 [0] 2
0 [0] 0.5 0 1.0 2
[0] 0.5 0 1 2.5 2
0.5 1.0 [0] 1 2.5 2
0 0 0 [0] 4.0 0
2.0 2.0 2.0 1 4.0 [0]

Machine 1 ---------------Job5 = 1
Machine 2 ---------------Job2 = 5
Machine 3 ---------------Job1 = 3
Machine 4 ---------------Job3 = 2
Machine 5 ---------------Job4 = 9
Machine 6 ---------------Job6 = 6
26

57
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Problem 2.
Manager of Transportation Company must order 5 trucks out of a fleet to be present at 5
specific locations for loading goods that are awaiting shipment eight trucks are at different
location. The costs are given in the table below. Assign 5 trucks so as to minimize the cost.
Loading Locations
A B C D E
1 300 290 280 290 210
2 250 310 290 300 200
3 180 190 300 190 180
Trucks 4 320 180 190 240 170
5 270 210 190 250 160
6 190 200 220 190 140
7 220 300 230 180 160
8 200 190 260 210 180

Solution;
The given problem is 8x5, so it is a unbalanced assignment problem, here we must had 3
fictitious loading locations as shown below.
Loading Locations
A B C D E F G H
1 300 290 280 290 210 0 0 0
2 250 310 290 300 200 0 0 0
3 180 190 300 190 180 0 0 0
Trucks 4 320 180 190 240 170 0 0 0
5 270 210 190 250 160 0 0 0
6 190 200 220 190 140 0 0 0
58
7 220 300 230 180 160 0 0 0
8 200 190 260 210 180 0 0 0
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Once the matrix is balanced and then usual procedure is used to solve the problem for
assignment.

Row minimization
300 290 280 290 210 0 0 0
250 310 290 300 200 0 0 0
180 190 300 190 180 0 0 0
320 180 190 240 170 0 0 0
270 210 190 250 160 0 0 0
190 200 220 190 140 0 0 0
220 300 230 180 160 0 0 0
200 190 260 210 180 0 0 0

Since, each row has zero (0) the row minimization remains same as the original problem.

Column minimization
120 110 90 110 70 0 0 0
70 130 100 120 60 0 0 0
0 10 110 10 40 0 0 0
140 0 0 60 30 0 0 0
90 30 0 70 20 0 0 0
10 20 30 10 0 0 0 0
40 120 40 0 20 0 0 0
20 10 70 30 40 0 0 0

59
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

120 110 90 110 70 0 [0] 0

70 130 100 120 60 [0] 0 0
[0] 10 110 10 40 0 0 0
140 [0] 0 60 30 0 0 0
90 30 [0] 70 20 0 0 0
10 20 30 10 [0] 0 0 0
40 120 40 [0] 20 0 0 0
20 10 70 30 40 0 0 [0]

T1----------------------------- G = 0
T2----------------------------- F = 0
T3----------------------------- A = 180
T4----------------------------- B = 180
T5----------------------------- C = 190
T6----------------------------- E = 140
T7----------------------------- D = 180
T8----------------------------- H = 0
870

60
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

The Travelling salesman (routing) problem

The travelling salesman problem is one of the problems considered as puzzles by the
mathematicians.
Suppose a salesman wants to visit a certain number of cities allotted to him.
He knows the distances (or cost or time) of journey between every pair of cities, usually
denoted by cij i.e. city I to city j.
His problem is to select such a route that stars from his home city. Passes through each city
once and only once and returns to his home icty in the shortest possible distance (or at the
least cost or in least time).

FORMULATION OF A TRAVELLING – SALESMAN PROBLEM AS ASSIGNMENT PROBLEM

Suppose cij is the distance 9or cost or time) from city I to city j and xij =1, if the salesman goes
directly from city I to city j, and zero otherwise. Then minimize ∑i ∑j xij cij with the additional
restriction that the xij must be so chosen that no city is visited twice before the tour of all cities
is completed. In particular, he cannot go directly from city I to I itself. This possibility may be
avoided in the minimization process by adopting the convention cij =∞ which ensures that xij
can never be unity.
Alternatively, omit the variable xij from the problem specification. It is also important to note
that onl single xij =1 for each value of I and j. the distance (or cost or time) matrix for this
problem is given in table 1.
To

∞ C12 --- C1n

C21 ∞ --- C2n

From --- -- ∞ --
Cn1 Cn2 --- ∞

61
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Problem 1:
Given the matrix of set-up costs, show how to sequence the production so as to minimize the
set-up cost per cycle.
To
A1 A2 A3 A4 A5
A1 ∞ 2 5 7 1
From A2 6 ∞ 3 8 2
A3 8 7 ∞ 4 7
A4 12 4 6 ∞ 5
A5 1 3 2 8 ∞

Solution:
Row minimization

A1 A2 A3 A4 A5
A1 ∞ 1 4 6 0
A2 4 ∞ 1 6 0
A3 4 3 ∞ 0 3
A4 8 0 2 ∞ 1
A5 0 2 1 7 ∞

olumn minimization
A1 A2 A3 A4 A5
A1 ∞ 1 3 6 0
A2 4 ∞ 0 6 0
A3 4 3 ∞ 0 3
A4 8 0 1 ∞ 1
A5 0 2 0 7 ∞

62
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

N=n, 5=5x5

∞ 1 3 6 [0]
4 ∞ [0] 6 0
4 3 ∞ [0] 3
8 [0] 1 ∞ 1
[0] 2 0 7 ∞

A1-------A5-----A1, A2-------A3------A4------A2
Cost = 1+3+4+4+1=13
As per the sequence from the above assignment indicates to produce the products A1, then A5
and then again A1, without producing the products A2,A3 and A4 thereby violates the
additional restriction of producing each product once and only once before returning to the
first product.
Step 2: next to examine the matrix for the best solutions to the assignment problem and first
we try with value one (1) the cells having 1 are c12, c43, c45, using this cells we try for one
sequence
Let us try with assigning with c15 to c12 and c42 to c45

∞ [1] 3 6 0
4 ∞ [0] 6 0
4 3 ∞ [0] 3
8 0 1 ∞ [1]
[0] 2 0 7 ∞

The sequence will be A1---A2---A3----A4---A5----A1

The cost will be 2+3+4+5+1 =15

Here the cost is increased by Rs.2. if you see in the matrix to get one sequence we have
changed the assignment from c15 to c12 contains 1 and c42 to c45 contains due this penalty
cost. The cost is increased by Rs 2.

63
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Problem 2
A machine operator processes 5 types of items on his machine each week, and must choose a
sequence for them. The set-up coast per change depends on the item presently on the machine
and the set-up to be made according to the following table:
To Item
A B C D E
A ∞ 4 7 3 4
B 4 ∞ 6 3 4
C 7 6 ∞ 7 5
D 3 3 7 ∞ 7
E 4 4 5 7 ∞
if the processes each type of item once and only once each week how should he sequence the
items on his machine in order to minimize the total set-up cost?
Solution: Using usual assignment problem
Row Minimization
∞ 1 4 1 1
1 ∞ 3 0 1
2 1 ∞ 2 0
0 0 4 ∞ 4
0 0 1 3 ∞
Column minimization
∞ 1 3 1 1
1 ∞ 2 0 1
2 1 ∞ 2 0
0 0 3 ∞ 4
0 0 0 3 ∞

64
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

Draw horizontal and vertical lines

∞ 1 3 1 1
1 ∞ 2 0 1
2 1 ∞ 2 0
0 0 3 ∞ 4
0 0 0 3 ∞

N≠n, 4≠5, least value is 1

∞ 0 2 1 1
0 ∞ 1 0 1
1 0 ∞ 2 0
0 0 3 ∞ 5
0 0 0 4 ∞

N=n
∞ [0] 2 1 1
0 ∞ 1 [0] 1
1 0 ∞ 2 [0]
[0] 0 3 ∞ 5
0 0 [0] 4 ∞
A---B----D----A, C----E---C, THE COST =4+3+5+3+5=20
In the given problem we have 2 sequence and doesn’t satisfies the travelling salesmen
procedure

So we try with shifting of cells from c12 to c15 and c35 to c32

65
 DAYANANDA SAGAR COLLEGE OF ENGINEERING
(An Autonomous Institute Affiliated to VTU, Belagavi)
Shavige Malleshwara Hills, Kumaraswamy Layout, Bengaluru-560078
DEPARTMENT OF MATHEMATICS

∞ 0 2 1 [1]
0 ∞ 1 [0] 1
1 [0] ∞ 2 0
[0] 0 3 ∞ 5
0 0 [0] 4 ∞

A---E---B---D—A, C---B, This also not satisfied the travelling salesmen

COST =4+3+6+3+5=21

Now we try with shifting c32 to c31 and c41 to c42

∞ 0 2 1 [1]
0 ∞ 1 [0] 1
[1] 0 ∞ 2 0
0 [0] 3 ∞ 5
0 0 [0] 4 ∞
A---E---C----A, B---D---B this is also not suitable to travelling salesmen
COST= 4+3+7+3+5=22
NOW WE TRY WITH SHIFITNG OF C15 TO C14 AND C24 TO C25
∞ 0 2 [1] 1
0 ∞ 1 0 [1]
[1] 0 ∞ 2 0
0 [0] 3 ∞ 5
0 0 [0] 4 ∞

A---D—B---E---C—A COST=4+4+7+3+5=23

66