Пиши Дома Нужные Работы

Обратная связь

Классические методы определения экстремумов

КЛАССИЧЕСКИЕ МЕТОДЫ ОПТИМИЗАЦИИ

Во многих экономических моделях исследования операций зависимости между постоянными и переменными факторами лишь в первом приближении можно считать линейными, более детальное рассмотрение позволяет обнаружить их нелиней­ность. Как правило, такие показатели, как прибыль, себестои­мость, капитальные затраты на производство и др., в действи­тельности зависят от объема производства, расхода ресурсов и т.п. нелинейно. В этом случае возникает задача нелинейного программирования, математическая модель которой (0.1), (0.2) приведена во введении.

Можно выделить класс нелинейных задач, которые относятся к классическим методам оптимизации. Допустим, что среди огра­ничений (0.1) нет неравенств, не обязательны условия неотрица­тельности, переменные не являются дискретными, т < п, а функ­ции tyj(X) и J[X) непрерывны и имеют частные производные по крайней мере второго порядка. В этом случае задачу оптимизации можно сформулировать так: найти переменные Х\, х2, ..., х„, удов­летворяющие системе уравнений

Ф,(Х|,х2,...,л:„) = bt, i = 1, 2, ..., т (ЮЛ)

и обращающие в максимум (минимум) целевую функцию

z = f(xl,x2,...,x„). (10.2)


Такие задачи в принципе можно решать классическими мето­дами дифференциального исчисления. Однако на этом пути встречаются такие вычислительные трудности, которые делают необходимым поиск других методов решения (например, см гл. 11, 12). Поэтому классические методы часто используется не ^ качестве вычислительного средства, а как основа для теоретиче­ского анализа.

Примером типичной и простой нелинейной задачи являете^ следующая: данное предприятие для производства какого-то продукта расходует два средства в количестве х\ и. Х2 соответст­венно. Это факторы производства, например, машины и труд, два различных вида сырья и т.п., а величины х\ и х2 — затраты факторов производства. Факторы производства впредь будег^ считать взаимозаменяемыми. Если это "труд" и "машины", то можно применять такие методы производства, при которые величина затрат машин в сопоставлении с величиной затрат труда оказывается больше или меньше (производство более или менее трудоемкое). В сельском хозяйстве взаимозаменяе­мыми факторами могут быть посевные площади или мине­ральные удобрения (экстенсивный или интенсивный метод производства).



Объем производства (выраженный в натуральных или стои­мостных единицах) является функцией затрат производства z = f(xx,x2). Эта зависимость называется производственной функ­цией. Издержки зависят от расхода обоих факторов (xj и х2) и от цен этих факторов (с\ и с2). Совокупные издержки .выражаются формулой b = с,х, + с2х2. Требуется при данных совокупных из­держках определить такое количество факторов производства, которое максимизирует объем продукции z.

(10.3) (10.4)

Математическая модель этой задачи имеет вид: определить та­кие переменные х\ и х2, удовлетворяющие условиям

с,Х| + с2х2 = Ь, хх Z 0, х2 2: 0,

при которых функция

z = /(*,,х2)

достигает максимума.



Глава 10


Классические методы оптимизации



 


Как правило, функция (10.4) может иметь произвольный не­линейный вид.

Используя классические методы оптимизации, следует четко представлять себе различие между локальным экстремумом функ­ции, глобальным экстремумом и условным экстремумом. При этом полезно повторить определение локального и глобального экс­тремумов для функции одной переменной. Понятие условного экстремума вводится для случая, когда число переменных я не меньше 2 (я > 2).

Будем полагать, что функция z = f(xbx2,...,x„) = f(X) дваж­ды дифференцируема в точке X' = (х,,^,...,**), (X* е D{f)) и в некоторой ее окрестности. Если для всех точек X этой окрестно­сти f(X')>f(X) или f(X')<f(X), то говорят, что функция

/(Л) имеет экстремум в X (соответственно максимум или мини­мум).

Точка X*, в которой все частные производные функции z = f(X) равны 0, называется стационарной точкой.

Необходимое условие экстремума.Если в точке X* функция *z - f(X) имеет экстремум, то частные производные функции в этой точке раны нулю:

Д0Г*) = 0, / = 1,2,...,я.

Следовательно, точки экстремума функции. z = f(X) удовле­творяют системе уравнений:

