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

Пример 6.6.4

Вычислим запасы времени для некритических процессов в сети проекта из приме­ра 6.6.2 и на основе этих расчетов построим окончательный временной график проекта.

Общие и свободные запасы времени некритических процессов представлены в сле­дующей таблице. Такие расчеты можно проводить непосредственно на сети проек­та, как показано на рис. 6.54.

Некритический Длительность Общий запас времени Свободный запас времени

процесс процесса (TF) (FF)

В (1, 3) 6 11-0-6 = 5 8-0-6 = 2

С (2,3) 3 11-5-3 = 3 8-5-3 = 0

Е(3,5) 2 13-8-2 = 3 13-8-2 = 3

F(3,6) 11 25-8-11 =6 25-8-11 =6

Н(4,6) 1 25-13-1 = 11 25-13 -1 = 11

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

Правило "красного флажка" следует применять только к процессам В и С, по­скольку для них FF < TF. Оставшиеся процессы (Е, F и Н) имеют FF — TF, поэтому они могут выполняться в любое время внутри своих максимальных интервалов времени выполнения.

Рассмотрим процесс В, помеченный "красным флажком". Поскольку для этого процесса TF= 5 дней, он может начаться в любой день из интервала 0-5 дней от на­чала выполнения всего проекта (см. рис. 6.57). Но если FF — 2 дня, то, поскольку процесс В начнется в 0-, 1- или 2-й день от начала выполнения проекта, это не ока­жет никакого влияния на последующие процессы Е и F. Однако, если процесс В начнется в (2 + d)-ft день (2 + d < 5), начало выполнения процессов Е и F необходимо сдвинуть от самого раннего срока их начала (8-й день от начала выполнения проек­та) на величину, не меньше d; только при таком условии не нарушатся отношения следования между процессами В, Е и F.

Для помеченного "красным флажком" процесса С имеем FF'= 0. Это означает, что любой сдвиг начала выполнения этого процесса должен сопровождаться таким же (не меньшим) сдвигом начала выполнения процессов Е и F.

Программа TORA обладает средствами реализации метода СРМ и построения временных графиков. Чтобы воспользоваться этими средствами, в меню Main Menu выберите команду Project PlanningOCPM-Critical Path Method (Планирование проектаОМетод критического пути). В выходном окне доступна опция СРМ Cal­culations (Вычисления метода СРМ), после выбора которой поэтапово выполня­ются проходы вперед и назад, а также вычисляются запасы времени. Для соз­дания и работы с временным графиком нужно выбрать опцию СРМ Ваг Chart (Временная диаграмма метода СРМ).

На рис. 6.59 показано выходное окно TORA с результатами вычислений мето­дом СРМ задачи из примера 6.6.2 (файл ch6ToraCPMEx6-6-2.txt). Для вычислений в пошаговом режиме используйте кнопку Next Step (Следующий этап).

На рис. 6.60 представлен временной график проекта из примера 6.6.2, для по­строения которого следует выбрать опцию СРМ Ваг Chart. По умолчанию все кри­тические процессы автоматически размещаются в расписании как можно рань­ше. Используя раскрывающиеся списки в нижней левой части экрана, можно исследовать, как будет влиять на расписание задержка выполнения некритиче­ских процессов. Это влияние, а также соответствующие пояснения будут показа­ны непосредственно на графике. Например, если задержка начала выполнения процесса В будет более 2 временных единиц, то задержка начала выполнения по­следующих процессов Е и F будет равна разнице между задержкой и запасом времени процесса В. Так, если задержка начала выполнения процесса В будет равна 3 единицам, то запас времени для этого процесса будет равен 2. Следова­тельно, задержка выполнения процессов Е и F будет равна как минимум 3-2 = 1 временной единице. Эта ситуация показана на рис. 6.60.

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

Рис. 6.60. Временной график проекта из примера 6.6.2

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

УПРАЖНЕНИЯ 6.6.3

