Промежуточные вычислении

Имя Узел

м N2 N3 N4 N5

Поток

40 50 0 -30 -60

Спрос От В Уд стоимость

40 50

о

-30 60

Поиск решения

Установить целевую ячейку: Равной: С максимальному значение

^р минимальному значению Изменяя ячейки:

|$В$1в

|$В$20:$В$39 Ограничения.

|$В$20:$В$Э9 <= $С$20:$С$39

значению:

31 Предположить ~~3 Добавить I

Выполнить

Закрыть

Параметры

Изменить ]

Удалить

Восстановить 1 Справка I

Рис. 6.49. Поиск потока минимальной стоимости в Excel

Глава 6. Сетевые модели

ch6SolverMinCostCapacitatedNetwork.xls). Матрица пропускных способностей запи­сана в диапазоне N6:W15.⁶ Незаполненные ячейки матрицы пропускных способно­стей показывают, что соответствующие дуги имеют бесконечную пропускную спо­собность. Нулевые значения пропускных способностей вводятся для несуществующих дуг. Матрица удельных стоимостей записана в диапазоне В6:К15. Здесь также нулевые значения вводятся для несуществующих дуг.

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

В диалоговом окне средства Поиск решения целевая ячейки, изменяемые ячейки и ограничения уже заданы. На рис. 6.49 видно, что изменяемые ячейки составляют диапазон В20:В39, а ограничения задаются как F19:F23=G19:G23 (баланс потоков для всех узлов) и В20:В39<=С20:С39 (ограничения пропускных способностей дуг).

Решение N1-N2 = 5, N1-N4 = 35, N2-N3 = 25, N2-N5 = 30, N3-N5 = 25 и N4-N5 = 5, показанное на рис. 6.49, дает общую стоимость потока, равную 490 долл.

УПРАЖНЕНИЯ 6.5.4

1. Решите следующие задачи с помощью средства Поиск решения.

a) Задача из упражнения 6.5.3.3.

b) Задача из упражнения 6.5.3.4.

c) Задача из упражнения 6.5.3.7.

d) Задача из упражнения 6.5.3.8.

На основе сетевых моделей разработано множество методов планирования, со­ставления временных расписаний и управления проектами. Наиболее известные — метод критического пути (Critical Path Method — СРМ), а также система планиро­вания и руководства программами разработок (Program Evaluation and Review Technique — PERT). В этих методах проекты рассматриваются как совокупность некоторых взаимосвязанных процессов (видов деятельности, этапов или фаз вы­полнения проекта), каждый из которых требует определенных временных и других ресурсов. В методах jCPM и PERT проводится анализ проектов для составления временных графиков распределения фаз проектов. На рис. 6.50 в обобщенной фор­ме показаны основные этапы реализации этих методов. На первом этапе определя­ются отдельные процессы, составляющие проект, их отношения последовательности (т.е. какой процесс должен предшествовать другому) и длительность. Далее проект представляется в виде сети, показывающей последовательность процессов, состав­ляющих проект. На третьем этапе на основе построенной сети выполняются вычис­ления, в результате которых составляется временной график реализации проекта.

6.6. МЕТОДЫ СЕТЕВОГО ПЛАНИРОВАНИЯ

Сеть

Временной график

]—»п Вычисления

Время

н, I—I

Рис. 6.50. Основные этапы выполнения методов СРМ и PERT

На рис. 6.49 строки от 11 до 15 и столбец К скрыты для экономии места.

6.6. Методы сетевого планирования 299

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

6.6.1. Построение сети проекта

Каждый процесс проекта обозначается в сети дугой, ориентированной по на­правлению выполнения проекта. Узлы сети (также называемые событиями) уста­навливают отношения предшествования среди процессов проекта.

Построение сети проекта основано на следующих правилах.

Правило 1. Каждый процесс в проекте представляется одной и только од­ной дугой.

Правило 2. Каждый процесс идентифицируется двумя концевыми узлами.

