f (X )≤ f (X0 ) ( f (X )≥ f (X0 )) для всех точек X M .

Точки локального условного и глобального максимума (минимума) функции y = f (X ) мы будем называть точками локального и,

соответственно, глобального экстремума функции y = f (X ) на мно-

жестве M Rn .

Ясно, что точка глобального экстремума f (X ) на множестве

M является одновременно и точкой локального экстремума на M . Обратное, вообще говоря, не верно. Тем не менее, для выпуклых (вогнутых) функций на выпуклых множествах верна следующая теорема.

Теорема 7.3 (о глобальном характере экстремума выпуклой функции). Если X0 – точка локального минимума (максимума) вы-

пуклой (вогнутой) функции y = f (X ) на выпуклом множестве

7.2. Теорема Куна-Таккера.

Общая задача о нахождении экстремумов функции y = f (X ) на

множестве M Rn называется задачей математического програм-

мирования. Как и в теории линейного программирования, функция y = f (X ) называется целевой функцией, а множество M Rn − до-

пустимым множеством. Далее мы подробнее остановимся на случае, когда целевая функция выпукла (вогнута), а допустимое множество является выпуклым и задано системой ограничений

g1 (X )*b1,

g2 (X )*b2 ,,

gm (X )*bm ,

где «*» обозначает «≥», «≤» или «=». Соответствующая задача

gi (x1, x2 , , xn )*bi , i =1, ,m.

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

96

Общие точные методы решения таких задач отсутствует, и часто для их решения приходится пользоваться приближенными методами решения.

Основное отличие задач выпуклого программирования от линейных задач оптимизации заключается в том, что оптимальное решение может достигаться не только в угловых точках границы, но и в ее внутренних точках.

Допустимым множеством является пятиугольник OABCD с угловы-

функции f лежит, очевидно, вне многоугольника OABCD. Далее, линиями уровня целевой функции являются концентрические окружности (x −16)2 +(y −12)2 = C с центром в точке (16,12). Поэтому ми-

нимальное значение функции f достигается в точке касания с отрезком BC окружности соответствующего радиуса, а максимальное значение – в точке O(0,0).

Найдем точку касания K как точку пересечения прямой l1 и прямой m1 , перпендикулярной l1 и проходящей через точку E (16,12). Так как прямая l1 определяется уравнением 2x + y =19, то вектор нормали к ней, равный n = (2,1), является направляющим вектором для прямой m1 . Таким образом, каноническое и общее уравнения m1 имеют вид x−216 = y−112 и x −2y = −8 соответственно. Точка пересече-

97

fmax = f (O)= f (0,0)= (0 −16)2 +(0 −12)2 = 400.

Отметим, что оба оптимальных решения задачи достигаются на границе области, причем одно из них – в ее угловой точке, а другое – во внутренней точке граничного отрезка.

Предположим теперь, что в пространстве заданы m функций

g1 (X ), g2 (X ), , gm (X ), и множество M Rn задано системой ограничений

Таким образом, первые k условий − условия типа неравенств, а оставшиеся − условия типа равенств.

Определение 7.3. Говорят, что система ограничений (7.1) удовлетворяет условию регулярности, если функции g1, g2 , , gm яв-

ляются вогнутыми, и существует точка X * M , такая, что все нелинейные функции среди g1, g2 , , gm больше нуля в этой точке.

Условие регулярности системы ограничений задачи выпуклого программирования иногда называют условием Слейтера. Таким об-

разом, должна существовать точка X * M , являющаяся внутренней для всех множеств, заданных условиями вида gr (X )≥ 0 для нели-

нейных функций gr (X ),r =1, ,m .

Заметим, что условие Слейтера означает, что каждая из входящих в нее нелинейных функций отлична от нуля в некоторых точках M . С др угой стороны, среди ограничений, определяющих M , есть

условия типа равенств gr (X )= 0, r = k +1, ,m .

