Эвристический метод решения задачи булева программирования.

 

Существует два метода решения задач с булевыми переменными.

Во-первых, их можно решать как обычные задачи целочисленного программирования, т. е. методом ветвей и границ. При этом на каждую переменную накладывается два требования: они должны быть в пределах ; должны быть целыми. Совершенно очевидно, что выполнение этих двух требований обеспечивает получение в решении значений , т. е. равных либо 0, либо 1.

Вторым методом является метод сплошного перебора. Посмотрим его на таком примере. Пусть требуется решить систему:

(1)

 

Поскольку , , могут принимать значения 0 или 1 в любом сочетании, рассмотрим все возможные сочетания, как это сделано в табл. 3.8.1. Работа при полном переборе выполняется в такой последовательности.

1. Заполнить все возможные варианты сочетаний допустимых значений , , .

2. Определить значения левых частей ограничений (1)–(4) и целевой функции и записать их.