Шелобаев С.И. Математические методы и модели

Подождите немного. Документ загружается.

-2

-4

-6

-8

-F

Fi =

-2xi

l2xi-\0

_l /

-^№—

T Д

-A-

-JL-

TYI

4 Sfb 7 x,

V 7

==?^===

f2 = 2x1-12x1+ 10

•)

3/-

^ffl^^^"'

ffl

»)

""f.W

Найдем первую произво)аную заданной функции:

rff,/A = -4x| + 12;

Приравняем первую производную нулю и решим полученное

уравнение: -4xi + 12 = 0; отсюда получим, что

Х|

= 3.

Таким образом, получаем, что экстремум функции находится в точ-

ке с координатой

Х|*

= 3.

Находим вторую производную заданной функции:

efif/dx^ = -4 < О,

т. е. в найденной точке

Xi*=

3 исследуемая функция имеет максимум.

Если же нам требуется найти 4чгнкиию

Fi(x)

-* max, то следует ввести

другую

функцию вида

F^x)

- -Fi(x) и отыскать

F^ix)

min.

Таким образом,

переходя от заданной функции Fi = -2xi^ + 12Х| —

к функции

—-Fi,

т. е. Fj = 2х|^- 12х| +

10,

получим ее значения (табл.

4.1,

рис.

4.3,

а).

Таблица

4.1.

Результаты вычиелаты функции

Функция Fi

(х\)

Fiixi)

FiiXi)

Значения аргумента

12 3 4 5

0 6 8 6 0

0 -6 -8 -6 0

101

Из сравнения функций Fj и /2 следует: а) вместо максимума

функции F\, равного max F\, появляется минимум функции р2,

равный min F2, б) значения х* = 3, соответствующие экстрему-

му для обеих функций, одинаковые; в) шах Fi = 8; min /2 ~ ~8.

Следовательно, имеем, что max Fj = —min /2- Значит, чтобы

уменьшить число вычислений, необходимо определять только

минимум функции.

Если же в задаче требуется определение максимума функции,

то необходимо: а) перейти от функции Fi к функции F2= —F\;

б) найти min

F2,

находящийся в точке

х*;

в) определить max Fj =

=—min /2, сохраняя значение

х*

без изменения.

Поясним работу этого алгоритма на следующем простом

примере.

Пример 4.2.

Требуется найти F| = —2(xi -3)^

—1

-> max.

Решение. Перейдем к функции вида

= -F^ = 2(х\ -3)^ +

+1 -> mill, вид графиков

и Fi приведен на рис. 4.3, б.

Вычислим первую производную функции:

dF-Jdx\

2 •

2(Х|

-3), отхуда

следует,

что

х^

= 3. При этом min

= 2(3-3)^ +

и max

= -min

Fi —

=-1.

Отсюда следует, что функция F\ имеет максимум в точке х' = 3,

при этом max Fx= -1 (с учетом этого свойства в дальнейшем будем

определять только минимум функции).

Признак минимума функции одной переменной dFldx\ = О

запишем в следующей форме:

