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


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


63

Множества допустимых значений для подзадачи 6 и подзадачи 7 показаны на рис. 6.6. Допустимым множеством для подзадачи 7 является отрезок ЕН, а для подзадачи 6 точка G.

К текущему моменту нерешенными являются задачи 3, 6 и 7. Согласно правилу выбора, можно решать подзадачу 6 или 7. Выберем, например, подзадачу 7. Результаты ее решения таковы: z* = 37, х\ =4, = 1 (точка Я, рис. 6.6). Поскольку полученное оптимальное решение является целочисленным, мы можем сделать два вывода:

1)данная точка является допустимой для исходной задачи (6.11), и, следовательно, мы можем определить текущее значение рекорда равным 37 (оценка снизу для решения исходной задачи), а точку (4,1) рассматривать как возможную кандидатуру на оптимальное решение;

2)допустимое множество подзадачи 7 не содержит целочисленных точек со значением целевой функции больше чем 37, а следовательно, не имеет смысла производить дальнейшее ветвление подзадачи 7, что позволяет нам считать ее прозондированной.

К текущему моменту нерешенными являются задачи 3 и 6. Согласно правилу выбора, нужно решать подзадачу 6. Результаты ее решения таковы, z* = 40, х\ =5, 2 = О (точка G, рис 6.6). Поскольку полученное оптимальное решение является целочисленным, мы можем сделать два вывода:

1)данная точка является допустимой для исходной задачи (6.11), и значение целевой функции в данной точке больше текущего значения рекорда. Следовательно, мы должны присвоить текущему значению рекорда новое значение равное 40 (новая оценка снизу для решения исходной задачи), а точку (5,0) рассматривать как новую возможную кандидатуру на оптимальное решение;

2)допустимое множество подзадачи 6 не содержит целочисленных точек со значением целевой функции больше чем 40, а следовательно, не имеет смысла производить дальнейшее ветвление подзадачи 6, что позволяет нам считать ее прозондированной.

К текущему моменту нерешенной является только задача 3. Результаты ее решения таковы: z* = 39, х* =3, = 3 (точка С, рис. 6.4). Поскольку полученное оптимальное значение задачи равное 39 (оценка сверху для значения целевой функции исходной задачи на целочисленных точках, содержащихся в допустимом множестве данной подзадачи) 196



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

Таким образом, процесс ветвления завершен, и оптимальным решением задачи (6.11) являются z* = 40, =5, = О .

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

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

Подзадача 2 * * . *

Z = 41, Х] = 4, 2 =-

;С2 2

Подзадача 4

Пустое множество допустимых точек

Подзадача 1

165 * 15 * 9

х,<3

Подзадача 3

Z* = 39, х* = 3, Х2 = 3

2 <1

Подзадача 5

* 365 . 40 . ,

Z =-, Х1=-, Х2 = 1

Подзадача 6

Z* = 40, х* = 5, Х2 = О

Кандидатура на оптимапьное решение

jCi < 4

Подзадача 7

Z* = 37, xJ" = 4, Х2 = 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]