ластей. p align="justify"> Завдання оптимізації (мінімізації або максимізації) лінійної цільової функції з булевими змінними і лінійними обмеженнями в загальному вигляді описується за допомогою однієї з наступних моделей лінійного булева програмування:. Модель А - для задачі мінімізації
(1)
(2)
II. Модель В - для завдання максимізації
(3)
(4)
тобто потрібно мінімізувати або максимізувати лінійну цільову функцію q (x) по булевим змінним x j ГЋ {0,1} при виконанні умови, що задається системою лінійних нерівностей виду (2) або (4).
Проблема відшукання рішення задачі (1), (2) або (3), (4) може в принципі вирішуватися із застосуванням методу повного перебору, суть якого полягає в переборі всіх булевих векторів заданої довжини, перевірці для кожного вектора виконання лінійних обмежень, обчисленні значень цільової функції для допустимих векторів і виборі з них мінімального чи максимального значення цільової функції. Однак рішення, отримане методом повного перебору, пов'язане з великим обсягом обчислень, який неможливий при великих розмірностях завдання навіть на надпродуктивних ЕОМ. Так як кожна з n компонент незалежно від інших може приймати два значення 0 або 1, тому загальне число булевих векторів довжини n одно 2 n .
Це величина і характеризує складність алгоритму повного перебору. У зв'язку з тим, що для більшості завдань дискретної оптимізації повний перебір нездійсненний, були розроблені різні методи неявного перебору, які забезпечують знаходження точного рішення без перегляду всіх булевих векторів. Такими є різні варіанти методу відсікань, методу гілок і меж, методу динамічного програмування. Але досвід застосування цих методів при вирішенні реальних завдань з досить великим числом змінних показав, що багато завдань лінійного програмування з булевими змінними ще є невирішуваними на ЕОМ через брак машинного часу. Отже, із зростанням розмі ра завдання n вона стає "труднорешаемой", тобто практично нерозв'язною.
Задача (1), (2) або (3), (4) в числі багатьох задач комбінаторної оптимізації віднесена до класу "труднорешаемих" або, NP (nо polynomial) - повних задач. Причина полягає в тому, що алгоритму, вирішального поставлене завдання за час, обмежене поліномах від "розміру задачі", в даний час немає. p align="justify"> У зв'язку з цим дослідження, спрямовані на розробку нових ефективних або поліноміальних методів вирішення завдань лінійного програмування з булевими змінними, є, безсумнівно, актуальними. p align="justify"> Спочатку розглянемо широко поширені практичні завдання, описувані моделями лінійного програмування з булевими змінними.
2. Перетворення завдання з дискретними змінними до задачі з булевими змінними
В
Нехай x дискретна змінна, що приймає тільки цілі значення 0,1,2 , ..., k. Тоді цю змінну можна представити як лінійну комбінацію (p +1) булевих змінних y 0 , y 1 , ..., y p , тобто:
, (1)
де p-найменше ціле число, яке задовольняє умові
(2)
Приклад. Розглянемо таку задачу цілочисельного програмування
В В В В
цілі.
Мінлива x 1 приймає шість цілих значень: 0,1,2,3,4,5. Для цієї змінної k 1 = 5 . Візьмемо для змінної x 1 найменше ціле число p 1 , воно визначається з умови (2)
звідки
Виходячи з (1), можна зробити заміну змінних:
В
Мінлива x 2 приймає чотири цілих значення 0,1,2,3.
Отже, для
В
Вихідна завдання дискретного програмування перет...
