Раздел 3 Динамическое программирование

1 Решите задачу эвакуации при ограничении на грузоподъемность G=11

	П1	П2	П3	П4
g (вес)	2	4	6	7
С (цена)	30	40	50	60
x

Ответ: x1 = 0, x2 = 1, x3 = 0, x4 = 1.

2 Решите задачу о распределении ресурсов

X	φ1	φ2	φ3	φ4
1	0,2	0,4	0,8	1,0
2	0,4	0,5	0,9	1,0
3	0,6	0,6	1,1	1,1
4	0,8	0,7	1,3	1,1
5	1,0	0,8	1,4	1,2
6	1,2	0,9	1,5	1,2
7	1,4	1,0	1,5	1,3
8	1,5	1,1	1,6	1,3

Используем метод динамического программирования.

1 шаг – даём 1 предприятию денег

2 шаг – даём 2 предприятию денег

Искусственное

П1 – П2 – П3 – П4 ->

Начинаем с последнего.

4

Ответ: Самое лучшее распределение ресурсов при φ1 = 1, φ2 = 0.4, φ3 = 0.8, φ4 = 1.

Раздел 4 Сетевые модели

По приведенному графу постройте сетевой график. Найдите критический путь; определите моменты ранних и поздних начал и окончаний работ, резервы времени для работ, не лежащих на критическом пути.

Сетевой график

Расчет сроков свершения событий.

Для i=1 (начального события), очевидно tp(1)=0. i=2: t^p(2) = t^p(1) + t(1,2) = 0 + 2 = 2. i=3: t^p(3) = t^p(1) + t(1,3) = 0 + 3 = 3. … i=9: max(t^p(7) + t(7,9);t^p(8) + t(8,9)) = max(14 + 9;17 + 3) = 23.

Длина критического пути равна раннему сроку свершения завершающего события 9: t_kp=tp(9)=23

При определении поздних сроков свершения событий t_п(i) двигаемся по сети в обратном направлении, то есть справа налево. Для i=9 (завершающего события) поздний срок свершения события должен равняться его раннему сроку (иначе изменится длина критического пути): t^п(9)= t^р(9)=23 Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 8. Просматриваются все строчки, начинающиеся с номера 8. i=8: t^п(8) = t^п(9) - t(8,9) = 23 - 3 = 20. 7. Просматриваются все строчки, начинающиеся с номера 7. i=7: t^п(7) = t^п(9) - t(7,9) = 23 - 9 = 14. …

1. Просматриваются все строчки, начинающиеся с номера 1. i=1: min(t^п(2) - t(1,2);t^п(3) - t(1,3)) = min(2 - 2;6 - 3) = 0.

Таблица 1 - Расчет резерва событий

Находим полный резерв R^П_i-j = Tп_j-t_i-j-Tр_i

Свободный резерв времени также можно найти и по формуле R^C_i-j = Tп_i-t_i-j-Tр_i

Независимый резерв времени также можно найти и по формуле R^Н_i-j = Tр_j-t_i-j-Tп_i

Таблица 2 - Анализ сетевой модели по времени

Критический путь: (1,2)(2,4)(4,7)(7,9) или (A,C)(C,H)(H,I)(I,G) по приведённому графу. Продолжительность критического пути: 23