4.4. Задача булева программирования и аддитивний алгоритм ее решения
Важный класс задач дискретного программирования составляет задача булева программирования вида
максимизировать 
(4.4.1)
при условиях
(4.4.2)
(4.4.3)
К этому классу задач сводятся многочисленные задачи исследования операций, такие как задачи о размещении производств, задачи о назначении, задачи синтеза структуры транспортных и информационных сетей и т.д.
Разработано много точных и приближенных методов ее решения. Некоторые из них будут рассмотренны ниже. Первый точный алгоритм решения булевой задачи предложил Э. Балаш в 1966 г. [3]. Этот алгоритм получил название аддитивного.
Рассмотрим його основные идеи.
Если учитывать только условия (4.4.3), то существует 
возможных наборов значений переменных x1, x2, ., xn... Многие из них недопустимы из-за ограничения (4.4.2) и лишь весьма небольшое число из них являются оптимальными.
Рассмотрим некоторое подмножество 
, 
, в котором каждой переменной поставлено в соответствие некоторое значение 0 или 1.
Такое подмножество называется частичным решением.
Переменные xj, не входящие в частичное решение, носят название свободных переменных. Любой набор числовых значений называется дополнением соответствующего частичного решения. Если частичное решение содержит s переменных, то существует 
дополнений. Формально процесс поиска оптимального решения можно представить в виде генерации некоторого дерева вариантов, где каждая вершина (не концевая) соответствует некоторому частичному решению, а возможные его дополнения генерируют ветви дерева (рис.4.8). Кроме того, каждому частичному решению соответствует некоторая задача основного списка.
Рис. 4.8.
Допустим, что известна нижняя достигнутая оценка оптимального значения целевой функции (4.5.1) и зафиксировано допустимое решение, дающее эту оценку. Тогда, если каким-то образом удается доказать, что для некоторого частичного решения не существует допустимого дополнения, которое имеет значение целевой функции, превышающее нижнюю текущую оценку, то нет необходимости в дальнейшем решении, т.е. это решение отсеивается. В этом случае говорят, что частичное решение прозондовано. При зондировании частичного решения, содержащего s переменных, неявным образом перебирается возможных значений. Существует связь между основной идеей адитивного
алгоритма и принципом оптимальности динамического программирования (см. п.7.1). Применительно к данному алгоритму этот принцип формулируется так. При заданном частичном решении значения остальных переменных должны выбираться так, чтобы дополнение этого решения было оптимальным. При отсутствии таких значений свободных переменных или в случае, когда оптимальные значения этих переменных приводят к худшему значению целевой функции по сравнению с текущей оценкой, не существует оптимального решения, содержащего заданное частичное решение.
Пусть на любой итерации n известна нижняя оценка 
оптимального значения ц.ф. (это значение можно выбрать точно так же, как и в методе ветвей и границ).
Кроме того, на каждой итерации формируется основной список задач, в котором каждой задаче соответствует определенное частичное решение. На итерации 1 основной список содержит две задачи, полученные в результате выбора 
, причем принимается, что частичное решение одной задачи = 0, а другой = 1.
Существует несколько способов, которые можно применить, чтобы установить, существует ли какое-либо дополнение решения, дающее значение ц.ф., превышающее текущую нижнюю оценку.
Например, если задача содержит ограничение
- 1x1 + 2x2-5x3 + 4x4-3x5 £ 0, (4.4.4)
то не существует дополнения частичного решения x1 = 1, x3 = 0, x4 = 1, удовлетворяющего условию (4.4.4). Предположим, что целевая функция описывается выражением
z0 = 1x1 + 2x2 + 4x3 + 3x4-1x5 (4.4.5)
и = 8.
Тогда, чтобы улучшить значения , дополнение должно удовлетворять ограничению
1x1 + 2x2 + 4x3 + 3x4-1x5 ³ + 1 = 9. (4.4.6)
Ни одно дополнение частичного решения x3 = 0, x5 = 0 не является допустимым по условию (4.4.6). Формализуем наши рассуждения следующим образом. При заданном частичном решении 
запишем ограничение (4.4.2) в следующем виде
(4.4.7)
где I - множество индексов переменных частичного решения, N\I - множество индексов свободных переменных, N - множество всех индексов переменных, и каждой переменной xj частичного решения поставлено в соответствие определенное значение, входящее в знак ∑ в правой части (4.4.7), а коэффициенты в ограничении при i = 0 (ц.ф.) равны a0 j = - cj, a b0 = - -1. Тогда не существует допустимого дополнения, которому соответствует значение ц.ф., превышает нижнюю оценку, если
при любом i. (4.4.8)
Как видим, левая часть (4.4.8) представляет собой суму всех отрицательных коэффициентов при свободных переменных.
Если эта сумма больше правой части неравенства, то даже, полагая = 1 для всех тех свободных переменных, для которых 
< 0, невозможно выполнить i-е ограничение (4.4.8).
Другим важным моментом является то, что при заданном частичном решении иногда удается определить, какое значение должна иметь свободная переменная при любом допустимом дополнении и в случае, когда значение целевой функции превосходит текущую нижнюю оценку.
В частности, для любой свободной переменной в случае, когда
при свободном i, (4.4.9)
= 0, если 
> 0, и = 1, если < 0.
Справедливость этого утверждения можно проверить на примере задачи, содержащей такое ограничение:
2x1 + (-2)x2 + 3x3-2x4 £ 0. (4.4.10)
Нетрудно убедиться, что при частичном решении x1 = 1, x2 = 1 в любом дополнении должно выполняться условие x3 = 0, так как только тогда будет выполняться ограничение (4.4.10).
Проверки (4.4.8),(4.4.6) можно применять также и к составным ограничениям, образованным в виде линейной положительной комбинации исходных ограничений (4.4.2), а именно:
(4.4.11)
где 
>0.
Приведем пример использования таких сложных ограничений.
Рассмотрим условия:
- x1 - x2-2x3 £ -1; 3x2-3x4 + 3x5 £ 0; 2x3 + 3x4-3x5 £ 0.
При частичном решении x1 = 0 применение проверки (4.4.8) к каждому ограничению в отдельности не указывает на недопустимость дополнения. Однако можно убедиться, что применение (4.4.8) к сумме этих ограничений: - x1 + 2x2 £ -1 при x1 = 0 сразу показывает, что допустимого дополнения не существует. Аналогичным образом, применение проверки (4.4.9) к сумме этих ограничений при x1 = 1 дает, что в любом допустимом дополнении x2 = 0.
Описание аддитивного алгоритма. Пусть уже проведено k итераций и найдена текущая нижняя оценка оптимального решения 
и список задач. Опишем (k+1)-ю итерацию.
П е р в ы й ш а г. Закончить вычисление, если основной список задач пуст. В противном случае выбрать очередную задачу из основного списка и вычеркнуть ее из него.
В т о р о й ш а г. Если можно найти свободные переменные, которые должны иметь определенные значения при любом дополнении, когда значение ц.ф. превосходит , то соответствующим образом расширить выбранное частичное решение. Если можно установить, что не существует допустимого дополнения, у которого значение ц.ф. превосходит , то положить 
= и вернуться к первому шагу. В противном случае перейти к третьему шагу.
Т р е т и й ш а г. Если расширенное частичное решение является полным (т.е. содержит все n переменных), зафиксировать его и вернутться к первому шагу. В противном случае перейти к четвертому шагу.
Ч е т в е р т ы й ш а г. Выбрать любую свободную переменную 
, не входящую в расширенное частичное решение. Ввести две новые задачи в основной список. В одной из них положить = 0 в расширенном решении, а в другой - = 1. Положить = и вернуться к первому шагу.
Замечание. При прекращении работы алгоритма в случае, когда зафиксировано допустимое решение, дающее значение ц.ф. 
, это решение будет оптимальным. В противном случае допустимых решений не существует. Алгоритм обеспечивает сходимость за конечное число итераций.
Пример 4.5. Рассмотрим задачу булева программирования
максимизировать 
= z, i=0 (1)
при ограничениях
£ 8, i=1; (2)
£ 8, i=2; (3)
(4)
Первая итерация. П е р в ы й ш а г. Примем 
= 0. Это соответствует допустимому решению, в котором все 
= 0. Предположим, что в основной список входит задача 1 с частичным решением 
= 1 и задача 2 с частичным решением = 0.
В т о р о й ш а г. Найдем некоторые свободные переменные (
¹ ), которые должны иметь определенные значения, чтобы удовлетворять ограничениям (2) - (4) при условии = 1. Применим проверку (4.4.9) при i = 1 и i = 2, тогда получим 
=
= 0. Далее, при условии, что = 1, а = = 0, вторичное применение условий (4.4.9) при i = 1, i = 2 дает 
=
=0. Таким образом, получено полное решение, содержащее все переменные.
Затем проверяется допустимость этого решения при i = 0, 1, 2, которая в данном случае сводится к проверке допустимости его по условиям (2) - (4).
Итак, фиксируем этт решение = = = = 0, = 1, 
= 13. Полагаем 
= 13 и перейдем ко второй итерации.
Вторая итерация. П е р в ы й ш а г. Выберем из списка задачу 2, где = 0. Ограничение по значению ц.ф. запишется следующим образом:
³ +1 = 14,
или
£ -14, i= 0. (5)
В т о р о й ш а г. Применение условий (4.4.9) при i = 0, 1, 2 не приводит к расширению частичного решения = 0, и аналогично применение (4.4.8) не исключает возможность появления допустимого решения со значением ц.ф. 
> 13. Поэтому переходим последовательно к третьему шагу, а потом к четвертому шагу, так как частичное решение не является полным.
Ч е т в е р т ы й ш а г. Выберем свободную переменную , и внесем в основной список задачу 3, в которой = 0, = 1, и задачу 4, в которой = 0, = 0. Переходим к первому шагу следующей итерации, положив = = 13.
Третья итерация. П е р в ы й ш а г. Выберем из списка задачу 3. Проверка по условиям (4.4.9) при i = 0, 1 не позволяет определить обязательные значения исходных переменных. Поэтому переходим к ограничению (3) i = 2. Проверка условия (4.4.9) для ограничения (3) дает = 0 для любого допустимого дополнения.
 |
