Eng | Rus | Ukr | |||||||
Исследование операций
|
24.12.2008
|
||||||
10.5. МЕТОД ДЕКОМПОЗИЦИИ НА ОСНОВЕ агрегирования в ЗАДАЧАХ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯЗадача квадратичного программированияРассмотрим теперь метод декомпозиции на основе агрегирования для блочных задач квадратичного программирования. Такие задачи можно получить из (10.4.55)-(10.4.58) путем введения в целевую функцию квадратичных членов и имеют следующий вид : максимизировать (10.5.1) при ограничениях (10.5.2) при при (10.5.3) . (10.5.4) Матрицы по предположению симметричны и им соответствуют отрицательно определенные квадратичные формы. Для задачи (10.5.1)-(10.5.4) рассмотрим двойственную задачу в виде : минимизировать (10.5.5) при ограничениях (10.5.6) при при (10.5.7) ; ; ; ; . (10.5.8) Введем задачу в агрегированных переменных для (10.5.1)-(10.5.4). Для этого, как и обычно, подставим в (10.5.1)-(10.5.4), считая весовые коэффициенты фиксированными. Получим задачу: максимизировать (10.5.9) при ограничениях ; ; (10.5.10) ; (10.5.11) ; (10.5.12) где к обозначениям (10.4.55) добавлено следующее: . Нетрудно убедиться , что матрица также симметрична и ей соответствует отрицательно определенная квадратичная форма. Двойственная задача к задаче (10.5.9)-(10.5.12) имеет вид: минимизировать (10.5.13) при ограничениях ; (10.5.14) ;;;;;; . (10.5.15) Пусть { } - оптимальное решение задачи (10.5.13)-(10.5.15), которое предполагается единственным. Сформулируем задачи для отдельных блоков, то есть при фиксированных j ( ): максимизировать (10.5.16) при ограничениях ; , (10.5.17) при при . (10.5.18) Двойственные задачи для блочных задач (10.5.16)-(10.5.18) записываются в виде: минимизировать (10.5.19) при ограничениях ; , (10.5.20) при при . (10.5.21) Сформулируем критерий оптимальности промежуточного решения. Пусть при некоторых весовых коэффициентах получено оптимальное решение макрозадачи (10.5.9)-(10.5.12) и единственным двойственным оценкам соответствуют оптимальные решения для отдельных блоков (10.5.16)-(10.5.18). Тогда справедлива следующая теорема (52). Теорема 10.8. Достаточным условием оптимальности дезагрегированного решения для задачи (10.5.1)-(10.5.4) является выполнение равенства (10.5.22) Если задача (10.5.1)-(10.5.4) разрешима, а { } неоптимально для нее, то в соотношении (10.5.22) знак '=' заменяется на знак '>'. Доказательство 10.8 проводится аналогично схеме доказательства теоремы 10.7. Задача выпуклого программированияОбобщим метод декомпозиции на основе агрегирования переменных для блочных сепарабельних задач выпуклого программирования (общая задача выпуклого программирования рассмотрена в гл.5). Пусть имеется задача вида: максимизировать (10.5.23) при ограничениях ; ,, (10.5.24) ;, (10.5.25) ;, (10.5.26) где при каждом фиксированном j вектор xj имеет компоненты { } ; функции fj(xj), предполагаются непрерывно дифференцированными, а их частные производные удовлетворяют условию Липшица. Кроме того, предполагается, что функции fj(xj) - вoгнуты, а - выпуклы. Тогда двойственная задача для задачи (10.5.23) имеет вид: минимизировать (10.5.27) при ограничениях
при (10.5.28) (10.5.29) при ; ; ; 0 ; ; . Вводя агрегированные переменные , и весовые коэффициенты агрегирования при фиксированных , приходим к задаче в агрегированных переменных: (10.5.30) ;; (10.5.31) ;; (10.5.32) ; . (10.5.33) где для удобства обозначено (10.5.34) Нетрудно убедиться , что функции , и являются выпуклыми по переменным xi, . Запишем двойственную задачу для макрозадачи (10.5.30)-(10.5.33): (10.5.35) (10.5.36) где и - множители Лагранжа. Пусть при некоторых весовых коэффициентах получены оптимальные множители Лагранжа { }, для задачи (10.5.35), (10.5.36). Рассмотрим блочные задачи при каждом фиксированном j ( ): , (10.5.37) ; ; ; (10.5.38) Двойственные задачи для блочных задач записываются в виде , (10.5.39) , (10.5.40) , (10.5.41) ; ; Предположим, что задача (10.5.23)-(10.5.26) имеет решение и для нее выполняется условие Слейтера (см.гл.5). Тогда это же условие выполняется и для блочных задач (10.5.37) по ограничениям (10.5.38). То же самое предполагается выполненным и для макрозадачи (10.5.30) для ограничений (10.5.31), (10.5.32), если весовые коэффициенты удовлетворяют условиям ; ; . Рассмотрим критерий оптимальности промежуточного решения для итеративного процесса. Пусть при некоторых значениях получено решение задачи задачи в агрегированных переменных (10.5.30)-(10.5.33) и { }- единственные оптимальные множители Лагранжа, которым соответствуют решения { }, , блочных задач (10.5.37), (10.5.38). Тогда справедливо следующее утверждение [52]. Теорема 10.9. Достаточным условием оптимальности дезагрегированного решения{ } для задачи (10.5.23)-(10.5.26) является выполнение равенства: . (10.5.42) Если же решение { } неоптимально для задачи (10.5.23)-(10.5.26), то в соотношении (10.5.42) знак '=' заменяется на '>'. Доказательство. Дезагрегированное решение допустимо к задаче (10.5.23)-(10.5.26), что устанавливается непосредственной проверкой. Значение целевой функции (10.5.23) для этого решения есть . Пусть , , - оптимальные решения двойственных задач (10.5.39)-(10.5.41). Тогда набор { } удовлетворяет условиям (10.5.28) и (10.5.29) двойственной задачи, что следует из (10.5.40), (10.5.41) и (10.5.36). Иными словами, вектор , является решением задачи о максимизации функционала (10.5.27) при фиксированных множителях Лагранжа { }, { }, равных { }, и . Поскольку между значениями ц.ф. двойственной и прямой задач выполняется неравенство вида , то . (10.5.43) При этом равенство в (10.5.43) обеспечивает оптимальность дезагрегированного решения для задачи (10.5.23)-(10.5.26). При условии разрешимости этой задачи и неоптимальности { } для нее соотношение (10.5.43) выполняется как строгое неравенство. Второе слагаемое левой части неравенства (10.5.43) равняется нулю в силу теоремы Куна-Таккера (условие дополняющей нежесткости в применении к блочным задачам). Отсюда и следует справедливость теоремы 10.9. Таким образом, общий итеративный метод решения блочных задач ЛП на основе агрегирования, рассмотренный в разделе 10.4, обобщается и на задачи квадратичного и выпуклого программирования. Описание алгоритма декомпозиции на основе агрегування
|
|||||||
Copyright © 2002-2004 | |||||||