Решебник_МО

Решая полученную систему уравнений, найдем точки, подозрительные на экстремум. Система имеет единственное решение х1=0, х2=0,5, так что подозрительной на экстремум будет единственная точка Х0=(0; 0,5).

Из курса математического анализа известно, что если функция f(х1,х2,...,хn) имеет в некоторой окрестности точки Х0=(х10, х20,… хn0) непрерывные вторые частные производные и если в этой точке выполняются необходимые условия существования экстремума, то в

случае, когда второй дифференциал	d 2 f ( X )	n n	2 f ( X )
			xi xk
		k 1 k 1

есть отрицательно определенная квадратичная форма, то функция f(х) имеет в точке Х0 максимум, а в случае, когда этот дифференциал есть положительно определенная квадратичная форма, функция f(х) имеет в этой точке минимум.

Для

рассматриваемой

функции имеем:

2 f

2 f

2

;

x1x2

x2

1

2 f

2 f

2 ;

2 f

2 f

2

; d 2 f 2 x2

2 x2

4 x x

.

2

x1x2

x 2

x1x2

x2 x1

1

2

1

2

Квадратичная форма здесь является неопределенной, т.е. знак d2f зависит от выбора x1 и x2.

Однако непосредственно из выражения для f(x1,x2) можно установить, что в точке (0; 0,5) функция имеет седло. Этот же результат можно получить, анализируя значение определителя:

2 f

2 f

2 x12

2 x1 x2

2

2

4 4 8.

2 f

2 f

2

2

2 x x

2

2 x 2

1

2

Для случая двух переменных, если ∆>0 и

2 f

<0, то f(х) в

2 x 2

1

точке X

0

имеет максимум, если ∆>0 и

2 f

>0 – минимум, а когда

2 x 2

1

∆<0, то в точке Х0 функция f(Х) имеет перегиб. Если ∆=0, то наличие

21

максимума или минимума можно определить с помощью приращений

х1 и х2.

В нашем случае ∆<0 и, следовательно, в точке Х0=(0;0,5) функция f(х1, х2) имеет перегиб.

НЕОБХОДИМЫЕ УСЛОВИЯ СУЩЕСТВОВАНИЯ ЭКСТРЕМУМА ФУНКЦИИ ПРИ РАЗЛИЧНЫХ ВИДАХ ОГРАНИЧЕНИЙ

Пусть имеется некоторая функция f(x1,x2,...,xn) в определенной области G значений переменных X=(xl,х2,...,xn). Область G задается системой неравенств вида gj(xl,х2,…, xn)≥bj, j=l,2,…,m. Предполагается, что точка X=(xl,х2,...,xn) и функции ограничений gj(x) принадлежат n - мерному действительному эвклидову пространству Rn, причем f(X), gj(Х) определены в пространстве непрерывных функций, частные производные которых также являются непрерывными функциями.

Методы исследования при наличии ограничений на область изменения независимых переменных можно использовать только для отыскания экстремальных значений внутри указанной области. В особенности это относится к задачам с большим числом независимых переменных (практически больше двух), в которых анализ значений критерия оптимальности на границе допустимой области изменения переменных становится весьма сложным.

В зависимости от вида ограничений будут различны и необходимые условия существования экстремума.

1. Когда на значения параметров X ограничений нет, оптимизация сводится к поиску безусловного экстремума. Необходимым условием при этом является условие обращения в нуль частных производных, т. е.

f (X0 ) = 0 или f ( X 0 ) 0,

(1)

x i

где Х0 – точка экстремума целевой функции и i I={1,2,...,n},

2. Если имеются несвободных переменных хi 0 и требуется определить необходимые условия положения экстремума (максимума) функции, то решением этой задачи будет такая точка Х0, которая находится либо внутри области допустимых значений, либо на ее границе.

22

Если Х0 находится внутри области допустимых значений, то требование хi 0 (требование неотрицательности) является несущественным, и необходимым условием положения экстремума будет стандартное условие (т.е. равенство 0 частных производных

функции): f (x0 ) 0 , i I={1,2,...,n}.xi

Пусть для некоторых несвободных переменных .хi ≥ 0,

i {1,…,n} экстремум достигается на границе области, тогда для них

имеем	f (x	0 )	0 . Соединяя два указанных условия, получим условие
	xi
дополняющей нежёсткости:
			xi f (x0 ) 0	или xoi f (X 0 ) 0	(2)
			xi

для несвободных переменных хi 0.

3. Если в задаче требуется найти экстремум функции при наличии ограничений в виде равенств g j (x) b j , где j 1, m , то