1. Дан процесс (i, j) длительностью £>,., самый ранний срок его начала — Ц и самый поздний срок его завершения — Д.. Определите самый ранний срок завершения этого процесса и самый поздний срок его начала.

2. Чему равны общий и свободный запасы времени критических процессов?

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

a) TF= 10, FF= 10, D = 4.

b) TF=10,FF=5,D = 4.

c) TF = 10,FF = 0, £> = 4.

4. В задаче из примера 6.6.4 на основе значений запасов времени ответьте на следующие вопросы.

a) Пусть процесс В начался в 1-й день от начала выполнения всего проекта, а процесс С — в 5-й день (см. рис. 6.57). Каков самый ранний срок начала процессов Е и F?

b) Пусть процесс В начался на 3-й день от начала выполнения проекта, а процесс С — на 7-й. Каков самый ранний срок начала процессов Е и F?

c) Может ли процесс В начаться после 6-го дня от начала выполнения проекта?

5. Пусть в проекте из примера 6.6.2 (рис. 6.54) длительность процессов В и F возросла до 20 и 25 дней соответственно.

a) Определите критический путь.

b) Найдите общие и свободные запасы времени для некритических процес­сов и пометьте при необходимости их "красными флажками".

c) Пусть процесс А начался на 5-й день от начала выполнения всего проекта. Оп­ределите по возможности самые ранние сроки начала процессов С, D, Е и Н.

d) Предположим, для выполнения процессов F, G и Н необходимо одно и то же оборудование. Определите минимально необходимое количество этого оборудования.

6. Вычислите запасы времени и расставьте "красные флажки" процессам про­ектов, показанных на рис. 6.56. Затем постройте временные графики при со­блюдении следующих условий.

Проект А

1. Процесс (1, 5) не может начаться раньше 14-го момента времени.

2. Процессы (5, 6) и (5, 7) используют одинаковое оборудование, которое в лю­бой момент времени может использоваться только в одном процессе.

3. Все другие процессы начинаются так рано, как только возможно. Проект Б

1. Процесс (1, 3) должен начаться так рано, как только возможно, с учетом то­го, что процессы (1, 2), (1, 3) и (1, 6) используют одинаковое оборудование, которое в любой момент времени может использоваться только в одном процессе.

2. Все другие процессы начинаются так рано, как только возможно.

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

6.6.4. Формализация задачи поиска критического пути как задачи ЛП

Задача определения критического пути в сети проектов, решаемая методом СРМ, противоположна задаче вычисления кратчайшего пути (раздел 6.3) в том смысле, что здесь ищется самый длинный путь от начального узла до конечного. Можно применить формализацию задачи поиска кратчайшего пути из разде­ла 6.3.3 к задачам нахождения критического пути, решаемых метом СРМ (для краткости будем называть такие задачи задачами СРМ), следующим образом. Предположим, что в сеть в начальном узле поступает одна единица потока, которая покидает сеть в конечном узле. Обозначим

