Міністерство внутрішніх справ України
Харківський національний університет внутрішніх справ
ННІ психології, менеджменту, СОЦІАЛЬНИХ та інформаційних технологій
Курсова робота з дисципліни:
«Вища математика»
на тему:
Метод гілок та меж для решение задач цілочісельного программирования
Виконала: курсант групи
ІПТ - 09-2 Руденко С.В.
Перевірів: доцент кафедри ПМ та
аналітичного забезпечення ОВС
Соколовська О.Г.
Харків 2011
План
Вступ
Постановка задачі
Математична модель задачі комівояжера
Алгоритм решение
Висновки
Список використаної літератури
Вступ
У +1859 р. Сер Вільям Гамільтон, знаменитий математик, Який давши світу теорію комплексного числа и кватерніоні, предложили дитячу головоломку, в Якій пропонувалося здійсніті «кругову подорож» по 20 містах, розташованіх у різніх Частинами земної Кулі. Кожне місто з єднувався дорогами з трьома сусіднімі так, что дорожня мережа утворювала 30 ребер додекаедра, у вершинах которого знаходиься міста a, b, ... t. Обов язковою умів Було Вимога: шкірний місто за вінятком Першого можна відвідаті один раз.
Гамильтонова Завдання про мандрівника нерідко превращается в задачу про комівояжера. Комівояжер - НЕ вільно Мандрівний турист, а ділова людина, ограниченной Тимчасовими, грошовими або будь-Якими іншімі ресурсами. Гамильтонова Завдання может стать Завдання про комівояжера, если Кожне з ребер Забезпечити числові характеристики. Це может буті кілометраж, годину на дорогу, ВАРТІСТЬ квитка, витрати пального и т.д. Таким чином, Умовні характеристики дадуть числовий ряд, елементи которого могут буті розподілені между ребрами як завгодно.
Постановка Завдання
Розглянемо задачу про комівояжера.
Є n міст, відстані (ВАРТІСТЬ проїзду, витрати пального на дорогу и т.д.) между Якими відомі. Комівояжер винен пройти всі n міст по одному разу, повернувшись в ті місто, з которого почав. Потрібно найти такий маршрут руху, при якому сумарная пройдений відстань (ВАРТІСТЬ проїзду и т.д.) буде мінімальнім.
Очевидно, что Завдання комівояжера - це проблема віднайдення найкоротшого гамільтонова циклу в ПОВНЕ графі.
Можна Запропонувати Наступний просту схему розв'язання задачі комівояжера: згенеруваті всі n! МОЖЛИВИЙ перестановок вершин полного графа, підрахуваті для кожної перестановки Довжину маршруту и ??вібрато найкоротшій. Однак, n! Із зростанням n зростанні швидше, чем будь-який поліном від n, и даже швидше, чем. Таким чином, решение задачі комівояжера методом полного перебору віявляється практично нездійсненнім, даже при й достатньо невеликих n.
Вірішіті задачу комівояжера такоже можна помощью алгоритмом Крускала и «дерев'яного» алгоритмом. ЦІ методи пріскорюють розробка алгоритму в порівнянні з методом полного перебору, вже не проти всегда дають оптімальне решение.
Існує метод розв'язання задачі комівояжера, Який дает оптімальне решение. Цей метод назівається методом гілок и між. Рішення задачі комівояжера методом гілок и між по-ІНШОМУ назівають алгоритмом Літтла.
Если вважаті міста вершинами графа, а комунікації (i, j) - его дугами, то Вимога знаходження мінімального шляху, что проходити одна и только один раз через шкірні місто, и повернення назад, можна розглядаті як знаходження на графі гамільтонова контуру мінімальної Довжину.
Для практичної реализации Ідеї методу гілок и між Стосовно до задачі комівояжера нужно найти метод визначення ніжніх між підмножіні и розбіття множини гамільтоновіх контурів на підмножіні (розгалуження).
Визначення ніжніх між базується на тому твердженні, что если до всіх елементів i-го рядка або j-го стовпця матриці C Додати або відняті число, то Завдання залиша еквівалентної КОЛІШНИЙ, тобто оптімальність маршрутом комівояжера НЕ змініться, а довжина будь-которого гамільтонова контуру змініться на Дану величину.
Опішемо алгоритм Літтла для знаходження мінімального гамільтонова контуру для графа з n вершинами. Граф представляються у виде матриці его дуг. Если между вершинами Xi и Xj немає дуги, то ставитиметься символ «?».
Алгоритм Літтла для розв'язання задачі комівояжера можна сформулюваті у виде Наступний правил:
. Знаходімо в шкірному рядку матриці мінімальній елемент и відніма...
