5.2 Двійкові змінні

 

Дуже часто цілочисельними задачами є задачі, в яких шукані змінні можуть приймати не будь-які цілі значення, а тільки одне із двох: або 0, або 1. Такі змінні називаються двійковими або булевими.

Розповсюдженими задачами із двійковими змінними є задачі вибору оптимального розв’язку (варіанта) з певного числа заданих розв’язків (варіантів). Якщо варіант входить в оптимальний розв’язок, то двійкова змінна, яка відповідає цьому варіанту, дорівнює 1. Якщо варіант не входить в оптимальний розв’язок, то відповідна двійкова змінна дорівнює 0. Наприклад, якщо лінія електропередачі входить в оптимальну електричну мережу, то двійкова змінна, яка відповідає цій лінії дорівнює 1; якщо лінія електропередачі не входить в оптимальну електричну мережу, то відповідна двійкова змінна дорівнює 0.

На відміну від традиційних змінних х_i двійкові змінні будемо позначати

Застосування двійкових змінних дозволяє накладати на розв'язувану задачу цілий ряд логічних умов типу «якщо..., то…».

Якщо в оптимальний розв’язок повинен входити один із двох (i і j) варіантів, то сума змінних:

                                                 (5.2)

Якщо в оптимальний розв’язок повинні входити й i-й і j-й варіанти, то сума змінних:

                                                 (5.3)

Якщо в оптимальне розв’язок може входити або не входити, кожний із двох (i і j) варіантів, то сума змінних:

                                                 (5.4)

Якщо при вході (не вході) в оптимальний розв’язок i-го варіанта в цей розв’язок повинен ввійти (не ввійти) і j-й варіант:

                                                       (5.5)

Аналогічні умови можна записати для трьох і більше варіантів. Якщо з n можливих варіантів в оптимальне розв’язок повинні входити тільки m варіантів (m<n), то:

                                   (5.6)

Очевидно, що кількість логічних умов типу «якщо..., то…» не обмежено.