В основе комбинаторных методов лежит идея перебора всех допустимых
целочисленных решений. Разумеется, на первый
план здесь выдвигается про-
блема разработки тестовых процедур, позволяющих непосредственно рассмат-
ривать лишь (относительно небольшую) часть указанных решений, а остальные
допустимые решения учитывать некоторым косвенным образом. Наиболее из-
вестным комбинаторным методом является метод ветвей и границ, который
также опирается на процедуру решения задачи с ослабленными ограничения-
ми. При таком подходе из рассматриваемой задачи получаются две подзадачи
путем специального разбиения пространства решений и отбрасывания обла-
стей, не содержащих допустимых целочисленных решений.
Когда целочисленные
переменные являются булевыми, применяются
комбинированные методы. Булевы свойства переменных существенно упро-
щают поиск решения.
Для решения задач, содержащих только булевы переменные, обычно ис-
пользуется так называемый
аддитивный алгоритм
. Для решения нелинейных
задач с булевыми переменными используется также обобщенный аддитивный
алгоритм.
Рассмотрим
задачу ЦЛП, записанную в стандартном виде (только огра-
ничения равенства):
𝑐
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.
Оказывается, что если исходная задача имеет решение, то данный алго-
ритм позволяет его найти за конечное число шагов.
Do'stlaringiz bilan baham: 
