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

Симплекс-таблица модифицированной задачи 
х
1
х
2
х
3
х
4
х
5
Решение 
Z 
0 
0 
28/11 
15/11 
0 
63 
x
2
0 
1 
7/22 
1/22 
0 
7/2 
x
1
1 
0 
–1/22 
3/22 
0 
9/2 
х
5
 
0 
0 
–7/22 
–1/22 
1 
–1/2 
Продолжая решение симплекс-методом, приходим к следующей заклю-
чительной симплекс-таблице (табл. 6.3). 
Таблица 6.3 
Заключительная симплекс-таблица задачи 
х
1
х
2
х
3
х
4
х
5
Решение 
Z 
0 
0 
0 
1 
8 
59 
x
2
0 
1 
0 
0 
1 
3 
x
1
1 
0 
0 
1/7 
–1/7 
32/7 
х
3
 
0 
0 
1 
1/7 
–22/7 
11/7 
Оптимальное значение целевой функции, равное 59, достигается в точке 
𝑥
∗
= (𝑥
1
∗
, 𝑥
2
∗
, 𝑥
3
∗
, 𝑥
4
∗
, 𝑥
5
∗
)
с координатами 
𝑥
1
∗
= 32/7
, 
𝑥
2
∗
= 3
, 
𝑥
3
∗
= 11/7
, 
𝑥
4
∗
= 0
, 
𝑥
5
∗
= 0
. Поскольку оптимальное решение задачи с ослабленными ограничениями 
опять не является целочисленным, то необходимо переходить к этапу 2, т.е. строить 
еще одно правильное отсечение. Поскольку две компоненты оптимального реше-
ния нецелочисленны, то выберем в качестве переменной, на базе которой строится 
отсечение, переменную 
𝑥
1
. Тогда, добавляя новую неотрицательную переменную 
𝑥
6
, получаем согласно (6.3) дополнительное ограничение следующего вида: 
− {
1
7
} 𝑥
4
− {−
1
7
} 𝑥
4
+ 𝑥
6
= − {
32
7
}
, 
или
−
1
7
𝑥
4
−
6
7
𝑥
5
+ 𝑥
6
= −
4
7
. 
(6.7) 
Добавляя новое ограничение к ограничениям задачи, рассмотренной на 
предыдущем шаге, получаем модифицированную задачу линейного програм-
мирования со следующей исходной симплекс-таблицей (табл. 6.4). 
Таблица 6.4 
Симплекс-таблица модифицированной задачи 
х
1
х
2
х
3
х
4
х
5
х
6
 
Решение 
Z 
0 
0 
0 
1 
8 
0 
59 
x
2
0 
1 
0 
0 
1 
0 
3 
x
1
1 
0 
0 
1/7 
–1/7 
0 
32/7 
х
3
 
0 
0 
1 
1/7 
–22/7 
0 
11/7 
х
6
 
0 
0 
0 
–1/7 
–6/7 
1 
–4/7 
118

---

Продолжая решение симплекс-методом, приходим к следующей заклю-
чительной симплекс-таблице (табл. 6.5). 
Таблица 6.5 
Заключительная симплекс-таблица задачи 
х
1
х
2
х
3
х
4
х
5
х
6
 
Решение 
Z 
0 
0 
0 
0 
2 
7 
55 
x
2
0 
1 
0 
0 
1 
0 
3 
x
1
1 
0 
0 
0 
–1 
1 
4 
х
3
 
0 
0 
1 
0 
–4 
1 
1 
х
4
 
