по дискретной математике

Контрольная работа по дискретной математике.



Задание 1. 

На рисунке изображен граф. Его дуги обозначены буквами a – p. Обозначить произвольным образом вершины графа. Взяв из таблицы вариантов данные о длине его дуг, определить:

1. Кратчайший путь  из начальной вершины в конечную, и длину кратчайшего пути.

2. Критический путь из начальной вершины в конечную, и длину критического пути.

3. Считая этот граф сетевым графиком некоторого процесса, а длины дуг – временем осуществления работ, определить:

- для каждой вершины-события ранний и поздний срок его свершения и его резерв времени, 

- для каждой дуги-работы независимый резерв времени.





a

b

c

d

e

f

     g

        h

  i

   j  

k

      l

       m

       n

o

       p
Варианты:



№

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