ворена до наступної задачі булева програмування:
В В
Якщо дискретна змінна x приймає довільні цілі дискретні значення c 1 , c 2 , c 3 , ..., c k , то в цьому випадку співвідношення (1) і (2) відповідно перетворюються на такі співвідношення:
В В
Таким чином, завжди можна обмежитися розглядом завдання булева програмування замість задачі дискретного програмування.
3. Перетворення завдання лінійного булева програмування до задачі нелінійного булева програмування
Завдання виду
(1)
(2)
в числі багатьох задач комбінаторної оптимізації віднесена до класу труднорешаемих . Отже, для ефективного вирішення на обчислювальних машинах завдань великого розміру потрібно шукати алгоритмічні принципи, що дозволяють визначати оптимальне рішення без необхідності явно перераховувати елементи множини булева вектора x = (x 1 , x 2 , ..., x n ) +2 n .
Саме ця ідея неявного (на противагу явного) перерахування рішень і лежить в основі методів, пропонованих і досліджуваних у даній книзі. Ідейна основа останніх полягає в перетворенні вихідної задачі (1), (2) до наступної задачі булева програмування:
. (3)
При переході від задачі (1), (2) до задачі (3) виникає питання: чи не втрачається чи смисловий зміст вихідної задачі при переході до нової форми. Виявляється, не втрачається, це пояснюється наступним чином: Максимізуючи функцію Ф (х) по булевим змінним x = ( x 1 , x 2 , ..., x n ), практично ми, по-перше, максимізували чисельник виразу (3), тобто лінійну функцію булевих змінних
В
що відповідає завданню (1). По-друге, при максимізації виразу (3), мінімізується знаменник цього виразу, тобто
В
Отже, мінімізація вираження хоча це процедура не забезпечує точного виконання умови (2), а сприяє виконанню цього ж умови.
У подальшому дослідженні задачі про рюкзаку (див. п.п. 4.1) буде викладена обчислювальна схема отримання рішення задачі (3) у вигляді упорядкованого ряду булевих змінних
(4)
але цей ряд булевих змінних може не задовольняти виконанню обмеження виду (2). Після отримання впорядкованого ряду (4) кожен черговий елемент цього ряду по черзі зліва направо буде вставлений у вирази (2) і таким чином перевірено виконання умови
В
до максимального числа перших n Вў змінних упорядкованого ряду (4).
Таким чином, перехід від вихідної задачі лінійного булева програмування виду (1), (2) до нової задачі - максимізації фішерських типу функціоналу виду (3) логічний.
Контрольні запитання
Роль і місце моделей булева програмування в проблемі оптимізації.
Основні види моделей лінійного булева програмування.
Про поліноміальних і не поліноміальних завданнях в дискретної оптимізації.
Перетворення завдання з дискретними змінними до задачі з булевими змінними.
Перетворення завдання *** до задачі нелінійного булева програмування.
Як записується функціонал фішерських типу.
Література
1. Растрігін Л.А. Сучасні принципи управління складними об'єктами, М.: Радянське радіо, 1980 р. - 232 стор
2. Хамдамов Р.Х., Каюмов Ш. Моделювання та оптимізація роботи насосної станції// Матеріали першої міжнародної науково-технічної та практичної конференції: Проблеми і перспективи автоматизації виробництва і управління// Автоматизація-97. I частина. Ташкент, 1997. - С. ...
