Практичне заняття 1. Основні поняття теорії графів. Матричне представлення графів. Алгоритм Флойда (стр. 9 )

Таблиця 5

Етап сорту-вання	Накопи-чувач	Розподіл напрямів сортування за накопичувачами
Вхідна послідовність напрямів сортування 03,06,05,05,10,10,00,07,08,01,05,01,03,04,15,13,00,02,02,07,07,12,03,08
1	А0 А1 А2 А3	00,08,04,00,12,08 05,05,01,05,01,13 06,10,10,02,02 03,07,03,15,07,07,03
Проміжна послідовність напрямів сортування після першого етапу сортування 00,08,04,00,12,08,05,05,01,05,01,13,06,10,10,02,02,03,07,03,15,07,07,03
2	А0 А1 А2 А3	00,00,01,01,02,02,03,03,03 04,05,05,05,06,07,07,07 08,08,10,10 12,13,15
Вихідна послідовність напрямів сортування після другого етапу сортування 00,00,01,01,02,02,03,03,03,04,05,05,05,06,07,07,07,08,08,10,10,12,13,15

Варіанти

1. q=2, s=4, n=14

00, 02, 04, 06, 08, 10, 12, 13, 11, 07, 05, 03, 01

2. q=2, s=4, n=16

15, 13, 11, 09, 07, 05, 03, 01, 00, 02, 04, 06, 08, 10, 12, 14

3. q=2, s=4, n=14

00, 01, 03, 05, 07, 09, 11, 13, 02, 04, 06, 08, 10, 12

4. q=4, s=2, n=16

00, 02, 04, 01, 03, 05, 06, 08, 10, 07, 09, 11, 12, 14, 13, 15

5. q=4, s=2, n=12

05, 07, 09, 11, 06, 08, 10, 00, 02, 04, 01, 03

6. q=2, s=4, n=16

00, 02, 03, 08, 04, 07, 09, 10, 12, 14, 15, 05, 11, 06, 13, 01

7. q=4, s=2, n=16

00, 02, 03, 08, 04, 07, 09, 10, 12, 14, 15, 05, 11, 06, 13, 01

8. q=3, s=3, n=23

22, 20, 18, 16, 14, 12, 10, 08, 06, 04, 02, 00, 01, 03, 05, 07, 09, 11, 13, 15, 17, 19, 21

10. q=4, s=2, n=16

15, 13, 11, 09, 07, 05, 03, 01, 00, 02, 04, 06, 08, 10, 12, 14

11. q=3, s=3, n=25

01, 03, 05, 07, 02, 04, 06, 08, 09, 11, 13, 15, 10, 12, 14, 00, 17, 19, 21, 23, 24, 16, 18, 20, 22

12. q=10, s=2, n=80

00, 02, 03, 05, 07, 09, 11, 13, 15, 01, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 04, 06, 08, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 64, 66, 68, 70, 72, 74, 76, 78

13. q=3, s=3, n=25

01, 03, 05, 07, 09, 11, 13, 15, 17, 19, 21, 23, 24, 22, 20, 18, 16, 14, 12, 10, 08, 06, 04, 02, 00

14. q=2, s=4, n=15

14, 12, 10, 08, 06, 04, 02, 00, 13, 09, 07, 05, 03, 01

15. q=4, s=2, n=14

00, 02, 04, 06,08, 10, 12, 13, 11, 09, 07, 05, 03, 01

16. q=10, s=2, n=70

00, 02, 04, 06, 08, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40,42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 69, 67, 65, 63, 61, 59, 57, 55, 53, 51, 49, 47, 45, 43, 41, 39, 37, 35, 33, 31, 29, 27, 25, 23, 21, 19, 17, 15, 13, 11, 09, 07, 05, 03, 01

17. q=4, s=2, n=13

00, 01, 03, 05, 07, 09, 11, 02, 04, 06, 08, 10, 12

18. q=2, s=4, n=12

05, 07, 09, 11, 06, 08, 10, 00, 02, 04, 01, 03

19. q=3, s=3, n=27

04, 06, 08, 10, 12, 13, 15, 16, 18, 14, 00, 02, 17, 01, 19, 21, 23, 25, 20, 22, 24, 26

20. q=3, s=3, n=27

00, 02, 04, 06, 01, 03, 05, 07, 08, 10, 12, 14, 16, 09, 11, 13, 15, 17, 18, 20, 22, 24, 26, 19, 21, 23, 25

21. q=2, s=4, n=15

03, 05, 07, 00, 02, 04, 08, 09, 10, 06, 11, 13, 12, 14, 01

22. q=10, s=2, n=60

58, 56, 54, 52, 50, 48, 46, 44, 42, 40, 38, 36, 34, 32, 30, 28, 26, 24, 22, 20, 18, 16, 14, 12, 10, 08, 06, 04, 02, 00, 01, 03, 05, 07, 09, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59