используется метод неопределенных множителей Лагранжа.

Основная идея метода состоит в переходе от задачи на условный экстремум к задаче отыскания безусловного экстремума некоторой построенной функции Лагранжа:

m

F(X,Λ)=f(X)+ j [gi ( X ) b j ], (3)

j 1

где f(X) – исходная целевая функция, gj(X)–bj – ограниченияравенства,

λj – неизвестные (неопределенные) множители Лагранжа. Необходимые условия положения экстремума (максимума)

функции следующие:

F ( X 0 , 0 ) 0,	F ( X 0 , 0 )	0	или F(X 0 , 0 ) 0,	(4)
xi	i

где i=1,2,...,n; j=1,2,...,m.

4. При наличии ограничений-неравенств (gj(X)–b) 0 необходимые условия положения экстремума следующие:

23

F(X 0 , 0 ) 0,	j	F(X 0, 0 ) 0	или xF(X 0, 0) 0,	j F(X 0, 0) 0,	(5)
xi		i

где i=1,2,...,n; j=1,2,…,m.

5. В общей задаче математического программирования для различных типов переменных и ограничений необходимые условия положения экстремума представляют совокупность всех ранее рассмотренных условий (1, 2, 4, 5), т. е.

F ( X 0 , 0 ) 0			для свободных переменных xi, i {1,…k};
	xi
xi	F ( X 0 , 0 ) 0		для xi 0, i {k+1,…n};
	xi
F ( X 0 , 0 ) 0			для ограничений-равенств gj(х)–bj = 0, j {1,…l};
	j
j	F ( X 0 , 0 )	0	для ограничений-неравенств gj(х)–bj ≥ 0,
	j

j {l+1,…,m}.

РЕШЕНИЕ ОБЩЕЙ ЗАДАЧИ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Для решения общей задачи математического программирования применяют следующий алгоритм.

1. Нумеруют подряд все ограничения неравенства вида x 0 и

gj(х)–bj ≥0.

2. Находят положение maxf(X) при отсутствии всех ограниченийнеравенств. Если найденная точка X0 удовлетворяет всем ограничениям-неравенствам, то задача решена. Если точка Х0 не удовлетворяет первым l неравенствам, то переходят к п. 3, приняв ν=1.

3. Решают методом Лагранжа C v	l!		задач поиска maxf(X),
l	v!(l v)!

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

4.Все полученные точки проверяют на соответствие

отброшенным неравенствам и выбирают те из них, которые

24

принадлежат допустимой области. Решением задачи является одна из выбранных точек, в которой целевая функция достигает наибольшего значения. Если таких точек не оказалось, то полагают ν:=ν+1 и переходят к п. 3 алгоритма.

Пример 2. Требуется найти max f (x) x при ограничениях

x12 x22 1 , (x1 1)2 x22 1 , x1 x2 1.

Решение. В соответствии с приведенным выше алгоритмом решения задачи математического программирования необходимо пронумеровать подряд все ограничения неравенства и найти положение maxf(X) при их отсутствии. В худшем случае придется решить семь задач поиска max f(Х) методом Лагранжа. Допустимые области значений параметров этих задач будут заданы следующим образом:

1) x 2				x 2				1 0;	2) (x 1) 2 x 2						1 0;		3) x x			2	1 0;
		1				2			1					2			1
		x	2	x			2	1 0,			2	x	2	1	0,			1)	2	x		2	1 0,
									x							(x
4)		1					2		5)	1			2			6)	1					2
(x		1) 2 x 2 1 0;							x x				2	1 0;			x x			2	1 0;
	1							2			1						1
		x12 x22 1 0,
		1)			2			2