[(rf/7fl[x,)']'/^

= 0, (4.1)

закончив определение экстремума функций от одной переменной.

Рассмотрим теперь процесс определения экстремума функций

от двух переменных на следующем относительно простом примере.

Пример

4.3.

Необходимо найти минимум функции вида:

F= (л:, -5)2/2 +

(X2

-3)2/3 + 4 -^ min,

график которой приведен на рис. 4.3, в.

Решение. В этом случае требуется найти частные производные

по каждой переменной и приравнять их нулю.

результате получим:

dF/dx^

= 2(xi -5)/2;

х,*

= 0;

л:,*

= 5;

dF/dx2

= 2(Х2

-3)/3;

^ -

= 0;

Xj*

= 3.

При этом имеем, что min F= (5 -5)2/2 + (3 -3)2/3 + 4 = 4.

В общем случае в функциях двух переменных действует сле-

дующий алгоритм: если задана целевая функция F

F =

f{x\,xi) -^ min.

102

то необходимо найти частные производные и решить систему

дР/дх^

= 0;

dF/dx2 =

О,

корни которой и явятся координатами точки минимума функции.

Для заданной функции из примера этот алгоритм запишем так:

[(Ф7йх,)2 +

(дГ/дх2)Ц'/'

= 0. (4.2)

Записи признака минимума функции одной переменной

(4.1) является частным случаем условия (4.2), определяющего

признак минимума функции двух переменных. Данный признак

в более компактной форме можно записать так:

t(df/dxj)

pV2

= 0.

Если теперь перейти к функции от п переменных, то ее гра-

фически представить нельзя, но на нее можно распространить те

выводы, что сделаны для функции двух переменных. Предста-

вим функцию л переменных следующим образом:

F = f{x\,X2,

...,х„)

-»min.

Данная функция имеет

минимум

в точке, координаты кото-

рой находятся в результате решения системы уравнений:

dF/dXi

= 0;

дР/дх2

= 0; ...,

дР/дх„

= 0. (4.3)

Условие (4.3) по аналогии с (4.2) можно записать следую-

щим образом:

lidP/dxi)^

{дР/дх2^

+...+

(а//ах„)2]|/2 = о,

или более кратко,

,-|'/2

Е(а//йХ;)

(4.4)

Условие (4.4) является признаком минимума функции п пере-

менных. Аналогичные признаки для двух и одной переменных явля-

ются частными случаями признака для любого числа переменных п.

На этом закончим рассмотрение аналитических методов на-

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

Задачи услошюй оптимизации и методы их решения. Пошаговое

перемещение человека от подножия горы к ее вершине можно

103

интерпретировать как процесс поиска экстремума функции с

программной реализацией вьиислительных методов на ЭВМ.

Известно, что все величины подразделяются на скалярные и

векторные. Скалярная величина (масса, объем, длина, энергия,

работа и т. д.) характеризуется одним значением.

Векторная

вели-

чина, или вектор (скорость, сила, ускорение, напряженность

электрического и магнитного поля и др.), характеризуется вели-

чиной и направлением. Если известны проекции вектора ОА на

оси координат 0А\ и OAi в двухмерном пространстве, то нетрудно

найти его величину (длину, норму или модуль) и направление.

Вектор ОА в л-мерном пространстве задается вектор-

столбцом, включающим п строк

04 =

041

ОЛг

0А„

а его модуль определяется так:

ОА

[OAi^

OAi^

+...+ 0-4„2]'/2.

Пусть задана функция п переменных F

=/{xi,

Х2,..., х„), или

короче F =Лх/). Ее частные производные будут равны df/dxi,

df/dx2, ...,

df/dx„.

Из этих частных производных составим век-

тор-столбец, который обозначим ДДдс,):

df/dxi

д/Ы=

дГ/дХ2

dfldxn

Такой вектор-столбец, составляющими которого являются

частные производные df/dxj, называют градиентом функции

/(xj).

Градиент показывает направление наискорейшего увеличения

функции. Вектор, противоположный фадиенту, называют ан-

тиградиентом, он показывает направление скорейшего умень-

шения функции. Численной мерой градиента, как и любого век-

тора, является модуль, определяемый

h-^M

^dfldx)\[dfldx^\-+(dfldxi)^

104

или |А/"(Х>)| =

Обозначим модуль фадиента через

i (dfldxX

П'/2

(4.5)

ем =

-i\n

i [dfldxi]

По аналогии с (4.4) можно утверждать, что признаком экс-

тремума является условие

8„ = 0. (4.6)

Если при работе с ЭВМ мы получим в некоторой точке зна-

чение модуля, например, ем = 0,00001, то, строго говоря, требо-

вание (4.6) не выполнится, хотя данную точку принять за экс-

тремум можно. Поэтому в практических расчетах задаются неко-

торым малым значением и считают признаком экстремума вы-

полнение условия

8„<еГ, (4.7)

т. е. если оптимальное значение целевой функции порядка еди-

ницы, то за допустимое значение можно принять

Е5Г"

~ 0.01-

При этом допускаемая ошибка составит менее 1%.

Для некоторых функций в точке, которую можно на практике

принять за экстремум, условие (4.7) не выполняется. Поэтому ю из-

бежание увеличения числа шагов при вычислении (для сокращения

времени поиска экстремума) вводят

еще

два признака экстремума:

ZF =

\Fk-F,.U^F""; (4.8)

ex =

ZH-^;"']/^>^E^^

(4.9)

.•=1

Величина e^- показывает

абсолютное значение приращения

це-

левой функции на к-и шаге (если это приращение мало, т. е.

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

экстремум). Следовательно, выполнение условия (4.8) обеспечи-

вает нахождение экстремума для пологих поверхностей (для го-

ризонтальной плоскости е/- = 0). Условие (4.9) позволяет опре-

делить экстремум для крутых поверхностей (для вертикальной

плоскости

= 0). Допустимые значения ef", ef" так же, как и

8Й°",

при целевой функции, составляющей несколько единиц,

можно принять

£ДОП= ^ДОП = ^ДОП

=0,01.

105

Наиболее простая задача условной оптимизации имеет вид:

f = fi.Xj) -> min;

oj < xj

bj,

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

задача условной оптимизации решается следующим алгоритмом.

Производится поиск вершины, как в случае безусловной

оптимизации: если в ходе поиска значение переменной xj на к-й

итерации выходит на (или за) нижнюю фаницу (т. е. оказывает-

ся Jc/<

OJ),

ТО В качестве оптимального принимается значение

Xj*=aj,

и поиск продолжается по остальным переменным; ана-

логично осуществляется поиск для верхней фаницы;

Если в ходе поиска получается, что х/

bj, то принима-

ется х/ =

bj.

Назначение фаничных условий, если оно не зада-

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

речивым требованиям: с одной стороны, интервал bj

— Oj

дол-

жен быть больше, чтобы в нем оказалась искомая вершина, а с

другой —его желательно иметь не очень большим, чтобы нахо-

ждение вершины не требовало очень большого числа итераций

(число итераций не только увеличивает продолжительность

решения задачи, но и приводит к тому, что всегда присутст-

вующие ошибки вычислений становятся соизмеримыми с ис-

комыми величинами, и чтобы выйти из этого противоречия,

лучше назначить небольшой интервал bj

—aj,

решить задачу и

определить, как назначенные фаницы влияют на результат).

В общем случае задача условной оптимизации имеет вид:

F =

f[xj)

min;

g,{xj)

• (4.10)

aj<Xj<bj.

Известен ряд достаточно сложных методов решения подоб-

ных задач [1, 2, 16, 78, 84, 129, 130]. Рассмотрим один из таких

методов, называемый

методом штрафных

функций,

суть которого

заключается в следующем. От задачи условной оптимизации

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

вая целевая функция, включающая, кроме заданной целевой

функции

J{Xj),

заданные офаничения

giixj).

Новая целевая функ-

ция записывается следующим образом:

4xj)

Ах) +

