Добавил:

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

Вуз:

Пермский национальный исследовательский политехнический университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

книги / Решение некоторых многоэкстремальных задач методом сужающихся окрестностей

..pdf

Скачиваний:

Добавлен:

12.11.2023

Размер:

12.71 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 6 7 89 / 219 10 11 12 13 14 15 16 17 18 19 20 21 > Следующая >>>

с	FREQ(X)	0.5 + 0.5*ERF(X/C)		0.5ERFC(A/C) i-0.6ERFC(X)
с	*********************************************************************
С
С	DIMENSION P I(4), Ql(4), P2(8), Q2(8), P3(5), Q3(5)
1	DATA P I/2.42667		95523 0532 E2,
1		2.19792	61618 2942 El,

26.99638 34886 1914 EO,

3—3.56098 43701 8154 E—2/

DATA Q1/2.15058		87586 9861 E2,
1	9.11649	05404 5149 El,	.
2	1.50827	97630 4078 E l,	.
3	1.00000 000000 000 Е0/
DATA	P2/3.00459	26102 0162 E2,
1	4.31918	95371 1873 E2,

23.39320 81673 4344 E2,

31.52989 28504 6940 E2,

44.31622 27222 0567 El,

57.21175 82508 8309 E0,

65.64195 51747 8974 E—1,

7—1.36864 85738 2717 E—7/

1	DATA Q2/3.00459	26095 6983 E2,
1	7.90950	92532 7898 E2,

29.31354 09485 0610 E2,

36.38980 26446 5631 E2,

42.77585 44474 3988 E2,

57.70001 52935 2295 El,

61.27827 27319 6294 El,

71.00000 00000 0000 Е0/ DATA P3/—2.99610 70770 3542 E—3,

1		—4.94730 91062 3251			E—2,
2		—2.96956 59353 9687			E—1,
3		—2.78661		30860 9648 E—1,
4		—2.23192		45973 4185 E—2/
1	DATA Q3/1.06209		23052 8468 E—2,
1		1.91308	92610 7830 E—1,
2		1.05167	51070 6793 E0,		'
3		1.98733	20181 7135 E0,
4		1.00000 00000 0000 Е0/
	DATA CONST 1/0.70710 67811 86548/
С	(CONST1 = SQRT(l/2))
	DATA CONST2/0.56418 95835 47756/
n	(CONST2 = SQRT(1/PI))
o o	**********************************************************#*m
n	ENTRY POINTS. SET IENTRY (=lFO R ER F,= 2 FOR ERFC,» 3 FOR
n o	ENTRY POINTS. SET IENTRY (=lFO R ER F,= 2 FOR ERFC,» 3 FOR
n o	FREQ).
n	ENTRY ERF
	ENTRY ERF
	IENTRY = 1
	T =	X
	A *	ABS(T)
	IF(A.LE.6.0) GO TO 11
	ERFXX — SIGN(l.O.X)
	RETURN
	ENTRY ERFC
	IENTRY = 2
	T =	X

6 9—961

IF(T.GE.— 6.0) GO TO 10

ERFXX = 2.0

RETURN

ENTRY FREQ

IENTRY = 3

T = CONST 1*X

IF(T.LE.6.0) GO TO 10

ERFXX = 1.0

RETURN

SELECT BASIC FUNCTION. SET IBASIC (= 1 FOR ERF, = 2 FOR ERFC).

10A = ABS(T)

11S = T**2

IF(A.GT.0.47) GO TO 20

n n o

IBASIC =	1. SET Y = ERF(T)
IBASIC =	1
Y = T(P1(1) + S(P1(2) + S(P1(3) + SP1(4))))
1 /(Ql (1) +	S(Q1(2) + S(Q1(3) + S*Q1(4))))
GO TO 30

ООО

IBASIC = 2 .'SET Y = ERFC(A).

20IBASIC = 2 IF(A.GT.4.0) GO TO 21

Y =	EXP(—S)*(P2(1) +		A*(P2(2) +	A(P2(3) + A(P2(4) +	A*(P2(5) +
1	A	*(P2(6) +	A*(P2(7) +	A*P2(8))))))))	A*(Q2(5) +
2	A	/ (Q2(l ) +	A*(Q2(2) +	A(Q2(3) + A(Q2(4) +	A*(Q2(5) +
3	A	*(Q2(6) +	A*(Q2(7) +	A*Q2(8))))))))

GOTO 30

21Y = 0.0

IF(A.GT.26.0) GO TO 30 R = l.O/A

	U =	R**2		\
	Y =	REXP(—S)(CONST2 +		U(P3(3) + U(P3(4) +	U*P3(5) ))))
	1	U*(P3(1) +	U*(P3(2) +	U(P3(3) + U(P3(4) +	U*P3(5) ))))
C	2	/(Q3(l) +	U*(Q3(2) +	U(Q3(3) + U (Q3(4) +	U*Q3(5))))))
C	EXPRESS FINAL RESULT IN TERMS OF Y.