7) (x1						x2 1 0,
		x1 x2						1 0.

В данном примере целевая функция линейна и, следовательно, не ограничена.

Составим функцию Лагранжа с учетом первого ограничениянеравенства, рассматривая его как ограничение равенством:

F(x1, x2 , ) f (x1, x2 ) 1(x12 x22 1) x 1(x12 x22 1) .

Решим задачу поиска maxF(X,λ1). Найдем частные производные функции Лагранжа по всем переменным и приравняем их к нулю:

F ( X , ) 1 2 x 0,	F ( X , ) 2 x 0,		F ( X , ) (x 2	x 2	1) 0.
1 1	1	2	1	2
x1	x2		1

Решая полученную систему уравнений, получим из первого

уравнения x1 1 , из второго –х2=0 или λ1=0.

2 1

25

В случае λ1=0 получаем x1 , поэтому этот вариант

значения λ1 отбрасываем. После подстановки значений х1 и х2 третье уравнение получаем

1 14 0,5 , а x1 1 .

Полученные точки Х1=(1;0) и Х2=(–1;0) проверим на соответствие отброшенным неравенствам. Точка Х1=(1;0) не

удовлетворяет второму ограничению (x1 1)2 x22 1 , а точка

Х2=(–1;0) удовлетворяет всем ограничениям, поэтому остальные шесть задач можно не решать.

В качестве решения задачи принимается точка Х=(–1;0), в которой целевая функция f(x)=1.

Пример 3.		Пусть		требуется найти max f (x) x1 при ограничениях
x2	x2		2 и	x x 4 .
1		2		1	3

Решение. В данной задаче имеется два ограничения равенством и отсутствуют ограничения-неравенства. Для нахождения максимума заданной функции составим функцию Лагранжа:

F(X,Λ)=f(х)+λ2( x2			x2	2 )+λ1( x	x	4 )=
		1	2	1	3
= x	1	+λ1( x x 4 )+λ2( x 2			x 2	2 ).
		1	3	1	2

Решим задачу поиска maxF(X,Λ). Найдем частные производные составленной функции Лагранжа по всем переменным и

приравняем их нулю:
		F			1 2x				0	,		F		2x					0 ,				F	0	,
								2								2		2
		x1		1			1					x2											1
																						x3
		F			x x		4 0 ,					F		x 2		x 2				2 0 .
						3
		1		1								2			1				2
		Решая полученную								систему уравнений,													получим		λ1=0 и
x	1				, а из второго уравнения –х										=0 или λ						=0.
1	2 2											2								2
		В			случае		λ2=0		получаем x1 ,											поэтому этот					вариант

значения λ1 отбрасываем. После подстановки значений х2 в последнее

					1
уравнение получаем х1=	2 , тогда 2							и х3=4–( 2 ).
					(
			2			2)

26

Проверяя на принадлежность области допустимых значений функции полученные точки Х1=( 2 ;0;4+ 2 ), Х2=( 2 ;0;4– 2 ),

Х3=(– 2 ;0;4+ 2 ), Х4=(– 2 ;0;4– 2 ), получим, что четвертая точка не удовлетворяет первому ограничению.

Вычислим значение функции в трех точках : f(Х1)= 2 , f(Х2)=

= 2 и f(Х3)= – 2 , следовательно, два первых решения системы могут быть взяты в качестве решения задачи.

Пример 4. Пусть требуется		найти		max f (x) x1 2x2 3x3 при
3		3
ограничениях xi2	1 0 ,	xi	1	0 , х3≥0.
i 1		i 1

Решение. В соответствии с приведенным выше алгоритмом решения общей задачи математического программирования для нахождения максимума заданной функции в худшем случае придется решить четыре задачи поиска maxf(Х) методом Лагранжа. Допустимые области значений параметров этих задач будут заданы следующим образом:

			3
	3		xi2	1 0
	1) xi2	1 0 ; 2) i 1
	i 1		3	1 0
			xi
		i 1

3 2

3)xii 1x3

			3
			xi 1			0
1 0,	4)	i 1
				3
0;			xi 1 0
		i 1
					0
		x		3

Найдем решение первой из этих задач, т.е. будем искать:

max f (x) x1 2x2 3x3 при							3
				ограничении			xi2	1 0		. Составим
							i 1
				3					3x	3
функцию Лагранжа: F(X,Λ)=f(х)+λ( x 2 1 )= x 2x								2		+λ ( x2	1 ).
				i			1		3	i
				i 1						i 1
Найдем частные производные составленной функции
Лагранжа по всем переменным и приравняем их нулю:
	F		1 2x 0	(a);	F	2 2x			0	(b);
								2
1					x2
	x1
	F				F		3
			3 2x3 0	(c);			xi2 1 0 (d).
	x3						i 1

27

Умножив (a), (b), (c) на х1, х2, х3 соответственно и просуммировав результаты, получаем:

3		F										3
x			(x	2x 2	) ( 2x		2x 2	) (3x		2x 2	)	f ( X ) 2 x2		0.
	i xi
i 1			1	1		2	2		3	3		i 1	i

С учетом первого ограничения имеем: f(х)+2λ=0, откуда = –0,5f(х).

Подставим найденное значение																в (a), (b),							(c) и получим f(х)=1/х1,
f(х)= –2/х2, f(х)=3/х3. Значит, 1/х1=3/х3																		откуда х1=											1			х3,						а 3/х3= –2/х2,
																											3