Рис. 4.9.
Расширяя соответствующим образом текущий частичное решение ( = 1; = 0; = 0) и повторно применяя (4.4.9) для условия (5) (i = 0), убедимся, что допустимого дополнения не существует (так как min 
> 
= -14 + 3 = -11).
Поэтому второй шаг заканчивается, и возвращаемся к первому шагу очередной итерации, положив 
= =13.
Четвертая итерация. П е р в ы й ш а г. Выберем задачу 4, в которой = = 0. Проверка по условию (4.4.9) при i = 0 показывает, что для любого допустимого дополнения
= 1. Применяя далее (4.4.9) для частичного решения = = 0, = 1 при i = 1, 2, находим, что = 0, = 0. Непосредственной проверкой убеждаемся, что это решение не удовлетворяет условию (5), т.е. не существует ни одного допустимого дополнения со значением ц.ф., превышающим . Возвращаемся к первому шагу, и, поскольку основной список задач пуст, робота алгоритма заканчивается. Итак, мы получили оптимальное решение
, = 13 =
.
Структурная схема алгоритма для этого примера приведена на рис.4.9.
Как следует из анализа решения задачи 3, всякий раз, когда проверка (4.4.9) приводит к расширению частичного решения, может оказаться выгодным повторение этой процедуры по всем ограничениям i = 0,1,2,.на основе расширенного частичного решения.
Замечание.
1. Одним из основных отличий между аддитивним методом Балаша и методом ветвей и границ является то, что в аддитивном алгоритме требуется выполнение только операций сложения и вычитания (не требуются операции умножения и деления). Выбор на первом и четвертом шагах может основываться на информации, полученной из оптимального решения задачи ЛП (4.4.1),(4.4.2) при условиях 0 £ £ 1.
2. Второе отличие следующее: каждое частичное решение удовлетворяет условию целочисленности, но в отличие от метода ветвей и границ, может не удовлетворять линейным неравенствам (4.4.2).
3. Применяя эффективные правила выбора на первом и четвертом шагах с помощью аддитивного алгоритма, можно найти допустимое по всем ограничениям и близкое к оптимальному решение уже на начальных итерациях.
4. Вычислительная сложность алгоритма тесно связана с числом целочисленных переменных. В данном алгоритме объем вычислений определяется прежде всего числом задач, входящих в основной список. Заметим, что дополнительные ограничения на самом деле могут оказаться весьма полезными для уменьшения объема вычислений, и хотя нужно выполнить большее число проверок на втором шаге, гораздо чаще удается возвращаться непосредственно к первому шагу без добавления новых задач в основной список.