' /Х]ьх2,...,хП) = 0,

,Л'2(*.,*2,-..,*л) = о, (105)

fx„(xl,x2,...,xn) = 0.

Как и в случае одной переменной, необходимое условие не яв­ляется достаточным для того, чтобы стационарная точка была точ­кой экстремума. Для получения достаточных условий следует опре­делить в стационарной точке знак дифференциала второго порядка. Дифференциал второго порядка обозначается d2f(xl,x2,...,x„) и равен сумме произведений частных производных второго порядка


на соответствующие приращения аргументов. Если от частной производной fx.(X) найти частную производную по переменной

xj, то получим частную производную второго порядка по пере­менным х„ xj, которая обозначается Д'х (X). В этом случае

п

/ = 1 у = 1

Достаточные условия экстремума:

а) в стационарной точке Х° функция z - f(X) имеет максимум,
если d2f(X°) <
0, и минимум, если d2f(X°) > 0, при любых Ах,- и
Axj (в этих случаях Х° = X*), не обращающихся в нуль одновремен­
но;

б) если d2f(X°)может принимать в зависимости от Ах,- и Дху-

и положительные, и отрицательные значения, то в точке Х° экс­тремума нет;

в) если d2f(X°) может обращаться в нуль не только при нуле­
вых приращениях
Ах,- и Лху-, то вопрос об экстремуме остается

открытым.

Для функции двух переменных z = /(x,,x2) достаточные усло­вия еще не очень сложны. Существуют четыре частные производ­ные второго порядка: Ц(Х), f?lX2(X), fx'2Xl(X), /;'ЛХ). Из них

две смешанные производные fx'lX2(X) и fx'2X](X), если непре­рывны, то равны.

Найдем значение частных производных второго порядка в ста­ционарной точке Х°(х^,Х2):

аи = Ц(Х°); ап = Д'^*0); а21 = Д„(*°); а22 = Ц(Х°)

(можно убедиться, что «12 = ягО- Обозначим через А определи­тель, составленный из Яу для z, j = 1,2:

f\\ fli2 И21 а22

«II «22 ~a\lal\-



Глава 10 '


Классические методы оптимизации



 


Тогда достаточные условия экстремума функции двух пере- ^
менных имеют вид: >

а) если А > 0 и ац< 0 (й22 < 0), то в точке Х° функция имеет \
максимум: если
Л > 0 и аи> 0 (022 > 0), то в точке Х° — мини- I
мум (в этих случаях Х° - X*);

б) если Д < 0, то экстремума нет;

в) если А = 0 , то вопрос об экстремуме остается открытым.

Схема определения экстремума функции п переменных совпа­дает с правилами определения локального экстремума функции одной переменной.

^ 10.1. Исследовать на экстремум функцию

_ 4 4 2 <■) 2

Z — Xj + Х2 — X] — ZXiX2 — Х2.

Решение. Находим частные производные:

(10.6)

|4, =4*i -2*i ~2х2, \z'X2 = 4х23-2х,-2х2.

Приравниваем частные производные нулю:

(Ю.7)

Ux,3 - 2х, - 2 = 0, [4x1 ~ 2х\ - 2х2 = 0.

Решаем систему уравнений (10.7). Вычитая из первого уравне­ния второе, получим 4х,3 - 4х\ = 0, поэтому х\ = х2, и из первого

уравнения найдем х,3 - х, = 0, откуда х\ = 0 или х, = ±1.

Имеем три стационарные точки: Х] = (0;0); X2 = (1;1);

X3 = (-1;-1).

Найдем вторые частные производные, используя (10.6):

