Сетевое планирование

Август 20, 2022

Главная
Математика
Сетевое планирование

Содержание

2. При исследовании операций на практике часто приходится встречаться с задачей рационального планирования сложных, комплексных работ. Примерами
3. Характерным для каждого такого комплекса работ является то, что он состоит из ряда отдельных, элементарных работ
4. Планирование любого такого комплекса работ должно производиться с учетом следующих существенных элементов: времени, потребного на выполнение
5. При планировании сравнительно небольших по объему (количеству звеньев) комплексов работ ответ на такие вопросы обычно дает
6. Одним из математических методов, широко применяемых при решении такого рода задач, является метод сетевого планирования или,
7. Обратные задачи, как правило, гораздо сложнее прямых. Чтобы решать обратные задачи, нужно прежде всего научиться решать
8. Пусть имеется некоторое количество видов работ A1, … , An. Некоторые из этих работ опираются на
9. Работа называется критической, если при задержке начала её выполнения увеличивается время выполнения всего комплекса работ. Если
10. Имеется комплекс из четырех работ А1, А2, А3, А4. Работы А3 и А4 опираются на А1
11. Описанный выше графический способ построения и анализа плана работ пригоден только в случае, когда планируемый комплекс
12. Эту задачу можно решить с помощью таблицы: Для нахождения резервного времени найдем все пути. Нахождение критического
13. Если работы не упорядочены по рангу, задачу решаем следующим образом. Упорядочиваем все работы по возрастанию ранга,
14. Пример (вариант 47)
15. Пример (вариант 47)
16. Пример (вариант 47)
17. Пример (вариант 47)
18. Пример (вариант 47)
19. Пример (вариант 47)
20. Пример (вариант 47)
21. Пример (вариант 47)
22. Пример (вариант 47)
23. Пример (вариант 47)
24. Пример (вариант 47)
25. Пример (вариант 47)
26. Пример (вариант 47)
27. Пример (вариант 47)
28. Пример (вариант 47)
29. Пример (вариант 47)
30. Пример (вариант 47)
31. Пример (вариант 47)
32. Пример (вариант 47)
33. Пример (вариант 47)
34. Пример (вариант 47)
35. Пример (вариант 47)
36. Пример (вариант 47)
37. Пример (вариант 47)
38. Пример (вариант 47)
39. Пример (вариант 47)
40. Пример (вариант 47)
41. Пример (вариант 47)
42. Пример (вариант 47)
43. Пример (вариант 47)
44. Пример (вариант 47)
45. Пример (вариант 47)
46. Пример (вариант 47)
47. Пример (вариант 47)
48. Пример (вариант 47)
49. Критическое время Критический путь в новых обозначениях: Критический путь в исходных обозначениях: Пример (вариант 47)
50. Найдем резерв времени для работы B7. Для этого найдем максимальную продолжительность пути, проходящего через B7. Пример
51. Пример (вариант 47)
52. Имеется комплекс работ А1, …, Аn. Будем считать, что время выполнения работ зависит от вложенных в
53. Если на Аi направлены дополнительные средства в количестве xi единиц, то при , где − максимально
54. Эта задача может быть сведена к двум задачам линейного программирования. 1) 2) Эти задачи могут быть
55. Рассмотрим два случая. Пример (вариант 50)
56. Пример (вариант 50)
57. ОДР − пятиугольник ABCDE. Решение в точке А. Вычислим координаты этой точки, решив систему: Таким образом,
58. Таким образом, получаем задачу: Аналогично первому случаю построим чертеж. Пример (вариант 50)
59. Пример (вариант 50)
60. Пример (вариант 50) Можно оба случая рассмотреть на одном чертеже.
61. ОДР − пятиугольник ОFAE. Решение в точке А (10, 20). Координаты точки А вычисляем как в
62. Имеется комплекс из четырех работ А1, А2, А3, А4. Работы А3 и А4 опираются на А1
64. Скачать презентацию

Слайд 2

При исследовании операций на практике часто приходится встречаться с задачей рационального

планирования сложных, комплексных работ.
Примерами таких работ могут быть:
строительство большого промышленного объекта,
перевооружение армии или отдельных видов вооруженных сил,
развертывание системы медицинских или профилактических мероприятий,
выполнение комплексной научно-исследовательской темы с участием ряда организаций и т. д.

Глава 2. Сетевое планирование

Введение

Слайд 3

Характерным для каждого такого комплекса работ является то, что он состоит

из ряда отдельных, элементарных работ или «звеньев», которые не просто выполняются независимо друг от друга, а взаимно обусловливают друг друга, так что выполнение некоторых работ не может быть начато раньше, чем завершены некоторые другие.
Так, например, при строительстве промышленного предприятия рытье котлована не может быть начато раньше, чем будут доставлены и смонтированы соответствующие агрегаты; укладка фундамента не может быть начата раньше, чем будут доставлены необходимые материалы, для чего, в свою очередь, требуется завершение строительства подъездных путей; для всех этапов строительства необходимо наличие соответствующей технической документации и т. д.

