Курсовая работа: Метод гілок та меж для рішення задач цілочисельного програмування
План
Вступ
Постановка задачі
Математична модель задачі комівояжера
Алгоритм рішення
Висновки
Список використаної літератури
Дата добавления на сайт: 04 марта 2025
Міністерство внутрішніх справ України
Харківський національний університет внутрішніх справ
ННІ Психології,менеджменту,соціальних та інформаційних технологій
Курсова робота з дисципліни:
«Вища математика»
на тему:
\"Метод гілок та меж для рішення задач цілочисельного програмування\"
Виконав: курсант групи
ІПТ-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 | 0 | 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). Розбиваємо безліч на дві підмножини: і .
| ji | 1 | 6 |
| 2 | 0 | 8 |
| 4 | 3 | 0 |
| 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 с. изд. дом «Феникс»