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

Рис. 6.5.
Множество допустимых решений
 
Теперь нерешенными остаются подзадачи 3 и 5. С точки зрения выше-
приведенного правила относительно порядка выбора решаемых подзадач сле-
дует выбрать подзадачу 5. Результаты ее решения таковы 
𝑧
∗
=
365
9
, 
𝑥
1
∗
=
40
9
, 
𝑥
2
∗
= 1
(точка 
I
) (см. рис. 6.5). Поскольку решение подзадачи 5 содержит только 
одну нецелочисленную компоненту, мы можем продолжить ветвление только 
по переменной 
𝑥
1
. Это приводит нас к рассмотрению двух ограничений 
𝑥
1
≥ 5
и 
𝑥
1
≤ 4
. Далее строятся две новые подзадачи: 
«подзадача 6» = «подзадача 5» + «дополнительное ограничение 
𝑥
1
≥ 5
»; 
«подзадача 7» = «подзадача 5» + «дополнительное ограничение 
𝑥
1
≤ 4
». 
Рис. 6.6.
Множества допустимых значений
 
Множества допустимых значений для подзадачи 6 и подзадачи 7 показа-
ны на рис. 6.6. Допустимым множеством для подзадачи 7 является отрезок 
EH
, 
а для подзадачи 6 точка 
G
.
К текущему моменту нерешенными являются задачи 3, 6 и 7. Согласно 
правилу выбора можно решать подзадачу 6 или 7. Выберем, например, подза-
дачу 7. Результаты ее решения таковы: 
𝑧
∗
= 37
𝑥
1
∗
= 4
𝑥
2
∗
= 1
(точка 
H
) (см. рис 
125

---

6.6). Поскольку полученное оптимальное решение является целочисленным, мы 
можем сделать два вывода. 
1.
Данная точка является допустимой для исходной задачи (6.11), следо-
вательно, мы можем определить текущее значение рекорда равным 37 (оценка 
снизу для решения исходной задачи), а точку (4,1) рассматривать как возмож-
ную кандидатуру на оптимальное решение. 
2.
Допустимое множество подзадачи 7 не содержит целочисленных точек 
со значением целевой функции больше, чем 37, а следовательно, не имеет 
смысла производить дальнейшее ветвление подзадачи 7, что позволяет нам 
считать ее прозондированной. 
К текущему моменту нерешенными являются задачи 3 и 6. Согласно пра-
вилу выбора нужно решать подзадачу 6. Результаты ее решения таковы: 
𝑧
∗
= 40
, 
𝑥
1
∗
= 5
, 
𝑥
2
∗
= 0
(точка 
G
) (см. рис 6.6). Поскольку полученное опти-
мальное решение является целочисленным, мы можем сделать два вывода: 

данная точка является допустимой для исходной задачи (6.11), и значе-
ние целевой функции в данной точке больше текущего значения рекорда. Сле-
довательно, мы должны присвоить текущему значению рекорда новое значе-
ние, равное 40 (новая оценка снизу для решения исходной задачи), а точку (5,0) 
рассматривать как новую возможную кандидатуру на оптимальное решение; 

допустимое множество подзадачи 6 не содержит целочисленных точек 
со значением целевой функции больше, чем 40, а следовательно, не имеет 
смысла производить дальнейшее ветвление подзадачи 6, что позволяет нам 
считать ее прозондированной. 
К текущему моменту нерешенной является только задача 3. Результаты ее 
решения таковы: 
𝑧
∗
= 39
𝑥
1
∗
= 3
, 
𝑥
2
∗
= 3
(точка 
C
) (см. рис. 6.4). Поскольку по-
лученное оптимальное значение задачи, равное 39 (оценка сверху для значения 
целевой функции исходной задачи на целочисленных точках, содержащихся в 
допустимом множестве данной подзадачи), меньше значения текущего рекорда, 
равного 40, то подзадачу 6 можно исключить из дальнейшего рассмотрения. 
Таким образом, процесс ветвления завершен, и оптимальным решением 
задачи являются 
𝑧
∗
= 40
, 
𝑥
1
∗
= 5
, 
𝑥
2
∗
= 0
. 
Процесс решения задачи по методу ветвей и границ удобно изображать 
графически в виде древовидной структуры, в которой вершины соответствуют 
подзадачам, а дуги — дополнительным ограничениям, возникающим в момент 
ветвления по какой-либо переменной. Число рядом с подзадачей обозначает 
хронологический порядок решения подзадач. Для вышерассмотренной задачи 
древо решения приведено на рис. 6.7. 
Между алгоритмами метода ветвей и границ, положенными в основу 
большинства используемых программ для ЭВМ, и описанным выше алгорит-
мом имеются определенные различия, которые главным образом связаны с 
правилами выбора последовательности рассмотрения подзадач и переменных, 
инициирующих процессы ветвления в вершинах. Обычно это эвристические 
правила, разработанные в ходе машинных экспериментов. 
В приведенном выше примере мы использовали следующий подход к 
выбору подзадачи — решать последнюю из сформированных подзадач. Опира-
126

---

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