Постановка задачи бивалентного (булева) программирования

Перейдем теперь к частному случаю задач целочисленного программирования. В этом частном случае искомая переменная в результате решения может принимать не любое целое значение, а только одно из двух: либо 0,
либо 1. Чтобы такие переменные отличать от обычных и каждый раз не писать [0; 1], будем их вместо обозначать . И это уже будет означать, что в результате решения задачи может быть равным или 0, или 1, т. е. всегда [0, 1]. Такие переменные обычно называют булевыми в честь предложившего их английского математика Джорджа Буля (1815–1864).

С помощью булевых переменных можно решать самые различные по содержанию задачи, в которых надо что-то выбирать из имеющихся различных вариантов. Рассмотрим еще две распространенные задачи, для решения которых применяют булевы переменные: задачу выбора вариантов; задачу дискретного программирования.

Задача выбора вариантов. Примем, что для получения результатов в виде прибыли необходимо два вида ресурсов: материальные и трудовые. Возможны четыре варианта расхода ресурсов и получения прибыли.

Таблица 3.7.1.

Характеристика					Наличие
Прибыль					—
Ресурсы:
материальные
трудовые

Количество расходуемого ресурса и получаемая прибыль для каждого варианта приведена в табл. 3.7.1. Требуется выбрать, какие варианты принять для реализации при условии, чтобы общее число принятых вариантов не превышало трех, т. е. . Для составления модели принимаем, что –му варианту будет соответствовать . При этом

(1)

Математическая модель задачи будет иметь вид:

(2)

Последняя строка системы (2) обеспечивает удовлетворение требования, чтобы общее число принятых вариантов не превышало трех. Результаты решения задачи приведены в первом столбце табл. 3.7.2, из которого видно, что наибольшая прибыль будет получена в том случае, если будут приняты третий и четвертый варианты. С помощью булевых переменных можно накладывать дополнительные различные логические условия связи между вариантами.

Таблица 3.7.2.

Дополнительное условие	Нет
Прибыль

Например, требуется, чтобы четвертый вариант был принят только в том случае, если принят второй. Если же второй вариант не принят, то и четвертый не должен быть принят. Это условие можно записать так: , или в форме записи ограничений

(3)

Результат решения задачи с учетом этого дополнительного условия приведен также в табл. 3.7.2.

Рассмотрим еще один вариант дополнительных условий. Допустим, нам надо, чтобы был принят либо третий вариант, либо четвертый. Это условие записывается так:

(4)

Результат решения задачи с этим дополнительным условием приведен также в табл. 3.7.2.

Сравнивая значения прибыли в оптимальном решении с полученными значениями прибыли при выполнении дополнительных условий, можно сделать вывод, что дополнительные условия, как всегда, привели к снижению прибыли.

Переходя от нашего примера, описываемого системой (2) с дополнительными условиями (3) и (4), к общему случаю, задачу выбора вариантов можно записать так:

(4)

В этой системе ограничение может учитывать самые разнообразные условия. Рассмотрим некоторые из них. Если накладывается требование «должен», то в ограничениях ставится знак равенства, если «может» — знак неравенства.

Так, если число принимаемых вариантов в нашем примере должно было бы быть равным 3, то надо было записать

Если накладывается требование «и», то условие записывается следующим образом:

.

Например, если могут быть приняты и первый и третий варианты, то . Если для вариантов накладывается требование «или», то это условие записывается так:

т. е., если из двух вариантов надо принять только один, то должно быть выполнено условие .

Значит, если обозначить — соответствует «быть», — «не быть», то вопрос «быть или не быть» может быть записан следующим образом:

В этом случае есть два допустимых решения: ; — означает «быть»; ; — означает «не быть». Так как целевая функция не сформулирована, то дать оптимальный ответ на этот извечный вопрос невозможно. Чтобы принять решение, необходимо знать, чего мы хотим.