Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

2.3. Оптимальные решения при ограничениях неравенствах. Теорема Куна-Таккера

Изученные особенности функции Φ(Х, Λ) позволяют сформулировать положения, относящиеся непосредственно к нелинейным задачам математического программирования. Пусть дана задача: найти

(2.6)

Все предположения относительно z и gi (i = 1,...,m), выдвинутые выше, сохраняются здесь полностью. Требуется получить условия существования решений, основанные на введенных понятиях.

Чтобы избежать неудобств, связанных с присутствием в (2.6) ограничений-неравенств и требований не отрицательности переменных xj, представим (2.6) в эквивалентной форме

(2.7)

где xui, xmi, xwj≥0 - вспомогательные переменные, позволяющие формально исключить знаки "≤, ≥", из (2.6). Для этого случая функция Лагранжа запишется как


а необходимые условия, которым должны удовлетворять оптимальные x°j, λ°i, принимают обычный вид

(∂Φ̃/∂xj)° = 0, (∂Φ̃/∂λi)° = 0 (j = 1,...,n; i = 1,....,m).

Рассмотрим более подробно равенства (д∂Φ̃/∂xj)° = 0 (j = 1,...,n). Их можно представить как

(2.8)

собрав под знаком Σ производные по первых двух сумм выражения Φ. Ясно, что появление здесь слагаемого λ°j есть следствие перехода от системы (2.6) к (2.7). Обратим теперь внимание на то, что в левую часть (2.8) входит выражение производной по xj функции

Φ (X, Λ) = f(X) + Σi λi[bi-gi].

т. е. функции Лагранжа в ее классическом виде (см. п. 2.1). Для составления Φ(Х, Λ) достаточно данных исходной задачи (2.6), поэтому естественно стремиться сформулировать такие условия существования экстремума f(X), которые включали бы только Φ(Х, Λ), а не Φ̃.

Обратим внимание на множитель λ̄°j, связанный с о-й искусственной строкой (2.7) и обладающий свойством λ̄°jwj = 0. При x°wj≥0 (или, что то же, при x°j≥0) он обращается в нуль, и необходимые условия существования Х° (из рассматриваемых в данный момент) принимают вид


Далее, при х°wj = 0 (это равносильно равенству x°j = 0, так как x°j-x°wj = 0) соответствующий множитель λ̄°j отличен, вообще говоря, от нуля. Его знак в этом случае определяется из следующих соображений: если правой части любой строки xj-xwj=0 дать отрицательное приращение, то область определения исследуемой задачи только расширится (произвольное значение хj≥0 удовлетворяет и неравенству xj≥bwj, bwj<0); величина z° при этом не уменьшится (всякое расширение U создает предпосылки для улучшения ожидаемых z°), т. е. dz°/dbwj≤0 или λ°j≤0. Таким образом, при x°j = 0 необходимые условия есть


Обращаясь теперь к группе соотношений (∂Φ̃/∂λi,)λ°i = 0 (i = 1,...,m) и применяя те же способы оценки знаков λ°i, можно получить объединенную сводку искомых необходимых условий, которым должны удовлетворять оптимальные x°j, λ°i (j = 1,...,n; i = 1,....,m) в рассматриваемой задаче (2.6):

(2.9)

Следует специально подчеркнуть, что соотношения (2.9) должны рассматриваться лишь тогда, когда существуют такие при которых ∂Φ/∂λi, т. е. gi(X)<bi (i = 1,...,u) gi(X) > bi (t = u+1,....,m); в противном случае возникает неопределенность выбора λi (нарушается условие регулярности ограничений (2.6), множество компонент Λ становится неограниченным), и равенства λ°i(∂Φ/∂λi)° = 0 теряют смысл.

Очевидно, требования (2.9) полностью совпадают с (2.5) при Х≥0, причем соответствие результатов распространяется и на достаточные условия существования Х°, Λ°.

Пусть точка Х°, Λ°, удовлетворяющая (2.9), является седловой для Φ(Х, Λ); следовательно, должно выполняться неравенство


