Економіка / Математичні методи в економіці

К.ф.м.н. Корольов Є.О., ст..Божко О.О.

Автомобільно-дорожній інститут ДНВЗ

«Донецький національний технічний університет»

ВИКОРИСТАННЯ МОДЕЛІ ГІЛОК ТА ГРАНИЦЬ В ОПТИМІЗАЦІЇ ЕКСКУРСІЙНИХ МАРШРУТІВ

Метод гілок і границь (англ. branch and bound) - загальний алгоритмічний метод для знаходження оптимальних рішень різних задач оптимізації, особливо дискретної і комбінаторної оптимізації. По суті, метод є варіацією повного перебору з відсівом підмножин допустимих рішень, які завідомо не містять оптимальних рішень.

В основі методу гілок і границь лежить ідея послідовного розбиття множини допустимих рішень на підмножини (стратегія "розділяй і володарюй"). На кожному кроці методу елементи розбиття піддаються перевірці для з'ясування, містить дана підмножина оптимальне рішення чи ні. Перевірка здійснюється за допомогою обчислення оцінки знизу для цільової функції у цій підмножині. Якщо оцінка знизу не менше рекорду – найкращого зі знайдених рішень, то підмножина може бути відкинута. Підмножина, яка перевіряється може бути відкинута ще й у тому випадку, коли у ній вдається знайти найкраще рішення. Якщо значення цільової функції на знайденому вирішенні менше рекорду, то відбувається зміна рекорду. По закінченню роботи алгоритму рекорд є результатом його роботи.

Якщо вдається відкинути всі елементи розбиття, то рекорд - оптимальне рішення задачі. В іншому випадку, з не відкинутих підмножин вибирається найбільш перспективна (наприклад, з найменшим значенням нижньої оцінки),і вона піддається розбиттю. Нові підмножини знову піддаються перевірці і т.д.

Постановка задачі: планується ввести новий екскурсійний маршрут який буде проходити містами АР Крим: 1 – Севастополь, 2 – Інкерман, 3 – Бахчисарай, 4 – Алупка, 5 – Сімферополь, 6 – Ялта, 7 – Алушта. Відомі відстані між цими містами С_ij, за умовою, що відстані С_ij = С_ji (табл.1).Екскурсія проходить таким чином, що автобус починає свій шлях із одного з міст, відвідує усі міста, кожне по одному разу, та повертається у початковий пункт. Необхідно знайти таку послідовність відвідування міст, при якій сумарна відстань шляху буде мінімальною.

Для рішення поставленої задачі необхідно визначити верхню і нижню границі, та початковий пункт екскурсії.

Визначаємо верхню границю. У якості верхньої границі можна узяти довжину будь-якого маршруту. Візьмемо маршрут «1-2-3-5-7-4-6-1». Довжина маршруту визначається за формулою:

S=20+33+30+41+48+19+81=272 В.Г = S=272

Далі визначаємо початковий пункт. Для цього складаємо матрицю відстаней (табл.1), елементи матриці Сij відповідають відстані від пункту i до пункту j.

В кожному рядку матриці С знаходимо мінімальний елемент (di). Далі вибираємо мінімальний елемент з тих, які залишилися у строках (di^/). Знаходимо мінімальних елементів di^// = di^/ - di. Обираємо max серед di^// , та знаходимо min тієї строки, де знаходиться max di^// (табл. 2). Таким чином визначили початковий пункт 1 – Севастополь.

Всю безліч маршрутів щодо ребра розгалуження (1,2) розбиваємо на дві підмножини (К_ij =1) і (К_ij=0). Включення ребра (1,2) проводиться шляхом виключення всіх елементів 1-го рядка і 2-го стовпця (замінюємо їх на N), в якій елемент d₂₁ замінюємо на N, для виключення утворення негамильтонового циклу. Оскільки нижня границя цієї підмножини (1,2) менше, ніж верхня границя множини, то ребро (1,2) включаємо до маршруту. Далі розрахунки нижніх границь проводимо аналогічно.

Таблиця 1– Матриця відстаней Таблиця 2– Знаходження початкового пункту

i j	1	2	3	4	5	6	7
1	N	20	53	62	83	81	100
2	20	N	33	53,5	63	71	100
3	53	33	N	77	30	58	71
4	62	53,5	77	N	89	19	48
5	83	63	30	89	N	70	41
6	81	71	58	19	70	N	29
7	100	100	71	48	41	29	N

i j	1	2	3	4	5	6	7	di	di^/	di^//
1	N	20	53	62	83	81	100	20	53	33
2	20	N	33	53,5	63	71	100	20	33	13
3	53	33	N	77	30	58	71	30	33	3
4	62	53,5	77	N	89	19	48	19	48	29
5	83	63	30	89	N	70	41	30	41	11
6	81	71	58	19	70	N	29	19	29	10
7	100	100	71	48	41	29	N	29	41	12

- продовження розгалуження веде до відсіку гілок

Рисунок 1 – Дерево гілок та границь, остання ітерація.

Таким чином, маємо оптимальний маршрут «1-2-3-5-7-6-4-1», відстань якого дорівнює 234 (км).

ЛІТЕРАТУРА

1. В.И. Мудров. Задача о коммивояжере — М.: «Знание», 1969. – 62 с.

2. Беллман Д. Динамическое программирование. М.: Изд-во иностр. лит., 1960. – 400 с.

3. Конюховский П.В. Метематические методы исследования операций. – СПб: Питер, 2001. – 192 с.