Метод гілок та меж для рішення задач цілочисельного програмування

Міністерство внутрішніх справ України

Харківський національний університет внутрішніх справ

ННІ Психології,менеджменту,соціальних та інформаційних технологій

Курсова робота з дисципліни:

«Вища математика»

на тему:

"Метод гілок та меж для рішення задач цілочисельного програмування"

Виконав: курсант групи

ІПТ-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

ji1234561?71621217213?211543233253?311794131027?33125921914?51642175923?

) Праворуч до таблиці приєднуємо стовпець Ui, в якому записуємо мінімальні елементи відповідних рядків. Віднімаємо елементи Ui з відповідних елементів рядка матриці.

ji123456Ui1?716212172213?21154323133253?3117934131027?3312105921914?512642175923?5

2) Внизу отриманої матриці приєднуємо рядок Vj, в якій записуємо мінімальні елементи стовпців. Віднімаємо елементи Vj з відповідних стовпців матриці.

ji123456Ui1?716212172213?21154323133253?3117934131027?3312105921914?512642175923?5

) У результаті обчислень отримуємо матрицю, наведену по рядках і стовпцях, яка зображена у вигляді таблиці 2.

Табл.2

ji1234561?5141701913203?80230832204?26144430017?230457071710?476371208218?

) Знаходимо константу приведення:

.

Таким чином, нижньою межею множини всіх гамільтонових контурів буде число .

) Знаходимо ступеня нулів повністю наведеної матриці. Для цього як би замінити в ній всі нулі на знак «?» і встановлюємо суму мінімальних елементів відповідного рядка і стовпця. Ступені нулів записані в правих верхніх кутах клітин, для яких .

) Визначаємо максимальну ступінь нуля. Вона дорівнює 19 і відповідає клітині (1, 5). Таким чином, претендентом на включення до гамільтонів контур є дуга (1, 5).

) Розбиваємо безліч всіх гамільтонових контурів на два: і . Матрицю з дугою (1; 5) отримуємо табл.2 шляхом викреслювання рядка 1 і стовпця 5. Щоб не допускати утворення негамільтонова контуру, замінюємо елемент (5; 1) на знак «?».

ji1234620?8083220?26443017?05?01710476371202?

8) Матрицю гамільтонових контурів отримаємо з таблиці 2 шляхом заміни елементу (1, 5) на знак «?».

ji1234561?51417?13520?803083220?2614443017?2305701710?47637120218?14

9) Робимо додаткове приведення матриці контурів: : = 0. Нижня межа множини дорівнює .

) Знаходимо константу приведення для множині контурів:. Отже, нижня межа множини дорівнює .

) Порівнюємо нижні межі підмножин і . Так як , то подальшого розгалуження піддаємо множини.

На рис.1 представлено розгалуження по дузі (1, 5).

рис.1

Переходимо до розгалуження підмножини . Його наведена матриця представлена в таблиці нижче.

ji12346203?802832204?264430017?045?010171047637120102?

12) Дізнаємося ступеня нулів матриці. Претендентами на включення до гамільтонів контур будуть кілька дуг (5, 2) і (6, 3). Для подальших розрахунків виберемо дугу (6, 3). Розбиваємо множину на дві підмножини: і (табл. 3 та 4). Щоб не допустити утворення негамільтонова контуру, у таблиці 3 замінюємо елемент (3; 6) на знак «?»

Табл.3

ji124620?08322026?430?05?01047

Табл.4

ji1234620?8083220?26443017?05?017104763712?2?28

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

ji1246203?02832202226?4300?085?0101047

Претендентом до включення в гамільтонів контур стане дуга (3, 2). Розбиваємо множину на дві і .

ji146200843?05?104710

Очевидно, , . Отже, чергового розгалуження потрібно піддати підмножина .

ji124620?08322?26?22430?05?01047

Переходимо до розгалуження підмножини . Його наведена матриця представлена в таблиці нижче.

ji14620300843?0115?03737

Визначаємо ступеня нулів. Претендентом на включення до гамільтонів контур є дуга (5, 4). Розбиваємо безліч на дві підмножини: і .

ji16208430

i\j146200843?05??3737

Знаходимо нижні межі , . Отже, чергового розгалуження потрібно піддати підмножина . Але його матриця має розмірність . Тому в гамільтонів контур слід включити дуги, що відповідають у матриці нульовим елементам. Це дуги (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 с. изд. дом «Феникс»