На рис. 6.51 показано, как с помощью фиктивного процесса можно представить два параллельных (конкурирующих) процесса А и В. По определению фиктивный процесс (который на схеме сети обычно обозначается пунктирной дугой) не поглощает времен­ных или других ресурсов. Вставив фиктивный процесс одним из четырех способов, показанных на рис. 6.51, мы получаем возможность идентифицировать процессы А и В по крайней мере одним уникальным концевым узлом (как требует правило 2).

Рис. 6.51. Представление двух параллельных процессов с помощью фиктивного процесса

Правило 3. Для поддержания правильных отношений предшествования при включении в сеть любого процесса необходимо ответить на сле­дующие вопросы.

1. Какой процесс непосредственно предшествует текущему?

2. Какой процесс должен выполняться после завершения текущего процесса?

3. Какой процесс конкурирует (выполняется параллельно) с текущим?

Ответы на эти вопросы, возможно, потребуют включить в сеть фиктивные процессы, чтобы правильно отобразить последовательность выполнения процессов. Предполо­жим, например, что четыре процесса должны удовлетворять следующим условиям.

1. Процесс С должен начаться сразу после завершения процессов А и В.

2. Процесс Е должен начаться непосредственно после завершения процесса В.

Глава 6. Сетевые модели

На рис. 6.52, а показано неправильное представление наших процессов, так как из него следует, что процесс Е должен начаться после завершения как про­цесса В, так и А. На рис. 6.52, б показано, как с помощью фиктивного процесса D разрешить эту коллизию.

а) б)

Рис. 6.52. Использование фиктивного процесса для правильного отображения последовательного выполнения процессов

Пример 6.6.1

Издатель имеет контракт с автором на издание его книги. Ниже представлена по­следовательность (упрощенная) процессов, приводящая к реализации проекта из­дания книги. Необходимо разработать сеть для этого проекта.

Процесс Предшествующий Длительность

процесс (недели)

А	Прочтение рукописи редактором	—
В	Пробная верстка отдельных страниц книги	—
С	Разработка обложки книги	—
D	Подготовка иллюстраций	—
Е	Просмотр автором редакторских правок и сверстанных страниц	А, В
F	Верстка книги (создание макета книги)	Е
G: Проверка автором макета книги	F
Н	Проверка автором иллюстраций	D
I:	Подготовка печатных форм	G, Н
J:	Печать и брошюровка книги	С, I

На рис. 6.53 показана сеть, представляющая взаимосвязь процессов данного проек­та. Фиктивный процесс (2, 3) введен для того, чтобы "развести" конкурирующие процессы А и В. Номера узлов сети возрастают в направлении выполнения проектов.

Рис. 6.53. Сеть проекта для примера 6.6.1

6.6. Методы сетевого планирования

УПРАЖНЕНИЯ 6.6.1

1. Постройте сеть проекта, содержащего процессы, помеченные латинскими буквами от А до L, с учетом следующих отношений предшествования.

a) Первые процессы А, В и С проекта могут выполняться параллельно.

b) Процессы А и В предшествуют процессу D.

c) Процесс В предшествует процессам Е, F и Н.

d) Процессы F и С предшествуют процессу G.

e) Процессы Е и Н выполняются перед процессами I и J.

f) Процессы С, D, F и J предшествуют процессу К.

g) Процесс К выполняется перед процессом L.

h) Проект заканчивается после завершения процессов I, G и L.

2. Постройте сеть проекта, содержащего процессы, помеченные латинскими буквами от А до Р, с учетом следующих отношений предшествования.

a) Первые процессы А, В и С проекта могут выполняться параллельно.

b) Процессы D, Е и F следуют за процессом А.

c) Процессы I и G выполняются после процессов В и D.

d) Процесс Н следует за процессами С и G.

e) Процессы К и L выполняются после процесса I.

f) Процесс J следует за процессами Е и Н.

g) Процессы М и N следуют за процессом F, но не могут начаться до завер­шения процессов Е и Н.

h) Процесс О следует за процессами М и I.

i) Процесс Р — за процессами J, L и О.

j) Проект заканчивается после завершения процессов К, N и Р.

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

