Transportation Problem
Dr\ Eman Monir
Faculty of Computers and Artificial Intelligence
Benha University
Spring 2020
Outline
• Problem Formulation
• Transportation Algorithms
1. Northwest-corner method
2. Least-cost method
3. Vogel approximation method
• Unbalanced transportation model
• Nontraditional Transportation Models
• Iterative Computations of the Transportation Algorithm
• Assignment Problem
12/11/2025 Operations Research 2
Hungarian Method
12/11/2025 Operations Research 3
Assignment Problem
• Joe Klyne’s three children, John, Karen, and Terri, want to earn some
money for personal expenses. Mr. Klyne has chosen three chores for
his children: mowing the lawn, painting the garage door, and washing
the family cars. To avoid anticipated sibling competition, he asks them
to submit individual (secret) bids for what they feel is fair pay for each
of the three chores. Table 5.19 summarizes the bids received. The
children will abide by their father’s decision regarding the assignment
of chores. The assignment problem will be solved by the Hungarian
method.
12/11/2025 Operations Research 4
Assignment Problem
12/11/2025 Operations Research 5
12/11/2025 Operations Research 6
Example #2
0 3 5 2
1
2 0 3 2
7
0 1 7 3
4
3 2 3 0
5
0 0 3 0
12/11/2025 Operations Research 7
Assignment Problem
0 3 2 2 0 2 1 1
2 0 0 2 3 0 0 2
0 1 4 3 0 0 3 2
3 2 0 0 4 2 0 0
12/11/2025 Operations Research 8
Optimal Assignment
Cost= 1+10+5+5=21
12/11/2025 Operations Research 9
Assignment Problem
12/11/2025 Operations Research 10
Using assignment problems in maximization
1 2 3 4 5 1 2 3 4 5
A 40 32 70 29 67 A 49 57 19 60 22 19
B 45 37 72 39 69 B 44 52 17 50 20 17
C 46 38 35 38 78 C 43 51 54 51 11 11
D 51 48 47 61 29 D 38 41 42 28 60
28
E 59 69 89 63 43 E 30 20 0 26 46
0
12/11/2025 Operations Research 11
1 2 3 4 5 1 2 3 4 5
30 38 0 41 3 A 20 25 0 41 3
A
27 35 0 33 3 B 17 22 0 33 3
B
32 40 43 40 0 C 22 27 43 40 0
C
10 13 14 0 32 D 0 0 14 0 32
D
30 20 0 26 46 E 20 7 0 26 46
E
10 13 0 0 0
12/11/2025 Operations Research 12
1 2 3 4 5 1 2 3 4 5
A 20 25 0 41 3 13 18 0 34 3
A
B 17 22 0 33 3 10 15 0 26 3
B
C 22 27 43 40 0 15 20 43 33 0
C
D 0 0 14 0 32 0 0 21 0 39
D
E 20 7 0 26 46 13 0 0 19 46
E
12/11/2025 Operations Research 13
1 2 3 4 5 1 2 3 4 5
A 13 18 0 34 3 A 3 18 0 14 3
B 10 15 0 26 3 B 0 15 0 16 3
C 15 20 43 33 0 C 5 20 43 23 0
D 0 0 21 0 39 D 0 10 31 0 49
E 13 0 0 19 46 E 3 0 0 9 46
profit= 70+45+78+61+69 =323
12/11/2025 Operations Research 14
12/11/2025 Operations Research 15