2015-04-30
3596
Задачу о максимальном потоке можно сформулировать как задачу линейного программирования (ЗЛП). Однако, решение сетевых задач симплекс-методом не целесообразно. С другой стороны, изучение формулировок сетевых задач как ЗЛП помогает идентифицировать модели ЛП, которые на первый взгляд не являются сетевыми, но которые либо непосредственно, либо с некоторыми модификациями можно свести к сетевым. Преимущество такого подхода состоит в том, что при использовании сетевых постановок эффективность вычислений может значительно увеличиться.
Построим математическую линейную модель задачи о максимальном потоке.
Переменные модели
Пусть хij – поток, пропускаемый через дугу (i; j), т.е. переменные линейной модели сопоставляются каждой дуге сетевой модели.
Целевая функция
Целевая функция модели должна формализовать цель задачи – поток, вышедший из истока должен быть максимальным. Суммарный поток, вышедший из истока S/, согласно введенных переменных равен 
, где суммирование ведется по всем дугам, начинающимся в истоке S/. Тогда целевая функция может быть записана в виде:
|
|
|
Система ограничений
Согласно технико-экономическому смыслу введенных переменных на них должны быть наложены следующие ограничения.
1. Суммарный поток, вышедший из истока S/, равен суммарному потоку, вошедшему в сток S//. Математически это можно записать так:
.
2. Для любой промежуточной вершины сети k суммарный поток, вошедший в нее, равен суммарному потоку, вышедшему из нее. Математически это записывается следующим образом:
.
3. Из определения понятия потока в сети следует условие:
,
где 
- пропускная способность дуги (i; j).
Таким образом, математическая линейная модель задачи о максимальном потоке будет иметь вид:
(4.12)