4. Допустим, в предыдущем упражнении одновременно с земляными работами может быть выполнено 10% работ по созданию водопроводно-канализационной сети здания, но в любом случае эти работы должны на­чаться до заливки фундаментных блоков бетоном. Кроме того, по 5% этих работ можно выполнить при достижении 95% готовности каждого фунда­ментного блока. Постройте сеть строительных работ.

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

6. В следующей таблице приведены работы (процессы), выполняемые при строительстве нового каркасного дома. Разработайте сеть этих работ.

Глава 6. Сетевые модели

	Процесс	Предшествующий процесс	Длительность (дни)
А	Очистка строительного участка	—
В	Завоз оборудования	—
С	Земляные работы	А
D	Заливка фундамента	С
Е	Наружные сантехнические работы	В, С
F	Возведение каркаса дома	D
G	Прокладка электропроводки	F
Н	Создание перекрытий	G
1:	Создание каркаса крыши	F
J:	Внутренние сантехнические работы	Е, Н
К	Покрытие крыши
L:	Наружные изоляционные работы	F, J
М	Вставка окон и наружных дверей	F
N	Обкладка дома кирпичом	L, М
О	Штукатурка стен и потолков	G, J
Р	Облицовка стен и потолков	О
Q	Изоляция крыши	1, Р
R	Окончание внутренних отделочных работ	Р
S	Окончание наружных отделочных работ	1, N
Т:	Ландшафтные работы	S
Компания готовит бюджет производства нового изделия. В следующей таб-
лице представлены этапы подготовки бюджета и их длительность. Постройте
сеть этапов подготовки бюджета.
	Процесс	Предшествующи й процесс	Длительность (дни)
А:	Прогнозирование объема продаж	—
В:	Изучение рынка конкурирующих товаров	—
С	Доводка изделия	А
D	Подготовка производственного плана	С
Е:	Оценка стоимости производства	D
F:	Определение отпускной цены	В, Е
G	Подготовка бюджета	Е, F

8. Расширение участка дороги требует переноса воздушной электролинии (длиной 1700 футов). В следующей таблице приведены этапы выполнения работ по замене электролинии. Постройте соответствующую сеть.

6.6. Методы сетевого планирования

Предшествующий Длительность процесс (дни)

А:	Определение объема работ	—
В:	Извещение пользователей о временном отключении электросети	А	0,5
С:	Подвозка материалов и оборудования	А
D:	Предварительные работы	А	0,5
Е:	Заготовка опор и материалов	С, D
F:	Развозка опор	Е	3,5
G:	Определение нового местоположения опор	D	0,5
Н:	Разметка местоположения опор	G	0,5
1:	Земляные работы для установки новых опор	Н
J:	Установка новых опор	F, 1
К:	Ограждение старой линии	F, 1
L:	Прокладка новых проводов	J, К
М:	Обустройство новой линии	L
N:	Натяжка проводов	L
О:	Подрезка деревьев	D
Р:	Отключение старой электролинии	В, М, N, О	0,1
Q:	Подключение новой электролинии	Р	0,5
R:	Уборка территории	Q
S:	Удаление проводов старой линии	Q
Т:	Удаление опор старой линии	S
U:	Возврат материалов и оборудования	R, Т

9. В следующей таблице показаны этапы покупки нового автомобиля. Построй­те соответствующую сеть.

	Процесс	Предшествующий Длительность процесс (дни)
А:	Принятие окончательного решения о покупке автомобиля
В:	Поиск потенциального покупателя имеющегося автомобиля	А
С:	Составление списка желаемых моделей машин	А
D:	Исследование желаемых моделей	С
Е:	Консультации у автомехаников	С
F:	Сбор рекламных материалов продавцов автомобилей	С
G:	Обобщение полученной информации	D, Е, F
Н:	Выбор трех наиболее подходящих моделей	G
I:	Знакомство "в натуре" с выбранными моделями	Н
J:	Сбор финансовой информации	Н
К:	Выбор одного автомобиля	I, J
L:	Выбор продавца автомобиля	К
М:	Выбор автомобиля желаемого цвета	L
N:	Повторная дорожная проверка выбранной модели	L
О:	Покупка нового автомобиля	В, М, N

