Добавил:

Teana Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Таврический Национальный Университет им. В.И. Вернадского

Предмет:

Экономика

Файл:

Методы оптимизации - Харчистов Б.Ф.

.pdf

Скачиваний:

137

Добавлен:

24.05.2014

Размер:

931 Кб

Скачать

☆

<<< < Предыдущая 1 2 34 / 144 5 6 7 8 9 10 11 12 13 14 > Следующая >>>

F(z) = z1 + z2 = (−4x1 − 2x2 + 4 − λ + v1 ) +

+(−2x1 − 4x2 + 6 − 2λ + v2 ) = 10 − 6x1 − 6x2 − 3λ + v1 + v2 .

Составляем вспомогательную задачу ЛП:

F (z) = 10 − 6x1 − 6x2 − 3λ + v1 + v2 → min,

4x1 + 2x2 + λ − v1 + z1 = 4, 2x1 + 4x2 + 2λ − v2 + z2 = 6, x1 + 2x2 + w = 2,

x1, x2 , λ, v1, v2 , w, z1, z2 ≥ 0.

Решаем задачу симплекс-методом с учетом условий дополняющей нежесткости. В качестве базисных выберем перемен-

ные z1 , z2			и w . Таким образом, начальный базис Б0 = {z1, z2 , w}.
В результате приходим к табл. 3.1.												Таблица 3.1
				↓								Таблица 3.1
				↓
	Базис		Своб.	x1			x2	λ	v1	v2	w		z1	z2
	Базис		член	x1			x2	λ	v1	v2	w		z1	z2
→
→		z1	4	4			2	1	−1	0	0		1	0	4/4=1

		z2	6	2		4		2	0	−1	0		0	1	6/2=3

		w	2	1		2		0	0	0	1		0	0	2/1=2

		F	10	6		6		3	−1	−1	0		0	0
															ДБР0=
		Начальное			допустимое				базисное			решение			ДБР0=
= (z1		= 4, z2 = 6, w = 2). ДБР0 не является оптимальным, посколь-

ку в строке целевой функции есть положительные коэффициенты

Fx1 = 6 , Fx2 = 6 , Fλ = 3.

Согласно условиям дополняющей нежесткости, в базис можно вводить x1, так как v1 = 0 , либо x2 , так как v2 = 0 , но нель-

								32
зя вводить λ , так как w > 0 . Находим Б1 :
			Fx		> 0		→ x1 вводим в базис,
				1
	4		6			2
min		= 1,		=	3,		= 2	= 1	→	z1 выводим из базиса.
min	4	= 1,	2	=	3,	1	= 2	= 1	→	z1 выводим из базиса.
	4		2			1

Таким образом, Б1 = {x1, z2 , w}. В результате приходим к

табл. 3.2.

Таблица 3.2

				↓
	Базис	Своб.	x	x	λ	v	v	w	z	z	2
		член	1	2		1	2		1		2
		член
	x1	1	1	1/2	1/4	−1/4	0	0	1/4	0		2

	z2	4	0	3	3/2	1/2	−1	0	−1/2	1		4/3
→
→	w	1	0	3/2	−1/4	1/4	0	1	−1/4	0		2/3

	F	4	0	3	3/2	1/2	−1	0	−3/2	0

	Получили		ДБР1 = (x1 = 1, z2 = 4, w = 1).					ДБР1 не является

оптимальным, поскольку в строке целевой функции есть положи-

тельные коэффициенты F

= 3 ,

= 3 и

F = 1 .

ν1

Согласно условиям дополняющей нежесткости, в базис

можно вводить x2 ,

так как v2 = 0 ,

но нельзя вводить λ, так как

w > 0 , и v1 , так как x1 > 0 . Находим Б2 :

Fx2 > 0

→ x2

вводим в базис,

1 2

→ w

min

= 2,

выводим из базиса.

Таким образом, Б2 = {x1, x2 , z2}. В результате приходим к табл. 3.3.

						33
					↓					Таблица 3.3
					↓
	Базис	Своб.	x	x	λ			v	v	w	z	z	2
		член	1	2			1		2		1		2
		член
	x1	2/3	1	0	1/3			−1/3	0	−1/3	1/3	0		2

	x2	2/3	0	1	−1/6		1/6		0	2/3	−1/6	0
