[pic]
Кафедра прикладной математики
Курсовая работа по курсу:
“Дискретная математика”
по теме:
“Сетевые методы в планировании”
Группа: ДИ 102
Студент: Шеломанов Р.Б.
Руководитель: Алферова З.В.
Москва 1998
Содеражание
Введение 3
Часть 1 Теоретическая часть к курсовому проекту 4
Глава 1 Теория графов 4
Глава 2 Календарное планирование сетевыми методами 8
Часть 2 Практическая реализация курсового проекта 13
Задание 13
Решение 14
Заключение 20
Список литературы 21
Введение
Для иллюстраций условий и решений многих задач люди пользуются графиками.
По своей сути графики являются набором из множества точек и отрезков прямых
соединяющих эти точки. Возникает вопрос: подчиняются ли графики каким-либо
законам и обладают ли они какими-нибудь свойствами? Этот вопрос был
поставлен Д. Кенигом, который впервые объединил все схематические
изображения, состоящие из совокупности точек и линий, общим термином “граф”
и рассмотрел граф как самостоятельный математический объект. Теория графов
нашла свое применение в решении целого ряда экономических задач. Эту
область приложения теории графов можно назвать: “Календарное планирование
программ сетевыми методами”. Изучение именно этой области является основной
целью моего курсового проекта. Программа определяет совокупность взаимосвязанных операций которые
необходимо выполнить в определенном порядке, чтобы достигнуть поставленной
в программе цели. Операции логически упорядочены в том смысле, что одни
операции нельзя начать, прежде чем не будут завершены другие. Операция
программы обычно рассматривается как работа, для выполнения которой
требуются траты времени и ресурсов. Как правило, совокупность операций
программы не повторяется. До появления сетевых методов календарное
планирование программ (т. е. планирование во времени) осуществлялось в
небольшом объеме. Наиболее известным средством такого планирования был
ленточный (линейный) график Ганта, задававший сроки начала и окончания
каждой операции на горизонтальной шкале времени. Его недостаток заключается
в том, что он не позволял восстановить зависимости между различными
операциями (определяющие в значительной мере темпы реализации программы). В
связи с повышением сложности современных программ потребовалась разработка
более четких и эффективных методов планирования, обеспечивающих оптимизацию
всего процесса осуществления программы. При этом эффективность
интерпретируется как минимизация продолжительности выполнения программы c
учетом экономических факторов использования имеющихся ресурсов. Организационное управление программами стало новой областью теоретических
и прикладных исследований благодаря разработке двух аналитических методов
структурного и календарного планирования, а также оперативного управления
программами. Эти методы, разработанные почти одновременно в 1957-1958 гг.
двумя различными группами, получили названия метод критического пути (МКП)
и метод оценки и пересмотра программ (ПЕРТ). Метод критического пути был предложен фирмой Е. I. du Роnt de Nemours &
Company для управления программами строительства, а затем был развит к
обобщен фирмой Маuсhlу Associates. Метод ПЕРТ разработан консультативной
фирмой по заказу военно-морского министерства США для календарного
планирования научно-исследовательских и опытно-конструкторских работ
программы создания ракет «Поларис». В методах ПЕРТ и МКП основное внимание уделяется временному аспекту
планов в том смысле, что оба метода в конечном счете определяют календарный
план программы. Хотя эти методы были разработаны независимо, они отличаются
поразительным сходством. Пожалуй, самым существенным различием
первоначально было то, что в методе МКП оценки продолжительности операций
предполагались детерминированными величинами, а в метод ПЕРТ — случайными.
В настоящее время оба метода составляю единый метод сетевого планирования и
управления (СПУ) программами.
Часть 1
Теоретическая часть к курсовому проекту
Глава1
Теория графов
Понятие графа
Графом G(X,U) называется совокупность двух объектов некоторого множества X и отображения этого множества в себя Г.
При геометрическом представлении графа элементы множества Х изображаются точками плоскости и называются вершинами графа. Линии, соединяющие любые пары точек x и y, из которых у является отображением х, называются дугами графа. Дуги графа имеют направление, обозначаемое стрелкой, которая направлена острием от элемента х к его отображению у.
Вершины и линии графа
Две вершины А и В являются граничными вершинами дуги, если А- начало дуги, а В ее конец.
Смежными называются различные дуги, имеющие общую граничную точку. Две вершины х и у смежны, если они различны и существует дуга, идущая от одной из них к другой .
Вершина называется изолированной, если она не соединена дугами с другими вершинами графа.
Если дуга U исходит из вершины х или заходит в х, то дуга U называется инцидентной вершине х, а вершины х инцидентной дуге U. Общее число дуг, инцидентной вершине х, являются степенью вершины х Р(х). Вершины, степень которых Р(х)>2, называются узлом, а со степенью Р(х)= 0. Величина L(j )-E(i)-d ij
называется полным резервом времени операции ( i , j ). Какое
максимальное количество времени может быть выделено для выполнения
операции (i ,j ) без введения дополнительных временных ограничений на
последующие операции? Для соблюдения этого условия операция ( i , j )
должна быть закончена к моменту времени Е ( j ). Поскольку операция ( i ,
j ) может начаться не ранее E ( i ), на ее выполнение без введения
дополнительных ограничений на последующие операции можно выделять не более
E( j )-E(i ) единиц времени. Величина E ( j ) -E ( i ) - d ij
Называется свободным резервом времени операции ( i ,j ). Свободный резерв
времени равен максимальной задержке выполнения операции ( i , j ), не
влияющей на выполнение последующих операций. Какое максимальное количество
времени может быть выделено для выполнения операции ( i,j ) без введения
дополнительных временных ограничений на любую операцию проекта? Для
выполнения этого условия операция ( i,j ) должна начаться в момент времени
L(i ) и закончиться к моменту времени E(j ), cледовательно, на выполнение
операции ( i,j ) в этом случае можно выделить не более Е ( J ) -L(i)
единиц времени. Величина Е( j )- L (i )-d ij называется независимым
резервом Времени операции (i ,j ). Независимый резерв времени равен
максимальной задержке, которую можно допустить при выполнении операции ( i
,j ) без введения дополнительных временных ограничений на любую другую
операцию проекта. Отрицательное значение независимого резерва означает,
что любая задержка с выполнением операции приведет к дополнительным
ограничениям на выполнение других операций.
Построение календарного графика и распределение ресурсов
Конечным результатом выполняемых на сетевой модели расчетов является
календарный график (план). Этот график легко преобразуется в реальную шкалу
времени, удобную для реализации процесса выполнения программы. При построении календарного графика необходимо учитывать наличие
ресурсов, так как одновременное (параллельное) выполнение некоторых
операций из-за ограничений, связанных с рабочей силой, оборудованием и
другими видами ресурсов, может оказаться невозможным. Именно в этом
отношении представляют ценность резервы времени некритических операций.
Сдвигая некритическую операцию в том или ином направлении, но в пределах ее
полного резерва времени, можно добиться снижения максимальной потребности в
ресурсах. Однако даже при отсутствии ограничений на ресурсы полные резервы
времени обычно используются для вырабатывания потребностей в ресурсах на
протяжении всего срока реализации программы. По существу, это означает, что
программу удается выполнить более или менее постоянным составом рабочей
силы по сравнению со случаем, когда потребности в рабочей силе (и др.
ресурсах) резко меняются при переходе от одного интервала времени к
другому. Для построения календарного графика прежде всего определяются календарные
сроки выполнения критических операций. Далее рассматриваются некритические
операция и указываются их ранние сроки начала Е и поздние сроки окончания
L. Критические операции изображаются сплошными линиями. Отрезки времени, в
пределах которых могут выполняться некритические операции, наносятся
пунктирными линиями, показывающими, что календарные сроки этих операций
можно выбрать в указанных пределах при условии сохранения отношений
следования. Фиктивная операция не требует затрат времени и поэтому
изображается на графике вертикальным отрезком. Числа, проставленные над
некритическими операциями, соответствуют их продолжительностям.
Роль полных и свободных резервов времени при выборе календарных сроков
выполнения некритических операций объясняется двумя общими правилами.
1. Если полный резерв равен свободному, то календарные сроки
некритической операции можно выбрать в любой точке между ее ранним началом
и поздним окончанием. 2. Если свободный резерв меньше полного, то срок начала некритической
операции можно сдвинуть по отношению к ее раннему сроку начала не более чем
на величину свободного резерва, не влияя при этом на выбор календарных
сроков непосредственно следующих операций. 3. Если свободный резерв времени операции больше полного, то это служит
признаком того, что окончательные календарные сроки такой операции нельзя
фиксировать, не проследив сначала, как это повлияет на сроки начала
непосредственно следующих операций. Столь ценную информацию можно получить
на основе расчетов сетевой модели. Теперь, после изучения теории сетевого планирования, я перехожу к
практической части курсового проекта.
Часть 2
Практическая реализация курсового проекта
Задание
Вариант № 24
Построить сетевую модель и календарный график по указанным в таблице данным.
|Номера |Каким |Продолжи-тел|Потребность в |
|работ |работам |ьность работ|трудресурсах |
|(опера-|предше-ству| | |
|ций) |ет | | |
|1 |2 |9 |2 |
|2 |3, 4, 5 |8 |1 |
|3 |6 |8 |9 |
|4 |8 |9 |5 |
|5 |7 |13 |1 |
|6 |7 |12 |4 |
|7 |10, 12 |14 |4 |
|8 |9, 10 |12 |3 |
|9 |10, 12 |14 |8 |
|10 |11 |6 |4 |
|11 |14 |9 |1 |
|12 |13, 17 |11 |3 |
|13 |15 |16 |6 |
|14 |15 |5 |1 |
|15 |16 |7 |5 |
|16 |18 |9 |1 |
|17 |18 |13 |2 |
|18 | |9 |3 |
Решение
На основе данных и предписаний указанных выше выполняем первый этап
проекта, тоесть строим сетевой график проекта (рис 4.1). События
пронумерованы в кружках, линии со стрелками - работы (далее вместо слова “
работы” я буду употреблять “операции”). Рядом со стрелками операций стоят
их номера и ( с черточками над и под числом) продолжительность. Пунктиром
выделены фиктивные операции.
[pic]
Рис 4.1
Теперь перейдем ко второму этапу - обратному и прямому проходам по
полученному сетевому графику. При прямом проходе вычисляем наиболее ранние
возможные сроки наступления событий, при обратном - наиболее поздние
допустимые сроки наступления событий. Вычисления производим по следующим
алгоритмам. Обозначим через Е/ j /- наиболее ранний возможный срок наступления j-го
события. Пусть d i,j- продолжительность операции, соединяющей i -е и j -е
события. Поскольку j-е событие не может произойти, пока не будут завершены
все операции ведущие к j-му узлу, то наиболее ранний возможный срок его
наступления будет вычисляться по следующему алгоритму.
Алгоритм расчета наиболее ранних возможных сроков наступления событий.
Шаг 1. Положить Е/0/ = 0
Шaг 2. Для j = 1,2,...,n вычислить
E(j)=max {E( i ) + d ij }, i: (ij) э А
где максимум берется по всем операциям, завершающимся, в j -m узле и
выходящим из любого предшествующего i -го узла. Обозначим теперь через L ( i ) наиболее поздний срок наступления i -го события, не влияющий на время завершения всего проекта. Начиная с
завершающего события движемся в обратном направлении через каждое
предшествующее событие. Вычисления осуществляются в этом случае по
следующему алгоритму.
Алгоритм расчета наиболее поздних допустимых сроков наступления событий.
Шаг 1. Положить L( n ) =Е( n ).
Шаг 2. Для i = n-1,n-2,......,0 вычислить
L(i)=min {L(j-dij)}, j:(ij)эA
где минимум берется по всем операциям
начинающимся в i -м узле и входящим в любой j-й узел. Действуя описанным выше способом, рассчитаем наиболее ранние возможные
сроки наступления событий и наиболее поздние допустимые сроки наступления
событий (рис 4.2). Наиболее ранние возможные сроки наступления событий
отображены в квадратиках рядом с самим событием, над квадратиками
расположены наиболее поздние допустимые сроки наступления событий. На
основе прямого и обратного проходов выделяем на графике критические
операции из которых складывается критический путь. Критический путь
составляют операции: 1,2,4,8,9,(из 6 до 8 события фиктивная
операция),12,13,15,16,18 - эти опреации выделены другим цветом на граффике
(рис 4.2). Критическое время проекта - 104.
[pic]Рис 4.2 Теперь вычислим резервы времени для некритических операций. Рассчитанные
резервы времени внесем в таблицу 1.
Таблица 1
[pic] Теперь преобразуем полученную таблицу к виду (таблица 2) необходимому
для построения календарного графика проекта. Введем в таблицу для каждой
операции такие понятия как срок позднего начала и срок раннего окончания.
Также добавим графу указывающую на потребности в ресурсах каждой операции.
Таблица 2
[pic]
На основе полученной таблицы строим календарный график реализации проекта
(рис 4.3) и два графика ресурсных профилей проекта - в первом, выберем в
качестве моментов начала некритических операций их ранние возможные сроки,
получим ранний календарный план реализации проекта (рис 4.5), а во втором
выберем в качестве моментов начала некритических операций их поздние
допустимые сроки, получим поздний календарный план реализации проекта (рис
4.6)
[pic].Рис 4.5
[pic]Рис 4.6
Заключение
Максимальная потребность в ресурсах как на раннем, так и на позднем
календарных планах равна 15, но на позднем календарном плане время
использования максимума ресурсов составляет 1, а на раннем плане 8. Также
из графиков видно, что наиболее равномерно ресурсы распределены на позднем
плане. Поэтому наиболее оптимальной реализацией проекта будет поздний
календарный план, тоесть когда мы возьмем наиболее поздние возможные сроки
операций.
Список использованной литературы
Таха Х. “Введение в исследование операций” т.1,2
М. Мир 1989 Ковалева Л.Ф. “Математическая логика и теория графов”
МЭСИ 1977