І. Постановка транспортної задачі

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

Введемо позначення:

х_ij – змінні, які підлягають розшуку та виражають кількість вантажу, який перевозиться від і-го постачальника до j-го споживача (і=1...m, j=1...n);

с_ij – вартість перевезення одиниці вантажу від i-го постачальника до j-го споживача;

а_i – кількість одиниць вантажу у і-го постачальника;

b_j – кількість одиниць вантажу, яка потрібна j-му споживачу.

Транспортна задача може бути сформульована як частковий випадок задачі лінійного програмування і вирішена симплекс-методом.

Кількість одиниць вантажу у постачальників відповідає попиту з боку споживачів, що відображається в умові балансу

. (6.1)

Така економіко-математична модель транспортної задачі називається закритою та з урахуванням умови (8.1) вона має вид:

; (6.2)

(6.3)

. (6.4)

Дана транспортна задача є збалансованою.

У наведених виразах формула (6.2) відповідає цільовій функції з мінімізації транспортних витрат. Формули (6.3) є обмеженнями задачі:

• перша формула характеризує те, що весь вантаж від постачальників має бути вивезеним;

• друга формула відтворює той факт, що попит споживачів задовільнений.

Формула (6.4) є умовою невід'ємності змінних.

Іі. Приклад рішення транспортної задачі за допомогою електронних таблиць

Задача.В Київський області 3 цукрових заводи (В) отримують від 5 сільськогосподарських підприємств (А) сировину. Скласти такий план перевезень від постачальників до споживачів, щоб вартість перевезень була мінімальною, вантаж від постачальників був вивезеним, а потреби заводів у сировині були задовільнені (табл. 6.2).

Таблиця 6.2

Вихідні дані для транспортної задачі

Витрати на перевезення одиниці вантажу
А1			А2			А3			А4			А5
В1	В2	В3	В1	В2	В3	В1	В2	В3	В1	В2	В3	В1	В2	В3
20	15	35	25	20	35	30	25	25	20	30	30	15	20	25

Продовження таблиці 6.2

Запаси постачальників					Потреби споживачів
А1	А2	А3	А4	А5	В1	В2	В3
100	220	110	170	120	220	240	260

Розглянемо загальну схему розміщення даних в середовищі Excel для рішення транспортної задачі (мал. 6.1).

Малюнок 6.1.

Рішення транспортної задачі на ПК проводиться за таким алгоритмом:

1. Заповнюємо шапку та заготовки рядків і стовпців як на мал. 6.2.

2. Заповнюємо електронну таблицю: блоки «Запаси», «Споживання» та «Матрицю вартості».

3. Записуємо економіко-математичну модель згідно з похідними даними:

F(x) = 20х₁₁+ 25х₁₂+ 30х₁₃+20х₁₄+ 15х₁₅+

+ 15х₂₁+ 20х₂₂+ 25х₂₃+ 30х₂₄+ 20х₂₅+

+ 35х₃₁+ 35х₃₂+ 25х₃₃+ 30х₃₄+ 25х₃₅min;

х₁₁+ х₁₂+ х₁₃+ х₁₄+ х₁₅=220,

х₂₁+ х₂₂+ х₂₃+ х₂₄+ х₂₅=240,

х₃₁+ х₃₂+ х₃₃+ х₃₄+ х₃₅= 260,

х₁₁+ х₂₁+ х₃₁= 100,

х₁₂+ х₂₂+ х₃₂= 220,

х₁₃+ х₂₃+ х₃₃= 110,

х₁₄+ х₂₄+ х₃₄= 170,

х₁₅+ х₂₅+ х₃₅= 120;

x_j≥ 0 (i=1…5; j=1…3).

4. В клітинку G16 за допомогою Майстра функційзаписуємо формулу цільової функції =СУММПРОИЗВ(B5:F7;B10:F12).

5. У клітинки D13F13 записуються формули сумування змінних по стовпцям, що відповідає запасам постачальників =СУММ(B10:B12).

6. У клітинки G10G12 записуються формули сумування змінних по рядках, що відповідає потребі споживачів=СУММ(B10:F10) (мал. 6.2).

Малюнок 6.2.

7. Відмітити клітинку G16 (цільова функція) та активізувати режим Севис/Поиск решения (мал. 6.3).

Малюнок 6.3.

8. Заповнити рядок Установить целевую ячейку.

9. Включити один з варіантів оптимізації. Для нашої задачі – Мінімальному значенню.

10. Заповнити рядок Изменяя ячейки посиланням на блок B10:F12.

11. Заповнити вікно Ограниченияобмеженнями за рядками і стовпцями змінних, що відповідає запасам постачальників та потребам споживачів (мал. 6.4).

12. У рядку Знаквибрати знак « = ».

Малюнок 8.4.

13. Заповнення рядків вікна Добавитьзакінчити натиском кнопки ОК.

14. Натиснути кнопку Параметрыта вибрати режимЛинейнаямодельіНеотрицательные значения, натиснути кнопку ОК (мал. 6.5).

Малюнок 6.5.

15. Далі натискаємо кнопку Выполнить.

16. Після виконання обчислень на екрані з’явиться вікно Результатыпоиска решений, в ньому відображено результат роботи: Решение найдено Все ограничения и условия оптимальности выполнены (мал. 6.6).

Малюнок 6.6.

Рішення транспортної задачі має вигляд (мал. 6.7):

Малюнок 6.7.