Оптимизация программы "диспетчер-кодировщик"

(мс)

 

2) Составим начальный  опорный план метода минимальной стоимости.

1. Находим ячейку таблицы с  наименьшей стоимостью.

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

3. Повторяем шаг №1 и шаг  №2, до тех пор пока все запасы ресурсов не закончатся.

 

	14		27		10		23		6	3
			0						3
	7		15		28		11		19	16
	11		0				5
	20		8		16		24		12	9
			9
	13		21		4		17		25	22
			15		7
	26		9		22		5		18	15
							15
11		24		7		20		3		65

(мс)

3) Составим  начальный опорный план метода аппроксимации Фогеля:

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

2. Находим строку (или столбец) имеющую максимальный штраф. Если будут альтернативные  максимумы – выбираем любой.

3. Ищем в строке (или столбце)  ячейку с наименьшей стоимостью {a_i ;b_j}.

4. Заполняем по максимуму ячейку  ресурсом. И «вычеркиваем» строку (или столбец), в которой закончился запас ресурсов.

5. Затем заново рассчитываем штрафы, не учитывая строки (или столбцы) закончившимся ресурсом и т.д.

	14		27		10		23		6	3	4	8	–	–	–	–	–	–	–
									3
	7		15		28		11		19	16	4	4	4	4	4	4	–	–	–
	11						5
	20		8		16		24		12	9	4	4	4	4	16	–	–	–	–
			9						0
	13		21		4		17		25	22	9	4	4	4	4	4	4	9	21
			15		7
	26		9		22		5		18	15	4	4	4	4	4	4	4	4	–
			0				15
11		24		7		20		3		65
6		1		6		6		6
6		1		–		6		6
6		1		–		6		6
–		1		–		6		6
–		1		–		6		–
–		6		–		6		–
–		12		–		12		–
–		12		–		–		–
–		21		–		–		–

 

 

Решение:

Итерация 1:      Итерация 2:

строка1: 10-6=4 столбец1: 13-7=6  строка1: 14-6=8 столбец1: 13-7=6

строка2: 11-7=4 столбец2: 9-8=1  строка2: 11-7=4 столбец2: 9-8=1

строка3: 12-8=4 столбец3: 10-4=6  строка3: 12-8=4 столбец3: –

строка4: 13-4=9 столбец4: 11-5=6  строка4: 17-13=4 столбец4: 11-5=6

строка5:  9-5=4 столбец5: 12-6=6  строка5:  9-5=4 столбец5: 12-6=6

a₄b₃=7       a₁b₅=3

 

Итерация 3:      Итерация 4:

строка1: –  столбец1: 13-7=6  строка1: –  столбец1: –

строка2: 11-7=4 столбец2: 9-8=1  строка2: 15-11=4 столбец2: 9-8=1

строка3: 12-8=4 столбец3: –   строка3: 12-8=4 столбец3: –

строка4: 17-13=4 столбец4: 11-5=6  строка4: 21-17=4 столбец4: 11-5=6

строка5:  9-5=4 столбец5: 18-12=6  строка5:  9-5=4 столбец5: 18-12=6

a₂b₁=11      a₃b₅=0

 

Итерация 5:      Итерация 6:

строка1: –  столбец1: –   строка1: –  столбец1: –

строка2: 15-11=4 столбец2: 9-8=1  строка2: 15-11=4 столбец2: 15-9=6

строка3: 24-8=16 столбец3: –   строка3: –  столбец3: –

строка4: 21-17=4 столбец4: 11-5=6  строка4: 21-17=4 столбец4: 11-5=6

строка5:  9-5=4 столбец5: –   строка5:  9-5=4 столбец5: –

a₃b₂=9       a₂b₄=5

 

Итерация 7:      Итерация 8:

строка1: –  столбец1: –   строка1: –  столбец1: –

строка2: –  столбец2: 21-9=12  строка2: –  столбец2: 21-9=12

строка3: –  столбец3: –   строка3: –  столбец3: –

строка4: 21-17=4 столбец4: 17-5=12  строка4: 21-17=4 столбец4: –

строка5:  9-5=4 столбец5: –   строка5:  9  столбец5: –

a₅b₄=15      a₅b₂=0 

 

Итерация 9:

строка1: –  столбец1: –

строка2: –  столбец2: 21

строка3: –  столбец3: –

строка4: 21  столбец4: –

строка5:  –  столбец5: –

a₄b₂=15

 

(мс)

 

По методу минимальной стоимости и по методу апроксимации Фогеля получили минимальное значение (мс)

. Для проверки на оптимальность выберем решение, полученное с помощью метода апроксимации Фогеля. Для этого воспользуемся одним из методов последовательного улучшения опорного плана вплоть до получения оптимального.

 

Воспользуемся методом потенциалов. Для этого:

1.Составляем и решаем систему уравнений U_i +V_j = C_ij, где i и j номера тех строк и столбцов, в которых стоят нагруженные опорным планом клетки. Количество уравнений=n+m-1; потенциалов=n+m. Один из них положим равным нулю (U₁=0).

V_j - потенциал j-го потребителя,

