1
УДК 519.254
Алгоритмы учета неопределенности информации
при точечном оценивании потоков в сетях
© Ю.Е. Гагарин
КФ МГТУ им. Н.Э. Баумана, Калуга, 248000, Россия
Рассмотрены алгоритмы учета погрешности исходной информации в задачах оп-
тимизации систем, обладающих сетевой структурой. На примере задачи о мак-
симальном потоке показаны особенности применения алгоритмов.
Ключевые слова:
линейное программирование, алгоритмы учета неопределенно-
сти, сетевые структуры, измерения с ошибками, оптимальное решение.
Многочисленные территориально распределенные системы —
транспортные, информационные, энергетические и т. п. — обладают
сетевой структурой. Для описания таких коммуникационных сетей
служит взвешенный граф, ребрам и вершинам которого приписывают
веса, соответствующие пропускным способностям и потребностям.
Формулируемые задачи для взвешенных графов позволяют оценить
значения функционалов, заданных на этих графах, и при фиксиро-
ванных весах вершин синтезировать такие веса на ребрах графа, что-
бы реализовывалось решение между истоками и стоками графа при
достижении экстремума функционала, заданного на множестве ребер
этого графа. Подобные задачи формулируются в терминах линейного
программирования, но удобнее формулировать задачи линейного про-
граммирования в терминах распределения потоков на графах.
Методы линейного программирования являются наиболее эф-
фективными и известными методами решения моделей исследова-
ния операций и применяются в различных областях. Широкое их ис-
пользование подкрепляется высокоэффективными компьютерными
алгоритмами линейного программирования, на которых базируются
алгоритмы более сложных типов моделей и задач исследования
операций, включая целочисленное, нелинейное и стохастическое
программирование.
Условия, в которых определяется оптимальное решение задачи ли-
нейного программирования, находят отражение в момент формирова-
ния модели. В действительности эти условия не остаются неизменными.
Поэтому особое значение приобретает анализ устойчивости, т. е. воз-
можность оценить изменения в оптимальном решении, вызванные из-
менениями в параметрах исходной модели: в коэффициентах целевой
функции, элементах матрицы, составленной из коэффициентов при не-
известных, и в правой части условий-ограничений. Особенно важно
знать, при каких изменениях параметров задачи оптимальное реше-