→
→	z2	2	0	0	2			0	−1	−2	0	1		1

	F	2	0	0	2		0		−1	−2	−1	0

Получили	ДБР2		=	2	,	x2	=	2	,	z2	= 2		ДБР2 не явля-
		= x1		3				3				.

ется оптимальным, поскольку в строке целевой функции есть по-

ложительный коэффициент Fλ = 2 .

Согласно условиям дополняющей нежесткости, в базис

можно вводить λ, так как w = 0 . Находим Б3 :

Fλ > 0

→ λ вводим в базис,

→ z2

min

= 2,

1 = 1

выводим из базиса.

Таким образом, Б3 = {x1, x2 , λ} . В результате приходим к

табл. 3.4.

Таблица 3.4

Базис

Своб.

член

1/3

−1/3

1/6

1/3

−1/6

5/6

1/6

−1/12

1/2

−1/6

1/12

Окончание табл. 3.4

λ	1	0		0		1	0		−1/2	−1	0	1/2

F	0	0		0		0	0		0	0	−1	−1

	Получили		ДБР3		= (x1 = 1 3,		x2	= 5 6,		λ = 1).	ДБР3	явля-

ется оптимальным решением.

Таким образом, вспомогательная задача ЛП решена. Поскольку min F(z) = 0, то оптимальное ДБР вспомога-

		z									x* задачи КП. Поэтому по-
тельной задачи определяет решение											x* задачи КП. Поэтому по-
лагаем		x* = (x* = 1 3, x*											5 6),
		x* = (x* = 1 3, x*										=	5 6),
						1				2
f * = f (x*) = 2			1				1	5			25		1		5		1
f * = f (x*) = 2			9 + 2				3	6 + 2			36		− 4 3	− 6	6	= −4	6 .
Ответ: x	*	1	,	5			f	*	= −4		1	.
Ответ: x		=	,	6	,		f		= −4		6	.
		3		6							6

Задачи

1. Решить задачу квадратичного программирования

f (x) = 2x12 + 3x22 + 4x1x2 − 6x1 − 3x2 → min , x1 + x2 ≤ 1,

2x1 + 3x2 ≤ 4 ,

x1 ≥ 0, x2 ≥ 0.

2. Решить задачу квадратичного программирования

f (x) = x1 + 2x2 − x22 → max , 3x1 + 2x2 ≤ 6 ,

x1 + 2x2 ≤ 4 , x1 ≥ 0, x2 ≥ 0.

4. ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ (МИНИМИЗАЦИИ) УНИМОДАЛЬНЫХ ФУНКЦИЙ

Унимодальными называются функции, имеющие на заданном отрезке ∆ = [a, b] единственный экстремум. На практиче-

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

Пусть f(x) унимодальна на ∆, x1, x2 ∆, x1 < x2. Тогда, ес-

ли f (x ) ≤ f (x ) , то		x* ≤ x ; если же		f (x	) ≥ f (x	) , то x* ≥ x .
1	2		2	1	2	1
Таким образом, на основании вычисленных значений f(x)
можно указать отрезок ∆′ = [a′, b′], в котором заключена точка x ,
меньшей	длины,	чем	исходный	отрезок		∆ = [a, b], т.е.
L′ = b′ − a′ < L = b − a.		Говорят, что точка минимума x локализо-
вана в отрезке [a′, b′], при этом сам отрезок называют отрезком
локализации минимума.
На	практических		занятиях рассматриваются алгоритмы

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

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

∆i = [ai ,bi ] и Li = bi − ai , i = 1,2,", − соответственно отрезок локализации и его длина после i вычислений значений f(x),

∆0 ≡ [a,b], L0 ≡ b − a;

N – количество вычислений значений f(x).

Исходными данными для решения задачи минимизации унимодальной функции являются исходный отрезок локализации

∆0 и N, результатами решения − итоговый отрезок локализации

∆N , а также оценки точки минимума x и величины минимума

