методичкаМОСС

																								Таблица 11
						Значения r j									Значения x j
L				Номер направления связи j									Номер направления											M
																связи j
		1		2		3		4		5		1			2		3			4		5
1		0,0200		0,0300		0,0600		0,0200				0			0		0			0		1		0,1500
2		0,0200		0,0300		0,0600		0,0200				0			0		0			0		2		0,2250
3		0,0200		0,0300				0,0200		0,0375		0			0		1			0		2		0,2850
4		0,0200		0,0300				0,0200		0,0375		0			0		2			0		2		0,3270
5		0,0200		0,0300		0,0294		0,0200				0			0		2			0		3		0,3645
6		0,0200				0,0294		0,0200		0,0188		0			1		2			0		3		0,3945
7		0,0200		0,0270				0,0200		0,0188		0			1		3			0		3		0,4239
8		0,0200				0,0206		0,0200		0,0188		0			2		3			0		3		0,4509
9		0,0200				0,0206		0,0200		0,0188		0			3		3			0		3		0,4752
10		0,0200				0,0206		0,0200		0,0188		0			4		3			0		3		0,4971
11		0,0200		0,0197				0,0200		0,0188		0			4		4			0		3		0,5177
12				0,0197		0,0144		0,0200		0,0188		1			4		4			0		3		0,5377
13		0,0160		0,0197		0,0144				0,0188		1			4		4			1		3		0,5577
14		0,0160				0,0144		0,0160		0,0188		1			5		4			1		3		0,5774

В табл.11 прямоугольниками обведены значения приращений функции эффективности r j, выбираемые на последовательных этапах распределения. На первом шаге выбор максимального приращения ведется в первой строке значений r j. Видно, что это – r5 (т.е. s=5). Следовательно, канал связи должен быть выделен на пятое направление. В соответствии с этим значение r5 обводится прямоугольником, пересчитывается, сносится,

наряду с остальными значениями , во вторую строку, и поиск очередного максимального приращения ведется во второй строке. Далее процесс повторяется. В табл.11 показано 14 таких шагов. Анализ окончания процесса ведется либо по первому столбцу таблицы (в прямой задаче) сравнением величин L и N, либо по последнему ее столбцу (в обратной задаче) сравнением величин M и M0. Необходимо отметить два важных обстоятельства:

- фактически при использовании ММЭ получается не одно, а совокупность оптимальных решений. Для прямой задачи, в частности, в табл. 11 содержится оптимальное решение не только для N = 14, но и для любого N, меньшего 14, т.е. для всех N ;

31

- процесс оптимального распределения может быть и прерван, и продолжен в любой момент, т.е. ММЭ в классификации работы [2] может быть отнесен к последовательным методам оптимизации, как, например, и метод золотого сечения.

Более сложной, чем (2.31)–(2.33), является обратная задача, в которой при сохранении условий (2.32) и (2.33) изменяется вид целевой функции, она представляет собой не суммарный расход каналов, а их суммарную стоимость:

.

(2.39)

Здесь s j – (удельная) стоимость создания и эксплуатации (либо стоимость аренды) одного канала на j-м направлении связи. По алгоритму 5 оптимальное целочисленное решение

можно получить здесь только по отношению к величинам yj = sj xj. Значения же в общем случае неизбежно будут нецелочисленными и проблема округления решения x = {xj} остается.

Решение задачи (39), (32), (33) основывается на использовании ОТМП и может быть получено по алгоритму 6.

Алгоритм 6 (решения обратной задачи распределения каналов по направлениям связи по критерию стоимости системы)

1. Ввести ИД: скаляры n (целое) и M0 (вещественное положительное) и векторы {v j }, {w j

} и {s j } .

2. Вычислить величины

	и
,	(2.40)

где

.

(2.41)

3. Проверить выполнение условия M0 > M0n. Если условие выполняется, перейти к п.4, если нет – к п.5.

32

4. Вычислить значение

,

(2.42)

компоненты оптимального решения

(2.43)

и перейти к п.10.

5. Построить вариационный ряд

z = (z1 z2

...

zn)

(2.44)

и перенумеровать направления связи в соответствии с расположением величин z j в этом ряду. Упорядоченные в соответствии с (2.44) значения z j хранятся в массиве {j}, значения s j – в массиве , значения A j – в массиве {b j}, значения {v j} – в массиве {c j}, старые номера величин j – в массиве {f j}.

6. Вычислить значения

и

(2.45)

для всех направлений связи .

7. Найти значение k из условия

M0k < M0 M0,k+1, k [1, n - 1].

(2.46)

8. Найти значение множителя Лагранжа

(2.47)

и компоненты оптимального решения

33

