Оптимизация модели сетевого планирования и управления

Федеральное Государственное образовательное  учреждение высшего профессионального  образования

Пермская  государственная сельскохозяйственная академия имени академика Д.Н.Прянишникова 
 
 
 
 

Кафедра Информационных технологий и автоматизированного  проектирования

Курсовая  работа

по дисциплине: «Методы оптимизации»

на тему:

«Оптимизация модели сетевого планирования и управления». 
 
 
 
 
 
 
 
 

Выполнил:

студент 3 курса очного отделения

по  специальности: 080801 «Прикладная информатика (в экономике)»

///

Проверил:

старший преподаватель Гревцев А.М. 
 
 
 

Пермь-2009

 

         Содержание

          Введение…………..………………………………………………………..3

1. Теоретические основы модели сетевого планирования и  управления. Основные понятия……………………………………….5

          1.1.Задача о строительстве объекта……………………………………..15

2.   Сетевое планирование  в условиях неопределенности……………21
1. Задача……………………………………………………………….24

  3. Оптимизация сетевого графика методом "время — стоимость"….28

Заключение………………………………………………………………..39

Список  литературы……………………………………………………….40 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

           Введение

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

       Модели  сетевого планирования и управления (модели СПУ) предназначены для планирования и управления сложными комплексами  работ (проектами), направленными на достижение определенной цели в заданные сроки (строительство, разработка и производство сложных объектов и др.).

       За  рубежом система СПУ известна как система РЕRТ (Рrоgram Еvaluation and Review Тechnique - метод анализа и оценки программ) или СРМ (Critical Рath Мethod - метод критического пути).

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

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

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

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

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

       Для отображения процесса выполнения проекта и управления им в системах СПУ используется сетевая модель. 
 
 
 
 
 
 
 
 
 
 

     Теоретические основы модели сетевого планирования и  управления. Основные понятия.

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

принятия  оптимальных решений.

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

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

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

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

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

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

     Сеть  — это ориентированный конечный связный граф, имеющий начальную вершину (источник) и конечную вершину (сток). Таким образом, сетевая модель представляет собой граф вида «сеть».

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

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

             Она может быть представлена в виде графика или таблицы. Основные понятия СМ: событие, работа и путь. На рисунке 1 графически представлена СМ, состоящая из 11 событий и 16 работ, продолжительность выполнения которых указана над работами.

             Работа характеризует материальное действие, требующее использования ресурсов, или логическое, требующее лишь взаимосвязи событий. При графическом представлении работа изображается стрелкой, которая соединяет два события. Она обозначается парой заключенных в скобки чисел (i,j), где i — номер события, из которого работа выходит, а j — номер события, в которое она входит. Работа не может начаться раньше, чем свершится событие, из которого она выходит. Каждая работа имеет определенную продолжительность t(i,j). Например, запись t (2,5) = 4 означает, что работа (2,5) имеет продолжительность 4 единицы. К работам относятся также такие процессы, которые не требуют ни ресурсов, ни времени выполнения. Они заключаются в установлении логической взаимосвязи работ и показывают, что одна из них непосредственно зависит от другой; такие работы называются фиктивными и на графике изображаются пунктирными стрелками (см. работу (6,9)). 
 

                 1

                  

                   5 6

               5 4

                  9

                

                              3                  6 3

                5

                    0

               4 

                                         

                                         Рисунок 1. Сетевая модель 

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

           Путь — это цепочка следующих друг за другом работ, соединяющих начальную и конечную вершины, например, в приведенной выше модели путями являются L1 = (1, 2, 3, 7, 10, 11), L2 — (1, 2, 4, 6, 11) и др. Продолжительность пути определяется суммой продолжительностей составляющих его работ.

            Критический путь  - это путь, имеющий максимальную длину, обозначается LKp, а его продолжительность — tкр. Работы, принадлежащие критическому пути, называются критическими. Их несвоевременное выполнение ведет к срыву сроков всего комплекса работ.[1]

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

• длина стрелки не зависит от времени выполнения работы (рисунок 2):

            

                                      15

                                                           4

                                                        1                                 … 

                                                                     Рисунок  2 

       

