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

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

У загальному вигляді її формулюють так: із заданих пунктів необхідно доставити вантаж споживачам, якщо відомі запаси вантажів у постачальників, транспортні витрати і потреби в обсягах перевезень кожному споживачеві.

Найпростіша класична постановка транспортної задачі за критерієм вартості полягає у наступному.

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

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

· запаси кожного постачальника повинні бути повністю вивезені;

· попит всіх пунктів споживання повинен бути задовільнений за рахунок розподілу всього запасу вантажів

· забезпечити мінімальні транспортні витрати.

Умови транспортної задачі подають у формі таблиці, яка має вигляд

Постачальники Аі	Споживачі Вj	Наявність вантажу
В1	В2	...	Вj	...	Вn
А1	С11	С12	...	С1j	...	С1n	а1
А2	С21	С22	...	С2j	...	С2n	а2
...	...	...	...	...	...	.....	...
Аi	Сi1	Сi2	...	Сij	...	Cin	ai
....	...	...	...	...	...	...	...
Am	Cm1	Cm2	...	Cmj	...	Cmn	am
Потреба у вантажах	b1	b2	...	bj	...	bn

Позначимо через x_ij кількість вантажу, який перевозиться з пункту постачання А_i в пункт споживання В_j та будемо розглядати змінні x_ij, які задають план перевезень як компоненти матриці перевезень Х розміром m х n.