Seminar 6:
Integer programming; assignment and traveling salesman
problems
Problem 1: 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 2: 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. Try to start the method from
different cities. Check the optimality of the best solution by the Hungarian
method.
Problem 3: Build a mathematical model for integer programming problems
and use Excel Solver to find their solutions:
a) Potatoes problem
The food company is processing potatoes; they produce chips, which are sold for
120 CZK per kg, and fries (76 CZK per kg). According to technological process,
2 kg of potatoes and 0,4 l of oil are used for the production of 1 kg of chips and
1,5 kg of potatoes and 0,2 l of oil are used for 1 kg of fries. Design the production
plan maximizing the profit and respecting the capacity of suppliers (100 kg of
potatoes and 16 liters of oil). The purchase prices of raw materials are 12 CZK
/ kg of potatoes and 40 CZK / liter of oil (we are neglecting labor costs, energy,
etc.). How will the optimal solution change if we can sell the products in XXL
packing only (3kg packing of chips of and 15kg packing of fries)?
b) Cutting schema problem
The metal manufacturing company buys the material from their supplier in the
form of 65 cm long pipes. They need at least 1200 pieces of 20 cm length pipes
and at least 900 pieces of 15 cm long pipes for further processing. How should
the company cut the long pipes so that the total amount of the purchased material
is minimal?
c) Scheduling problem
The art gallery needs to schedule the following number of workers for service on
a particular day:
Mon Tue We Thu Fri Sat Sun
22 17 13 14 15 18 24
Workers are always working for five consecutive days, followed by two days off.
The working cycle can start any day of the week.
The task is to schedule the number of employees starting their 5-day working
cycles for every day in a week and determine the smallest number of employees
necessary to cover operational needs of the art gallery.