х_ц — величина потока, проходящего по дуге (£, j), соответствующей процессу (г, j), D_tj — длительность процесса (i,;'). В этих обозначениях целевая функция задачи линейного программирования за­пишется как

максимизировать г = £Д,*„

но всем процессам

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

общий входной поток = общий выходной поток.

Очевидно, что все переменные x_tj неотрицательны. Отметим, что одно из ограниче­ний избыточно.

Опять, как и в задачах поиска кратчайшего пути, для решения задачи СРМ можно применить двойственную задачу ЛП. В следующем примере покажем две формализации задачи СРМ.

Пример 6.6.5

Ниже дана формулировка задачи из примера 6.6.2 (см. рис. 6.54) в терминах се­тевых моделей линейного программирования. Отметим, что узлы 1 и 6 являются соответственно начальным и конечным узлами.

	А	В	с	D	Е	F	Фиктивный	Н	G
	Х12	*13	Х23	Х24	Х35	X36	X45	*46	Х56
Максимизировать z
Узел 1	-1	-1								= -1
Узел 2			-1	-1						= 0
Узел 3					-1	-1				= 0
Узел 4							-1	-1		= 0
Узел 5									-1	= 0
Узел 6										= 1

С помощью программы TORA было получено следующее оптимальное реше­ние: 2 = 25, х₁₂(А)= 1, x_2i(D) = 1, х₄₅(Фиктивный) = 1, x₆₆(G) = 1, все другие перемен­ные равны 0. Решение определяет следующий критический путь: А -> D -> Фиктив­ный -» G, при этом длительность проекта равна 25 дней.

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

Приведем формулировку двойственной задачи ЛП.

Минимизировать w = y₆- у_х

при выполнении условий

Уг	- Уг > 5 (А),
Уг	-г/,>б(В),
Уг	-у2>3(С),
У*	-y2>S(T>),
Уь	- У3 ^ 2(E),
Уе	- У3 > 11(F),
У,	- у4 > 0 (Фиктивный),
Уе	-у4>1(Щ,
Уе	-уъ> 12(G),

все у, не ограничены в знаке.

В формулировке двойственной задачи можно дать интересную интерпретацию двойственных переменных. Пусть y_t — время узла отсчитываемое от некоторого момента времени, общего для всех узлов. В этом случае w = у_е - у₁ будет представ­лять длительность проекта. Каждое ограничение связано с определенным процес­сом, они устанавливают отношения предшествования между различными процес­сами. Например, неравенство у₂-у_л > 5 эквивалентно неравенству у₂>у_] + 5, которое показывает, что для узла 2 время у₂ не может быть меньшим времени у, + 5. Минимум целевой функции определяет наименьший промежуток времени, при котором будут выполняться все ограничения. В этой интерпретации двойст­венные переменные могут принимать только неотрицательные значения. Время начала выполнения проекта у, естественно установить равным нулю. В этом случае целевую функцию можно переписать как w = у_&. Задание значения у₁ = О также со­гласуется с тем, что одно из первоначальных условий лишнее.

С учетом того, что переменные могут принимать только неотрицательные зна­чения, в программе TORA было получено следующее оптимальное решение двойст­венной задачи: w = 25, г/, = 0, у₂ = 5, у₃ = 11, у₄ = 13, у_ъ = 13, у_в = 25. Из полученного решения видно, что длительность проекта составляет w = 25 дней.

В соответствии с ограничениями, которые выполняются строго в виде равенств, определяем критические процессы: А -> D -> Фиктивный -> G. Из того факта, что, если ограничение удовлетворено в виде равенства, то соответствующее значение двойственной задачи должно быть положительным, в данном случае вытекает, что значения переменных прямой задачи СРМ (поскольку мы решаем двойственную), ассоциированные с такими ограничениями, будут равны 1. На этом основании можно заполнить следующую таблицу.

Ограничение А	В	С	D	Е	F	Фиктивный	G	Н
Переменная прямой задачи 1

Отсюда получаем, что путь А —» D —» Фиктивный -> G является критическим. Заметьте, что положительное значение переменной прямой задачи всегда равно 1, поскольку задержка в один день для любого критического процесса приведет к уве­личению продолжительности проекта на один день (напомним, что двойственные переменные интерпретируются как стоимость единицы ресурса, см. раздел 4.3.1).

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

УПРАЖНЕНИЯ 6.6.4

1. Используя формализацию линейного программирования, определите крити­ческий путь для сети проекта, показанного на рис. 6.55.

2. Используя формализацию линейного программирования, определите крити­ческий путь для сетей проектов, которые представлены на рис. 6.56.

6.6.5. Сети PERT

Метод PERT отличается от СРМ тем, что здесь длительность процессов характе­ризуется тремя оценками.

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

2. Наиболее вероятная оценка времени т, когда предполагается, что выполне­ние процесса будет происходить нормально.

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

Любая возможная оценка времени выполнения процесса будет лежать в интер­вале (а, Ь). Поэтому оценка времени т также должна лежать в этом интервале. На основе этих оценок среднее время D выполнения процесса и дисперсия v вычисля­ются по формулам

— a + Am + b (b-a\²

Все вычисления метода СРМ, которые описаны в разделах 6.6.2 и 6.6.3 выпол­нимы, если заменить значения длительностей D процессов оценками D.

Теперь можно определить вероятность того, что узел модели будет достигнут в заранее запланированное время S_f. Пусть е.— время наискорейшего достижения узла Поскольку длительности выполнения процессов, которые ведут от начального узла к узлу j, — случайные величины, то е_; также является случайной величиной. Предположив, что все процессы в сети статистически независимы, можно определить среднее (математическое ожидание) М{е_;) и дисперсию var{e_;} следующим образом. Если существует только один путь от начального узла к узлу j, то среднее является суммой ожидаемых длительностей D выполнения всех процессов, входящих в этот путь, а дисперсия равна сумме дисперсий v тех же процессов. С другой стороны, если к узлу ведет более одного пути, то до того, как будут вычислены среднее и диспер­сия, необходимо найти вероятностное распределение длительности выполнения про­цессов, которые составляют самый длинный путь. Эта задача достаточно сложная, поскольку она эквивалентна задаче, вычисляющей распределение максимума не­скольких случайных величин. Для упрощения этой задачи среднее МЦ} и дисперсия var{e^} вычисляются только для пути, для которого сумма ожидаемой длительности выполнения процессов максимальна. Если несколько путей имеют равные значения среднего, то выбирается тот, для которого дисперсия больше, поскольку этот путь от­ражен наименее четко, и поэтому будет вычислена более общая оценка вероятностей.

После того как будет вычислено среднее М{е} и дисперсия var^}, вероятность того, что узел будет достигнут в запланированное время S, можно вычислить по формуле

