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


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


62

Сначала решим задачу (6.11) без требования целочисленности, т.е. на расширенном допустимом множестве. Эту задачу назовем «подзадача 1». Если найденное в этом случае решение бьшо бы целочисленным, то это и было бы решение задачи (6.11). Однако получаем следующее - . 165 . 15 . 9 „

Z =-,х, = -= -. На рис. 6.3 представлена геометрическая интер-

44 4

претация решения подзадачи 1. Четырехугольник ABCD есть допустимое множество подзадачи 1.

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

Далее, согласно схеме метода, переходим к процессу ветвления задачи. Выберем одну из нецелочисленных компонент решения, полученного на предьщущем шаге. Например, =9/4. Тогда любая допустимая точка

задачи (6.11) удовлетворяет одному из ограничений х, <3 или Xi>4. Произведем ветвление задачи на две новые подзадачи, которые для краткости запишем в некотором схематичном виде: «подзадача 2» = «подзадача 1» + «дополнительное ограничение Xi>4»; «подзадача 3» = «подзадача 1» + «дополнительноеограничение х<Ъ».

С (15/4.9/4)

h л:., = 6

Рис. 63

Эту процедуру называют ветвление по переменной . На рис. 6.4 изображены допустимые множества обеих подзадач.



D\ Xi+X2 =

+ 2 = 6 x\ E9x1+5x2=45

Puc. 6.4

Допустимое множество подзадачи 3 есть четырехугольник ABCD, а подзадачи 2 - треугольник EFG. Как и следовало ожидать, эти два множества не пересекаются, и их объединение покрывает допустимое множество задачи (6.11).

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

решение приводит к результату z*=41, х*=4, 2=~ (точка F)- Поскольку решение подзадачи 2 содержит только одну нецелочисленную компоненту, мы можем продолжить ветвление только по переменной 2. Это приводит нас к рассмотрению двух ограничений 2 > 2 и 2 < 1. Далее строятся две новые подзадачи: «подзадача 4» = «подзадача 2» + «дополнительное ограничение 2 > 2 »; «подзадача 5» = «подзадача 2» + «дополнительное ограничение 2 < 1».

Множества допустимых значений для подзадачи 4 и подзадачи 5 показаны на рис. 6.5. Допустимым множеством для подзадачи 5 является многоугольник FHIG.

К этому моменту остаются нерешенными подзадачи 3, 4 и 5. Нет однозначного правила выбора порядка решения задач в методе ветвей и границ. Один из возможных подходов- это решать последнюю из сформированных подзадач. С этой точки зрения можно решать подзадачу 4 или 5. Выберем задачу 4. Как видно из рис. 6.5, эта подзадача имеет пустое множество допустимых решений. Следовательно, согласно приведенной схеме метода эта подзадача исключается из рассмотрения.



Х2=2

/(40/9, 1)

Х2=\

Рис. 6.5

Теперь нерешенными остаются подзадачи 3 и 5. С точки зрения приведенного правила относительно порядка выбора решаемых подзадач, следует вы-

. 365 . 40 . ,

брать подзадачу 5. Результаты ее решения таковы: z == 2 = 1

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

Xi > 5 и Xi < 4. Далее строятся две новые подзадачи: «подзадача 6» =

«подзадача 5» + «дополнительное ограничение х, > 5 »; «подзадача 7» =

«подзадача 5» + «дополнительное ограничение Xi < 4 ».

*1=4

*,=5

Подзадача 7 ~

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