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

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

Пример 6.6.6

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

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

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

Программа TORA содержит модуль для выполнения вычислений методом PERT. Чтобы им воспользоваться, из главного меню выберите команду Project PlanningoPERT-Program Evaluation & Review Technique (Планирование проекта1 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

Longest Pdlh Based on Men Dm dlions

I ViewnAodty Input Dote i

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

УПРАЖНЕНИЕ 6.6.5

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

ЛИТЕРАТУРА

1. Ahuja R., Magnati Т., Orlin J. Network Flows: Theory, Algorithms and Applications, 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.7

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

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

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

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