• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

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

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

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

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

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

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

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

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

1. I. ЗАДАЧИ ДЛЯ ПРАКТИЧЕСКИХ ЗАНЯТИЙ И САМОСТОЯТЕЛЬНЫХ РАБОТ
2. I. Застосування похідної та інтеграла до роз’язування задач елементарної математики.
3. III. Інформаційне забезпечення задачі
4. IIІ. Інформаційне забезпечення задачі
5. IV. Алгоритм вирішення задачі
6. IV. Алгоритм розв’язання задачі
7. IV. Алгоритм розв’язання задачі
8. IV. Алгоритм розв’язання задачі
9. Rete-алгоритм
10. VІ УМОВИ ЗАДАЧ
11. Word problem (задачи)
12. А) Задачі, що розкривають зміст дій

Переглядів: 944