Необходимые сведения

ТРАНСПОРТНАЯ ЗАДАЧА

Важным частным случаем задачи линейного программирования является транспортная задача. Необходимо определить план перевозок некоторого однородного груза, минимизирующий затраты на общую стоимость перевозок, из m пунктов отправления (производства) А₁, А₂, …A_m. в n пуктов потребления В₁, В₂, …, В_n.

Введем следующие переменные:

a_i – величина предложения продукта в пункте i, i = 1, …,m;

b_j – величина спроса на продукт в пункте j, j = 1, …,n;

c_ij – затраты на транспортировку единицы продукта из пункта i в пункт j;

x_ij – количество продукта, перевозимого из пункта i в пункт j.

Тогда транспортную задачу можно представить в виде таблицы 1.

Т а б л и ц а 2.1

Пункты производства	Пункты потребления	Предложение
B1	B2	…	Bj	…	Bn
A1	c11	c12	…	c1j	…	c1n	a1
A2	c21	c22	…	c2j	…	c2n	a2
…	…	…	…	…	…	…	…
Ai	ci1	ci2	…	cij	…	cin	ai
…	…	…	…	…	…	…	…
Am	cm1	cm2	…	cmj	…	cmn	am
Спрос	b1	b2	…	bj	…	bn

В сделанных обозначениях математическую модель транспортной задачи можно записать следующим образом:

(2.1)

(2.2)

(2.3)

Существует несколько вариантов транспортной задачи.

1. Закрытая транспортная задача

Общий спрос равен общему предложению:

Это равенство является необходимым и достаточным условием существования допустимого плана задачи (2.1) – (2.3).

2. Открытая транспортная задача

а) Пусть существует излишек продукта, т.е.

б) Пусть существует дефицит продукта, т.е.

Такую задачу можно свести к закрытой задаче, вводя дополнительный столбец (строку), равный по величине имеющейся разности между общим спросом и общей потребностью, тарифы c_ij которого считают условно равными нулю.

3. Транспортная задача с фиксированными перевозками

Если объем перевозок между пунктами i и j задан, то в задаче (2.1) – (2.3) вводится дополнительное ограничение x_ij = v_ij, где v_ij – заданный объем перевозок.

4. Задача с ограничениями на пропускные способности

Если объем перевозок из пункта i в j пункт ограничен величиной w_ij, то в задаче (2.1) – (2.3) вводится дополнительное ограничение x_ij ≤ w_ij.

Все приведенные выше модели описывают транспортную задачу в виде задачи линейного программирования. В этой форме она может быть решена стандартными средствами ЛП, например, с помощью симплекс-метода. Однако специфичная форма системы ограничений данной задачи (в виде уравнений-равенств) позволяет существенно упростить обычный симплекс-метод. Такой метод решения транспортной задачи (ТЗ) называют распределительным, или методом потенциалов. По аналогии с общим случаем ЗЛП, решение в нем осуществляется по трем шагам:

· нахождение первоначального опорного решения;

· проверка критерия оптимальности;

· переход к следующему опорному решению.