Имя материала: Математика в экономике Часть 2

Автор: Солодовников А.С.

§ 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

Начнем со случая 1). Перепишем условия Куна-Таккера:

'- 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) -единственная точка глобального минимума.

 

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 |