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

Міністерство освіти і науки, молоді та спорту України Вінницький національний технічний університет

Інститут автоматики, електроніки та комп’ютерних систем управління Кафедра КСУ Напрям «Системна інженерія» 08−01.МП та ДО.031.00.000 ПЗ Пояснювальна записка до курсової роботи з дисципліни «Математичне програмування та дослідження операцій»

Тема: «Розв'язок задач лінійного програмування»

Керівник курсової роботи к.т.н., доцент Ковтун В.В.

Розробив студент гр. 1СІ-09

Титарчук Є.О.

Вінниця — 2011

Індивідуальне завдання на виконання курсової роботи на тему: «Розв'язання задач лінійного програмування»

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

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

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

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

1. Розробити математичну модель.

2. Обрати спосіб вирішення поставленої задачі.

3. Розробити алгоритм рішення.

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

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

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

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.

ЗМІСТ

• ВСТУП
• 1. ОГЛЯД ТА ВАРІАНТНИЙ АНАЛІЗ СУЧАСНИХ МЕТОДІВ МАТЕМАТИЧНОГО ПРОГРАМУВАННЯ ДЛЯ ДОСЛІДЖЕННЯ ОПЕРАЦІЙ
• 1.1 Класифікація задач дослідження операцій (ДО)
• 1.2 Методи розв’язання задачі комівояжера
• 1.3 Вибір методу розв’язання транспортної задачі
• 1.4 Аналіз об'єкту дослідження
• 1.5 Вибір середовища програмування
• 2. РОЗРОБКА АЛГОРИТМІЧНОГО ЗАБЕЗПЕЧЕННЯ
• 3. ПРОЕКТУВАННЯ ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ НА МОВІ UML
• 4. РОЗРОБКА ТЕСТІВ
• 5. РОЗРОБКА ДОКУМЕНТІВ ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ
• 5.1 Інструкція програмісту
• 5.2 Інструкція користувачеві
• ВИСНОВКИ
• ЛІТЕРАТУРА
• ДОДАТКИ

ВСТУП

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

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

