close

Вход

Забыли?

вход по аккаунту

?

курсач(7)

код для вставкиСкачать
Сетевой график и правила его построения.
Одним из математических методов современной теории управления большими
системами, широко применяемым на практике, является метод сетевого
планирования и управления (СПУ). Методы СПУ были разработаны сравнительно
недавно. Так как они разрабатывались в разных странах, возникло несколько их
разновидностей: СПУ—в СССР, РЕRТ и СРМ—в США и др.
Метод РЕRТ применяется в планировании научно-исследовательских и опытноконструкторских разработок, для которых характерна неопределенность в оценке
затрат времени, необходимого для выполнения отдельных операций (работ).
Метод СРМ применяется тогда, когда оценки времени операций
детерминированные.
Основой метода СПУ является сетевой график (сетевая модель), отражающий(ая)
логическую взаимосвязь и взаимообусловленность входящих в него
элементарных операций (работ).
Сетевые графики, рассматриваемые в данной главе с математической точки
зрения, представляют собой орграфы без контуров, дугам или вершинам которых
приписаны некоторые числовые значения.
В системах СПУ используются следующие, наиболее распространенные способы
построения сетевых графиков:
1) сетевые графики в терминах «дуги-операции». В таких графиках вершины,
называемые событиями, соответствуют моментам времени начала или
окончания одной или нескольких операций, а дуги — операциям;
2) сетевые графики в терминах «дуги-связи», в которых операции изображаются
вершинами сети, а дуги показывают порядок выполнения (взаимосвязь)
отдельных операций.
Каждый из способов построения сетевых графиков имеет как преимущества, так и
недостатки. Учитывая, однако, что первый способ получил большее практическое
применение в нашей стране, в дальнейшем сетевые графики будем
рассматривать в терминах «дуги-операции».
В сетевом графике различают три вида событий: исходное, завершающее и
промежуточное. Исходное — это такое событие, с которого начинается
выполнение комплекса операций. Завершающее соответствует достижению
конечной цели, т. е. завершению комплекса операций. Сетевые графики с
несколькими завершающими событиями называются многоцелевыми. К
промежуточным относятся все прочие события.
События обозначаются кружками или другими геометрическими фигурами.
Предполагается, что события не имеют продолжительности и наступают как бы
мгновенно.
Моментом свершения события считается момент окончания выполнения всех
входящих в это событие операций.
Рис. 1.4.
Рис. 1.5.
Пока не выполнены все входящие в событие операции, не может свершиться
само событие, а следовательно, не может быть начата ни одна из непосредственно следующих за ним операций. Различают три вида операций:
1) действительная операция процесс, требующий затрат времени и ресурсов
(разработка проекта, подвоз материалов, выполнение монтажных работ и т. д.);
2) операция-ожидание процесс, требующий только затрат времени (затвердение
бетона, естественная сушка штукатурки перед началом малярных работ, рост
растений и т. д.);
3) фиктивная операция, или логическая зависимость, отражает технологическую
или ресурсную зависимость в выполнении некоторых операций.
При построении сетевых графиков необходимо соблюдать определенные
правила:
1) в сети не должно быть событий (кроме исходного), в которые не входит ни одна
дуга;
2) не должно быть событий (кроме завершающего), из которых не выходит ни
одной дуги;
3) сеть не должна содержать контуров;
4) любая пара событий сетевого графика может быть соединена не более чем
одной дугой. Если изобразить одновременно (параллельно) выполняемые три
различные операции b, с, а с общими начальным и конечным событиями (рис.
1.4), то возникает путаница из-за того, что различные операции имеют одно и то
же обозначение (2,5). В этом случае рекомендуется ввести дополнительные события и соединить их с последующими фиктивными операциями (рис.1.5);
5) если какие-либо операции могут быть начаты до полного окончания
непосредственно предшествующей им операции, то последнюю целесообразно
представить как ряд последовательно выполняемых операций, завершающихся
определенными событиями.
Алгоритм построения максимального потока в транспортной сети.
Важным следствием теоремы Форда-Фалкерсона является Алгоритм построения
максимального потока в транспортной сети.
Алгоритм:
Шаг 1. Полагаем i=0. Пусть - любой допустимый поток в транспортной сети D
(например, полный, можно начинать с нулевого потока: ).
Шаг 2. По сети D и потоку строим орграф приращений .
Шаг 3. Находим простую цепь , являющуюся минимальным путем из в в
нагруженном орграфе . Если длина этой цепи равна бесконечности, то
поток максимален, и работа алгоритма закончена. В противном случае
увеличиваем поток вдоль цепи на максимально допустимую величину , такую, что
при этом сохраняется условие 1 допустимого потока (для любой дуги величина ,
называемая потоком по дуге х, удовлетворяет условию ). В силу , используя и ,
получаем, что указанная величина существует. В результате меняется поток в
транспортной сети D, т.е. от потока мы перешли к потоку , и при этом .
Присваиваем и переходим к шагу 2.
3. Практическая часть Постановка задачи: Информация о строительстве
комплекса задана нумерацией работ, их продолжительностью (в ед. времени),
последовательностью выполнения и оформлена в виде таблицы. За какое
минимальное время может быть завершён весь комплекс работ?
i
1
j
2
Продолжительность 2
работы
1
3
4
1
5
6
2
6
8
2
4
10
3
5
9
3
6
8
4
8
2
5
7
7
6
8
4
7
8
7
3.1 по данным таблицы построить сетевой график комплекса работ и найти
правильную нумерацию его вершин;
3.2 рассчитать на сетевом графике ранние и поздние сроки наступления
событий, а также резервы времени событий;
Тр(1)=0
Тп(8)=27
TR(1)=0
Тр(2)=max(2)=2
Тп(7)=min(20)=20
ТR(2)=13
Тр(3)=max(4)=4
Тп(6)=min(23)=23
ТR(3)= 0
Тр(4)=max(12)=12
Тп(5)=min(13)=13
ТR(4)=13
Тр(5)=max(13,6)=13
Тп(4)=min(25)=25
ТR(5)=0
Тр(6)=max(10,12)=12
Тп(3)=min(15,4)=4
ТR(6)=11
Тр(7)=max(20)=20
Тп(2)=min(15,15)=15
ТR(7)=0
Тр(8)=max(14,16,27)=27
Тп(1)=min(13,0,7)=0
ТR(8)=0
Тогда Ткр = 27 – минимальное время графика
3.3 выделить на сетевом графике критические пути;
(1,3) (3,5) (5,7) (7,8)
3.4 для не критических работ найти полные и свободные резервы времени;
Работа
Продолжительност Ранние
ь
сроки
Поздние
сроки
Полный
резерв
Свободный
резерв
(i,j)
tij
Tip
Tjp
Tiп
Тjп
Rij
rij
1,2
2
0
2
0
15
13
0
2,4
10
2
12
15
25
12
0
2,6
8
2
12
15
23
13
2
4,8
2
12
27
25
27
13
13
1,3
4
0
4
0
4
0
0
3,6
8
4
12
4
23
11
0
6,8
4
12
27
23
27
11
11
3,5
9
4
13
4
13
0
0
1,5
6
0
13
0
13
7
7
5,7
7
13
20
13
20
0
0
7,8
7
20
27
20
27
0
0
Здесь Rij=Tjп-Tip-tij;
rij=Tjр-Tiр-tij; -полный и свободный резерв.
3.5 проанализировать результаты решения.
4. вывод
Документ
Категория
Экономико-математическое моделирование
Просмотров
30
Размер файла
90 Кб
Теги
курсач
1/--страниц
Пожаловаться на содержимое документа