Cтраница 3
Когда же эти границы совпадут, то yr l дает решение координирующей задачи. При изложении метода мы молчаливо предполагали, что подзадача i имеет оптимальное решение, и что существует вектор оптимальных двойственных переменных. [31]
Уо) является оптимальным, состоит в том, что у0 решает координирующую задачу, причем ни одно из линейных ограничений не выполняется как равенство. [32]
Центр анализирует предлагаемые элементами варианты работы, или, другими словами, решает координирующую задачу. В результате решения этой задачи центр или приходит к выводу, что на основе уже переданных вариантов можно получить оптимальное решение, или формирует новый координирующий сигнал, который посылается элементам и позволяет найти новые эффективные точки. [33]
Теперь оптимальным решением становится точка 4, которая уже включена в оптимальное решение суженной координирующей задачи. Следовательно, эта точка преобразует ( 11) в равенство, и текущее проверяемое решение является истинным оптимумом. [34]
На каждой итерации, на которой не удовлетворяется критерий оптимальности, уменьшается целевая функция координирующей задачи f ( y), либо обнаруживается альтернативный оптимальный базис в одной или более подзадачах. [35]
Вначале остановимся на самостоятельной проблеме решения задач дробно-линейного программирования, а затем рассмотрим новый подход к координирующей задаче. [36]
Сравнение с ( 4) показывает, что задача Р2 в процедуре Бен-дерса и двойственная к координирующей задаче в схеме декомпозиции являются идентичными. Задача МР2 двойственная к сокращенной координирующей задаче, содержащей только подмножество допустимых столбцов. Пусть ( у, У) - двойственные переменные, соответствующие оптимальному решению некоторой сокращенной координирующей задачи. [37]
Как и в § 7.6, здесь немедленно оцениваются верхние и нижние границы минимального значения целевой функции координирующей задачи. [38]
Все вычисления осуществляются в соответствии с процедурой одновременного решения прямой и двойственной задач с учетом факта, что координирующая задача имеет колоссальное количество столбцов, которые не могут быть заданы в явном виде. [39]
В статье [174] демонстрируются два основных принципа, которые используются для получения некоторых базисных алгоритмов решения так называемой координирующей задачи. Эти алгоритмы состоят в решении последовательности вспомогательных задач, чьи решения сходятся к оптимальному решению координирующей задачи. Делая частные выборы для вспомогательных задач, можно получить или классические алгоритмы ( градиентный, Ньютона, Уд завы) или двухуровневые алгоритмы декомпозиции. Дается систематический способ получения новых алгоритмов. [40]
Однако если это ограничение является жестким в точке оптимума, необходимо осуществить проверку, является или нет решение координирующей задачи неограниченным. При использовании прямого симплекс-метода ответ на этот вопрос мы получаем в процессе вычислений. [41]
В ( 23) uja есть вектор двойственных переменных, соответствующих i -му множеству ограничений ( 21) в оптимуме координирующей задачи. [42]
Существует более усложненный вариант алгоритма решения сепа-рабельных задач, при котором сходимость обычно ускоряется, однако за счет увеличения размерности суженной координирующей задачи. По существу, это та же постановка, которая была приведена для задач сепарабельного программирования в разд. [43]
Используя начальный базис из двух дополнительных переменных и 1 ] ( вес, ассоциированный с х), решить начальную сокращенную координирующую задачу. Учтите, что у входит линейно и по у нет необходимости в линеаризации. [44]
Вместе с тем вторая фаза ( генерация столбцов) может быть применена и для решения иных проблем, не связанных с построением координирующей задачи. Такие проблемы могут возникать в различных ситуациях и обычно не поддаются решению без использования специальных приемов, поскольку число переменных в них доходит до многих миллионов. В данной главе рассматривается ряд подобных проблем. [45]