Cтраница 1
Двойственные алгоритмы оперируют оптимальными решениями двойственной задачи для коррекции начального недопустимого потока. Идея двойственного алгоритма Басакера - Гоуэна состоит в последовательном наращивании потока из источника в сток до требуемой величины, начиная от нулевого потока. Каждый новый поток образуется из предыдущего за счет наращивания потока вдоль кратчайшего пути из источника в сток в графе приращений. [1]
Если применить двойственный алгоритм для примера 2.3, то получим тот же результат, что и для прямого алгоритма: двойственный алгоритм дает то же решение, что и прямой, и, следовательно, сколь угодно сильно отличающееся от оптимального. [2]
Итак, двойственный алгоритм решения задачи ( 5) состоит из двух частей. [3]
В заключение этого параграфа отметим преимущество решения с помощью двойственного алгоритма, несвойственное прямым методам. Любой итеративный алгоритм будет производить последовательность значений и, и1, сходящуюся к значению и, которое является решением двойственной. [4]
Поскольку в линейных подзадачах больше неравенств, чем неизвестных, для их решения наиболее эффективным является двойственный алгоритм. Сходный комментарий приложим и к координирующей задаче, поскольку ее главная трудность обычно состоит в наличии большого числа ограничений. Метод проекций градиента Розена [4] является, следовательно, весьма подходящим для решения координирующей задачи, так как он представляет собой двойственный метод, эффективность которого зависит в основном от числа переменных в задаче и только косвенным образом от числа ограничений. Этот метод может быть также использован для решения линейных подзадач. В [4] показано, что метод проекций градиента будет сходиться к глобальному решению задачи с выпуклой целевой функцией и линейными ограничениями при стремлении числа итерацией и линей-нечности. В работе [5] описывается модификация этого метода, которая продемонстрировала в численных экспериментах более быструю сходимость. [5]
Если применить двойственный алгоритм для примера 2.3, то получим тот же результат, что и для прямого алгоритма: двойственный алгоритм дает то же решение, что и прямой, и, следовательно, сколь угодно сильно отличающееся от оптимального. [6]
Двойственные алгоритмы оперируют оптимальными решениями двойственной задачи для коррекции начального недопустимого потока. Идея двойственного алгоритма Басакера - Гоуэна состоит в последовательном наращивании потока из источника в сток до требуемой величины, начиная от нулевого потока. Каждый новый поток образуется из предыдущего за счет наращивания потока вдоль кратчайшего пути из источника в сток в графе приращений. [7]
Вторая подзадача.| Третья подзадача. [8] |
При решении задачи (14.15) или ее модификаций с помощью рассмотренных до сих пор методов отсечений пытаются аппроксимировать допустимую область F. В двойственном алгоритме отсечений вместо этого используется функция Лагранжа и двойственная задача. [9]
Термин прямой, примененный к алгоритму целочисленного программирования, обозначает метод, который приводит к оптимальному решению посредством получения последовательно улучшаемых решений. Одним из вероятных достоинств прямого алгоритма является возможность прервать вычисления, до того как получено оптимальное решение, и использовать наилучшее из полученных решений как приближенное. Кроме того, можно использовать прямой алгоритм в соединении с двойственными алгоритмами, чтобы получать различные составные алгоритмы, которые могут переходить от фазы, дающей двойственно допустимые решения, к фазе, дающей прямо допустимые решения. [10]