3. Задача выбора вариантов

Перейдем теперь к частному случаю задач целочислен­ного программирования — задаче выбора вариантов.

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

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

Пример 2. В задаче выбора вариантов примем, что для получения результата в виде максимально возможной при­были необходимы два видя ресурсов: материальные и тру­довые. Возможны четыре варианта расхода ресурсов и по­лучения прибыли (табл. 2).

Требуется выбрать, какие варианты принять для реа­лизации при условии, чтобы общее число принятых вариантов не превышало трех (k 3).

Решение. Для составления модели примем, что j-му варианту будет соответствовать (j – 1, …, 4). При этом

Тогда математическая модель задачи запишется:

max L = 65 + 80 + + 210 ,

Таблица 2.
Показатели	Варианты				Наличие
	1	2	3	4
Прибыль, д. е./ед.	65	80	90	210	_
Материальные ресурсы	200	180	240	250	800
Трудовые ресурсы	10	15	22	28	50

Последняя строка системы обеспечивает выполнение условия, чтобы общее число принятых вариантов не пре­вышало трех.

Из результатов решения этой задачи (первый столбец табл. 3) видна, что наибольшая прибыль (max L = 300) будет получена в том случае, если будут приняты третий и четвертый варианты.

Таблица 3.
Оптимальное решение	Дополнительные условия
	нет	=	+ = 1
	0	0	1
	0	1	1
	0	0	1
	1	1	0
Прибыль (max L)	300	290	235

С помощью булевых переменных можно накладывать дополнительные логические связи между вариантами. На­пример, требуется, чтобы четвертый вариант был принят только в том случае, если принят второй; а если же второй вариант не принят, то и четвертый не должен быть принят. Это условие можно записать так: = или в форме запи­си ограничений - = 0 (результат решения этой задачи во втором столбце табл. 15).

Может быть сформулирован и другой вариант допол­нительных условий. Например, требуется, чтобы был при­нят либо третий вариант, либо четвертый, т. е. (результат решения в третьем столбце).

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

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

Max L =

где последнее ограничение может учитывать самые разно­образные условия.

Если накладывается требование «должен», то в ограничении ставится знак равенства: (число принятых вариантов «должно быть» три).

Если требование «может», то — знак неравенства, в частности:

• если накладывается требование «И», то

например, принятие и первого и третьего вариантов запишется ;

• если для вариантов накладывается требование «ИЛИ», то условие запишется:

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