§ 3.15. наибольшее значение вогнутой функции

§ 3.15. наибольшее значение вогнутой функции: Математика в экономике Часть 2, Солодовников А.С., 2000 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Во второй части учебника изучаются математический анализ функций одной и нескольких переменных, выпуклый анализ, ряды и дифференциальные уравнения. Для преподавателей и студентов экономических вузов и факультетов, бизнес-школ, колледжей.

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

Математика в экономике Часть 2

Математика в экономике Часть 2

Обсуждение Математика в экономике Часть 2

Комментарии, рецензии и отзывы

§ 3.15. наибольшее значение вогнутой функции: Математика в экономике Часть 2, Солодовников А.С., 2000 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Во второй части учебника изучаются математический анализ функций одной и нескольких переменных, выпуклый анализ, ряды и дифференциальные уравнения. Для преподавателей и студентов экономических вузов и факультетов, бизнес-школ, колледжей.