Вказівки до виконання

1. Визначаються показники інвестицій, витрат та доходів за своїм варіантом. (i”-дорівнює передостанній, а “j”- останній цифрі номеру залікової книжки).

2. Визначаються етапи вирішення задачі.

3. Будується мережна модель, де довжина дуг – чисельно дорівнює доходам від реалізації кращого припустимого проекту, а вузли – етапи реалізації капіталовкладень.

4. Знаходиться найдовший шлях, який відповідає максимізації прибутку від реалізації проекту.

Контрольні питання

1. Що є критерієм оптимальності у задачах динамічного програмування (ДП)?

2. Які типи задач можна вирішувати за допомогою ДП?

Практичне заняття № 8

ЗАДАЧА КОМІВОЯЖЕРА

Мета заняття: закріплення практичних навичок рішення задачі комівояжера.

Завдання. Визначити порядок відвідування комівояжером міст з мінімізацією загальної довжини шляху.

Задача. Комівояжер повинен виїхати із заданого міста, відвідати кожен із n-1 міст, що залишились тільки один раз і повернутися у місто, з якого він виїхав. Визначити послідовність об’їзду міст, при якій комівояжеру потребується проїхати найменшу сумарну відстань.

В таблиці 8.1 задана вихідна матриця, в який зазначені відстані між кожною парою міст в кілометрах.

Таблиця 8.1 – Матриця відстаней

Місто	1	2	3	4	5	6
1	-	27+i	43-i-j	16-j	30-j	26-i
2	7	-	16+i	1+j	30-i	30-j
3	20-i	13+i	-	35	5+j	0
4	21-j	16-j	25-i	-	18+i	18+j
5	12+i	46-i-j	27-j	48-i-j	-	5+j
6	23-j	5+i	5+j	9+i	5+j	-

Вказівки до виконання

1. Визначаються відстані між за своїм варіантом. (i”-дорівнює передостанній, а “j”- останній цифрі номеру залікової книжки).

2. Визначаються нижні межі методом редукції.

3. Проводиться розгалуження множини всіх маршрутів на підмножини, що пересікаються.

4. Проводиться процедура розрахунків.

Контрольні питання

1. Яким методом вирішується задача комівояжера?

2. Назвіть засновника методу?

3. Що процедура редукції?

4. Що таке верхня та нижня межа?

5. Що таке оптимальний маршрут?

Список літератури

1. Балашевич В.А. Математические методы управления производством. - Минск: Вышейш. шк., 1976.

2. X. Таха. Введение в исследование операций. Т.І.- М.: Мир, 1985.

3. X. Таха. Введение в исследование операций. Т.2.- М.: Мир, 1985.

4. А.В. Кузнецов и др. Математическое программирование ‑ М.: Высшая школа, 1980.

5. А.В. Кузнецов и др. Математическое программирование.- М.: Высшая школа, 1994.

6. Калихман И.Л. Сборник задач по математическому программированию. ‑ М.: Высш. шк., 1974.

7. Симовский Ю.А. Сборник задач по математическому программированию. ‑ X.: ХВВУТ МВД СССР, 1986.

8. Справочник по математике для зкономистов / Под ред. В.И. Ермакова. ‑ М.: Высш. шк., 1989.

9. Душкін В.Д. Навчально-методичні матеріали з дисципліни "Математичне моделювання". ‑ X.: Військ. ін-т ВВ МВС України, 2002.

10. Исследование операций в экономике. Учеб. пособие для вузов/ Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридмак; Под. ред.. проф. Н.Ш. Кремера – М.:ЮНИТИ, 2004 – 407с.