ГЛАВА 6. ТРАНСПОРТНЫЕ  ЗАДАЧИ. МЕТОДЫ ИХ РЕШЕНИЯ.

Постановка задачи.

Предположим, что в пунктах  хранится однородный груз в количестве  единиц. Этот груз следует доставить в  заданных пунктов назначения , причем в каждый из них требуется завезти соответственно  единиц этого груза. Обозначим через  стоимость перевозки единицы груза из пункта    в пункт .

Транспортные задачи делят на две группы:

1) задачи, удовлетворяющие условию баланса, означающему, что общий запас груза на всех пунктах хранения равен суммарной потребности всех пунктов назначения;

2) задачи с нарушенным балансом, среди которых выделяют два случая:

а)  (запасы больше потребностей);

б)  (запасы меньше потребностей).

Рассмотрим сначала задачу, удовлетворяющую условию баланса.

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

Ограничения представляются уравнениями вывоза и привоза груза:

                                                ,        ;

                                                ,       ;

                                                ,                                   ;      .

Решение , ;  , системы называется планом перевозок.

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

.

Условия задачи удобно записывать в виде матрицы перевозок.

Так как поставленная задача является частным случаем задачи линейного программирования, то стратегия решения аналогична:

1) находится начальный план перевозок;

2) производится улучшение начального плана, т.е. последовательный переход от одного плана к другому, связанный с уменьшением суммарной стоимости перевозок. Процесс перехода от одного плана к другому завершается, когда уменьшение суммарной стоимости перевозок станет невозможным.