Математическое программирование
Методическое пособие - Компьютеры, программирование
Другие методички по предмету Компьютеры, программирование
ы сетевого планирования
Сетевой график - сеть, вершины которой - события, результаты определённых работ или состояния этапов промежуточных работ), а дуги - работы (протяжённый во времени процесс, приводящий к соответствующему событию). Веса дуг, как правило, - время выполнения работ.
Пример.
Составление сетевого графика требует выполнения определённых организационных и формальных правил.
Организационные правила:
) составляется подробный перечень всех работ от отправного момента до целевого результата;
) определяется продолжительность всех работ;
) устанавливаются технологические связи между всеми промежуточными событиями и упорядочивается их последовательность, т.е. для каждого события определяются все предшествующие и все последующие работы.
Формальные правила:
1) сетевой график должен иметь только одно исходное событие - исток и только одно завершающее - сток;
) любые два события должны быть связанны не более чем одной работой и, наоборот, каждая работа должна заключаться между двумя событиями;
) сеть не должна иметь контуров, петель, изолированных участков, не связанных работами с её остальной частью;
) сетевой график должен быть упорядочен по вершинам.
Замечание: для выполнения формальных правил и учёта ряда технологических процессов вводят фиктивные события и работы. В частности.
1.Если комплекс работ начинается с нескольких работ, не имеющих предшествующих (нарушается п. 1 формальных правил), вводится фиктивный исток с дугами к указанным работам.
2.Если два события связанны параллельными дугами (нарушается п.2 формальных правил), вводится фиктивное событие, на которое замыкается одна из работ.
.Если следует учесть зависимость событий, не связанных реальными работами (различные работы a и b выполняются на одном оборудовании), то вводится фиктивная работа c:
В случаях 1) - 3) фиктивные работы не имеют протяжённости во времени.
. Если технологический процесс требует естественного дозревания, брожения, затвердевания, высушивания и т. д., т.е. когда реальная работа не производится, но следующее событие без учёта этих процессов начаться не может, то вводится фиктивная работа, имеющая протяжённость во времени.
К основным параметрам сетевого графика относятся:
1)продолжительность t* критического пути, т.е. наиболее протяжённого во времени пути от истока к истоку;
2)резервы времени событий R(i),определяющие предельно допустимые задержки событий i, не приводящие к изменению t*;
3)полный резерв времени промежуточной работы Rij, определяющий максимальный запас времени, на который можно задержать начало работы или увеличить её продолжительность, не изменяя t*;
4)свободный резерв времени промежуточной работы rij, определяющий максимальный запас времени, на которое можно задержать начало работы или увеличить её продолжительность, не нарушая самые ранние сроки начала всех последующих работ.
Критический путь - последовательность работ и событий, не имеющих резервов времени. Общий срок завершения комплекса работ определяется продолжительностью критического пути.
Если события i дают начало работам, продолжающимся tij ед. времени и завершающимся событием j, то ожидаемый (ранний) срок ti наступления j-ого события равен
, (1)
(1-е событие - исток),
где ti - ожидаемый (ранний) срок i - го события (i<j).
Наиболее поздний срок наступления i - го события
Ti = min(Tj - tij), i = n = tn = t* (n-e coбытие - сток) (2)
Т =
Резерв времени наступления i-го события
(3)
Свободный резерв времени работы (i,j)
(4)
Полный резерв времени работы (i,j)
(5)
Расчёты параметров сетевого графика проводят в 5 этапов, изображая события кружками с четырьмя секторами, которые заполняются по ходу выполнения этапов:
1)находят все ti по формулам (1), при этом перемещаются по сетевому графику согласно номерам событий слева направо;
2)находят Ti по формулам (2), при этом перемещаются по сетевому графику от стока влево по мере убывания номеров событий;
)определяю Ri по формуле (3)
)выделяют критический путь;
)вычисляют все остальные параметры.
Пример.
Замечания:
1.Резерв времени наступления события Ri позволяет варьировать сроки готовности события i в пределах ti Ti.
.Свободные резервы времени работ с учётом их значений можно использовать (отсрочить начало или затянуть окончание) по всем некритическим работам сети одновременно, не изменив t*.
.Полные резервы времени использовать одновременно удаётся не всегда.
Правила построения двойственной задачи.
Исходя из общего вида прямой и двойственной задач можно установить связь между этими задачами, позволяющую для любой ЗЛП строить двойственную ей задачу.
Свойства двойственных задач (правила).
9.Число неизвестных двойственной задачи равно числу ограничений прямой задачи. Число ограничений двойственной задачи равно числу неизвестных прямой задачи.
10.Матрица коэффициентов двойственной задачи является транспонированной матрицей коэффициентов прямой задачи.
.Коэффициенты целевой функции двойственной задачи являются свободными членами ограничений прямой задачи.
.Свободные члены ограничений двойственной задачи являются коэффициентами целевой функции прямой задачи.
13.Если ограничения прямой задач