Cтраница 2
Оптимальные двойственные оценки удовлетворяют всем условиям двойственной задачи. При этом минимальное значение целевой функции двойственной задачи, равное F nn 12 - ( 5 / 7) 17 - 0 4 - ( 6 / 7) 12, совпадает с максимальным значением целевой функции Рта исходной задачи. [16]
Возникают ли ситуации, когда соответствующее решение двойственной задачи перестает быть допустимым. Какие значения принимает при этом целевая функция двойственной задачи. [17]
Предполагая, как и прежде, что оптимальное решение невырожденно, допустим теперь, что имеет место единичное увеличение как Si, так и DJ. Можно показать, что к целевой функции добавляется величина vt Wj, это вытекает из рассмотрения целевой функции двойственной задачи. [18]
Если, например, один из них будет опущен ( для него /, 0), то на следующем цикле, если соответствующий множитель 7Ч отрицателен, новое число k будет равно нулю. Такая итерация, вообще говоря, является излишней в том смысле, что в результате ее осуществления значение целевой функции двойственной задачи не возрастает. Если новые оптимальные значения функции равны нулю, то не требуется решать новые подзадачи, и новая ограниченная координирующая задача находится на основе полученного решения. [19]
Вычислительный процесс при этом организуется иначе: вместо минимизации функции L в пространстве переменных п ведется поиск максимума этой функции по переменным X. Такую замену называют переходом от решения прямой задачи к решению сопряженной с ней двойственной задачи. В теории выпуклого программирования доказывают теоремы, позволяющие из формулировки прямой задачи по стандартным правилам составить соответствующую ей двойственную. В общем случае часть целевой функции двойственной задачи, от которой зависят координаты максимума, представляет собой функцию Лагранжа прямой задачи, а вместо ограничений я / ( А) 0 в прямой задаче выступают ограничения (22.10) в двойственной. [20]
С точки зрения условия 2 двойственные методы уступают прямым методам. Это прежде всего относится к двойственному симплекс-методу, для которого отсутствуют процедуры, основанные на использовании неоптимальных решений. Метод одновременного решения прямой и двойственной задач эффективнее в том смысле, что допускает использование различных вариантов оптимальных решений подзадач для генерации столбцов новой ограниченной координирующей задачи. Однако использование околооптимальных решений здесь не дает преимущества, в отличие от прямых методов. Кроме того, как уже отмечалось, если не используются все варианты оптимальных решений, значение целевой функции двойственной задачи может на следующей итерации не возрасти. Таким образом, теряется гибкость, присущая прямым методам. [21]