f * .

4.1. ПАССИВНЫЙ МЕТОД ПОИСКА МИНИМУМА

Метод оптимизации называется пассивным, когда все точки xi , i = 1, N, вычислений характеристик задачи (в данном слу-

чае значений целевой функции) выбираются одновременно до начала вычислений.

Если N четное, т.е. N = 2l, l = 1,2,", то наилучшее (в смысле максимального уменьшения длины отрезка локализации)

размещение точек xi ,

i =

1, N

, получается разбиением их на рав-

ноотстоящие ε-пары, т.е.

2 j −1

= a +

b − a

j − ε ,

2 j

= a +

b − a

j + ε , j = 1, N 2,

(4.1)

N 2 +1

где ε − некоторое малое положительное число.

При этом

b − a

+ ε .

LN =

N 2 +1

l +1

Если N нечетное,

т.е. N = 2l +1, l = 1,2,", то наилучшим

является равномерное распределение точек, т.е.

= a +

b − a

i =

(4.2)

1, N

N +1

При этом

b − a

= 2

N +1

l +1

Нетрудно заметить, что использование нечетного числа точек при пассивном методе поиска неэффективно.

	После определения точек			xi , i =	1, N	, вычисляются значе-
ния	функции f (xi ) . Пусть		f (xk ) = min f (xi ).				Тогда, полагая
				i =1, N
x0 = a, xN +1 = b ,		определяется		итоговый		отрезок локализации
∆N	= [xk −1, xk +1] .	Точка xk	принимается			за	аппроксимацию

(оценку) точки минимума x , значение функции f (xk ) − за оцен-

ку f * = f (x*) , т.е.

x* xk , f * f (xk ).

Пример. Определить с помощью пассивного поиска ми-

нимум функции

f (x) = x + 1 ,

заданной на отрезке ∆ = [0,2]: а)

при N=6, ε=0,1; б) при N=7.

Решение.

а) N=6, ε

=0,1.

x2 j−1,

x2 j

Определяем пары точек

с помощью соотноше-

ния (4.1):

2 − 0

j − 0.1 = 0,5 j − 0,05,

x2 j−1

= 0 +

j =

1,3;

3 +1

x2 j

= 0 +

2 − 0

j +

0.1 =

0,5 j + 0,05,

j =

1,3.

3 +1

Результаты вычислений x и

f (x) заносим в табл. 4.1.

Таблица 4.1

Номер

отсчета

0,45

0,55

0,95

1,05

1,45

1,55

f (x)

2,67

2,37

2,0026

2,0024

2,14

2,20

Поскольку

f (x4 ) = min f (xi ) ,

то

полагаем

∆6=[x3, x5]=

i =1,6

=[0,95; 1,45], x x4

= 1,05,

f *

f (x4 ) = 2,0024.

Ответ: ∆6

= [0,95; 1,45] ,

x* 1,05,

f * 2,0024.

б) N=7.

Определяем xi помощью соотношения (4.2):

xi = 0 +

2 − 0

i = 0,25i,

i =

1,7.

7 +1

Результаты вычислений x и f (x) заносим в табл. 4.2. Таблица 4.2

	Номер	1			2	3		4			5	6	7
	отсчета	1			2	3		4			5	6	7
	отсчета
	x	0,25		0,5		0,75		1			1,25	1,5	1,75

	f (x)	4,25	2,50			2,08	2,00				2,05	2,17	2,32

	Поскольку				f (x4 ) = min f (xi ) ,					то полагаем ∆7=[x3, x5]=
						i =1,7
=[0,75, 1,25], x* x				4	=1,	f * f (x	4	) =	2 .
				4			4
	Ответ: ∆7		= [0,75; 1,25], x* 1,							f * 2 .

4.2. АКТИВНЫЕ МЕТОДЫ ПОИСКА МИНИМУМА

Метод оптимизации называется активным, если точки xi ,

