Page 47 - 4168

Поділ на підмножини у симплекс-методі здійснюється
шляхом введення нових обмежень x ≤ [ ] або x i ≥ x 0 i +
[ ] 1.
x
0 i
i
При розв’язку задачі максимізації функції використову-
ють верхні оцінки.
Двійкові змінні
Окремим випадком цілочислових задач є задачі, в яких
шукані змінні можуть приймати не будь-які цілі значення, а
тільки одне з двох: 0 або 1. Такі змінні називаються двійкови-
ми або булевими.
Поширеними задачами з двійковими змінними є задачі
вибору оптимального розв’язку (варіанту) з певного числа за-
даних розв’язків (варіантів). Якщо варіант входить в оптима-
льний розв’язок, то двійкова змінна, відповідна цьому варіан-
ту, дорівнює 1. Якщо варіант не входить в оптимальний
розв’язок, то відповідна двійкова змінна дорівнює 0. Напри-
клад, якщо конденсаторна батарея встановлена у вузлі, то
двійкова змінна, відповідна цьому вузлу дорівнює 1; якщо
конденсаторна батарея не встановлена у вузлі, то відповідна
двійкова змінна дорівнює 0.
На відміну від традиційних змінних х i, двійкові змінні
позначають δ i , де i =1, 2 ... n.
Застосування двійкових змінних дозволяє накладати на
розв’язувану задачу цілий ряд логічних умов типу «якщо ..., то
...».
Якщо в оптимальний розв’язок повинен входити один з
двох (і чи j) варіантів, то сума зміннихδ i + δ j = 1.
Якщо в оптимальний розв’язок повинні входити і i-й, і j-й
варіанти, то сума зміннихδ i + δ j = 2 .
Якщо в оптимальний розв’язок може входити або не вхо-
дити кожен з двох (і чи j) варіантів, то сума змінних
δ i + δ j ≥ 0 .
Якщо при вході (не вході) в оптимальний розв’язок i-го
варіанту в цей розв’язок повинен ввійти (не ввійти) j-й варіант,
тоδ = δ .
j
i
Аналогічні умови можна записати для трьох і більше ва-
ріантів. Якщо з п можливих варіантів в оптимальний розв’язок
повинні входити тільки т варіантів (т<п), то
δ 1 + δ 2 + ... + δ n = m .

47