23. q=10, s=2, n=70

00, 02, 04, 06, 08, 10, 01, 03, 05, 07, 09, 12, 14, 16, 18, 20, 11, 13, 15, 17, 19, 22, 24, 26, 28, 30, 21, 23, 25, 27, 29, 32, 34, 36, 38, 40, 31, 33, 35, 37, 39, 42, 44, 46, 48, 50, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 52, 54, 56, 58, 60, 62, 64, 66, 68, 61, 63, 65, 67, 69

24. q=10, s=2, n=60

00, 02, 04, 06, 08, 10, 01, 03, 05, 07, 09, 12, 14, 16, 18, 20, 11, 13, 15, 17, 19,22, 24, 26, 28, 30, 21, 23, 25, 27, 29, 32, 34, 36, 38, 40, 31, 33, 35, 37, 39, 42, 44, 46, 48, 50, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 52, 54, 56, 58

25. q=2, s=4, n=16

00, 02, 04, 01, 03, 05, 06, 08, 10, 07, 09, 11, 12, 14, 13, 15

26. q=10, s=2, n=80

00, 02, 04, 06, 08, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 79, 77, 75, 73, 71, 69, 67, 65, 63, 61, 59, 57, 55, 53, 51, 49, 47, 45, 43, 41, 39, 37, 35, 33, 31, 29, 27, 25, 23, 21, 19, 17, 15, 13, 11, 09, 07, 05, 03, 01

Практичне заняття 3

Мета: Отримати практичні навики по визначенню числа робочих місць з оброблення поштових відправлень

Ключові положення

Метод. керівництво: “Застосування методів теорії графів для розв’язування типових задач поштового зв’язку” -, , Одеса 2000.

Навчальний посібник: “Мережі та системи поштового зв’язку” -, , Кріль С. С, Одеса 2008.

, , Беркман зв¢язок. – К.: Техніка, 2003

Число робочих місць з оброблення поштових відправлень у вузлі поштового зв’язку визначається значеннями поштового навантаження, що надходить у цей вузол, нормативом припустимого часу оброблення поштових відправлень, тобто припустимої затримки закінчення оброблення поштових відправлень відносно часу їхнього надходження у вузол, і значенням продуктивності праці одного робітника (кількості поштових відправлень, що обробляє один робітник за одну годину).

Нерівномірність надходження поштового навантаження у вузол поштового зв’язку обумовлює необхідність використання різного числа робочих місць у різні інтервали доби.

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

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

Нижче наведені метод і алгоритм точного визначення необхідного числа робочих місць з оброблення поштових відправлень у вузлі поштового зв’язку.

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

N1 N2 Ni Nj Nk

… … …

T1 T2 Ti Tj T

Рисунок 3.1

Оскільки кожне поштове відправлення повинно бути оброблене за час, що не перевищує заданого нормативу, графік оброблення поштових відправлень може бути поданий у виді гіпотенузи прямокутного трикутника, катетами якого є навантаження Ni, що надходить у вузол в момент Ti, і інтервал часу ΔT припустимого оброблення навантаження у вузлі (рис. 6.2.2).

Ni

a

Ti Ti + ΔT

Рисунок 3.2.

Тангенс кута нахилу гіпотенузи трикутника являє собою значення продуктивності оброблення поштових відправлень у вузлі

.

Реально в інтервалі часу ΔT можуть мати місце кілька надходжень поштових навантажень, внаслідок чого в зазначеному інтервалі часу виконується оброблення поштових відправлень, що залишилися необробленими в попередньому інтервалі, і поштових відправлень, що надійшли в поточному інтервалі. В свою чергу оброблення поштових відправлень, що залишилися необробленими в поточному інтервалі часу, виконується в наступному інтервалі.

Таким чином, можуть мати місце зсуви оброблення поштових відправлень за умови, що максимальна затримка оброблення будь-якого надходження поштових відправлень не перевищує заданого нормативу ΔT.

Отже, йдеться про знаходження максимального серед мінімальних значень кутів нахилу гіпотенуз усіх трикутників, що відповідають усім надходженням поштових відправлень у вузол, яке забезпечує оброблення будь-якого надходження поштових відправлень в заданому інтервалі часу.

Оскільки для оброблення навантажень Ni і Nj, що надходять у вузол в моменти часу Ti і Tj в межах одного інтервалу ΔT, може бути виділений час, рівний Tj – Ti +ΔT, значення необхідної продуктивності оброблення поштових відправлень у вузлі визначається значенням тангенсу кута нахилу гіпотенузи відповідного спільного трикутника

,

принцип побудови якого випливає з рис. 3.2.

Ni + Nj

Ni

Nj

a

Ti Tj Tj + ΔT

Рисунок 3.3

