Контрольні питання:

1. Що таке припустимий план перевезень?

2. Яким чином заповнюють клітини рядку та стовпця різниць з використанням Епсілон-прийому?

3. Яким чином заповнюють клітини рядку та стовпця різниць з використанням 0-підстановки?

4. Коли використовують обидві способи?

Література [1,7]

Практична робота 11. Рішення транспортної задачі розподільчим методом

Мета: навчитись використовувати розподільчий метод для знаходження оптимального плану розподілу транспортної задачі.

Задача

Дані роботи №8.

Завдання

1. Відстані та вантажообіг розрахувати згідно свого варіанту по таблиці 8.1

2. Скласти оптимальний план перевезень вантажів розподільчим методом

Методичні вказівки

Транспортна задача має вид:

Розглянемо тепер двоїсту задачу. Оскільки обмежень усього m + n, то і відповідні перемінні двоїстої задачі позначимо так: (перемінні, відповідні першої m обмеженням) і (перемінні, відповідні останньої n обмеженням). Тоді, з огляду на вид векторів та вид вектора , запишемо двоїсту задачу в наступному виді:

Величини називаються потенціалами складів, а величини  потенціалами пунктів споживання.

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

Отже тепер  оптимальний опорний план транспортної задачі. Тоді, відповідно до теореми подвійності, повинне виконуватися умова

Це і дозволяє перевірити оптимальність будь-якого опорного плану.

Сам алгоритм виконується за допомогою алгоритму:

1. Один з потенціалів задається довільно, скажемо, покладається .

2. Розглядається система лінійних рівнянь виду для тих наборів індексів i , j , для яких , і знаходяться потенціали та усіх складів і всіх пунктів споживання.

Для всіх інших наборів індексів i , j (для яких ) перевіряється умова .

Якщо ця умова виконується для всіх наборів індексів i , j , для яких , то розглянутий план є оптимальним. Якщо ж, хоча б для однієї пари , тобто план не оптимальний - треба побудувати цикл, починаючи з клітинки у якої максимальна позитивна різниця між сумою потенціалів та цільовим елементом. Цикл будують за правилом: початкова клітина - стовбець – рядок – стовбець – рядок …- початкова клітина. Кожен кут циклу повинен знаходитись в завантаженої клітинці. Далі розставляють знаки кутів: початкова клітинка «+», сусідні – «-« і так далі чередують знаки кутів. З негативних кутів обирають найменше навантаження – це значення перерозподіляють по контуру згідно знаків кутів. Потім дії з потенціалами рядків і стовпчиків повторюють.

Контрольні питання

1. Склад математичної моделі транспортної задачі лінійного програмування.

2. Методи розв'язання задач лінійного програмування

3. Сутність і алгоритм розв'язання транспортної задачі лінійного програмування

4. Способи побудови початкового припустимого плану при розв'язуванні транспортної задачі розподільчим методом.

5. Перевірка припустимого плану на оптимальність.

6. Удосконалення неоптимального плану.

7. Основні типи транспортних задач, що вирішуються розподільчим методом.

8. Транспортна задача відкритого типу.

9. Визначення допоміжних чисел (потенціалів) рядків і стовпчиків матриці

10. Перерозподіл завантаження клітинок матриці. Побудова контура

11. Знаходження потенціальних незавантажених клітинок

Література [1, 2, 3, 5]

Практична робота 12. Рішення транспортної задачі методом розв’язуючих доданків.

Мета: навчитись використовувати метод розв’язуючих доданків для знаходження оптимального плану розподілу.

Задача

Дані роботи №8.

Завдання

1. Відстані та вантажообіг розрахувати згідно свого варіанту по таблиці 8.1

2. Скласти оптимальний план перевезень вантажів методом розв’язуючих доданків.