Контрольная работа по "Экономико-математическому моделированию"

Фиктивные работы и события  необходимо вводить и в ряде других случаев. Один из них - отражение зависимости  событий, не связанных с реальными  работами. Например, работы А и Б (рис.5а) могут выполняться независимо друг от друга, но по условиям производства работа Б не может начаться раньше, чем окончится работа А. Это обстоятельство требует введения фиктивной работы С.

Другой случай - неполная зависимость работ. Например, работа С требует для своего начала завершения работ А и Б, но работа Д связана только с работой Б, а от работы А не зависит. Тогда требуется введение фиктивной работы Ф и фиктивного события , как показано на рис 5б.

 

                                        Б                                                   А                С           

                 1               3               4  4                               1                           4         

                                       С                                                                     Ф                      

                        А                                                                       Б                 Д                         

      2                              5                                2                 3                 5                               

 

а)                           б)

                                                      Рис.5                     

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

Пример 10.1. Для освоения курса исследования операций студент должен изучить следующие дисциплины: 1) вычислительную математику (два семестра - ВЫЧ1 и ВЫЧ2), 2) статистику (три семестра - СТАТ1, СТАТ2, СТАТ3), 3) линейное программирование (один семестр - ЛП), 4) нелинейное программирование (один семестр - НП), 5) стохастическое программирование (один семестр - СП). При этом ясно, что к изучению вычислительной математики во втором семестре (ВЫЧ2) можно приступить только после освоения материала семестра 1 (ВЫЧ1), к изучению СТАТ3 - после освоения СТАТ2, к изучению СТАТ2 - после освоения СТАТ1 и ВЫЧ2, к изучению СТАТ1 - после освоения ВЫЧ1. Для изучения линейного программирования (ЛП) не требуется знания никаких предварительных дисциплин, для изучения нелинейного программирования (НП) требуется знание ВЫЧ2 и ЛП, для изучения стохастического программирования (СП) - знание ВЫЧ2, СТАТ2 и ЛП.

Сетевой график этой учебной  программы изображен на рис. 6. На всю эту учебную программу студенту потребуется самое меньшее 5 семестров, если он последовательно, семестр за семестром, пройдет ВЫЧ1, СТАТ1, СТАТ2, СТАТ3 и СП. Любая задержка в изучении указанной последовательности дисциплин приведет к такой же по времени задержке окончания всего курса обучения.

 

 

 

                                                                                                           D- фиктивная дуга

                                  ЛП                  9                      НП               

                                                   D             D

          а                 b                  c                     d               e                f               h               

                ВЫЧ1         ВЫЧ2        D                СТАТ2    СТАТ3      СП          

 

                                                     СТАТ1

 

Рис.6

 

4. Упорядочение сетевого графика.

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

Алгоритм нумерации событий  (нумерация событий осуществляется после построения сети).

Начальному событию присваивается  номер 1. Затем вычеркиваются все выходящие из него работы (стрелки), после чего несколько событий окажутся без входящих работ. Этим событиям присваиваются номера 2,3,...,N1 (события первого ранга). Далее вычеркиваются все работы, выходящие из событий первого ранга. Событиям, оставшимся без входящих работ, присваиваются номера N1+1,N1+2,...,N1+N2 (события второго ранга) и т.д. до конечного события.

События одного ранга нумеруют очередными номерами в произвольном порядке.

5. Критический путь

Сетевая модель сама по себе не может служить средством управления комплексом работ. Для управления комплексом работ с помощью сетевого графика необходимо располагать количественными оценками элементов сети - параметрами. Рассмотрим временн е параметры сетевых графиков, включающие параметры событий и работ.  Будем считать, что для каждой работы (i, j) задано время (продолжительность) ее выполнения - .

При расчете параметров сети используется понятие пути. Последовательность работ, приводящая от одного события к другому и в которой каждая работа встречается не более одного раза, составляет путь. Полный путь - это путь от начального события до конечного. Продолжительность пути определяется суммой продолжительностей составляющих его работ. Полный путь, имеющий максимальную длину, называют критическим и обозначают L_кр, а его продолжительность t_кр. Работы, принадлежащие критическому пути, называются критическим. Критический путь определяет общую продолжительность всего комплекса работ в целом. Изменение продолжительности работ, лежащих на критическом пути, может привести к сокращению или удлинению срока наступления конечного события, т.е. даты достижения конечной цели, определенной при планировании. Сетевой график может иметь несколько критических путей.

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

.

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

  а -критический путь (это будет показано ниже).

В связи с тем, что  все ненапряженные пути имеют  определенный резерв времени, события и работы, лежащие на таком пути, также имеют определенные резервы времени.

 

 

 

6. Временные параметры событий

К временным параметрам событий относятся: наиболее ранний срок наступления события, наиболее поздний срок наступления события и резерв времени наступления события.

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

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

,

где max берется по всем вершинам i, предшествующим вершине j.

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

  ,  

где min берётся по всем вершинам , следующим за вершиной .

Разность между наиболее поздним  и наиболее ранним сроками свершения  события составляет резерв времени  события  :

 

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

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

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

 

7. Временные параметры  работ

Полный резерв времени. Рассмотрим некоторую работу (i,j). Какое максимальное количество времени можно выделить для ее выполнения без задержки своевременного окончания выполнения всего проекта? Работа (i,j) может начаться не ранее E(i) и должна закончиться не позднее L(j). Таким образом, без задержки окончания проекта на выполнение работы (i,j) можно выделить не более L(j) - E(i) единиц времени. Следовательно, при выполнении работы (шбо) можно допустить максимальную задержку L(j) - E(i) - t(i,j) - это максимально возможное увеличение продолжительности работы (i,j) без увеличения времени выполнения всего проекта. Величина

L(j) - E(i) - t(i,j)

называется полным резервом времени  работы (i,j).

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

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

Свободный резерв времени. Какое  максимальное количество времени может быть выделено для выполнения работы (i,j) без введения дополнительных временных ограничений на последующие работы? Для выполнения этого условия работа (i,j) должна быть закончена к моменту времени E(j). Поскольку работа (i,j) может начаться не ранее E(i), на ее выполнение без введения дополнительных временных ограничений на последующие работы может быть выделено не более E(j) - E(i) единиц времени. Величина

E(j) - E(i) - t(i,j)

называется свободным резервом времени работы (i,j). Свободный резерв времени равен максимальной задержке выполнения работы (i,j), не влияющий на выполнение последующих работ, т.е. это максимально возможное увеличение продолжительности работы (i,j), при котором можно начать все работы, выходящие из j в наиболее ранние сроки.

Свободным резервом времени можно  пользоваться для предотвращения случайностей, которые могут возникнуть в ходе выполнения работ. Если планировать выполнение работ по ранним срокам их начала и окончания, то всегда будет возможность при необходимости перейти на поздние сроки начала и окончания работ.

Независимый резерв времени. Какое максимальное количество времени может быть выделено для выполнения работы (i,j) без введения дополнительных временных ограничений на любую работу проекта? Для выполнения этого условия работа (i,j) должна начаться как можно позднее (т.е. в момент времени L(i)) и закончиться как можно раньше (т.е. в момент времени E(j)). Следовательно, на выполнение работы (i,j) в этом случае можно выделить не более E(j) - L(i) единиц времени. Величина

E(j) - L(i) - t(i,j)

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

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