6.3. Линейное программирование и потоки в сетях
Потоки в сетях будут подробно рассматриваться далее в главе 7. В данном случае будет дано лишь неформальное пояснение основной идеи потока с тем, чтобы продемонстрировать связь задач о потоках с задачами линейного программирования.
Пусть вершины 
ориентированного графа обозначают источник и сток некоторого вещества, протекающего по дугам. Кроме того, предположим, что дуге из вершины 
в вершину поставлена в соответствие пропускная способность или верхнее ограничение на величину потока 
Наконец, пусть обозначает стоимость
единицы потока по дуге. Теперь задачу о потоке можно представить в виде задачи линейного программирования, в которой требуется минимизировать 
Для общего потока с из 
при условиях
Потоки в сетях иногда оказываются удобным средством решения задачи линейного программирования такого типа, которая известна под названием транспортной задачи.