Глава 6. Сетевые модели

6.6.2. Метод критического пути

Конечным результатом применения метода критического пути (СРМ) будет по­строение временного графика выполнения проекта (см. рис. 6.50). Для этого прово­дятся специальные вычисления, в результате чего получаем следующую информацию.

1. Общая длительность выполнения проекта.

2. Разделение множества процессов, составляющих проект, на критические и некритические.

Процесс является критическим, если он не имеет "зазора" для времени своего начала и завершения. Таким образом, чтобы весь проект завершился без задержек, необходимо, чтобы все критические процессы начинались и заканчивались в строго определенное время. Для некритического процесса возможен некоторый "дрейф" времени его начала, но в определенных границах, когда время его начала не влияет на длительность выполнения всего проекта.

Для проведения необходимых вычислений определим событие как точку на вре­менной оси, где завершается один процесс и начинается другой. В терминах сети, собы­тие — это сетевой узел. Нам понадобятся также следующие определения и обозначе­ния.

□ — самое раннее возможное время наступления события j, Aj — самое позднее возможное время наступления события j, D_tJ — длительность процесса (i, j).

Вычисление критического пути включает два этапа (прохода). При проходе вперед вычисляются самые ранние времена наступления событий, а при проходе назад — самые поздние времена наступления тех же событий.

Проход вперед. Вычисления начинаются в узле 1 и заканчиваются в послед­нем узле п.

Начальный шаг. Полагаем П₁ = 0; это указывает на то, что проект начинает­ся в нулевой момент времени.

Основной шаг j. Для узла j определяем узлы р, q, v, непосредственно свя­занные с узлом j процессами (р, j), (q, j), (v,j), для кото­рых уже вычислены самые ранние времена наступления со­ответствующих событий. Самое раннее время наступления события j вычисляется по формуле

