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

Практична реалізація задачі Гамільтона про мандрівника методом гілок та меж. Математична модель задачі комівояжера, її вирішення за допомогою алгоритму Літтла. Програмне знаходження сумарних мінімальних характеристик (відстані, вартості проїзду).
Краткое сожержание материала:

Размещено на

Размещено на

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

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

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

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

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

на тему:

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

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

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

...

ji	1	2	3	4	5	6
1	?	7	16	21	2	17
2	13	?	21	15