Курсова робота на тему: «МЕТОД ВІТОК І ГРАНИЦЬ В ЗАДАЧАХ ОПТИМІЗАЦІЇ»

Зміст

Вступ…………………………………………………………………………………………………………3

Розділ І. Загальний опис методу віток і границь………………………………………….5

Розділ ІІ. Задача про комівояжера………………………………………………………………7

Розділ ІІІ. Задача про рюкзак……………………………………………………………………14

Розділ IV. Задача про призначення……………………………………………………………17

Висновок………………………………………………………………………………………………….22

Література……………………………………………………………………………………………….23

Вступ

Комбінаторика – розділ математики, присвячений розв’язуванню завдань вибору і розташування елементів деякої, зазвичай скінченної множини відповідно до заданих правил.

Кожне таке правило визначає спосіб побудови деякої конструкції з елементів вихідної множини, званою комбінаторною конфігурацією. Тому можна сказати, що метою комбінаторного аналізу є вивчення комбінаторних конфігурацій. Це вивчення включає питання існування комбінаторних конфігурацій, алгоритми їх побудови, оптимізацію таких алгоритмів, а також розв’язування завдань перелічування, зокрема визначення числа конфігурацій даного класу. Простим прикладом комбінаторних конфігурацій є перестановки, комбінації і розміщення.

Великий внесок у систематичний розвиток комбінаторних методів був зроблений Г. Лейбніцем (дисертація «Комбінаторне мистецтво»), Я. Бернуллі (робота «Мистецтво припущень»), Л. Ейлером. Можна вважати, що з появою робіт Я. Бернуллі і Г. Лейбніца комбінаторні методи виділилися в самостійну частину математики. Роботи Л. Ейлера по розбиттю і композиціям натуральних чисел на доданки дали початок одному з основних методів перелічування комбінаторних конфігурацій – методу виробляючих функцій.

Повернення інтересу до комбінаторного аналізу відноситься 50-і роки ХХ ст. у зв’язку з бурхливим розвитком кібернетики і дискретної математики і широким використанням електронно-обчислювальної техніки. У цей період активізувався інтерес до класичних комбінаторних завдань.

Класичні комбінаторні завдання – це завдання вибору і розташування елементів скінченної множини, що мають як початкове деяке формулювання розважального вмісту типа головоломок.

У 1859 р. У. Гамільтон придумав гру «Кругосвітня подорож», що полягає у відшуканні такої дороги, що проходить через всі вершини (міста, пункти призначення) графа, щоб відвідати кожну вершину однократно і повернутися в початкову. Дороги, що володіють такою властивістю, називаються гамільтоновими циклами.

Задачі про гамільтонові цикли в графі отримало різні узагальнення. Одне з цих узагальнень – задача комівояжера, що має ряд вживань в дослідженні операцій, зокрема при розв’язанні деяких транспортних проблем.

Завдання роботи:

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

Мета курсової роботи – це освоєння та правильне використання методу віток і границь при розв’язуванні задач оптимізації.

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

РОЗДІЛ І. Загальний опис методу віток і границь

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

В порівнянні з методом пошуку з поверненням метод віток і границь вимагає:

  • способу отримати для кожного вузла дерева простору станів границю найкращого значення цільової функції для всіх рішень, які можуть бути отримані шляхом подальшого додавання компонентів до часткового рішення, представленого вузлом;
  • значення найкращого рішення, отриманого до цього моменту.

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

У загальному випадку завершується шлях пошуку в поточному вузлі дерева пространства станів алгоритму віток і границь по одній з трьох наступних причин.

  • Значення границі вузла не краще за значення найкращого рішення, найденного до цього моменту.
  • Вузол не представляє допустимих рішень із-за порушення обмежень, що накладаються завданням.
  • Підмножина допустимих рішень, що представляється вузлом, складається з одного елементу (отже, подальший вибір неможливий) – в цьому випадку порівнюємо значення цільової функції для цього допустимого рішення із значенням цільової функції найкращого полученного до цього моменту рішення і оновлюєм останнє теперішнім, якщо нове рішення виявляється кращим.

РОЗДІЛ ІІ.
Задача про комівояжера

Використаєм метод віток і границь, застосовуючи його до задачі комівояжера, коли комівояжер повинен вийти з першого міста, поразу відвідати в довільному порядку міста 1,2,…,6 і повернутися в перше місто.

Нехай маємо матрицю С розміром 6×6, кожен елемент якої Cij дорівнює вартості прямого проїзду з міста i в місто j, де вартість проїзду з міста i прямо в місто j не обов’язково така ж, як вартість проїзду з міста j в місто i. Безкінечності по діагоналі означають, що з міста i в місто i ходити не можна.

С =

6

4

8

7

14

6

7

11

7

10

4

7

4

3

10

8

11

4

5

11

7

7

3

5

7

14

10

10

11

7

Для алгоритму нам буде зручно отримати більше нулів в матриці С, не отримуючи там негативних чисел. Скористаємося таким правилом: віднімаючи будь-яку константу зі всіх елементів будь-якого рядка або стовпця матриці, ми залишаємо мінімальний тур мінімальним. Отже зафіксуємо в кожному рядку мінімальний елемент, а потім віднімемо його з кожного рядка.

ЗАВАНТАЖИТИ

Для скачування файлів необхідно або Зареєструватись

Metod Vitok I Gr V Z Opt (317.0 KiB, Завантажень: 4)

Сторінка: 1 2 3 4
завантаження...
WordPress: 23.46MB | MySQL:26 | 0,538sec