= тах{Ц, + D_pj, U_q + D_qi, ...,□„ + DJ.

Проход вперед завершается, когда будет вычислена величина □„ для узла п.

По определению величина П_у равна самому длинному пути (длительности) от начала проекта до узла (события) j.

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

Начальный шаг. Полагаем Д_л = это указывает, что самое раннее и самое позднее времена для завершения проекта совпадают.

Основной шаг j. Для узла j определяем узлы р, q, v, непосредственно свя­занные с узлом j процессами (j, р), (j, q), (/', v), для кото­рых уже вычислены самые поздние времена наступления со­

6.6. Методы сетевого планирования

ответствующих событий. Самое позднее время наступления события j вычисляется по формуле

Д_; = тт{Д, - D_jp, Д, - D_jq, .... Д„ - DJ.

Проход назад завершается при вычислении величины Д, для узла 1.

Процесс (i, j) будет критическим, если выполняются три условия.

1. Д, = Ц

2. Д, = Ц

3. Д,-Д, = Ц-Ц=Д,

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

Пример 6.6.2

Найдем критический путь для сети проекта, показанной на рис. 6.54. Длитель­ность всех процессов дана в днях.

А

Обозначения: Проход вперед: [ZF" Проход назад: Л«-Критический путь: (7)—

-А

Конец прохода. назад

Начало f

прохода

вперед

Начало прохода назад

^Ч^ Конец прохода вперед

Рис. 6.54. Проходы вперед и назад для проекта из примера 6.6.2

Проход вперед

Узел 1. Полагаем Dj = 0.

Узел 2. = +D₁₂ = 0 + 5 = 5.

Узел 3. □, = max{D, + D₁₃, + DJ = тах{0 + 6, 5 + 3} = 8. Узел 4. П₄ = П₂ +D_2i = 5 + 8 = 13.

Узел 5. = тах{П₃ + D₈₅, П₄ + DJ = тах{8 + 2, 13 + 0} = 13. Узел 6. □, = тах{П₃ + D_M, П₄ + D„, D_s + DJ =

= тах{8 + 11,13 + 1, 13 + 12} = 25. Таким образом, расчеты показывают, что проект можно выполнить за 25 дней.

Глава 6. Сетевые модели

Проход назад

Узел 6. Полагаем Д₆ = П₆ = 25. Узел 5. Д₅ = Д₆ - D₅₆ = 25 - 12 = 13.

Узел 4. Д₄ = гшп{Д₆ - D₄₆, Д₅ - DJ = min{25 -1,13-0} = 13. Узел 3. Д₃ = гшп{Д₆ - D₃₆, Д₆ - DJ = min{25 - 11, 13 - 2} = 11. Узел 2. Д₂ = min{A₄ - D₂₄, Д₃ - DJ = min{13 - 8, 11 - 3} = 5. Узел 1. Д, = min{A₃ - D_J3, Д₂ - D₁₂} = min{ll - 6, 5 - 5} = 0. Вычисления без ошибок всегда приводят к результату Д, = 0.

Результаты вычислений, выполняемых при проходах вперед и назад, показаны на рис. 6.54. Правила определения критических процессов показывают, что крити­ческий путь составляют процессы 1->2->4->5—>6, т.е. этот путь проходит от начального узла 1 до конечного узла 6. Сумма длительностей критических про­цессов (1, 2), (2, 4), (4, 5) и (5, 6) равна длительности всего проекта (т.е. 25 дней). Отметим, что процесс (4, 6) удовлетворяет первым двум условиям критического пути (Д₄ = □„ = 13 и Д₆ = □„ = 25), но не удовлетворяет третьему условию - П₄ # D₄₆). По­этому данный процесс не является критическим.

УПРАЖНЕНИЯ 6.6.2

1. Найдите критический путь для сети проекта, показанной на рис. 6.55.

Рис. 6.55. Сеть проекта для упражнения 1

2. Найдите критические пути для сетей проектов, показанных на рис. 6.56.

3. Найдите критический путь в задаче из упражнения 6.6.1.6.

4. Найдите критический путь в задаче из упражнения 6.6.1.8.

5. Найдите критический путь в задаче из упражнения 6.6.1.9.

6.6. Методы сетевого планирования

Проект А Проект Б

Рис. 6.56. Сети проектов для упражнения 2

6.6.3. Построение временного графика

В этом разделе показано, как на основе данных, полученных расчетным путем в предыдущем разделе, строится временной график последовательного выполнения проекта. Мы уже знаем, что □, для процесса (i, указывает на самое раннее время начала этого процесса, а Д. — на самое позднее время завершения процесса. Таким образом, пара величин (□,, Д^) ограничивает максимальный интервал времени, в течение которого может выполняться процесс (i, /).

Построение предварительного графика. Метод построения предварительного временного графика выполнения проекта покажем на следующем примере.

Пример 6.6.3

Построим временной график проекта из примера 6.6.2 (см. рис. 6.54). Предварительный временной график проекта можно начертить, используя макси­мальные интервалы выполнения каждого процесса. В результате получим график, представленный на рис. 6.57. Сделаем два замечания.

1. Критические процессы (показаны на графике сплошными линиями) располага­ются последовательно друг за другом без временных зазоров и перекрытий. Та­ким образом, их суммарная длительность равна длительности выполнения всего проекта (в данном случае 25 дней).

2. Некритические процессы (показаны на графике пунктирными линиями) пред­ставлены максимальными интервалами выполнения, которые превышают ре­альную длительность выполнения этих процессов. Поэтому необходимо каким-то образом определиться с началом выполнения этих процессов.

Как выбрать время начала выполнения некритического процесса? Обычно предпо­читают начинать некритические процессы по возможности в самый ранний срок. В этом случае остается запас времени (остаток максимального интервала выполне­ния), который можно использовать для решения неожиданно возникших во время выполнения процесса проблем. Вместе с тем при необходимости можно перенести начало выполнения какого-либо процесса. Допустим, если в нашем примере во время выполнения процессов Е и F (см. рис. 6.57) используется одно и то же обору­дование, причем в каждый момент времени его можно задействовать только для одного процесса, значит, можно исключить временное наложение этих процессов, начав процесс F после завершения Е.

Глава 6. Сетевые модели

А-5

D-8

В-6

С-3

ь­—I

Е-2