17-04-2021

Example 1
Suppose TSM students have an option to earn by doing some jobs
in the campus and the assignments are mowing the lawn,
painting the wall, watering the plants and collecting the plastics
in the campus. For these jobs they can bid as per as what they
feel about a fair pay to avoid anticipated competitions. The Dean
asks 4 randomly chosen students to submit their individual
Special Case of Transportation problem secret bid and the details are given below. How the Dean should
assign the works?
Assignment Problem Work →
Student ↓
Mow Paint Water Plastic
collection
Student 1 5 9 3 6
Student 2 8 7 8 2
Student 3 6 10 12 7
Student 4 3 10 8 6

Note: all the costs are in INR per every 30 minutes

DMOT | Network and Distribution Models- Hungarian Algorithm

1 2

Network Representation
Assignment Problem
Transportation Problem
• An assignment problem seeks to minimize the total Assignment Problem
cost assignment of m workers to m jobs, given that the c11
cost of worker i performing job j is cij. 1 1 1 d1
c12
c
• It assumes all workers are assigned and each job is Agents
c13
Tasks s1 1 1 c12
performed. c21 c1 13
c22 2 d2
• An assignment problem is a special case of a 2 2 c21
c23
transportation problem in which all supplies and all s2 2 c22
demands are equal to 1; hence assignment problems c31 c23
may be solved as linear programs. c32 3 d3
3 3
c33
• The network representation of an assignment problem Sources Destinations
with three workers and three jobs is shown on the next
slide.

DMOT | Network and Distribution Models- Hungarian Algorithm DMOT | Network and Distribution Models- Hungarian Algorithm

3 4

Assignment Problem
Assignment Problem
 Linear Programming Formulation • Linear Programming Formulation (continued)
m n
Using the notation: Min  c x
i 1 j 1
ij ij

xij = 1 if agent i is assigned to task j n

0 otherwise  xij  1
j1
i 1, 2, , m Agents
m
cij = cost of assigning agent i to task j
x
i 1
ij 1 j 1, 2, , n Tasks
continued
xij > 0 for all i and j

DMOT | Network and Distribution Models- Hungarian Algorithm

5 6

1
 17-04-2021

Assignment Problem: Example Assignment Problem: Example

An electrical contractor pays his subcontractors a fixed  Network Representation

fee plus mileage for work performed. On a given day the 50
contractor is faced with three electrical jobs associated with West. A
36
various projects. Given below are the distances between the
subcontractors and the projects. Subcontractors 16
Projects
28
Projects 30
Fed. B
Subcontractor A B C
18
Westside 50 36 16
35 32
Federated 28 30 18
Goliath 35 32 20 Gol. C
20
Universal 25 25 14
25
25

How should the contractors be assigned to minimize total Univ. 14

mileage costs?

7 8

Assignment Problem: Example Assignment Problem: Example

 Linear Programming Formulation • The optimal assignment is:

Min 50x11+36x12+16x13+28x21+30x22+18x23 Subcontractor Project Distance
+35x31+32x32+20x33+25x41+25x42+14x43 Westside C 16
s.t. x11+x12+x13 < 1 Federated A 28
x21+x22+x23 < 1 Goliath (unassigned)
Agents Universal B 25
x31+x32+x33 < 1
x41+x42+x43 < 1 Total Distance = 69 miles
x11+x21+x31+x41 = 1
x12+x22+x32+x42 = 1 Tasks
x13+x23+x33+x43 = 1
xij = 0 or 1 for all i and j

DMOT | Network and Distribution Models- Hungarian Algorithm

9 10

Example 2 Example 3
Man → 1 2 3 4 Job → I II III IV
Job ↓ Man ↓
I 12 30 21 15 A 2 3 4 5
II 18 33 9 31 B 4 5 6 7
III 44 25 24 21 C 7 8 9 8
IV 23 30 28 14 D 3 5 8 4

Find Optimal Assignment. Find Optimal Assignment.

DMOT | Network and Distribution Models- Hungarian Algorithm DMOT | Network and Distribution Models- Hungarian Algorithm

11 12

2
 17-04-2021

Example 4 Example 5
Jobs ↓ P1 P2 P3 P4 P5 P6
Man → I II III IV V
Persons
Job ↓
→
A 9 22 58 11 19 27
A 11 7 10 17 10
B 43 78 72 50 63 48 B 13 21 7 11 13
C 41 28 91 37 45 33 C 13 13 15 13 14
D 74 42 27 49 39 32 D 18 10 13 16 14
E 36 11 57 22 25 18 E 12 8 16 19 10

F 3 56 53 31 17 28

DMOT | Network and Distribution Models- Hungarian Algorithm DMOT | Network and Distribution Models- Hungarian Algorithm

13 14

Hungarian Algorithm Hungarian Algorithm (Contd…)

When there is no optimal assignment in first cost reduction matrix –then
• Step 1: Subtract the smallest entry in each row from all the follow Step 4
entries of its row.
STEP 4
• Step 2: Subtract the smallest entry in each column from all the I. Tick an UNASSIGNED ROW.
entries of its column.
II. If a ticked row has a ZERO, then tick the corresponding column.
• Step 3a: Starting with row 1 of the reduced cost matrix (from III. If a ticked column has an assignment, tick the corresponding row.
Step 2), examine rows successively until a row with exactly 1 IV. Repeat step (ii) and (iii) till no more ticking is possible.
zero element is found and mark (box) it as an assignment.
Mark (X) at all other zeros in the corresponding columns. V. Draw lines through UNTICKED rows and through TICKED columns to
Proceed this until the last row is being examined. cover all zeros.
STEP 5: Select the smallest of the elements that do not have a line through
• Step 3b:Continue steps 1 and 2 until the following situation
reached, them, SUBTRACT it from all the element that do not have a line through
them, ADD it to every element that lies at the intersection of two lines and
– I. All zeros are marked or crossed
LEAVE the remaining elements of the matrix unchanged.
– II. The remaining unmarked zeros lies at least two in each
row.
STEP 6: At the end of the STEP 5 , number of zeros are increased (never
decreases) in the matrix than that of STEP 3. Now repeat the STEP 3 to the
modified matrix obtained in STEP 5, to get improved allocation matrix .
DMOT | Network and Distribution Models- Hungarian Algorithm DMOT | Network and Distribution Models- Hungarian Algorithm

15 16

Ex-6: An air line that operates seven days in a week has

timetable shown below. Crews must have a minimum layover
Example 7
time 5 hours between the flights. Obtain the pair of flights
that minimizes layover time away from home. Also for each Job → I II III IV
pair mention the town where the crew should be based. Man ↓
A 5 9 3 6
Delhi- Jaipur Jaipur- Delhi B 8 7 8 2
Flight No Depart Arrive Flight No Depart Arrive
C 6 10 12 7
D 3 10 8 6
101 6.00 AM 8.00 AM 201 8.00 AM 10.00 AM

102 8.00 AM 10.00 AM 202 9.00 AM 11.00 AM

Find Optimal Assignment.
103 2.00PM 4.00 PM 203 2.00 PM 4.00 PM

104 8.00 PM 10.00 PM 204 7.00 PM 9.00 PM

DMOT | Network and Distribution Models- Hungarian Algorithm

17 18