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

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

Дата добавления на сайт: 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 с. изд. дом «Феникс»

Комментарии:

Вы не можете оставлять комментарии. Пожалуйста, зарегистрируйтесь.