Российский экономический

Рис. 6.3. 
Геометрическая интерпретация решения подзадачи 1
 
Как было отмечено в начале данного параграфа при описании общей 
схемы метода, максимальная из оценок, полученных на подмножествах, есть 
оценка сверху для оптимального значения исходной задачи. Поэтому на дан-
ном этапе оценкой сверху для оптимального решения задачи является число 
165/4.
Далее, согласно схеме метода, переходим к процессу ветвления задачи. 
Выберем одну из нецелочисленных компонент решения, полученного на 
предыдущем шаге. Например, 
𝑥
1
= 9/4
. Тогда любая допустимая точка задачи 
(6.11) удовлетворяет одному из ограничений 
𝑥
1
≤ 3
или 
𝑥
1
≥ 4
. Произведем 
ветвление задачи на две новые подзадачи, которые для краткости запишем в 
некотором схематичном виде: 
«подзадача 2» = «подзадача 1» + «дополнительное ограничение 
𝑥
1
≥ 4
»; 
123

---

«подзадача 3» = «подзадача 1» + «дополнительное ограничение 
𝑥
1
≤ 3
». 
Эту процедуру называют ветвлением по переменной 
𝑥
1
. На рисунке 6.4 
изображены допустимые множества обоих подзадач.
 
Рис. 6.4.
Допустимые множества решений
 
Допустимое множество подзадачи 3 есть четырехугольник ABCD, а под-
задачи 2 – треугольник EFG. Как и следовало ожидать, эти два множества не 
пересекаются, и их объединение покрывает допустимое множество задачи 
(6.11). 
Далее выбираем любую из подзадач, для которой еще не получена оценка 
сверху исходной целевой функции. Например, подзадачу 2. Ее решение приво-
дит к результату 
𝑧
∗
= 41
, 
𝑥
1
∗
= 4
, 
𝑥
2
∗
=
9
5
(точка 
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, эта подзадача имеет пустое множество допустимых 
решений. Следовательно, согласно приведенной схеме метода эта подзадача 
исключается из рассмотрения. 
124

---