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

Міністерство  освіти і науки, молоді та спорту України

Вінницький  національний технічний університет

Інститут  автоматики, електроніки та комп’ютерних систем  управління

 

                                                                                        Кафедра КСУ

 

 

 

Розв’язок задач лінійного програмування

 

Пояснювальна  записка

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

до курсової роботи за напрямом

“Системна інженерія”

08-01.МПтаДО.031.00.000 ПЗ

 

 

 

        Керівник курсової роботи

           к.т.н., доцент Ковтун В.В.

”___” ____________2011 р.

 

                                                                           Розробив студент гр. 1СІ-09      Титарчук Є.О.

”___” ____________2011 р.

 

 

 

 

Вінниця ВНТУ 2011

Міністерство освіти і науки, молоді та спорту України

Вінницький  національний технічний університет

Інститут  автоматики, електроніки та комп’ютерних систем управління

 

ЗАТВЕРДЖУЮ

Зав. кафедри  КСУ проф, д.т.н.

_____________ В.М.  Дубовой

«____»______________2011р.

 

 

 

ІНДИВІДУАЛЬНЕ ЗАВДАННЯ

на  виконання  курсової роботи

на  тему:

”Розв’язання  задач лінійного програмування. ”

з дисципліни „ Математичне програмування  та дослідження операцій ”

студента  гр. 1СІ-09 Титарчук Є.О.

 

Розробка  програмного комплексу для розв’язання  задачі цілочисельного програмування  типу «Задача комівояжера»

 

Для розв’язання  задачі необхідно:

1. Розробити математичну модель.
2. Обрати спосіб вирішення поставленої задачі.
3. Розробити алгоритм рішення.
4. Розробити програмне забезпечення щодо вирішення поставленої задачі.

 

Дата видачі «___»_________ 2011р.       Керівник ________Ковтун В.В.

                                                                                                  

                                                                        Завдання отримав____________

 

АНОТАЦІЯ

В представленій курсовій роботі розроблено програмний комплекс для розв’язання задачі цілочисельного програмування типу «Задача комівояжера». Для підтвердження правильності роботи програми, результати виконання порівняно з результатами розв’язування задачі ручним методом.

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

 

 

 

 

 

 

 

ABSTRACT

In the presented course work developed software system for solving integer programming problems such as "Traveling Salesman Problem.". For validation of the functioning the program, the results of the execution relatively with result of the decision of the task by manual method.

Also, the term paper contains the mathematical model of the transport task and methods, which exist for her decisions.

 

 

 

 

 

 

 

 

 

 

ЗМІСТ

ВСТУП 5

1 ОГЛЯД ТА ВАРІАНТНИЙ АНАЛІЗ  СУЧАСНИХ МЕТОДІВ МАТЕМАТИЧНОГО  ПРОГРАМУВАННЯ ДЛЯ ДОСЛІДЖЕННЯ  ОПЕРАЦІЙ 7

1.1 Класифікація задач дослідження  операцій (ДО) 7

1.2 Методи розв’язання задачі комівояжера 9

1.3 Вибір методу розв’язання  транспортної задачі 13

1.4 Аналіз об’єкту дослідження 13

1.5 Вибір середовища програмування 14

2 РОЗРОБКА АЛГОРИТМІЧНОГО ЗАБЕЗПЕЧЕННЯ 15

3 ПРОЕКТУВАННЯ ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ НА МОВІ UML 18

4 РОЗРОБКА ТЕСТІВ 24

5 РОЗРОБКА ДОКУМЕНТІВ ПРОГРАМНОГО  ЗАБЕЗПЕЧЕННЯ 28

5.1  Інструкція програмісту 28

5.2  Інструкція користувачеві 28

ВИСНОВКИ 29

ЛІТЕРАТУРА 30

ДОДАТКИ 31

Додаток А. Технічне завдання 32

Додаток Б. Лістинг інтерфейсу 34

Додаток В. Лістинг розв'язку 37

Додаток Г. Схема 38

 

 

 

 

ВСТУП

 

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

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

Задача  комівояжера (комівояжер — бродячий торговець; англ. Travelling Salesman Problem, TSP) є  оптимізаційною задачею, що часто виникає  на практиці і полягає у знаходженні  найвигіднішого маршруту, що проходить  через вказані міста хоча б  по одному разу. В умовах завдання вказуються критерій вигідності маршруту (найкоротший, найдешевший, сукупний критерій тощо) і відповідні матриці відстаней, вартості тощо. Зазвичай задано, що маршрут  повинен проходити через кожне  місто тільки один раз, в такому випадку  розв'язок знаходиться серед гамільтонових  циклів.

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

Прості  методи розв'язання задачі комівояжера: повний лексичний перебір, жадібні  алгоритми (метод найближчого сусіда), метод включення найближчого  міста, метод найдешевшого включення), метод мінімального кістяка дерева. На практиці застосовують різні модифікації  ефективніших методів: метод гілок  і меж і метод генетичних алгоритмів, а так само алгоритм мурашиної  колонії.

Всі ефективні (такі, що скорочують повний перебір) методи розв'язання задачі комівояжера —  евристичні. У більшості евристичних  методів знаходиться не найефективніший  маршрут, а наближений розв'язок. Користуються популярністю так звані any-time алгоритми, тобто алгоритми, що поступово покращують деякий поточний наближений розв'язок.

