о максимальном потоке в сети должна удовлетворять следующим условиям – сумма потоков дуг

f(u,v) = 0 для всех . Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь.
Неформальное описание
1.    Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью.
2.    В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся.
3.    Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток:
1.   На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью cmin.
2.   Для каждого ребра на найденном пути увеличиваем поток на cmin, а в противоположном ему – уменьшаем на cmin.
3.   Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.
4.    Возвращаемся на шаг 2.
Важно, что алгоритм не конкретизирует, какой именно путь мы ищем на шаге 2 или как мы это делаем. По этой причине алгоритм гарантированно сходится только для целых пропускных способностей, но даже для них при больших значениях пропускных способностей он может работать очень долго. Если пропускные способности вещественны, алгоритм может работать бесконечно долго, не сходясь к оптимальному решению.
Сетевая постановка транспортной задачи.
На практике вместо общей постановке рассматривается сетевая постановка транспортной задачи, которая позволяет учесть влияние маршрутов на доставку более точно. В этом случае транспортная задача задается в виде ориентированного графа, в котором его вершины соответствуют пунктам отправления/назначения, а дуги маршрутам между ними.

Пусть задан граф = ( , ), где = ∪ – множество пунктов от- правления/назначения, = × – множество путей между пунктами, такое что любой ∈ представим в виде ( , ), где ∈ , ∈ . Поэтому матрицы С (составлена из всех ) и (составлена из ) можно рассматривать векторы [ ] и [ ] Заметим, что:

Тогда ограничения можно записать так:
Пусть ∈ , когда ∈ или ∈ . Тогда транспортную задачу можно сформулировать следующим образом:
При этой формулировке транспортная задача может быть поставлена для любого графа и интерпретируется следующим образом.
Граф представляет собой транспортную сеть, узлы которой – вершины , а магистрали – дуги . Для каждого узла задан объем потребления продукта (отрицательное потребление означает – пункт производства, нулевое –перевалочный пункт (не влияет на способ решения задачи). На этом графе необходимо составить план транспортировки с минимальными издержками
Область применения метода ДП. Понятия и определения, связанные с динамическими процессами.
Динамическое программирование – метод оптимизации, приспособленный к операциям, в которых процесс принятия решений может быть разделен на отдельные этапы (шаги)
Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико.
Метод динамического программирования сверху — это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем. Динамическое программирование снизу включает в себя переформулирование сложной задачи в виде рекурсивной последовательности более простых подзадач.
Общая постановка задачи динамического программирования формулируется следующим образом. Имеется некоторая управляемая система , характеризующаяся определенным набором параметров. В этой системе происходят какие-то процессы (экономические, производственные, технологические и т.п.), которые можно представить как многошаговые. На каждом шаге процессам в системе соответствуют определенные значения параметров, описывающих состояние системы. Заданы условия, позволяющие определять или начальное, или конечное состояние системы, или оба этих состояния. Иногда задаются области начальных и конечных состояний. Поскольку управление системой осуществляется для достижения конкретной цели, то указан показатель эффективности управления, называемый целевой функцией, численно выражающий эффект («выигрыш»), получаемый при тот или ином управлении из множества допустимых управлений.
В экономических системах целевая функция может определять прибыль, затраты, рентабельность, объем производства и т.п….