назад Оглавление вперед


[Старт] [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] [92] [93] [94] [95] [96] [97] [98] [99] [ 100 ] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]


100

Узел j

Самый длинный путь Среднее пути

Стандартное

P(z<Kj)

отклонение пути

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 (Планирование проекта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

tpp»- mu»niitti 11 - ! in ia

сф1квш0-звНамуд таи mptjltntiim

PROJECT PLA*IN*G PE*T

So*d Output Option-1

HbH fl

>

TltW: Ew pi* 6 6.-6

PAHtf AN AND STD. DEVIA1 -1 N

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. Для всех узлов проекта определите вероятности того, что эти узлы будут достигнуты без задержек.



Проект А

Проект Б

Процесс

(а, т, Ь)

Процесс

(а, т, Ь)

Процесс

(а, т, Ь)

Процесс

(а, т, Ь)

(5, 6, 8)

(3, 4, 5)

(1.3, 4)

(12, 13, 14)

(1.3, 4)

(4, 8, 10)

(5, 7, 8)

(10, 12, 15)

(2, 4, 5)

(5, 6, 8)

(6, 7, 9)

(8, 10, 12)

(4, 5, 6)

(9, 10, 15)

(1,2, 3)

(7, 8, 11)

(7, 8, 10)

(4, 6, 8)

(3, 4, 5)

(2, 4, 8)

(8, 9, 13)

(3, 4, 5)

(7, 8, 9)

(5, 6, 7)

(5, 9, 19)

(Ю, 15, 20)

ЛИТЕРАТУРА

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



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

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

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

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.

[Старт] [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] [92] [93] [94] [95] [96] [97] [98] [99] [ 100 ] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]