• стрелка не обязательно должна представлять прямолинейный отрезок (рисунок 3);

       

                                

         

              

                  Рисунок 3  

       

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

       

       

       

       

                                                    

                                                      Рисунок 4

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

       событиями (рисунок 5), во избежание такой ситуации используют фиктивные работы;

       

       

                                           
 

                                                        Рисунок 5 

       

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

       

       

       

         

                                                        Рисунок  6 

       

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

       

       

       

       

       

       Рисунок 7

        

• не должно быть висячих событий, кроме исходного (рисунок 8);

       

       

       

         

                                                               Рисунок 8 

       

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

       

       

       

         

                                                       Рисунок  9 

       

• не должно быть циклов (рисунок 10);

       

       

         

                

                                                      Рисунок 10                                

• номер начального события должен быть меньше номера конечного события (рисунок 11). [2]

 

                                                              Рисунок 11

При невыполнении последнего требования необходимо использовать алгоритм перенумерации событий, который заключается в следующем: нумерация событий начинается с исходного события, которому присваивается № 1; из исходного события вычеркивают все исходящие из него работы (стрелки), и на оставшейся сети находят событие, в которое не входит ни одна работа, ему и присваивают № 2; затем вычеркивают работы, выходящие из события № 2, и вновь находят событие, в которое не входит ни одна работа, и ему присваивают № 3, и так продолжается до завершающего события, номер которого должен быть равен количеству событий в сетевом графике; если при очередном вычеркивании работ одновременно несколько событий не имеют входящих в них работ, то их нумеруют очередными номерами в произвольном порядке.[1]

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

• какие работы необходимо завершить непосредственно перед началом рассматриваемой работы?
• какие работы должны непосредственно следовать после завершения данной работы?
• какие операции могут выполняться одновременно  рассматриваемой работой? [2]

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

             Для событий рассчитывают три характеристики: ранний и поздний срок совершения события, а также его резерв.

             Ранний срок свершения события определяется величиной наиболее длительного отрезка пути от исходного до рассматриваемого события, причем tp (1) = 0, a tp (N) = tKp (L):  

                                  tр (j) = {tp (i)+t (i,j)}; j=                                         (1)

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

 

                              tп(i) =min {tп  (j) — t (i,j)}; i= .                                    (2) 

               Этот показатель определяется «обратным ходом», начиная с завершающего события, с учетом соотношения tп (N) = tр (N).

               Все события, за исключением событий, принадлежащих критическому пути, имеют резерв R(i): 

                                               R(i) = tп(i) - tр(i);                                                 (3) 

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

               Для всех работ (i,j) на основе ранних и поздних сроков свершения

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

              Ранний срок начала:

 

                                                     tрн(i,j) = tр(i);                                                      (4)

 

              Ранний срок окончания : 

                                                  tро(i,j) = tр(i,j)+t(i,j);                                            (5) 

              Поздний срок окончания: 

                                                     tпо(i,j) = tп(j) ;                                                  (6) 

              Поздний срок начала: 

                                               tпн(i,j) = tп(j) - t(i,j);                                                 (7) 

              Полный резерв времени: 

                                             Rп(i,j) = tп(j) – tр(i) – t(i,j);                                        (8) 

              Полный резерв времени показывает, на сколько можно увеличить время выполнения конкретной работы при условии, что срок выполнения всего комплекса работ не изменится.[1]

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

                                 Rс(i,j) =  tр(j) – tр(i) – t(i,j) = tр(j) – tро(i,j).[3]                     (9) 

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

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

                  Кн (i,j) =                             (10) 

              где  - продолжительность максимального пути, проходящего через работу (i,j);

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

               t''(Lmax) – длительность отрезка пути максимальной продолжительности, проходящего через работу (i,j) и не совпадающего с критическим путем;

              t’’кр   - продолжительность участка критического пути, не совпадающего с максимальным из путей, проходящих через работу (i,j)[4] 

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

        • напряженные (Kн(i,j) > 0,8);

        • подкритические (0,6 < Kн(i,j) < 0,8);

        • резервные (Kн(i,j) < 0,6).

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

       Рассмотрим задачу

    Организационно-технологическая модель осуществления строительства объекта.

    Задание: по данным таблицы 1 требуется:

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

• можно ли отложить выполнение работ K,U   без отсрочки завершения проекта в целом?
• На сколько недель можно отложить выполнение работы D без отсрочки завершения проекта в целом?
• за счет каких резервных работ в основном возможна оптимизация СМ?
• как повлияет на ход выполнения проекта задержка работы О на 37 недель?

    Таблица 1