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

      Рисунок 4.1 - Початкові дані до задачі і допустимий розв’язок

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

      Для розвантаження комірки, згідно алгоритму, потрібно використати комірку з  часом 2. Отже, в комірку в 3 рядку  і 3 стовпці, яка має час 4 додаємо 100 одиниць, так само в комірку  в 4 рядку і 2 стовпці, з часом 9 додаємо 100 одиниць, а в комірці, що в 4 рядку і 3 стовпці віднімаємо 100 одиниць. В результаті маємо повну розгрузку комірки з максимальним часом. Варто зазначити, що, якщо не чітко слідувати алгоритму, то можна побудувати і інший «розвантажувальний» цикл. Тобто, можна використати комірку не з часом 2, а останню комірку в лівому нижньому куті. Якби не повністю була «розвантажена» комірка з максимальним часом, то потрібно було використати саме останню комірку. Результат приведених дій наведений на рисунку 4.2

      Рисунок 4.2 - Результат першого «розвантаження»

      Далі  аналізуємо таблицю і помічаємо, що максимальний час 12 в комірці в другому рядку, першому стовпцю. Діючи за алгоритмом «розгрузки», знаходимо клітинку в останньому рядку і другому стовпцю. Мінімум рівний 100. Тому ми розвантажуємо тільки 100 одиниць. В комірках не може бути від’ємне значення. В комірку в другому рядку другого стовпця додаємо 100 одиниць і в комірку з часом 11 додаємо 100 одиниць. Оскільки комірка з поточним максимальним часом ще не повністю «розвантажена», шукаємо клітини, по яких можна побудувати цикл. Проаналізувавши таблицю це клітинка, яка іде відразу за попередньо обраною(в останньому рядку третього стовпця) і остання, оскільки клітина з часом 2 може розвантажити лише 25 одиниць продукції.

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

      Рисунок 4.3 - Розв’язання після другого «розвантаження»

      Для порівняння сформуємо початковий базис методом найменшого часу. Як видно з таблиці, максимальний час в початковій таблиці рівний 20. Якщо виконує людина процедуру «розвантаження»,  то вона відразу обере в останньому рядку комірку з часом 2(останній рядок, третій стовпець). Це дозволить відразу прийти до оптимального розв’язку. Комп’ютер діє за заданим алгоритмом. Тому він спочатку додасть в комірку праворуч від себе  з часом 19 150 одиниць, додасть в комірку вище себе з часом 12 також 150 одиниць і відніме в комірці з часом перевезення 1 150 одиниць. Потім решту 50 одиниць буде «розвантажувати», використовуючи комірку з часом 6. В результаті цієї операції, в базисі з’являються комірки з часом 12 і 19, які треба буде розвантажувати. Це є прикладом того, як, здавалося, кращий алгоритм отримання початкового базису дає більше ітерацій. Проілюструємо вище сказане з допомогою таблиці.

      На  рисунку 4.4 показаний початковий базис методом найменшого часу.

      Рисунок 4.4 - Початковий базис, отриманий методом найменшого часу.

      На  рисунку 4.5 показаний результат після «розгрузки».

      Рисунок 4.5 - Результат після першої розгрузки.

      Розвантажуємо комірку з часом 19. Результат наведений на рисунку 4.6

      Рисунок 4.6. «Розвантаження» комірки з часом 19

      Далі  розвантажуємо комірку з часом 12 і отримуємо остаточний розв’язок, наведений на рисунку 4.7.

      Рисунок 4.7 - Остаточний розв’язок

      Приклад 2. Чотири постачальники з вантажем відповідно з 550, 250, 300, 100 одиниць можуть забезпечити споживачів, які потребують відповідно 400, 200, 150, 450 одиниць цих вантажів. Знайти мінімальний час для здійснення цих перевезень, якщо матриця часу має вигляд,  показаний на рисунку 4.8.