перевезти в другие пункты (пункты назначения). Пункты отправления связаны с пунктами назначения транспортной сетью. Необходимо спланировать перевозки груза по этой сети так, чтобы суммарные транспортные затраты были минимальными.
Пусть 
пункту отнесено число 
где 
. Если 
то пункт i является пунктом отправления (поставщиком) груза и в нем находится единиц груза. Если 
то пункт i является пунктом назначения (потребителем) груза и ему нужно получить 
единиц груза. Если 
то пункт i является промежуточным для перевозки груза. 
единиц груза, которое может быть перевезено из пункта i в соседний пункт 
по участку сети, непосредственно связывающему их, равно 
Пусть 
транспортные затраты по перевозке х единиц груза по этому участку. Числа 
определяют поток в сети, заданный графом (I, U), где 
мн-во вершин графа, 
мн-во его дуг, соответствующих участкам транспортной сети. Тогда С. з. заключается в отыскании потока в сети 
минимизирующего функционал
Поток в сети, минимизирующий функционал 
оптимальным. Следовательно, С. з. состоит в отыскании оптим. потока в сети. Если ф-ции 
выпуклы вниз и непрерывны для 
то справедливы следующие условия оптимальности: поток в сети 
оптим. тогда и только тогда, когда для каждой вершины 
существует число называемое потенциалом, и для каждой насыщенной дуги 
(для которой 
) неотрицательное дуговое число такое, что
где 
соответственно левая и правая производная ф-ции 
. Частичный граф 
, где 
опорой потока 
Если опора является связным графом (см. Графов связность), то поток наз. невырожденным. В противном случае поток является вырожденным.
На приведенных условиях оптимальности (2) основан спец. итерационный метод решения С. з. - метод потенциалов. Отдельная итерация этого метода заключается в преобразовании полученного на предыдущей итерации потока в сети таким образом, что в результате получается новый поток в сети, связанный с меньшими транспортными затратами. Вначале итерации по опоре потока в сети строится система потенциалов и дуговых чисел. Если эти потенциалы и дуговые числа удовлетворяют условиям (2), то поток оптим. В противном случае строится цикл, содержащий дугу, для которой не выполняется одно из условий (2). Остальные дуги цикла берутся из мн-ва дуг, по которому определялись потенциалы. Вдоль этого цикла поток в сети перераспределяется. В результате получается новый поток в сети с меньшими транспортными затратами. Начальный поток выбирается произвольным. На каждой итерации требуется невырожденность потока в сети. Если на какой-то итерации встретится вырожденный поток в сети, то необходимо исходную С. з. изменить так, чтобы в результате получилась новая С. з. с невырожденными потоками в сети.
Если все ф-ции 
линейны, т. е. 
, то С. з. наз. линейной, или сетевой транспортной задачей (с. т. з.). В этом случае условия оптимальности формулируются так: для оптимальности потока в сети 
необходимо и достаточно существование потенциалов 
таких, что
С. т. з. является спец. задачей программирования линейного. Потенциалы вершин, удовлетворяющие условиям оптимальности (3), вместе с дуговыми числами, 
являются решением задачи, двойственной к с. т. з. С помощью метода потенциалов, частично упрощенного по сравнению с общим случаем, решают с. т. з. за конечное к-во итераций.
Другим методом решения с. т. з. является метод Форда — Фалкерсона. Этот метод основан на одновременном решении с. т. з. и двойственной к ней. На канадой его итерации определяется макс. поток из источников (вершин графа, для которых 
в стоки (вершины графа, для которых 
в частичной сети 
, где 
потенциалы вершин, определенные на предыдущей итерации. Макс. поток ищется из условия, что на дугах, для которых 
он должен равняться ее пропускной способности 
Если при этом потребности стоков будут удовлетворены, то построенный поток в сети будет оптимальным, т. к. он удовлетворяет условиям оптимальности (3)
В противном случае потенциалы некоторой части вершин изменяются. Изменение это производится таким образом, чтобы расширить мн-во дуг U (а значит, и частичный граф 
и чтобы значение целевой функции двойственной задачи увеличилось. В расширенной части сети, соответствующей графу 
снова определяется макс. поток и т. д. С каждой итерацией невязки частичного потока, равные неудовлетворенности потребностей стоков, уменьшаются. Через конечное к-во итераций будут получены потенциалы 
для которых макс. поток в соответствующей частичной сети будет удовлетворять потребностям стоков в сети, т. е. будет являться решением с. т. з.
Лит.: Ермольев Ю. М., Мельник И. М. Экстремальные задачи на графах. К., 1968 [библиогр. с. 172—174]. И. М. Мельник.