0 
0 
0 
1 
6 
–7 
4 
𝑥
∗
= (𝑥
1
∗
, 𝑥
2
∗
, 𝑥
3
∗
, 𝑥
4
∗
, 𝑥
5
∗
, 𝑥
6
∗
)
с координатами 
𝑥
1
∗
= 4
, 
𝑥
2
∗
= 3
, 
𝑥
3
∗
= 1
, 
𝑥
4
∗
=
4
, 
𝑥
5
∗
= 0
, 
𝑥
6
∗
= 0
. 
Поскольку оптимальное решение задачи с ослабленными ограничениями 
является целочисленным, то процесс поиска оптимального решения исходной 
задачи (6.4) завершен — оптимальной точкой является точка (4,3) со значением 
целевой функции 55.
В ходе решения задачи по методу Гомори были построены два дополни-
тельных линейных отсечения. Для того чтобы представить себе геометриче-
ский смысл построенных отсечений, преобразуем ограничение (6.6), выразив 
переменные 
𝑥
3
3
x
и 
𝑥
4
через исходные переменные 
𝑥
1
и 
𝑥
2
из уравнений (6.5). 
А именно: 
−
7
22
(6 + 𝑥
1
− 3𝑥
2
) −
1
22
(35 − 7𝑥
1
− 𝑥
2
) + 𝑥
5
= −
1
2
, 
или 
𝑥
2
+ 𝑥
5
= 3
, что эквивалентно, учитывая неотрицательность пере-
менной 
𝑥
5
: 
𝑥
2
≤ 3
. 
(6.8) 
Аналогичным образом преобразуем линейное отсечение (6.7), выразив 
переменную 
3
x
и 
4
x
из уравнений (6.5) и переменную 
5
x
из уравнений (6.6), а 
именно: 
−
1
7
(35 − 7𝑥
1
− 𝑥
2
) −
6
7
(−
1
2
+
7
22
(6 + 𝑥
1
− 3𝑥
2
) +
1
22
(35 − 7𝑥
1
− 𝑥
2
)) +
𝑥
6
= −
4
7
, 
или 
𝑥
1
+ 𝑥
2
+ 𝑥
6
= 7
, что эквивалентно, учитывая неотрицательность пе-
ременной 
𝑥
6
: 
𝑥
1
+ 𝑥
2
≤ 7
. 
(6.9) 
Изобразив ограничения (6.8) и (6.9), эквивалентные, как мы показали, ли-
нейным отсекающим ограничениям (6.6) и (6.7), мы получим геометрическую 
интерпретацию метода отсекающих плоскостей (рис. 6.2). 
119

---

Рис. 6.2.
Геометрическая интерпретация метода отсекающих плоскостей
 
Новое допустимое множество решений, получившееся после отсечений, 
есть многоугольник ABCDEF. 
6
.4. Метод ветвей и границ 
Методы типа ветвей и границ широко используются для решения не 
только задач линейного целочисленного и частично целочисленного програм-
мирования, но и для решения многих других дискретных оптимизационных за-
дач (например, задача коммивояжера). Поэтому первоначально мы рассмотрим 
схему метода в общем виде, а затем конкретизируем ее для задач ЦЛП.
Пусть требуется решить некоторую оптимизационную задачу, записан-
ную в общем виде, как: 
max𝐹(𝑥)
(6.10) 
𝑥 ∈ 𝑋
. 
Метод предполагает наличие некоторого способа вычисления оценок 
сверху целевой функции 
𝐹(𝑥)
на подмножествах множества 
𝑋, 𝑋
′
⊂ 𝑋
. Эту 
оценку на подмножестве будем обозначать как 
𝑅(𝑋
′
)
. Оценка сверху предпола-
гает выполнения следующего соотношения 
𝐹(𝑥) ≤ 𝑅(𝑋
′
), 𝑥 ∈ 𝑋
′
. 
Способ оценивания зависит от специфики решаемой задачи, однако 
весьма часто в основе оценивания функции 
𝐹(𝑥)
на множестве 
𝑋
′
лежит реше-
ние задачи максимизации на некотором более широком множестве. Как прави-
ло, задача максимизации функции на расширенном множестве оказывается 
проще с вычислительной точки зрения. Сразу поясним, что для задач ЦЛП это 
расширение заключается в отбрасывании требования целочисленности пере-
менных, что, с одной стороны, расширяет допустимое множество, а с другой, 
сводит задачу максимизации к задаче линейного программирования, которая 
существенно проще с вычислительной точки зрения. 
120

---

