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


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


60

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

согласно (6.3) дополнительное ограничение следующего вида: -{1/7}х4-{-1/7}х5+х,=-{32/7}

-1/7x4-6/7x5=-4/7.

(6.7)

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

Таблица 6.4

Решение

-1/7

32/7

-22/7

11/7

-1/7

-6/7

-4/7

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

Таблица 6.5

Решение

X =(х1,Х2,Хз,Х4,Х5,Хб) С координатами х =4, Xj = 3, Х3 = 1, Х4 =4,

х; = О, х; = 0.

Поскольку оптимальное решение задачи с ослабленными ограничениями является целочисленным, то процесс поиска оптимального решения исходной задачи (6.4) завершен- оптимальной точкой является точка (4, 3) со значением целевой функции 55.

В ходе решения задачи по методу Гомори было построено два дополнительных линейных отсечения. Для того чтобы представить себе геометрический смысл построенных отсечений, преобразуем ограничение



(6.6), выразив переменные Х3 и через исходные переменные х и Х2 из уравнений (6.5). А именно:

ИЛИ 2 + = 3, ЧТО эквивалентно, учитывая неотрицательность переменной X.

Х2<3.

(6.8)

Аналогичным образом преобразуем линейное отсечение (6.7), выразив переменную Х3 и Х4 из уравнений (6.5) и переменную х5 из уравнения (6.6), а именно:

1(35-7x1-X2)-(~4-(6 + Xi-3x2)4-(35-7x1-Х2)) + Х

или X, + Х2 + Хб = 7, что эквивалентно, учитывая неотрицательность переменной Х,

Х1+Х2 <7.(6.9)

Изобразив ограничения (6.8) и (6.9) эквивалентные, как мы показали, линейным отсекающим ограничениям (6.6) и (6.7), мы получим геометрическую интерпретацию метода отсекающих плоскостей (рис. 6.2).



Новое допустимое множество решений, получившееся после отсечений, есть многоугольник ABCDEF.

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

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

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

Идея метода ветвей и границ

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

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

шах F(x) хеХ.

(6.10)

Метод предполагает наличие некоторого способа вычисления оценок сверху целевой функции F(x) на подмножествах множества X, X аХ ,

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

F(x)<R{X),x еУ.

Способ оценивания зависит от специфики решаемой задачи, однако

весьма часто в основе оценивания функции F{x) на множестве X лежит решение задачи максимизации на некотором более широком множестве. Как правило, задача максимизации функции на расширенном множестве оказывается проще с вычислительной точки зрения. Сразу поясним, что для задач ЦЛП это расширение заключается в отбрасывании требования целочисленности переменных, что, с одной стороны, расширяет допустимое множество, а с другой- сводит задачу максимизации к задаче линейного программирования, которая существенно проще с вычислительной точки зрения.

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