Курсовая: Сетевые методы в планировании - текст курсовой. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Курсовая

Сетевые методы в планировании

Банк рефератов / Математика

Рубрики  Рубрики реферат банка

закрыть
Категория: Курсовая работа
Язык курсовой: Русский
Дата добавления:   
 
Скачать
Архив Zip, 367 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникальной курсовой работы

Узнайте стоимость написания уникальной работы

20 Кафедра прикладной математики Курсовая работа по курсу : “Дискретная математика” по теме : “Сетевые методы в планировании” Группа : ДИ 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с h lу Associates. Метод ПЕРТ разработан консультативной фирмой по заказу военно-морского министерства США для календарного планирования н аучно-исследовательских и опытно-конструкторских работ программы создания ракет «Поларис». В методах ПЕРТ и МКП основное внимание уделяется временному аспекту планов в том смысле , что оба метода в конечном счете определяют календарный план программы . Хотя эти методы были разработаны независимо , они отличаются поразительным сходством . Пожалуй , самым существенным различием первоначально было то , что в методе МКП оценки продолжительности операций предполагались детерминированными величинами , а в метод ПЕРТ — с лучайными . В настоящее время оба метода составляю единый метод сетевого планирования и управления (СПУ ) программами. Часть 1 Теоретическая часть к курсовому проекту Глава 1 Теория графов Понятие графа Графом G(X,U) называется совокупность двух объ ектов некоторого множества X и отображения этого множества в себя Г . При геометрическом представлении графа элементы множества Х изображаются точками плоскости и называются вершинами графа . Линии , соединяющие любые пары точек x и y , из которых у является о тображением х , называются дугами графа . Дуги графа имеют направление , обозначаемое стрелкой , которая направлена острием от элемента х к его отображению у . Вершины и линии графа Две вершины А и В являются граничными вершинами дуги , если А - начало дуги , а В ее конец. Смежными называются различные дуги , имеющие общую граничную точку . Две вершины х и у смежны , если они различны и существует дуга , идущая от одной из них к другой . Вершина называется изолированной , если она не соединена дугами с другими верш инами графа . Если дуга U исходит из вершины х или заходит в х , то дуга U называется инцидентной вершине х , а вершины х инцидентной дуге U . Общее число дуг , инцидентной вершине х , являются степенью вершины х Р (х ) . Вершины , степень которых Р (х )>2 , называют ся узлом , а со степенью Р (х )<2 - антиузлом. Полустепень захода Р + (х ) вершины х - количество дуг , заходящих в данную вершину . Полустепень исхода Р - (х ) - количество дуг , исходящих из данной вершины. Последовательность линий на графе Путь - последовательно сть дуг ( U 1 , U 2 , ...U n ), в которой конец каждой предыдущей дуги совпадает с началом последующей . Путь может быть конечным и бесконечным. Путь называется простым , если в нем никакая дуга не встречается дважды , и составным , если любая из дуг встречается боле е одного раза. Путь , в котором ни одна из вершин не встречается более одного раза , называется элементарным путем. Гамильтонов путь - путь проходящий через все вершины , но только по одному разу, Эллеров путь - путь содержащий все дуги графа , при этом только по одному разу. Длинна пути - число дуг последовательности ( U 1 , U 2 , ...U n ). Ветвь - путь , в котором начальная и конечная вершины являются узлами . Дуга (x,y) называется замыкающей , если удаление ее не приводит к аннулированию пути из x в y. Контур - конеч ный путь , начинающийся и заканчивающийся в одной и той же вершине . Контур единичной длинны называется петлей. Ориентированный граф - граф , у которого вершины соединяются направляющими стрелками. Графы можно рассматривать с учетом или без учета ориентации е го дуг. Разновидности графов Нуль-граф - граф (X,U) , состоящий только из изолированных вершин. Однородный граф - если степени всех вершин графа одинаковы и P + (x)= P - (x) =0. Симметрический граф - граф , в котором две любые смежные вершины соединены тольк о двумя противоположно ориентированными дугами. Антисимметрический - граф , в котором каждая пара смежных вершин соединена только в одном направлении. Полный - граф , в котором любая пара вершин соединена одинаковым числом дуг. Мультиграф - граф , в котором хотя бы две смежные вершины соединены более чем одной дугой . Наибольшее число дуг , соединяющих смежные вершины графа называется кратностью. Подмножества графов Подграфом графа G(X,U) называется граф G(A,U A ) , определяемый следующим образом : 1. Вершинами A подграфа G(A,U A ) является некоторое подмножество вершин графа G(X,U); 2. Отображением каждой вершины подграфа является пересечение отображения той же вершины в графе G(X,U) со всем подмножеством вершин A подграфа G(A,U A ). Частичным графом для графа G(X,U) называется граф G(X,U) , в котором содержатся все вершины и некоторое подмножество дуг исходного графа. Частичный подграф - это частичный граф от подграфа. Фактором графа G(X,U) называется частичный граф G(X,U) , в котором каждая вершина обладает пол устепенями исхода и захода , равными единице , имеются одна заходящая и одна исходящая дуги. Базисным графом называется ориентированный частичный граф , образованный из исходного удалением петель и замыкающих дуг. Связность графа В общем случае граф может быть представлен несколькими отдельными графами , не имеющими общих дуг . Тогда граф G(X,U) называется несвязным , а каждый из составляющих его графов G 1 , G 2 ,...G n - компонентами связности . Граф называется связным , когда каждую его вершину можно соединить с любой другой его вершиной некоторой цепью. Операции над графами 1. Объединение графов G 3 (X 3 ,Гх 3 ) = G 1 (X 1 ,Г 1х 1 ) G 2 (X 2 ,Г 2х 2 ) , где X 3 =X 1 X 2 , а Г x 3 =Г 1x 1 Г 2x 2 При мер (Рис 1.1). Рис 1.1 2. Пересечение графов G 3 (X 3 ,Гх 3 ) = G 1 (X 1 ,Г 1х 1 ) G 2 (X 2 ,Г 2х 2 ) , где X 3 =X 1 X 2 , а Г x 3 =Г 1x 1 Г 2x 2 Пример (ри с 1.2). Рис 1.2 4. Прямое (декартово ) произведение графов. Прямым произведением множеств Х x 1 .......x n и Y называется множество Z, элементами которого являются всевозможные пары вида x i , y j , где x i X, y j Y. Обозначают : Z=X x Y. G 3 (X 3 ,Гх 3 ) = G 1 (X 1 ,Г 1х 1 ) G 2 (X 2 ,Г 2х 2 ) , где X 3 =X1 X2, а Г x 3 =Г 1х 1 Г 2х 2 Пример . (рис 2.3) G 1 (X,Гх )=G 1 (X 1 ,Гх 1 ) G 2 (Y,Г y)= G 2 (X 2 ,Гх 2 ) X= x 1 x 2 x 3 Y= y 1 y 2 Гх 1 =0 Гу 1 = y 1 y 1 Гх 2 = x 1 x 3 Гу 2 = y 1 Гх 3 =0 Z=X x Y= x 1 y 1 , x 1 y 2 , x 2 y 1 , x 2 y 2 , x 3 y 1 , x 3 y 2 Z= z 1 z 2 z 3 z 4 z 5 z 6 Рис 2.3 7. Расширение графа. Расширение графа - это превращение , линии , соединяющей любые две вершины графа в элементарный путь введением новых промежуточных вершин на этой линии. 8. Сжатие графа. Сжатие графа - это превращение элементарного пути , соединяющего две любые вершины графа , в линию . 9. Стягивание графа. Если граф содержит вершины Х 1 и Y 1 , то операцией стягивания называется исключение всех дуг между вершинами Х 1 и Y 1 и превращение всех вершин в одну об щую вершину Х. Некоторые числа теории графов Пусть существует мультиграф с b вершинами , p ребрами , и R компонентами связности , тогда цикломатическое число мультиграфа определяется равенством : V = p - b + R Матрицы для графов Матрицей смежности графа G(X,Гх ) , содержащего n вершин называется квадратная бинарная матрица А (G) n x n , c нулями на диагонали . Число единиц в строке равно степени соответствующей вершины . Матрицей инциденций ориентированного графа G(X,U) называется прямоугольная матрица порядка [m x n] n - мощность множества Х, m - мощность множества U. Каждый элемент которой определяется следующим образом : 1, если х i - начало дуги U j a ij = -1, если х i - конец дуги U j 0, если х i - не инцидентна дуге U j Пример. Построим матрицы смежности (М 1) и инциденций (М 2) для графа G(X,U) (рис 2.1). Рис 2.1 Дополнительная матрица графа G(X,U) представляет собой квадратную матрицу А 1 , которая получается из матрицы смежности этог о графа путем замены всех нулей единицами и наоборот. Деревья и прадеревья Деревом называется неориентированный связный граф с числом вершин не менее двух , не содержащий петель и циклов . Вершины , инцидентные только одной дуге дерева , называются висячими . Прадрево - ориентированное дерево. Корень прадерева - вершина у которой Р + (х )=0 . Глава 2 Календарное планирование программ сетевыми методами Сетью называется конечный граф G(X,Y) , без циклов и петель , ориентированный в одном общем направлении от ве ршин V, являющимися входами графа , к вершинам W, являющимися выходами. Сетевое планирование и управление программами включает три основных этапа : структурное планирование , календарное планирование и оперативное управление. Этап структурного планирования на чинается с разбиения программы на четко определенные операции . Затем определяются оценки продолжительности операций и строится сетевая модель (сетевой график , стрелочная диаграмма ), каждая дуга (стрелка ) которой отображает работу . Вся сетевая модель в цел о м является графическим представлением взаимосвязей операций программы . Построение сетевой модели на этапе структурного планирования позволяет детально проанализировать все операции и внести улуч шения в структуру программы еще до начала ее реализации . Од н ако еще более существенную роль играет использование сетевой модели для разработки календарного плана выполнения программы. Конечной целью этапа календарного планирования является построение календарного графика , определяющего моменты нача ла и окончания к аждой операции , а также ее взаимосвязи с другими операциями программы . Кроме того , календарный график должен давать возможность выявлять критические операции (с точки зре ния времени ), которым необходимо уделять особое внимание , чтобы закончить программу в директивный срок . Что касается некрити ческих операций , то календарный план должен позволять определять их резервы времени , которые можно выгодно использовать при за держке выполнения таких операций или с позиций эффективного использования ресурсов. Заклю чительным этапом является оперативное управление процессом реализации программы . Этот этап включает использование сетевой модели и календарного графика для составления периодических отчетов о ходе выполнения программы . Сетевая модель под вергается анализ у и в случае необходимости корректируется . В этом случае разрабатывается новый календарный план выполне ния остальной части программы. Сетевая модель Сетевая модель отображает взаимосвязи между операциями и порядок их выполнения (отношение упорядочения или следования ) Как правило , для представления операции используется стрелка (ориентированная дуга ), направление которой соответствует процессу реализации программы во времени . Отношение упорядоченное между операциями задается с помощью событий . Событие опред еляется как момент времени , когда завершаются одни операции и начинаются другие . Начальная и конечная точки любой операции описываются , таким образом , парой событий , которые обычно называют начальным событием и конечным событием . Операции , выходящие из нек оторого события , не могут начаться , пока не будут завершены все операции , входящие в это событие . По принятой в СПУ терминологии каждая операция представляется ориентировано дугой , а каждое событие — узлом (вершиной ). Не требуется , что длина дуги была про п орциональна продолжительности операции , а графическое изображение дуг не обязательно должно представлять прямолинейный отрезок. 1 i j 3 4 2 (а ) (б ) Рис . 3.1 На рис . 3.1 а приведен типичный пример графического отображения операции i , j с начальным событием i и конечным событием j . На рис . 3.1 б показан другой пример , из которого видно , что для возможности начала операции (3, 4) требуется з авершение операций (1,3) и (2, 3). Протекание операций во времени задается порядком нумерации событий , причем номер начального события всегда меньше номера конечного . Такой способ нумерации особенно удобен выполнении вычислений на ЭВМ. Правила построения сетевой модели Правило 1. Каждая операция в сети представляется одной и только одной дугой (стрелкой ). Ни одна из операций не должна появляться в модели дважды . При этом следует различать случай , когда какая-либо операция разбивается на части ; тогда кажда я часть изображается отдельной дугой . Так , например , прокладку трубопровода можно расчленить на прокладку отдельных секций и рассматривать прокладку каждой секции как самостоятельную опе рацию. Правило 2. Ни одна пара операций не должна определяться оди на ковыми начальным и конечным событиями. Возможность неод нозначного определения операций через события появляется в слу чае , когда две или большее число операций допустимо выполнять одновременно . Пример этого случая приведен на рис . 3.2 а, где операции А ' и В имеют одинаковые начальное и конечное события . Чтобы исключить такую «ошибку» между А и ( a ) ( б ) рис 3.2 конечным (начальным ) событием ил и между В и конечным (начальным ) событием , вводится фиктивная операция D . Рис . 3.2 б иллюстрирует различные ва рианты введения такой фиктивной операции D. В результате опе рации А и В определяются теперь однозначно парой событий , отлича ющихся либо номеро м начального , либо номером конечного со бытия . Следует обратить внимание на то , что фиктивные операции не требуют затрат ни времени , ни ресурсов. Фиктивные операции позволяют также правильно отображать логические связи , которые без их помощи нельзя задать на сети . Предположим , что в некоторой программе операции А и В должны непосредственно предшествовать С, а операции Е непосредственно предшествует только В . На рис 12.3 а э ти условия отражены неверно , так как , хотя упорядочения между А . В и С показаны пра в ильно , из этого фрагмента следует , что операции Е должны непо средственно предшествовать обе операции А и В. Правильное пред ставление указанных условий дает фрагмент , изображенный на рис 12.3 б в котором используется (а ) (б ) Рис 3.3 фиктивная операция D. Поскольку на операцию D не затрачиваются ни время , ни ресурсы заданные отношения упорядочения выполняются. Правило 3. При включени и каждой операции в сетевую модель для обеспечения правильного упорядочения необходимо дать ответы на следующие вопросы : а ) Какие операции необходимо завершить непосредственно перед началом рассматриваемой операции ? б ) Какие операции должны непосредственно следовать после завершения данной операции ? в ) Какие операции могут выполняться одновременно с рассматриваемой ? Это правило не требует пояснений . Оно позволяет проверять (и перепроверять ) отношения упорядочения в процессе пос троения сети. Расчет сетевой модели Применение методов СПУ в конечном счете должно обеспечить получение календарного плана , определяющего сроки начала и окончания каждой операции . Построение сети является лишь первым шагом на пути к достижению этой цели. Вследствие наличия взаимосвязей между различными операциями для определения сроков их начала и окончания необходимо проведение специальных расче тов . Эти расчеты можно выполнять непосредственно на сети , пользуясь простыми правилами . В результате вычислен и й определяются критические и некритические операции программы . Операция счи тается критической , если задержка ее начала приводит к увеличению срока окончания всей программы . Некритическая операция отли чается тем , что промежуток времени между ее ранним нач алом и поздним окончанием (в рамках рассматриваемой программы ) боль ше ее фактической продолжительности. Определение критического пути Критический путь определяет непрерывную последовательность критических операций , связывающих исходное и завершающее со бытия сети . Другими словами , критический путь задает все крити ческие операции программы . Расчет критического пути включает два этапа . Первый этап называется прямым проходом . Вычисления начинаются с исходно го события и продолжаются до тех пор , пока не б у дет достигнуто завершающее событие всей сети . Для каждого события вычисляет ся одно число , представляющее ранний срок его наступления . На втором этапе , называе мом обратным проходом , вычисления начинаются с завершающего события сети и продолжаются , пока не будет достигнуто исходное событие . Для каждого события вычисляется число , представляющее поздний срок его наступления . Обратный проход начинается с завершающего события сети . При этом целью является определение поздних сроков окончания всех операций , вход ящих в событие. Теперь , используя результаты вычислений при прямом и обратном проходах , можно определить операции критического пути . Операция ( i , j) принадлежит критическому пути, если она удовлетворяет следующим трем условиям : E(i) - ранние сроки начала всех операций , выходящих из события i. L(i) - поздние сроки окончания всех операций , входящих в событие i. D ij - продолжительность операции , соединяющей i-тое и j- тое события . 1. E(i)=L(i) 2. E(j)=L(j) 3. E(j)-E(i)=L(j)-L(i)=D ij По существу , эти условия означают , что между ранним сроком : начала (окончания ) и поздним сроком начала (окончания ) критической операции запас времени отсутствует. Резервы времени некритических операций Резерв критической операции равен нулю . Рассмотрим некоторую некрити ческую операцию / i , j /. Какое максимальное количество времени можно выделить для ее выполнения без задержки своевременного окончания всего проекта ? Операция / i , j / может начаться не ранее Е / i /и должна закончиться не позднее L ( j ). Таким образо м , без задержки окончания проекта на выполнение операции / i , j / можно выделить не более L ( j )-Е ( i ) единиц времени . Следовательно , при выполнении этой операции можно допустить максимальную задержку L ( j )-Е ( i )- d ij >= 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). События пронумерованы в кружках , линии со стрелками - работы (далее вместо слова “ работы” я буду употреблять “операции” ). Рядом со стрелками операций стоят их номера и ( с черточками над и под числом ) продолжительность . Пунк т иром выделены фиктивные операции. Рис 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. Рис 4.2 Теперь вычислим резервы времени для некритических операций . Рассчитанные резервы времени внесем в таблицу 1. Таблица 1 Теперь преобразуем полученную таблицу к виду (таблица 2) необходимому для построения календарного графика проекта . Введем в таблицу для каждой операции такие понятия как срок позднего начала и срок раннего окончания . Также добавим графу указывающую на потребности в ресурсах каждой операции. Таблица 2 На основе полученной таблицы строим календарный график реализации проекта (рис 4.3) и два графика ресурсных профилей проекта - в первом , выберем в качестве моментов начала некритических операций их ранние возможные сроки , получим ранний календарный план реализации проекта (рис 4.5), а во втором выберем в качестве моментов начала некритических операций их поздние допустимые сроки , получим поздний календарный план реализации проекта (рис 4.6) .Рис 4.5 Рис 4.6 Заключение Максимальная потребность в ресурсах как на раннем , так и на позднем календарных планах равна 15, но на позднем календарном плане время использования максиму ма ресурсов составляет 1, а на раннем плане 8. Также из графиков видно , что наиболее равномерно ресурсы распределены на позднем плане . Поэтому наиболее оптимальной реализацией проекта будет поздний календарный план , тоесть когда мы возьмем наиболее поздни е возможные сроки операций . Список использованной литературы Таха Х . “Введение в исследование операций” т .1,2 М . Мир 1989 Ковалева Л.Ф . “Математическая логика и теория графов” МЭСИ 1977
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Сушилка в общественном туалете - это отличный способ погреть руки перед тем, как вытереть их об джинсы.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, курсовая по математике "Сетевые методы в планировании", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru