5 Транспортна задача (тз)

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

Постановка задачі. Є m пунктів А₁, А₂, ..., А_m, у яких виготовляється або зберігається однорідний або взаємозамінний продукт у кількостях відповідно а₁, а₂, ..., а_m. Цей продукт необхідно доставити в n пункти споживання В₁, В₂, ..., В_n, де він потрібний відповідно в кількостях в₁, в₂, ...в_n. Відомі транспортні витрати (тарифи) c_ij, пов'язані із транспортуванням одиниці продукції з i пункту зберігання в j пункт споживання.

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

Для наочності ТЗ представляють у вигляді таблиці, яка називається розподільною.

Пост.	Споживач					Зап.
	В1	В2	В3	В4	Вn
А1	с11 х11	с12 х12	с13 х13		с1n х1n	a1
А2	с21 х21	с22 х22	с23 х23		с2n х2n	a2
А3	с31 х31	с32 х32	с33 х33		с3n х3n	a3
...	...	...	...	...	...	...
Аm	сm1 хm1	сm2 хm2	сm3 хm3		сmn хmn	am
Потр.	в1	в2	в3	...	вn

Матриця називається матрицею тарифів.

Для такої задачі невідомою є матриця перевезень – (тут х_ij означає кількість вантажу, перевезеного з i пункту постачальника в j пункт споживача.

Сформулюємо задачу математично, тобто складемо її математичну модель. Цільовою функцією такої задачі буде функція мінімізації сумарних транспортних витрат

(69)

Така задача вирішується при наступних обмеженнях: весь вантаж з пунктів постачальника повинен бути повністю вивезеним, і всі потреби пунктів споживача повинні бути повністю задоволені

(70)

(71)

(72)

Умовою сумісності транспортної системи обмежень є наявність балансу

запаси вантажу дорівнюють потребам (73)

Якщо умова (73) виконується, то математична модель ТЗ називається закритою. Якщо умова (73) не виконується, то математична модель ТЗ називається відкритою.

Відмітимо, що відкриту модель завжди можна привести до її закритого виду. Допустимо, що , тоді в розподільну таблицю ТЗ уводиться фіктивний (n+1) пункт споживання з потребами відповідно рівними . У той же час тарифи для даного пункту.

Такий підхід дозволяє записати математичну модель закритої задачі.

5.1. Особливості математичної моделі тз

1. Задача представлена в 1-ій канонічній формі.

2. Коефіцієнти при невідомих в обмеженнях рівні 1.

3. Кожна змінна входить лише двічі у відповідні обмеження (це означає, що така таблиця буде слабозаповненою).

4. Ранг системи обмежень ТЗ ч = m + n –1.

5. Усього в ТЗ буде m∙ n змінних, з них базисних m∙ n-1, а вільних m∙ n-(m∙ n-1).

Висновок. Представлений аналіз математичної моделі ТЗ показує, що така задача може розв’язуватись симплексною процедурою. Однак особливості її математичної моделі дозволили розробити більше прості й зручні методи розв’язування такої задачі, а саме:

- угорський метод;

- метод диференціальних рент;

- метод потенціалів.

Одним з найбільш простих є метод потенціалів.