Введение

Слайд 4

Планирование любого такого комплекса работ должно производиться с учетом следующих существенных

элементов:
времени, потребного на выполнение всего комплекса работ и его отдельных звеньев;
стоимости всего комплекса работ и его отдельных звеньев;
сырьевых, энергетических и людских ресурсов.
Рациональное планирование комплекса работ требует, в частности, ответа на следующие вопросы:
Как распределить имеющиеся материальные средства и трудовые ресурсы между звеньями комплекса?
В какие моменты начинать и когда заканчивать отдельные звенья?
Какие могут возникнуть препятствия к своевременному завершению комплекса работ и как их устранять?

Введение

Слайд 5

При планировании сравнительно небольших по объему (количеству звеньев) комплексов работ ответ

на такие вопросы обычно дает руководитель, причем без специальных математических расчетов, просто на основе опыта и здравого смысла.
Однако, когда речь идет об очень сложных, дорогостоящих комплексах работ, состоящих из большого числа звеньев, сложным образом обусловливающих друг друга, такие приемы становятся недопустимыми.
В этих случаях возникает необходимость в специальных расчетах, позволяющих обоснованно ответить на поставленные выше вопросы и ряд других.

Введение

Слайд 6

Одним из математических методов, широко применяемых при решении такого рода задач,

является метод сетевого планирования или, как его часто называют, СПУ (сетевое планирование управления).
Метод сетевого планирования позволяет решать как прямые, так и обратные задачи исследования операций.
Прямые задачи отвечают на вопрос:
что будет, если мы примем данную схему организации операции?
Обратные отвечают на вопрос:
как нужно организовать (спланировать) операцию, чтобы она обладала, в каком-то смысле, максимальной эффективностью?

Введение

Слайд 7

Обратные задачи, как правило, гораздо сложнее прямых. Чтобы решать обратные задачи,

нужно прежде всего научиться решать прямые.
Основным материалом для сетевого планирования является список или перечень работ (звеньев) комплекса, в котором указаны не только работы, но и их взаимная обусловленность (окончание каких работ требуется для начала выполнения каждой работы).
Будем называть такой список структурной таблицей комплекса работ.

Введение

Слайд 8

Пусть имеется некоторое количество видов работ A1, … , An. Некоторые

из этих работ опираются на другие работы. Известна продолжительность выполнения каждой работы, и будем обозначать время выполнения работы Ai через ti. Некоторые работы могут выполняться одновременно. Требуется определить минимальное время выполнения всех работ.
Будем называть работу работой первого ранга, если она не опирается ни на какие другие работы. Выполнение всех работ первого ранга может начинаться в начальный момент времени (начальный момент времени будем брать равным нулю, тогда время завершения последней работы определяет время выполнения комплекса работ). Работа называется работой ранга k, если она опирается на работы рангов меньше k и опирается, по крайней мере, на одну работу ранга k – 1. Для комплекса работ можно построить схему – временной график.

Основные понятия

Слайд 9

Работа называется критической, если при задержке начала её выполнения увеличивается время

выполнения всего комплекса работ.
Если же выполнение некоторой работы может быть отложено на некоторый промежуток и при этом время выполнения всего комплекса работ не увеличится, то она называется некритической. Максимальный промежуток времени, на который мы можем отложить выполнение некритической работы без увеличения времени выполнения всех работ, называется резервом времени. У критических работ резерва времени нет.
Последовательность критических работ называется критическим путём. Критический путь может быть найден следующим образом. Для работ, которые заканчиваются последними, надо взять работы, на которые они опираются существенно. Для этих работ тоже взять работы, на которые они опираются существенно и т.д. Пройдя по цепочке от конца к началу, можно найти все критические работы.

Основные понятия

Слайд 10

Имеется комплекс из четырех работ А1, А2, А3, А4. Работы А3

и А4 опираются на А1 и А2 каждая. Время выполнения работ: ,
, , . Надо найти критическое время, критический путь и резервы времени всех работ. Решим задачу с помощью временного графика.
Критический путь:

Нахождение критического времени и критического пути

Слайд 11

Описанный выше графический способ построения и анализа плана работ пригоден только

в случае, когда планируемый комплекс не слишком сложен (по количеству работ и логических связей).
На практике часто встречаются комплексы работ, состоящие из огромного числа звеньев (порядка тысяч и более), сложным образом опирающихся друг на друга. Естественно, что в таких случаях вычерчивание сетевого графика вручную – тяжелое и неблагодарное занятие, так как основное преимущество сетевого графика – его наглядность – при этом теряется.

Нахождение критического времени и критического пути

Слайд 12

Эту задачу можно решить с помощью таблицы:
Для нахождения резервного времени найдем

все пути.

Нахождение критического времени и критического пути

Слайд 13

Если работы не упорядочены по рангу, задачу решаем следующим образом. Упорядочиваем

