Главная > Математика > Конечные графы и сети
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

6.3. Линейное программирование и потоки в сетях

Потоки в сетях будут подробно рассматриваться далее в главе 7. В данном случае будет дано лишь неформальное пояснение основной идеи потока с тем, чтобы продемонстрировать связь задач о потоках с задачами линейного программирования.

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

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

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

<< Предыдущий параграф Следующий параграф >>
Оглавление