30IF(IENTRY.NE.l) GO TO 40 IF(IBASIC.EQ.2) GO TO 31 ERFXX = Y

RETURN

31ERFXX = 1.0.— Y

IF(X.LT.O.O) ERFXX = -E R F X X

RETURN

40IF(IENTRY.NE.2) GO TO 50 IF(IBASIC.EQ.2) GO TO 41 ERFXX = 1.0 — Y RETURN

41ERFXX = Y

IF(X.LT.O.O) ERFXX = 2.0 — Y RETURN

50R = 0.5*Y

IF(IBASIC. EQ.2) GO TO 51 ERFXX = 0 .5 + R

RETURN

Б1 ERFXX = 1.0. —R IF(X.LT.O.O) ERFXX «• R RETURN

END

По этой программе вычисляется значение функций ERF (и) и FREQ

(и). Для получения значений Е (и) достаточно одного из следующих соотношений:

£ ( M) = 4 11 +	ERFW1*
или
Е (и) — FREQ (У Т и).
Из формул (3.9) и (ЗЛО) следует
Р	(3.11)

Как известно,^ математическое ожидание случайной величины г, распределенной по закону (3.2), равно т. Вычислим математи ческое ожидание М случайной величины у, распределенной по за

кону	(3.5):
м	_	да =	О) = y ^ s	r I	[ - ( - ^ п г ) ’] dx. (3.12)
В интеграле, стоящем			в правой	части равенства (3.12), проведем
замену		переменной

	и =		х — т	*
Тогда			V 2 а	*
Тогда	dx
du =	dx	,	х = Y 2 аи + т.
du =	V J а	,	х = Y 2 аи + т.
Из соотношений (3.12) — (3.14)			получаем
	вВ
М = y t j J			аи + tn)exp(— u?)du,
где	I
где	а — т			b — т
	а — т		В =	b — т
	V Ь		’ ~	у Т с

Производя замену переменной интегрирования, находим

У и pyp (— ц») Л, - _«Р ( - Л2) - ехр ( - б2)

(3.13)

(3.14)

(3.15)

(3.16)

