ОДЗ №2 Исследование операций

Міністерство освіти і науки, молоді та спорту України

Сумський державний університет

Кафедра комп’ютерних наук

Секція комп’ютеризованих систем управління

Обов’язкове домашнє завдання

з дисципліни: «Дослідження операцій»

на тему: «Теорія графів»

Варіант 27

Виконав студент

групи СУ-02

Паламарчук О. І.

Перевірив: Журба В. О.

Суми 2011

Зміст

1. Пошук шляху компонування . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2. Оптимізація компонування робочої технологічної схеми насосної станції . . . . 7

Пошук шляху компонування

Дані: технологічна схема (ТС) насосної станції другого підйому комунального водопостачання. Вага дуг орграфа наведена в таблиці 1. Номери нероботоздатних елементів ТС: 2, 3. Номери вершин для пошуку компонування 0-14.

Таблиця 1

Дуга	0-1	1-2	2-3	3-4	1-6	1-11	3-8	3-13	5-6	6-7	7-8	8-9	6-11	8-13	10-11	11-12	12-13	13-14
Вага дуги, м	3	1	2	3	2	6	3	7	4	5	3	3	2	4	4	3	4	2

Розв’язок:

1. Математична модель технологічна схема (ТС) насосної станції другого підйому комунального водопостачання у вигляді орграфа показана на рисунку 1.

2. Математичний опис цього орграфа у вигляді матриці інцидентності і матриці суміжності показані в таблицях 2 і 3.

3. Орграф робото здатної ТС подано на рисунку 2.

4. Матриця ваг дуг орграфа подана в таблиці 4.

Рисунок 1

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	1	0	0	0	1	0	0	0	0	1	0	0	0
2	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0
3	0	0	0	0	1	0	0	0	1	0	0	0	0	1	0
4	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
5	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0
6	0	1	0	0	0	0	0	1	0	0	0	1	0	0	0
7	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0
8	0	0	0	1	0	0	0	0	0	1	0	0	0	1	0
9	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
10	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0
11	0	1	0	0	0	0	1	0	0	0	0	0	1	0	0
12	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0
13	0	0	0	1	0	0	0	0	1	0	0	0	0	0	1
14	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

Таблиця 2

	0-1	1-2	2-3	3-4	1-6	1-11	3-8	3-13	5-6	6-7	7-8	8-9	6-11	8-13	10-11	11-12	12-13	13-14
0	-1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	1	-1	0	0	-1	-1	0	0	0	0	0	0	0	0	0	0	0	0
2	0	1	-1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
3	0	0	1	-1	0	0	-1	-1	0	0	0	0	0	0	0	0	0	0
4	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
5	0	0	0	0	0	0	0	0	-1	0	0	0	0	0	0	0	0	0
6	0	0	0	0	1	0	0	0	1	-1	0	0	-1	0	0	0	0	0
7	0	0	0	0	0	0	0	0	0	1	-1	0	0	0	0	0	0	0
8	0	0	0	0	0	0	1	0	0	0	1	-1	0	-1	0	0	0	0
9	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0
10	0	0	0	0	0	0	0	0	0	0	0	0	0	0	-1	0	0	0
11	0	0	0	0	0	1	0	0	0	0	0	0	1	0	1	-1	0	0
12	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	-1	0
13	0	0	0	0	0	0	0	1	0	0	0	0	0	1	0	0	1	-1
14	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1

Таблиця 3

Рисунок 2

0

1

5

6

7

8

9

10

11

12

13

14

0

0

3

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

1

∞

0

∞

2

∞

∞

∞

∞

6

∞

∞

∞

5

∞

∞

0

4

∞

∞

∞

∞

∞

∞

∞

∞

6

∞

2

∞

0

5

∞

∞

∞

2

∞

∞

∞

7

∞

∞

∞

∞

0

3

∞

∞

∞

∞

∞

∞

8

∞

∞

∞

∞

∞

0

3

∞

∞

∞

4

∞

9

∞

∞

∞

∞

∞

∞

0

∞

∞

∞

∞

∞

10

∞

∞

∞

∞

∞

∞

∞

0

4

∞

∞

∞

11

∞

6

∞

2

∞

∞

∞

∞

0

3

∞

∞

12

∞

∞

∞

∞

∞

∞

∞

∞

∞

0

4

∞

13

∞

∞

∞

∞

∞

4

∞

∞

∞

∞

0

2

14

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

0