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


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


139

Прямолинейный способ определения верхней границы оптимального цикла заключается в том, чтобы выбрать какой-либо полный цикл и подсчитать его длину. Например, полный цикл 1-2-3-4-5-1 (выбран произвольно) дает общую длину 10 + 5 + 7+ 4+ 3 = 29. (Можно получить лучшее значение верхней границы, если взять другой полный цикл. Помните, что наименьшая верхняя граница - цель поиска методом ветвей и границ.)

Вычисленные нижняя и верхняя границы показывают, что длина оптимального полного цикла лежит в интервале от 15 до 29. Подзадачи, дающее решение с длиной цикла больше 29, отбрасываются как "не оправдавшие надежд".

Чтобы исключить частичные циклы в задаче узла 1, надо "разбить" эти частичные циклы путем принудительного приравнивания переменных х , задающих эти циклы, нулю. Частичный цикл 1-3-1 можно разбить, если положить х13 = 0 или х31 = О (одновременно только одну переменную). Аналогично частичный цикл 2-5-4-2 можно разбить, если ввести ограничения х2Ь = 0, х54 = 0 или xi2 = 0. Каждое из подобных ограничений порождает отдельную ветвь дерева подзадач (и, конечно, отдельную подзадачу). Важно заметить, что нет необходимости разбивать все имеющиеся частичные циклы - достаточно исключить только один частичный цикл. Причина этого в том, что введение в задачу нового ограничения автоматически влияет на значения всех переменных этой задачи, что создает "благоприятные" условия для формирования полного цикла. На основании этого аргумента обычно разбивают один частичный цикл, наименьший по количеству составляющих его дуг, поскольку это приводит к меньшему количеству новых ветвей в дереве подзадач.

Выбирая для удаления короткий цикл 1-3-1, получаем на дереве подзадач две ветви, определяемые условиями х13 = 0 и х31 = 0, выходящие из узла 1. Новые задачи о назначениях строятся путем удаления из последней задачи переменной ветвления (т.е. х]3 или х31), что уменьшает размер подзадач. Другой путь построения подзадач (который дает тот же самый результат при решении этих подзадач и который сохраняет их размер) заключается в том, чтобы назначить переменным ветвления значения расстояний, равные бесконечности. Например, в подзадаче с ограничением х13 = 0 расстоянию d13 присваивается значение °°.

Из двух имеющихся подзадач решим сначала задачу с условием х13 = 0 (узел 2 на рис. 9.14) - порядок решения подзадач произвольный. Получаем решение 2=17, которое формирует два частичных цикла (2-5-2) и (1-4-3-1). Эту подзадачу разбиваем на две путем введения дополнительных ограничений х25 = 0 и х52 = 0 так же, как это сделано в задаче узла 1.

Теперь имеется три нерешенные подзадачи, которые соответствуют узлам 3, 4 и 5 на рис. 9.14. Произвольно выбираем для решения подзадачу узлаЗ. В исходных данных для этой подзадачи устанавливаем dl3 = °° и d2b = °°. Ее решение дает 2 = 21 с полным циклом 1-4-5-2-3-1. Поскольку получено решение с полным циклом, то ветвления в узле 3 не будет.

Решение подзадачи узла 3 позволяет улучшить значение верхней границы, г = 21, оптимальной длины полного цикла. Это означает, что любая нерассмотренная подзадача, для которой можно показать, что она даст решение, превышающее или равное 21, можно отбросить и не рассматривать.

Из нерассмотренных подзадач 4 и 5 выбираем для решения подзадачу 4. Для ее решения в данных исходной задачи о назначениях положим dn = °° и d52 = °°. Получаем решение этой подзадачи с 2 = 19 и полным циклом 1-4-2-5-3-1. Это решение предлагает новую верхнюю границу г = 19.



Осталась нерассмотренной только подзадача узла 5. Для ее решения в данных исходной задачи о назначениях положим d31 = °°. Получаем решение с г = 16 и полным циклом 1-3-4-2-5-1, а также новую верхнюю границу г = 16.

Нерассмотренных подзадач не осталось. Оптимальным циклом будет цикл 1-3-4-2-5-1 с длиной в 16 миль.

Сделаем замечание. Излишне длинная последовательность решения подзадач 1-» 2-> 3-> 4-> 5, приведшая к оптимальному решению в данном примере, снова показывает основной недостаток метода ветвей и границ - невозможно предсказать последовательность выбора подзадач, ведущую к оптимальному решению наиболее коротким путем. Например, если первой была бы решена подзадача узла 5, то это дало бы значение верхней границы, равное 16. Это автоматически отбрасывает возможные подзадачи, порождаемые в узле 2.

Конечно, существуют эвристические подходы, позволяющие помочь в "предсказании" последовательности подзадач, ведущей к оптимальному решению наиболее эффективным путем. Например, после того, как определены все ветви (подзадачи), выходящие из некоторого узла дерева подзадач, первой решается та подзадача, у которой исключаемой переменной хц соответствует наибольшее значения расстояния dtj среди рассматриваемых подзадач. Если воспользоваться этим правилом в данном примере, то после определения подзадач узла 1 первой надо решать подзадачу 5, что приведет к оптимальному решению всего за два этапа. (Первый этап - решение подзадачи 5, второй этап - решение подзадачи 2, которое дает худшее значение целевой функции (г = 17), чем существующая на тот момент верхняя граница, равная 16.)

УПРАЖНЕНИЯ 9.3.2

1. Решите задачу примера9.3.2, начав с удаления частичного цикла 2-5-4-2. При прохождении дерева подзадач примените следующие правила.

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

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

2. Решите методом ветвей и границ задачу из упражнения 9.3.1.1.

3. Решите методом ветвей и границ задачу из упражнения 9.3.1.2.

4. Решите методом ветвей и границ задачу из упражнения 9.3.1.3.

9.3.2. Применение метода отсекающих плоскостей для решения задачи коммивояжера

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



вится в соответствие непрерывная неотрицательная переменная и,. Тогда дополнительные ограничения имеют вид

и, - ц. + nxIJ<n - 1, i = 2, 3, n,j = 2, 3, п, j.

Эти ограничения, добавленные в исходную задачу о назначениях, автоматически удаляют из решения частичные циклы, оставляя все полные циклы.

Пример 9.3.3

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

~ 13 21 26"

10 °о 29 20

30 20 оо 5

Л2 30 7 «.

Данная задача коммивояжера формализуется как соответствующая задача о назначениях плюс следующие дополнительные ограничения, исключающие из решения частичные циклы. Все переменные xtj двоичные, все переменные ut неотрицательные. Задача решается как частично-целочисленная задача линейного программирования.

•*"13

X Л21

•*-24

«1

и»

<3

<3

<3

<3

<3

<3

Оптимальное решение этой задачи (полученное с помощью TORA) следующее:

и2 = 0, и3 = 1, ut = 2, х12 = х23 = х34 = х41 = 1, длина полного цикла = 59.

Это решение формирует полный цикл 1-2-3-4-1. Решение удовлетворяет всем дополнительным ограничениям (проверьте!).

Чтобы показать, что частичные циклы не удовлетворяют дополнительным ограничениям, рассмотрим решение с частичными циклами (1-2-1) и (3-4-3): х12 = х21 = 1, хм = ха = 1. Теперь рассмотрим ограничения 4 и 6, представленные в выше приведенной таблице.

4x34 + u3-u4<3,

4x43-u3 + u4<3.

Подставив в эти выражения значения х34 = х"43 = 1 и сложив их, получим невыполнимое неравенство 8 < 6, что говорит о невозможности частичного цикла 3-4-3.

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

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