^2 = (4х3-2х{-2х2УХ] = 12х,2-2;

%Х2 = (4*.3 - 2*, - 2)'Х2 = -2; %2Х1 =(4х23-2х2-2х1)^1 =-2; z;'2 ={4x\-2x2-2x,)'Xl = 12х2-2.


Вычисляем значения вторых частных производных в каждой стационарной точке, составляем определитель А и применяем достаточные условия экстремума.

В точке Xх = (0; 0) аи = —2; ап = «21 = ~2\ «22 = ~2\

0.
Д =

-2 -2 -2 -2

Вопрос об экстремуме остается открытым (такая точка называ­ется седловой).

В точке X2 = (1; 1) (а также и в точке X3 = (-1;-1)):

10 -2 -2 10
96.

ап = 10; ап = «21 = ~2; «22 =Ю; А =

Функция в этих точках имеет минимум, так как А > 0, аХ\ > 0.

Выше шла речь о локальном экстремуме функции п перемен­ных. Как правило, в практических задачах необходимо определить наибольшее и наименьшее значения функции (глобальный экс­тремум) в некоторой области.

Говорят, что функция z = f(X) имеет в точке Х° заданной области D глобальный максимум (наибольшее значение) или глобаль­ный минимум (наименьшее значение), если неравенство f{X) <, f(X°y^\ f(X) > f(X°) соответственно выполняется для

любой точки

Если область D замкнута и ограничена, то дифференцируемая функция z = f(X) достигает в этой области своих наибольшего и наименьшего значений или в стационарной точке, или в граничной точке области (теорема Вейерштрасса)2.

' В точках Х2=(1;1) и X3 = (-1;-1) d2f(X2) = d2f(X3) =

= 10(Дх,)2 - 4Дх,Дх2 + 10(Дх2)2 = 2(Дх, - Ах2)2 + 8(Дх,)2 + 8(Дх2)2 и

при любых Axj и Дх2. не равных нулю одновременно, d f(X ) =

- d2f(X3) > 0.

2 Вейерштрасс К. Т. (1815-1897) — немецкий математик.



Глава 10 *


Классические методы оптимизации



 


Упростив это выражение, получим Л

z = 4(2-x2)2x22. (10.13)г

При этом х2 е[0;2]. Найдем глобальный экстремум функции ':, (10.13) на отрезке [0;2]. Производная этой функции равна z' = l6(2-x2)x2(l-x2).

Стационарные точки: х2 = 0, х2 - 1 и х2 = 2. Одна из них xi = 1, лежит внутри отрезка, две другие совпадают с концами. Найдем значения функции (10.13) в стационарной точке х2 = 1 и на концах отрезка: z (1) = 4; z (0) = 0; z (2) = 0.

Следовательно, zmax = 4 и достигается при х2 = 1, х\ - 4 -— 2x2 = 2, т.е. в точке (2; 1).

Максимальный объем производства, равный zmax = 4 ед., дос­тигается при условии, что затраты производственных факторов х\ и х2 равны соответственно 2 ед. и 1 ед>

V 10.2. Метод множителей Лагранжа

Другой способ определения условного экстремума начинается
с построения вспомогательной функции Лагранжа1, которая в
области допустимых решений достигает максимума для тех же
значений переменных хь Х2, ..., х„, что и целевая функция г. ;,

Пусть решается задача определения условного экстремума }<
функции z = /(X) при ограничениях (10.8). ,^'

Составим функцию

L(X) = f(X)+Zh<?i(X), (10.14)i

которая называется функцией Лагранжа. А., — постоянные множите­ли (множители Лагранжа). Отметим, что множителям Лагранжа можно придать экономический смысл. ЕслиДх!, х2, ..., х„) — доход, соответствующий плану Х= (х\, х2, ..., хп), а функция <р,(хь х2, ..., х„) — издержки г-го ресурса, соответствующие этому плану, то X, — цена (оценка) /-го ресурса, характеризующая изменение экстремального значения целевой функции в зависимости от из-

1 Лагранж Ж.Л. (1736-1813) — французский математик и механик.


менения размера /'-го ресурса (маргинальная оценка). L(X) — функция п+т переменных (хь х2, ..., х„, A.ls Х2, ..., Хт). Опреде­ление стационарных точек этой функции приводит к решению системы уравнений

0, j -1,2,...,п, = 0, г = 1,2,...,/и.

дЦХ)

(10.15)

dXj дЦХ)

dXt

Легко заметить, что LJk.{X) = q>i{X), т.е. в (10.15) входят урав­нения связи. Таким образом, задача нахождения условного экс­тремума функции z = f{X) сводится к нахождению локального экстремума функции L (X). Если стационарная точка найдена, то вопрос о существовании экстремума в простейших случаях реша­ется на основании достаточных условий экстремума — исследова­ния знака второго дифференциала d2L(X) в стационарной точке при условии, что переменные приращения Дх; связаны соотно-

шениями

(10.16)
/и,
дх,

