Задача 10

Транспортна задача ставиться таким чином: є m пунктів відправлення А₁, А₂ ..., А_m, в яких зосереджені запаси якихось однорідних вантажів в кількості відповідно а₁, а₂ ..., а_m одиниць. Є n пунктів призначення В₁, В₂ ..., В_n, що подали заявки відповідно на b₁, b₂ ..., b_n одиниць вантажу. Відомі вартості С_i,j перевезення одиниці вантажу від кожного пункту відправлення А_i до кожного пункту призначення В_j. Всі числа С_i,j, створюючи прямокутну таблицю, задані. Потрібно скласти такий план перевезень, (звідки, куди і скільки одиниць поставити), щоб всі заявки були виконані, а загальна вартість всіх перевезень була мінімальна.

Завдання:

Знайдіть рішення транспортної задачі:

– способом «північно-західного кута»,

– способом мінімальної вартості по рядку,

– способом мінімальної вартості по стовпцю.

Умови транспортної задачі задані транспортною таблицею (табл. 2).

Таблиця 2

Умови задачі

Приклад розв’язання завдання:

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

Умови транспортної задачі задані транспортною таблицею.

Таблиця 3

Умови задачі

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

Одержане рішення є опорним рішенням транспортної задачі (табл. 4)

Таблиця 4

Опорне рішення транспортної задачі методом «північно-західного кута»

Складений нами план перевезень не є оптимальним за вартістю, оскільки при його побудові ми зовсім не враховували вартість перевезень С_i,j.

Інший спосіб — спосіб мінімальної вартості по рядку заснований на тому, що ми розподіляємо продукцію від пункту A_i не в будь-якій з пунктів B_j, а в той, до якого вартість перевезення мінімальна. Якщо в цьому пункті заявка повністю задоволена, то ми прибираємо його з розрахунків і знаходимо мінімальну вартість перевезення з пунктів B_j, що залишилися. У всьому іншому цей метод схожий з методом «північно-західного кута».

В результаті опорний план, складений способом мінімальної вартості по рядку, виглядає як показано в таблиці №5.

При цьому методі може вийти, що вартості перевезень C_i,j і C_i,k від пункту A_i до пунктів B_j і B_k рівні. В цьому випадку з економічної точки зору вигідніше розподілити продукцію в той пункт, в якому заявка більше. Так наприклад, в рядку 2 C_2,1 = C_2,4, але заявка b₁ більше заявки b₄, тому 4 одиниці продукції ми розподілимо в клітку (2,1).

Спосіб мінімальної вартості по стовпцю аналогічний попередньому способу. Їх відмінність полягає в тому, що в другому способі ми розподіляємо продукцію від пунктів Bi до пунктів Aj за мінімальною вартістю Cj,i_. Опорний план, складений способами мінімальних вартостей, звичайно більш близький до оптимального рішення.

Так, в нашому прикладі загальні витрати на транспортування за планом, складеному першим способом, F₀ = 1039, а по другому — F₀ = 723.

Таблиця 5

Опорне рішення транспортної задачі

способом мінімальної вартості по рядку

Клітки таблиці, в яких стоять ненульові перевезення, є базисними. Їх число повинне дорівнювати m + n - 1.

Необхідно відзначити також, що зустрічаються такі ситуації, коли кількість базисних кліток менше ніж m + n - 1. В цьому випадку розподільна задача називається виродженою. В цьому випадку слідує в одній з вільних кліток поставити кількість перевезень рівне нулю. Так, наприклад, в таблиці №5:

m + n - 1 = 4 + 5 - 1 = 8

а базисних кліток 7, тому потрібно в одну з кліток рядка 3 або стовпця 2 поставити значення «0». Наприклад, в клітку (3,5).

Складаючи план за способами мінімальних вартостей, на відміну від плану за способом «північно-західного кута», ми враховуємо вартості перевезень C_i,j, і цей план є більш оптимальним.