Следствие 7.1. Функции gk+1 (X ), gk+2 (X ), , gm (X ) являются линейными.

Кроме этого, условие регулярности системы ограничений накладывает некоторые ограничения на структуру множества M .

Следствие 7.2. Множество M , заданное системой ограничений (7.1), является выпуклым.

Определим теперь функцию Лагранжа

m

L (X , Λ)= f (X )+∑λi gi (X ),

i=1

98

где Λ = (λ1, λ2 , , λm ), и сформулируем общую теорему о решении

задачи выпуклого программирования.

Теорема 7.4 (Куна-Таккера). Пусть M Rn – выпуклое множество, заданное регулярной системой ограничений (7.1), функция

y = f (X ) – вогнутая, а функции f , g1, g2 , , gm – дифференцируемы на M . Для того, чтобы точка X0 M являлась точкой глобального максимума функции y = f (X ) на M , необходимо и достаточно,

чтобы существовал вектор Λ0 = (λ10 ,λ20 , λm0 ) Rm , удовлетворяю-

щий условиям

Lx′i (X0 ,Λ0 )= 0, i =1, ,n ,

λi0 gi (X0 )= 0, λi0 ≥ 0 , i =1, ,k .

Пример 7.4. Рассмотрим задачу из примера 7.3 и проверим, что точка X0 = (6,7) удовлетворяет условиям теоремы Куна-Таккера.

Перепишем систему ограничений в виде

L(X ,Λ) = −(x −16)2 −(y −12)2 +λ1 (−2x − y +19)+

+λ2 (3x −5y +30)+λ3 (−5x +4y +15) +λ4 x +λ5 y.

Теперь мы можем записать условия теоремы в виде системы:

Lx′= −2(x −16) −2λ1 +3λ2 −5λ3 +λ4 = 0,

Ly′= −2(y −12) −λ1 −5λ2 +4λ3 +λ5 = 0,

λ1 (−2x − y +19) = 0,λ2 (3x −5y +30)= 0,λ3 (−5x + 4y +15)= 0,λ4 x = 0, λ5 y = 0,

λi ≥ 0,i =1, ,5.

99

Пример 7.5. Найдите объемы ресурсов K и L , при которых затраты на производство не менее 80 единиц продукции минимальны,

если производственная функция Кобба–Дугласа Q(K, L)= K 34 L14 , а цены на ресурсы pK = 6 , pL = 2.

Решение. Поскольку целевая функция имеет вид

f(K, L)= pK K + pL L , то имеем задачу

f = 6K +2L → min,

K

K 34 L14 ≥80,≥ 0, L ≥ 0.

Заметим, что функция f (K, L) линейна, т.е. выпукла и вогнута одно-

временно. Далее, функция Кобба-Дугласа является вогнутой и условие регулярности, очевидно, выполнено (достаточно проверить точку

(81,81)). Теперь для применения теоремы Куна–Таккера достаточно записать постановку задачи в виде

Составим функцию Лагранжа

L = −6K −2 L +λ1 (K 34 L14 −80)+λ2 K +λ3 L.

Тогда условия теоремы Куна–Таккера записываются следующим образом:

100

λ1 ≥ 0, λ2 ≥ 0, λ3 ≥ 0.

В силу условия K 34 L14 −80 ≥ 0 получаем, что K ≠ 0, L ≠ 0 и, следо-

Таким образом, все условия Куна-Таккера выполнены и K = L =80 – производственный план с минимальными издержками, причем

fmin = f (80,80)= 640.

Задачи для самостоятельного решения

Для задач 105-107 найти оптимальное решение графическим методом и для полученного решения проверить выполнение условий теоремы Куна-Таккера;

101

108. Найдите объемы ресурсов K и L , при которых затраты на производство не менее 140 единиц продукции минимальны, если произ-

водственная функция Кобба–Дугласа Q(K, L)= K 23 L13 , а цены на ресурсы pK =12 , pL = 3.

102