Сетевое планирование и управление

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

НАБЕРЕЖНОЧЕЛНИНСКИЙ ИНСТИТУТ (ФИЛИАЛ) ФЕДЕРАЛЬНОГО

ГОСУДАРСТВЕННОГО АВТОНОМНОГО ОБРАЗОВАТЕЛЬНОГО УЧРЕЖДЕНИЯ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

Кафедра «Математические методы в экономике»

КУРСОВАЯ РАБОТА

На тему: «Сетевое планирование и управление»

Выполнил

Студент группы 4102195

Колчанова Г.Э

Проверили

Профессор, д.ф.-м.н.

А.Г. Исавнин

Ст. преподаватель

З.И. Чуева

Ст. преподаватель

Г.Р. Мингазова

ВВЕДЕНИЕ

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

Методы сетевого планирования и управления (СПУ), разработанные в начале 50-х годов, широко и успешно применяются для оптимизации планирования и управления сложными разветвленными комплексами работ, требующими участия большого числа исполнителей и затрат ограниченных ресурсов. Для оптимизации сложных сетей, состоящих из нескольких сотен работ, вместо ручного счета следует применять типовые макеты прикладных программ по СПУ, имеющиеся в составе математического обеспечения ЭВМ.

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

Анализ сетевой модели, представленной в графической или табличной (матричной) форме, позволяет, во-первых, более четко выявить взаимосвязи этапов реализации проекта и, во-вторых, определить наиболее оптимальных порядок выполнения этих этапов в целях, например, сокращения сроков выполнения всего комплекса работ.

Таким образом, методы сетевого моделирования относятся к методам принятия оптимальных решений.

1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

.1 Сетевое планирование и управление

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

Основная цель сетевого планирования - сокращение до минимума продолжительности проекта.

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

·    выявить перечень работ вашего проекта;

·        наглядно представить порядок их следования;

·        определить длительности каждой работы и всего проекта;

·        определить критические работы проекта и его критический путь;

·        определить резервы времени по каждой работе и т.д.

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

Наиболее распространенными направлениями применения сетевого планирования являются:

·    целевые научно-исследовательские и проектно-конструкторские разработки сложных объектов, машин и установок, в создании которых принимают участие многие предприятия и организации;

·        планирование и управление основной деятельностью разрабатывающих организаций;

·        планирование комплекса работ по подготовке и освоению производства новых видов промышленной продукции;

·        строительство и монтаж объектов промышленного, культурно-бытового и жилищного назначения;

·        реконструкция и ремонт действующих промышленных и других объектов;

·        планирование подготовки и переподготовки кадров, проверка исполнения принятых решений, организация комплексной проверки деятельности предприятий, объединений, строительно-монтажных организаций и учреждений.

1.2 Построение сетевых моделей

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

·  действительной, т.е. требующей затрат времени;

·        фиктивной, т.е. формально не требующей затрат времени.

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

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

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

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

Рисунок 1

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

Рисунок 2

Существуют два способа изображения событий и работ на сетевых графиках: граф «вершины-работы» и граф «вершины-события».

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

Рисунок 3

В сетях типа вершины-события все работы или действия представлены стрелками, а события - кружками (рисунок 4).

Рисунок 4

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

1.3 Правила построения сетевого графика

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

·  длина стрелки не зависит от времени выполнения работы;

·        стрелка может не быть прямолинейным отрезком;

·        для действительных работ используются сплошные, а для фиктивных работ - пунктирные стрелки; (рисунок 5)

Рисунок 5

·    каждая операция должна быть представлена только одной стрелкой;

·        между одними и теми же событиями не должно быть параллельных работ, т.е. работ с одинаковыми кодами; (рисунок 6)

Рисунок 6

·    следует избегать пересечения стрелок; (рисунок 7)

Рисунок 7

·    не должно быть стрелок, направленных справа налево; (рисунок 8)

Рисунок 8

·    номер начального события должен быть меньше номера конечного события; (рисунок 9)

Рисунок 9

·    не должно быть висячих событий (т.е. не имеющих предшествующих событий), кроме исходного события; (рисунок 10)

Рисунок 10

·    не должно быть тупиковых событий (т.е. не имеющих последующих событий), кроме завершающего события; (рисунок 11)

Рисунок 11

·    не должно быть циклов. (рисунок 12)

Рисунок 12

Исходные данные для построения сетевой модели могут задаваться различными способами, например:

·    описанием предполагаемого проекта. В этом случае необходимо самостоятельно разбить его на отдельные работы и установить их взаимные связи;

·        списком работ проекта. В этом случае необходимо проанализировать содержание работ и установить существующие между ними связи;

·        списком работ проекта с указанием их упорядочения. В этом случае необходимо только отобразить работы на сетевом графике.

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

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

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

Рисунок 13

1.4 Временные характеристики сетевых графиков

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

Расчет сетевой модели начинают с временных параметров событий, которые вписывают непосредственно в вершины сетевого графика (рисунок 14).