AXj =0, / = 1, 2,

У=1

полученными путем дифференцирования уравнений связи. Рас­смотрим пример. ^ 10.3.Найти наибольшее и наи­меньшее значения функции z = 9х2 + 4x2 + х2 - (Зх2 + 2х2 + х2)

при условии, что Х\, х2, хз удовле­творяют уравнению

Решение. Уравнение связи
определяет в пространстве сферу
единичного радиуса с центром в
начале координат (рис. 10.2). Так
как сфера — замкнутое ограничен­
ное множество, то согласно теоре- рис jq 2


                           
     
   
         
 
 
 
   
   
 
 
 

Глава 10

ме Вейерштрассафункция достигает на ней своего наибольшего инаименьшего значений.

Необходимо найти условный глобальный экстремум. Запишем уравнение связи в виде: xf + х\ + х2 - 1 = 0.

Составим функцию Лагранжа:

L(xl,x2,x3) = 9х2 + 4x1 + х1 ~Oxi +2^2 + xl)2 + Hxi + xi з -!)•Найдем частные производные этой функции по х\, xi, Х3, X.

1'ч = 18х, - 2(3х2 + 2х2 + х2)6х, + 2Ххи 1^ = 8х2 - 2(3х2 + 2х2 + х3)4х2 + 2Хх2, L'X2 = 2х3 - 2(3х2 + 2X2 + *з)2*з + 2^з. L'k = х,2 + х22 + х32 -1.

Приравнявчастные производные нулю, получим систему:

"х,((9 + X) - 6(3х,2 + 2х22 + х2)) = О, х2 ((4 + X) - 4(3х,2 +2х| + х32)) = О, х3((1 + X) - 2(3х2 + 2х22 + х32)) = 0,

Xj + Х2 + Х3 = 1.

Решая систему, получим стационарные точки, в которых най­дем значения функции z:

1. X] = х2 = 0; х3 = ±1 => z = 0.

2. х, = 0; х2 = ±1; х3 = 0 => z = 0.

3. X! = ±1; х2 = х3 = 0 => z = 0.

V2

4. х, = 0; х2 = х3 = ±

5'Х| ' *2 = 0; Хз = ±~Р) =>г = 1-

6.x, =х2 =±-гт\ *з =0 => г = |.


■ Классические методы оптимизации 211

и Выберем из всех значений z наибольшее и наименьшее: гнаиб = 1, а 2наим. = 0. Легко видеть, в каких точках сферы достигаются эти 'значения. ►

Если число переменных п = 2, нелинейные задачи можно ре­шать геометрически. Ограничения должны быть записаны в виде неравенств

Ф,(х„х2) < Ь„ i = 1,2,...,т, (10.17)

а целевая функция иметь вид

* = /(х„х2). (10.18)

Как и в случае геометрического решения задач линейного программирования, сначала необходимо построить область допус­тимых решений (ОДР) — множество точек плоскости, удовлетво­ряющих неравенствам (10.17). Но в отличие от задач линейного программирования здесь ОДР не обязательно будет выпуклой и может быть даже разрывной. Экстремум функции может дости­гаться и внутри области, и на границе.

После построения ОДР следует записать уравнения линий уровня целевой функции — множество точек плоскости, в кото­рых целевая функция (10.18) постоянна: / {, х2) = С, и опреде­лить направление возрастания (убывания) целевой функции, по­строив, например, линии уровня для разных значений С. Затем, перемещая линию уровня в нужном направлении в ОДР, найти точки области, в которых целевая функция принимает оптималь­ное значение.

t> 10.4.Найти наибольшие значения функции z = 2х2 - х2 при ограничениях

х, - х2 < 2, х2 < 4, х, + х2 - ххх2 > 0, х, > 0, х2 > 0.

Решение. ОДР (рис. 10.3) ограничена прямыми хх — х2 = 2, х2 = 4, осями координат xj = 0, х2 = 0 и гиперболой х, + х2 -

- х^2 = 0, уравнение которой приводится к виду х2 = 1 +------- .

х, -1



Глава 10


Классические методы оптимизации



 


                   
   
   
 
     
 
 
 
     
 