откуда х2=	2		х3.			Тогда				f(х)= x						2x 3x							1	x			4	x						3x							14		x			.			Но
	3																						3				3
												1							3						3							3							3	3					3
f(х)=3/х3, следовательно,								14	x3			3			и, отсюда,									x3									3					. Поскольку в
							3					x3																					14
силу ограничения						(с)	х3≥0, то принимаем																		x30								3			=0,8.									Теперь
																																	14
получаем x0			1			=0,27, x0						2				=–0,54.
1			14				2					14
Проверим						ограничение						(в):					x	x				x				1							1					2		3						2			1.
																				2					3
																	1																		14											14

Следовательно X0 принадлежит допустимой области. Поэтому оставшиеся три задачи можно не решать, а в качестве решения

принимаем X0: f ( X 0 ) 14 =3,74.

ДВОЙСТВЕННАЯ ЗАДАЧА

Задача поиска минимума функции Лагранжа F(X, λ) по называется двойственной по отношению к прямой задаче нахождения максимума функции Лагранжа F(X, λ) по Х.

Любую задачу математического программирования можно рассматривать как двойственную.

Построение задачи, двойственной к исходной, осуществляется по правилу, приведенному в табл. 1.

Теорема, сформулированая Куном и Такером доказывает, что решение обеих задач прямой и двойственной достигается в одной и той же точке (Х0;0), которая является седловой точкой.

28

Таблица 1

Прямая задача

Двойственная задача

n

m

max[ f (x) j (g j (x) b j )]

min[ f (x)

j (g j (x) b j )]

x

j 1

j 1

x – свободные переменные,

F

F (x)

m

j

g j (x)

0

–

i

i {1,…,k}

xi

xi

j 1

xi

ограничения-равенства, i {1,…,k}

xi 0 – несвободная

F (x)

m

g j (x)

j

0

, ограничения-

переменная, i {k+1,…,n}

xi

xi

j 1

неравенства, i {k+1,…,n}

g j (x) b j 0 – ограничения-

j – свободные переменные, j {1,,l}

равенства, j {1,…,l}

g j (x) b j 0 , ограничения-

j

0 – несвободные переменные,

неравенства, j {l+1,…,m}

j {l+1,…,m}

Пример.

Требуется

составить

задачу,

двойственную

к

прямой:

3

3

определите

maxF(X)= ci xi

при

ограничениях

xi

100 0 ,

i 1

i 1

3

0,5ai xi2 1000

0

и xi ≥0, где i {1,2,3}.

i 1

Решение. Составим функцию Лагранжа и сформулируем

двойственную задачу в соответствии с правилом согласно табл. 1:

3

3

100)

3

x2

1000)

F(X,λ)= c

x

i

( x

i

2

( 0,5a

– функция

i

1

i

i

i 1

i 1

i 1

Лагранжа для исходной задачи. Элементы двойственной задачи будут иметь следующий вид:

Прямая задача			Двойственная задача
max F(X, )			min	F(X, )
X
Несвободные переменные:	Ограничения-неравенства
xi≥0, i=1,2,3		F	≥0, i=1,2,3:	с1+λ1+λ2*а1х1≥0,
		x
		i
	с2+λ1+λ2*а2х2≥0, с2+λ1+λ2*а3х3≥0

29

Свободные переменные	Ограничения-равенства
отсутствуют	отсутствуют
Ограничения-равенства:	Свободная переменная
3	λ1
xi 100 0
i 1
Ограничения-неравенства:	Несвободная переменная
3	2 0
0,5ai xi2 1000 0
i 1

Пример 6. Составьте двойственную задачу для задания: требуется

найти	максимум			функции			f (x) x1x2 x2 x3			при
ограничениях x 2		x	2	2 0	и x	2	x	3	2 0 .
	1		2

Решение. Составим функцию Лагранжа для данной задачи:

F(X,λ)= x1x2 x2 x3 +λ1( x12 x22 2 )+λ2( x2 x3 2 ).

Тогда соответствие между прямой и двойственной задачами будут иметь следующий вид:

	Прямая задача			Двойственная задача
	max F(X, )			min		F(X, )
	X
Несвободные переменные		Ограничения-неравенства
xi≥0 отсутствуют		отсутствуют
Свободные переменные:		Ограничения-равенства
xi, i=1,2,3			F	=0, i=1,2,3: x		2x 0,
					2
			xi			1
			x1 x3 2x2 2 0, x2 2 0
Ограничения-равенства:		Свободные переменные:
x12 x22	2 =0,	λ1,
x2 x3	2 =0	λ2
Ограничения-неравенства		Несвободные переменные
отсутствуют		отсутствуют

30