^\gi

{Xj)\

-> mill, (4.11)

где

^[gi(Xj)] —

штрафная функция.

106

Вводимая штрафная функция 4'[gi

(х/)]

должна удовлетворять

следующим требованиям:

^ISi

(Xj)]

О,

если

находится в области допустимых решений;

^[Si (Xj)] -*

О, если xj находится вне области допустимых решений.

Штрафная функция может иметь следующий вид:

4'[g,M=Ml^^(;c,),

(4.12)

1=1

где М— большое число (например, если ожидаемое оптимальное значение

целевой функции порядка единиц, то можно принять М= 1000).

Если Xj находится

области допустимых решений, то выпол-

няются все ограничения

и,

значит, gj

(Xj)

= 0.

При этом штраф-

ная функция (4.12) равняется нулю,

новая целевая функция

(4.11) оказывается равной заданной, т.

е.

Ф(^у) =f{Xj)-^ min.

Если Xj не находится

области допустимых решений,

то не

выполняются ограничения, т.

е.

gj (xj)

0. Значит, g,Hxj)

О,

большое число Л/приводит

тому, что

новой целевой функ-

ции (4.11) штрафная функция (4.12) оказывается существенно

больше заданной целевой функции/(д^). Поэтому

ходе мини-

мизации благодаря большому фадиенту