(2.48) 9. Перейти к прежней нумерации направлений связи, т.е. от вектора {y j} к вектору {x j} по

правилу
.	(2.49)
10. Округлить решение {x j} до целых величин в большую сторону

(2.50)

11. Print

.

12. End.

Пример 2.4. Исходные данные и результаты расчетов при M0=0,5 приведены в табл.12.

34

Таблица 12

	Пункт(ы)						Номер направления связи j
	алгоритма	Параметр
6			1	2	3	4		5	6	7	8	9	10
		v j	0,12	0,06	0,06	0,05		0,09	0,20	0,12	0,07	0,08	0,15
	1	w j	0,63	0,15	0,20	0,99		0,86	0,39	0,56	0,71	0,24	0,41
		s j	3,8	2,0	1,7	4,7		4,2	2,4	3,2	3,9	3,0	3,1
		A j	1,006	6,153	4,481	0,217		0,509	2,023	1,218	0,808	3,644	1,895
2
		z j	31,857	205,100	126,962	20,398		23,753	24,276	32,480	45,017	136,650	39,163
		j	20,398	23,753	24,276	31,857		32,840	39,163	45,017	126,962	136,650	205,100
		f j	4	5	6	1		7	10	8	3	9	2
5
		a j	4,7	4,2	2,4	3,8		3,2	3,1	3,9	1,7	3,0	2,0
		b j	0,217	0,509	2,023	1,006		1,218	1,895	0,808	4,481	3,644	6,153
		c j	0,05	0,09	0,20	0,12		0,12	0,15	0,07	0,06	0,08	0,06
6		M 0 j	0	0,007	0,010	0,088		0,101	0,178	0,250	0,605	0,623	0,729
8		y j	0,303	0,634	2,475	0,958		1,122	1,413	0,490	0	0	0
	9–10		1	0	0	1		1	3	2	1	0	2
							35

Видно, что заданное значение M0 =0,5 располагается между M0 7 и M0 8, т.е. k=7, три последних направления связи (3-е, 9-е и 2-е) не используются, поэтому соответствующие значения y j равны нулю.

2.3. Распределение разнотипных каналов по направлениям связи

Оптимизационная задача в данном случае формулируется следующим образом:

,

(2.51)

	(2.52)
x 0.	(2.53)

Здесь M(x) – математическое ожидание числа надежно функционирующих направлений связи;

m – количество типов каналов (i – номер типа канала);

N i – заданное количество каналов i-го типа;

ij = - ln(1 - w ij);

w ij – надежность одного канала i-го типа, используемого на j -м направлении;

x ij – количество каналов i-го типа, выделяемых на j -е направление.

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

Приближенное целочисленное решение задачи (2.51)–(2.53) можно получить по алгоритму 7, в котором используется ММЭ.

Алгоритм 7 (приближенного целочисленного распределения разнотипных каналов по направлениям связи с использованием ММЭ)

1. Ввести ИД: скаляры n и m, векторы {N i}, и , матрицу {w ij},

.

36

2.Вычислить матрицу значений приращений эффективности , и

обнулить массив x ij: = 0 для всех i и j и ячейку M: = 0, где будет накапливаться значение суммарной эффективности.

3.Найти максимальное приращение эффективности

	(2.54)
и зафиксировать номера соответствующих типа канала s и направления связи l.
4. Выполнить присвоения
Ns: = Ns- 1, M : = M + r sl и x sl : = x sl + 1	(2.55)
и пересчитать значения приращений эффективности на l–м направлении связи:
.	(2.56)

5.Проверить выполнение условия Ns > 0. Если условие выполняется, то перейти к п.3, если нет – то к п.6.

6.Обнулить значения приращений эффективности в s-й строке матрицы приращений

эффективности, поскольку распределены все каналы s-го типа: .

7.Проверить выполнение условия . Если условие выполняется, то перейти к п.3, если нет – то к п.8.

8.Print ({x ij}, M).

9.End.

Пример 2.5. Исходные данные приведены в табл.13, результаты нескольких шагов решения приведены в табл.14.

						Таблица 13
				Номер направления связи j
	Количество	Номер типа
	каналов i-		1	2	3	4
		канала i
	го типа N i
				Значения w ij
	6	1	0,564	0,287	0,486	0,461
	3	2	0,295	0,363	0,284	0,321
	5	3	0,271	0,237	0,101	0,452
	Значение v j		0,2	0,1	0,3	0,4

37

			Приращения эффективности r ij					Распределение каналов по				Кол-во
												каналов
	Номер							направлениям связи x ij
												после
Номер шага	типа
												L-го
