Контрольная работа по дискретной математике.
Задание 1.
На рисунке изображен граф. Его дуги обозначены буквами a – p. Обозначить произвольным образом вершины графа. Взяв из таблицы вариантов данные о длине его дуг, определить:
1. Кратчайший путь из начальной вершины в конечную, и длину кратчайшего пути.
2. Критический путь из начальной вершины в конечную, и длину критического пути.
3. Считая этот граф сетевым графиком некоторого процесса, а длины дуг – временем осуществления работ, определить:
- для каждой вершины-события ранний и поздний срок его свершения и его резерв времени,
- для каждой дуги-работы независимый резерв времени.
Варианты:
| №
|
a
|
b
|
c
|
d
|
e
|
f
|
g
|
h
|
i
|
j
|
k
|
l
|
m
|
n
|
o
|
p
|
| 1
|
4 |
5 |
3 |
5 |
6 |
4 |
2 |
7 |
4 |
8 |
2 |
8 |
6 |
2 |
1 |
4 |
| 2
|
3 |
3 |
4 |
2 |
5 |
7 |
4 |
3 |
3 |
5 |
8 |
2 |
2 |
6 |
7 |
3 |
| 3
|
3 |
4 |
4 |
3 |
2 |
1 |
3 |
5 |
5 |
4 |
3 |
4 |
7 |
1 |
2 |
2 |
| 4
|
3 |
4 |
4 |
4 |
4 |
4 |
6 |
6 |
7 |
3 |
8 |
5 |
1 |
4 |
1 |
3 |
| 5
|
3 |
2 |
1 |
4 |
6 |
3 |
1 |
1 |
5 |
3 |
6 |
7 |
8 |
4 |
2 |
6 |
| 6
|
3 |
2 |
2 |
4 |
5 |
2 |
6 |
9 |
4 |
5 |
2 |
3 |
4 |
2 |
6 |
7 |
| 7
|
3 |
5 |
5 |
4 |
6 |
7 |
2 |
3 |
4 |
5 |
6 |
3 |
6 |
3 |
2 |
5 |
| 8
|
3 |
4 |
4 |
4 |
2 |
2 |
3 |
1 |
2 |
3 |
4 |
2 |
3 |
1 |
3 |
3 |
| 9
|
3 |
6 |
4 |
3 |
5 |
6 |
2 |
5 |
2 |
5 |
6 |
2 |
5 |
3 |
4 |
3 |
| 10
|
3 |
4 |
1 |
7 |
4 |
7 |
3 |
4 |
2 |
5 |
2 |
5 |
1 |
3 |
7 |
5 |
| 11
|
3 |
4 |
3 |
5 |
6 |
4 |
2 |
7 |
4 |
8 |
2 |
8 |
6 |
2 |
1 |
4 |
| 12
|
5 |
3 |
5 |
2 |
5 |
7 |
4 |
3 |
3 |
5 |
8 |
2 |
2 |
6 |
7 |
3 |
| 13
|
5 |
4 |
4 |
2 |
2 |
1 |
3 |
5 |
5 |
4 |
3 |
4 |
7 |
1 |
2 |
2 |
| 14
|
4 |
4 |
4 |
4 |
1 |
4 |
6 |
6 |
7 |
3 |
8 |
5 |
1 |
4 |
1 |
3 |
| 15
|
4 |
2 |
1 |
4 |
6 |
6 |
1 |
1 |
5 |
3 |
6 |
7 |
8 |
4 |
2 |
6 |
| 16
|
6 |
2 |
2 |
4 |
5 |
2 |
7 |
9 |
4 |
5 |
2 |
3 |
4 |
2 |
6 |
3 |
| 17
|
5 |
5 |
5 |
4 |
6 |
7 |
2 |
8 |
4 |
5 |
6 |
3 |
6 |
3 |
7 |
5 |
| 18
|
4 |
4 |
4 |
4 |
2 |
2 |
3 |
1 |
4 |
3 |
4 |
2 |
3 |
6 |
3 |
3 |
| 19
|
6 |
6 |
4 |
3 |
5 |
6 |
2 |
5 |
2 |
8 |
6 |
2 |
4 |
3 |
4 |
3 |
| 20
|
7 |
4 |
1 |
7 |
4 |
7 |
3 |
4 |
2 |
5 |
1 |
6 |
1 |
3 |
7 |
5 |
| 21
|
8 |
5 |
3 |
5 |
6 |
4 |
2 |
7 |
4 |
8 |
2 |
8 |
6 |
2 |
1 |
4 |
| 22
|
6 |
3 |
4 |
2 |
5 |
7 |
4 |
3 |
3 |
5 |
8 |
2 |
2 |
6 |
7 |
3 |
| 23
|
7 |
4 |
4 |
3 |
2 |
1 |
3 |
5 |
5 |
4 |
3 |
4 |
7 |
1 |
2 |
2 |
| 24
|
6 |
4 |
4 |
4 |
4 |
4 |
6 |
6 |
7 |
3 |
8 |
5 |
1 |
4 |
1 |
3 |
| 25
|
6 |
2 |
1 |
4 |
6 |
3 |
1 |
1 |
5 |
3 |
6 |
7 |
8 |
4 |
2 |
6 |
| 26
|
6 |
2 |
2 |
4 |
5 |
2 |
6 |
9 |
4 |
5 |
2 |
3 |
4 |
2 |
6 |
7 |
| 27
|
7 |
5 |
5 |
4 |
6 |
7 |
2 |
3 |
4 |
5 |
6 |
3 |
6 |
3 |
2 |
5 |
| 28
|
8 |
4 |
4 |
4 |
2 |
2 |
3 |
1 |
2 |
3 |
4 |
2 |
3 |
1 |
3 |
3 |
Задание 2.
Проект состоит из последовательного выполнения работ u1
, u2
, u3
, u4
.
Для каждой работы ui
() определена зависимость ее стоимости si
от времени ее осуществления ti
.
1. Предполагая, что , определить:
a) время осуществления работ , для которых общая стоимость проекта минимальна при условии, что весь проект должен быть закончен не позднее времени Tmax
. Также найти при этих условиях минимальную стоимость проекта и стоимость осуществления каждой работы .
Значения
,
Tmax
для каждого варианта даны в столбцах 2 - 6 таблицы вариантов
б) стоимости работ , для которых общее время осуществления проекта минимально при условии, что общая стоимость проекта не более Smax
. Также найти при этих условиях минимальное время осуществления проекта и время осуществления каждой работы .
Значения
,
Smax
для каждого варианта даны в столбцах 2 – 5 и 7 таблицы вариантов.
2. Предполагая, что зависимость si
от ti
линейная и убывающая, и зная для каждой работы ui
ее минимальное и максимальное время осуществления и , а также минимальную и максимальную стоимость и определить:
a) время осуществления работ , для которых общая стоимость проекта минимальна при условии, что весь проект должен быть закончен не позднее времени Tmax
. Также найти при этих условиях минимальную стоимость проекта и стоимость осуществления каждой работы .
Значения
, ,
, , Tmax
для каждого варианта даны в столбцах 8 – 15 и 6 таблицы вариантов.
б) стоимости работ , для которых общее время осуществления проекта минимально при условии, что общая стоимость проекта не более Smax
. Также найти при этих условиях минимальное время осуществления проекта и время осуществления каждой работы .
Значения
, ,
, , Smax
для каждого варианта даны в столбцах 8 – 15 и 7 таблицы вариантов.
Варианты:
| 1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
| №
вар-та.
|
a1
|
a2
|
a3
|
a4
|
Tmax
|
Smax
|
|
|
|
|
|
|
|
|
| 1
|
6 |
5 |
3 |
1 |
10 |
40 |
|
|
|
|
|
|
|
|
| 2
|
2 |
3 |
4 |
2 |
15 |
70 |
|
|
|
|
|
|
|
|
| 3
|
3 |
6 |
4 |
2 |
10 |
10 |
|
|
|
|
|
|
|
|
| 4
|
3 |
4 |
1 |
7 |
10 |
40 |
|
|
|
|
|
|
|
|
| 5
|
3 |
2 |
1 |
4 |
10 |
30 |
|
|
|
|
|
|
|
|
| 6
|
3 |
2 |
5 |
4 |
15 |
20 |
|
|
|
|
|
|
|
|
| 7
|
3 |
5 |
9 |
4 |
20 |
70 |
|
|
|
|
|
|
|
|
| 8
|
3 |
4 |
2 |
1 |
25 |
20 |
|
|
|
|
|
|
|
|
| 9
|
3 |
6 |
4 |
1 |
10 |
60 |
|
|
|
|
|
|
|
|
| 10
|
3 |
4 |
1 |
7 |
10 |
70 |
|
|
|
|
|
|
|
|
| 11
|
3 |
4 |
8 |
5 |
10 |
40 |
|
|
|
|
|
|
|
|
| 12
|
5 |
3 |
7 |
2 |
15 |
70 |
|
|
|
|
|
|
|
|
| 13
|
5 |
4 |
3 |
2 |
20 |
10 |
|
|
|
|
|
|
|
|
| 14
|
4 |
2 |
1 |
3 |
10 |
40 |
|
|
|
|
|
|
|
|
| 15
|
4 |
2 |
1 |
3 |
20 |
60 |
|
|
|
|
|
|
|
|
| 16
|
6 |
1 |
2 |
4 |
25 |
20 |
|
|
|
|
|
|
|
|
| 17
|
5 |
3 |
2 |
4 |
25 |
70 |
|
|
|
|
|
|
|
|
| 18
|
4 |
2 |
1 |
5 |
20 |
20 |
|
|
|
|
|
|
|
|
| 19
|
6 |
2 |
4 |
3 |
10 |
60 |
|
|
|
|
|
|
|
|
| 20
|
7 |
4 |
1 |
3 |
15 |
70 |
|
|
|
|
|
|
|
|
| 21
|
8 |
5 |
3 |
9 |
10 |
40 |
|
|
|
|
|
|
|
|
| 22
|
6 |
3 |
4 |
2 |
20 |
70 |
|
|
|
|
|
|
|
|
| 23
|
7 |
4 |
9 |
3 |
25 |
10 |
|
|
|
|
|
|
|
|
| 24
|
6 |
7 |
9 |
5 |
20 |
40 |
|
|
|
|
|
|
|
|
| 25
|
6 |
2 |
1 |
4 |
20 |
30 |
|
|
|
|
|
|
|
|
| 26
|
6 |
2 |
3 |
4 |
15 |
20 |
|
|
|
|
|
|
|
|
| 27
|
7 |
5 |
6 |
4 |
20 |
70 |
|
|
|
|
|
|
|
|
| 28
|
8 |
1 |
3 |
4 |
20 |
20 |
|
|
|
|
|
|
|
|