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

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

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

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

Таблица 3.7.1.

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

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

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

Таблица 3.7.2.

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

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

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

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

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

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

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

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

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

.

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

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

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

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