Оскільки  комівояжер в кожному з міст постає перед вибором наступного міста  з тих, що він ще не відвідав, існує (n − 1)! маршрутів для асиметричної та (n − 1)! / 2 маршрутів для симетричної  задачі комівояжера. Таким чином, розмір простору пошуку залежить над-експоненційно  від кількості міст.

Задача  комівояжера — NP-повна. Для NP-повних задач не відомо кращого методу рішення, ніж повний перебір всіх можливих варіантів, і, на думку більшості  математиків, малоймовірно, щоб кращий метод був колись знайдений. Оскільки такий повний пошук практично  нездійсненний для великого числа  міст, то евристичні методи використовуються для знаходження прийнятних, хоч  і неоптимальних рішень. Часто  на ній проводять випробування нових  підходів до евристичного скорочення повного перебору.

 

 

 

1 ОГЛЯД ТА ВАРІАНТНИЙ АНАЛІЗ СУЧАСНИХ МЕТОДІВ МАТЕМАТИЧНОГО ПРОГРАМУВАННЯ ДЛЯ ДОСЛІДЖЕННЯ ОПЕРАЦІЙ

1.1 Класифікація  задач дослідження операцій (ДО)

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

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

Метою дослідження  операцій є кількісне обґрунтування  рішень, які приймаються для управління організаційною системою.

Основні етапи дослідження операцій:

1. Постановка задачі (результатом є словесна постановка)
2. Побудова математичної моделі

                                                            – цільова стрічка

                                                                     –  обмеження

де: – функція і-го аргументу

       – величина і-го ресурсу

        – вектор керованих змін

      – вектор не керованих змін

3. Перевірка та корегування математичної моделі
4. Реалізація знайденого розв’язку

Типовий клас задач дослідження операцій

1. Управління запасами
2. Задачі розподілу ресурсів
3. Задачі ремонту і заміни даних
4. Задачі масового обслуговування
5. Задачі впорядкування
6. Задачі мережевого планування, управління, вибору маршруту
7. Комбіновані методи

Особливості типових задач

Задачі  управління запасами:

Зі збільшенням  кількості запасів збільшення витрат на їх зберігання, але зменшуються  можливі витрати через їх нестачу.

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

Три задачі управління запасами:

1. Моменти постачань або оформлення замовлень – фіксовані. Необхідно визначити обсяг поставок та виготовленої продукції.
2. Обсяги поставок – фіксовані. Необхідно визначити моменти оформлення замовлень.
3. Моменти оформлення замовлень та обсяги поставок – не фіксовані.

Розв’язати задачу дослідження  операцій з метою максимізації певного  якісного показника.

Задача розподілу ресурсів

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

Постановка задачі

1. Задано роботу і ресурси. Визначити, яку кількість робіт можна виконати   з наявними ресурсами для максимізації робіт.
2. Задані лише ресурси. Визначити, які роботи можна з ними виконати для максимізації прибутку.
3. Задані роботи. Потрібно визначити, які ресурси необхідні для максимізації прибутку.

Задачі ремонту та заміни обладнання

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

Задачі масового обслуговування

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

Задачі впорядкування

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

Задача управління маршрутом

Задача управління маршрутом  полягає у визначенні найбільш ефективного  маршруту для економії певного ресурсу  за умови необхідності відвідування кожної з точок маршруту. 

1.2 Методи розв’язання задачі комівояжера

 

Відомі  методи розв'язання поділяють на дві  групи, що можна комбінувати. Точні  методи знаходять, маючи достатньо  часу, гарантовано оптимальний шлях. Евристичні методи знаходять, часто  за коротший час, гарні розв'язки, що, в загальному випадку, можуть бути гіршими  за оптимальні. Для метричної задачі існують евристики, що знаходять  за поліноміальний час розв'язки гірші  за оптимальні у 1.5—2 рази.:

Метод гілок і меж

Можна знайти точний розв'язок задачі комівояжера, тобто, обчислити довжини всіх можливих маршрутів та обрати маршрут з  найменшою довжиною. Однак, навіть для  невеликої кількості міст в такий  спосіб задача практично нерозв'язна. Для простого варіанта, симетричної  задачі з n містами, існує (n − 1)! / 2 можливих маршрутів, тобто, для 15 міст існує 43 мільярдів  маршрутів та для 18 міст вже 177 більйонів. Те, як стрімко зростає тривалість обчислень можна показати в наступному прикладі. Якщо існував би пристрій, що знаходив би розв'язок для 30 міст за годину, то для для двох додаткових міст в тисячу раз більше часу; тобто, більш ніж 40 діб.

 Методи  дискретної оптимізації, зокрема  гілок і меж дозволяють знаходити  оптимальні або приблизні розв'язки  для достатньо великих задач.

В геометричній інтерпретації, ці методи розглядають  задачу як опуклий політоп, тобто, багатовимірний багатокутник в m-вимірному одиничному кубі [0,1]m, де m дорівнює кількості ребер  в графі. Кожне ребро цього  одиничного куба відповідає маршруту, тобто, вектору з елементами 0/1 що задовольняє описаним вище лінійним нерівностям. Гіперплощини, що описуються цими нерівностями відсікають такі ребра  одиничного куба, що не відповідають жодному  маршруту.