ПОСТАНОВКА ЗАДАЧИ И ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ
/(Х*) = хПpound;Зг/^: /(**)и (31)
где X = \х |
, /ии р - числа; /(*) - целевая функция, |
pound;/(*) = 0, у=1 тlt;п]
pound;, (х)pound;0, у = т + 1,...,р gj{x)J = 1 - функции, задающие ограничения (условия).
Будем считать функции /(*); gj{x)J = 1,дважды непрерывно дифференцируемыми на множестве Яп, Примерами рассматриваемых задач являются примеры 1.5-1.8. При р = т задача (3.1) со смешанными ограничениями (см. далее разд. 3.4) преобразуется в задачу с ограничениями типа равенств (см. разд. 3.2), а при т = 0 в задачу с ограничениями типа неравенств (см. разд. 3.3).
Определение 3.1. Функция
(3.2) |
Ь(х,Х0,Х) = Х0/(х) + pound; Ху- gj(x)
gt;1
называется обобщенной функцией Лагранжа, числа А-оДь-Д^ - множителями Лагранжа, А, = (а,ь... Д^)Г. Классической функцией Лагранжа называется функция
(3.3)
Определение 3.2. Градиентом обобщенной (классической) функции Лагранжа по х называется векгор-столбец, составленный из ее частных производных первого порядка по х,-, / = 1,...,я:
(дЦх,ха ,ху
Д)~ |
(3.4) |
Зх,
3 А.)
дх.
ГзДх,Х)у | |
'?хЦх,Х) = | дХу дЬ(х,Х) |
дх» л |
Определение 3.3.
Вторым дифференциалом обобщенной (классической) функции Лагранжа pound;(хД0Д) [Цх,А,)] называется функцияаЧ(х, к0,х)=Ц д2%х,pound;gt;’^ , (3.5)
/=1 gt;1 ЩоХ]
^1lt;*А).pound;pound;^МЛ,Л/
/=1 у=1 ЩдХ]
Определение 3.4. Первым дифференциалом ограничения gj(x) называется функция
•' = 1 р- lt;3-6gt;
/-1 дХ!
Пример 3.1. Выписать функции (3.2) - (3.6) для задачи поиска условного экстремума функции /(х) = х2 + х2 на множестве X = {х | х\ -хх +3 = 0 } (см.
пример 1.5), заданном ограничением ^(х) = х2 - X! + 3 = 0.
? Обобщенная функция Лагранжа: Х,(хД0Д1) = Я0(х2 + х2) + ^\[х2 ~х\ + з].
Классическая функция Лагранжа: Цх, Я^ = х2 + х2 + Я^х2 - хх + з|. Градиент функций Лагранжа:
Ухpound;(х,ЯоД1) = (2ЯоХ1 -Я1;2Я()Х2 +2Я1Х2)^; УжХ(хД1) = (2х1 -Я1;2х2 +2Я1Х2)^. Второй дифференциал функций Лагранжа:
*/2pound;(хДоД1) = 2Яо дх( #9632;*quot; (2Яо + ЗЯ^^йс2 \ ^^хД]) = 2Л^ +^2 + 2Я^^2.
Первый дифференциал ограничения: ^(х) = -дхх + 1х2дх2. #9632;
Пример 3.2. Выписать функции (3.2) - (3.6) для задачи поиска условного экстремума функции /(х) = х2 на множестве X = {х | X! + х2 = 1, X! pound; 0, х2 pound; 0 }.
? Перепишем ограничения в каноническом виде (3.1):
*1(х) = XI + х2 -1 = 0, ^2(^) = -XI ^ 0, *3(х) = -х2 pound; 0.
Функции Лагранжа:
Х(хДоД) = ЯоХ2 + Я^Х1 + Х2 -1) + Я2(-Х|) + Яз(-Х2);
Цх9 Я) = X2 + Я^Х! + х2 -1) + Яг^Х!) + Я3(-х2).
Градиент функций Лагранжа:
^дрХ^х,Я0Д) = (2Я0Х| + Я| - Я2, Я| ~ Я3) , ^7 Х1^х9Я) — (2х| + Я| - Я2» Я| — Я3) Второй дифференциал функций Лагранжа:
*/21{хДоД1) = 2Яо дх\\ ^/2Х»(хД) = 2(Ьс\.
Первый дифференциал ограничений:
dgx(x) = lt;Ьсх+бх2, dg2(x) = -lt;amp;!, dgг(x) = -(Ьс2. ш
Определение 3.5. Ограничение pound;у(х) pound; 0 называется активным в точке х*, если = 0. Если pound;у(х*| lt; 0, то ограничение называется пассивным.
Пример 3.3. Классифицировать ограничение gj(x) = х\ + х2 - 2 й 0 в точках х* =(1gt;1)Гgt; х = (0,0)т.
? В точке х* pound;/(**) = 0, т.е.
неравенство превращается в равенство. Следовательно, ограничение является активным. В точке х справедливо pound;у(х) = -2 lt; О, поэтому ограничение в этой точке является пассивным. #9632;Определение 3.6. Градиенты ограничений g1(x),...,g/„(x) являются линейно
независимыми в точке х*, если равенство kiVg^x'j + X,2Vg2(x*j+...+A,mVgm(x*) = О
выполняется только при А.1 = =...= Хт = 0. Если существуют числа
одновременно не равные нулю, для которых равенство выполняется, то градиенты линейно зависимы. В этом случае один из них есть линейная комбинация остальных. Один вектор Vgj(x*) тоже образует систему векторов: при Vg,(x*)*0
линейно независимую, а при Vg^x*j = 0 линейно зависимую.
Система векторов, содержащая нулевой вектор, всегда линейно зависима. Если rang Л = = т* Т° система вект°Р°в линейно
независима. Если rang А lt; т, то система линейно зависима.
Пример 3.4. Исследовать градиенты активных ограничений в точках X* =(1,0)Т ,х = (0,0)г для pound;l(x) = -X! ^0, g2(x) = -X2 *0, g3(x) = X2-(l-X,)3 *0.
? Найдем градиенты:
Vg,(x) = (-l,0)r; Vg2(x) = (0-l)r; Vg3(x) = (3(l-x,)2,l)7’.
,pound;з(*) = *2-(1-*1)3 =0 |
Рис. 3.1 |
V*2(*) g\{x) = -X\ - 0 ^ |
В точке х* = (1,0)Г активны второе и третье ограничения: #2(**) = pound;з(х*) =
^pound;2(**) = (0,-1)Г;^з^х*| = (0,1)г. Так как гаг^^ то градиенты
второго и третьего ограничений линейно зависимы. Действительно, Мlt;ИГ + ^з(В,1)Г = 0, например, при Х2 = 1Д3 = 1. В точке х = (0,0)г активны первое и второе ограничения: ^(х) = $2(х) = 0; ^(х) = (-1,0)Г; У^2(х) = (0,-1)г.
Так как гаг^ ^ ^ = 2 = /и, то градиенты линейно независимы (рис. 3.1). #9632;
3.1.
Еще по теме ПОСТАНОВКА ЗАДАЧИ И ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ:
- 2.5. РОЛЬ ПОЛЬЗОВАТЕЛЯ В СОЗДАНИИ АИС И АИТ И ПОСТАНОВКЕ ЗАДАЧ
- 2.6. ТЕХНОЛОГИЯ ПОСТАНОВКИ ЗАДАЧИ
- 1.1. Управление: основные понятия, система управления, ее признаки, принципы организации деятельности
- § 1. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ОПТИМИЗАЦИИ И ОСНОВНЫЕ ПОЛОЖЕНИЯ
- ПОСТАНОВКА ЗАДАЧИ И ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ
- § 14. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ И ОСНОВНЫЕ ПОЛОЖЕНИЯ
- МЕТОД ВАРИАЦИЙ В ЗАДАЧАХ С НЕПОДВИЖНЫМИ ГРАНИЦАМИ
- МЕТОД ВАРИАЦИЙ В ЗАДАЧАХ С ПОДВИЖНЫМИ ГРАНИЦАМИ
- Приемы решения задач
- 6.3. ПОРТФЕЛЬ МАРКОВИЦА 6.3.1. Постановка задачи