Якщо для транспортної задачі виконується одна з умов
то модель задачі називають відкритою. Щоб таке завдання мала рішення, необхідно її привести до закритого типу, тобто щоб виконувалося рівність.
Це роблять так: якщо. то додають фіктивного споживача з попитом (в розподільній таблиці з'явиться додатковий стовпець), якщо. то додають фіктивного постачальника з пропозицією (в розподільній таблиці з'явиться додатковий рядок). В обох випадках тарифи вважають рівними нулю. Далі завдання вирішується за таким же порядком, як було розглянуто раніше.
Запишемо алгоритм вирішення транспортної задачі:
1) Перевірка типу моделі ТЗ.
2) Побудова початкового опорного плану (будь-яким способом).
3) Перевірка плану на вирожденність.
4) Перевірка плану на оптимальність методом потенціалів:
а) знаходження потенціалів з системи
(Для всіх заповнених клітин);
б) перевірка другого умови оптимальності
(Для всіх порожніх клітин).
5) Перехід до нехудшему опорному плану (якщо це необхідно).
Приклад. На складах є запаси однотипного товару в кількості а (35; 40; 40; 50), який необхідно доставити споживачам. Потреби споживачів задає вектор b (31; 52; 17; 20). Матриця витрат на доставку одиниці товару від i -го постачальника j -му споживачеві:
Скласти план перевезень з мінімальними транспортними витратами.
Рішення. Визначимо тип моделі транспортної задачі. Сумарна потужність постачальників: 35 + 40 + 40 + 50 = 165 (одиниць товару); Сумарний попит споживачів: 31 + 52 + 17 + 20 = 120 (одиниць товару).
Оскільки . то маємо модель відкритого типу.
Введемо фіктивного споживача, попит якого дорівнює
165 -120 = 45 (одиниць товару).
Тарифи 0. Таким чином отримуємо модель закритого типу, m = 4 - число постачальників, n = 5 - число споживачів. Ранг матриці завдання. Побудуємо початковий опорний план методом мінімального елемента (найменшої вартості).
Число заповнених клітин розподільчої таблиці 8 одно рангу матриці завдання r = 8, отже, опорний план є невироджених.
Транспортні витрати, відповідні опорному плану:
Досліджуємо опорний план на оптимальність, використовуючи метод потенціалів.
Доповнимо таблицю 1 стовпчиком і рядком потенціалів і. Систему потенціалів знайдемо, використовуючи перша умова оптимальності: для заповнених поставками клітин.
З записаної системи знаходимо:. . . . . . . . .
Перевіримо виконання другої умови оптимальності. Для всіх порожніх клітин має виконуватися нерівність:.
(1; 1) 0 + 1 - 5 = -4 0;
(1; 2) 0 + 2 - 4 = -2 0;
(1; 5) 0 - 4 - 0 = -4 0;
(2; 3) 1 + 3 - 5 = -1 0;
(2; 4) 1 + 1 - 8 = -6 0;
(2; 5) 1 - 4 - 0 = -4 0;
(3; 1) 4 + 1 - 6 = -1 0;
(3; 2) 4 + 2 - 8 = -2 0;
(3; 3) 4 + 3 - 7 = 0 0;
(3, 4) 4 + 1 - 10 = -5 0;
(4; 1) 4 + 1 - 5 = 0 0;
(4; 4) 4 + 1 - 2 = 3 0.
Оскільки серед вільних клітин є такі, в яких друга умова оптимальності не виконується, то план не оптимальний.
Здійснимо перехід до нехудшему опорного плану. Найбільш перспективна для заповнення клітина (4; 4), тому що їй відповідає найбільша позитивна оцінка
Знайдемо цикл перерозподілу вантажу для цієї клітини.
Обраної для заповнення клітці присвоюємо знак «+», далі знаки чергуємо. Серед вершин зі знаком «-» вибираємо найменшу поставку.
Перерозподілили поставки по циклу, тим самим перейдемо до нового опорного плану.
Транспортні витрати, відповідні опорному плану:
Досліджуємо опорний план на оптимальність. Знайдемо значення потенціалів, використовуючи перша умова оптимальності. Для заповнених поставками клітин.
Перевіримо виконання другої умови оптимальності. Для всіх порожніх клітин має виконуватися нерівність:.
Випишемо клітини, в яких умова порушена:
(1; 2) 0 + 5 - 4 = 1 0.
Здійснимо перехід до нехудшему опорного плану. Найбільш перспективна для заповнення клітина (1; 2), тому що їй відповідає позитивна оцінка 1. Знайдемо цикл перерозподілу вантажу для цієї клітини.
Число заповнених клітин розподільчої таблиці 8 одно рангу матриці завдання r = 8, отже, опорний план (таб. 3) є невироджених.
Транспортні витрати, відповідні опорному плану:
Досліджуємо опорний план на оптимальність.
Знайдемо значення потенціалів, використовуючи перша умова оптимальності. Для заповнених поставками клітин.
Перевіримо виконання другої умови оптимальності. Для всіх порожніх клітин має виконуватися нерівність:.
Друга умова оптимальності виконується для всіх вільних клітин, отже план оптимальний.
Найменші транспортні витрати.
Відповідь:; оптимальний план розподілу поставок розташований в таб.3.
Завдання для самостійної роботи.
Скласти план перевезень з мінімальними транспортними витратами.