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

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

Для визначення нижньої межі користуються операцією редукції або приведення матриці по рядках, для чого необхідно в кожному рядку матриці 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 – Відстані між містами (км)

Міста	Вінниця	Київ	Тернопіль	Рівне	Черкаси
Вінниця	-	250	235	298	336
Київ	250	-	433	330	183
Тернопіль	235	433	-	151	571
Рівне	298	330	151	-	500
Черкаси	336	183	571	500	-

 

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

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

 

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

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

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

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

 

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

 

ПОЧАТОК

Вводимо кількість міст

 

 

Створюємо таблицю для заповнення відстаней

 

 

Заповнюємо  таблицю

 

 

Для рішення  задачі скористаємось класом "GreedyAlgorithm"

 

 

Виведення відповіді

 

КІНЕЦЬ

 

 

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

 

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

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

 

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

Функція 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.

                  ::Створення моделі даних, що були введені користувачем та перевірені на валідність

::Інтерфейс

К::Користувач1

1:Авторизація

2:Передача інформації

12:Виведення розв`язку

: Аналіз даних

3: Перезапит умови

4:Початок розв`язання

::Знаходження найменшого елементу стрічки

5:Передача даних

::Перехід до наступного міста

6:Передача даних

::Перевірка чи є місто початковим

::Підрахунок мінімальної вартості перевезень

7:Передача даних

10:Передача даних

9:Передача даних

  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

 

 

 

 

 

 

 

вивід інформації про задачу, що досліджується

 

введення інформації про модель

 

введення параметрів моделі

 

Вибір початкового міста

 

Моделювання умови

 

користувач

інтерфейс

 

Розв'язання

 

Вивід результатів

 

 

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

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

                         Клас інтерфейсу