Далее,	точка X0	называется	точкой глобального максимума
(минимума)	функции	y = f (X )	на множестве M Rn , если

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 ) на выпуклом множестве

M Rn , то X0	– точка глобального экстремума функции	f (X ) на
M , т.е. f (X0 )	– наименьшее (наибольшее) значение f (X )	на M .

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

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

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

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

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

g1 (X )*b1,

g2 (X )*b2 ,,

gm (X )*bm ,

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

z = f (x , x		, , x	)→ max (min)
	1 2	n

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

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

96

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

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

	y			Пример 7.3. Рассмотрим задачу
l1			поиска минимального и максимально-
		E	го	значения	функции
	B		f	= (x −16)2 +(y −12)2	в области, за-
A		K			2x + y ≤19,
l2		C
			данной условиями		−5y +3x ≥ −30,
m1	Ol3	D
			x		5x −4y ≤15,
					x ≥ 0, y ≥ 0.

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

ми точками O(0,0) ,	A(0,6),	B(5,9), C (7,5) и D(3,0). Ясно, что
fx′ = 2(x −16), fy′ = 2	(y −12).	Поэтому стационарная точка E (16,12)

функции 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 соответственно. Точка пересече-

ния K =l1 ∩m1	находится как решение системы	2x + y =19,
		x −2y = −8.
K (6,7). Таким образом, решением задачи на минимум является
точка X0 = (6,7)	и fmin = f (X0 )= f (6,7)= (6 −16)2 +(7 −12)2		=125, а

97

решением

задачи

на

максимум

–

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

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

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

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

	g	r	(X )≥ 0, r =1, ,k
					(7.1)
gr (X )= 0,				r = k +1, ,m.

Таким образом, первые 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) удовлетворяет условиям теоремы Куна-Таккера.

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

	−2x − y +19 ≥ 0,
	3x −5y +30 ≥ 0,
		4y +15 ≥ 0,
	−5x +
	x ≥ 0,
	y ≥ 0.
и	составим функцию Лагранжа для вогнутой функции
f	= −(x −16)2 −(y −12)2

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

Подставляя	x = 6, y = 7 ,	немедленно	убеждаемся,		что
λ2 = λ3 = λ4 = λ5			20 −2λ1	= 0,	от-
	= 0 , и система сводится к условиям
			10 −λ1 = 0,
куда имеем, что λ1 =10 ≥ 0, т.е. для точки X0			= (6,7) условия теоре-
мы выполнены.

Пример 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)). Теперь для применения теоремы Куна–Таккера достаточно записать постановку задачи в виде

f = −6K −2 L → max,
	K	3	1	−80 ≥ 0,
			4 L 4
	K ≥ 0,			L ≥ 0.

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

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

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

100

3		−1			1
LK′ = −6 + 4 λ1K				4	L 4	+λ2 = 0,
LL′= −2 +	1		3		−3
	4 λ1 K				4 L	4 +λ3 = 0,
λ1 (K 34 L14 −80)	= 0, λ2 K = 0, λ3 L = 0,

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

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

вательно

λ2 = λ3 = 0.

Подставляя

λ2 = 0

в первое уравнение, имеем

λ1 ≠ 0. Таким образом, мы приходим к следующей системе:

3

−1

1

=8K 14

L−14

4

λ1K

4 L

4

= 6,

λ

,

1

14

−1

=

8 K

−34 3

,

1

3

−3

−3

3

4

4

λ1

K

4 = 2,

λ1 =8 K

4 ,

8K

L

L

4

4 L

4 L

34

14

K 34 L14

=80.

K

=80.

K

34

14

=80

L

L

Из последней системы заключаем,

что K = L =80 ,

причем λ1 =8 ≥ 0.

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

fmin = f (80,80)= 640.

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

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

				2x +7 y ≤ 74,
105.	f	= (x −15)2 +(y −29)2 → min при	x ≥ 0, y ≥ 0 и
				−2y + x ≥ −18,
					2
				2x −5y ≤
				x + y ≤17,
106.	f	= (x −32)2 +(y −33)2 → min при	x ≥ 0, y ≥ 0 и
				−y +6x ≥ −3,
				3x −10y ≤12

101

		2x +3y ≤ 34,
107. f = (x −24)2 +(y −30)2 → min при x ≥ 0, y ≥ 0 и
	−y + 2x ≥ −6,
		x −5y ≤ 4

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

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

102