Week 7- Operations Research- Dr. Mohamed Sameh .pdf

operation research

1. OPERATIONS
RESEARCH
Dr. Mohamed Sameh

2. LESSON 7:
TRANSPORTATION
MODEL (CONTD.)

3. Transportation Model
Using Excel Solver
Objective
function
Decision Variables
(B2:D4)
Cost
Supply sum
=sum(B3:D3)
Demand sum
=sum(B2:B4)

4. Transportation Model
Using Excel Solver
Objective
function
Decision Variables
(B2:D4)
Algorithm
Constraints

5. Transportation Model
Using Excel Solver
Minimum
cost
Decision
variables

6. LESSON 7:
ASSIGNMENT MODEL

7. Assignment Model
oA special case of a transportation problem in which all sources and all demands are
equal to 1.
oCharacterized by a set of sources, a set of tasks(demands), and a score (cost) for each
assignment of a source to a demand.
oAssigns personnel to tasks, jobs to machines, inventory to locations, or salespersons to
territories.
oCan be mathematically summarized as follows:
-Xij= 0, if source iis not assigned to task j
-Xij= 1, if source I is assigned to task j
oAssumes total supply = total demand (a square matrix).
oEach assignee should perform one task, and each task is performed by one assignee.
oSeeks to minimize the total cost.
oUsing traditional transportation models would get too many degenerate values.
oThe Hungarian method is used instead.

8. ◦Linear Programming Formulation
Objective function: Min
��c
ijx
ij
Constraints: 
��x
ij<1 for each source i

&#3627408470;&#3627408471;x
ij<1 for each demand j
x
ij= 0 or 1 for all iand j.
◦Note: A modification to the right-hand side of the first constraint set can be made if a
worker is permitted to work more than 1 job.
Assignment Model

9. Hungarian Method
1.Row reduction : for each row, subtract the minimum number from all other row numbers.
2.Column reduction: for each column that does not have a zero, subtract the minimum
number from all other column numbers.
3.Draw the minimum number of horizontal and vertical lines that can cover all the matrix
zeroes.
4.If the drawn lines number >the number of rows or columns (m), an assignment is made
(go to step 10).
5.If the number is less than m, find the minimum uncovered value (x).
6.Subtract xfrom all other uncovered numbers.
7.Add xto the numbers covered by two lines.
8.Numbers covered by one line remain the same.
9.Return to step 3.
Assignment Model

10. Hungarian Method
10.Make the assignments one at a time in positions that have zero elements.
11.Begin with rows or columns that have only one zero (circle the zero).
12.Cross out both the row and the column.
13.Move on to the rows and columns that are not yet crossed out to select the next
assignment, with preference again given to any such row or column that has only one
zero that is not crossed out and circle them (break ties arbitrarily).
14.Continue until every row and every column has exactly one assignment and so has been
crossed out.
15.The complete set of assignments made in this way is an optimal solution for the problem.
Assignment Model

11. Assignment example
Al-Arabygroupmanufacturesfivedifferentelectricaldevices(1,2,3,4,5).Afteraproductis
assembled,itistransportedfromtheassemblylinetooneoffivedifferentinspectionstations
(A,B,C,D,E)forqualityassurance.Thetime(minutes)requiredtotransporteachproductto
eachinspectionstationasshowninthefollowingtable.Assigneachproducttoacertain
inspectionstationsoastominimizethetotaltransportationtime.
Assignment Model
Inspection station
A B C D E
Product
1 10 4 6 10 12
2 11 7 7 9 14
3 13 8 12 14 15
4 14 16 13 17 17
5 19 11 17 20 19

12. Assignment example (row reduction)
Assignment Model
Inspection station
A B C D E
Product
1
10 4 6 10 12
2
11 7 7 9 14
3
13 8 12 14 15
4
14 16 13 17 17
5
19 11 17 20 19

13. Assignment example (column reduction)
Assignment Model
Inspection station
A B C D E
Product
1
6 0 2 6 8
2
4 0 0 2 7
3
5 0 4 6 7
4
1 3 0 4 4
5
8 0 6 9 8

14. Assignment example
Assignment Model
Inspection station
A B C D E
Product
1
5 0 2 4 4
2
3 0 0 0 3
3
4 0 4 4 3
4
0 3 0 2 0
5
7 0 6 7 4
Number of lines
= 3 (< m)
No optimal solution