распределения	канала
				Номер направления связи j				Номер направления связи j				шага
	i
												распр. N
		1		2	3		4	1	2	3	4
												i
	1	0,1128		0,0287	0,1458			0	0	0	1	5
1	2	0,0590		0,0363	0,0852		0,1284	0	0	0	0	3
	3	0,0542		0,0237	0,0303		0,1808	0	0	0	0	5
	1	0,1128		0,0287			0,0994	0	0	1	1	4
2	2	0,0590		0,0363	0,0852		0,0692	0	0	0	0	3
	3	0,0542		0,0237	0,0303		0,0975	0	0	0	0	5
	1	0,0492		0,0287	0,0385			1	0	2	3	0
6	2	0,0257		0,0363	0,0225		0,0373	0	0	0	0	3
	3	0,0236		0,0237	0,0080		0,0525	0	0	0	0	5
	1	0		0	0		0	1	0	2	3	0
7	2	0,0257			0,0225		0,0201	0	1	0	0	2
	3	0,0236		0,0237	0,0080		0,0283	0	0	0	0	5
	1	0		0	0		0	1	0	2	3	0
11	2	0		0	0		0	1	2	0	0	0
	3			0,0096	0,0080		0,0155	1	0	0	1	3
	1	0		0	0		0	1	0	2	3	0
14	2	0		0	0		0	1	2	0	0	0
	3	0,0089			0,0080		0,0085	2	1	0	2	0

Таблица 14

Суммарная

эффективность после L-го шага распр. M

0,1844

0,3302

0,6709

0,7072

0,8010

0,8382

38

Контрольное задание

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

																														Таблица 15
	Предпоследняя									Номер
	цифра номера																Тип задачи							Характер решения
										алгоритма
	зачетной книжки
	0 или 1										3						прямая						оpt нецелочисленное
	2 или 3										4						прямая							оpt целочисленное
	4 или 5										5						прямая							оpt целочисленное
	6 или 7										5						обратная							оpt целочисленное
		8									6						обратная						приближенное целочисленное
		9									7						прямая						приближенное целочисленное
																														Таблица 16
	Номер																Номер направления связи j
			Параметр
	алгоритма
								1				2					3		4			5				6				7		8
	3 и 4		v j					0,231				0,176					0,115		0,333			0,145
			w j					0,140				0,065					0,373		0,099			0,547
	5		v j					0,100				0,140					0,125		0,236			0,060				0,240			0,021			0,078
			w j					0,305				0,276					0,130		0,318			0,556				0,121			0,754			0,874
			v j					0,091				0,236					0,028		0,063			0,159				0,230			0,193
	6		w j					0,619				0,947					0,382		0,676			0,990				0,474			0,355
			s j					1,08				6,94					1,90		2,01			5,47				1,15			3,77
			Номер
			типа											Значения wij
			канала
	7					1		0,311						0,262			0,192		0,220
			i			2		0,112						0,173			0,282		0,093
						3		0,074						0,308			0,237		0,111
			v j					0,191						0,280			0,310		0,219

39

Таблица 17

Последняя цифра номера зачетной книжки

Предпоследняя

цифра номера Параметр зачетной

книжки

			0		1		2		3		4		5		6		7		8		9
0		N		1		3		5		7		9		11		13		15		17		19
1		N		2		4		6		8		10		12		14		16		18		20
2		N		1		4		7		10		13		16		19		22		25		28
3		N		2		5		8		11		14		17		20		23		26		29
4		N		5		7		9		11		13		15		17		19		21		23
5		N		4		6		8		10		12		14		16		18		20		22
6		M 0		0,10		0,15		0,20		0,25		0,30		0,35		0,40		0,45		0,50		0,55
7		M 0		0,13		0,18		0,23		0,28		0,33		0,38		0,43		0,48		0,53		0,58
8		M 0		0,250		0,300		0,350		0,400		0,450		0,500		0,550		0,600		0,650		0,700
		N1		1		2		4		5		2		3		4		1		1		2
9		N2		2		4		1		2		5		2		3		3		4		1
		N3		4		1		2		3		3		5		1		4		3		3

Литература

1.Клейнрок Л. Вычислительные системы с очередями: Пер. с англ. – М.: Мир, 1979.

2.Гурин Л.С., Дымарский Я.С., Меркулов А.Д. Задачи и методы оптимального распределения ресурсов. – М.: Сов. радио, 1968.

3.Берлин А.Н., Лазарева И.Л., Рябошапка А.П. Методы и алгоритмы оптимизации в коммутационной технике: Методические указания к лабораторным работам / СПбГУТ. – СПб, 1997.

4.Корн Г. и Корн Т. Справочник по математике для научных работников и инженеров. – М.: Наука, 1974.

40