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

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

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

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

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

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

на тему:

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

Выполнил:

студент 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);