Задачи с булевыми переменными
В частном случае искомая переменная Xj в результате решения может принимать не любое целое значение, а только одно из двух: 0 либо 1. Чтобы такие переменные отличать от обычных, будем их вместо Xj обозначать dj.
И это уже будет означать, что в результате решения задачи dj может быть равным или 0, или 1, т. е. всегда dj [0; 1]. Такие переменные обычно называют булевыми в честь предложившего их английского математика Джорджа Буля (18151864).
С помощью булевых переменных можно решать самые различные по содержанию задачи, в которых надо выбирать из имеющихся различных вариантов.
Пример. В задаче выбора вариантов примем, что для получения результата в виде максимально возможной прибыли необходимы два вида ресурсов: материальные и трудовые (табл. 8.7).
Таблица 8.7 Задача выбора вариантов
Показатели Варианты Наличие
1 2 3 4
Прибыль, ден. ед./ед. 65 80 90 210 -
Материальные ресурсы 200 180 240 250 800
Трудовые ресурсы 10 15 22 28 50
Возможны четыре варианта расхода ресурсов и получения прибыли. Требуется выбрать, какие варианты принять для реализации при условии, чтобы общее число принятых вариантов не превышало трех, т. е. k < 3.
Решение. Для составления модели примем, что j-му варианту будет соответствовать dj (j = 1... 4). При этом
[1, если^-й вариант принят; j [0, если^-й вариант не принят.
Тогда математическая модель задачи запишется в виде: тах L = 65^ + 80d2 + 90d3 + 210d4;
200^ + 180 d2 + 240 d3 + 250d4 < 800;
10^ + 154 + 2Щ + 28Й4 < 50; 4 + S2 + S3 + Si < 3.
Последняя строка системы обеспечивает выполнение условия, чтобы общее число принятых вариантов не превышало трех (табл. 8.8).
Таблица 8.8
Показатель Вариант
1 2 3
Прибыль 300 290 235
я0 $1 0 0 1
$2 0 1 1
$3 1 0 1
$4 1 1 0
Из вариантов решения задачи видно, что наибольшая прибыль (max L = 300) достигается, если будут приняты третий и четвертый варианты.
С помощью булевых переменных можно накладывать дополнительные логические связи между вариантами. Например, требуется, чтобы четвертый вариант был принят только в том случае, если принят второй, а если же второй вариант не принят, то и четвертый не должен быть принят. Это условие можно записать так: <52 = <5>4 или в форме записи ограничений §2 - <5>4 = 0.
Может быть сформулирован и другой вариант дополнительных условий: например, требуется, чтобы был принят либо третий вариант, либо четвертый, т. е. <53 + 1; если для вариантов накладывается требование «ИЛИ», то условие (*) запишется:
s
I = 1-
j=1
Похожие рефераты:
