ТЕМА 2. Транспортная задача.

Задача 7

Решите задачу о назначениях

3 8 2 10

8 7 2 9

6 4 2 7

8 4 2 3

Решение.

Выявление наименьших элементов по строкам

Наименьший элемент вычитается из всех элементов соответствующей строки.

Ищем наименьший элемент по столбцам.

Наименьший элемент вычитается из всех элементов соответствующего столбца.

5
3

Осуществляем назначения (по строкам).

Осуществляем назначения (по столбцам).

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

То есть оптимальный выбор будет в следующих клетках: (1, 1)–(2, 3)–(3, 2)–(4, 4).

Минимальный вариант составит:

3+2+4+3=12.

ТЕМА 3. Модели сетевого планирования и управления

Задача 2

Рассчитать параметры сетевого графика:

1. Выделить критический путь и найти его длину;

2. Определить резервы времени каждого события;

3. Определить резервы времени всех работ и коэффициент напряженности работы предпоследней работы

Решение.

Определим ранние сроки:

t_р (0) = 0

t_р (1) = 0 + 2 = 2

t_р (2) = 0 + 5 = 5

t_р (3) = max {2+12; 5+9} = 14

t_р (4) = 14 + 9 = 23

t_р (5) = max {14+8; 23+3} = 26

t_р (6) = 26 + 9 = 35

t_р (7) = max {2+15; 26+5; 35+7} = 42

t_р (8) = max {23+5; 35+4} = 39

t_р (9) = max {39+6; 35+9} = 45

t_р (10) = max {42+10; 45+8} = 53

Определим поздние сроки совершения событий. Начиная с последнего и затем двигаясь к первому:

t_п (10) = t_р (10) = 53

t_п (9) = 53 – 8 = 45

t_п (8) = 45 – 6 = 39

t_п (7) = 53 – 10 = 43

t_п (6) = min {43-7; 45-9; 39-4} = 35

t_п (5) = min {35-9; 43-5} = 26

t_р (4) = min {26-3; 39-5} = 23

t_р (3) = min {23-9; 27-8} = 14

t_п (2) = 14 – 9 = 5

t_р (1) = min {14-12; 43-15} = 2

t_п (0) = min {2-2; 5-5} = 0

Определим резервы времени по формуле:

R (0) = 0 – 0 = 0

R (1) = 2 – 2 = 0

R (2) = 5 – 5 = 0

R (3) = 14 – 14 = 0

R (4) = 23 – 23 = 23

R (5) = 26 – 26 = 0

R (6) = 35 – 35 = 0

R (7) = 43 – 42 = 1

R (8) = 39 – 39 = 0

R (9) = 45 – 45 = 0

R (10) = 53 – 53 = 0

Для определения критического пути фиксируем события, не имеющие резервов времени. Следовательно, путь 0 → 1(2) → 3 → 5 → 6 → 8 → 9 → 10 является критическим.

Длина критического пути t_кр = t_р (М) = 53.

Определим коэффициент напряженности работы предпоследней работы:

Т.к. коэффициент напряженности равен 1, то предпоследняя работа является очень напряженной и ее ложно выполнить в установленный срок.