11. Знаходження опорного плану задачі транспортного типу

Розв’язок ЗТТ, як і кожної ЗЛП починається із знаходження опорного (допустимого) розв’язку, або, як будемо говорити, опорного плану. На відміну від загального випадку ЗЛП розв’язок ЗТТ завжди існує, оскільки сумарна вартість перевезень – невід’ємна обмежена знизу функція.

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

Приклад. Розглянемо таблицю:

ПП ПВ	В1	В2	В3	В4	В5	Запаси ai
А1	10	8	5	6	9	48
А2	6	7	8	6	5	30
А3	8	7	10	8	7	27
А4	7	5	4	6	8	20
Замовленняbj	18	27	42	12	26	125

(11.1)

Треба знайти опорний (допустимий) план.

Розв’язування. Перепишемо табл. (11.1) і будемо поступово заповнювати її перевезеннями, починаючи з лівої верхньої клітинки (1,1) (північно-західного кута таблиці).

Міркуємо таким чином. Пункт В₁ подав замовлення на 18 одиниць вантажу. Задовольнимо це замовлення за рахунок запасу 48, який є в пункті А₁, і запишемо перевезення 18 в клітинці (1,1). Після цього замовлення з пункту В₁ виконане, а в пункті А₁ залишилося ще 48-18=30 одиниць продукції. Задовольняємо за їх рахунок замовлення з пункту В₂ (27 одиниць). Запишемо 27 в клітинку (1,2). Три одиниці продукції в пункті А₁ призначимо пункту В₃. У складі замовлення В₃ залишилися незабезпеченими 39 одиниць. З них 30 покриємо за рахунок пункту А₂, чим його запас буде вичерпано, а ще 9 візьмемо з пункту А₃. Із 18 одиниць пункту відправлення А₃ 12 виділимо на пункт В₄; 6 одиниць, що лишилися, призначимо пункту В₅ і разом з 20 одиницями пункту А₄ повністю покриємо його замовлення. Одержимо:

ПП ПВ	В1	В2	В3	В4	В5	Запаси ai
А1	10 18	8 27	5 3	6	9	48
А2	6	7	8 30	6	5	30
А3	8	7	10 9	8 12	7 6	27
А4	7	5	4	6	8 20	20
Замовлення bj	18	27	42	12	26	125

(11.2)

Як видно з табл. (11.2) розподіл запасів закінчено: кожен пункт призначення одержав вантаж згідно зі своїм замовленням. Це випливає з того, що сума перевезень у кожному рядку дорівнює відповідному запасу, а у стовпчику – замовленню.

Таким чином, складено план перевезень, що задовольняє балансові рівняння вигляду (10.3), (10.4). Одержаний розв’язок не тільки допустимим, а й опорний розв’язок ЗТТ.

Клітинки таблиці (11.2), в яких стоять ненульові перевезення – базові, їх кількість задовольняє умову r= n+m-1=8. Інші клітинки – вільні (порожні), їх кількість (m-1)(n-1)=12. Отже, план опорний і поставлене завдання побудови опорного плану виконане. Виникає запитання: а чи оптимальний за сумарною вартістю перевезень план отримано? Звичайно, ні. Адже під час побудови опорного плану зовсім не враховувалась вартість локальних перевезень . Природно, що цей план не зобов’язаний бути оптимальним. Дійсно, сумарна вартість цього плану складає:

.

Не важко переконатися, що коли перенесемо 18 одиниць з клітини (1,1) в клітину (2,1), а потім 18 одиниць з клітини (2,3) в (1,3), одержимо сумарну вартість перевезень:

Балансові співвідношення при цьому не були порушені. Отже, попередній план перевезень не був оптимальним.