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

6
.3. Методы решения задач целочисленного 
программирования. Метод отсекающих плоскостей 
Методы решения задач целочисленного программирования можно клас-
сифицировать как методы отсечений и комбинаторные методы. 
Исходной задачей для демонстрации возможностей методов отсечений, 
используемых при решении линейных целочисленных задач, является задача с 
ослабленными ограничениями, которая возникает в результате исключения 
требования целочисленности переменных. По мере введения специальных до-
полнительных ограничений, учитывающих требование целочисленности, мно-
гогранник допустимых решений ослабленной задачи постепенно деформирует-
ся до тех пор, пока координаты оптимального решения не станут целочислен-
ными. Название «методы отсечений» связано с тем обстоятельством, что вво-
димые дополнительные ограничения отсекают (исключают) некоторые области 
многогранника допустимых решений, в которых отсутствуют точки с целочис-
ленными координатами. 
114

---

В основе комбинаторных методов лежит идея перебора всех допустимых 
целочисленных решений. Разумеется, на первый план здесь выдвигается про-
блема разработки тестовых процедур, позволяющих непосредственно рассмат-
ривать лишь (относительно небольшую) часть указанных решений, а остальные 
допустимые решения учитывать некоторым косвенным образом. Наиболее из-
вестным комбинаторным методом является метод ветвей и границ, который 
также опирается на процедуру решения задачи с ослабленными ограничения-
ми. При таком подходе из рассматриваемой задачи получаются две подзадачи 
путем специального разбиения пространства решений и отбрасывания обла-
стей, не содержащих допустимых целочисленных решений. 
Когда целочисленные переменные являются булевыми, применяются 
комбинированные методы. Булевы свойства переменных существенно упро-
щают поиск решения. 
Для решения задач, содержащих только булевы переменные, обычно ис-
пользуется так называемый 
аддитивный алгоритм
. Для решения нелинейных 
задач с булевыми переменными используется также обобщенный аддитивный 
алгоритм. 
Рассмотрим задачу ЦЛП, записанную в стандартном виде (только огра-
ничения равенства): 
𝑐
1
𝑥
1
+ ⋯ + 𝑐
𝑛
𝑥
𝑛
→ max
(6.1) 
∑
𝑎
𝑖𝑗
𝑥
𝑗
= 𝑏
𝑖
𝑛
𝑗=1
; (
i 
= 1,...,
m
), 
𝑥
𝑗
≥ 0
; (
j 
= 1,...,
n
),
𝑥
𝑗
∈ 𝑍
,
где 
Z
— множество целых чисел. 
Основная идея метода отсечений состоит в том, что исходная задача ЦЛП 
первоначально рассматривается без требований целочисленности переменных. 
Если оптимальное решение такой задачи с ослабленными ограничениями тем 
не менее является целочисленным, то, как нетрудно показать, оно является оп-
тимальным решением для исходной задачи. В противном случае по специаль-
ному алгоритму строится некоторое дополнительное линейное ограничение, 
обладающее следующими свойствами: 

данное дополнительное ограничение отсекает полученное нецелочис-
ленное оптимальное решение (т.е. оно не удовлетворяет данному дополнитель-
ному ограничению); 

данное дополнительное ограничение не отсекает ни одного целочис-
ленного решения (т.е. любое допустимое целочисленное решение предыдущей 
задачи удовлетворяет данному дополнительному ограничению). 
Дополнительное линейное ограничение, обладающее вышеприведенны-
ми свойствами, будем называть 
правильным отсечением
. 
Нижеприведенный алгоритм построения правильных отсечений был 
предложен Гомори (метод Гомори). Пусть решение исходной задачи с ослаб-
ленными ограничениями (без требования целочисленности) симплекс-методом 
дало на последнем шаге, соответствующем оптимальному решению, следую-
115

---

щее выражение основных (базисных) переменных 
𝑥
1
, … , 𝑥
𝑚
через неосновные 
(свободные) переменные 
𝑥
𝑚+1
, … , 𝑥
𝑛
: 
𝑥
1
= 𝑏
1
′
− 𝑎
1𝑚+1
′
𝑥
𝑚+1
− ⋯ − 𝑎
𝑛
′
𝑥
𝑛
, 
(6.2) 
𝑥
𝑖
= 𝑏
𝑖
′
− 𝑎
𝑖𝑚+1
′
𝑥
𝑚+1
− ⋯ − 𝑎
𝑖𝑛
′
𝑥
𝑖𝑛
, 
𝑥
𝑚
= 𝑏
𝑚
′
− 𝑎
𝑚𝑚+1
′
𝑥
𝑚+1
− ⋯ − 𝑎
𝑚𝑛
′
𝑥
𝑛
. 
Как следует из теории симплекс-метода, оптимальным решением задачи 
в этом случае является вектор 
𝑥
∗
= (𝑏
1
′
, … , 𝑏
𝑚
′
, 0, … , 0)
. Если все компоненты 
этого вектора целочисленные, то, как было отмечено выше, это и есть опти-
мальное решение исходной задачи. Иначе среди компонент вектора есть хотя 
бы одна нецелочисленная (с положительной дробной частью). Пусть это будет 
компонента 
𝑏
𝑘
′
({𝑏
𝑘
′
> 0})
. Тогда рассмотрим следующее линейное ограниче-
ние: 
{𝑏
𝑘
′
} − {𝑎
𝑘𝑚+1
′
}𝑥
𝑚+1
− ⋯ − {𝑎
𝑘𝑛
′
}𝑥
𝑛
≤ 0
. 
(6.3) 
Сформулируем теперь этапы решения задачи целочисленного линейного 
программирования методом Гомори. 
Этап 1.
 
Используя симплекс-метод, решаем исходную задачу без ограни-
чений на целочисленность. Если задача с ослабленными ограничениями не 
имеет решения, то и исходная задача не имеет решения. Если решение задачи 
оказывается целочисленным, то оно является решением исходной задачи и про-
цесс поиска решения завершен. 
Этап 2.
 
Выбирается одна из нецелых компонент полученного на этапе 1 
решения (как правило, выбирается компонента, имеющая наибольшую дроб-
ную часть). Исходя из выбранной компоненты, строится правильное отсечение. 
Этап 3.
 
Неравенство, полученное на этапе 2, преобразуется в равенство 
путем добавления новой неотрицательной переменной: 
{𝑏
𝑘
′
} − {𝑎
𝑘𝑚+1
′
}𝑥
𝑚+1
− ⋯ − {𝑎
𝑘𝑛
′
}𝑥
𝑛
+ 𝑥
𝑚+1
= 0, 𝑥
𝑛+1
≥ 0
. 
Эти соотношения присоединяем к ограничениям задачи, рассмотренной 
на этапе 1. 
Этап 4. 
Решаем задачу с модифицированными на этапе 3 ограничениями. 
Если ее оптимальное решение является целочисленным, то это и есть опти-
мальное решение исходной задачи, иначе возвращаемся к этапу 2. 
Оказывается, что если исходная задача имеет решение, то данный алго-
ритм позволяет его найти за конечное число шагов.