Page 87 - 4719

4. Наведіть алгоритм методу віток і меж.
5. На скільки підмножин необхідно розбити множину
можливих розв’язків згідно методу віток та меж?

ПРАКТИЧНЕ ЗАНЯТТЯ 15

Тема: ВИЗНАЧЕННЯ ОПТИМАЛЬНОГО РОЗВ’ЯЗКУ
ДВІЙКОВИХ ЦІЛОЧИСЛОВИХ ЗАДАЧ

Мета заняття: навчити студентів визначати оптимальний
розв’язок двійкових цілочислових задач

1. Основні теоретичні положення

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

86