Розв’язок задач лінійного програмування - Курсовая работа

Лінійне програмування є одним з важливих розділів дослідження операцій і зводиться до оптимізації лінійної цільової функції на множині, яка описується лінійними рівняннями і нерівностями. Серед спеціальних задач на практиці найчастіше зустрічається так звана задача комівояжера і різні її модифікації та узагальнення. Travelling Salesman Problem, TSP) є оптимізаційною задачею, що часто виникає на практиці і полягає у знаходженні найвигіднішого маршруту, що проходить через вказані міста хоча б по одному разу. В умовах завдання вказуються критерій вигідності маршруту (найкоротший, найдешевший, сукупний критерій тощо) і відповідні матриці відстаней, вартості тощо. Існує маса різновидів узагальненої постановки задачі, зокрема геометрична задача комівояжера (коли матриця відстаней відображає відстані між точками на площині), трикутна задача комівояжера (коли на матриці вартостей виконується нерівність трикутника), симетрична та асиметрична задачі комівояжера.Дослідження операцій (ДО) - наука, яка займається розробкою та практичним застосуванням методів найбільш ефективного або оптимального управління організацією системи. Предметом виступають системи управління організації, які складаються з великої кількості взаємодіючих підрозділів, причому між цими підрозділами інтереси не співпадають. Метою дослідження операцій є кількісне обґрунтування рішень, які приймаються для управління організаційною системою. Отже задачі дослідження операцій є визначенням кількості запасів, коли виникає баланс між кількістю запасів та ризиком їх нестачі. Ці задачі виникають, коли необхідно розподілити обмежену кількість ресурсів серед обмеженої кількості робіт з метою максимізації показника роботи системи.Точні методи знаходять, маючи достатньо часу, гарантовано оптимальний шлях. Можна знайти точний розвязок задачі комівояжера, тобто, обчислити довжини всіх можливих маршрутів та обрати маршрут з найменшою довжиною. / 2 можливих маршрутів, тобто, для 15 міст існує 43 мільярдів маршрутів та для 18 міст вже 177 більйонів. Якщо існував би пристрій, що знаходив би розвязок для 30 міст за годину, то для для двох додаткових міст в тисячу раз більше часу; тобто, більш ніж 40 діб. Наприклад, маючи нижню границю на рівні 100, та після знаходження маршруту вартістю 102, оптимальний маршрут може знаходитись в межах від 100 до 102.Для знаходження отримання опорного плану поставленої задачі обрано метод найближчого сусіда, тому що даний метод знаходить найшвидший розвязок порівняно із іншими методами, також і метод є більш простий і зрозумілий для користувача.Дано пять міст України: · Вінниця · Тернопіль Карта з найкоротшими відстанями (таблиця 1) при подорожі автомобілем можна побачити в додатку Г (отримані за допомогою сервісу Google maps). Міста Вінниця Київ Тернопіль Рівне Черкаси На рисунку 1.1 наведено інтерпретацію цієї задачі у формі графу.C# вибраний через надзвичайну безпечність та простоту коду, технологія .NET значно зменшує зменшує час розробки програми.Створимо програму вирішення задачі комівояжера за наступним алгоритмом (рисунок 2.1) Перший, клас Form1, наслідує базовий клас Form і необхідний для реалізації користувацького інтерфейсу (рисунок 2.2, лістинг класу знаходиться в додатку Б). В класі Form1 є функція INPUTCOUNTOFTOWN яка реагує на подію введення тексту у TEXTBOX. Після введення створюється двовимірний масив текст-боксів з якого за допомогою функції CREATMATRIX буде сформована таблиця відстаней між містами.Отже, ми коротко розглянемо такі види діаграм, як: - діаграма класів; Прецедент (use-case) - опис окремого аспекту поведінки системи з точки зору користувача . Прецедент (use case) - опис множини послідовних подій (включаючи варіанти), що виконуються системою, які призводять до результату, який спостерігає актор. Прецедент представляє поведінку сутності, описуючи взаємодію між акторами і системою. Прецедент не показує, "як" досягається деякий результат, а тільки що" саме виконується.Для перевірки правильності роботи програми розвяжемо дану програму вручну і порівняємо результати. Занесемо дані задачі в матрицю відстаней (таблиця 4.1): Таблиця 4.1 Знайдемо в стрічці яка відповідає місту 1 найменше число: 235 знаходиться на третій позиції в стрічці а отже найближче до Вінниці з наведених міст - Тернопіль. Аналогічно знаходимо інші міста в маршруті (таблиця 4.2). З таблиці 4.2 можна зробити висновок що маршрут комівояжера буде пролягати наступним чином: Вінниця-> Тернопіль-> Рівне-> Київ-> Черкаси-> ВінницяДля експлуатації даної програми необхідно мати у програмному забезпеченні компютера .NET Framework 4.0 який можна легко завантажити з офіційного сайту Microsoft.Для обрахування задачі комівояжера, запускаємо файл COURSEWORK.exe і поле зверху вікна ввести кількість міст, а потім у таблицю, що зявиться ввести відстані між містами та натиснути кнопку щоб отримати рішення.В роботі було наведено аналіз сучасних методів математичного програмування та дослідження операцій. Були розглянуті основні метод

ЗМІСТ

ВСТУП

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

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

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

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

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

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

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

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

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

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

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

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

ВИСНОВКИ

ЛІТЕРАТУРА

ДОДАТКИ