9.2. Класична транспортна задача. Особливості транспортної задачі

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

Постачальники	Споживачі							Наявність вантажу
	1		2		…	п
1		C11		C12	…		C1n	a1
	X11		X12			X1n
2		C21		C22	…		C2n	a2
	X21		X22			X2n
…	...		...		.	...		...
m		C1m		C2m	…		Cmn	am
	X		X			X
Потреба у вантажі	b1		b2		…	bn		Z Z

Позначення:

- номер постачальника; =1,2,3,… ;

- номер споживача; =1,2,3,… n;

Х - кількість вантажу, що перевозиться від -го постачальника до - споживача;

C - собівартість перевезення вантажу від з -го постачальника до - го споживача (або відстань між -им постачальником і -им споживачем);

а - наявність вантажу у -го постачальника;

b - потреба у вантажі -го споживача.

Задача полягає у відшуканні такого плану перевезень ,

який би забезпечував мінімум загальної вартості перевезень (або мінімум відстаней) при повному задоволенні запитів постачальників і споживачів.

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

Модель має вигляд:

При виконанні умов:

1. Умова повного задоволення постачальників:

2. Умова повного задоволення споживачів:

3. Умова позитивності змінних:

Для вирішення задачі необхідно зібрати наступну інформацію:

1. Кількість вантажу у кожного з постачальників

2. Кількість вантажу, яка необхідна кожному споживачу

Відстані між постачальниками і споживачами або тарифи (витрати на перевезення одиниці вантажу від i - го постачальника до j – ого споживача).

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

Через особливості транспортної задачі для її вирішення розроблені спеціальні методи: потенціалів, диференціальних рент, індексний, угорський, апроксимації Фогеля, загальний розподільний.

Особливості транспортної задачі полягають в наступному:

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

2. Всі показники (техніко-економічні коефіцієнти і вільні члени) в обмеженнях обох типів мають одну і ту ж одиницю вимірювання, а коефіцієнти при невідомих в критерії оптимальності (відстань або вартість) задані з розрахунку на ту ж одиницю вимірювання (центнер, тонну).

3. Матриці, складені із змінних обох типів обмежень є транспонованими по відношенню одна до одної.