§ 3.15. наибольшее значение вогнутой функции
§ 3.15. наибольшее значение вогнутой функции
Напомним, что линейной функцией и переменных называется функция /(х) = Дх,+...+Дх„ + у, гдеД(/ = 1,...,л), у -произвольные, фиксированные действительные числа. Неравенство вида /(х)>0, где /(х) линейная функция, также называется линейным. Точкой глобального максимума (глобального минимума) функции /(х) на множестве X с R" называется всякая точка х' еХ, в которой значение функции является наибольшим (наименьшим) на X.
205
Теорема 3.17. Пусть выпуклое множество X<z R" задано системой линейных неравенств
'/,(*)> О,
' "' (3-57) /,(*)> О,
X' некоторое выпуклое подмножество в X; f(x)функция, вогнутая на X' , и х' є X' точка, в которой f(x) дифференцируема. Тогда:
если для некоторых чисел А,,...,Л,выполняются условия:
а) х*стационарная точка функции
i(x) = /(*)+V, (*)+■■■+А',00;
б) Alll(x*) = Ou А, >Одля каждого i=l,...,s,
то f(x*) наибольшее значение fix) на X' ;
напротив, если X'= X и f(x*) наибольшее значение f{x) на X, то найдутся числа А1,...,А1, для которых выполняются условия а) и б).
Условия а) и б) называются условиями Куна-Таккера. Функция L(x) называется функцией Лагранжа, а числа Al,...,As,-множителями Лагранжа.
Доказательство. І.Из условия б) следует, что /(**) = L(x*). Далее, функции A^(x),...,Asls(x) являются вогнутыми потому, что все они линейные функции. Функция L{x) является вогнутой, поскольку она сумма нескольких вогнутых функций. Вследствие теоремы 3.16 значение L(x') является наибольшим значением функции Дх) на множестве X', т.е. L(x') > L(x) для любой точки х є X'. Так как А, > О и для любой точки х еХ' выполняются все неравенства системы (3.57), то
А,/,(*)+...+ЛЛ(*)>0.
Поэтому L(x)Z f{x) на X'. Итак, мы получили цепочку соотношений
fix) = L{x)>L{x)>f(x)
Следовательно, fix') наибольшее значение функции f(x) на X'.
2. Рассмотрим произвольную точку х е X' = X. Всякая точка отрезка х'х имеет вид x(t) = x* +t(x-x*), t є[0;1]. Пусть <P(t) f (x(t)) ограничение функции/на отрезок х'х . Поскольку отрезок х'х целиком содержится ъ X, a f (х') = q>(0) наибольшее значение / на X, то для любого ' є[0;1] имеем неравенство (p(0)>(p(t). Следовательно,
С другой стороны, по формуле (3.20) имеем <p'(0) = (gradf(x'),x-x'), поэтому для любой точки х еХ выполняется неравенство (grad/(x*),* -**)< 0
или
(grad/(jf*X *)<(grad/(;c*), х'). (3.58)
Положим с, = ^* с(х) = сххх+...+с„х„. Тогда из неравенства
ас,
(3.58) следует, что х' оптимальное решение следующей задачи линейного программирования:
(I) с(х) —> max, при условиях (3.59)
Далее, для простоты записи, считаем, что п-2, 5 = 3. Линейные функции /Дх) запишем следующим образом: /, (х) = Ь, а1х1 а,2х2, і = 1,2,3. Тогда задача (I) примет вид
" а2]Х +a22X2^bl'
(I)
агххх +аг2х2 <Ъъ, с|х, + с2х2 -> max.
ляются линейными уравнениями. Задача линейного программирования, двойственная к (I), выглядит так:
' агУ) +аггУг + йз2.Уз = ci>
(II) I У] > 0,у2 > 0,у, > О,
Ь}у{ +Ь2у2 + Ьъуъ -» min. По основной теореме двойственности из разрешимости задачи (I) следует разрешимость задачи (II). Пусть у' = (у",у,у)оптимальное решение задачи (И). Положим Я, = у', А, у'. A3 = у'3. Для заданных таким образом множителей Лагранжа имеем
' ' дх2
= с< Vn V31 о. я(0.
а2 ~^
cJL(x') = c>f(x-) ( ^ dl,(x) t <?/2(х') t ^ ^(х') =
Аналогично
с2 Ьап Я,*22 V32 = о. Итак, условие а)
выполнено. Условие б) выполняется вследствие теоремы равновесия для пары двойственных задач (I) и (II).
Из доказательства теоремы 3.17 видна глубокая связь этой теоремы с двойственностью в линейном программировании. Так, множители Лагранжа Я,,..., As можно интерпретировать как двойственные переменные.
Пример 3.28. Найти точку глобального максимума функции z = In х, + In х2 + In х3 при условии х, + 2х, + Зхя < 90.
Решение. Составим функцию Лагранжа:
L(x) = In х, + In х2 + In x3 + Л(90 x, 2x2 3x3). Затем запишем условия Куна-Таккера:
• 2Я = 0,
і
ЗЛ = 0,
Я(90-х,-2х3-Зх3) = 0. Л >0.
Из первых трех уравнений следует, что х, = — ,х2 = — ,х3 = —,
А, 2.А ЗЛ,
причем Л * 0 Поэтому из четвертого уравнения получаем
3
90-х.-2х2-Зх, =90— = 0.
Следовательно, а = = 30,дг2 = 15,х3 = 10. Функция z вогнута в
области определения, поэтому х' = (30;15;10)точка глобального максимума.
Теорема 3.18. Строго выпуклая (строго вогнутая) функция /(х) на выпуклом множестве X a R" не может иметь более одной точки глобального максимума (минимума).
Доказательство этой теоремы почти дословно повторяет доказательство теоремы 2.25, поэтому мы его не приводим.
Замечание. Функция z из примера 3.28 является строго вогнутой, поэтому найденная в нем точка х* единственная точка глобального максимума.
Теорема 3.17 может применяться не только для определения наибольшего значения вогнутой функции, но также и для определения наименьшего значения выпуклой функции. Действительно,
пусть f(x) выпуклая функция на выпуклом множестве X <z R". Определим функцию g{x) на области определения функции f(x) (которая может быть больше X) формулой g(x)= -fix). Тогда функция g{x) будет вогнутой на X. Применяя теорему 3.17, во многих случаях удается найти точку х* глобального максимума g(x) на X. Очевидно, что х* одновременно будет и точкой глобального минимума /(х) на X.
Пример 3.29. Фирма, производящая продукцию на трех заводах, решила выпускать в месяц не менее 210 единиц продукции при наименьших суммарных затратах. Сколько продукции ежемесячно следует выпускать на каждом заводе, если функции издержек заводов имеют вид;
1 ,
С,(х,) = х, + — х, для первого завода; С2(х2) = хг+-^х] для второго завода; С,(х,) = 2х3+-^-Хз для третьего завода?
14-1.«
209
Решение. Необходимо найти точку глобального минимума функции f(x) = Cl(x() + C2(x2) + CJ(xJ) при условии /(х)>0, где линейная функция 1(х) определяется равенством /(*) = *, +х2 + х3 -210. Данная задача эквивалентна задаче на
максимум для функции g(x) ~ -f(x). Поэтому функция Лагран-жа будет
1 20Х| х2 7^л:2-2х3-—х3^ +
* 2 __LY2_7r 1_-2 ■
20 1 2 40 2 3 60
+ А(х, +х2 + х3 -210).
Условия Куна-Таккера примут вид:
1
Я-1—X, =0, 10 1
А-1— х2 =0, 20 2
А-2— х3 =0, 30 3
А(х,+х2+х3-210) = 0. А>0.
Из первых трех уравнений находим:
х, = 10А-10,х2 = 20А-20,х3 = ЗОЯ-60.
По смыслу задачи все х, > 0, поэтому сначала будем искать решение системы Куна-Таккера, предполагая, что А > 0. Тогда из четвертого уравнения вытекает равенство
х, +х2 +х3 -210 = 60Я-90-210 = 0,
откуда Я = 5, х, = 40, х2 = 80, х3 = 90. Следовательно, х' =(40; 80; 90) точка глобального минимума функции затрат при условии
х, +х2 + х3 > 210.
Так как f(x) строго выпуклая функция, то других точек глобального минимума не существует.
Мы уже отмечали аналогию между множителями Лагранжа и двойственными переменными в задаче линейного программирования. Эта аналогия имеет дальнейшее развитие: если выпуклое множество X задается системой линейных ограничений, содержащей как неравенства (/,(х) > 0) (/ = 1,...,/и), так и уравнения lj(x) = 0 (j = 1,...,к), то множители Лагранжа Х}, соответствующие уравнениям, не имеют условия неотрицательности. Так же как и в теории двойственности, это утверждение легко выводится из эквивалентности одного уравнения /(*) = о двум неравенствам
/(х)>0 и -/(х)>0.
Итак, условия Куна-Таккера б) записываются только для множителей Лагранжа А,, соответствующих неравенствам. Теорема 3.17 остается при этом в силе.
Пример 3.30. Найти все точки глобального минимума функции
/(x) = i(x2+x2+x2)
при условиях: х, > 0,х2 > 0,х3 > 0 и х, + 2х2 + Зх3 = 140.
Решение. Составим функцию Лагранжа для функции -Дх):
Дх) = -у(х2 +х2 +х3)+А,х, +А2х2 +А3х3 + А4(х, +2х2 +3х2 -140). Затем запишем условия Куна-Таккера:
х, + Я, + Я4 = 0, -х2 + а + 2А4 =0, < х3 + A3 + ЗА4 = 0, Я,Х| = 0, А^ = 0,АзХ3 = 0, А, >0,А2 >0,Яз>0. Далее, вообще говоря, необходимо рассмотреть 8 случаев:
А, =0, Aj =0,Яз = 0; 5) А, фО,^ =0, A3 =0;
^=0^=0^*0; 6) А, *0, Aj =0,Аз *0;
Я, = 0, А? * 0,Аз = 0; 7) А, * 0, а ф 0,Aj = 0;
А, =0, Aj *0,Аз *0; 8) А, ф0, ^ фО,^ ф0.
Однако следует помнить, что /(х) строго выпуклая функция и на любом выпуклом множестве у нее не более одной точки глобального минимума. Поэтому, как только при разборе случаев 1 )-8) обнаруживается решение системы Куна-Таккера, рассмотрение оставшихся случаев становится нецелесообразным.
14* 211
'jc, + А4 = О, < х2 + 2А4 = О, -хг + ЗД4 = 0.
Из этих уравнений следует, что х, = Д4, х2 = 2ЯА, хъ = ЗЛ4. Используя исходное ограничение х, +2х2 +3л;3 = 140, получим 14Д4 = 140. Откуда
Л4 = 10, х, = 10, х2=20, х3= 30.
Остальные случаи разбирать не имеет смысла: дг* = (10; 20; 30) -единственная точка глобального минимума.
Обсуждение Математика в экономике Часть 2
Комментарии, рецензии и отзывы