Ю.Е. Гагарин
2
ние этой задачи остается неизменным. Параметры задачи линейного
программирования можно варьировать путем изменения условий
функционирования описываемых объектов. Например, в транспорт-
ных моделях может меняться количество транспорта, который пере-
мещается из одного пункта в другой, или пропускная способность
между узлами транспортной сети. Эти изменяющиеся параметры
влекут неопределенность параметров задачи [1].
Параметры задачи линейного программирования могут являться
случайными величинами, и тогда важно знать, как может изменяться
решение задачи в зависимости от изменения исходных данных. При
этом необходимо иметь по крайней мере сведения о математическом
ожидании и дисперсии этих случайных величин, если нет возможности
оценить их функции распределения. В таком случае неопределенно-
стям значений параметров необходимо указать соответствующие дове-
рительные вероятности. Как правило, в подобных случаях для получе-
ния оптимального решения рассматривают серию прямых близких
задач, изменяя значения параметров.
В задаче о максимальном потоке [2] каждая дуга сети характеризу-
ется некоторой пропускной способностью. Пусть узел
s
— источник,
узел
t
— сток,
v
— внешний поток, входящий в сеть в узле
s
и вы-
ходящий из нее в узле
t
. Задачу о максимальном потоке можно запи-
сать как задачу линейного программирования: найти максимум
v
при ограничениях
0,
O
T
i
i
k
k
k M k M
f
f
, ;
i N s t
0;
O
T
i
i
k
k
k M k M
f
f
v
0;
O
T
i
i
k
k
k M k M
f
f
v
0
;
r
v v
0
k
k
f
c
,
,
k M
где
M
— список дуг;
,
i
O
i
T
— набор начальных и конечных узлов
соответственно;
k
f
— поток по дуге
k
;
N
— множество узлов;
k
c
—
пропускная способность дуги
k
(определяет верхнюю границу потока
по дуге).
В стандартной постановке задачи о максимальном потоке поток
сохраняется при прохождении по дугам сети. Если
k
f
является пото-
ком в начале дуги ,
k
а
k
f
— в ее конце, то
.
k
k
f
f
