Файл: Z9411_КафкаРС_ИссОп_КР.docx

Цикл приведен в таблице (3,3 → 3,2 → 1,2 → 1,3). Оценка свободной клетки равна Δ₃₃ = (4) - (3) + (5) - (3) = 3. (3;4): В свободную клетку (3;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	ai
A1	5	5[8]	3[32]	4	40
A2	6	7[22][+]	6	5[28][-]	50
A3	4	3[35][-]	4	5[+]	35
A4	3[48]	5	7	6[22]	70
bj	48	65	32	50	195

Цикл приведен в таблице (3,4 → 3,2 → 2,2 → 2,4). Оценка свободной клетки равна Δ₃₄ = (5) - (3) + (7) - (5) = 4. (4;2): В свободную клетку (4;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	ai
A1	5	5[8]	3[32]	4	40
A2	6	7[22][-]	6	5[28][+]	50
A3	4	3[35]	4	5	35
A4	3[48]	5[+]	7	6[22][-]	70
bj	48	65	32	50	195

---

Цикл приведен в таблице (4,2 → 4,4 → 2,4 → 2,2). Оценка свободной клетки равна Δ₄₂ = (5) - (6) + (5) - (7) = -3. (4;3): В свободную клетку (4;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	B1	B2	B3	B4	ai
A1	5	5[8][+]	3[32][-]	4	40
A2	6	7[22][-]	6	5[28][+]	50
A3	4	3[35]	4	5	35
A4	3[48]	5[+]	7[+]	6[22][-]	70
bj	48	65	32	50	195

Цикл приведен в таблице (4,3 → 4,4 → 2,4 → 2,2 → 1,2 → 1,3). Оценка свободной клетки равна Δ₄₃ = (7) - (6) + (5) - (7) + (5) - (3) = 1. Опорный план является неоптимальным, поскольку имеются отрицательные оценки клеток (4,2;) равные: (-3).

Переход от неоптимального опорного плана к лучшему. Поскольку в исходном опорном плане рассматриваемой задачи свободная клетка (4;2) имеет отрицательную оценку, то для получения плана, обеспечивающего меньшее значение целевой функции, эту клетку следует занять возможно большей поставкой, не нарушающей при этом условий допустимости плана. Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 4) = 22. Прибавляем 22 к объемам грузов, стоящих в плюсовых клетках и вычитаем 22 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

---

	B1	B2	B3	B4	ai
A1	5	5[8]	3[32]	4	40
A2	6	7[0]	6	5[50]	50
A3	4	3[35]	4	5	35
A4	3[48]	5[22]	7	6	70
bj	48	65	32	50	195

Минимальные затраты составят:

Lф = 5*8 + 3*32 + 5*50 + 3*35 + 3*48 + 5*22 = 745

Анализ оптимального плана. Из 1-го склада необходимо груз направить в 2-й магазин (8 ед.), в 3-й магазин (32 ед.) Из 2-го склада необходимо весь груз направить в 4-й магазин. Из 3-го склада необходимо весь груз направить в 2-й магазин. Из 4-го склада необходимо груз направить в 1-й магазин (48 ед.), в 2-й магазин (22 ед.)

Проверка в Excel:

---

Раздел 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

---