Specially Structured Linear

Programs
Transporta6on and Assignment Problem
Chapter-11
Prepared By:
Tasneema Khan
Assistant Professor
Department of Banking and Insurance
University of Dhaka
 Introduc6on
• Assignment problem involves assigning
employees to tasks, salesperson to territories,
contracts to bidders, or jobs to plants.
Characteris6cs
• The number of rows must be equal to number
of columns
• In the opHmal soluHon, there will be only one
assignment in a given row or column
 Assignment Method-Minimiza6on (Balanced)
Job Machine
X Y Z
A $25 $31 $35
B 15 20 24
C 22 19 17

• Also known as Flood’s Technique or Hungarian method.

Three steps
1. Determine the opportunity-cost table
2. Determine whether an opHmal assignment can be
made
3. Revise the total opportunity cost table
 SoluHon
Ini6al Solu6on
J M X Y Z Total
Requi.
A 1 1

B 0 1 1

C 0 1 1

Total 1 1 1 3 3
Capacity
No. of Stone Square ≠ (Rim Requirement – 1)
3≠5
Since, this creates degeneracy problem at each stage, the
flood’s technique is followed as below:
 Job Machine
Job Opportunity Cost Table X Y Z
X Y Z A $25 $31 $35
A $10 $12 $18 B 15 20 24
C 22 19 17
B 0 1 7
C 7 0 0
Total Opportunity Cost Table
X Y Z
A 0 2 8
B 0 1 7
C 7 0 0

No of lines ≠ No. of row or column

This means that we do not have zero opportunity cost opHon for
each of job individually, hence, this is not the opHmal soluHon.
 X Y Z
A $0 2 8
B 0 1 7
C 7 0 0

Improved Solu6on

X Y Z
A $0 1 7
B 0 0 6
C 8 0 0

No of lines = No. of row or column

3=3
This means, we have zero opportunity cost opHon for each of job individually, therefore, this is the opHmal
soluHon. Now, opHmal assignment is possible.
A to X
B to Y
C to Z
Total cost is ($25+$20+$17)= $62
 SoluHon
Ini6al Solu6on

V W X Y Z

A 1 0 1

B 1 0 1

C 1 0 1

D 1 0 1

E 1 1

1 1 1 1 1 5

No. of Stone Square ≠ (Rim Requirement – 1)

5 ≠9
Since, this creates degeneracy problem at each stage, the flood’s
technique is followed as below:
Company Opportunity Cost Table
V W X Y Z Co. Bid
A 15 40 35 45 5 V W X Y Z

B 20 35 0 45 20 A 45 60 75 100 30
B 50 55 40 100 45
C 30 50 40 55 15
C 60 70 80 110 40
D 0 0 20 0 0
D 30 20 60 55 25
E 30 5 25 130 10 E 60 25 65 185 35

Total Opportunity Cost Table

V W X Y Z
A 10 35 30 40 0
B 20 35 0 45 20
C 15 35 25 40 0
D 0 0 20 0 0
E 25 0 20 125 5
No of lines ≠ No. of row or column
4≠5

This means we do not have zero opportunity cost opHon for each of job individually, hence, this is not the opHmal soluHon
 V W X Y Z
Improved Solu6on
A 10 35 30 40 0
V W X Y Z
A B 20 35 0 45 20
B C 15 35 25 40 0
C
D 0 0 20 0 0
D
E E 25 0 20 125 5
 V W X Y Z
Improved Solu6on
A 10 35 30 40 0

B 20 35 0 45 20

C 15 35 25 40 0

D 0 0 20 0 0

E 25 0 20 125 5

V W X Y Z

A 0 25 30 30 0

B 10 25 0 35 20

C 5 25 25 30 0

D 0 0 30 0 10

E 25 0 30 125 15
Improved Solu6on

V W X Y Z
A 0 25 30 30 0
B 10 25 0 35 20
C 5 25 25 30 0
D 0 0 30 0 10
E 25 0 30 125 15
No of lines = No. of row of column
5=5

This means, we have zero opportunity cost opHon for each of job individually, therefore,
this is the opHmal soluHon. Now, opHmal assignment is possible.
A to V
B to X
C to Z
D to Y
E to W
Total cost is ($45,000+$40,000+$40,000+$55,000+$25,000)= $205,000
Assignment Problem- Maximiza6on
(Balanced)
 Assignment Problem- Maximiza6on
(Balanced)
Minimiza6on Maximiza6on
Lowest value opHon is the Highest value opHon is the Cost/ Hme - minimizaHon
best opHon best opHon
Profit/income/u6lity/
earning - maximizaHon
Convert the (cost) table Convert the (profit/bid/
into uHlity) table into
Opportunity cost table Regret value table

Each value – lowest value Highest value – each value Onwards same concept
= Opportunity Cost = Regret value
Because you will try to find
zero opportunity cost/
zero regret value op6on
for each column or row.
Individual Regret Value Table
Chevrolet Ford Plymouth AMC

A 150 100 0 150

B 50 0 150 100

C 100 50 200 0

D 0 0 150 50

Total Regret Value Table

Chevrolet Ford Plymouth AMC

A 150 100 0 150

B 50 0 150 100

C 100 50 200 0

D 0 0 150 50
• A to P
• B to F
• C to AMC
• D to C
• Total sales revenue ($1100+$1000+$1050+
$1150) = $ 4300
 Assignment Problem - Unbalanced
W X Y Z
A $18 $24 $28 $32
B 8 13 17 19
C 10 15 19 22

• No. of row does not equal to No. of row, so

one dummy row needs to be added.
W X Y Z
A $18 $24 $28 $32
B 8 13 17 19
C 10 15 19 22
Dummy D 0 0 0 0
 W X Y Z
Job opportunity cost table A $18 $24 $28 $32
W X Y Z B 8 13 17 19

A $18 $24 $28 $32 C 10 15 19 22

Dum 0 0 0 0
B 8 13 17 19
my
C 10 15 19 22 D

Dummy D 0 0 0 0

Total opportunity cost table

W X Y Z
A 0 6 10 14
B 0 5 9 11
C 0 5 9 12
Dummy D 0 0 0 0
Improved solu6on W X Y Z

W X Y Z A 0 6 10 14

A 0 1 5 9 B 0 5 9 11

B 0 0 4 6 C 0 5 9 12
C 0 0 4 7
Du 0 0 0 0
Dummy D 5 0 0 0 m
my
D
 W X Y Z
A 0 1 5 9
B 0 0 4 6
C 0 0 4 7
Dummy D 5 0 0 0
 W X Y Z
A 0 1 5 9
B 0 0 4 6
C 0 0 4 7
Dummy D 5 0 0 0

W X Y Z
A 0 1 1 5
B 0 0 0 2
C 0 0 0 3
Dummy D 9 4 0 0