Seminar 5:
Transportation and assignment problem, traveling salesman
problem
Problem 1: Consider the transportation problem having 4 suppliers and 3 customers
with unit costs of transport given by the following parameter table:
S1 S2 S3 S4 request
C1 11 11 7 12 50
C2 6 9 6 10 200
C3 5 8 11 10 150
capacity 120 90 70 120
a) Formulate mathematical model for this transportation problem
b) Introduce a dummy line to balance the problem if necessary.
c) Use the northwest corner rule to construct an initial basic feasible solution.
d) Starting with the initial basic solution from part (b), interactively apply
the transportation simplex method (MODI) to obtain an optimal solution.
e) Check the solution using Excel Solver
Problem 2: (modified from Hillier and Lieberman, 8.3-2.) 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 cargoes, the total cost of loading, transporting,
and unloading the goods for the different ship-port combinations varies
considerably, as shown in the following table:
Port
Ship 1 2 3 4
A $500 $400 $600 $700
B $600 $300 $700 $500
C $700 $500 $800 $600
D $600 $400 $700 $600
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.
a) Formulate mathematical model for this assignment problem
b) Obtain an optimal solution using Hungarian method.
c) Check the optimality of the solution using Excel Solver
Problem 3: The Financial Office recruits candidates for positions of heads of
the three departments, requiring different skills and knowledge. Five candidates
were selected for the assessment center where their competence for individual
jobs has been tested. The results are shown in the table (the highest possible
score was 30 points).
Applicant
Department A B C D E
D1 25 27 24 27 28
D2 28 23 25 24 27
D3 22 21 23 20 24
Introduce dummy lines to balance the problem if necessary and use the Hungarian
method to assign the candidates to appropriate positions so that their
competence for work in the individual departments is as high as possible. (Maximization
problem!)
Problem 4: Traveling salesman living in the city A has to visit places B, C, D,
E and come back to A. The distance table is given below.
A B C D E
A X 50 70 40 60
B 50 X 40 30 80
C 70 40 X 40 60
D 40 30 40 X 50
E 60 80 60 50 X
In what order should he visit the cities so as the total length of the round-trip
is minimal? Use the closest neighbor method.