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


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


138

Метод полного перебора контуров практически применим лишь для задач малой размерности. Например, сеть с 11 узлами имеет 10! = 3 628 800 контуров. Следовательно, требуется более эффективный подход к решению таких задач.

Определим переменные хц равными 1, если узел ; достигается из узла г, и 0 в противном случае. Необходимым условием для контура (цикла) является то, что узел I связывается лишь с одним узлом и узел j достигается лишь из одного узла. Считая М достаточно большим положительным числом, мы можем записать задачу предприятия, производящего краски, следующим образом.

Минимизировать г = МхББ + 10хБЖ + ПхБЧ + 15x£/f + 20хЖБ + Мхжж + 19хжч + )хЧБ + 44д

при ограничениях

+ 18хжк + 50хЧБ + 44хчж + Мхчч + 25хчк + 4ЬхКБ + 40хкж + 20хкч + Мхкк

ХББ ХБЖ ХБЧ ХБК ~~ ХЖБ ХЖЖ ХЖЧ ХЖК ~ >

хЧБ + хчж + хчч + хчк - 1,

ХКБ ХКЖ ХКЧ ХКК ~ ХББ ХЖБ ХЧБ ХКБ = 1»

х 4- х 4- х 4- X ~ 1 хБЧ -Ь хжч + xt/1J + хкч - 1,

•""ВЙ ХЖК ХЧК~~ ХКК ~ 1

хц = 0 или 1 для всех i и

решение должно быть контуром (полным циклом).

Использование константы М в целевой функции гарантирует, что производство краски одного цвета не будет повторяться подряд.

УПРАЖНЕНИЯ 9.3.1

1. Менеджер проектов имеет 10 сотрудников, которые работают над шестью проектами, причем каждый работает одновременно над несколькими проектами, как показано в следующей таблице.

Сотрудники



Менеджер должен встретиться с каждым из 10 сотрудников один раз в неделю для обсуждения их проблем. Беседа с каждым из них длится примерно 20 минут, т.е. на разговоры со всеми сотрудниками уходит 3 часа 20 минут. Предлагается проводить встречи менеджера с группами сотрудников, работающих над одним и тем же проектом, чтобы уменьшить суммарное время, которое тратится на совещания. Менеджер планирует составить график обсуждения проектов таким образом, чтобы уменьшить движение в офисе, т.е. сократить число сотрудников, входящих и выходящих из комнаты для совещаний. В какой последовательности необходимо рассматривать проекты?

2. Продавец книг, проживающий в городе А, один раз в месяц должен посетить своих четырех клиентов, которые проживают в городах Б, В, Г и Д соответственно. Приведенная ниже таблица содержит расстояния в милях между различными городами.

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

3. Пусть в предыдущем упражнении города Б, В, Г и Д обозначены через 1,2,3 и 4, а город А разделен на два, которые обозначены через 0 и 5. Пусть маршрут продавца книг начинается в городе 0, проходит (в некотором порядке) через города 1, 2, 3 и 4 и заканчивается в городе 5. Определим переменную vt для города i (i = 0, 1, 5), которая удовлетворяет условиям 0 < и( < 5. Пусть xtj = 1, если в маршруте город j следует за городом г, и 0 в противном случае. Покажите, что ограничения

у,-уу + 5х,.<4, г = 0,1.....4, j = 1, 2, 5,

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

9.3.1. Применение метода ветвей и границ для решения задачи коммивояжера

Вначале алгоритм ветвей и границ применяется к задаче о назначениях, соответствующей данной задаче коммивояжера. Если полученное оптимальное решение образует полный цикл, то на этом вычисления заканчиваются. В противном случае в задачу необходимо ввести ограничения, удаляющие частичные циклы. Это создает ряд подзадач, которых в общем случае столько же, сколько переменных образуют один частичный цикл. В каждой подзадаче одна из таких переменных устанавливается равной нулю (напомним, что переменные, ассоциированные с каким-либо циклом, имеют единичные значения). Решения этих подзадач могут либо сформировать, либо нет полный цикл. Если такой цикл сформирован в какой-либо подзадаче, то оптимальное значение целевой функции этой подзадачи дает верхнюю границу длины полного цикла. Если же подзадача не формирует полный



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

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

Пример 9.3.2

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

Решение начальной задачи о назначениях (полученное с помощью TORA) следующее:

2 = 15, (х13 = x3l = 1), (хг5 = хи - xi2 = 1), все остальные переменные равны 0.

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

z = 15 (1-3-1)(2-5-4-2)

z=17 (2-5-2)(1-4-3-1)

z= 16 (1-3-4-2-5-1)

z = 21 (1-4-5-2-3-1)

z=19 (1-4-2-5-3-1)

Рис. 9.14. Дерево подзадач решения задачи коммивояжера методом ветвей и границ

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