Транспортна задача

У загальному вигляді транспортну задачу можна сформулювати таким чином: в m пунктах відправлення А₁ ,…, А_n знаходиться однорідний вантаж, кількість якого дорівнює а₁ ,…, а_n одиниць. Вантаж потрібно доставити споживачам В₁ ,…, В_n, попит яких становить b₁ ,…, b_n. Вартість перевезення одиниці вантажу з i-го ( ) пункту відправлення до j-го ( ) пункту призначення дорівнює . Необхідно скласти план перевезень, що повністю задовольнить попит споживачів у вантажі, при цьому сумарні транспортні витрати мінімальні.

Модель транспортної задачі називають закритою (збалансованою), якщо сумарний об’єм вантажу, що є у постачальників, дорівнює сумарному попиту споживачів, інакше модель задачі є відкритою (незбалансованою).

Приклад транспортної задачі. Виробництво продукції здійснюється на чотирьох підприємствах, а потім доставляється у п’ять пунктів споживання. Підприємства можуть випускати на день 235, 175, 185 і 175 одиниць продукції. Пункти споживання готові приймати щодня 125, 160, 60, 250 і 175 одиниць продукції. Зберігання на підприємстві одиниці продукції обходиться у 2 у.о. на день, штраф за недопостачання – 3,5 у.о. на день за одиницю продукції. Вартість перевезення одиниці продукції (в у.о.) з підприємств у пункти споживання наведена у табл. 15.

Таблиця 15

Підприємства	Пункти споживання
	1	2	3	4	5
1	3,2	3	2,35	4	3,65
2	3	2,85	2,5	3,9	3,55
3	3,75	2,5	2,4	3,5	3,4
4	4	2	2,1	4,1	3,4

Необхідно мінімізувати загальні транспортні витрати з перевезення продукції.

Для вирішення даної задачі будемо використовувати програму MS Excel, процедуру Поиск решения. Запишемо умови задачі у робочій книзі (рис. 11).

Рис. 11.

Недопостачання визначається як різниця між обсягом споживання і сумарною кількістю перевезень у пункт споживання: {=B9:F9-B8:F8}. Залишки на підприємстві знаходяться як різниця між обсягом виробництва і сумарними перевезеннями з підприємства: {=H4:H7-G4:G7}.

Сумарна кількість перевезень у пункт 1 в клітині В8 знаходиться за формулою =СУММ(B4:B7), ця формула копіюється на клітини С8:F8. Сумарна кількість перевезень з підприємства 1 в клітині G4 визначається за формулою =СУММ(B4:F4), потім ця формула копіюється на клітини G5:G7.

У клітині Н9 визначається, чи збалансована задача (=ЕСЛИ(ОКРУГЛ(G9;0)=ОКРУГЛ(H8;0);"Задача збалансована";"Задача не-збалансована")) шляхом порівняння загального обсягу споживання у клітині G9 (=СУММ(B9:F9)) і загального обсягу виробництва у клітині Н8 (=СУММ(H4:H7)).

Знаходимо вартість зберігання залишків у клітині J4 ({=СУММ(I4:I7;B8:F8-B9:F9)*2}) і штраф за недопостачання ({=СУММ(B9:F9-B8:F8)*3,5}) у клітині J7.

Вартість перевезень у пункт споживання 1 у клітині В18 знаходиться за формулою масиву {=СУММ(B4:B7*B14:B17)}, потім ця формула копіюється на клітини С18:F18. Загальна вартість перевезень визначається за формулою: =СУММ(B18:F18).

Формулювання математичної моделі задачі:

• змінні для вирішення задачі: кількість перевезень з підприємств у пункти споживання (В4:F7);

• визначення цільової функції (критерію оптимізації): серед усіх припустимих значень змінних знайти таку кількість перевезень з підприємств у пункти споживання, що мінімізують загальні транспортні витрати з перевезення продукції (В19);

• обмеження на змінні: об’єми перевезень не можуть бути від’ємними (В4:F7≥0);

• оскільки модель збалансована, то вся продукція повинна бути вивезена з підприємств, а потреби всіх пунктів споживання повинні бути повністю задоволені, у загальному вигляді: сумарна кількість перевезень у кожен пункт споживання з усіх підприємств повинна бути не менше обсягу споживання (В8:F8≥B9:F9) та сумарна кількість перевезень з кожного підприємства не може бути більше, ніж обсяг виробництва (G4:G7≤H4:H7).

Для вирішення даної задачі будемо використовувати програму Excel, інструмент Поиск решения. Обираємо опцію Сервис, Поиск решения. У вікні Поиск решения встановлюємо мінімальне значення у цільовій клітині В19, вказуємо для зміни клітини В4:F7 і додаємо обмеження.

Результати вирішення задачі показані на рис. 12. Об’єми залишків на підприємстві і недопостачання є нульовими.

Рис. 12.