Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 3.3. ДВОЙСТВЕННАЯ ЗАДАЧА ГЕОМЕТРИЧЕСКОГО ПРОГРАММИРОВАНИЯЧрезвычайно интересным и практически важным приложением теории двойственности является ее применение в ГП. Используя теорию двойственности, мы сведем довольно сложную форму задачи ГП, выведенную в гл. 1., к эквивалентной задаче, решить которую намного легче. Эквивалентная задача. В гл. 1 была выведена следующая задача ГП:
при условии
где
Цель данного параграфа — показать, что решение этой задачи ГП при определенных условиях эквивалентно, решению следующей задачи:
при условиях
Здесь Следует обратить внимание на то, что целевая функция в гл. 8, решается значительно легче, чем задача (1.6) или (3.10). Ниже показано, что, как только решена задача (3.11), оптимальные значения
Построение двойственной задачи ГП. Теперь необходимо показать, как из задачи (3.10) получить задачу (3.11). Прежде всего должна быть доказана выпуклость функций Напомним, что, так как выпуклая функция представляет собой вогнутую функцию, взятую со знаком минус, функция будет выпуклой, если матрица Гесса из вторых частных производных положительно полуопределена. Матрица
Лемма 3.1. Пусть Доказательство состоит в том, что будет показана непрерывность и положительная полуопределенность гессиана. Положим
Тогда
Поэтому для любых
где последнее равенство следует из того, что если Следует обратить внимание на то, что
Поэтому
Отсюда
Следовательно,
Применяя лемму 3.1, убеждаемся, что функции получим, что задача, двойственная к (3.10), принимает вид
при
Из уравнения
при
Теперь мы должны преобразовать задачу (3.13) к форме (3.11). Основная трудность в выполнении этого преобразования заключается в том, что не определен у, для которого Предложение 3.2. Пусть
Доказательство. В силу того, что точка
Поэтому справедливо (а). Чтобы доказать (б), суммируем (3.14)
Но
Если
Умножая на
Далее, применяя пункт (б) настоящего утверждения, получаем, что справедливо уравнение (3.15), следовательно, и (в). Из предложения 3.2 вытекает, что мы можем записать двойственную задачу (3.13) в виде: найти
где Следует обратить внимание на то, что задача (3.16) совпадает с задачей (3.11) во всем, за исключением ограничений
Теперь покажем, что в действительности эти ограничения излишни. Напомним, что согласно предположению о том, что Теорема 3.3. Пусть существует
Тогда, если Доказательство. Не теряя общности, можно предположить, что
Обратите внимание также на то, что если точка 6 оптимальна для (3.16), то она допустима для задачи (3.11). Теперь пусть
Сначала установим, что точка
Полагая
и учитывая, что
Отсюда
так как согласно (3.22)
Тогда из (3.19) — (3.23) следует, что точка В силу того, что 6 — оптимальная точка для задачи (3.16), а точка
Далее, переходя к пределу и замечая, что
Замечания. Теорема 3.3 утверждает, что некоторые из оптимальных точек задачи (3.11) являются оптимальными и для задачи (3.16). Требование существования Используя теорему 3.3, мы можем обосновать утверждения, сделанные в первой части этого параграфа. Именно при умеренных предположениях теория двойственности обеспечивает, что задача (3.10) и двойственная к ней задача (3.13) имеют решения и оптимальные значения целевых функций этих задач равны. Тогда, решив задачу (3.11), мы тем самым определим оптимальное значение целевой функции для задачи (3.13), а следовательно, и для задачи ГП. Теорема 3.3 дает также следующее. Существует оптимальная точка возможность определить оптимальные значения х и у для задачи
Эта формула представляет собой ограничения задачи (3.16), так что точки Таким образом, при соответствующих предположениях, решая задачу (3.11) и определяя
|
1 |
Оглавление
|