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


[Старт] [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]


78

Пример 6.3.1. Замена оборудования

Компания по прокату автомобилей разрабатывает план по обновлению парка своих машин на следующие пять лет (2001-2005 гг.). Каждый автомобиль должен проработать не менее одного и не более трех лет. В следующей таблице приведена стоимость замены автомобиля в зависимости от года покупки и срока эксплуатации.

Стоимость замены (долл.) в зависимости от срока эксплуатации

Год покупки

2001

4000

5400

9800

2002

4300

6200

8700

2003

4800

7100

2004

4900

Задачу можно сформулировать как сетевую с пятью узлами с номерами от 1 до 5, соответствующими годам 2001-2005. Из узла 1 (2001 год) дуги идут только к узлам 2, 3 и 4, поскольку автомобиль может эксплуатироваться не менее одного и не более трех лет. Дуги из других узлов интерпретируются аналогично. Стоимости дуг равны стоимостям замены автомобилей. Решение задачи эквивалентно нахождению кратчайшего пути между узлами 1 и 5.

На рис. 6.9 показана построенная сеть. С помощью программы TORA находим кратчайший путь 1->3->5 (показан на рис. 6.9 жирными линиями). Это решение означает, что автомобили, приобретенные в 2001 году (узел 1), будут эксплуатироваться 2 года, до 2003 года (узел 3), затем они будут заменены новыми, которые будут эксплуатироваться до конца 2005 года. Общая стоимость замены составит 5400 + 7100= 12 500 долл.

9800

Рис. 6.9. Задача замены оборудования как задача поиска кратчайшего пути

6.3.1. Практические примеры задачи поиска кратчайшего пути



Пример 6.3.2. Самый надежный маршрут

М-р Разумник ежедневно ездит на работу на автомобиле. Закончив в свое время полный курс по теории исследования операций, он легко определил самый короткий путь от дома до работы. К сожалению, данный маршрут усиленно патрулируется нарядами полиции, и автомобиль Разумника часто останавливают за превышение скорости (как ему кажется, не обоснованно). Таким образом, самый короткий путь оказался не самым быстрым. Поэтому м-р Разумник планирует разработать новый маршрут, на котором он имел бы самую высокую вероятность не быть остановленным полицией. Схема сети дорог, по которой м-р Разумник может добраться от дома до работы, показана на рис. 6.10. На этой же схеме приведены вероятности не быть остановленным для каждого сегмента сети дорог. Вероятность не быть остановленным на всем пути следования автомобиля Разумника равна произведению вероятностей не быть остановленным на каждом сегменте выбранного пути. Например, вероятность не быть остановленным на маршруте 1-»3-»5-»7 равна 0,9 х 0,3 х 0,25 = 0,0675. Таким образом, м-ру Разумнику необходимо решить задачу выбора маршрута, который максимизировал бы вероятность не быть остановленным.

Рис. 6.10. Сетевая модель

Эту задачу можно сформулировать как задачу нахождения кратчайшего пути, если вместо вероятностей использовать логарифмы вероятностей. Тогда произведение вероятностей преобразуется в сумму логарифмов вероятностей: если plk=p1* р2х ... хрк - вероятность не быть остановленным на маршруте 1->2->к, тогда

log plk = log р, + log р2 + ... + log рк.

С точки зрения математики задача максимизации вероятности р1к эквивалентна задаче максимизации величины \ogplk. Поскольку \ogpn<0, задача максимизации величины \ogplk эквивалентна задаче минимизации -logpu. Заменив на рис. 6.10 вероятности рк на величины -\ogpk, получаем сеть (рис. 6.11), к которой можно применить алгоритм определения кратчайшего пути.

Рис. 6.11. Сетевая модель для задачи поиска кратчайшего пути



С помощью программы TORA находим кратчайший путь для полученной сети: 1-»3-»5-»7 с соответствующей "длиной" пути 1,1707 (=-logp17). Таким образом, максимальная вероятность не быть остановленным равнар17 = 0,0675.

Пример 6.3.3. Головоломка о трех бидонах

Восьмилитровый бидон заполнен некой жидкостью, а два бидона емкостью 5 и 3 литра пусты. Необходимо разделить 8 литров жидкости на две равные части, используя только три имеющихся бидона. Какое минимальное количество переливаний из бидона в бидон надо сделать, чтобы достичь желаемого результата?

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

В этой сетевой модели каждый узел будет соответствовать объемам жидкости в 8-, 5- и 3-литровом бидонах. Начальным узлом будет (8, 0, 0), а конечным - (4, 4, 0). Новый узел получается из текущего при однократном переливании жидкости из одного бидона в другой.

На рис. 6.12 показаны различные маршруты, ведущие от начального узла (8, 0, 0) к конечному (4, 4, 0). Таким образом, наша головоломка сведена к задаче определения кратчайшего пути между узлами (8, 0, 0) и (4, 4, 0).

Рис. 6.12. Головоломка о трех бидонах как задача вычисления кратчайшего пути

Оптимальное решение, показанное в нижней части рис. 6.12, требует семи переливаний из бидона в бидон.

УПРАЖНЕНИЯ 6.3.1

1. Создайте заново модель замены оборудования из примера 6.3.1, предполагая, что автомобиль до замены должен эксплуатироваться не менее 2-х и не более 4-х лет. Стоимость замены автомобилей в 2001-2005 годах приведена в следующей таблице.

[Старт] [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]