Four cargo ships will be used for shipping goods from one port to four other por
ID: 454098 • Letter: F
Question
Four cargo ships will be used for shipping goods from one port to four other ports (labeled 1, 2, 3, 4). Any ship can be used for making any one of these four trips. However, because of differences in the ships and cargos, the total cost of loading, transporting, and unloading the goods for the different ship-port combinations varies considerably, as shown in the table. The objective is to assign the four ships to four different ports in such a way as to minimize the total cost for all four shipments. Solve this assignment problem to get the optimal solution with the ship-port assignment and total cost.Explanation / Answer
This is a assignment problem.
Objective = Minimize the cost
Port
1
2
3
4
1
560
720
460
570
2
640
550
700
520
3
650
450
590
610
4
570
430
630
720
Step 1: Column Reduction (selects a minimum element in each column and then subtract the individual cell value from that min value.
Port
1
2
3
4
1
0
290
0
50
2
80
120
240
0
3
90
20
130
90
4
10
0
170
200
Step 2: Row Reduction (selects a minimum element in each row and then subtract the individual cell value from that min value).
Port
1
2
3
4
1
0
290
0
50
2
80
120
240
0
3
70
0
110
70
4
10
0
170
200
Step 3: Draw the straight lines to cover all the zeros
Port
1
2
3
4
1
0
290
0
50
2
80
120
240
0
3
70
0
110
70
4
10
0
170
200
If the number of straight lines are less than either no of rows or columns means , here the lines are 3 and no of rows are 4, then it will not give optimal solution. We have to revise the above table by subtracting the min element (10) from the uncut cell values and add that min value (10) at the intersection point.
Port
1
2
3
4
1
0
300
0
50
2
80
130
240
0
3
60
0
100
60
4
10
0
160
190
Here the drawn lines are 4 equal to no of rows i.e. 4
Means, now we can assign the assignment in the above table.
Port
1
2
3
4
1
0
300
0
0
2
80
130
240
0
3
60
0
100
60
4
0
0
160
190
So the final solution of the problem is
1==== 3 ====$ 460
2==== 4====$520
3====2====$450
4====1====$570
Total cost is $ 2000
Port
1
2
3
4
1
560
720
460
570
2
640
550
700
520
3
650
450
590
610
4
570
430
630
720
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.