В силу (2.9) (сумма


равна нулю, а каждое слагаемое суммы


неотрицательно поскольку знаки разностей bi-gш(X) в (2.6) и соответствующих λ°i в (2.9) всегда совпадают. Таким образом, приходим к утверждению "f(X) + (неотрицательная величина) "f(Х°)" и тем более f(X)≤f(X°). Этим подтверждается достаточность исходного предположения.

Проведенный анализ свойств экстремума z в задаче (2.6) позволяет дать краткую формулировку теоремы Куна - Таккера: для того, чтобы экстремум функции f (X) был достигнут в точке Х°=(x°1, х°2, ..., х°n) при условиях (2.6), необходимо и достаточно требовать существования таких (i = 1,...,u), λ°i≤0 (i = u+1,....,m) при которых Х°, Λ° является седловой точкой функции (Х, Λ).

Заметим теперь, что теорема Куна - Таккера, отражающая роль седловой точки Х°, Λ°, может рассматриваться с более общих позиций, вне связи с предположениями о дифференцируемости Φ(Х, Λ).

Пусть, например, в задаче (2.6) отсутствуют требования существования производных df(X)/dxj, dgi(X)/dxj и некоторая точка X*, Λ* является седловой для функции


на множестве U, причем λi≥0 (i = 1,....,u), λi≤0, (i = u+1,....,m). Нетрудно убедиться, что эти условия являются достаточными условиями экстремума (в данном случае максимума). Действительно, из определения седловой точки (см. § 2.2) следует Φ(Х, Λ*) ≤ Φ(Х*, Λ*) ≤ Ф(Х*, Λ); правое неравенство есть


поскольку знаки λi* совпадают со знаками соответствующих разностей bi-gi(X*), и кроме того, рассматриваемое неравенство выполняется для всех допустимых λi (в частности, для ∀ λi=0 i=1,....,m), получаем


в этой ситуации левое неравенство принимает вид f(X) + (неотрицательная величина) f(X*) или f(X)≤f(X*), что и подтверждает оптимальность Х*.

Т образом, использование производных функции Φ(Х, Λ) в ходе доказательств теорем о существовании экстремума совсем не обязательно, однако в инженерных задачах оно часто приводит к упрощениям расчетов.

В заключение полезно подвести некоторые итоги: исследована проблема обобщения классического метода множителей Лагранжа на случай ограничений вида gi(X)≤bi и Х≥0 в задачах нелинейного программирования; показана возможность такого обобщения и изучены особенности функции Лагранжа Φ(Х, Λ) в точке относительного экстремума f(X); установлена связь между условиями существования точек Х° и Х°, Λ°, выраженная теоремой Куна - Таккера. Ниже дан пример непосредственного использования полученных результатов.

Пример: найти x1, х2 → max {z = -10(x1-2)2-20(x2-3)2} при x1+x2≤6, x1-x2≤1, 2x12≥6, x1/2-х2≥-4; х1, х2 ≥ 0.

Решение: составим функцию Лагранжа в ее классическом виде (так, как это было бы в случае ограничений-равенств и отсутствия требований не отрицательности х1, х2):


Из условий x°j (Φ'xj)j = 0 (j = 1, 2) и λ°i (Φ'xj)λ°i = 0 (i = 1,...,4) получаем


Среди возможных решений этой системы нужно выбрать теперь те, которые удовлетворяют соотношениям (2.9). Оказывается, этим свойством обладает одно решение: x*1 = 2, x*2 = 3, λ1* = λ*2 = λ3* = = λ*4 = 0; тот факт, что все λi* - оказались равными нулю, a x*1,2>0, указывает на несущественность исходных ограничений задачи; проверка достаточных условий сводится к установлению факта выпуклости z (это можно сделать здесь простыми геометрическими построениями).

Теория Куна - Таккера позволяет заметно расширить круг задач нелинейного программирования, решение которых может быть получено в аналитическом виде.

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"