\е -Ще } S.-M{e }} P{'jZS,} = P\; '< ; \ = P{z<K,},

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

где 2 — случайная величина, имеющая стандартное нормальное распределение, _к _ 5,-М{е,.}

Случайная величина z имеет среднее 0 и стандартное отклонение 1 (см. прило­жение В). В данном случае использование нормального распределения оправдано тем, что е. является суммой независимых случайных переменных. Согласно цен­тральной предельной теореме (см. раздел 12.5.4) величина e_f приближенно распре­делена по нормальному закону.

Пример 6.6.6

Рассмотрим проект из примера 6.6.2. Чтобы не повторять вычисление критиче­ского пути, значения а, т и Ь, представленные в таблице ниже, были выбраны так, чтобы D. - D_y для всех i и /.

Процесс i-j (а, т, Ь) Процесс i-j (а, т, Ь)

А 1-2 (3,5,7)	Е	3-5	(1.2, 3)
В 1-3 (4,6,8)	F	3-6	(9,11,13)
С 2-3 (1,3,5)	Н	4-6	(1,1.1)
D 2-4 (5,8,11)	G	5-6	(Ю, 12, 14)
Средние D:j и дисперсии Уц для различных процессов даны в следующей табли-
це. Заметьте, что для фиктивного процесса (а, т, Ъ) —	(0, 0, 0), поэтому его среднее
и дисперсия также равны нулю.
Процесс i-j Dij Vij	Процесс	Ч	Dij V/j
А 1-2 5 0,444	Е	3-5	2 0,111
В 1-3 6 0,444	F	3-6	11 0,444
С 2-3 3 0,444	Н	4-6	1 0,000
D 2-4 8 1,000	G	5-6	12 0,444
В таблице ниже приведены самые длинные пути (которые были определены по
средней длительности) от начального узла 1 ко всем остальным узлам, а также со-
ответствующие средние значения и дисперсии.
Узел Самый длинный путь i	Среднее пути	Стандартное отклонение пути
2 1-2	5,00		0,67
3 1-2-3	8,00		0,94
4 1-2-4	13,00		1,20
5 1-2-4-5	13,00		1,20
6 1-2-4-5-6	25,00		1,37

И наконец, в следующей таблице представлены вычисленные аналитиком значения вероятностей того, что каждый узел будет достигнут в запланирован­ное время S_tj.

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

Узел j	Самый длинный путь Среднее пути	Стандартное	S)	К/	P(z<Kj)
		отклонение пути
	1-2	5,00	0.67	5,00		0,5000
	1-2-3	8,00	0,94	11,00	3,19	0,9993
	1-2-4	13,00	1,20	12,00	-0,83	0,2033
	1-2-4-5	13,00	1,20	14,00	0,83	0,7967
	1-2-4-5-6	25,00	1,37	26,00	0,73	0,7673

