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

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

При построении сетевого графика необходимо соблюдать ряд правил.

1. 
   Сеть строится слева направо, от начального события к конечному событию.
   
2. 
   Длина и наклон стрелок, с помощью которых изображаются работы, значения не имеют, но все они должны иметь одно направление - слева направо, от предшествующего события к последующему.
   
3. 
   Сетевой график - это плоский граф, поэтому стрелки в нем не должны пересекаться. Избежать пересечения стрелок можно путем смещения событий, изображения стрелок в виде ломаной линии, введения фиктивных событий и работ.
   

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

4. 
   Пара событий может быть соединена только одной работой, т.е. сетевой график не может быть мультиграфом. Для устранения ситуации, когда пара событий соединяется более чем одной работой (рис.2а), вводится дополнительное событие и фиктивная работа (рис.2б).
   

5. В сети не должно быть (кроме начального) «хвостовых» событий, т.е. событий, в которые не входит ни одна работа (событие 3 - на рис. 3а). Здесь работы, предшествующие событию 3, не предусмотрены. Поэтому событие 3 не может свершиться, а, следовательно, не может быть выполнена и следующая за ним работа (3,5). Обнаружив в сети такие события, необходимо определить исполнителей предшествующих им работ и включить эти работы в сеть.

1 3 7 1 3 7

4 6 4 6
а Рис.3 б

6. В сети не должно быть (кроме конечного) «тупиковых» событий, т.е. событий из которых не выходит ни одна работа (рис.3б). Здесь либо работа (2,3) не нужна и ее необходимо удалить, либо не замечена необходимость определенной работы, следующей за событием 3 для свершения какого-либо последующего события. В таких случаях необходимо тщательное изучение взаимосвязей событий и работ для исправления возникшего недоразумения.

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



3 0 3 6



2 5 2 5
a) Рис.4 б)

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

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

1 3 4 4 1 4

С Ф

А Б Д

а) б)

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

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

D D

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

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

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

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

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

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

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

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

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

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

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

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

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

,

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

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

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

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

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

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 в наиболее ранние сроки.

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

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

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

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

Для отражения временных параметров событий на сетевом графике применяется четырехсекторный способ фиксации параметров. Круг (рис.7), обозначающий событие, разбивается на четыре сектора.

R(j)
L(j) j E(j)

i₁,i₂,...

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

1. 
   Рассчитываются наиболее ранние сроки наступления событий. Полученные величины записываются в правый сектор соответствующих событий, а в нижний - номера предшествующих событий, через которые к данному событию идет путь максимальной продолжительности. Количество таких номеров соответствует количеству предшествующих событий, лежащих на путях максимальной продолжительности.
   
2. 
   Рассчитываются наиболее поздние сроки наступления событий, эти величины записываются в левый сектор.
   
3. 
   Рассчитываются резервы времени событий, эти величины записываются в верхний сектор.
   

Значения всех трех резервов времени для любой работы соотносятся между собой следующим образом:

полный резерв свободный резерв независимый резерв