Классические методы определения экстремумов КЛАССИЧЕСКИЕ МЕТОДЫ ОПТИМИЗАЦИИ
Во многих экономических моделях исследования операций зависимости между постоянными и переменными факторами лишь в первом приближении можно считать линейными, более детальное рассмотрение позволяет обнаружить их нелинейность. Как правило, такие показатели, как прибыль, себестоимость, капитальные затраты на производство и др., в действительности зависят от объема производства, расхода ресурсов и т.п. нелинейно. В этом случае возникает задача нелинейного программирования, математическая модель которой (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.
Математическая модель этой задачи имеет вид: определить такие переменные х\ и х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:
«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.
Решение. Находим частные производные:
|4, =4*i -2*i ~2х2, \z'X2 = 4х23-2х,-2х2.
Приравниваем частные производные нулю:
Ux,3 - 2х, - 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; %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\
-2 -2 -2 -2
Вопрос об экстремуме остается открытым (такая точка называется седловой).
В точке X2 = (1; 1) (а также и в точке X3 = (-1;-1)):
ап = 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,...,/и.
| дЦХ)
dXj дЦХ)
dXt
Легко заметить, что LJk.{X) = q>i{X), т.е. в (10.15) входят уравнения связи. Таким образом, задача нахождения условного экстремума функции z = f{X) сводится к нахождению локального экстремума функции L (X). Если стационарная точка найдена, то вопрос о существовании экстремума в простейших случаях решается на основании достаточных условий экстремума — исследования знака второго дифференциала d2L(X) в стационарной точке при условии, что переменные приращения Дх; связаны соотно-
шениями
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.
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+х22 <40,
5х, + 2х2 < 20, х, > 0, х2 > 0.
| х,2 + х\ > 4,
X] > 0, х2 > 0.
(2х2+3х22),
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
2х{ + Ъх\ < 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
|