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

Реферат

Сетевые графики

Банк рефератов / Логистика

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

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Microsoft Word, 804 kb, скачать бесплатно
Обойти Антиплагиат
Повысьте уникальность файла до 80-100% здесь.
Промокод referatbank - cкидка 20%!

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

Многие крупные проекты , такие как строительство дома , из готовление станка , разработка автоматизированной системы бухгалтерского учета и т.д ., можно разбить на большое количест во различных операций (работ ). Некоторые из этих операц ий могут выполняться одновременно , другие — только последовательно : одна операция после окончания другой . Например , при строительстве дома можно совместить во времени внутренние отде лочные работы и ра боты по благоустройству территории , однако возводить стены можно то лько после того , как будет готов фундамент . Задачи планиров ания работ по осуществлению некоторого проект а состоят в определении времени возможного окончания как всего проекта в целом , та к и отдельных работ , образующих проект ; в определении резервов времени для выполне ния отдельных работ ; в определении критически х работ , то есть таких работ , задержка в выполнении которых ведет к задержке вып олнения всего проекта в целом ; в управлени и ресурса м и , если таковые имеются и т.п. Пусть некоторый проект W состоит из работ V 1 ,..., V n ; для каждой работы V k , известно , или может быть достаточно точно оценено время ее выполнения t ( V k ). Кроме того , дл я каждой работы V k известен , в озможно пустой , список ПРЕДШ ( V k ) работ , непосред ственно предшествующих выполнению работы V k . Иначе говоря , работа V k может начать выполняться только после завершения всех работ , входящих в список ПРЕДШ ( V k ). Для удобства , в список работ проекта W добавим две фиктивные работы s и p , где работа s обозначает начало всего проекта W. а работа p — завершение работ по проекту W. При этом будем считать , что работа s предшеств ует всем тем работам v W, для которых список ПРЕДШ (v) пуст , иначе говоря , для всех таких ра бот v W положим ПРЕДШ (v)= s . Положим далее ПРЕДШ (s) = , ПРЕ ДШ ( p )= v W: v не входит ни в один список ПРЕДШ (w) , то есть счита ем , что работе p предшествуют все те р аботы , которые могут выполняться самыми последними . Время выполнения работ s и p естественно положить ра вными нулю : t(s)=t( p )=0. Весь проект W теперь удобно представить в виде сети G =( V , E , c ). Ориентированный взвешенный граф G =( V , E , c ) называется сетью . Се ть может быть представлена матрицей весов дуг , массивами смежностей СЛЕД или ПРЕДШ , или списками СЛЕД [ v ] или ПРЕДШ [ v ] . При этом записи в списках смежност и состоят из трех компонент : поля имени узла , поля веса соответствующей дуги и поля ссылки на следующую запись ), где сеть G =( V , E , c ) определим по правилам : 1. V = W , то есть множеством узлов объявим множество работ ; 2. E = ( v , w ) : v ПРЕДШ (w) , то есть отношение п редшествования задает дуги в сети ; 3. c(v,w)=t(w). Так построенную сеть G часто называют сетевым графиком выполнения работ по проекту W. Ле гко видеть , что списки смежностей этой сет и ПРЕДШ [v] совпадают с заданными для проект а списками предшествующих работ ПРЕДШ (v). Понятно , что сетевой график любого про екта не должен соде ржать контуров . Дей ствительно , пусть узлы V k 1 , V k 2 ,..., V kr = V k 1 образуют контур в сети G. Это означает , что работа V k 2 не может на чаться раньше , чем будет завершена работа V k 1 , р абота V k 3 — раньше , чем завершится работ а V k 2 , и т.д ., и , наконец , V kr = V k 1 — раньше , чем будет завершена работа V kr -1 . Но тогда никакая и з работ V k 1 ,..., V kr никогда не сможет быть выполнена . А каждый реал ьный проект должен допускать возможность его завершения . Следовательно , в сетевом графике нет контуров. Отсутствие контуров в сет и G позволяет п ронумеровать работы проекта W таким образом , чтобы для каждой дуги ( V i , V j ) сети G выполнялось услови е i < j , то есть каждая дуга идёт из узла с меньшим номером в узел с бол ьшим номером . Осущест вить такую нумерацию узл ов сети G можно с помощью алгоритма т опологической сортировки . Поэтому в дальнейшем будем считать , что узлы в сети G топологи чески отсортированы. Конечной целью построения сетевой модели является получе ние информации о возможных сроках выполнения как отдельных работ , так и о возм ожном сроке выполнения в сего проекта в це лом. Обозначим через PB ЫП ( v ) (соответственно PHA Ч ( v )) наиболее ранний возможны й срок выполнения работы v (соответственно наибо лее ранний возможный срок начала работы v). Удобно считать , что PB ЫП ( s )= PHA Ч ( s )=0. Поскольку н а чать выполнять работу v можно только после того , как будут выполнены все работы , пр едшествующие данной работе v, то получим следую щие формулы для расчета значений PHA Ч ( v ) и PB ЫП ( w ) : PHA Ч ( v ) = МАКС PB ЫП ( w ) : w ПРЕДШ (v) , PBЫП (v) = PHAЧ (v) + t(v). Значение PB ЫП ( p ) дает наиболее ранний возможный срок заве ршения всего проекта в целом . Приведем запись алгоритма , непосредственно вычисляющего характеристики РНАЧ и РВЫП. АЛГОРИТМ 1. Данные : Сетевой график G работ V , задан ный списками ПРЕДШ ( v ) , v V . Результаты : Наиболее ранние возможные сро ки начала и выполнения работ РНАЧ ( v ), РВЫП ( v ), v V . Шаг 1. Объявить возможные ранние сроки начала РНАЧ ( v ) и выполнения Р ВЫП ( v ) работ равными нулю . Текущей вершиной объявить первую вершину v k =v 1. Шаг 2. Всем вер шинам v предшествующим текущей вер шине v k , з начение Р НАЧ ( v k ) присвоить максимум из значений РВЫП ( v ) и РНАЧ ( v k ). З начение РВЫП ( v k ) положить равн ым значению РНАЧ ( v k ) плюс время выпол нения самой работы текущей вершины t ( v k ) . Шаг 3. Если име ется следующая вершина (работа ) после текущей , то объявить ее текущей вершиной v k , иначе перейти в Шаг 5. Шаг 4. Вернуться в Шаг 2. Шаг 5. Выдать н аиболее ранние во зможные сроки начала и выполнения работ РНАЧ (v), РВЫП (v), v V, конец работы алгоритма. Пусть T — плановый срок выполнения проекта W. Ясно , что Т должно удовлетворять неравенству Т >= РВ ЫП ( V n +1 ). Через ПВЫП ( v ) (соответственно ПНАЧ ( v )) обозначим наиболее поздний допустимый срок выполнен ия (начала ) работы v , то есть такой срок , который не увеличивает срок Т реализации всего проекта. Значения возможных и допустимых сроков выполнения работ позволяют определить резервы времени для в ыполнения той или и ной работы . Полный резерв (иногда его называют суммарный ) времени выполнен ия работ определяется по формуле : PE3EPB(v)=П HAЧ (v)-PHAЧ (v). Значение PE 3 EPB ( v ) равно максимальной задержке в выпол нен ии работы v, не влияющей на плановый срок Т . Понятно , что справедливо и такое равенство : РЕЗЕРВ (v)=ПВЫП (v)-РВЫП (v). Работы , имеющие нулевой резерв времени , называются критическими. Через любую такую работу проходит некоторый мак симальный s- p -путь в сети G. Критическ ие работы характеризуются тем , ч то люб ая задержка в их выполнении автоматически ведет к увеличению времени выполнения всег о проекта. Приведем запись алгоритма , непосредственно вычисляющего характеристики ПВЫП и ПНАЧ . АЛГОРИТМ 2. Данные : Сетевой график G работ V , заданн ый списками ПРЕ ДШ ( v ) , v V , плановый срок окончания проекта – Т. Результаты : Наиболее поздние до пустимые сроки выполнения и начала работ ПВЫП ( v ) и ПНАЧ ( v ). Шаг 1. Объявить для вс ех работ v V значение на иб олее позднего срока выполнения работ равным Т – значению планового срока о кончание проекта и вершину v p фиктивной работы p объявить текущей v k . Шаг 2. Присвоить значение ПНАЧ текущей работы v k равным значению ПВЫП работы и вычесть время выполнения тек ущей работ ы. Шаг 3. Присвоить значению ПВЫП (v) для всех работ v ПРЕДШ (v) предшествующи х текущей работе v k минимальное значение из значений ПВЫП выполнения роботы v или ПНАЧ выполнения текущей работы v k , если таковых нет п ерейти в Шаг 4. Шаг 4. Если име ется предыдущая вершина (работа ) к текущей , то объявить её текущей , иначе перейти в Шаг 6. Шаг 5. Перейти в Шаг 2. Шаг 6. Выдать н аиболее поздние допустимые сроки выполнения и начала работ ПВЫП ( v ) и ПНАЧ ( v ), ко нец работы ал горитма. Проиллюстрируем работу приведенных алгоритмо в на следующих примерах : Пример 1: Проект гаража для стоянки автопогрузчиков. n Наименование работы Предшеству-ющие работы Время вы-полнения t ( v k ) 1 Н ачало проекта (фиктивн . работа ) Нет 0 2 Срезка растител ьного слоя грунта 1 5 3 Монтаж каркаса 2 30 4 Обшивка стен профнастилом 3 15 5 Кровля из профна стила 3 12 6 За полнение проема воротами 4 5 7 Масляная окраска ворот и профнастила 5,6 10 8 Щебёночное основание под полы 7 3 9 Ас фальт овое покрытие 8 3 10 Уборка строительного мусора после строит. 7 3 11 Конец проекта (фи ктивная работа ) 9,10 0 Рис 1. Проект гаража для стоянки автопо грузчиков. Найдем значения наиболее раннего начала и выполнения раб от проекта посредством алгоритма 1. Работу алго ритма изложим в виде последовательности выпол няемых шагов. Шаг n Д ействия выполняемые шагом 1 Объявление значений РНАЧ ( v ) и РВЫП ( v ) , v V равными нул ю . Текущая вершина v k =1. 2 Вершин предшествую щей первой нет . РВЫП (1)=РНАЧ (1)+ t (1). РНАЧ (1) стало равным 0 3 Текущая вершина v k =2. 4 Перех од в Шаг 2. 2 РНАЧ (2)=МАКС РВЫП (1),РНАЧ (2) РНА Ч (2) стало равным 0 РВЫП (2)=РНАЧ (2)+ t ( 2) РВЫП (2) стало равным 5 . 3 Текущая верши на v k =3. 4 Переход в Шаг 2. 2 РНАЧ (3)=МАКС РВЫП (2),РНАЧ (3) РНАЧ (3) стало р авным 5 РВЫП (3)=РНАЧ (3)+ t (3) РВЫП (3) стало равным 35 . 3 Текущая вершина v k =4. 4 Переход в Шаг 2. 2 РНАЧ (4)=МАКС РВЫП (3),РНАЧ (4) РНАЧ (4) стало равным 35 РВЫП (4)=РНАЧ (4)+ t (4) РВЫП (4) стало равным 50 . 3 Текущая вершина v k =5. 4 Переход в Шаг 2. 2 РНАЧ (5)=МАКС РВЫП (3),РНАЧ (5) РНАЧ (5) стало р авным 35 РВЫП (5)=РНАЧ (5)+ t (5) РВЫП (5) стало равным 47 . 3 Текущая вершина v k =6. 4 Переход в Шаг 2. 2 РНАЧ (6)=МАКС РВЫП (4),РНАЧ (6) РНАЧ (6) стало равным 50 РВЫП (6)=РНАЧ (6)+ t (6) РВЫП (6) стало равным 55 . 3 Текущая вершина v k =7. 4 Переход в Шаг 2. 2 РНАЧ (7)=МАКС РВЫП (5),РНАЧ (7) РНАЧ (7) стало равным 47 РНАЧ (7)=МАКС РВЫП (6),РНАЧ (7) РНАЧ (7) стало равным 55 РВЫП (7)=РНАЧ (7)+ t ( 7) РВЫП (7) стало равным 65 . 3 Текущая вершина v k =8. 4 Переход в Шаг 2. 2 РНАЧ (8)=МАКС РВЫП (7),РНАЧ (8) РНАЧ (8) стало равн ым 65 РВЫП (8)=РНАЧ (8)+ t (8) РВЫП (8) стало равным 68 . 3 Текущая вершина v k =9. 4 Переход в Шаг 2. 2 РНАЧ (9)=МАКС РВЫП (8),РНАЧ (9) РНАЧ (9) стало равным 68 РВЫП (9)=РНАЧ (9)+ t (9) РВЫП (9) стало равным 71 . 3 Текущая вершина v k =10. 4 Переход в Шаг 2. 2 Р НАЧ (10)=МАКС РВЫП (7),РНАЧ (10) РНАЧ (10) стало равным 65 3 Текущая вершина v k =11. 4 Переход в Шаг 2. 2 РНАЧ (11)=МАКС РВЫП (9),РНАЧ (11) РНАЧ (11) стало равным 71 РНАЧ (11)=МАКС РВЫП (10),РНАЧ (11) РНАЧ (11) стало равным 71 3 Переход в Шаг 5. 5 Конец рабо ты алгоритма , выдача значений наиболее раннего начала и выполнения работ. Таблица результатов работы алгоритма. n 1 2 3 4 5 6 7 8 9 10 11 РНАЧ ( v ) 0 0 5 35 35 50 55 65 68 65 71 РВЫП ( v ) 0 5 35 50 47 55 65 68 71 68 71 Получили , что минимальное время , тр ебуемое для выполнения проекта рав но Т =РВЫП (11), Т =71. Теперь найдем посредством алгоритма 2 значение времени наиболее позднег о начала и выполнения работ . Работу алгори тма изложим в виде последовательности выполня емых шагов. Шаг n Действия выполняемые ша гом 1 Объявление значений ПВЫП ( v ), v V равны м Т. Текущая вершина v k =11. 2 ПНАЧ (11)=ПВЫП (11)- t (11) ПНАЧ (11) стало равным 71 . 3 ПВЫП (9)=МИН ПВЫП (9),ПНАЧ (11) ПВЫП (9) ст ало равным 71 ПВЫП (10)=МИН ПВЫП (10),ПНАЧ (11) ПВЫП (10) стало равным 71 4 Текущая вершина v k =10. 5 Переход в Шаг 2. 2 ПНАЧ (10)=ПВЫП (10)- t (10) ПНАЧ (10) стало равным 68 3 ПВЫП (7)=МИН ПВЫП (7),ПНАЧ (10) ПВЫП (7) ст ало равным 68 4 Текущая вершина v k =9. 5 Переход в Шаг 2. 2 ПНАЧ (9)=ПВЫП (9)- t (9) ПНАЧ (9) ст ало равным 68 3 ПВЫП (8)=МИН ПВЫП (8),ПНАЧ (9) ПВЫП (8) стало равным 68 4 Текущая вершина v k =8. 5 Переход в Шаг 2. 2 ПНАЧ (8)=ПВЫП (8)- t (8) ПНАЧ (8) стало равным 65 3 ПВЫП (7)=МИН ПВЫП (7),ПНАЧ (8) ПВЫП (7) ста ло равным 65 4 Текущая вершина v k =7. 5 Переход в Шаг 2. 2 ПНАЧ (7)=ПВЫП (7)- t (7) ПНА Ч (7) стало равным 55 3 ПВЫП (5)=МИН ПВЫП (5),ПНАЧ (7) ПВЫП (5) стало равным 55 ПВЫП (6)=МИН ПВЫП (6),ПНАЧ (7) ПВЫП (6) стало равным 55 4 Текущая вершина v k =6. 5 Переход в Шаг 2. 2 ПНАЧ (6)=ПВЫП (6)- t (6) ПНАЧ (6) стало равным 50 3 ПВЫП (4)=МИН ПВЫП (4),ПНАЧ (6) ПВЫП (5) стало равным 50 4 Текущая вершина v k =5. 5 Переход в Шаг 2. 2 ПНАЧ (5)=ПВЫП (5)- t (5) ПНАЧ (5) стало равным 43 3 ПВЫП (3)=МИН ПВЫП (3),ПНАЧ (5) ПВЫП (3) стало равным 43 4 Текущая вершина v k =4. 5 Переход в Шаг 2. 2 ПНАЧ (4)=ПВЫП (4)- t (4) ПНАЧ (4) стало равным 35 3 ПВЫП (3)=МИН ПВЫП (3),ПНАЧ (4) ПВЫП (3) стало равным 35 4 Текущая вершина v k =3. 5 Переход в шаг 2. 2 ПНАЧ (3)=ПВЫП (3)- t (3) ПНАЧ (3) стало равным 5 3 ПВЫП (2)=МИН ПВЫП (2),ПНАЧ (3) ПВЫП (2) стало равным 5 4 Текущая вершина v k =2. 5 Переход в Шаг 2. 2 ПНАЧ (2)=ПВЫП (2)- t (2) ПНАЧ (2) стало равным 0 3 ПВЫП (1)=МИН ПВЫП (1),ПНАЧ (2) ПВЫП (1) стало равным 0 4 Текущая вершина v k =1. 5 Переход в Шаг 2. 2 ПНАЧ (1)=ПВЫП (1)- t (1) ПНАЧ (1) стало ра вным 0 3 Переход в Шаг 4. 4 Переход в Шаг 6. 6 Конец работы алгоритма , выдача значений времени наиболее позднего начала и выполнения работ. Дадим таблицу результатов работы алгоритма с результатами предыдущего алгоритма и сосчитаем резерв времени для каждой работы по формуле PE 3 EPB ( v )=ПНАЧ ( v )- PHA Ч ( v ) или РЕЗЕРВ (v)=ПВЫП (v)-РВЫП (v). Рабо ты РНАЧ РВЫП ПНАЧ ПВЫП Резерв 1 0 0 0 0 0 2 0 5 0 5 0 3 5 35 5 35 0 4 35 50 35 50 0 5 35 47 43 55 8 6 50 55 50 55 0 7 55 65 55 65 0 8 65 68 65 68 0 9 68 71 68 71 0 10 65 68 68 71 3 11 71 71 71 71 0 Из таблицы видно , что критическим и работами являются 1, 2, 3, 4, 6, 7, 8, 9, 11, которые и образуют в сети G критический путь . Расчеты выполнены при Т =71. Пример 2: Проект склада сажи и других материалов в помещен ие производственного цеха . n Наименование работ ы Предшеству-ющие работы Время вы-полнения t ( v k ) 1. Начало проекта (фиктивн . работа ) Нет 0 2. Монтаж металлоконс трукций нижней каркаса 1 5 3. Устройство бетона под стойки 2 3 4. Монтаж стоек 3 10 5. Монтаж опорных столиков 4 5 6. Монтаж балок 2 7 7. Монтаж металлоконструкций ворот 6 7 8. Обшивка стен и кровли волнистым листо м 6 12 9. Монтаж козлового крана 7 5 10. Устройст во асфальтобетонных покрытий 8 5 11. Конец проекта ( фиктивн . работа ) 5,9,10 0 Рис 2. Проект склада сажи и других материалов в помещение производственного цеха. Найдем значения наиболее раннего начала и выполнения раб от проекта посредством алгоритма 1. Работу алгоритма изложим в виде последовательности выполняемых шагов. Шаг n Действи я выполняемые шагом 1 Объявление значени й РНАЧ ( v ) и РВЫП ( v ), v V равным нулю. Текущая вершина v k =1 . 2 Вершин предшествующей первой нет . Значение РНАЧ (1)=РВЫП (1)+ t (1). 3 Текущая вершина v k =2. 4 Переход в Шаг 2. 2 РНАЧ (2)=МАКС РВЫП (1),РНАЧ (2) РНАЧ (2) стало равным 0 РВЫП (2)=РНАЧ (2)+ t (2) РВЫП (2) стало равным 5 . 3 Текущая вершина v k =3. 4 Переход в Шаг 2. 2 РНАЧ (3)=МАКС РВЫП (2),РНАЧ (3) РНАЧ (3) стало равным 5 РВЫП (3)=РНАЧ (3)+ t (3) РВЫП (3) стало равным 8 . 3 Текущая вершина v k =4. 4 Переход в Шаг 2. 2 РНАЧ (4)=МАКС РВЫП (3),РНАЧ (4) РНАЧ (4) стало равным 8 РВЫП (4)=РНАЧ (4)+ t (4) РВЫП (4) стало равным 18 . 3 Текущая верши на v k =5. 4 Переход в Шаг 2. 2 РНАЧ (5)=МАКС РВЫП (4),РНАЧ (5) РНАЧ (5) стало равным 18 РВЫП (5)=РНАЧ (5)+ t (5) РВЫП (5) стало равным 23 . 3 Текущая вершина v k =6. 4 Переход в Шаг 2. 2 РНАЧ (6)= РВ ЫП (2),РНАЧ (6) РНАЧ (6) стало равным 5 РВЫП (6)=РНАЧ (6)+ t (6) РВЫП (6) ста ло равным 12 . 3 Текущая вершина v k =7. 4 Переход в Шаг 2. 2 РНАЧ (7)=МАКС РВЫП (6),РНАЧ (7) РНАЧ (7) стало равным 12 РВЫП (7)=РНАЧ (7)+ t (7) РВЫП (7) стало равным 19 . 3 Текущая верши на v k =8. 4 Переход в Шаг 2. 2 РНАЧ (8)=МАКС РВЫП (6),РНАЧ (8) РНАЧ (8) ст ало равным 12 РВЫП (8)=РНАЧ (8)+ t (8) РВЫП (8) стало равным 24 . 3 Текущая вершина v k =9. 4 Переход в Шаг 2. 2 РНАЧ (9)=МАКС РВЫП (7),РНАЧ (9) РНАЧ (9) стало равным 19 РВЫП (9)=РНАЧ (9)+ t (9) РВЫП (9) стало равным 24 . 3 Текущая вершина v k =10. 4 Переход в Ша г 2. 2 РНАЧ (10)=МАКС РВЫП (8), РНАЧ (10) РНАЧ (10) стало равным 24 РВЫП (10)=РНАЧ (10)+ t (10) РВЫП (10) стало равным 29 . 3 Текущая вершина v k =11. 4 Переход в Шаг 2. 2 РНАЧ (11)=МАКС РВЫП (9), РНАЧ (11) РНАЧ (11) стало равным 24 РНАЧ (11)=МАКС РВЫП (10),РНАЧ (1 0) РНАЧ (11) стало равным 29 РВЫП (11)=РНАЧ (11)+ t (11) РВЫП (11) стало равным 29 . 3 Переход в Шаг 5. 5 Конец работы алгоритма , выдача значений наиболее раннего начала и выполнения работ. Таблица результатов работы алг оритма. n 1 2 3 4 5 6 7 8 9 10 11 РНАЧ ( v ) 0 0 5 8 18 5 12 12 19 24 29 РВЫП ( v) 0 5 8 18 23 12 19 24 24 29 29 Получили , что минимальное время , требуемое для выполнения проекта равно Т =РВЫП (11), Т =29. Теперь найдем посредством алгор итма 2 значение времени наиболее позднего нача ла и выполн ения работ . Работу алгоритм а изложим в виде последовательности выполняем ых шагов. Шаг n Действия выполняемые шагом 1 Объявление значений ПВЫП ( v ), v V равны м Т. Текущая вершина v k =11. 2 ПНАЧ (11)=ПВЫП (11)- t (11) ПНАЧ (11) стало равным 29 . 3 ПВЫП (9)=МИН ПВ ЫП (9),ПНАЧ (11) ПВЫП (9) стало ра вным 29 ПВЫП (10)=МИН ПВЫП (10),ПНАЧ (11) ПВЫП (10) стало равным 29 . 4 Текущая верши на v k =10. 5 Переход в Шаг 2. 2 ПНАЧ (10)=ПВЫП (10)-t(10) ПНАЧ (10) стало равным 24 . 3 ПВЫП (8)=МИН ПВ ЫП (8),ПН АЧ (10) ПВЫП (8) стал о равным 24 4 Текущая вершина v k =9. 5 Переход в Шаг 2. 2 ПНАЧ (9)=ПВЫП (9)- t (9) ПНАЧ (9) стало равным 24 . 3 ПВЫП (7)=МИН ПВЫП (7),П НАЧ (9) ПВЫП (7) стало равным 24 . 4 Текущая вершина v k =8. 5 Переход в Шаг 2. 2 ПНАЧ (8)=ПВЫП (8)- t (8) ПНАЧ (8) стало равным 12 . 3 ПВЫП (6)=МИН ПВЫП (6),ПНАЧ (8) ПВЫП (6) стало равным 12 . 4 Текущая вершина v k =7. 5 Переход в Шаг 2. 2 ПНАЧ (7)=ПВЫП (7) - t (7) ПНАЧ (7) стало равным 17 . 3 ПВЫП (6)=МИН ПВЫП (6),ПНАЧ (7) ПВЫП (6) стало равным 12 . 4 Текущая вершин а v k =6. 5 Переход в Шаг 2. 2 ПНАЧ (6)=ПВЫП (6)- t (6) ПНАЧ (6) стало равным 5 . 3 ПВЫП (2)=МИН ПВЫП (2),ПНАЧ (6) ПВЫП (2) стало равным 5 . 4 Текущая вершина v k =5. 5 Переход в шаг 2. 2 ПНАЧ (5)=ПВЫП (5)- t (5) ПНАЧ (5) стало равным 24 . 3 ПВЫП (4)=МИН ПВЫП (4),ПН АЧ (5) ПВЫП (4) стало равным 24 . 4 Текущая вершина v k =4. 5 Переход в Шаг 2. 2 ПНАЧ (4)=ПВЫП (4)- t (4) ПНАЧ (4) стало равным 14 . 3 ПВЫП (3)=МИН ПВЫП (3),ПНАЧ (4) ПВЫП (3) стало равным 14 . 4 Текущая вершина v k =3. 5 Переход в Шаг 2. 2 ПНАЧ (3)=ПВЫП (3)- t (3) ПНАЧ (3) стало равным 11 . 3 ПВЫП (2)=МИН ПВЫП (2),ПНАЧ (3) ПВЫП (2) стало равным 5 . 4 Текущая вершина v k =2. 5 Переход в Шаг 2. 2 ПНАЧ (2)=ПВЫП (2)- t (2) ПНАЧ (2) стало равным 0 . 3 ПВЫП (1)=МИН ПВЫП (1),ПНАЧ (2) ПВЫП (1) стало равным 0 . 4 Текущая вершина v k =1. 5 Переход в Шаг 2. 2 ПНАЧ (1)=ПВЫП (1)- t (1) ПНАЧ (1) стало равным 0 . 3 Переход в Шаг 4. 4 Переход в Шаг 6. 6 Конец работы а лгоритма , выдача значений времени наиболее по зднего начала и выполнения работ. Дадим таблицу результатов рабо ты алгоритма с результатами предыдущего алгоритма и сосчитаем резерв времени для каждой работы по формуле PE 3 EPB ( v )=П HA Ч ( v )- PHA Ч ( v ) или РЕЗЕРВ (v)=ПВЫП (v)-РВЫП (v). Рабо ты РНАЧ РВЫП ПНАЧ ПВЫП Резерв 1 0 0 0 0 0 2 0 5 0 5 0 3 5 8 11 14 3 4 8 18 14 24 10 5 18 23 24 29 5 6 5 12 5 12 0 7 12 19 17 24 7 8 12 24 12 24 0 9 19 24 24 29 5 10 24 29 24 29 0 11 29 29 29 29 0 Из таблиы видно , что критическими работами являются 1, 2, 6, 8, 10, 11, которые и образуют в сети G критический путь . Расчеты выполнены при Т =29. П ример 3: Проект водоснабжения и на ружной канализации при застройки квартала по ул . Токарей-Синяева в г . Екатеринбурге. n Наименование работ ы Предшеству-ющие работы Время вы-полнения t ( v k ) 1. Начало проекта (фиктивн . Работа ) Нет 0 2. Разработка грунта экс каваторами с ковшом 0.5 м 3 с погрузкой на автомобили-самосвалы. 1 16 3. Зачистка дна и стенок с выкидкой грунта. 2 10 4. Монтаж водопроводных колодцев 1 32 5. Монтаж плит перекрытий из легкого бет она. 3 21 6. Пробивка в бетонных стенах и полах отверсти й. 5 5 7. Оклейка плит р убероидом и гидроизолом на нефтебитуме в 1 слой. 4,5 14 8. Заделка сальников при проходе труб че рез фундаменты или стены подвалов. 5 10 9. Монтаж скоб. 6 7 10. Устройство стяжек цементных. 9 5 11. Конец проекта . ( фиктивн . Работ а ) 7,8,10 0 Рис 3. Проект водоснабжения и наружной канализации при з астройки квартала по ул . Токарей-Синяева в г . Екатеринбурге. Найдем значения наиболее раннего начала и выполн ения работ проекта посредств ом алгоритма 1. Работу алгоритма изложим в виде последовательности выполняемых шагов. Шаг n Действи я выполняемые шагом 1 Объявление значени й РНАЧ ( v ) и РВЫП ( v ), v V равным нулю. Текущая вершина v k =1 . 2 Вершин предшествующей первой нет . Значение РНАЧ (1)=РВЫП (1)+ t (1). 3 Текущая вершина v k =2. 4 Переход в Шаг 2. 2 РНАЧ (2)=МАКС РВЫП (1),РНАЧ (2) РНАЧ (2) стало равным 0 РВЫП (2)=РНАЧ (2)+ t (2) РВЫП (2) стало равным 16 . 3 Текущая вершина v k =3. 4 Переход в Шаг 2. 2 РНАЧ (3)=МАКС РВЫП (2),РНАЧ (3) РНАЧ (2) ст ало равным 16 РВЫП (3)=РНАЧ (3)+ t (3) РВЫП (3) стало равным 26 . 3 Текущая вершина v k =4. 4 Переход в Шаг 2. 2 РНАЧ (4)=МАКС РВЫП (1),РНАЧ (4) РНАЧ (4) стало равным 0 РВЫП (4)=РНАЧ (4)+ t (4) РВЫП (4) стало ра вным 32 . 3 Текущая вершина v k =5. 4 Переход в Шаг 2. 2 РНАЧ (5)=МАКС РВЫП (3),РНАЧ (5) РНАЧ (5) стало равным 26 РВЫП (5)=РНАЧ (5)+ t (5) РВЫП (5) стало равным 47 . 3 Текущая вершина v k =6. 4 Переход в Шаг 2. 2 РНАЧ (6)=МАКС РВЫП (5),РНАЧ (6) РНАЧ (6) ст ало рав ным 47 РВЫП (6)=РНАЧ (6)+ t (6) РВЫП (6) стало равным 52 . 3 Текущая вершина v k =7. 4 Переход в Шаг 2. 2 РНАЧ (7)=МАКС РВЫП (5),РНАЧ (7) РНАЧ (7) ст ало равным 47 РВЫП (7)=РНАЧ (7)+ t (7) РВЫП (7) стало равным 61 . 3 Текущая вершина v k =8. 4 Переход в Шаг 2. 2 РН АЧ (8)=МАКС РВЫП (5),РНАЧ (8) РНАЧ (8) стало равным 47 РВЫП (8)=РНАЧ (8)+ t (8) РВЫП (8) стало равным 57 . 3 Текущая вершина v k =9. 4 Переход в Шаг 2. 2 РНАЧ (9)=МАКС РВЫП (6),РНАЧ (9) РНАЧ (9) ст ало равным 52 РВЫП (9)=РНАЧ (9)+ t (9) РВЫП (9) стало равным . 3 Тек ущая ве ршина v k =10. 4 Переход в Шаг 2. 2 РНАЧ (10)=МАКС РВЫП (9),РНАЧ (10) РНАЧ (10) ст ало равным 59 РВЫП (10)=РНАЧ (10)+ t (10) РВЫП (10) стало равным 64 . 3 Текущая вершина v k =11. 4 Переход в Шаг 2. 2 РНАЧ (11)=МАКС РВЫП (7),РНАЧ (11) РНАЧ (11) ст ало равным 61 РНАЧ (11)=МАКС РВЫП (8),РНАЧ (11) РНАЧ (11) стало рвным 61 РНАЧ (11)=МАКС РВЫП (10),РНАЧ (11) РНАЧ (11) стало равным 64 РВЫП (11)=РНАЧ (11)+ t (11) РВЫП (11) стало равным 64 . 3 Переход в Шаг 5. 5 Конец работы алгоритма , выдача значе ний наиболее раннего нач ала и выполне ния работ. Таблица результатов работы алг оритма. n 1 2 3 4 5 6 7 8 9 10 11 РНАЧ ( v) 0 0 16 0 26 47 47 47 52 59 64 Р ВЫП ( v ) 0 16 26 32 47 52 61 57 59 64 64 Получили , что минимальное время , требуемое для выполнения проекта равно Т =РВЫП (11), Т =64. Теперь найдем посредством алгоритма 2 значение времени наиболее позднего начала и выполнения работ . Работу алгорит ма изложим в виде последовательности выполняе мых шагов. Шаг n Действия выполняемые шагом 1 Объявление значений ПВЫП ( v ), v V равны м Т. Текущая вершина v k =11. 2 ПНАЧ (11)=ПВЫП (11)- t (11) ПНАЧ (11) стало равным 64 . 3 ПВЫП (7)=МИН ПВЫП (7),ПНАЧ (11) ПВЫП (7) стало равным 64 ПВЫП (8)=МИН ПВЫП (8),ПНАЧ (11) ПВЫП (8) стало равным 64 ПВЫП (10)=МИН ПВЫП (10),ПНАЧ (10) ПВ ЫП (9) стало равным 64 . 4 Текущая верши на v k =10. 5 Переход в Шаг 2. 2 ПНАЧ (10)=ПВЫП (10)- t (10) ПНАЧ (10) стал о равным 59 . 3 ПВЫП (9)=МИН ПВЫП (9),ПНАЧ (10) ПВЫП (9) стало равным 59 . 4 Текущая вершина v k =9. 5 Переход в Шаг 2. 2 ПНАЧ (9)=ПВЫП (9)- t (9) П НАЧ (9) стало ранвым 52 . 3 ПВЫП (6)=МИН ПВЫП (6),ПНАЧ (9) ПВЫП (6) стало равным 52 . 4 Текущая вершина v k =8. 5 Переход в Шаг 2. 2 ПНАЧ (8)=ПВЫП (8)- t (8) ПНАЧ (8) стало равным 54 . 3 ПВЫП (5)=МИН ПВЫП (5),ПНАЧ (8) ПВЫП (5) стало равным 54 . 4 Текущая вершина v k =7. 5 Переход в Шаг 2. 2 ПНАЧ (7)=ПВЫП (7)- t (7) ПНАЧ (7) стало равным 50 . 3 ПВЫП (5)=МИН ПВЫП (5),ПНАЧ (7) ПВЫП (5) стало равным 50 ПВЫП (4)=МИН ПВЫП (4),ПНАЧ (7) ПВЫП (4) стало равным 50 . 4 Текущая вершина v k =6. 5 Переход в Шаг 2. 2 ПНАЧ (6)=ПВЫП (6)- t (6) ПНАЧ (6) стало равным 47 . 3 ПВЫП (5)=МИН ПВЫП (5),ПНАЧ (6) ПВЫП (5) стало равным 47 . 4 Текущая вершина v k =5. 5 Переход в Шаг 2. 2 ПНАЧ (5)=ПВЫП (5)- t (5) ПНАЧ (5) стало равным 26 . 3 ПВЫП (3)=МИН ПВЫП (3),ПНАЧ (5) ПВЫП (3) стало равным 26 . 4 Текущая в е ршина v k =4. 5 Переход в Шаг 2. 2 ПНАЧ (4)=ПВЫП (4)- t (4) ПНАЧ (4) стало равным 18 . 3 ПВЫП (1)=МИН ПВЫП (1),ПНАЧ (4) ПВЫП (1) стало равным 18 . 4 Текущая вершина v k =3. 5 Переходв Шаг 2. 2 ПНАЧ (3)=ПВЫП (3)- t (3) ПНАЧ (3) стало равным 16 . 3 ПВЫП (2)=МИН ПВЫП (2),ПНАЧ (3) ПВЫП (2) стало равным 16 . 4 Текущая вершина v k =2. 5 Переход в Шаг 2. 2 ПНАЧ (2)=ПВЫП (2)- t (2) ПНАЧ (2) стало равным 0 . 3 ПВЫП (1)=МИН ПВЫП (1),ПНАЧ (2) ПВЫП (1) стало равным 0 . 4 Текущая вершина v k =1. 5 Переход в Шаг 2. 2 ПНАЧ (1)=ПВЫП (1)- t (1) ПНАЧ (1) стало равным 0 . 3 Переход в Шаг 4. 4 Переход в Шаг 6. 6 Конец работы а лгоритма , выдача значений времени наиболее по зднего начала и выполнения работ. Дадим таблицу результатов рабо ты алгоритма с результатами предыдущего алгор итма и сосч итаем резерв времени для каждой работы по формуле PE 3 EPB ( v )=П HA Ч ( v )- PHA Ч ( v ) или РЕЗЕРВ (v)=ПВЫП (v)-РВЫП (v). Рабо ты РНАЧ РВЫП ПНАЧ ПВЫП Резерв 1 0 0 0 0 0 2 0 16 0 16 0 3 16 26 16 26 0 4 0 32 18 50 32 5 26 47 26 47 0 6 47 52 47 52 0 7 47 61 50 64 3 8 47 57 54 64 10 9 52 59 52 59 0 10 59 64 59 64 0 11 59 64 64 64 0 Из таблицы видно , что критическими работами являются 1, 2, 3, 5, 6, 9, 10, 11, которые и образуют в сети G критический путь . Расчеты выполнены при Т =64. Литература : 1. Асанов М . О . “Ди скретная оптими зация” , УралНАУКА , Екатеринбург 1998.

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Экономико-математическое моделирование
91Экономическая теория

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

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

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

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


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