Метод гілок та меж для рішення задач цілочисельного програмування
Міністерство
внутрішніх справ України
Харківський
національний університет внутрішніх справ
ННІ
Психології,менеджменту,соціальних та інформаційних технологій
Курсова
робота з дисципліни:
«Вища
математика»
на
тему:
"Метод
гілок та меж для рішення задач цілочисельного програмування"
Виконав: курсант групи
ІПТ-09-2 Руденко С.В.
Перевірив: доцент
кафедри ПМ та
аналітичного
забезпечення ОВС
Соколовська О.Г.
Харків
2011
План
Вступ
Постановка задачі
Математична модель задачі комівояжера
Алгоритм рішення
Висновки
Список використаної літератури
Вступ
У 1859 р. Сер Вільям Гамільтон,
знаменитий математик, який дав світу теорію комплексного числа і кватерніони,
запропонував дитячу головоломку, в якій пропонувалося здійснити «кругове
подорож» по 20 містах, розташованих у різних частинах земної кулі. Кожне місто
з'єднувався дорогами з трьома сусідніми так, що дорожня мережа утворювала 30
ребер додекаедра, у вершинах якого знаходилися міста a, b,... t. Обов'язковою
умовою було вимога: кожне місто за винятком першого можна відвідати один раз.
Гамильтонова завдання про
мандрівника нерідко перетворюється на задачу про комівояжера. Комівояжер - не
вільно мандрівний турист, а ділова людина, обмежений тимчасовими, грошовими або
будь-якими іншими ресурсами. Гамильтонова завдання може стати завданням про
комівояжера, якщо кожне з ребер забезпечити числовою характеристикою. Це може
бути кілометраж, час на дорогу, вартість квитка, витрата пального і т.д. Таким
чином, умовні характеристики дадуть числовий ряд, елементи якого можуть бути
розподілені між ребрами як завгодно.
Постановка завдання
Розглянемо задачу про комівояжера.
Є n міст, відстані (вартість
проїзду, витрата пального на дорогу і т.д.) між якими відомі. Комівояжер
повинен пройти всі n міст по одному разу, повернувшись в те місто, з якого
почав. Потрібно знайти такий маршрут руху, при якому сумарний пройдене відстань
(вартість проїзду і т.д.) буде мінімальним.
Очевидно, що завдання комівояжера -
це проблема віднайдення найкоротшого гамильтонова циклу в повному графі.
Можна запропонувати
наступну просту схему розв'язання задачі комівояжера: згенерувати всі n!
можливих перестановок вершин повного графа, підрахувати для кожної перестановки
довжину маршруту і вибрати найкоротший. Однак, n! із зростанням n росте швидше,
ніж будь-який поліном від n, і навіть швидше, ніж .
Таким чином, рішення задачі комівояжера методом повного перебору виявляється
практично нездійсненним, навіть при досить невеликих n.
Вирішити задачу комівояжера
також можна за допомогою алгоритму Крускала і «дерев'яного» алгоритму. Ці
методи прискорюють розробку алгоритму в порівнянні з методом повного перебору,
проте не завжди дають оптимальне рішення.
Існує метод розв'язання
задачі комівояжера, який дає оптимальне рішення. Цей метод називається методом
гілок і меж. Рішення задачі комівояжера методом гілок і меж по-іншому називають
алгоритмом Літтла.
Якщо вважати міста
вершинами графа, а комунікації (i, j) - його дугами, то вимога знаходження
мінімального шляху, що проходить один і тільки один раз через кожне місто, і
повернення назад, можна розглядати як знаходження на графі гамильтонова контуру
мінімальної довжини.
Для практичної
реалізації ідеї методу гілок і меж стосовно до задачі комівояжера потрібно
знайти метод визначення нижніх меж підмножини і розбиття множини гамільтонових
контурів на підмножини (розгалуження).
Визначення нижніх меж
базується на тому твердженні, що якщо до всіх елементів i-го рядка або j-го
стовпця матриці C додати або відняти число, то завдання залишиться
еквівалентної колишньою, тобто оптимальність маршруту комівояжера не зміниться,
а довжина будь-якого гамильтонова контуру зміниться на дану величину .
Опишемо алгоритм Літтла
для знаходження мінімального гамильтонова контуру для графа з n вершинами. Граф
представляють у вигляді матриці його дуг. Якщо між вершинами Xi і Xj немає
дуги, то ставиться символ «∞».
Алгоритм Літтла для
розв'язання задачі комівояжера можна сформулювати у вигляді наступних правил:
. Знаходимо в кожному
рядку матриці мінімальний
елемент і
віднімаємо його з усіх елементів відповідного рядка. Отримаємо матрицю,
наведену по рядках, з елементами
.
. Якщо в матриці ,
наведеної по рядках, виявляться стовпці, що не містять нуля, то наводимо її по
стовпцях. Для цього в кожному стовпці матриці вибираємо мінімальний
елемент, і віднімаємо його з усіх елементів відповідного стовпця. Отримаємо
матрицю
,
кожен рядок і стовпець,
якої містить хоча б один нуль. Така матриця називається наведеної по рядках і
стовпцях.
. Підсумовуємо елементи і
,
отримаємо константу приведення
,
яка буде нижньою межею
множини всіх допустимих гамільтонових контурів, тобто
.
. Знаходимо ступеня
нулів для наведеної по рядках і стовпцях матриці. Для цього подумки нулі в
Матіца замінюємо на знак «∞» і знаходимо суму мінімальних елементів рядка
і стовпця, відповідних цьому нулю. Записуємо її в правому верхньому кутку
клітки:
.
. Вибираємо дугу ,
для якої ступінь нульового елемента досягає максимального значення
.
. Розбиваємо безліч всіх
гамільтонових контурів на
дві підмножини і
.
Підмножина гамільтонових
контурів містить дугу ,
- її
не містить. Для отримання матриці контурів , що включають дугу ,
викреслюємо в матриці рядок
і
стовпець .
Щоб не допустити утворення негамільтонова контуру, замінимо симетричний елемент
на
знак «∞».
. Наводимо матрицю
гамільтонових контурів .
Нехай -
константа її приведення. Тоді нижня межа множина визначиться так:
.
. Знаходимо множину
гамільтонових контурів,
що не включають дугу.
Виняток дуги досягається
заміною елемента в
матриці на
∞.
. Робимо приведення
матриці гамільтонових контурів. Нехай -
константа її приведення. Нижня межа множина визначається так:
.
. Порівнюємо нижні
множини, підмножини гамільтонових контурів і.
Якщо ,
то подальшого розгалуження в першу чергу підлягає множина .
Якщо ж ,
то розбиття підлягає множина .
Процес розбиття множин
на підмножини супроводжується побудовою дерева розгалужень.
. Якщо в результаті
розгалужень отримуємо матрицю , то визначаємо
отриманий розгалуженням гамільтонів контур і його довжину.
. Порівнюємо довжину гамильтонова
контуру з нижніми межами обірваних гілок. Якщо довжина контуру не перевищує їх
нижніх меж, то завдання виконане. В іншому випадку розвиваємо гілки підмножин з
нижньою межею, меншою отриманого контуру, до тих пір, поки не отримаємо маршрут
з меншою довжиною або не переконаємося, що такого не існує.
Математична модель
задачі комівояжера
Завдання комівояжера
може бути сформульована як цілочисельна введенням булевих змінних ,
якщо маршрут включає переїзд з міста i безпосередньо в місто j і в
іншому випадку. Тоді можна задати математичну модель задачі, тобто записати
цільову функцію і систему обмежень:
(1)
Умови (2) - (4) в
сукупності забезпечують, що кожна змінна дорівнює або нулю, або одиниці. При
цьому обмеження (2), (3) висловлюють умови, що комівояжер побуває в кожному
місті один раз на нього прибувши (обмеження (2)), і один раз з нього виїхавши
(обмеження (3)).
Проте цих обмежень не
достатньо для постановки задачі комівояжера, так як вони не виключають рішення,
де замість простого циклу, що проходить через n вершин, відшукуються 2 і більше
окремих циклу (підциклу), що проходить через менше число вершин. Тому завдання,
описана рівняннями (2) - (4) повинна бути доповнена обмеженнями, що
забезпечують зв'язність шуканого циклу.
Для того, щоб виключити
при постановці завдання всі можливі підцикли в систему обмежень задачі
включають такі обмеження:
, Де ,
і .
Алгоритм рішення
Дана матриця відстаней,
представлена в таблиці 1. Необхідно за допомогою алгоритму Літтла вирішити
завдання комівояжера.
Табл.1
ji
|
1
|
2
|
3
|
4
|
5
|
6
|
1
|
∞
|
7
|
16
|
21
|
2
|
17
|
2
|
13
|
∞
|
21
|
15
|
43
|
23
|
3
|
25
|
3
|
∞
|
31
|
17
|
9
|
4
|
13
|
10
|
27
|
∞
|
33
|
12
|
5
|
9
|
2
|
19
|
14
|
∞
|
51
|
6
|
42
|
17
|
5
|
9
|
23
|
∞
|
) Праворуч до таблиці приєднуємо
стовпець Ui, в якому записуємо мінімальні елементи відповідних рядків.
Віднімаємо елементи Ui з відповідних елементів рядка матриці.
ji
|
1
|
2
|
3
|
4
|
5
|
6
|
Ui
|
1
|
∞
|
7
|
16
|
21
|
2
|
17
|
2
|
2
|
13
|
∞
|
21
|
15
|
43
|
23
|
13
|
3
|
25
|
3
|
∞
|
31
|
17
|
9
|
3
|
4
|
13
|
10
|
27
|
∞
|
33
|
12
|
10
|
5
|
9
|
2
|
19
|
14
|
∞
|
51
|
2
|
6
|
42
|
17
|
5
|
9
|
23
|
∞
|
5
|
2) Внизу отриманої матриці
приєднуємо рядок Vj, в якій записуємо мінімальні елементи стовпців. Віднімаємо
елементи Vj з відповідних стовпців матриці.
ji123456Ui
|
|
|
|
|
|
|
|
1
|
∞
|
7
|
16
|
21
|
2
|
17
|
2
|
2
|
13
|
∞
|
21
|
15
|
43
|
23
|
13
|
3
|
25
|
3
|
∞
|
31
|
17
|
9
|
3
|
4
|
13
|
10
|
27
|
∞
|
33
|
12
|
10
|
5
|
9
|
2
|
19
|
14
|
∞
|
51
|
2
|
6
|
42
|
17
|
5
|
9
|
23
|
∞
|
5
|
) У результаті обчислень отримуємо
матрицю, наведену по рядках і стовпцях, яка зображена у вигляді таблиці 2.
Табл.2
ji
|
1
|
2
|
3
|
4
|
5
|
6
|
1
|
∞
|
5
|
14
|
17
|
019
|
13
|
2
|
03
|
∞
|
8
|
02
|
30
|
8
|
3
|
22
|
04
|
∞
|
26
|
14
|
4
|
4
|
3
|
00
|
17
|
∞
|
23
|
04
|
5
|
7
|
07
|
17
|
10
|
∞
|
47
|
6
|
37
|
12
|
08
|
2
|
18
|
∞
|
) Знаходимо константу приведення:
.
Таким чином, нижньою
межею множини всіх гамільтонових контурів буде число .
) Знаходимо ступеня
нулів повністю наведеної матриці. Для цього як би замінити в ній всі нулі на
знак «∞» і встановлюємо суму мінімальних елементів відповідного рядка і
стовпця. Ступені нулів записані в правих верхніх кутах клітин, для яких .
) Визначаємо максимальну
ступінь нуля. Вона дорівнює 19 і відповідає клітині (1, 5). Таким чином,
претендентом на включення до гамільтонів контур є дуга (1, 5).
) Розбиваємо безліч всіх
гамільтонових контурів на
два: і
.
Матрицю з
дугою (1; 5) отримуємо табл.2 шляхом викреслювання рядка 1 і стовпця 5. Щоб не
допускати утворення негамільтонова контуру, замінюємо елемент (5; 1) на знак «∞».
ji
|
1
|
2
|
3
|
4
|
6
|
2
|
0
|
∞
|
8
|
0
|
8
|
3
|
22
|
0
|
∞
|
26
|
4
|
4
|
3
|
0
|
17
|
∞
|
0
|
5
|
∞
|
0
|
17
|
10
|
47
|
6
|
37
|
12
|
0
|
2
|
∞
|
8) Матрицю гамільтонових
контурів отримаємо
з таблиці 2 шляхом заміни елементу (1, 5) на знак «∞».
ji
|
1
|
2
|
3
|
4
|
5
|
6
|
|
1
|
∞
|
5
|
14
|
17
|
∞
|
13
|
5
|
2
|
0
|
∞
|
8
|
0
|
30
|
8
|
|
3
|
22
|
0
|
∞
|
26
|
14
|
4
|
|
4
|
3
|
17
|
∞
|
23
|
0
|
|
5
|
7
|
0
|
17
|
10
|
∞
|
47
|
|
6
|
37
|
12
|
0
|
2
|
18
|
∞
|
|
|
14
|
|
9) Робимо додаткове приведення
матриці контурів: :
= 0. Нижня межа множини дорівнює
.
) Знаходимо константу
приведення для множині контурів:.
Отже, нижня межа множини дорівнює
.
) Порівнюємо нижні межі
підмножин і
.
Так як ,
то подальшого розгалуження піддаємо множини.
На рис.1 представлено
розгалуження по дузі (1, 5).
рис.1
Переходимо до
розгалуження підмножини .
Його наведена матриця представлена в таблиці нижче.
ji
|
1
|
2
|
3
|
4
|
6
|
2
|
03
|
∞
|
8
|
02
|
8
|
3
|
22
|
04
|
∞
|
26
|
4
|
4
|
3
|
00
|
17
|
∞
|
04
|
5
|
∞
|
010
|
17
|
10
|
47
|
6
|
37
|
12
|
010
|
2
|
∞
|
12) Дізнаємося ступеня
нулів матриці. Претендентами на включення до гамільтонів контур будуть кілька
дуг (5, 2) і (6, 3). Для подальших розрахунків виберемо дугу (6, 3). Розбиваємо
множину на дві підмножини: і (табл.
3 та 4). Щоб не допустити утворення негамільтонова контуру, у таблиці 3
замінюємо елемент (3; 6) на знак «∞»
Табл.3
ji
|
1
|
2
|
4
|
6
|
2
|
0
|
∞
|
0
|
8
|
3
|
22
|
0
|
26
|
∞
|
4
|
3
|
0
|
∞
|
0
|
5
|
∞
|
0
|
10
|
47
|
Табл.4
ji
|
1
|
2
|
3
|
4
|
6
|
|
2
|
0
|
∞
|
8
|
0
|
8
|
|
3
|
22
|
0
|
∞
|
26
|
4
|
|
4
|
3
|
0
|
17
|
∞
|
0
|
|
5
|
∞
|
0
|
17
|
10
|
47
|
|
6
|
37
|
12
|
∞
|
2
|
∞
|
2
|
|
8
|
|
Визначимо константи
приведення для цих матриць,
.
Отже, ,
.
Так як ,
то подальшого розгалуження підлягає підмножина . Знаходимо ступеня
нулів матриці.
ji
|
1
|
2
|
4
|
6
|
2
|
03
|
∞
|
02
|
8
|
3
|
22
|
022
|
26
|
∞
|
4
|
3
|
00
|
∞
|
08
|
5
|
∞
|
010
|
10
|
47
|
Претендентом до
включення в гамільтонів контур стане дуга (3, 2). Розбиваємо множину на
дві і
.
ji
|
1
|
4
|
6
|
|
2
|
0
|
0
|
8
|
|
4
|
3
|
∞
|
0
|
|
5
|
∞
|
10
|
47
|
10
|
Очевидно, ,
.
Отже, чергового розгалуження потрібно піддати підмножина .
ji
|
1
|
2
|
4
|
6
|
|
2
|
0
|
∞
|
0
|
8
|
|
3
|
22
|
∞
|
26
|
∞
|
22
|
4
|
3
|
0
|
∞
|
0
|
|
5
|
∞
|
0
|
10
|
47
|
|
Переходимо до розгалуження
підмножини .
Його наведена матриця представлена в таблиці нижче.
ji
|
1
|
4
|
6
|
2
|
03
|
00
|
8
|
4
|
3
|
∞
|
011
|
5
|
∞
|
037
|
37
|
Визначаємо ступеня
нулів. Претендентом на включення до гамільтонів контур є дуга (5, 4).
Розбиваємо безліч на
дві підмножини: і
.
i\j
|
1
|
4
|
6
|
|
2
|
0
|
0
|
8
|
|
4
|
3
|
∞
|
0
|
|
5
|
∞
|
∞
|
37
|
37
|
Знаходимо нижні межі ,
.
Отже, чергового розгалуження потрібно піддати підмножина .
Але його матриця має розмірність . Тому в гамільтонів
контур слід включити дуги, що відповідають у матриці нульовим
елементам. Це дуги (2; 1) і (4, 6).
На рис.2 представлено
дерево розгалужень. Визначимо отриманий гамільтонів контур. До нього увійшли
дуги .
Довжина контуру дорівнює .
Так як кордони обірваних гілок більше довжини контуру 1 - 5 - 4 - 6 - 3 - 2 -
1, то цей контуру має найменшу довжину.
Рис.2
гамільтон модель задача
комівояжер
Висновки
Завдання комівояжера є
частковим випадком гамильтоновой завдання про мандрівника. Суть задачі
комівояжера полягає в знаходженні сумарною мінімальної характеристики
(відстані, вартості проїзду і т.д.), при цьому комівояжер повинен пройти всі n
міст по одному разу, повернувшись в те місто, з якого почав.
Існують кілька методів
розв'язання задачі комівояжера: метод повного перебору, за допомогою методу
гілок і меж (алгоритм Літтла), алгоритму Крускала, «дерев'яного» алгоритму і
т.д. Однак тільки метод гілок і меж дає нам у результаті найоптимальніше
рішення.
Основна ідея методу
Літтла полягає в тому, що спочатку будують нижню межу довжин маршрутів для
всього безлічі гамільтонових контурів . Потім вся безліч
контурів розбивають
на дві підмножини таким
чином, щоб перше підмножина складалося з гамільтонових контурів, містять деяку
дугу (i, j), а інше підмножина не містило цієї дуги.
Для практичної
реалізації ідеї методу гілок і меж стосовно до задачі комівояжера потрібно
знайти метод визначення нижніх меж підмножини і розбиття множини гамільтонових
контурів на підмножини (розгалуження). Таке визначення нижніх меж базується на
тому твердженні, що якщо до всіх елементів i-го рядка або j-го стовпця матриці
C додати або відняти число , то завдання залишиться
еквівалентної колишньою, тобто оптимальність маршруту комівояжера не зміниться,
а довжина будь-якого гамильтонова контуру зміниться на дану величину.
Використовуючи ЕОМ,
методом гілок і меж можна вирішити задачі комівояжера для .
Список використаної
літератури
1. О.Е. Акимов «Дискретная математика. Логика, группы, графы»,
Москва, 2003, 376 с., ил., изд. дом «Лаборатория базовых знаний».
. Ф.А. Новиков «Дискретная математика для программистов»
С.-Петербург, 2002 г. 304 с., ил., изд. дом «Питер».
. В.М. Бондарев «Основы программирования» 1998 г., 368 с. изд. дом
«Феникс»