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

- int[][] A;

         - TextBox[][] tbA;

        - int _n;

        - int _oldN;

       - bool _alreadyExists; 

 

+ CreatMatrix()

 

Клас розв'язку

 

 

 

- int[][] A;

- int[] column;

- int N;

- List<int> AnswerList;

 

     +GreedyAlgorithm(int[][] matrix)

+List<int> Answer()

 

 

 

 

 

 

 

 

 

Рисунок 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	Вінниця	-	250	235	298	336
2	Київ	250	-	433	330	183
3	Тернопіль	235	433	-	151	571
4	Рівне	298	330	151	-	500
5	Черкаси	336	183	571	500	-

 

 

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

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

 

 

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

Аналогічно  знаходимо інші міста в маршруті (таблиця 4.2).

 

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

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

 

 

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

Вінниця –> Тернопіль –> Рівне –> Київ –> Черкаси –> Вінниця

Або якщо користуватися  номерами міст:

1 –> 3–> 4 –> 2 –> 5 –> 1

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

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

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

 

Рисунок 4.1 – Результат роботи програми

 

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

 

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

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

 

Таблиця 4.3 –  Умова задачі

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

 

Таблиця 4.4 – Розв’язок  задачі

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

 

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

    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. Кузнєцов Ю.Н., Кузубов В.И., Волощенко А.Б.  “Математическое