Рисунок 14

Характеристики событий:

. Ранний срок наступления событий:

при этом , {i} - множество предшествующих событий.

,

где  - любой путь, предшествующий j-ому событию.

Ранние сроки совершения событий вычисляются по сетевому графику слева направо по прямому ходу.

. Поздний срок совершения событий:

,

{j} - множество последующих событий.

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

. Резерв времени

Характеристики работ:

Временные параметры работ определяются на основе ранних и поздних сроков событий:

1. - ранний срок начала работы;

. - ранний срок окончания работы;

.- поздний срок окончания работы;

. - поздний срок начала работы;

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

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

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

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

.  - резерв времени пути, все резервы времени неотрицательны, вместо отрицательных величин используется ноль.

Проверка резервов

, если начальное событие iпринадлежит критическому пути;

, если завершающее событие j принадлежит критическому пути

, если событие (i,j) принадлежит критическому пути.

.5 Сетевое планирование в условиях неопределенности

При выполнении комплекса работ на сроки выполнения работы и на их последовательность могут влиять различные факторы. В этом случае комплекс работ представляет собой стохастическую сеть с вероятными числовыми характеристиками с не до конца определенной топологией сети.

При определении временных параметров сетевого графика до сих пор предполагалось, что время выполнения каждой работы точно известно. Допустим, продолжительность работы t(i,j) заранее неизвестна, т.е. является случайной величиной и задается законом распределения. Следовательно, характеризуется своими числовыми характеристиками:

 - среднее значение или математическое ожидание;

 - дисперсия (мера отклонения от среднего значения).

В этих условиях полагаем:

·  Закон распределения непрерывный;

·        Закон распределения является унимодальной функцией;

·        Закон распределения имеет две точки пересечения с осью абсцисс;

·        Закон распределения обладает положительной асимметрией.

Этим свойствам удовлетворяет β-распределение.

Для определения характеристик  и  на основе экспертных оценок задают величины

.  - оптимистическая оценка;

.  - пессимистическая оценка;

.  - наиболее вероятная оценка.

В этом случае для β-распределения можно получить соотношения

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

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

=

В рамках планирования в условиях неопределенности могут решаться две взаимообратные задачи:

. Оценка вероятности того, что срок выполнения проекта  не превзойдет заданного директивного срока Т находится по формуле

Ф(z)=

. Обратная задача: определение максимального срока выполнения проекта Т, который возможен с заданной вероятностью β.

Т=

 - нормированное отклонение случайной величины, определяемой функцией Лапласа

1.6 Оптимизация сетевого графика по схеме «Время-стоимость»

Для оптимизации сетевого графика используется частная оптимизация (уменьшение стоимости проекта). При использовании метода «время-стоимость» предполагают, что уменьшение продолжительности работ пропорционально возрастанию ее стоимости. Каждая работа (i,j) характеризуется продолжительностью t(i,j), которая может находиться в пределах

a(i,j) ≤ t(i,j)≤ b(i,j)

где a(i,j) - минимальная возможная продолжительность работы (i,j);

t(i,j) - наиболее вероятная продолжительность работы (i,j);

b(i,j) - максимальная продолжительность работы (i,j).

При этом стоимость С(i,j) работы (i,j) заключена в границах:

С_max - минимальная стоимость работы, оптимистическая оценка стоимости работы, стоимость при минимальных сроках выполнения работы;

С_min - максимальная стоимость работы, пессимистическая оценка стоимости работы, стоимость при максимальных сроках выполнения работы.

Далее при оптимизации вычисляют:

h(i,j) - коэффициент увеличения затрат от ускорения работы (i,j);

h(i,j) =

C(i,j) - наиболее вероятная стоимость проекта

C(i,j) = С_min+(b-t(i,j))*h(i,j)

Таким образом увеличение продолжительности работ может привести к уменьшению Стоимости проекта. Но продолжительность каждой работы целесообразно увеличить на такую величину. Что бы не изменить ранние сроки наступления всех событий сети что означает с одной стороны - продолжительность каждой работы можно увеличить на свободный резерв времени. С другой - эта продолжительность не должна превышать предельно допустимую Продолжительность b(i,j).

Оптимальную Продолжительность работы можно найти на основе соотношения

 или

,

где .

В этом случае стоимость выполнения работы находят по формуле

Оптимизированный проект имеет суммарную стоимость

2. ПРАКТИЧЕСКАЯ ЧАСТЬ

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

Сетевой график:

                                            4                          6                           5

                                                            5                    7

                       3                10          8                                                

      4                          7                                       7          4                                      10

                                                    2                         1                          1

Рисунок 15

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

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

I                      II                     III                    IV                    V                     VI                    VII

Рисунок 16

Теперь пронумеруем события в соответствии с их положением в системе упорядочивания. И получим следующий график

Рисунок 17

2.2 Определение критического пути

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

Метод простого перебора:

Определим все полные пути сетевого графика, рассчитаем их длительность и выберем путь с максимальной длительностью.