Решая систему, составленную из этих двух уравнений, получим х\ - 2 + 42, х*2 = V2, X* = (V2~ + 2; V2). Поэтому zmax = - 2(л/2 + 2)2 - л/2 или zmax * 21,9. ► Трудности применения классических методов оптимизации уже отмечались выше (с. 10). Поэтому разработаны приближен­ные методы решения нелинейных задач программирования, особенно плодотворные для некоторых классов функций, на­пример, для выпуклых (вогнутых) функций, рассмотренных в следующей главе. УПРАЖНЕНИЯ В задачах 10.5—10.7найти локальный экстремум следующих функций. 10.5.z = х3 + yi - Зху. 10.6.z = хУ (12 - х - у), х > 0, у > 0. 10.7.z-x2+xy + y2+x-y + l.

 

„ i  
*2    
l | Щ\ *Way
\\   fHi)
\ 0 у X,

Рис. 10.3

покидают ОДР через точку X*

1 „ 0

х-, = 1 +------ и прямой х, - х2 = 2.

X, - 1


Линии уровня целевой функции — 2Х|2 - х2 = С.

Для разных значений С графиком уравнения х^ =

= 2х,2 - С является пара­бола с осью симметрии, совпадающей с осью ординат.

При С=0 парабола про­ходит через начало коор­динат. При С > 0 пара­болы сдвигаются вниз. Перемещая в направле­нии возрастания, полу­чим, что линии уровня пересечения гиперболы


В задачах 10.8—10.12найти глобальный экстремум (наиболь­шее и наименьшее значения) функции z в области решений сис­темы неравенств (или неравенства). Дать геометрическое реше­ние.

10.9.z = x2 + .y2-2x-10>> + 26

10.8.z - 3xj + х2

2 £ -4,

х,222 <40,

5х, + 2х2 < 20, х, > 0, х2 > 0.

х,2 + х\ > 4,

X] > 0, х2 > 0.

z = е ' 2 х2 + х2 < 4.

(2х2+3х22),

10.11.

10.10.z = x,2+2x2-3

| х,2 + х22 < 10, 1 х, > 0, х2 > 0.

10.12. z = XjX2,

Г 0 < х, < 3,

[2Х] + х2 < 8. . .v -В задачах 10.13—10.15найти условный экстремум функции z с

помощью метода исключения.

10.13. z - х2 + xj при Х[ + Х2 = 1.

10.14.z = х2 - х2 в области х2 + х2 < 16 при xj - х2 = 4.

10.15.z = Зх2 + 2х22 - Зх, +1 при х2 + х22 = 4.

В задачах 10.16—10.19найти условный экстремум с помощью метода Лагранжа.

 

10.16. z = Х]Х2 при х2 + х2 = = 2.
10.17. z = Xj +х2 1 1 при — + — X] Х2 = 1.
10.18.z = — + — X, Х2 1 1 при — + — х\ х2 = 1

10.19.z = х3 + х2 при Xj + х2 = 2, X) > 0, х2 > 0.



Глава 11


 


11.13. Z = х2 - х? -»• max

{ + Ъх\ < 3, • 0<х, <2/3, х2 > 0.

Указание: Отрезок изменения каждой из переменных раз­бить на 4 части.

11.14. Для данной функции Z— х\х2 найти:

а) общее выражение градиента функции VZ;

б) линию уровня, проходящую через точку А(4; 1) и градиент
VZ (А), и изобразить их на чертеже;

в) производную по направлению /= (—1; -1).

11.15. Решить задачу 11.14 при условии, что Z = xf - х2 + 2.


Глава 12






ТОП 5 статей:
Экономическая сущность инвестиций - Экономическая сущность инвестиций – долгосрочные вложения экономических ресурсов сроком более 1 года для получения прибыли путем...
Тема: Федеральный закон от 26.07.2006 N 135-ФЗ - На основании изучения ФЗ № 135, дайте максимально короткое определение следующих понятий с указанием статей и пунктов закона...
Сущность, функции и виды управления в телекоммуникациях - Цели достигаются с помощью различных принципов, функций и методов социально-экономического менеджмента...
Схема построения базисных индексов - Индекс (лат. INDEX – указатель, показатель) - относительная величина, показывающая, во сколько раз уровень изучаемого явления...
Тема 11. Международное космическое право - Правовой режим космического пространства и небесных тел. Принципы деятельности государств по исследованию...



©2015- 2024 pdnr.ru Все права принадлежат авторам размещенных материалов.