Российский экономический

 
113

---

Пример 
(задача оптимального выбора на множестве взаимозависимых аль-
тернатив).
 
В общем виде задача формулируется следующим образом. Пусть 
имеется 
N
альтернатив, каждая из которых приносит прибыль в размере 
𝑝
𝑖
, 𝑖 =
1, … , 𝑁
. Необходимо выбрать не более 
k
из данных альтернатив так, чтобы сум-
марная прибыль была бы максимальна. На альтернативы наложены некоторые 
ограничения нескольких типов, а именно:
 

i
-я альтернатива может быть выбрана только в том случае, если выбрана 
j
-я; 

i
-я альтернатива не может быть выбрана, если выбрана 
j
-я; 

хотя бы одна из альтернатив, 
i
-я или 
j
-я, обязательно должна быть выбра-
на; 

одна и только одна из альтернатив (
i
-я или 
j
-я) обязательно должна быть 
выбрана; 

k
-я альтернатива может быть выбрана, только если выбрана хотя бы одна 
из альтернатив: 
i
-я или 
j
-я. 
Для математической постановки задачи введем переменные логического (бу-
лева) типа, а именно положим 
𝑥
𝑖
= {
1, если альтернатива 𝑖 выбирается
0, если альтернатива 𝑖 не выбирается
.
Целевую функцию задачи можно записать в виде 
𝑝
1
𝑥
1
+ ⋯ 𝑝
𝑁
𝑥
𝑁
. 
Покажем, как можно выразить математически ограничения вышеперечислен-
ных типов: 
1)
𝑥
𝑖
− 𝑥
𝑗
≤ 0
; 
2)
𝑥
𝑖
+ 𝑥
𝑗
≤ 1
; 
3)
𝑥
𝑖
+ 𝑥
𝑗
≥ 1
; 
4)
𝑥
𝑖
+ 𝑥
𝑗
= 1
; 
5)
𝑥
𝑘
− 𝑥
𝑖
− 𝑥
𝑗
≤ 0
. 
Таким образом, разнообразные ограничения на выбор альтернатив могут быть 
выражены с помощью линейных ограничений, накладываемых на булевы пере-
менные. 
Естественно, что, кроме вышеприведенных типов ограничений, возмож-
ны и многие другие.