Двойственный алгоритм - Большая Энциклопедия Нефти и Газа, статья, страница 1
Длина минуты зависит от того, по какую сторону от двери в туалете ты находишься. Законы Мерфи (еще...)

Двойственный алгоритм

Cтраница 1


Двойственные алгоритмы оперируют оптимальными решениями двойственной задачи для коррекции начального недопустимого потока. Идея двойственного алгоритма Басакера - Гоуэна состоит в последовательном наращивании потока из источника в сток до требуемой величины, начиная от нулевого потока. Каждый новый поток образуется из предыдущего за счет наращивания потока вдоль кратчайшего пути из источника в сток в графе приращений.  [1]

Если применить двойственный алгоритм для примера 2.3, то получим тот же результат, что и для прямого алгоритма: двойственный алгоритм дает то же решение, что и прямой, и, следовательно, сколь угодно сильно отличающееся от оптимального.  [2]

Итак, двойственный алгоритм решения задачи ( 5) состоит из двух частей.  [3]

В заключение этого параграфа отметим преимущество решения с помощью двойственного алгоритма, несвойственное прямым методам. Любой итеративный алгоритм будет производить последовательность значений и, и1, сходящуюся к значению и, которое является решением двойственной.  [4]

Поскольку в линейных подзадачах больше неравенств, чем неизвестных, для их решения наиболее эффективным является двойственный алгоритм. Сходный комментарий приложим и к координирующей задаче, поскольку ее главная трудность обычно состоит в наличии большого числа ограничений. Метод проекций градиента Розена [4] является, следовательно, весьма подходящим для решения координирующей задачи, так как он представляет собой двойственный метод, эффективность которого зависит в основном от числа переменных в задаче и только косвенным образом от числа ограничений. Этот метод может быть также использован для решения линейных подзадач. В [4] показано, что метод проекций градиента будет сходиться к глобальному решению задачи с выпуклой целевой функцией и линейными ограничениями при стремлении числа итерацией и линей-нечности. В работе [5] описывается модификация этого метода, которая продемонстрировала в численных экспериментах более быструю сходимость.  [5]

Если применить двойственный алгоритм для примера 2.3, то получим тот же результат, что и для прямого алгоритма: двойственный алгоритм дает то же решение, что и прямой, и, следовательно, сколь угодно сильно отличающееся от оптимального.  [6]

Двойственные алгоритмы оперируют оптимальными решениями двойственной задачи для коррекции начального недопустимого потока. Идея двойственного алгоритма Басакера - Гоуэна состоит в последовательном наращивании потока из источника в сток до требуемой величины, начиная от нулевого потока. Каждый новый поток образуется из предыдущего за счет наращивания потока вдоль кратчайшего пути из источника в сток в графе приращений.  [7]

8 Вторая подзадача.| Третья подзадача. [8]

При решении задачи (14.15) или ее модификаций с помощью рассмотренных до сих пор методов отсечений пытаются аппроксимировать допустимую область F. В двойственном алгоритме отсечений вместо этого используется функция Лагранжа и двойственная задача.  [9]

Термин прямой, примененный к алгоритму целочисленного программирования, обозначает метод, который приводит к оптимальному решению посредством получения последовательно улучшаемых решений. Одним из вероятных достоинств прямого алгоритма является возможность прервать вычисления, до того как получено оптимальное решение, и использовать наилучшее из полученных решений как приближенное. Кроме того, можно использовать прямой алгоритм в соединении с двойственными алгоритмами, чтобы получать различные составные алгоритмы, которые могут переходить от фазы, дающей двойственно допустимые решения, к фазе, дающей прямо допустимые решения.  [10]



Страницы:      1