Программа TORA содержит модуль для выполнения вычислений методом PERT. Чтобы им воспользоваться, из главного меню выберите команду Project PlanningoPERT-Program Evaluation & Review Technique (Планирование проекта¹^ PERT). В выходном окне для вычисления среднего и дисперсии каждого процесса надо выбрать опцию Activity Mean/Var (Среднее/дисперсия процессов). Чтобы сразу вычислить средние и дисперсии для самых длинных путей к каждому узлу сети, следует выбрать опцию PERT Calculations (Вычисления методом PERT).

На рис. 6.61 показаны результаты вычислений методом PERT, полученные в системе TORA, для примера 6.6.6 (файл ch6ToraPERTEx6-6-6.txt).

WW DiVWorkUoraP ilejVfi* loraPFR I [ хб 6 6.1st

PROJECT PLANNING PERT/CPM

ГО>.-|М|»ЦцЩ 11—■ 11 III 111] Сф|1|КВШ0-ЗВНамуд Tata MP|ltntiiM	PROJECT PLA*IN'*G PE*T
	bo**ct Output Option—1 Hb^H ■^■■^■^■fl «^^^^^^р	>
T№»: Ew pi* 6 6.-6	РА'ЧК AN AND STD. DEVIA'1 -1 N

Longest Pdlh Based on Мели Dm dtioiis

I ViewnAodty Input Dote I

Рис. 6.61. Вычисления для примера 6.6.6

УПРАЖНЕНИЕ 6.6.5

1. Ниже приведены оценки (а, т, Ь) для проектов из упражнения 6.6.2.2. Для всех узлов проекта определите вероятности того, что эти узлы будут достиг­нуты без задержек.

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

	Проект А			Проект Б
Процесс	(а, т, Ь)	Процесс	(а, т, Ь)	Процесс	(а, т, Ь)	Процесс	(а, т, Ь)
1-2	(5, 6, 8)	3-6	(3. 4, 5)	1-2	(1.3, 4)	3-7	(12, 13, 14)
1-4	(1.3, 4)	4-6	(4, 8, 10)	1-3	(5, 7, 8)	4-5	(10, 12, 15)
1-5	(2, 4, 5)	4-7	(5, 6, 8)	1-4	(6, 7, 9)	4-7	(8, 10, 12)
2-3	(4, 5, 6)	5-6	(9, 10, 15)	1-6	(1,2, 3)	5-6	(7, 8, 11)
2-5	(7, 8, 10)	5-7	(4, 6, 8)	2-3	(3, 4, 5)	5-7	(2, 4, 8)
2-6	(8, 9, 13)	6-7	(3, 4, 5)	2-5	(7, 8, 9)	6-7	(5, 6, 7)
3-4	(5, 9, 19)			3-4	(Ю, 15, 20)

ЛИТЕРАТУРА

1. Ahuja R., Magnati Т., Orlin J. Network Flows: Theory, Algorithms and Applica­tions, Prentice Hall, Upper Saddle River, N.J., 1993.

2. Bazaraa M., Jarvis J., Sherali H. Linear Programming and Network Flow, 2nd ed., Wiley, New York, 1990.