15. Assignment example
Assignment Model
Inspection station
A B C D E
Product
1
3 0 0 2 2
2
3 2 0 0 3
3
2 0 2 2 1
4
0 5 0 2 0
5
5 0 4 5 2
Number of lines
= 4 (< m)
No optimal solution

16. Assignment example
Assignment Model
Inspection station
A B C D E
Product
1
2 0 0 1 1
2
3 3 1 0 3
3
1 0 2 1 0
4
0 6 1 2 0
5
4 0 4 4 1
Number of lines
= 5 (= m)
Optimal solution

17. Assignment example
Assignment Model
Inspection station
A B C D E
Product
1
2 0 0 1 1
2
3 3 1 0 3
3
1 0 2 1 0
4
0 6 1 2 0
5
4 0 4 4 1
Assignments:
Product ➔station
1 ➔ C
2 ➔ D
3 ➔ E
4 ➔ A
5 ➔ B
Total Transportation time (Z) = 6 + 9 + 15 + 11 + 14= 55 minute

18. Special cases of assignment problem
a)Unbalanced transportation (Total number of sources not equal to total
number of demands) :
-add dummy row(s) (sources) or column(s) (demands) with 0
assignment costs as needed.
b)Unacceptable assignment (Sourceican’t or shouldn’t be assigned to
demand j):
-Put Min the cost cell.
c)Maximization problem:
-Convert into a minimization problem by subtracting all elements
from the highest one then solve.
Assignment Model

19. LESSON 7:
TRANSSHIPMENT
MODEL

20. Transshipment Problem
◦A transportation problem in which a shipment may move through intermediate nodes
(transshipment nodes)before reaching a destination.
◦Can be converted to larger transportation problems and solved by transportation
methods.
◦Transshipment problems can also be solved by general linear programming techniques.

21. ◦Supply point: is a point that can send goods to another point but can not receive
goods from any other point
◦Demand point: is a point that can receive goods form other points but cannot send
goods to any other point.
◦Transshipment (intermediate) point : is a point that can both receive goods from
other points and send goods to other points
Transshipment Problem

22. Transshipment Problem
2
3
4
5
6
7
1
c
13
c
14
c
23
c
24
c
25
c
15
s
1
c
36
c
37
c
46
c
47
c
56
c
57
d
1
d
2
INTERMEDIATE
NODES
SUPPLY DEMAND
s
2

23. Transshipment Problem
Linear Programming Formulation
Objective function: Z = Min 
&#3627408470;&#3627408471;c
ijx
ij
Constraints: 
&#3627408470;&#3627408471;x
ij<S
i for each source i

&#3627408470;&#3627408471;x
ij<d
j for each demand j
x
ik-x
kj= 0 for each intermediate k
x
ij>0 or 1.

24. Thomas Industries and Washburn Corporation supply three firms (Zrox, Hewes,
Rockwright) with customized shelving for its offices. They both order shelving from
the same two manufacturers, Arnold Manufacturers and Supershelf, Inc.
Currently, weekly demands by the end users are 50 for Zrox, 60 for Hewes, and
40 for Rockwright. Both Arnold and Supershelfcan supply at most 75 units/week to
its customers. According to the contracts, unit costs from the manufacturers to the
suppliers and the cost to install the shelving at the various locations are:
Transshipment Problem
ThomasWashburn
Arnold 5 8
Supershelf 7 4
ZroxHewesRockwright
Thomas 1 5 8
Washburn 3 4 4

25. ARNOLD
WASH
BURN
ZROX
HEWES
75
75
50
60
40
5
8
7
4
1
5
8
3
4
4
Arnold
Super
Shelf
Hewes
Zrox
Thomas
Wash-
Burn
Rock-
Wright
Transshipment Problem

26. ◦a transshipment problem can be transformed to a balanced transportation problem by
using the following procedure:
1.If necessary, add a dummy row or column to balance the scale.
2.Construct a transportation table as follows:
a)A row in the table will be needed for each sourceand transshipment point.
b)A column will be needed for each demandand transshipment point.
c)each transshipment point will have:
1.Supply = its original supply (if it has one) + total available supply.
2.Demand = its original demand (if it has one) + total available demand.
Transshipment Problem

