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


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


135

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

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

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

20х1 + 15л:.!-л:з<10, 12x1 + 3x2 + 4x3<13, х„ х2, х3>0.

8. Преобразуйте представленную ниже задачу в частично-целочисленную, после чего в системе TORA сгенерируйте для нее дерево подзадач. Каким будет оптимальное решение?

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

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

j-jc1 + 10jc2 - 3xs > 15, 2х1+х2 + х3<10, xv х2, х3 > 0.

9.2.3. Метод отсекающих плоскостей

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

Пример 9.2.2

Продемонстрируем применение метода отсекающих плоскостей для решения следующей задачи ЦЛП.

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

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

-хх +3х2<6, 7х1+х3<35, х,, х2> 0 и целые.

Данный метод путем добавления отсечений (отсекающих плоскостей) преобразует пространство допустимых решений соответствующей задачи линейного программирования в выпуклый многогранник, вершина которого, соответствующая оптимуму, является целочисленной и представляет решение исходной задачи. На рис. 9.12 показан пример двух таких отсечений. Мы начинаем с оптимального решения непрерывной задачи линейного программирования (хх, х2) = (4,5, 3,5) и z = 66,5. Затем прибавляем отсечение I, которое вместе с ограничениями исходной задачи линейного программирования приводит к оптимальному решению (х,, х2) = (4 у , 3) с z = 62. После этого прибавляется отсечение II, которое вместе с отсечением I и исходными ограничениями приводит к оптимальному решению (xv х2) - (4, 3) с z = 58. Последнее решение является полностью целочисленным, как и требуется.



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

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

Рис. 9.12. Последовательность построения отсечений

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

При дополнительных переменных хъ и х4 для ограничений 1 и 2 оптимальная симплекс-таблица исходной задачи имеет следующий вид.

Базис

Решение

63/22

31/22

66,5

7/22

1/22

-1/22

3/22

Оптимальным непрерывным решением является х1 = 4,5, х2 = 3,5, хг = 0, xt = О иг = 66,5. Целочисленное отсечение получается в предположении, что все переменные задачи являются целочисленными. Поскольку коэффициенты исходной целевой функции являются целочисленными, то и значение г, соответствующее целочисленному решению, должно быть целочисленным.

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

z-уравнение: z + x3+±х4 = 66,

х2-уравнение: хг+хг +*4 =3-

Xj-уравнение: х, -Jx, + х4 =4.



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

Z+ 22 ХЪ + 22*4 = 2 (пРоизводяЩая z-строка).

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

Разложение коэффициентов производящей z-строки приводит к следующему уравнению.

При переносе всех целочисленных слагаемых в левую часть уравнения, а всех дробных слагаемых в правую часть получаем следующее.

z + 2V*4-66 = l-g*3-£*4.

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

i-lir -S-r =1 2 22 3 22 4 2

• - " \22*3 + 22 4/

Поскольку х3, xt > О, выражение в скобках является неотрицательным. Поэтому величина \-хг -£*4 > будучи целочисленной, не может превышать 1/2. Следовательно, необходимое условие целочисленности можно записать следующим образом.

i-iix --2-х <0 2 22 3 22 4-и

Это и есть дробное отсечение, порожденное z-строкой. Нетрудно убедиться, что ранее найденное оптимальное непрерывное решение хх = 4,5, х2 = 3,5, х3 = О, х4 = 0 не удовлетворяет отсечению. Действительно, так как х3 = xt = О, отсечение не удовлетворяется (оно приводит к неравенству 1/2 <0). Следовательно, если мы присоединим отсечение к конечной симплекс-таблице, то оптимальное решение новой симплекс-таблицы будет "двигаться" в направлении выполнения ограничения целочисленности. Можно таким же образом построить отсечение, исходя из производящей л-строки или лг2-строки. Рассмотрим сначала jCj-строку. Имеем

Xi~22X3 + 22ХА = 4 2 (пРоизволяЩая *f строка). Операция разложения приводит к уравнению

ч+(-,+ёМ0+4К-К)-

Соответствующим отсечением является

21 .. 3 ... 1

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