Алгоритм розв’язування задач цілочислового програмування

Алгоритм розв’язування задач цілочислового програмування наступний:

1. Розв'язується задача лінійного програмування без обмежень на цілочисельність, наприклад, симплекс-методом.

2. Якщо оптимальне рішення задачі лінійного програмування нецілочисельне, то проводиться «велика ітерація». Будується лінійне обмеження, якому задовольняє будь-яке цілочисельне рішення задачі і не задовольняє отримане оптимальне нецілочисельне значення. Геометрично це означає – провести перетин (гіперплощина), який відсікав би нецілочисельну вершину, не зачіпаючи решту цілочисельних крапок. Такий перетин називають правильним. Правильний перетин повинен задовольняти наступним умовам:

1) умова відсікання: оптимальне рішення задачі лінійного програмування не задовольняє умові відсікання;

2) умова правильності: всі цілочисельні рішення задачі задовольняють умові відсікання.

Оскільки для початкової задачі додаткове обмеження (відсікання) даватиме неприпустиме базисне рішення, необхідно провести «малі ітерації» для отримання оптимального рішення. Якщо отримане оптимальне рішення нецілочисельне, то проводиться наступне відсікання. В іншому випадку пошук завершений.

Р. Гомори запропонував ідею формування додаткових обмежень, яка призводить до вирішення задач цілочислового програмування за кінцеве число кроків.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Основні поняття і сутність цілочислового програмування	\|	Метод Гомори

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.004 сек.