Глава 5. Транспортная задача

5.1. Экономико-математическая модель транспортной задачи

5.2. Методы построения начального опорного плана

5.3. Решение транспортной задачи методом потенциалов

5.1. Экономико-математическая модель транспортной задачи

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

Пусть в пунктах производится некоторый однородный продукт, причем объем производства этого продукта в пунктесоставляетединиц,(– количество пунктов производства). Произведенный в пунктах производства продукт должен быть доставлен в пункты потребления, причем объем потребления в пунктесоставляетединиц продукта,(– количество пунктов потребления). Предполагается, что транспортировка готовой продукции возможна из любого пункта производства в любой пункт потребления и транспортные издержки, приходящиеся на перевозку единицы продукта из пунктав пункт, составляетденежных единиц. Задача состоит в организации такого плана перевозок, при котором суммарные транспортные издержки были бы минимальными.

Формально задача ставится следующим образом. Пусть – количество продукта, перевозимого из пунктав пункт. Требуется определить совокупность извеличин, удовлетворяющих условиям

(5.1)

и обращающих в минимум линейную форму ,

В соответствии с условиями задачи обратные перевозки не допус­каются .

Группа ограничений (5.1) связана с тем обстоятельством, что объем вывезенного из каждого пункта производства продукта, а объем ввезенного в пункт потребления продукта в точности соответствует его потребности. При этих ограничениях необходимым и достаточным условием для разрешимости транспортной задачи является условие баланса

.

Если условие баланса соблюдается, то такая транспортная задача называется закрытой, в противном случае – открытой и для решения должна быть сведена к закрытой путем введения фиктивного потребителя либо поставщика.

Специфическим для транспортной задачи являются следующие два обстоятельства:

а) каждое из переменных входит в два уравнения системы (5.1);

б) все коэффициенты при переменных принимают лишь два значения 0 или 1.

Эти условия позволили разработать для решения транспортной задачи алгоритмы, существенно более простые, чем симплексный метод, который является одним из основных методов решения задач линейного программирования.

Исходные данные транспортной задачи удобно представлять в виде табл. 5.1, где А_i, – пункты отправления (производства);В_j, – пункты назначения (потребления).

Таблица 5.1

Пункты отправлений	Пункты назначения				aj
	В1	В2	…	Bn
A1	C11 X11	C12 X12	...	C1n X1n	a1
A2	C21 X21	C22 X22	...	C2n X2n	a2
...	...	...	...	...	...
Am	Cm1 Xm1	Cm2 Xm2	...	Cmn Xmn	am
bj	b1	b2	...	bn

В верхнем правом углу каждой клетки таблицы записываются затраты на перевозку c_ij, а в самих клетках – искомые количества грузов х_ij. Суммируя х_ij по горизонтали и вертикали и приравнивая их соответственно а_i и b_j, мы получаем систему ограничений (5.1).