Задача о наибольшей общей подпоследовательности

      Рисунок 5.2 - Допоміжні матриці та цільова функція.

      Після виконання цих дій, можна заповняти  відповідні комірки відповідними даними і запускати пошук розв’язку.

      Далі  наведені 3 приклади використання Microsoft Excel для розв’язання транспортної задачі за критерієм часу.

      На  рисунку 5.3 наведений розв’язок прикладу 2, розв’язаного «вручну». 

      Рисунок 5.3 - Перший приклад розв’язання з допомогою Excel.

      Аналогічні  дії виконані для прикладів 3 і 4, розв’язаних «вручну». На рисунку 5.4 зображений третій приклад.

      Рисунок 5.4 - Розв’язання в Excel прикладу транспортної задачі.

      Як  видно з рисунку 5.4, Excel знайшов оптимальний розв’язок, який не зовсім співпадає з тим, який був знайдений «вручну». Оскільки нас цікавить лише наявність перевезень в клітинках, то оптимальних планів може бути дуже багато.

      На  рисунку 5.5 показаний третій приклад  розв’язання транспортної задачі за критерієм часу з використанням  Microsoft Excel.

Рисунок 5.5 - Третій приклад розв’язання задачі в Excel.

6 ПРОГРАМНА РЕАЛІЗАЦІЯ АЛГОРИТМУ

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

       Для створення програми, яка реалізує алгоритм північно-західного кута, було використано Microsoft Visual Studio 2010. Програма написана на мові програмування C#. Вони були обрані для того, щоб програмний продукт мав зручний і привабливий інтерфейс та високу швидкодію. Використовуючи Java, можна було б зробити сумісність програми з операційними системами, відмінними по архітектурі від операційних систем сімейства Windows NT. Оскільки більшість комп’ютерів мають операційну систему на базі ядра Windows NT , то не доцільно віддавати в жертву привабливий графічний інтерфейс і швидкодію програми для підтримки екзотичних операційних систем.

       Програма  має дуже простий інтерфейс. Користувач спочатку обирає пункт меню Файл -> Розв’язати задачу. Далі отримує вікно, в якому задає кількість виробників і споживачів продукції. Після натиснення кнопки «Ок» програма дає вікно з таблицею, яку користувач повинен заповнити. Після заповнення таблиці, користувач натискає кнопку «Знайти оптимальний розв’язок». І програма записує в таблицю перше число – кількість відправленої продукції по маршруту, далі ставить знак «|» і записує час проходження часу. Разом з тим, програма відразу дає повідомлення, в якому чітко прописано, який час максимальний буде при оптимальному плані перевезення. 

       На  рисунку 6.1 наведений результат виконання  програми

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

ВИСНОВОК

     В даній курсовій роботі детально розібрана  транспортна задача за критерієм  часу. В роботі: описані математична модель і приклади постановок задач, які приводять до транспортної задачі за критерієм часу; побудовані алгоритми побудови початкового плану, «розвантаження» маршрутів з найдовшим часом, наведені приклади розв’язання задачі «вручну» та за допомогою Microsoft Excel, побудована програма, яка знаходить оптимальний план перевезень.

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

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

     В математичній моделі транспортної задачі за критерієм часу є функція max. Тому дана задача не може бути лінійною Цим зумовлені особливості розв’язання цієї задачі.

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

ПЕРЕЛІК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

1. Калихман И.Л. Линейная алгебра и программирование. – Высшая школа, 1964-426 с.

2. Лунгу К.Н. Линейное программирование. Руководство к решению задач. – М.: ФИЗМАТЛИТ, 2005. – 128с. – ISBN 5-9221-0631-7.

Додаток А. Лістинг програми