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

Міністерство внутрішніх справ України Харківський національний університет внутрішніх справ ННІ Психології, менеджменту, соціальних та інформаційних технологій Курсова робота з дисципліни:

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

на тему:

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

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

ІПТ-09−2 Руденко С.В.

Перевірив: доцент кафедри ПМ та аналітичного забезпечення ОВС Соколовська О.Г.

Харків 2011

План Вступ Постановка задачі

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

Вступ У 1859 р. Сер Вільям Гамільтон, знаменитий математик, який дав світу теорію комплексного числа і кватерніони, запропонував дитячу головоломку, в якій пропонувалося здійснити «кругове подорож» по 20 містах, розташованих у різних частинах земної кулі. Кожне місто з'єднувався дорогами з трьома сусідніми так, що дорожня мережа утворювала 30 ребер додекаедра, у вершинах якого знаходилися міста a, b,… t. Обов’язковою умовою було вимога: кожне місто за винятком першого можна відвідати один раз.

Гамильтонова завдання про мандрівника нерідко перетворюється на задачу про комівояжера. Комівояжер — не вільно мандрівний турист, а ділова людина, обмежений тимчасовими, грошовими або будь-якими іншими ресурсами. Гамильтонова завдання може стати завданням про комівояжера, якщо кожне з ребер забезпечити числовою характеристикою. Це може бути кілометраж, час на дорогу, вартість квитка, витрата пального і т.д. Таким чином, умовні характеристики дадуть числовий ряд, елементи якого можуть бути розподілені між ребрами як завгодно.

Постановка завдання Розглянемо задачу про комівояжера.

Є n міст, відстані (вартість проїзду, витрата пального на дорогу і т.д.) між якими відомі. Комівояжер повинен пройти всі n міст по одному разу, повернувшись в те місто, з якого почав. Потрібно знайти такий маршрут руху, при якому сумарний пройдене відстань (вартість проїзду і т.д.) буде мінімальним.

Очевидно, що завдання комівояжера — це проблема віднайдення найкоротшого гамильтонова циклу в повному графі.

Можна запропонувати наступну просту схему розв’язання задачі комівояжера: згенерувати всі n! можливих перестановок вершин повного графа, підрахувати для кожної перестановки довжину маршруту і вибрати найкоротший. Однак, n! із зростанням n росте швидше, ніж будь-який поліном від n, і навіть швидше, ніж. Таким чином, рішення задачі комівояжера методом повного перебору виявляється практично нездійсненним, навіть при досить невеликих n.

Вирішити задачу комівояжера також можна за допомогою алгоритму Крускала і «дерев'яного» алгоритму. Ці методи прискорюють розробку алгоритму в порівнянні з методом повного перебору, проте не завжди дають оптимальне рішення.

Існує метод розв’язання задачі комівояжера, який дає оптимальне рішення. Цей метод називається методом гілок і меж. Рішення задачі комівояжера методом гілок і меж по-іншому називають алгоритмом Літтла.

Якщо вважати міста вершинами графа, а комунікації (i, j) — його дугами, то вимога знаходження мінімального шляху, що проходить один і тільки один раз через кожне місто, і повернення назад, можна розглядати як знаходження на графі гамильтонова контуру мінімальної довжини.

Для практичної реалізації ідеї методу гілок і меж стосовно до задачі комівояжера потрібно знайти метод визначення нижніх меж підмножини і розбиття множини гамільтонових контурів на підмножини (розгалуження).

Визначення нижніх меж базується на тому твердженні, що якщо до всіх елементів i-го рядка або j-го стовпця матриці C додати або відняти число, то завдання залишиться еквівалентної колишньою, тобто оптимальність маршруту комівояжера не зміниться, а довжина будь-якого гамильтонова контуру зміниться на дану величину .

Опишемо алгоритм Літтла для знаходження мінімального гамильтонова контуру для графа з n вершинами. Граф представляють у вигляді матриці його дуг. Якщо між вершинами Xi і Xj немає дуги, то ставиться символ «?».

Алгоритм Літтла для розв’язання задачі комівояжера можна сформулювати у вигляді наступних правил:

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

.

2. Якщо в матриці, наведеної по рядках, виявляться стовпці, що не містять нуля, то наводимо її по стовпцях. Для цього в кожному стовпці матриці вибираємо мінімальний елемент, і віднімаємо його з усіх елементів відповідного стовпця. Отримаємо матрицю

кожен рядок і стовпець, якої містить хоча б один нуль. Така матриця називається наведеної по рядках і стовпцях.

