Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Бурков В.Н. Элементы теории графов
 
djvu / html
 

' j
Любое решение системы неравенств (2)-(3) определяет путь в
сети без контуров (но не в сети с контурами).
Пусть все контуры имеют строго положительную длину, то
есть нет контуров отрицательной и нулевой длины. Тогда решение
задачи (1)-(3) определяет путь кратчайшей длины.
Сформулируем задачу ЛП, двойственную задаче (1)-(3), по-
ставив в соответствие ограничениям (2) двойственные переменные
АО и Я„, а ограничениям (3) - двойственные переменные {Яг-},
i= \,n-\:
(4) Я„ - АО —> max
(5)Я,--Я,- По теореме двойственности линейного программирования [7],
для оптимальных решений задач (1)-(3) и (4)-(5) значения целевых
функций совпадают.
Задача (4)-(5) называется задачей о потенциалах вершин гра-
фа. Общая ее формулировка такова: найти потенциалы вершин
{Яг-}, удовлетворяющие системе неравенств (5) и максимизирую-
щие некоторую функцию Ф(Я), где Я = (Я0, Я/, ..., Я„). Примером
является задача о ближайших потенциалах, в которой
Ф(Я) = 2_, \^j~ hj •> гДе {^°j} могут интерпретироваться как
j
желательные потенциалы.
Аналогично задаче о кратчайшем пути формулируется и ре-
шается задача о максимальном (длиннейшем) пути — достаточно
изменить знаки дуг на противоположные и решить задачу о крат-
чайшем пути. Для существования решения задачи о максимальном
пути необходимо и достаточно отсутствия контуров положитель-
ной длины.
В задаче поиска пути максимальной надежности длины дуг
интерпретируются, например, как вероятности того, что существу-
ет связь между соответствующими двумя пунктами. Заменяя дли-
ны дуг их логарифмами, взятыми с обратными знаками, получаем,
10

 

1 10 11 12 13 14 15 16 17 18 19 20


Математика