3.3. ДВОЙСТВЕННАЯ ЗАДАЧА ГЕОМЕТРИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Чрезвычайно интересным и практически важным приложением теории двойственности является ее применение в ГП. Используя теорию двойственности, мы

сведем довольно сложную форму задачи ГП, выведенную в гл. 1., к эквивалентной задаче, решить которую намного легче.

Эквивалентная задача. В гл. 1 была выведена следующая задача ГП:

при условии

где

— переменные, — фиксированный -мерный вектор, — фиксированная матрица размером

Цель данного параграфа — показать, что решение этой задачи ГП при определенных условиях эквивалентно, решению следующей задачи:

при условиях , где

Здесь — вектор, входящий в задачу Чтобы обеспечить непрерывность выражения в точке мы принимаем, что Тогда функция непрерывна при .

Следует обратить внимание на то, что целевая функция вогнута (упр. 3.2). Следовательно, задача (3.11) является задачей НЛП с вогнутой целевой функцией и линейными ограничениями и, как показано

в гл. 8, решается значительно легче, чем задача (1.6) или (3.10).

Ниже показано, что, как только решена задача (3.11), оптимальные значения в задачах (1.6) и (3.10) могут быть определены по известным оптимальным значениям с помощью соответствующих формул (упр. 3.3):

Построение двойственной задачи ГП. Теперь необходимо показать, как из задачи (3.10) получить задачу (3.11). Прежде всего должна быть доказана выпуклость функций Это позволит использовать теорию двойственности.

Напомним, что, так как выпуклая функция представляет собой вогнутую функцию, взятую со знаком минус, функция будет выпуклой, если матрица Гесса из вторых частных производных положительно полуопределена. Матрица положительно полуопределена, если для любого данного вектора или эквивалентно

Лемма 3.1. Пусть Тогда выпуклая функция.

Доказательство состоит в том, что будет показана непрерывность и положительная полуопределенность гессиана. Положим

Тогда

Поэтому для любых

где последнее равенство следует из того, что если то

Следует обратить внимание на то, что

Поэтому

Отсюда

Следовательно,

Применяя лемму 3.1, убеждаемся, что функции выпуклы. Перестроив вогнутую двойственную задачу гл. 2 для выпуклых функций,

получим, что задача, двойственная к (3.10), принимает вид

при

Из уравнения кроме того, после введения переменной двойственная задача сводится к нахождению

при

Теперь мы должны преобразовать задачу (3.13) к форме (3.11). Основная трудность в выполнении этого преобразования заключается в том, что не определен у, для которого или эквивалентно, не определен Поэтому данный случай требует специального рассмотрения.

Предложение 3.2. Пусть -допустимая точка для задачи (3.13). Тогда

Доказательство. В силу того, что точка допустима для задачи (3.13), имеем

Поэтому справедливо (а).

Чтобы доказать (б), суммируем (3.14)

Но и поэтому справедливо (б). Утверждение (в) доказывается тем, что будет показано:

Если по и (3.15) удовлетворяется. Пусть тогда из Отсюда опять на основе (3.14) имеем

Умножая на и суммируя, получаем

Далее, применяя пункт (б) настоящего утверждения, получаем, что справедливо уравнение (3.15), следовательно, и (в).

Из предложения 3.2 вытекает, что мы можем записать двойственную задачу (3.13) в виде: найти при

где

Следует обратить внимание на то, что задача (3.16) совпадает с задачей (3.11) во всем, за исключением ограничений

Теперь покажем, что в действительности эти ограничения излишни. Напомним, что согласно предположению о том, что функция непрерывна при

Теорема 3.3. Пусть существует такое, что

Тогда, если —оптимальная точка для задачи (3.16), то она оптимальна также и для задачи (3.11).

Доказательство. Не теряя общности, можно предположить, что

Обратите внимание также на то, что если точка 6 оптимальна для (3.16), то она допустима для задачи (3.11).

Теперь пусть произвольная допустимая точка для задачи (3.11). Чтобы доказать теорему, мы должны показать, что а (6), так как это означает, что точка оптимальна для (3.11). Построим последовательность

Сначала установим, что точка допустима для задачи (3.16). Согласно выбору точек получаем

Полагая

и учитывая, что можно определить

Отсюда

так как согласно (3.22)

Тогда из (3.19) — (3.23) следует, что точка допустима для задачи (3.16).

В силу того, что 6 — оптимальная точка для задачи (3.16), а точка допустима, получаем

Далее, переходя к пределу и замечая, что а функция и (8) непрерывна, получаем

Замечания. Теорема 3.3 утверждает, что некоторые из оптимальных точек задачи (3.11) являются оптимальными и для задачи (3.16). Требование существования здесь может рассматриваться как условие регулярности.

Используя теорему 3.3, мы можем обосновать утверждения, сделанные в первой части этого параграфа.

Именно при умеренных предположениях теория двойственности обеспечивает, что задача (3.10) и двойственная к ней задача (3.13) имеют решения и оптимальные значения целевых функций этих задач равны. Тогда, решив задачу (3.11), мы тем самым определим оптимальное значение целевой функции для задачи (3.13), а следовательно, и для задачи ГП.

Теорема 3.3 дает также следующее. Существует оптимальная точка для задачи (3.16), именно в теореме 3.3, которая является оптимальной и для задачи (3.11). При наличии этой точки мы имеем

возможность определить оптимальные значения х и у для задачи с помощью формулы

Эта формула представляет собой ограничения задачи (3.16), так что точки удовлетворяют им.

Таким образом, при соответствующих предположениях, решая задачу (3.11) и определяя , мы получаем решение задачи ГП.