Существует два метода решения задач с булевыми переменными.
Во-первых, их можно решать как обычные задачи целочисленного программирования, т. е. методом ветвей и границ. При этом на каждую переменную накладывается два требования: они должны быть в пределах ; должны быть целыми. Совершенно очевидно, что выполнение этих двух требований обеспечивает получение в решении значений , т. е. равных либо 0, либо 1.
Вторым методом является метод сплошного перебора. Посмотрим его на таком примере. Пусть требуется решить систему:
(1) |
Поскольку , , могут принимать значения 0 или 1 в любом сочетании, рассмотрим все возможные сочетания, как это сделано в табл. 3.8.1. Работа при полном переборе выполняется в такой последовательности.
1. Заполнить все возможные варианты сочетаний допустимых значений , , .
2. Определить значения левых частей ограничений (1)–(4) и целевой функции и записать их.