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


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


133

Последовательность решения подзадач, показанная на рис. 9.8 (ЛПО, ЛП2, ЛП4, ЛПЗ, ЛП6, ЛП5, ЛП1), является наихудшей; тем не менее, она встречается на практике. Этот пример указывает на основную слабость метода ветвей и границ: как выбирать следующую подзадачу для исследования и как выбирать для нее переменную ветвления?

В процессе решения, представленного на рис. 9.7, мы случайно наткнулись на хорошую нижнюю границу значений целевой функции на самой первой подзадаче ЛП1, что позволило прозондировать ЛП2 без детальных исследований и закончить вычисления. По существу, мы завершили вычисления, решив лишь одну подзадачу. В процессе решения, представленном на рис. 9.8, мы были вынуждены исследовать семь подзадач, и лишь тогда завершились вычисления метода ветвей и границ. Хотя имеются эвристические соображения, позволяющие "угадать", какая из ветвей может привести к улучшенному решению задачи ЦЛП (см., например, [3]), не существует строгой теории, которая всегда обеспечивала бы надежные результаты.

Теперь сформулируем алгоритм метода ветвей и границ в общем случае. Предположим, что рассматривается задача максимизации. Зададим нижнюю границу оптимального значения целевой функции z задачи ЦЛП равной Положим i = 0.

Шаг 2. (Зондирование и определение границы). Выбираем i-ю подзадачу линейного программирования ЛГО для исследования. Решаем ЛШ и зондируем ее, при этом возможна одна из трех ситуаций.

a) Оптимальное значение целевой функции задачи ЛГО не может улучшить текущей нижней границы.

b) ЛГО приводит к лучшему допустимому целочисленному решению, чем текущая нижняя граница.

c) ЛГО не имеет допустимых решений. Возможны два варианта.

a) Если задача ЛГО прозондирована, нижняя граница изменяется только при условии, что найдено лучшее решение задачи ЦЛП. Если все подзадачи прозондированы, необходимо закончить вычисления: оптимальным решением задачи ЦЛП является то, которое соответствует текущей нижней границе, если такая существует. Иначе положить i = i + 1 и повторить шаг 1.

b) Если задача ЛГО не прозондирована, переходим к шагу 2 для выполнения ветвления.

Шаг 2. Ветвление. Выбираем одну из целочисленных переменных х:, оптимальное значение xf которой в оптимальном решении задачи ЛГО не является

целым числом. Исключаем из пространства допустимых решений область [ху]<Х;<[х]] + 1 (где [у]- наибольшее целое, не превосходящее v) путем

формирования двух подзадач ЛП, которые соответствуют ограничениям

хИ +

Положим i = i + 1 и переходим к шагу 1.



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

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

УПРАЖНЕНИЯ 9.2.1

1. Решите задачу ЦЛП из примера 9.2.1 методом ветвей и границ, начиная с переменной х2 как переменной ветвления. Решите подзадачи с помощью программы TORA, используя опцию MODIFY (Изменить) для задания верхней и нижней границ. Начните с решения подзадачи, включающей ограничение х, ГхЛ .

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

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

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

2х, + 5х2 < 9, 4х, + 2х2 < 9, х,, х2 > О и целые.

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

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

5х, + 7х2<35, 4х, + 9х2 < 36, xv х2>Ои целые.

с) Максимизировать z = х, + х2 при ограничениях

2х, + 5х2< 16, б*, + 5х2 < 27, xv х2 > 0 и целые.

d) Минимизировать z = 5х, + 4х2

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

Зх, + 2х2>5, 2х, + Зх2 > 7, xv х2 > 0 и целые.

е) Максимизировать z = 5х, + 7х2 при ограничениях

2х, +х2< 13, 6х, + 9х2<41, х,, х2>Оицелые.



3. Решите задачи из предыдущего упражнения, предполагая, что на переменную Xj не налагается условие целочисленности.

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

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

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

Юх, + 10х2 < 9, 10х, + 5х2> 1, хр х2 > 0 и целые.

5. Решите следующую задачу методом ветвей и границ. Максимизировать z = 18х, + 14х2 + 8х3 + 4х4

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

15х, + 12х2 + 7х3 + 4х4 + хь < 37, х,, х2, х3, х4, х5 = 0 или 1.

9.2.2. Метод ветвей и границ в системе TORA

Модуль целочисленного программирования системы TORA позволяет интерактивно генерировать деревья подзадач в методе ветвей и границ. Чтобы воспользоваться этой возможностью, в выходном окне модуля целочисленного программирования выберите опцию User-guided В&В (Учебный режим метода ветвей и границ). В этом окне представлена вся информация, необходимая для создания дерева подзадач. На рис. 9.9 показан внешний вид окна, в котором представлен корень N10 дерева подзадач, которое соответствует задаче ЛПО на рис. 9.6 (файл ch9ToraB&BEx9-2-l.txt). Каждый узел определяется двумя цифрами, перед которыми стоит буква N. Левая цифра определяет строку таблицы, в которой находится узел, а правая цифра представляет порядковое значение в пределах той же строки. Например, обозначение N10 на рис. 9.9 указывает, что узел 0 расположен в строке 1 (это единственный узел в этой строке). В программе TORA может быть не более 10 подзадач в одной строке. Но помните, что в автоматическом режиме нет каких-либо ограничений на количество генерируемых подзадач.

Далее следует выбрать переменную ветвления, щелкнув на любом из узлов, помеченных "х?". Эти узлы выделены зеленым цветом. Если щелкнуть на записи одного узла над областью, где расположено дерево, появится соответствующее решение. Как показано на рис. 9.10, из решения для узла N10 видно, что х, = 3,75 и х2 = 1,25. Также следует обратить внимание на то, какие переменные ограничены целыми значениями. Щелчок на любой из переменных приведет к автоматическому созданию двух подзадач, которые соответствуют выделенной переменной ветвления. На рис. 9.11 показан результат выбора х, в качестве переменной ветвления в узле N10. К дереву были добавлены узлы N20 (соответствует новому ограничению х, < 3) и N21 (соответствует новому ограничению х, > 4). В узле N20 получено целочисленное решение, поэтому он считается прозондированным. Прозондированные узлы выделяются красным или пурпурным цветом. Пурпурный цвет используется тогда, когда в прозондированном узле была достигнута текущая нижняя граница значения целевой функции, что в данном случае произошло с узлом N20. Узел N21 пока не прозондирован. Поэтому щелчок на нем приведет к созданию следующих узлов в строке 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]