первую очередь

уменьшается штрафная функция 4'[g,

(х,)],

пока

она не

станет

равной нулю (т.

е.

пока значения Xj не войдут

область допус-

тимых решений

или

пока

мы не

получим допустимого реше-

ния),

далее начинается процесс минимизации заданной целе-

вой функции,

чем уже упоминалось.

Пример

4.4.

Нужно решить задачу условной оптимизации вида:

Х2

min;

2(jci-2)

+1;

(xi-з) +(х2-0,5)

^4;

О <

Х|

О < Xj <

Решение. Первое ограничение представляет собой параболу

координатами вершины А (2;1), второе

—

часть плоскости, находящую-

ся вне окружности радиусом Л

2, центр которой имеет координаты О

(3;

0,5). Без наложения второго ограничения минимум находился бы

вершине параболы

точке

А и

имел бы значение /"i

= 1.

Наложение

дополнительного условия ухудшило результат. Минимум переместился

в точку В с координатой х, =1,4. При этом ^2*

^2~ 1.8, т.

е.

его зна-

чение ухудшилось.

107

Решение этой задачи методом штрафных функций предусматривает

следующий алгоритм.

Записывается условие задачи в виде системы (4.10):

F =

х^

-> min;

jC2-2(jci-2)

{x,-3f

(x,-

0 <

дс,

< 4; 0 <

y,iO.

-1 = 0;

-0^)'-

X2<3;

У\-

-4

Чтобы удовлетворить форме выражения (4.10), во втором ограниче-

нии сделан переход от неравенства к уравнению и введена неотрица-

тельная переменная

у/

iO.

Составляется новая целевая функция, включающая штрафную

функцию с числом М= 1000. Тогда получим:

mm;

= X2

+ 100o| х2-2(х,-2)'-1]

[(х,-з)'

(х,-0^)'-У,-4 I

^ 4;

Х2

5 3;

Далее проводится решение полученной системы.

Рассмотрим решение ряда прикладных проблем потребитель-

ского выбора с иллюстрацией на конкретных примерах и при-

менением наиболее распространенных нелинейных методов оп-

тимизации, в частности, метода Лагранжа с геометрической ин-

терпретацией получаемых результатов.

4.2.

Применение метода Лафанжа для решения задач

оптимизации на условный экстремум

Суть

метода Лагранжа

состоит в построении функции вида

Цх\,

Х2,

X) = Дхь хг) +

(xj, Х2) от трех переменных Х), хг, X,

называемой функцией Лафанжа, и в сведении задачи на услов-

ный экстремум в случае двух независимых переменных к задаче

на абсолютный экстремум функции Дх|, хг, X.) трех независи-

мых переменных

Х{, Х2,

108

функция Лагранжа

Цхи хг, X) представляет собой сумму це-

левой функции (4.13) и функции ограничения (4.14), умножен-

ной на новую независимую переменную X, называемую

множи-

телем

Лагранжа,

входящую обязательно в первой степени:

/Х],

хг)

-*•

max

(ДХ],

хг) -» min) (4.13)

при условии

«(х„ хг) =

(4.14)

Необходимое условие локального условного экстремума функ-

ции (4.13) при наличии ограничения (4.14) в аналитической фор-

ме имеет следующий вид: пусть функции