. 0 - 5 - 8 - 9                                                                                    /13

. 0 - 4 - 5 - 8 - 9                                                                     /14

. 0 - 1 - 2 - 4 - 5 - 8 - 9                                                          /29

. 0 - 1 - 2 - 3 - 5 - 8 - 9                                                          /29

. 0 - 1 - 2 - 3 - 3 - 8 - 9                                                          /30

. 0 - 1 - 2 - 3 - 6 - 9                                                                         /22

. 0 - 4 - 7 - 9                                                                                   /17

. 0 - 4 - 5 - 7 - 9                                                                     /17

. 0 - 5 - 7 - 9                                                                                    /13

. 0 - 1 - 2 - 4 - 5 - 7 - 9                                                          /29

. 0 - 1 - 2 - 3 - 7 - 9                                                                         /24

. 0 - 1 - 2 - 4 - 7 - 9                                                                        /32

. 0 - 1 - 2 - 3 - 5 - 7 - 9                                                          /29

Графический метод:

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

Рисунок 18

На графике видно, что путь 12 находится дальше всех от нуля по оси ОХ и является критическим путем 0 - 1 - 2 - 4 - 7 - 9.

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

2.3 Временные характеристики сетевого графика

Характеристики работ

Результаты расчетов временных характеристик работ оформим в виде таблицы. (таблица 1)

сетевой неопределенность график критический

Таблица 1

Резерв времени пути:

R (1) = 32-13=19                             R (10) = 32-29=3(2) = 32-14=18                                 R (11) = 32-24=8(3) = 32-29=3                                   R (12) = 32-32=0(4) = 32-29=3                                      R (13) = 32-29=3

R (5) = 32-30=2(6) = 32-22=10(7) = 32-17=15 (8) = 32-17=15

R (9) = 32-13=19

2.4 Сетевое планирование в условиях неопределенности

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

Таблица 2

На основании полученных результатов можно рассчитать среднее значение и дисперсию пути

 2,2+1,6+10,2=14

 0,11+0,11+0,11=0,33

 2,2+1,6+1,6+10,2=15,6

0,11+0,11+0,11+0,11=0,44

4,2+3,2+10,2+1,6+1,6+10,2=31

 0,11+0,11+0,11+0,11+0,11+,011=0,66

4,2+3,2+4,2+7,2+1,6+10,2=30,6

0,11+0,11+0,11+0,11+0,11+0,11=0,66

4,2+3,2+4,2+6,2+3,2+10,2=31,2

0,11+0,11+0,11+0,11+0,11+0,11=0,66

4,2+3,2+4,2+6,2+5,2=23

0,11+0,11+0,11+0,11+0,11=0,55

2,2+8,2+7,2=17,6

0,11+0,11+0,11=0,33

2,2+1,6+4,2+7,2=15,2

0,11+0,11+0,11+0,11=0,44

2,2+4,2+7,2=13,6

0,11+0,11+0,11=0,33

4,2+3,2+10,2+1,6+4,2+7,2=30,6

0,11+0,11+0,11+0,11+0,11+0,11=0,66

4,2+3,2+4,2+6,2+7,9=25,7

0,11+0,11+0,11+0,11+0,11=0,55

4,2+3,2+10,2+8,2+7,2=33

0,11+0,11+0,11+0,11+0,11=0,55

4,2+3,2+4,2+7,2+4,2+7,2=30,2

0,11+0,11+0,11+0,11+,011+0,11=0,66

Рассчитаем оценку вероятности того, что срок выполнения проекта =32 не превзойдет заданного директивного срока Т=40.

Определим максимальный срок выполнения проекта Т, который возможен с заданной вероятностью β=0,372

=1,14

Т=33+1,14*=33+1,14*0,81=33+0,92=33,92.

2.5 Оптимизация сетевого графика по схеме «Время-стоимость»

Рассчитаем наиболее вероятную стоимость проекта, результаты оформим в виде таблицы. (таблица 3)

Таблица 3

Рассчитаем оптимальную продолжительность работы, результаты оформим в виде таблицы. (таблица 4)

Таблица 4

Рассчитаем стоимость выполнения работ, результаты оформим в виде таблицы. (таблица 5)

Таблица 5

Оптимизированный проект имеет суммарную стоимость:

=7,5+12+14+12+11+17+14+12+14+17+7,5+13+8+10,5+13+13+11=206,5

ЗАКЛЮЧЕНИЕ

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

Современное сетевое планирование начинается с разбиения программы работ на операции.

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

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1.   Динамическое программирование и уравнения в частных производных. Р. Беллман, Э. Энджел. М., 2000г;

2.      Линейное программирование. Лунгу К.Н. -М., 2005г.;

.        Математические методы в экономике. Замков О.О., Толстопятенко А.В., Черемных Ю.Н. -М., 2001г.;

.        Математическое моделирование экономики: Учебно-практическое пособие/ Малыхин В. И. -М., 2007г.