Глава III Транспортные задачи линейного программирования § 3.1. Постановка транспортной задачи общего вида

Наиболее часто в практической деятельности человеку приходится встречаться с задачами о распределении транспортных потоков. Пример простейшей задачи транспортного типа рассмотрен в § 2.2.

Классическая постановка транспортной задачи общего вида такова.

Имеется пунктов отправления – «поставщиков» и пунктов потребления – «потребителей» некоторого одинакового товара. Для каждого пункта определены:

объемы производства -го поставщика,

спрос -го потребителя, ;

стоимость перевозки одной единицы продукции из пункта – i-го поставщика, в пункт – j-го потребителя.

Обычно данные удобно представлять в виде таблицы, которую называют таблицей стоимостей перевозок

Поставщики	Потребители	В1	В2	…	Вn	запасы
А1		C11	C12		C1n	a1
А2		C21	C22		C2n	a2
Аm		Cm1	Cm2		Cmn	am
Потребности		b1	b2		bn

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

Под планом перевозок понимают объем перевозок – количество товара, которое необходимо перевезти от -го поставщика к -му потребителю. Для построения математической модели задачи необходимо ввести штук переменных каждая переменная обозначает объем перевозок из пункта в пункт . Набор переменных и будет планом, который необходимо найти, исходя из постановки задачи.

Ограничения задачи примут вид (3.1):

Очевидно, что для разрешимости задачи (3.1) необходимо, чтобы суммарный спрос не превышал объемы производства у поставщиков: . Если это неравенство выполняется строго, то задача называется «открытой» или «несбалансированной». Если же , то задача называется «закрытой» транспортной задачей.

Мы остановимся сейчас на решении закрытых транспортных задач (ЗТЗ).

В силу ограничений (3.1) нетрудно увидеть, что ТЗ является задачей ЛП и может быть решена симплекс–методом после приведения ее к специальному виду. Но структура системы ограничений имеет некоторую специфику, а именно каждая переменная входит ровно два раза в неравенства системы и все переменные входят в неравенства системы с коэффициентом 1. В силу этой специфики разработан собственный метод решения, называемый методом потенциалов. По–прежнему идеей является переход от одного опорного плана к другому, обязательно «лучшему», с точки зрения значения целевой функции. Здесь целевая функция последовательно уменьшает свои значения, т.к. цель задачи – минимизировать расходы. Каждому опорному плану также соответствует своя распределительная таблица. Переход осуществляется, пока полученный план не будет удовлетворять условию оптимальности. Сначала необходимо построить первоначальный опорный план. В качестве первоначального плана годится любое решение системы уравнений (3.1). Заметим, что это система линейных уравнений, состоящая из уравнений, с неизвестными. Можно доказать, что линейно–независимых уравнений в системе (3.1) , ввиду условия сбалансированности, т.е. базисных переменных должно быть , остальные будут нулевыми. Итак, в качестве плана будем представлять себе таблицу размера , в которой должно быть занято ровно клеток, отвечающих базисным переменным . Стоимости перевозок всегда будем записывать в правом верхнем углу ячейки таблицы, естественно считая их постоянными на протяжении решения задачи.