Задача комівояжера (комівояжер — бродячий торговець; англ. 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 що задовольняє описаним вище лінійним нерівностям. Гіперплощини, що описуються цими нерівностями відсікають такі ребра одиничного куба, що не відповідають жодному маршруту.

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

Для визначення нижньої межі користуються операцією редукції або приведення матриці по рядках, для чого необхідно в кожному рядку матриці D знайти мінімальний елемент. Маючи нижню границю для оптимальних розв’язків можна оцінити те, наскільки відрізняється знайдений маршрут від оптимального. Наприклад, маючи нижню границю на рівні 100, та після знаходження маршруту вартістю 102, оптимальний маршрут може знаходитись в межах від 100 до 102. Так званий інтервал оптимальності, або максимальна відносна відстань між вартістю оптимального маршруту та найдешевшим відомим маршрутом становитиме (102—100)/100 = 2%, тобто вартість знайденого маршруту 102 щонайбільше на 2% відрізняється від оптимальної. Коли вартість обчисленого маршруту дорівнює вартості попереднього, вважається, що знайдений розв’язок є оптимальним. Для пошуку маршрутів прийнятної довжини точні методи можуть комбінуватись з евристичними, деякі з них описано нижче.

Генетичний алгоритм

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

Особливістю генетичного алгоритму є акцент на використання оператора «схрещення», який виконує операцію рекомбінацію рішень-кандидатів, роль якої аналогічна ролі схрещення в живій природі.

Задача кодується таким чином, щоб її вирішення могло бути представлено в вигляді масиву подібного до інформації складу хромосоми. Цей масив часто називають саме так «хромосома». Випадковим чином в масиві створюється деяка кількість початкових елементів «осіб», або початкова популяція. Особи оцінюються з використанням функції пристосування, в результаті якої кожній особі присвоюється певне значення пристосованості, яке визначає можливість виживання особи. Після цього з використанням отриманих значень пристосованості вибираються особи допущені до схрещення (селекція). До осіб застосовується «генетичні оператори» (в більшості випадків це оператор схрещення (crossover) і оператор мутації (mutation), створюючи таким чином наступне покоління осіб. Особи наступного покоління також оцінюються застосуванням генетичних операторів і виконується селекція і мутація. Так моделюється еволюційний процес, що продовжується декілька життєвих циклів (поколінь), поки не буде виконано критерій зупинки алгоритму. Таким критерієм може бути:

— Знаходження глобального, або над оптимального вирішення.

— Вичерпання числа поколінь, що відпущені на еволюцію.

— Вичерпання часу, відпущеного на еволюцію.

Можна виділити такі етапи генетичного алгоритму:

— Створення початкової популяції.

— Обчислення функції пристосованості для осіб популяції (оцінювання).

— Повторювання до виконання критерію зупинки алгоритму:

· вибір індивідів із поточної популяції (селекція);

· схрещення або/та мутація;

· обчислення функції пристосовуваності для всіх осіб;

· формування нового покоління.

Генетичні алгоритми можуть використатися для пошуку рішень в дуже великих і тяжких просторах пошуку.

Метод найближчого сусіда

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

Формулюється таким чином:

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

Алгоритм простий в реалізації, швидко виконується, але, як і інші «жадібні» алгоритми, може видавати неоптимальні рішення. Одним з евристичних критеріїв оцінки рішення є правило: якщо шлях, пройдений на останніх кроках алгоритму, порівняємо з шляхом, пройденим на початкових кроках, то можна умовно вважати знайдений маршрут прийнятним, інакше, імовірно, існують більш оптимальні рішення. Інший варіант оцінки рішення полягає у використанні алгоритму нижньої граничної оцінки.

Для будь-якої кількості міст більшого за три в задачі комівояжера можна підібрати таке розташування міст (значення відстаней між вершинами графа і вказівка початкової вершини), що алгоритм найближчого сусіда буде видавати найгірше рішення

Алгоритм розв’язання транспортної задачі.

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

1. Сформувати матрицю відстаней між містами;

2. За обраним алгоритмом знайти список міст через які повинен пройти комівояжер.

3. Потрібно знайти мінімальну відстань у стрічці що відповідає початковому місту.

4. Номер стовпчика в якому знайдено мінімальний елемент відповідатиме наступному місту в яке повинен потрапити комівояжер.

5. В циклі переходимо між містами доки кількість переходів не стане рівна кількості міст.

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

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

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

Дано п’ять міст України:

· Вінниця

· Київ

· Тернопіль

· Рівне

· Черкаси

Карта з найкоротшими відстанями (таблиця 1) при подорожі автомобілем можна побачити в додатку Г (отримані за допомогою сервісу Google maps).

Таблиця 1

Відстані між містами (км)

На рисунку 1.1 наведено інтерпретацію цієї задачі у формі графу.

Рисунок 1.1 — Граф задачі

Необхідно знайти найкоротший маршрут що проходить через кожне з даних міст.

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

Програма у даній курсовій роботі розроблена в середовищі Visual Studio 2010 на мові C# з платформою Microsoft .NET. C# вибраний через надзвичайну безпечність та простоту коду, технологія .NET значно зменшує зменшує час розробки програми.

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

Створимо програму вирішення задачі комівояжера за наступним алгоритмом (рисунок 2.1)

Рисунок 2.1 — Алгоритм розробки програми для розв’язку задачі

Для вирішення задачі створимо два класи. Перший, клас Form1, наслідує базовий клас Form і необхідний для реалізації користувацького інтерфейсу (рисунок 2.2, лістинг класу знаходиться в додатку Б). Другий клас, GreedyAlgorithm, потрібен для розв’язання задачі комівояжера жадібним алгоритмом (метод найближчого сусіда).

В класі Form1 є функція InputCountOfTown яка реагує на подію введення тексту у TextBox. Після введення створюється двовимірний масив текст-боксів з якого за допомогою функції CreatMatrix буде сформована таблиця відстаней між містами.

Рисунок 2.2 — Інтерфейс програми

Функція CreatMatrix у циклі створює екземпляри функції CreateNewRow кожна з яких створює рядок текст-боксів і додає їх на фурму за допомогою системного методу Invoke.

При кожному введенні значення у один з текст-боксів таблички за допомогою системного делегата викликається функція TextChange. У даній функції в циклі опитуються всі текст-бокси таблиці, і якщо в поле введене якесь значення то воно переноситься у масив відстаней. При неправильному введенні з’являється повідомлення (рисунок 2.3), а помилкове значення стирається для повторного введення.

Рисунок 2.3 — Повідомлення про помилку

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

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

Отже, ми коротко розглянемо такі види діаграм, як:

— діаграма класів;

— діаграма об'єктів;

— діаграма послідовностей;

— діаграма взаємодії;

— діаграма станів;

— діаграма активності;

— діаграма розгортання.

Прецедент (use-case) — опис окремого аспекту поведінки системи з точки зору користувача .

Прецедент (use case) — опис множини послідовних подій (включаючи варіанти), що виконуються системою, які призводять до результату, який спостерігає актор. Прецедент представляє поведінку сутності, описуючи взаємодію між акторами і системою. Прецедент не показує, «як» досягається деякий результат, а тільки що" саме виконується.

UML-діаграма прецедентів програмного комплексу розв’язання задачі комівояжера зображена на рисунку 3.3

UML-діаграма об`єктів зображена на рисунку 3.1.

Рисунок 3.1 — UML-діаграма об`єктів

UML-діаграма взаємодії зображена на рисунку 3.2.

Рисунок 3.2 — UML-діаграма взаємодії

Рисунок 3.3 — UML-діаграма прецедентів

UML-діаграма класів зображена на рисунку 3.4.

Рисунок 3.4 — UML-діаграма класів

UML-діаграма активності зображена на рисунку 3.5.

Рисунок 3.5 — UML-діаграма активності

UML-діаграма станів зображена на рисунку 3.6.

Рисунок 3.6 — UML-діаграма станів

UML-діаграма послідовностей зображена на рисунку 3.7.

Рисунок 3.7 — UML-діаграма послідовностей

UML-діаграма розгортання зображена на рисунку 3.8.

Рисунок 3.8 — UML-діаграма розгортання Всі діаграми виконані згідно з технічним завданням та дотриманням ГОСТів.

цілочисельний програмний транспортний задача

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

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

Занесемо дані задачі в матрицю відстаней (таблиця 4.1):

Таблиця 4.1

Матриця відстаней між містами

За початкове місто візьмемо місто 1 (Вінниця), а шлях спочатку рівен 0.

Знайдемо в стрічці яка відповідає місту 1 найменше число:

235 знаходиться на третій позиції в стрічці а отже найближче до Вінниці з наведених міст — Тернопіль. Тому місто 3 наступне в нашому маршруті. Аналогічно знаходимо інші міста в маршруті (таблиця 4.2).

Таблиця 4.2

Таблиця з відстанями маршруту

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

Вінниця -> Тернопіль -> Рівне -> Київ -> Черкаси -> Вінниця Або якщо користуватися номерами міст:

1 -> 3-> 4 -> 2 -> 5 -> 1

Додавши всі шляхи між містами отримаємо оптимальний шлях 1235 км.

Розв’яжемо тепер цю задачу за допомогою програми.

Результати на рисунку 4.1.

Рисунок 4.1 — Результат роботи програми Як видно з рисунків рішення задачі на ЕОМ повність співпадає з розв’язком задачі вручну. Це означає, що дана задача була розв’язана вірно та кінцевий шлях є оптимальним для даної умови. Тобто відстань яку потрібно проїхати комівояжеру при подорожі між даними містами становить 1235 кілометрів.

Для перевірки правильності роботи програми проведемо ще один тест

1. Умова задачі (таблиця 4.3)

Таблиця 4.3

Умова задачі

Таблиця 4.4

Розв’язок задачі

Оптимальний шлях пролягатиме через:

1 -> 2 -> 8 -> 3 -> 4 -> 6 -> 7 -> 5 -> 1

S = 1 + 1 + 1 + 1 + 1 + 1 + 3 + 3 = 12

Програма після введення даних (таблиця 4.3) вивела наступні результати (рисунок 4.2)

Рисунок 4.2 — Програмні результати розв’язку задачі

Розв’язки задачі однакові.

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

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

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

Розроблений комплекс програм призначений для розв’язання задачі комівояжера. Завданням програми є обчислення мінімального шляху між містами. Для експлуатації даної програми необхідно мати у програмному забезпеченні комп’ютера .NET Framework 4.0 який можна легко завантажити з офіційного сайту Microsoft.

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

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

Для обрахування задачі комівояжера, запускаємо файл CourseWork. exe і поле зверху вікна ввести кількість міст, а потім у таблицю, що з’явиться ввести відстані між містами та натиснути кнопку щоб отримати рішення.

ВИСНОВКИ

В роботі було наведено аналіз сучасних методів математичного програмування та дослідження операцій. Були розглянуті основні методи розв’язання задачі комівояжера та розроблена програма що розв’язує задачу за методом найближчого сусіда.

Для програми були розроблені UMLдіаграми та блок-схема алгоритму, а також інструкція користувачу та програмісту.

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

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

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

ЛІТЕРАТУРА

1. Бугір М.К., Якімов Ф.П. «Посібник для розв’язування задач з математичного програмування» — Тернопіль, 1996. — 200 c.

2. Вивальнюк Л. Н. «Елементи лінійного програмування» — Київ: Вища школа, 1975. — 356 с.

3. Кузнецов Ю. Н., Козубов В. И., Волощенко А. Б. Математическое програмирование. — М.: Высш. Шк., 1976.

4. Нортроп Т., Уилдермьюс Ш., Райан Б. Основы разработки приложений на платформе Microsoft .NET Framework. Учебный курс Microsoft / Пер. с англ. — М.: «Русская редакция», СПб.: «Питер», 2007. — 864 с.

5. Цегелик Г. Г. «Лінійне програмування» — Львів: Світ, 1995; 150 c.

6. Кузнєцов Ю.Н., Кузубов В. И., Волощенко А. Б. «Математическое программирование» — Москва: Высшая школа, 1980 — 600 c.

7. Калихман И. Л. Линейная алгебра и программирование. М.: Высш. Шк., 1967

8. Кюнци Г. П., Крелле В. Нелинейное программирование. — М.: Сов. Радио, 1965

9. Большакова И. В., Кураленко М. В. Линейное программирование — М.: Высшая школа, 2004. — 148 с.

10. Вагнер Г. П. Основы исследования операций — М.: Мир, 1972;1973. -336 с.

11. Ковтун В. В. «Конспект лекцій по математичному програмуванні і дослідженні операцій «- Вінниця 2008.

12. Москвіна С.М., Дубіненко С.Б., Перевозніков С.І Методичні вказівки до лабораторних робіт з курсу «Обчислювальні методи та застосування на ЕОМ» ч. І - Вінниця: ВПІ, 1992.

ДОДАТОК А

ТЕХНІЧНЕ ЗАВДАННЯ на виконання курсової роботи

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

Найменування продукту, що розробляється: програмне забезпечення розв’язання задачі комівояжера

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

Підстава для розробки продукту:

Навчальний план спеціальності 6.91 400 — системи управління і автоматики.

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

Індивідуальне завдання на курсову роботу

Вимоги до програмного продукту:

Операційна система — WINDOWS.

Середовище програмування — довільне Необхідний об'єм пам’яті - не менше 64 MB

ПЗ необхідно протестувати та зробити висновки щодо придатності його до використання.

Все програмне забезпечення та супроводжуюча технічна документація повинні задовольняти наступним ГОСТам:

ГОСТ 19.701−90

ИСО 5807−85 — ГОСТ на розробку програмних документів, схеми алгоритмів програм, даних та системи.

ГОСТ 19.781−74 — вимоги до розробки програмного забезпечення ГОСТ 19.101−77 (СТ СЭВ 1626−79) — держстандарт на розробку програмної документації, видів програм та програмних документів.

ГОСТ 19.401−78 — Текст програми. Вимоги до змісту та оформлення.

ГОСТ 19.106−78 — вимоги до програмної документації.

ГОСТ 7.1.-84 та ДСТУ 3008−95 — розробка технічної документації.

Етапи розробки:

Класифікація типу задачі

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

Вибір методів розв’язання задачі

Розробка алгоритмів обраних методів Програмна реалізація Тестування Висновки по роботі

Порядок контролю та приймання курсової роботи:

Отримання завдання на виконання курсової роботи Термін здачі курсової роботи на перевірку Термін захисту курсової роботи

ДОДАТОК Б

Лістинг програми, клас Form1

using System;

using System.Collections.Generic;

using System.Windows.Forms;

using System. Threading;

namespace CourseWork

{

public partial class Form1: Form

{

private int[][] A;

private TextBox[][] tbA;

private int _n;

private int _oldN;

private bool _alreadyExists;

private bool _ready;

public Form1()

{

InitializeComponent ();

}

private void InputCountOfTown (object sender, EventArgs e)

{

_n = Convert. ToInt32(tbCount.Text);

if (_n > 50)

{

_n = 50;

}

progressBar.Maximum = _n*_n;

progressBar.Value = 0;

progressBar.Visible = true;

if (_alreadyExists)

{

DeleteMatrix ();

}

CreatMatrix ();

_oldN = _n;

_alreadyExists = true;

}

private void DeleteMatrix ()

{

for (int i = 0; i < _oldN; i++)

{

for (int j = 0; j < _oldN; j++)

{

tbA[i][j]. Dispose ();

}

}

Panel.Invalidate ();

}

private void CreatMatrix ()

{

var thread = new Thread[_n];

int i;

A = new int[_n][];

for (i=0;i<_n;i++)

A[i] = new int[_n];

tbA = new TextBox[_n][];

for (i = 0; i < _n; i++)

{

tbA[i] = new TextBox[_n];

thread[i] = new Thread (CreateNewRow);

thread[i]. Start (i);

}

}

private void CreateNewRow (object obj)

{

int i = (int) obj;

int j;

for (j = 0; j < _n; j++)

{

tbA[i][j] = new TextBox ();

tbA[i][j]. Width = 40;

tbA[i][j]. Left = 5 + j * 40;

tbA[i][j]. Top = 5 + i * 20;

tbA[i][j]. Visible = true;

if (i ≠ j)

{

tbA[i][j]. TextChanged += TextChange;

}

else

{

tbA[i][j]. Text = @" -" ;

tbA[i][j]. Enabled = false;

}

Panel.Invoke (new MethodInvoker (()=>{Panel.Controls.Add (tbA[i][j]);}));

progressBar.Invoke (new MethodInvoker (()=>{progressBar.Value += 1; }));

}

}

private void TextChange (object sender, EventArgs e)

{

_ready = true;

for (int i = 0; i < _n; i++)

{

for (int j = 0; j < _n; j++)

{

if (i == j)

{

tbA[i][j]. Text = @" -" ;

A[i][j] = 1 000 000;

}

else

{

if (tbA[i][j]. Text ≠ String. Empty)

{

try

{

A[i][j] = Convert. ToInt32(tbA[i][j]. Text);

}

catch

{

MessageBox.Show (@" Невірний формат введення");

tbA[i][j]. Text = «» ;

}

}

}

if (tbA[i][j]. Text == «»)

{

_ready = false;

}

}

}

}

private void ButtonClick (object sender, EventArgs e)

{

if (_ready)

{

var greedyAlgorithm = new GreedyAlgorithm (A);

List list = greedyAlgorithm. Answer ();

int sum = 0;

int prev = 0;

textBox2.Text = @" 1 -> «;

for (int i = 0; i < _n; i++)

{

textBox2.Text += (list[i] + 1).ToString ();

if (i ≠ _n — 1)

{

textBox2.Text += @" -> «;

}

sum += A[prev][list[i]];

prev = list[i];

}

tbSum.Text = sum. ToString ();

}

else

{

MessageBox.Show (@" Потрібно заповнити всю матрицю");

}

}

}

}

ДОДАТОК В

Лістинг програми, клас GreedyAlgorithm

using System.Collections.Generic;

namespace CourseWork

{

class GreedyAlgorithm

{

private int[][] A;

private int[] column;

private int N;

private List AnswerList;

public GreedyAlgorithm (int[][] matrix)

{

A = matrix;

N = matrix. Length;

column = new int[N];

AnswerList = new List ();

}

public List Answer ()

{

int j;

int s = 0;

for (int i = 0; i < N; i++)

{

j = MinInS (s);

s = j;

}

return AnswerList;

}

private int MinInS (int i)

{

int min = 1 000 000;

int nextPoint = 0;

for (int j=0;j

{

if (A[i][j] < min)

{

if (column[j] ≠ 1)

{

min = A[i][j];

nextPoint = j;

}

}

}

AnswerList.Add (nextPoint);

column[i] = 1;

return nextPoint;

}

}

}

ДОДАТОК Г

Карта