27. ZroxHewesRockwrightThomaswashburnSupply
Arnold M M M 5 8 75
Supper shelfM M M 7 4 75
Thomas 1 5 8 0 M 150
Washburn 3 4 4 M 0 150
Demand 50 60 40 150 150 Total =
450
•Where M is a very large number and used when the route is not valid
•Zero cost is used from a destination to itself.
•There is no need for dummy row or column, since the problem is balanced
Transshipment Problem

28. ZroxHewesRockwrightThomasWashburnSupply
Arnold 75
Supper shelf 75
Thomas 150
Washburn 150
Demand
50 60 40 150 150 Total = 450
M M
M
M
M M
M
M
5 8
5
3
1
7 4
044
8 0
Transshipment Problem
3
3
1
3
45412
150

29. ZroxHewesRockwrightThomasWashburnSupply
Arnold 75
Supper shelf 75
Thomas 150
Washburn 150
Demand
50 60 40 0 150 Total = 450
M M
M
M
M M
M
M
5 8
5
3
1
7 4
044
8 0
3
3
1
3
42
150
MMM
50
Transshipment Problem

30. ZroxHewesRockwrightThomasWashburnSupply
Arnold 75
Supper shelf 75
Thomas 150
Washburn 150
Demand
50 60 40 0 150 Total = 450
M M
M
M
M M
M
M
5 8
5
3
1
7 4
044
8 0
3
3
1
4
42
150
MMM
50 60
Transshipment Problem

31. ZroxHewesRockwrightThomasWashburnSupply
Arnold 75
Supper shelf 75
Thomas 150
Washburn 150
Demand
50 60 40 0 150 Total = 450
M M
M
M
M M
M
M
5 8
5
3
1
7 4
044
8 0
3
3
1
4
42
150
MMM
50 60
Transshipment Problem
40

32. ZroxHewesRockwrightThomasWashburnSupply
Arnold 75
Supper shelf 75
Thomas 150
Washburn 150
Demand
50 60 0 0 150 Total = 450
M M
M
M
M M
M
M
5 8
5
3
1
7 4
044
8 0
3
3
1
4
42
150
0MM
50 60
Transshipment Problem
40
75

33. ZroxHewesRockwrightThomasWashburnSupply
Arnold 75
Supper shelf 75
Thomas 150
Washburn 150
Demand
50 60 0 0 150 Total = 450
M M
M
M
M M
M
M
5 8
5
3
1
7 4
044
8 0
M
3
1
4
42
150
0MM
50 60
Transshipment Problem
40
0 75
75

34. ZroxHewesRockwrightThomasWashburnSupply
Arnold 75
Supper shelf 75
Thomas 150
Washburn 150
Demand
50 60 40 150 150 Total = 450
M M
M
M
M M
M
M
5 8
5
3
1
7 4
044
8 0
0
-4
-5
-8
85
150
121211
50 60
Transshipment Problem
40
0 75
75
u
v
0
MMM
M M M
M
M
6
-5 -2 1

35. ZroxHewesRockwrightThomasWashburnSupply
Arnold 75
Supper shelf 75
Thomas 150
Washburn 150
Demand
50 60 40 150 150 Total = 450
M M
M
M
M M
M
M
5 8
5
3
1
7 4
044
8 0
0
-4
-5
-8
85
100
12126
50
60
Transshipment Problem
40
50 25
75
u
v
50
MMM
M M M
M
M
6
-2 1
5

36. ZroxHewesRockwrightThomasWashburnSupply
Arnold 75
Supper shelf 75
Thomas 150
Washburn 150
Demand
50 60 40 150 150 Total = 450
M M
M
M
M M
M
M
5 8
5
3
1
7 4
044
8 0
0
-2
-5
-6
65
75
10106
50
35
Transshipment Problem
40
75
75
u
v
75
MMM
M M M
M
M
4
3
3
25
2
oTotal Transportation cost (Z) = 5*75+4*75+1*50+5*25+0*75+4*35+4*40+0*75= 1150 L.E.

37. Seventh Lesson
Summary
•Transportation scheme (contd.).
•Assignment model.
•Transshipment model.

38. Course Progress
Lesson 7
Assignment
Model
Lesson 8 Lesson 9Lesson 10Lesson 11

39. THANK YOU!