<<
>>

ПОСТАНОВКА ЗАДАЧИ И ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

Общая постановка задачи и основные положения изложены в § 1. Здесь мы рассмотрим случаи, когда множество допустимых решений X задается равенства­ми и неравенствами, т.е.

/(Х*) = хП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-е изд., исправл. — М.: Высш. шк.,— 544 с.: ил.. 2005

Еще по теме ПОСТАНОВКА ЗАДАЧИ И ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ:

  1. 2.5. РОЛЬ ПОЛЬЗОВАТЕЛЯ В СОЗДАНИИ АИС И АИТ И ПОСТАНОВКЕ ЗАДАЧ
  2. 2.6. ТЕХНОЛОГИЯ ПОСТАНОВКИ ЗАДАЧИ
  3. 1.1. Управление: основные понятия, система управления, ее признаки, принципы организации деятельности
  4. § 1. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ОПТИМИЗАЦИИ И ОСНОВНЫЕ ПОЛОЖЕНИЯ
  5. ПОСТАНОВКА ЗАДАЧИ И ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ
  6. § 14. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ И ОСНОВНЫЕ ПОЛОЖЕНИЯ
  7. МЕТОД ВАРИАЦИЙ В ЗАДАЧАХ С НЕПОДВИЖНЫМИ ГРАНИЦАМИ
  8. МЕТОД ВАРИАЦИЙ В ЗАДАЧАХ С ПОДВИЖНЫМИ ГРАНИЦАМИ
  9. Приемы решения задач
  10. 6.3. ПОРТФЕЛЬ МАРКОВИЦА 6.3.1. Постановка задачи