3. Підсумовуємо елементи і, отримаємо константу приведення

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

.

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

.

5. Вибираємо дугу, для якої ступінь нульового елемента досягає максимального значення

.

6. Розбиваємо безліч всіх гамільтонових контурів на дві підмножини і. Підмножина гамільтонових контурів містить дугу , — її не містить. Для отримання матриці контурів, що включають дугу, викреслюємо в матриці рядок і стовпець. Щоб не допустити утворення негамільтонова контуру, замінимо симетричний елемент на знак «?».

7. Наводимо матрицю гамільтонових контурів. Нехай — константа її приведення. Тоді нижня межа множина визначиться так:

.

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

9. Робимо приведення матриці гамільтонових контурів. Нехай — константа її приведення. Нижня межа множина визначається так:

.

10. Порівнюємо нижні множини, підмножини гамільтонових контурів і. Якщо, то подальшого розгалуження в першу чергу підлягає множина. Якщо ж, то розбиття підлягає множина .

Процес розбиття множин на підмножини супроводжується побудовою дерева розгалужень.

11. Якщо в результаті розгалужень отримуємо матрицю, то визначаємо отриманий розгалуженням гамільтонів контур і його довжину.

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

Математична модель задачі комівояжера Завдання комівояжера може бути сформульована як цілочисельна введенням булевих змінних, якщо маршрут включає переїзд з міста i безпосередньо в місто j і в іншому випадку. Тоді можна задати математичну модель задачі, тобто записати цільову функцію і систему обмежень:

(1)

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

Проте цих обмежень не достатньо для постановки задачі комівояжера, так як вони не виключають рішення, де замість простого циклу, що проходить через n вершин, відшукуються 2 і більше окремих циклу (підциклу), що проходить через менше число вершин. Тому завдання, описана рівняннями (2) — (4) повинна бути доповнена обмеженнями, що забезпечують зв’язність шуканого циклу.

Для того, щоб виключити при постановці завдання всі можливі підцикли в систему обмежень задачі включають такі обмеження:

Де, і .

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

Табл.1

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

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

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

Табл.2

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

.

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

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

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

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

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

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

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

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

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

рис.1

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

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

Табл.3

Табл.4

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

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

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

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

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

Знаходимо нижні межі,. Отже, чергового розгалуження потрібно піддати підмножина. Але його матриця має розмірність. Тому в гамільтонів контур слід включити дуги, що відповідають у матриці нульовим елементам. Це дуги (2; 1) і (4, 6).

На рис. 2 представлено дерево розгалужень. Визначимо отриманий гамільтонів контур. До нього увійшли дуги. Довжина контуру дорівнює. Так як кордони обірваних гілок більше довжини контуру 1 — 5 — 4 — 6 — 3 — 2 — 1, то цей контуру має найменшу довжину.

Рис.2

гамільтон модель задача комівояжер

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

Існують кілька методів розв’язання задачі комівояжера: метод повного перебору, за допомогою методу гілок і меж (алгоритм Літтла), алгоритму Крускала, «дерев'яного» алгоритму і т.д. Однак тільки метод гілок і меж дає нам у результаті найоптимальніше рішення.

Основна ідея методу Літтла полягає в тому, що спочатку будують нижню межу довжин маршрутів для всього безлічі гамільтонових контурів. Потім вся безліч контурів розбивають на дві підмножини таким чином, щоб перше підмножина складалося з гамільтонових контурів, містять деяку дугу (i, j), а інше підмножина не містило цієї дуги.

Для практичної реалізації ідеї методу гілок і меж стосовно до задачі комівояжера потрібно знайти метод визначення нижніх меж підмножини і розбиття множини гамільтонових контурів на підмножини (розгалуження). Таке визначення нижніх меж базується на тому твердженні, що якщо до всіх елементів i-го рядка або j-го стовпця матриці C додати або відняти число, то завдання залишиться еквівалентної колишньою, тобто оптимальність маршруту комівояжера не зміниться, а довжина будь-якого гамильтонова контуру зміниться на дану величину.

Використовуючи ЕОМ, методом гілок і меж можна вирішити задачі комівояжера для .

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

1. О. Е. Акимов «Дискретная математика. Логика, группы, графы», Москва, 2003, 376 с., ил., изд. дом «Лаборатория базовых знаний».

2. Ф. А. Новиков «Дискретная математика для программистов» С.-Петербург, 2002 г. 304 с., ил., изд. дом «Питер».

3. В. М. Бондарев «Основы программирования» 1998 г., 368 с. изд. дом «Феникс»