Кроме этого, метод предполагает наличие некоторого правила ветвления, 
суть которого состоит в следующем. Пусть имеется некоторое разбиение мно-
жества 
X
на систему подмножеств. Правило предполагает выбор некоторым 
способом одного из подмножеств и разбиение (ветвление) его на непересека-
ющиеся подмножества. Как правило, в качестве подмножества для ветвления 
выбирается подмножество с максимальным значением оценки. Иногда говорят 
не о ветвлении допустимого множества, а о ветвлении задачи (разбиение на 
подзадачи). 
Далее для вновь появившихся в результате ветвления подмножеств 
𝑋
′
строятся их оценки сверху. При этом могут возникнуть следующие ситуации: 
1)
подмножество 
𝑋
′
оказалось пустым; 
2)
полученная оценка 
𝑅(𝑋
′
)
меньше или равна наибольшему из уже вы-
численных к этому моменту значений функции 
𝐹(𝑥)
, которое называется теку-
щим значением рекорда. Отсюда следует, что оптимальное решение исходной 
задачи находится вне множества 
𝑋
′
; 
3)
точка из расширенного множества, в которой достигается оценка 
𝑅(𝑋
′
), 
принадлежит самому множеству 
𝑋
′
. 
Во всех трех случаях подмножество 
𝑋
′
исключается из рассмотрения. В 
случае 3, кроме того, вычисленное значение 
max𝐹(𝑥)
на множестве 
𝑥 ∈ 𝑋
′
сравнивается с текущем значением рекорда. В качестве нового значения теку-
щего рекорда выбирается максимальное из этих чисел. 
Важным достоинством метода ветвей и границ является то обстоятель-
ство, что в процессе решения на каждом шаге мы располагаем двусторонними 
оценками для оптимального значения задачи (6.10). А именно это значение 
ограничивается снизу значением текущего рекорда и ограничивается сверху 
максимумом из всех имеющихся оценок 
𝑅(𝑋
′
)
. Эти оценки в процессе решения 
уточняются, поэтому, если точность оценок на каком-либо шаге удовлетворяет, 
процесс вычисления по данному алгоритму может быть прекращен. 
Рассматриваемый метод решения задачи целочисленного программиро-
вания также опирается на решение задач с ослабленными ограничениями. Од-
нако в отличие от методов отсечений метод ветвей и границ непосредственно 
применим как к полностью, так и к частично целочисленным задачам. 
Согласно общей идее метода сначала решается задача с ослабленными 
ограничениями (задача линейного программирования). Пусть 
𝑥
𝑟
— целочис-
ленная переменная, значение 
𝑥
𝑟
∗
которой в оптимальном решении ослабленной 
задачи является дробным. Интервал: 
[𝑥
𝑟
∗
] < 𝑥
𝑟
< [𝑥
𝑟
∗
] + 1
не содержит допустимых целочисленных компонент решения. Поэтому 
допустимое целое значение 
х
должно удовлетворять строго одному
 
из нера-
венств: 
𝑥
𝑟
≤ [𝑥
𝑟
∗
] или 𝑥
𝑟
≥ [𝑥
𝑟
∗
] + 1
.
 
Введение этих условий в задачу с ослабленными ограничениями порож-
дает две не связанные между собой задачи. В таком случае говорят, что исход-
ная задача разветвляется (или разбивается) на две подзадачи. Осуществляемый 
121

---

в процессе ветвления учет необходимых условий целочисленности позволяет 
исключить части многогранника допустимых решений, не содержащих точек с 
целыми координатами. 
Затем каждая подзадача решается как задача линейного программирова-
ния (с целевой функцией исходной задачи). Если полученный оптимум оказы-
вается допустимым для целочисленной задачи, такое решение следует зафик-
сировать как наилучшее. При этом нет необходимости продолжать «ветвление» 
подзадачи, поскольку улучшить полученное решение, очевидно, не удастся. В 
противном случае подзадача, в свою очередь, должна быть разбита на две под-
задачи опять при учете условия целочисленности переменных, значения кото-
рых в оптимальном решении не являются целыми. Разумеется, как только по-
лученное допустимое целочисленное решение одной из подзадач оказывается 
лучше имеющегося (текущее значение рекорда), оно фиксируется вместо за-
фиксированного ранее. Процесс ветвления продолжается, насколько это воз-
можно, до тех пор, пока каждая подзадача не приведет к целочисленному ре-
шению или пока не будет установлена невозможность улучшения имеющегося 
решения. В этом случае зафиксированное допустимое решение является опти-
мальным. 
Эффективность вычислительной схемы метода можно повысить, введя в 
рассмотрение понятие границы, на основе которого делается вывод о необхо-
димости дальнейшего разбиения каждой из подзадач. Если оптимальное реше-
ние подзадачи с ослабленными ограничениями обеспечивает худшее значение 
целевой функции, чем имеющееся решение, эту подзадачу далее рассматривать 
не следует (п. 2 общей схемы метода). В таких случаях говорят, что подзадача 
прозондирована, ее можно вычеркнуть из списка подзадач, порожденных ис-
ходной задачей. Иными словами, как только получено допустимое целочис-
ленное решение некоторой подзадачи, соответствующее значение целевой 
функции может быть использовано в качестве (верхней в случае минимизации 
и нижней в случае максимизации) границы, наличие которой позволяет форма-
лизовать процедуру исключения прозондированных подзадач. 
Следует подчеркнуть исключительную важность проблемы выявления, 
достаточно близкой к оптимальному решению границы уже на первых этапах 
вычислений. Успешное разрешение указанной проблемы находится в прямой 
зависимости от порядка, в котором порождаются и решаются различные подза-
дачи, а также от выбора переменной, инициирующей процесс ветвления. К со-
жалению, вопрос о «наилучшем» способе выбора переменной ветвления или, 
последовательности решения конкретных подзадач пока еще не решен.