U_i - потенциал i-го отправителя.

V1=-6		V2=2			V3=-15			V4=-2			V5=6
U1=0			14			27			10			23			6		3
															3
U2=13			7			15			28			11			19		16
			11									5
U3=6			20			8			16			24			12		9
						9									0
U4=19			13			21			4			17			25		22
						15			7
U5=7			26			9			22			5			18		15
						0						15
11		24			7			20			3			65

 

Получим:

U₁+V₅=6   V₅=6 U₃+V₅=12  U₃=6 U₃+V₂=8  V₂=2 

U₄+V₂=21  U₄=19 U₄+V₃=4  V₃=-15 U₅+V₂=9  U₅=7 

U₅+V₄=5  V₄=-2 U₂+V₄=11  U₂=13 U₂+V₁=7  V₁=-6

2.Определим значения d_ij по формуле d_ij=U_i+V_j-С_ij (i и j для ненагруженных клеток).

Получим: 

   

    

    

    

   

Так как  d_ij 0, то полученный опорный план является оптимальным и дальнейшее улучшение плана не требуется.

 

Следовательно, пересылка пачек информации занимает 640 миллисекунд, и распределена следующим образом:

Пересылка информации из модуля А1 в  модуль В5 объемом 3 байта за время  мс.

Пересылка информации из модуля А2 в  модуль В1 объемом 11 байт за время  мс.

Пересылка информации из модуля А2 в модуль В4 объемом 5 байт за время мс.

Пересылка информации из модуля А3 в модуль В2 объемом 9 байт за время мс.

Пересылка информации из модуля А4 в модуль В2 объемом 15 байт за время мс.

Пересылка информации из модуля А4 в модуль В3 объемом 7 байт за время мс.

Пересылка информации из модуля А5 в модуль В4 объемом 15 байт за время мс.

 

Определение характера  и интенсивности информационного потока, поступающего на вход блока запросов.

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

 

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

,

где k – число последовательных сигналов,

      u/Y – отношение времени, в течение которого первый сигнал ожидает последнего, к длине отрезка времени, в течение которого появляются сигналы.

 

u/Y = 0,933

k = 10

 

Тогда:         

 

2) Определим характер и интенсивность потока запросов, поступающих на вход БВЗ.

В результате просеивания стационарного  потока интенсивностью λ_исх получается снова простейший поток с интенсивностью l.

, где λ_исх – это интенсивность Пуассоновского стационарного потока, направляемого в БВЗ.

λ_исх = 100 с^-1

получим: с^-1

 

Полученный поток является Пуассоновским, т.к. он является:

 

• При просеивании простейшего потока мы получаем снова простейший поток  , где – вероятность того, что пачка сохранится; – интенсивность просеянного потока.
• Ординарным (сигналы приходят поодиночке, а не группами).
• Марковским (для любых двух непересекающихся интервалов времени число сигналов, пришедших во время одного из них, не зависит от того, сколько сигналов пришло во время другого интервала).

 

Оптимизация работы блока  выполнения запросов.

Рассмотрим БВЗ как систему  массового обслуживания типа М/М/n с  ограничением по длине очереди, то есть как n-канальную СМО (канал это модуль блока БВЗ) с простейшим потоком заявок (заявка – это запрос) и показательным законом обслуживания заявки.

Полагая количество модулей, занятых  обслуживанием запросов в БВЗ, n = [1..10], для каждого из этих n вариантов рассчитаем средний доход в единицу времени D от эксплуатации АИС и относительную пропускную способность АИС Q, рассматривая в дальнейшем параметры D и Q как компоненты векторного критерия оптимальности W = (D;Q), а пару D(n), Q(n) для каждого n как допустимое решение.

Совокупный  средний доход в единицу времени D от эксплуатации АИС может быть записан в количественном виде следующей формулой:

,

где:  
– доход, который приносит фирме один выполненный запрос;  
– штраф за единицу времени обслуживания одного запроса;  
– среднее время пребывания запроса в АИС;  
– абсолютная пропускная способность блока выполнения запросов (среднее число выполняемых запросов в единицу времени);  
– убытки от неучастия в течение единицы времени одного модуля БВЗ в выполнении вспомогательных операций;  
– количество модулей БВЗ, непосредственно занятых выполнением запросов.

Используя формулы приведенные в «исходных данных» найдем:

 

;

(руб);

(руб/сек);

(руб/сек);

 

Чтобы найти совокупный средний  доход в единицу времени D,

где ,

необходимо определить среднее  время пребывания запроса в АИС  и абсолютную пропускную способность БВЗ (А).

,

где ( – среднее число заявок находящихся в АИС), а l получена на втором этапе l = , в свою очередь

 

, ( – среднее число заявок находящихся в очереди)

где m = 3 и n = 10  (по исходным данным)

,

 Т = 0,08  (по исходным данным)

 

, ( – среднее число занятых каналов)

 

Для определения А:

 

  ,

 

где Q – относительная пропускная способность.

 

 

Используя все вышеприведенные формулы вычислим D и Q  в программе..

Получили  множество допустимых решений: