Транспортная задача в сетевой постановке

(с промежуточными пунктами).

В КТЗ продукция перевозится непосредственно из любого пункта производства в любой пункт потребления. Однако в реальных задачах перевозка грузов производится по различным коммуникациям. Из данного пункта производства в данный пункт потребления можно попасть различными путями, побывав в других промежуточных пунктах. Например: Заводы- Оптовые базы- Потребители.

Постановка задачи. Пусть дана транспортная сеть, т. е. совокупность множества узлов и направленных дуг, соединяющих эти узлы между собой. Узлы сети пронумерованы как , каждый узел сети означает некоторый пункт. Если узел i соединен с узлом j дугой (i,j), то это означает возможность непосредственного движения из пункта i в пункт j. Каждый узел i взвешен числом , означающим объем продукции в этом пункте. Если , то в этом пункте имеется излишек продукции, а если , то недостаток продукции в количестве . Если же , то в этом пункте нет ни излишка, ни недостатка. Будем считать, что , т.е. суммарный излишек продукции равен суммарной потребности. Каждая дуга (i,j) взвешена числом - стоимостью перевозки единицы продукции по дуге (i,j). В общем случае . В транспортной сети присутствуют дуги в виде петель.

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

В настоящее время для решения таких задач существуют достаточно эффективные алгоритмы, основанные на модификации метода последовательного улучшения плана ЗЛП.

Рассмотрим два способа решения транспортной задачи в сетевой постановке, основанные на ее сведении к КТЗ: метод отыскания путей минимальной стоимости и метод буферного запаса.