3. Evans J. R., Minieka E. Optimization Algorithms for Networks and Graphs, 2nd ed., Marcel Dekker, New York, 1992.

4. Murty K. Network Programming, Prentice Hall, Upper Saddle River, N. J., 1992.

Литература, добавленная при переводе

1. Ахо А. В., Хопкрофт Дж. Э., Ульман Дж. Д. Структуры данных и алгорит­мы. — М.: Издательский дом "Вильяме", 2000.⁷

2. Форд Л. Р., Фалкерсон Д. Р. Потоки в сетях. — М.: Мир, 1966.

КОМПЛЕКСНЫЕ ЗАДАЧИ

6.1. Любитель свежего воздуха, житель Сан-Франциско (СФ), планирует во время своего 15-дневного отпуска посетить четыре национальных парка: Йосемитский (ЙО), Йеллоустонский (ЙЕ), Гренд-Тетон (ГТ) и Маунт-Рушмор (MP). Во время путешествия, которое начнется и закончится в Сан-Франциско, он планирует посетить парки в таком порядке: СФ-»ЙО->ЙЕ->ГТ-»МР->СФ. На осмотр каждого парка отводится 2 дня. От одного парка до другого можно добраться либо самолетом, либо автомоби­лем. Если пользоваться самолетом, то перелет между любыми парками (а также между парками и Сан-Франциско) занимает примерно полдня. Ес­ли путешествовать на автомобиле, то маршрут СФ - ЙО занимает полдня, ЙО - ЙЕ — 3 дня, ЙЕ - ГТ — один день пути, ГТ - MP — два дня, и воз­вращение из MP в СФ требует 3 дня. В общем случае проезд на автомобиле дешевле перелета на самолете, но, естественно, путешествие на автомобиле занимает больше времени. Разработайте наиболее дешевый маршрут посе­щения национальных парков (т.е. определите вид транспорта на каждом

⁷ В данной книге представлены (с вычислительной точки зрения) все рассмотренные в данной главе алгоритмы. — Прим. ред.

Комплексные задачи

этапе путешествия) с учетом того, что длительность путешествия не может превышать 15 дней. В следующей таблице приведена стоимость проезда на автомобиле и перелета на самолете.

Стоимость полета в Стоимость проезда в

Из	СФ	ЙО	ЙЕ	гт	MP	СФ	ЙО	ЙЕ	гт	MP
СФ	—					—
ЙО		—					—
ЙЕ			—					—
ГТ									—
MP					—					—

6.2. Некто желает подарить большое количество ценных книг публичной библиотеке. Все книги имеют различные размеры по высоте корешка: 12, 10, 8 и 6 дюймов. Заведующий библиотекой подсчитал, что для размеще­ния книг высотой 12 дюймов необходимы полки общей длиной 12 футов, для книг высотой 10 дюймов — полки длиной 18 футов, для книг высотой 8 дюймов — полки длиной 9 футов и для книг высотой 6 дюймов — полки длиной 10 футов. Цена книжных полок состоит из фиксированной цены и цены, рассчитываемой в зависимости от суммарной длины полок, как показано в следующей таблице.

Высота полки (дюймы) Фиксированная цена (долл.) Цена (долл.) за фут длины полки

12 25 5,50

10 25 4,50

8 22 3,50

6 22 2,50

Сколько и каких полок необходимо для библиотеки, если учесть, что книги меньшего размера могут храниться на полках для книг большего размера?

6.3. Судоходной компании необходимо доставить пять партий груза из пор­тов А, В и С в порты D и Е. Сроки доставки грузов приведены в следую­щей таблице.

Партия груза	Маршрут доставки	Срок доставки (дни)
	из А в D
	из А в Е
	из В в D
	из В в Е
	из С в Е

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

Основано на материалах статьи Ravindran A. "On Compact Storage in Libraries", Opsearch, Vol. 8, No. 3, pp. 245-252, 1971.

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

	А	В	С	D	Е
А
В
С
D
Е

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

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