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


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


134

Рис. 9.10. Выбор переменной ветвления



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

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

УПРАЖНЕНИЯ 9.2.2

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

Минимизировать у

при выполнении условий

2(х, + х2 + ...+xls) + y=\b. Все переменные двоичные.



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

a) Сколько подзадач было решено прежде, чем было найдено оптимальное решение?

b) Сколько подзадач было решено прежде, чем была проверена оптимальность найденного решения?

2. Дана следующая задача ЦЛП.

Максимизировать z - 18х, + 14х2 + 8х3 при выполнении условий

15х, + 12х2+ 7х3 < 43,

х1( х2, х3 - неотрицательные целые.

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

3. Вернитесь к задаче из упражнения 2. Преобразуйте эту задачу в задачу ЦЛП с двоичными переменными, затем решите ее в программе TORA в автоматическом режиме. Сравните размеры деревьев подзадач в каждом из упражнений.

4. В следующей задаче ЦЛП с двоичными переменными с помощью TORA сгенерируйте дерево подзадач.

Максимизировать z = Зх, + 2х2 - 5х3 - 2х4 + Зхь

при выполнении условий

х, + х2 + х3 + 2х4 + х6 < 4, 7х, + Зх3 - 4х4 + Зх5 < 8, ИхбХг + Зх.-ЗхЗ, хр х2, х3, х4, х5 = О или 1.

5. Используя программу TORA в режиме пошагового выполнения, покажите, что следующая задача не имеет допустимого решения.

Максимизировать z = 2х, + х2

при выполнении условий

10х, + 10х2 < 9, Юх, + 5х2> 1, х,, х2 = 0 или 1.

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

Максимизировать z = х, + 2х2 - Зх3

при выполнении условий

Зх, + 4х2 - х3 < 10, 2х, - Зх2 + 4х3 < 20, х,, х2 неотрицательные целые, х3>0.

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