i = 1, N, вычислений характеристик задачи (в данном случае зна-

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

лизации после j итераций будет обозначаться ∆( j) = [a( j) , b( j ) ]. Если при этом произведено i вычислений значений f(x), то

∆( j) ≡ ∆i , a( j) ≡ ai , b ( j ) ≡ bi .

На практических занятиях рассматриваются такие активные методы поиска, как метод дихотомии, метод Фибоначчи и метод золотого сечения. Для каждого из этих методов на j-й,

j =1,2,…, итерации рассматривается пара точек x1( j ) и x2( j ) , при этом x1( j ) < x2( j ). Значения функции в этих точках будут обозначаться соответственно f1( j) и f2( j) .

Метод дихотомии (половинного деления)

В данном случае общее количество вычислений f(x) четное, т.е. N = 2l, l = 1,2,", на j-м шаге (j-й итерации) произво-

дится пара вычислений x( j ) и x( j ) , отстоящих на расстоянии ε / 2
	1	2
по обе стороны от	середины текущего			отрезка локализации
[a( j −1) ,b( j −1) ]. Если	f ( j) ≤	f ( j) , то отбрасывается часть отрезка,
	1	2	f ( j) > f ( j ) , то отбрасывается
расположенная справа от		x( j ) ; если	f ( j) > f ( j ) , то отбрасывается
		2	1	2
часть отрезка, расположенная слева от x( j ) .
			1
Используются два условия окончания вычислений:
а) выполнение заданного количества вычислений N;
б) достижение заданной величины δ			уменьшения отрезка лока-
лизации.

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

1. Задаются N (либо δ) и ε, полагается j=1. 2. На j-й итерации вычисляются

x( j) = 1		(a( j −1) + b( j −1) ) − ε ,		x( j) = 1		(a( j −1) + b( j −1) ) + ε ,
1	2		2	2	2	2
	2		2		2	2
		f ( j)	= f (x( j) ),	f ( j) = f (x( j) ).
		1	1	2		2
Если	f ( j)	≤ f ( j) , то	a( j ) = a( j −1) , b( j) = x( j) .
	1	2				2
Если	f ( j)	> f ( j) , то	a( j) = x( j) ,	b( j) = b( j −1) .
	1	2	1

3. Проверяется условие окончания вычислений:

а) j=N/2 либо б) L2 j ≤ δ .

Если оно выполняется, то определяются итоговый отрезок локализации, оценки точки минимума x и величины минимума

f * = f (x*) , и вычисления завершаются.

Если условие не выполняется, то полагается j = j +1 и

осуществляется переход к п.2.

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

Пример. Определить методом дихотомии минимум функции f (x) = x4 − 6x2 +10 , заданной на отрезке ∆=[1,3], при N=8,

ε=0,1.

Решение.

В данном случае будут выполнены N/2=4 итерации. Результаты вычислений заносим в табл. 4.3.

Таблица 4.3

Номер	x1( j )	x2( j )	f1( j)	≤	f2( j)	a( j)	b( j)
итерации				>
0	—	—	—		—	1	3
1	1,95	2,05	1,644	<	2,446	1	2,05
2	1,475	1,575	1,680	>	1,270	1,475	2,05
3	1,713	1,813	1,004	<	1,082	1,475	1,813
4	1,594	1,694	1,211	>	1,017	1,594	1,813

Поскольку j=N/2=4, то вычисления завершаются.

Точка минимума локализована на отрезке ∆8 = [1,594; 1,813] . На данном отрезке исследованы 4 точки:

a(4)	= 1,594 → f (a(4) ) = 1, 211;
b(4)	= 1,813 → f (b(4) ) = 1,082;
b(4)	= 1,813 → f (b(4) ) = 1,082;		*	(3)	= 1,713, f	*	(3)	) = 1,004.
x2(4)			x	x1	= 1,713, f		f (x1	) = 1,004.
x2(4)	=1,694 → f (x2(4) ) =1,017;
x(3)	=1,713	→ f (x(3) ) =1,004;
1		1
Ответ: ∆8		= [1,594; 1,813] , x* 1,713,			f * 1,004 .

<<< < Предыдущая 1 2 34 / 144 5 6 7 8 9 10 11 12 13 14 > Следующая >>>

Соседние файлы в предмете Экономика