все работы по возрастанию ранга, вводя при необходимости новые обозначения. Сначала вводим обозначения для работ, которые не опираются на другие работы. Затем обозначаем те работы, которые опираются на уже имеющие новые обозначения. Таких способов введения новых обозначений имеется несколько.
Определяем время завершения каждой работы, прибавляя к её продолжительности время работы, на которую она опирается существенно. Критическое время выполнения работ – это максимальное время завершения некоторой работы. Критический путь определяется по цепочке от конца к началу, беря на каждом шаге работы, на которые данная работа опирается существенно. Другими словами, берутся работы, которые завершаются последними из тех на которые опирается данная работа.

Нахождение критического времени и критического пути

Слайд 14

Пример (вариант 47)

Слайд 15

Пример (вариант 47)

Слайд 16

Пример (вариант 47)

Слайд 17

Пример (вариант 47)

Слайд 18

Пример (вариант 47)

Слайд 19

Пример (вариант 47)

Слайд 20

Пример (вариант 47)

Слайд 21

Пример (вариант 47)

Слайд 22

Пример (вариант 47)

Слайд 23

Пример (вариант 47)

Слайд 24

Пример (вариант 47)

Слайд 25

Пример (вариант 47)

Слайд 26

Пример (вариант 47)

Слайд 27

Пример (вариант 47)

Слайд 28

Пример (вариант 47)

Слайд 29

Пример (вариант 47)

Слайд 30

Пример (вариант 47)

Слайд 31

Пример (вариант 47)

Слайд 32

Пример (вариант 47)

Слайд 33

Пример (вариант 47)

Слайд 34

Пример (вариант 47)

Слайд 35

Пример (вариант 47)

Слайд 36

Пример (вариант 47)

Слайд 37

Пример (вариант 47)

Слайд 38

Пример (вариант 47)

Слайд 39

Пример (вариант 47)

Слайд 40

Пример (вариант 47)

Слайд 41

Пример (вариант 47)

Слайд 42

Пример (вариант 47)

Слайд 43

Пример (вариант 47)

Слайд 44

Пример (вариант 47)

Слайд 45

Пример (вариант 47)

Слайд 46

Пример (вариант 47)

Слайд 47

Пример (вариант 47)

Слайд 48

Пример (вариант 47)

Слайд 49

Критическое время
Критический путь в новых обозначениях:
Критический путь в исходных обозначениях:

Пример (вариант 47)

Слайд 50

Найдем резерв времени для работы B7.
Для этого найдем максимальную продолжительность пути,

проходящего через B7.

Пример (вариант 47)

Слайд 51

Пример (вариант 47)

Слайд 52

Имеется комплекс работ А1, …, Аn. Будем считать, что время выполнения

работ зависит от вложенных в них дополнительных средств. Полагаем, что эти зависимости являются линейными. В этом случае задача может быть сведена к нескольким задачам линейного программирования.
Если с работой Аi снимается xi единиц средств, то время ее выполнения определяется формулой:
при .
− время выполнения работы Аi без изменения средств,
− некоторый коэффициент,
− максимальное количество средств, которое может быть снято.

Задача сетевого планирования с перераспределением средств

Слайд 53

Если на Аi направлены дополнительные средства в количестве xi единиц, то

при , где − максимально возможное количество добавлямых средств.
Рассмотрим эту задачу на примере комплекса из трех работ. Работы А1 и А2 первого ранга, А3 опирается на А1 и А2.
Без ограничения общности полагаем, что А1 завершается раньше А2. Тогда с работы А1 можно снять часть средств и направить их на работы А2 и А3.
Ставится задача найти способ перераспределение средств, при котором критическое время будет минимальным.

Задача сетевого планирования с перераспределением средств

Слайд 54

Эта задача может быть сведена к двум задачам линейного программирования.
1) 2)

Эти задачи могут быть решены геометрическим методом.

так как .

Задача сетевого планирования с перераспределением средств

Слайд 55

Рассмотрим два случая.
Пример (вариант 50)

Слайд 56

Пример (вариант 50)

Слайд 57

ОДР − пятиугольник ABCDE. Решение в точке А.
Вычислим координаты этой точки,

решив систему:
Таким образом, получаем

Пример (вариант 50)

Слайд 58

Таким образом, получаем задачу:
Аналогично первому случаю построим чертеж.
Пример (вариант 50)

Слайд 59

Пример (вариант 50)

Слайд 60

Пример (вариант 50)
Можно оба случая рассмотреть на одном чертеже.

Слайд 61

ОДР − пятиугольник ОFAE.
Решение в точке А (10, 20).
Координаты

точки А вычисляем как в предыдущем случае. Таким образом получаем:
Ответ:

Пример (вариант 50)

Слайд 62

Имеется комплекс из четырех работ А1, А2, А3, А4. Работы А3

и А4 опираются на А1 и А2 каждая. Время выполнения работ:
Резервы времени работ равны соответственно...
1) 3, 0, 0, 2;
2) 0, 2, 3, 0;
3) 2, 0, 0, 3;
4) 0, 3, 2, 0.

Задание для самоконтроля