Дх],

хг), ^xj, хг) непре-

рывны и имеют непрерывные частные производные первого по-

рядка по переменным xj и хг; пусть (х?, xj) —точка условного

локального экстремума функции (4.13) при наличии ограниче-

ния (4.14) и пусть grad gix° , xl) = 0. Тогда существует единст-

венное число

Х*',

такое, что (трехмерная) точка (xf , х° ,

Я.<*)

удов-

летворяет следующей системе трех уравнений с тремя неизвест-

ными xi,

Х2,

X.:

dL{xi,X2,X)/dxi

dL(x\,X2,X) /дx2

дL{x^,X2,X)/дk=0

(4.15)

(отметим, что всегда дДх), Xj,

Х)/дХ.=

g(X|, Х2).

Иначе говоря, если двумерная точка (xf, х") есть точка ло-

кального экстремума функции (4.13) при наличии ограничения

(4.15),

то трехмерная точка (х", х", Х^) — критическая точка

функции Лагранжа. Отсюда следует, что для нахождения точек

(условного) локального экстремума функции (4.13) при наличии

ограничения (4.14) прежде всего следует найти критические

точки функции Лагранжа, т. е. найти все решения системы

уравнений (4.15). Далее критические точки функции Лагранжа

следует укоротить, удалив из них последние координаты

Х^.

За-

тем каждую укороченную критическую точку необходимо про-

анализировать, является ли она в действительности точкой

(условного) локального экстремума функции (4.13) при наличии

ограничения (4.14) или не является. При этом используют гео-

метрические или содержательные экономические соображения.

109

в некоторых новых задачах на условный экстремум, появ-

ляющихся в экономике, обычно укороченная критическая точка

функции Лагранжа действительно является точкой условного

локального (и глобального) экстремума функции (4.13).

Пример

4.5. Найти экстремум функции у = х\ + х\ при условии,

что

Х2

— 1 = о, т. е. решить задачу на условный экстремум методом

Лагранжа.

Решение. Имеем

Ых^,

Х2,

= х] + х\ + \

(Х|

х^

-\), отку-

да следует, что

dL[x\

,xi л) / дх\

2х\

"к

а1(х1,Х2Д)/<Зх2

2х2

+ Х =

0; • (4.16)

dL[xi ,Х2

Д) / Л =

XI + Х2

= 0.

Из первых двух уравнений получаем, что Xi= Х2, откуда, используя

третье уравнение, получаем, что х" = х\ =1/2.

Таким образом, система уравнений (4.16) имеет единственное ре-

шение, т. е. дает единственную критическую точку функции Лагранжа

(1/2,

1/2, -1) (Х" =

—2x1

~ ~2 • 1/2 = -1). Укороченная критическая

точка (х? , х") = (1/2; 1/2) есть точка условного локального (также и

глобального) минимума заданной функции при ее заданном ограниче-

нии, так как непосредственно проверяется, что при (Х], х{) {х\ , х\)

справедливо неравенство/(Х], X2)>f(x1,x\)= 1/2.

Если задана общая задача (4.17) с офаничениями (4.18) на

определение условного экстремума:

/(Х|,...,

х„)

-> max (/"(х,,..., х„) -> min) (4.17)

^|(Х|,...,х„) = 0,

(4.18)

g„

(х,,..., х„) =

(обычно т

п),

то функция Лагранжа имеет вид:

1(х,,..., х„, X,,...,

Х,„)

=/(х,,..., х„) + Xigixi,...,

х„)

+... +

X^^ixy,...,

х„).

При этом система (4.16) переписывается в виде системы п + т

уравнений с п + т неизвестными

л:],...,

х„, \\,..., Х^.

Критическая (и + /п)-мерная точка (х°,..., xj,

Х?,...,

Х°,)

функции Лагранжа после операции укорачивания приобретает

вид

(jcj*,...,

х°) и-мерной точки.

110

при условиях