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


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


131

ограничений. Используйте программу TORA, чтобы найти оптимальное решение, которое максимизирует целевую функцию г = 2хх + Зх2 при ограничениях, определяющих область, изображенную на рис. 9.4, а.

х2 х2

а б в

Рис. 9.4. Пространства решений для упражнения 6

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

g,(xvx2.....хп)<Ъ i = l,2, .... т.

Покажите, как это сделать.

8. Правая часть следующего ограничения может принимать одно из значений bi> Ь2> °т> т-е-

gixlt х2.....хп) < bv b2, ... или bm.

Покажите, как можно представить это ограничение.

9.2. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ

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

Шаг 1. "Ослабление" пространства допустимых решений задачи целочисленного линейного программирования путем замены любой двоичной переменной у непрерывным ограничением 0 < у < 1 и отбрасывания требования целочисленности для всех остальных переменных. В результате получается обычная задача линейного программирования.

Шаг 2. Решение задачи линейного программирования и определение ее оптимального решения.

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

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



1. Метод ветвей и границ.

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

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

9.2.1. Метод ветвей и границ

Впервые метод ветвей и границ был предложен в 1960 году А. Лэндом (A. Land) иДж. Дойгом (G. Doig) для решения полностью целочисленных и частично-целочисленных задач линейного программирования. Позднее в 1965 году Э. Бэлес (Е. Balas) разработал аддитивный алгоритм для решения задач с двоичными переменными. Этот алгоритм с вычислительной точки зрения оказался настолько прост (в основном используя только операции сложения и вычитания), что его рассматривали как возможный прорыв в методах решения задач ЦЛП общего вида.3 К сожалению, этот алгоритм не оправдал возлагаемые на него надежды. Более того, если первоначально алгоритм не был связан с методом ветвей и границ, то вскоре было установлено, что аддитивный алгоритм является частным случаем метода ветвей и границ.

В этом разделе мы представим только метод ветвей и границ и основы этого метода объясним на численном примере.

Пример 9.2.1

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

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

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

ж, + ж2< 5, Юж, + 6х2 < 45, ж,, х2> 0 и целые.

На рис. 9.5 пространство допустимых решений задачи целочисленного линейного программирования представлено точками. Соответствующая начальная задача линейного программирования (обозначим ее ЛПО) получается путем отбрасывания условий целочисленности. Ее оптимальным решением будет ж, = 3,75, ж2 = 1,25 и z = 23,75.

Поскольку оптимальное решение задачи ЛПО не удовлетворяет условию целочисленности, метод ветвей и границ изменяет пространство решений задачи линейного программирования так, что в конечном счете получается оптимальное решение задачи целочисленного линейного программирования. Для этого сначала выбирается одна из целочисленных переменных, значение которой в оптимальном решении задачи ЛПО не является целочисленным. Например, выбирая ж1 (= 3,75), замечаем,

3 Общую задачу ЦЛП можно выразить через двоичные переменные следующим образом. Любая целочисленная переменная х, значения которой не превышают конечной верхней границы и (т.е. 0 < х < и), может быть выражена через двоичные переменные с помощью представления х = 2°у0 + 2у, + 22у2 +... + 2кyt, где к - наименьшее целое число, удовлетворяющее условию 2*-1>и,а y0,y,,...,)>i -двоичные переменные.



что область 3 < jc, < 4 пространства допустимых решений задачи ЛПО не содержит целочисленных значений переменной лс, и, следовательно, может быть исключена из рассмотрения, как бесперспективная. Это эквивалентно замене исходной задачи ЛПО двумя новыми задачами линейного программирования ЛП1 и ЛП2, которые определяются следующим образом:

Рис. 9.5. Пространство решений задачи ЦЛП

пространство допустимых решений ЛП1 = пространство допустимых решений ЛПО

+ (х, < 3),

пространство допустимых решений ЛП2 = пространство допустимых решений ЛПО

+ (х, > 4).

На рис. 9.6 изображены пространства допустимых решений задач ЛП1 и ЛП2. Оба пространства содержат все допустимые решения исходной задачи ЦЛП. Это означает, что задачи ЛП1 и ЛП2 "не потеряют" решения начальной задачи ЛПО.

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

Новые ограничения х, < 3 и i, > 4 взаимоисключаемы, так что задачи ЛП1 и ЛП2 необходимо рассматривать как независимые задачи линейного программирования, что и показано на рис. 9.7. Дихотомизация задач ЛП - основа концепции ветвления в методе ветвей и границ. В этом случае хх называется переменной ветвления.

Оптимальное решение задачи ЦЛП находится в пространстве допустимых решений либо задачи ЛП1, либо ЛП2. Следовательно, обе подзадачи должны быть решены.

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