Алгоритм и этапы решения задачи
Пример 1. Пусть реализуется проект по асфальтированию участка земли под АТС, при этом привлекаемые рабочие могут выполнять любую из выделенных по принятой технологии работ. Менеджер проекта установил, что в данном проекте от начала до завершения ра-бот можно выделить пять событий и существуют шесть различных видов работ, связывающих эти события. При первоначальном распределении рабочих по видам работ на основе имеющихся нормативов трудоемкости были рассчитаны длительности выполнения работ (в днях). Таким образом, сетевой график реализации данного проекта имеет вид модели, представленной на рис. 19.1
Требуется рассчитать основные характеристики событий, работ и всей сетевой модели в целом, а также определить наличие резерва времени для некоторых работ в целях оптимизации модели и сокращения сроков выполнения проекта за счет перераспределения рабочих по видам работ.
Решение. Рассмотрим этапы табличного метода расчета данной сетевой модели. Результаты расчетов приведены в табл. 5.3 в графах 1—9.
Пояснения
Этап 1. Перечень работ и их продолжительность запишем в гр. 2 и 3 табл. 5.3, при этом работы записываются последовательно в гр. 2: сначала — начинающиеся с номера 1, затем с ном.2 и т.д.
Этап2 . В первой графе поставим число Kпр, показывающее количество работ, непосредственно предшествуюших событию i, с которого начинается рассматриваемая работа . Для работ , начинающихся с номера 1 предшествующих работ нет . Для работы , начинающейся с номера к, просматриваются все верхние строки второй гра-фы и отыскиваются работы, начинающиеся на к . Количество найденных работ записывается во все строки гр.1, которые соответствуют рабо-там, начинающимся с номера k Например, для работы (4, 5) в гр. 1 поставим цифру 2, так как на номер 4 оканчиваются две работы: (1, 4) и (3, 4).
Этап 3. Заполнение таблицы начинается с расчета раннего срока работ tp(i). Для работ, имеющих цифру «НОЛь» в первой графе, в гр. 4 также заносятся нули и рассчитываются соответствующие значения гр. 5 (ранний срок окончании tро(I,j) как суммы соответствующих чисел в гр. 2 и 3 (см. формулу (5.41)). В нашей модели таких работ три; в первой строке гр. 5 ставим 6 + 0 = 6, аналогично во второй и третьей строках.
Для заполнения следующих строк гр. 4. для работ (i,j)просматриваются заполненные строки гр. 5, котОрые содержат работы, оканчивающиеся на номер i, и максимальНое из наИденных значений (если их несколько) переносится в гр 4 для обрабатываемых строк. Так, в нашем примере в четвертой строке в гр. 4 ставим 6, а гр 5
15 (9 + 6 = 15).
Аналогично в пятой строке гр. 4 и 5 ставим соответственно 5 и 17
(12 + 5 = 17).
В последней, шестой, строке гр. 4 ставим 17 (наибольшее из чисел 8 и 17 в гр 5) и соответственно в гр. 5 ставим 21 (4 + 17 = 21).
Этап 4. Графы 7 и 6 заполняются «обратным ходом», т.е. снизу вверх. Для этого просматриваются строки (работы), оканчивающиеся на номер N последнего события , и из гр.5 выбирается величина. Эта величина записывается в гр. 7 по всем строкам, оканчивающимся на N (см. формулу (5.42) с учетом равенства tn(N) = tp(N)). Затем заполняется гр. 6 по этим строкам как разность между гр. 7 и 3 (см. формулу (5.43)).
В нашем примере таких строк две (четвертая и шестая), в гр. 5 стоят числа 15 и 21; выбираем наибольшее из них (21) и записываем его в гр. 7 по этим строкам, после чего заносим соответствующие числа в гр. 6.
Далее просматриваются строки, оканчивающиеся на номер события, предшествующего заверша-ющему, т.е. на (N — 1). Для этих строк просмат-риваются все строки гр. 6, лежащие ниже и начинающиеся с номера (N — 1). Среди них в гр. 6 выбирается минимальная величина, которая переносится в гр. 7 по обрабатываемым строкам, после чего заполняется гр. 6. В нашем примере таких строк две (третья и пятая); ниже их с номера 4 начинается одна (последняя) работа, и в гр. 6 стоит 17, следовательно, в гр. 7 по этим строкам ставим число 17, после чего заполняется гр. 6.
Затем аналогичный процесс повторяется для строк, оканчивающихся на (N — 2), (N — 3) и т д., до тех пор, пока не будут заполнены все строки по гр. 7 и 6. В нашем примере результаты приведены в соответствующих графах табл. 5.3.
Этап 5. Показатели гр. 8 рассчитываются как разности соответствующих показателей гр. 6 и 4 или гр. 7 и 5 (см. формулы (5.39) или (5.44)). Чтобы заполнить гр. 9, можно предварительно рассчитать резервы времени каждого события по формуле (5.39), а затем воспользоваться формулой (5.46). В нашем примере резервы времени для каждого из пяти событий равны соответственно: R(1) = 0; R(2) = 12 - 6 = 6; R(3) = 5-5 = 0; R(4) = 17 - 17 = 0; R(5) = 0. Последующие результаты по формуле (5.46) приведены в гр. 9 табл. 5.3.
Этап 6. На этом этапе подводятся основные итоги расчета. Учитывая, что нулевой резерв времени имеют только работы (Rn = 0) и события (R(i) = 0), принадлежащие критичес-кому пути, получаем, что критическим является путь LKp = (1, 3, 4, 5), продолжительность которого (tкр) равна 21 дню.
Так как работы (1, 2), (1, 4) и (2, 5) имеют ненулевые резервы Rn, то очевидно, что путем перевода некоторого числа рабочих с этих работ на работы, принадлежащие критиче-кому пути, можно сократить продолжитель-ность этого пути и тем самым сократить сроки выполнения проекта в целом.
Сети Петри. Сети Петри — математический аппарат для моделирования динамических дискретных систем.
Впервые описаны Карлом Петри в 1984 году.
Сеть Петри представляет собой двудольный ориентированный граф, состоящий из вершин двух типов — позиций и переходов, соединённых между собой дугами, вершины одного типа не могут быть соединены непосредственно. В позициях могут размещаться метки (маркеры), способные перемещаться по сети.
Событием называют срабатывание перехода, при котором метки из входных позиций этого перехода перемещаются в выходные позиции. События происходят мгновенно, либо разновременно, при выполнении некоторых условий.
Пример сети Петри. Белыми кружками обозначены позиции, полосками — переходы, чёрными кружками — метки.
Некоторые виды сетей Петри:
- Временная сеть Петри — переходы обладают весом, определяющим продолжительность срабатывания (задержку).
- Стохастическая сеть Петри — задержки являются случайными величинами.
- Функциональная сеть Петри — задержки определяются как функции некоторых аргументов, например, количества меток в каких-либо позициях, состояния некоторых переходов.
- Цветная сеть Петри — метки могут быть различных типов, обозначаемых цветами, тип метки может быть использован как аргумент в функциональных сетях.
- Ингибиторная сеть Петри — возможны ингибиторные дуги, запрещающие срабатывания перехода, если во входной позиции, связанной с переходом ингибиторной дугой, находится метка.
- Иерархическая сеть — содержит не мгновенные переходы, в которые вложены другие, возможно, также иерархические, сети. Срабатывание такого перехода характеризует выполнение полного жизненного цикла вложенной сети.
- WF-сети
Основными свойствами сети Петри являются:
- ограниченность — число меток в любой позиции сети не может превысить некоторого значения K;
- безопасность — частный случай ограниченности, K=1;
- сохраняемость — постоянство загрузки ресурсов, постоянна. Где Ni — число маркеров в i-той позиции, Ai — весовой коэффициент;
- достижимость — возможность перехода сети из одного заданного состояния (характеризуемого распределением меток) в другое;
- живость — возможность срабатывания любого перехода при функционировании моделируемого объекта.
В основе исследования перечисленных свойств лежит анализ достижимости.
Сети Петри - это аппарат для моделирования динамических дискретных систем (преимущественно асинхронных параллельных процессов). Сеть Петри определяется как четверка <Р, Т, I, О>, где Р и Т - конечные множества позиций и переходов, I и О -множества входных и выходных функций. Другими словами, сеть Петри представляет собой двудольный ориентированный граф, в котором позициям соответствуют вершины, изображаемые кружками, а переходам - вершины, изображаемые утолщенными черточками; функциям I соответствуют дуги, направленные от позиций к переходам, а функциям О - дуги, направленные от переходов к позициям.
Как и в системах массового обслуживания, в сетях Петри вводятся объекты двух типов: динамические, которые изображаются метками (маркерами) внутри позиций, и статические, которым соответствуют вершины сети Петри.
Распределение маркеров по позициям называют маркировкой. Маркеры могут перемещаться в сети. Каждое изменение маркировки называют событием, причем каждое событие связано с определенным переходом. Считается, что события происходят мгновенно и разновременно при выполнении некоторых условий.
Каждому условию в сети Петри соответствует определенная позиция. Совершению события соответствует срабатывание (возбуждение или запуск) перехода, при котором маркеры из входных позиций этого перехода перемещаются в выходные позиции. Последовательность событий образует моделируемый процесс.
Правила срабатывания переходов (рис. 2.8) конкретизируют следующим образом: переход срабатывает, если для каждой из его входных позиций выполняется условие Ni> Кi, где Ni - число маркеров в i-й входной позиции, Ki - число дуг, идущих от i-й позиции к переходу; при срабатывании перехода число маркеров в i-й входной позиции уменьшается на Кi, а в j-й выходной позиции увеличивается на Мj ,где Мj - число дуг, связывающих переход с j-й позицией.
На рис. 19.2. показан пример распределения маркеров по позициям перед срабатыванием, эту маркировку записывают в виде (2, 2, 3, 1) или (2231). После срабатывания перехода маркировка принимает вид (1,0,1,4).
Можно вводить ряд дополнительных правил и условий в алгоритмы моделирования, получая ту или иную разновидность сетей Петри. Так, прежде всего полезно ввести модельное время, чтобы моделировать не только последовательность событий, но и их привязку ко времени. Это осуществляется приданием переходам веса - продолжительности (задержки) срабатывания, которую можно определять, используя задаваемый при этом алгоритм. Полученную модель называют временной сетью Петри..
Рис. 19.2. Фрагмент сети Петри Рис. 19.3. Конфликтная ситуация
Если задержки являются случайными величинами, то сеть называют стохастической. В стохастических сетях возможно введение вероятностей срабатывания возбужденных переходов. Так, на рис. 2.9 представлен фрагмент сети Петри, иллюстрирующий конфликтную ситуацию - маркер в позиции p может запустить либо переход t1 ,либо переход t2. В стохастической сети предусматривается вероятностный выбор срабатывающего перехода в таких ситуациях.
Если задержки определяются как функции некоторых аргументов, которыми могут быть количество маркеров в каких-либо позициях, состояния некоторых переходов и т.п., то сеть называют функциональной.
Во многих задачах динамические объекты могут быть нескольких типов, и для каждого типа нужно вводить свои алгоритмы поведения в сети. В этом случае каждый маркер должен иметь хотя бы один параметр, обозначающий тип маркера. Такой параметр обычно называют цветом; цвет можно использовать как аргумент в функциональных сетях. Сеть Петри при этом называют цветной.
Среди других разновидностей сетей Петри следует упомянуть ингибиторные сети, характеризующиеся тем, что в них возможны запрещающие (ингибиторные) дуги. Наличие маркера во входной позиции, связанной с переходом ингибиторной дугой, означает запрещение срабатывания перехода.
Введенные понятия поясним на следующих простых примерах.
Пример 1. Требуется описать с помощью сети Петри функционирование системы из предприятий A, В и С. Предприятия А и В поставляют узлы Х1 и X2 соответственно, а на предприятии С происходит сборка, в каждый сборочный узел входит один узел X1 и два узла X2. На рис. 2.10 предприятиям А, В и С соответствуют переходы t1, t2 и t3.
Рис. 19.4 Сеть Петри для примера 1
Срабатывание перехода t3 происходит только в том случае, если, во-первых, в позиции pl имеется метка, а в позиции р2 - не менее двух меток, что
означает поступление от пред-приятии А и В соответствующих комплектующих, и, во-вторых, имеется метка в позиции p4, что означает, что предприятие С закончило сборку предыдущего изделия и готово приступить к сборке следующего. Пока очередное изделие не будет собрано, метки в p4 не будет, следовательно, запросы, пришедшие во входные позиции р1 и р2, вынуждены ожидать срабатывания перехода t4. Переходам t1, t2 и t3 поставлены в соответствие процедуры вычисления задержек срабатывания. Задержки в первых двух переходах равны интервалам времени между появлениями готовых узлов, задержка в t3 равна времени сборки изделия.
Пример 2. Требуется описать с помощью сети Петри процессы возникновения и устранения неисправностей в некоторой технической системе, состоящей из М однотипных блоков; в запасе имеется один исправный блок; известны статистические данные об интенсивностях возникновения отказов и длительностях таких операций, как поиск неисправностей, замена и ремонт отказавшего блока. На рис. 2.11 представлена соответствующая сеть Петри. Отметим, что при числе меток в позиции, равном М, можно в ней не ставить М точек, а записать в позиции значение М.
Рис. 2.11. Сеть Петри для примера 2
В нашем примере значение M в позиции р2 соответствует числу имеющихся в системе блоков. Переходы отображают следующие события: t1 - отказ блока, t2- поиск неисправного блока, t3 - его замена, t4 - окончание ремонта.
Очевидно, что при непустой позиции рг переход t1 срабатывает, но с задержкой, равной вычисленному случайному значению моделируемого отрезка времени между отказами. После выхода маркера из t1 он попадает через р1 в t2, если имеется метка в позиции р6, это означает, что обслуживающая систему бригада специалистов свободна и может приступить к поиску возникшей неисправности. В переходе t2 метка задерживается на время, равное случайному значению длительности поиска неисправности. Далее маркер оказывается в р3 и если имеется запасной блок (маркер в р4), то запускается переход t3, из которого маркеры выйдут в р2 , р5 и р6 через отрезок времени, требуемый для замены блока. После этого в t4 имитируется восстановление неисправного блока.
Рассматриваемая модель описывает функционирование системы в условиях, когда отказы могут возникать и в рабочем, и в неисправном состояниях системы. Поэтому не исключены ситуации, при которых более чем один маркер окажется в позиции р1.
Марковские случайные процессы. Названы по имени выдающегося русского математика А.А.Маркова , впервые начавшего изучение вероятностной связи случайных величин и создавшего теорию, которую можно назвать "динамикой вероятностей". В настоящее время теория марковских процессов и ее приложения широко применяются в самых различных областях и , в том числе, в исследовании операций и теории принятия оптимальных решений.
Марковский процесс— дискретный или непрерывный случайный процесс X(t), который можно полностью задать с помощью двух величин:
· вероятности P(x,t) того, что случайная величина x(t) в момент времени t равна x, и
· вероятности P(x2, t2|x1,t1) того, что если x при t = t1 равен x1, то при t = t2 он равен x2.
Вторая из этих величин называется вероятностью перехода из состояния x1 при t = t1 в состояние x2 при t = t2.
Цепями Маркова называют дискретные по времени и значению Марковские процессы .
Пример 1. Предположим, что речь идет о последовательных бросаниях монеты при игре "в орлянку "; монета бросается в условные моменты времени t = 0, 1, ... и на каждом шаге игрок может выиграть ±1 с одинаковой вероятностью 1/2, таким образом в момент t его суммарный выигрыш есть случайная величина ξ(t) с возможными значениями j = 0, ±1, ... При условии, что ξ(t) = k, на следующем шаге выигрыш будет уже равен ξ(t+1) = k ± 1, принимая указанные знчения j = k ± 1 c одинаковой вероятностью 1/2. Условно можно сказать, что здесь с соответствующей вероятностью происходит переход из состояния ξ(t) = k в состояние ξ(t+1) = k ± 1.
Формулы и определения Марковских цепей. Обобщая этот пример, можно представить себе "систему" со счетным числом возможных "фазовых" состояний, которая с течением дискретного времени t = 0, 1, ... случайно переходит из состояния в состояние.
Пусть ξ(t) есть ее положение в момент t в результате цепочки случайных переходов ξ(0) - ξ(1) - ... - ξ(t) - ... ... (1)
Формально обозначим все возможные состояния целыми i = 0, ±1, ... Предположим, что при известном состоянии ξ(t) = k на следующем шаге система переходит в состояние ξ(t+1) = j с условной вероятностью
pkj = P(ξ(t+1) = j|ξ(t) = k) ... (2)
независимо от ее поведения в прошлом, точнее, независимо от цепочки переходов (1) до момента t:
P(ξ(t+1) = j|ξ(0) = i, ..., ξ(t) = k) = P(ξ(t+1) = j|ξ(t) = k) при всех t, k, j ... (3) - марковское свойство.
Такую вероятностную схему называют однородной цепью Маркова со счетным числом состояний - ее однородность состоит в том, что определенные в (2) переходные вероятности pkj, ∑j pkj = 1, k = 0, ±1, ..., не зависят от времени, т.е.
P(ξ(t+1) = j|ξ(t) = k) = Pij - матрица вероятностей перехода за один шаг не зависит от n. Ясно, что Pij - квадратная матрица с неотрицатель-ными элементами и единичными суммами по строкам. Такая матрица (конечная или бесконечная) называется стохастической матрицей. Любая стохастическая матрица может служить матрицей переходных вероятностей.
Дата добавления: 2017-01-16; просмотров: 2196;