Узагальнюючи таке визначення значення кута нахилу гіпотенузи трикутника на довільний розподіл надходжень N1, N2, …, Ni, …, Nj, …, Nk поштового навантаження в моменти часу T1, T2, …, Ti, …, Tj, …, Tk на протязі доби дійдемо висновку, що значення необхідної продуктивності оброблення поштових відправлень у вузлі визначається максимальним значенням кута нахилу гіпотенузи серед всіх трикутників, що відповідають будь-яким можливим послідовностям надходжень поштового навантаження у вузол.

Число робочих місць R з оброблення поштових відправлень дорівнює

R = éQмакс / Qр ù ,

де Qмакс - максимальна продуктивність оброблення поштових відправлень у вузлі.

Qр – продуктивність праці одного робітника,

éХ ù - значення Х, округлене до найближчого більшого цілого числа.

Алгоритм розрахунку числа робочих місць з оброблення поштових відправлень.

Крок 1.- виконується введення початкових даних: кількості надходжень поштових відправлень k; графіку надходження поштових відправлень N1, T1, N2, T2, …, Nk, T k; значення припустимої затримки оброблення поштових відправлень у вузлі ΔT; значення продуктивності праці одного робітника Qр.

Крок 2 - обнулюється значення максимальної продуктивності оброблення поштових відправлень Qмакс .

Крок 3 - обнулюється значення поточного індексу і.

Крок 4 - значення поточного індексу і збільшується на одиницю.

Крок 5 - обчислюється значення поточного індексу j = i - 1.

Крок 6 - обнулюється значення навантаження послідовності надходжень поштових відправлень Nп.

Крок 7 - значення поточного індексу j збільшується на одиницю.

Кроку 8 - значення навантаження послідовності надходжень поштових відправлень Nп збільшується на величину поточного надходження поштових відправлень Nj.

Крок 9 - обчислюється значення часу, що виділяється на оброблення навантаження послідовності надходжень поштових відправлень, Tп = Tj - Ti + ΔT.

Крок 10 - обчислюється значення необхідної продуктивності оброблення навантаження послідовності надходжень поштових відправлень Qп = Nп / Tп .

Крок 11 - виконується перевірка виконання умови Qмакс < Qп. Якщо “Так” – перехід до наступного блоку, якщо “Ні” – до кроку 13.

Крок 12 - значення Qмакс замінюється значенням Qп.

Крок 13 - виконується перевірка, чи дорівнює значення поточного індексу j значенню загального числа надходжень поштового навантаження k. Якщо “Так” – перехід до наступного блоку, якщо “Ні” – повернення до кроку 7.

Крок 14 виконується перевірка, чи дорівнює значення поточного індексу і значенню загального числа надходжень поштового навантаження k. Якщо “Так” – перехід до наступного блоку, якщо “Ні” – повернення до кроку 4.

Крок 15 - обчислюється необхідне число робочих місць R з оброблення поштових відправлень у вузлі як округлене до найближчого цілого числа відношення знайденого значення Qмакс до значення продуктивності праці одного робітника Qр.

Нижче наведено приклад визначення числа робочих місць з оброблення письмової кореспонденції у вузлі поштового зв’язку.

Кількість надходжень поштового навантаження – 4.

Графік надходження поштового навантаження (тис. листів) у вузол наведено в табл. 3.1

Таблиця 3.1

Навантаження	6	4	8	3
Час надходження	08.00	10.30	12.00	14.00

Норматив часу оброблення письмової кореспонденції у вузлі – 3 години.

Продуктивність праці одного працівника – 2 тис. листів за годину.

В табл. 3.2. наведено значення результатів циклічного виконання блоків алгоритму рис. 3.2.

Таблиця 3.2.

№ блоку	Змінна	Цикли
і = 1	і = 2	і = 3	і = 4
j=1	j=2	j=3	j=4	j=2	j=3	j=4	j=3	j=4	j=4
2.	Qмакс	0
3.	і	0
4.	і	1				2			3		4
5.	j	0				1			2		3
6.	Nп	0				0			0		0
7.	j	1	2	3	4	2	3	4	3	4	4
8.	Nп	6	10	18	21	4	12	15	8	11	3
9.	Tп	3	5,5	7	9	3	4,5	6,5	3	5	3
10.	Qп	2,00	1,82	2,57	2,33	1,33	2,67	2,31	2,67	2.22	1,00
11.	Qмакс < Qп?	Так	Ні	Так	Ні	Ні	Так	Ні	Ні	Ні	Ні
12.	Qмакс	2,00		2,57			2,67
13.	j = k ?	Ні	Ні	Ні	Так	Ні	Ні	Так	Ні	Так	Так
14.	і = k?				Ні			Ні		Ні	Так
15.	R										2

Як випливає з отриманих результатів, для оброблення письмової кореспонденції в зазначеному вузлі достатньо двох робочих місць з максимальною продуктивністю оброблення письмової кореспонденції 2,67 тис. за годину (по 1,33 тис. на кожному з робочих місць).