(3л7>

Из соотношений (3.15) и (3.17) с учетом формулы (3.10) следует

М = -р [Е (В) — Е (Л)] + — ?_ - (ехр (— Л2) — ехр (— 5 2)].

6*	ва

Учитывая формулу (3.11), находим окончательно

М = т + / 2 я	ехр (— Л2) — ехр (->■‘-6*)'		(3.18)
	Щв^ Щ	аГ

Из определения (3.10) следует, что функция Е (и) является моно тонно возрастающей (рис. 19). Поэтому знак разности М — т сов

падает со знаком величины

ехр (— А2) — ехр (— В2).
Для того чтобы выполнялось неравенство
М < т,
необходимо и достаточно, чтобы
ехр (— А2) < ехр (— В2),
или	(3.19)
\| Л \| > \| В \| .	(3.19)

Если учесть соотношение (3.16), то неравенство (3.19) эквивалентно следующему:

|а — т\ > \Ь — т\.

В свою очередь неравенство (3.20) сводится к венств

| т < а ,

1 а — т > b— т, | а < т < Ь , \т — а > Ь — т, (т >Ь,

\т — а > т — Ь.

(3.20)

системам нера

(3.21)

(3.22)

(3.23)

Вследствие очевидного требования	а < b	система	(3.21) не
имеет решений. Решение системы (3.22) имеет вид
т >	,		(3.24)
а решение системы (3.23)
яJ ;> Ь.			(3.25)
Очевидно, что неравенство (3.24) следует из		неравенства (3.25).
Поэтому неравенства (3.19) и (3.24) эквивалентны.
Окончательный вывод можно сформулировать в виде теоремы.
Теорема 3.1. Для того чтобы~	математическое		ожидание

М закона F*(z), заданного соотношением (3.5), было меньше, чем математическое ожидание т закона F (г), заданного соотношением (3.2), необходимо, чтобы выполнялось неравенство (3.24).

Таким образом, если значения функционала на перестановках, взятых из множества П, распределены по нормальному закону, то математическое ожидание значений функционала на перестанов ках из Ilv будет меньше, чем математическое ожидание всех значе ний, если

aV"Ь <т. 2~~

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

Пусть основной закон распределения имеет вид

Ф(г) = т к 1^	е1р\|- \| '"V , гн*-	^
■п		г < х\.
О	,	г < х\.

Усечение этого закона на интервал (а, Ь) (предполагается, что

а >• т])	имеет	вид
	10	,	г <	а,
Ф* (г) =	'	г
Ф* (г) =	'
		,	Z >	b.
				(3.26)

Здесь R — это вероятность того, что случайная величина, распределенная по закону Ф (г), попадает на интервал (а,Ь). Вычис лим величину R. По определению

/2 я <

Проведем замену переменной интегрирования

			JnjA t-J - p				(3.27)
			V i s				(3.27)
Тогда			V i s
Тогда
			ln(&—Т\|>—М>
		1	VTs
		1	J	exp (— и2)du,
		VTT	J	exp (— и2)du,
		VTT	ln(g—П)—д
			ln(g—П)—д
или вследствие	(3.10)		VTs
или вследствие	(3.10)
* -	г [		] —	g [	~	r ] •	(3-28)
Найдем математическое ожидание l случайной						величины,	рас
пределенной по	закону (3.3):
—оо		п
Воспользовавшись		подстановкой (3.27),			определим
		оо
t = -X=		J [n + ехр (]/2~ su -f р)] ехр (— и2) du.
У И — оо

Выделяя полный квадрат в выражении под знаком экспоненты, находим

1	©о		оо
1	Ч J ехр (— и2) du +	ехр ^	+ p j $ ехр J— (ы—
Уп	Ч J ехр (— и2) du +	ехр ^	+ p j $ ехр J— (ы—
Уп
			(3.29)

Для подсчета этого интеграла можно воспользоваться известным еоотношением

W j >exp(“ ^ "	L
Получим
/ = Г ) + exp^-f	(3.30)

Вычислим математическое ожидание L величины, распределен ной по закону (3.26):

— оо

(3.31)

В правой части (3.31) проведем замену переменной интегрирования по формуле (3.27). Получим

	н
L =	1 [тЦехр (У Т sy + ц)] ехр (— у2) dy,

где введены обозначения

in (а — л) — и	. j y	In (ft — п ) — и	(3.32)
V I s	’	У 1 8

По аналогии о (3.29) находим

L = v h {ч1ехр1(- Л* +ехр(■*+ т)	[- (» - тгЛ У
С учетом формулы (3.10) отсюда следует
L = {л [Е (Я) - Е (О)] + ехр (\|* + 4	) [е (н ~ j f ) -

~ E{G~w)]}'

Воспользовавшись соотношением (3.28), получим

L = я +	/		Е ( и ~ w ) ~ B ( ° ~ w )
L = я +	ехр (t1 +	2 )		E{H) —E(G)	'	(3 -3 3 *
или с учетом формулы (3.32),
	Л	1п ( 6 — л) — [A — S* 1 __ F In (а — л) — \\ — sa 1
	* 1		/ Г .	с	V 2 s	J
L = rH -exp	* 1		/ Г .	]	V 2 s	J
L = rH -exp		- Г I n (6 — л) — И 1 __ F			In (а — л) — Ц 1
		- Г I n (6 — л) — И 1 __ F			In (а — л) — Ц 1
		е [	У 1 .	--- Li	V 2 s	\
		е [	У 1 .	]	V 2 s	\
						(3.34)
Из формул (3.30) и (3.33) следует, что неравенство
			L < 1			(3.35)
эквивалентно	следующему:

£{н- w ) - е (°-- тт)<Е[m - Е'

аэто неравенство, в свою очередь, эквивалентно такому:

н— s	н
VJ	н
j	e-‘‘dt < j er-‘'dt.

о— VJ

На рис. 20 показан вид функции ехр (— t2). Нетрудно видеть, что при Я < 0 сдвиг интервала (G, Я) влево приводит к уменьшению

интеграла по этогёу интервалу. В самом деле, точке t из интервала

(G, Н) соответствует точка t ---- = t	из интервала	(G-	S
			/ 2

Н -----3 ПРИ ^ ^ ® из неравенства tx <	t имеемexp (— t\) <

< exp (— t2).

Следовательно, для того чтобы выполнялось неравенство (3.35), достаточно выполнении неравенства G < 0, или с учетом формулы

(3.32) неравенства	(3.36)
Ь< т] + ^ .

Таким образом, доказано следующее предположение.

Теорема 3.2. Для того чтобы математическое ожидание L слу чайной величины, распределенной по закону (3.26), было меньше, чем среднее значение I величины, имеющей закон распределения (3.3), достаточноу чтобы выполнялось неравенство (3.36).

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

чение функционала на перестановках из множества n vбудет меньше,

чем математическое ожидание	всех значений функционала,		при
bv <	т] +	е*.	(3.37)
Приведем численные примеры,		иллюстрирующие сдвиг матема

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

В качестве модельного выберем функционал

8(Р) =	2 M t C O S (p * f. +	£ Mi sin cpkj	(3.38)
	1=1	,i= 1

в котором p = (kv &2,..., Ю — произвольная перестановка из n символов, а величины ф* определяются так:

2nk

Положим п = 84, а числа ^зададим в соответствии с табл. 3.1,

Рассмотрим выборку в N — 1000 значений функционала g (р), где р — произвольные перестановки из пространства П. Матема тическое ожидание значений g (р) равно 240,57, а соответствующая гистограмма изображена на рис. 21. Наименьшее значение функ ционала (3.38) при этом равно 12, 96, а наибольшее— 781, 74.

Выберем перестановку				р0, на	которой функционал g(p)				принимает
								Т а б л и ц а		3.1
	i	0	2	3	4	5	6	- 7	8	9
	M i	0	2	22	11	20	26	58	14	33
	i	10	11	12	13	14	15	16	17	18
	M t	43	40	2	0	12	73	0	8	—6
	i	19	20	21	22	23	24	25	26	27
	M i	34	—26	8	42	9	8	46	46	34
	i	28	29	30	31	32	33	34	35	36
	M i	29	25	47	—20	90	41	26	—5	21
	i	37	38	39	40	41	42	43	44	45
	M i	53	33	13	10	—32	0	30	56	13
	i	46	47	48	49	50	51	52	53	54
	M i	46	16	— 18	— 15	40	29	—18	- 5 6	—41
	i	55	56	57	58	59	60	61	62	63
\	M t	9	4	— 10	30	—17	12	—40	9	40
\	i	64	65	66	67	68	69	70	71	72
!	M i	17	—36	2	—2	—26	0	—20	10	10
	i	73	74	75	76	77	78	79	80	81
	M i	28	48	—3	—10	—77	—42	0	2	0
	i	82	83	84
	M i	14	—6	—40

шименынее из всех просмотренных значений: (30, 33, 42, 71, 27,


28,		14,	17,		12,			43,			72,		55,		73,		79,		8,	15,		23,	7,	77,		13,	46,		63,	76,		66,
I,	24,		10,	69,			64,			84,		52, 22,				80,		57,		31,		40,	49,		39,	45,		59,	54,		70,	2,
>9, 34,			9,	37,		32,			44,			58,		21,		3,	65, 26,				74, 5,		75,		68,	18, 60,			50,		36, 41,
51, 56,			19,		25,			48,			62,		16,		51,		83,		11,		35,	47,	4,		67,	53,20,81,				78,		38,
52,		6).			рассмотрим								выборки					в	1000			значений функционала g										(р)
		Далее

при условии, что перестановки р выбираются из шара радиуса зять в центре с перестановкой р0. Если расстояние определяется транспозиционной метрикой, то гистограмма имеет вид, показанный на рис. 22 с математическим ожиданием 108,43. Гистограмма для инверсной метрики представлена на рис. 23. Среднее значение

<<< < Предыдущая 1 2 3 4 5 6 7 89 / 219 10 11 12 13 14 15 16 17 18 19 20 21 > Следующая >>>

Соседние файлы в папке книги