Задача выбора пропускных способностей и распределения потоков (впс и рп).

Ранее были даны оптимальные решения задач ВПС и РП. Объединив эти задачи в задачу ВПС и РП, мы не сможем найти глобально оптимальные решения, но зато опишем процедуры поиска локальных минимумов для .

Так как нужно опять выбирать , то представляется, что фиксированные процедуры выбора маршрутов также должны быть оптимальными. Известно, что в случае линейных стоимостных функций ( ) фиксированные процедуры выбора маршрутов являются оптимальными; это справедливо в силу свойства вогнутости . Кроме того, как можно показать, локальные минимумы получаются на потоках по кратчайшим маршрутам (подкласс потов, направленных фиксированной процедурой выбора маршрутов), так как минимумы должны располагаться в узлах выпуклого многогранника реализуемого множества потоков.

Подход к отысканию этих локальных минимумов состоит в том, чтобы начиная с реализуемого начального потока получить оптимальный набор пропускных способностей при линеаризованных стоимостях, с помощью алгоритма ОП найти оптимальные потоки, повторить решение задачи ВПС для этих новых потоков и продолжать итерации к решениям задачи ВПС и задачи РП до отыскания (локального) минимума. Заметим, в частности, что алгоритм ОП будет особенно простым в этом случае, так как значение всегда будет равно единице (поток, направленный фиксированной процедурой выбора маршрутов). Таким образом, при известном реализуемом начальном потоке алгоритм состоит в следующем:

ПОДОПТИМАЛЬНЫЙ АЛГОРИТМ ВПС И РП.

1. Положить .

2. Выполнить алгоритм ВПС для потока и найти оптимальное множество пропускных способностей, используя линеаризованные стоимости.

3. Используя длины , выполнить алгоритм ОП при на каждом шаге. Полученный в результате оптимальный поток обозначается через .

4. Если для больше либо равен для , то STOP; поток дает локальный минимум. В противном случае положить и прейти к шагу 2.

Алгоритм сходится, так как имеется лишь конечное число потов по кратчайшим маршрутам.

При этом ( из формулы ) задается равенством:

.

Отсюда следует, что и отрицательные циклы существовать не могут

(что требует алгоритм отыскания кратчайших путей). Заметим, что это значит, что если в итерации поток ( и, следовательно, пропускная способность) обращается в нуль, то как поток, так и пропускная способность, остаются нулевыми при последующих итерациях, так как добавочная стоимость размещения потока становится бесконечной и отклоняемый поток превысит нулевую пропускную способность.

Теперь перед нами стоят 2 задачи: 1). найти реализуемый начальный поток и 2). Просматривая многие локальные минимумы отыскать глобальный минимум. Решим обе задачи, повторяя алгоритм ВПС и РП для многих различных начальных реализуемых потоков. Каждый начальный реализуемый поток находится путем случайного назначения каналам исходных длин. Для каждого назначения затем выполняется алгоритм отыскания потоков по кратчайшим путям, использующий выбранные таким образом длины, и проверка условия для этого потока. Если условия удовлетворяются, то найдем реализуемый начальный поток и можем приступить к алгоритму ВПС и РП, в противном случае исходный поток отвергается и делается попытка случайного назначения множества других длин. Так как алгоритм ВПС и РП устраняет некоторые каналы при итерациях, приводящих к (локальным) минимумам, то его можно использовать как вспомогательное средство при топологическом проектировании сетей (то есть в задаче ВТПС и РП).

Задачу ВПС и РП можно сформулировать в двойственной форме:

Дано:	топология сети.
Минимизировать:	.
Варьируются:	{ }и { }.
Ограничение:	.

Описанный выше алгоритм ВПС и РП применим к этой двойственной задаче, если заменить определение длины новым определением .

При линейной ( ) стоимостной функции пропускных способностей выражения для и идентичны ранее полученным для и (получаются таким же способом).