Основні поняття і сутність цілочислового програмування

Цілочислове програмування – це вид задач лінійного програмування, в яких змінні, що використовуються й отримані результати мають цілочислове значення.

Задачі цілочислового програмування можуть бути лінійними, якщо обмеження і цільова функція задачі є лінійною залежністю, або нелінійними – якщо залежності будуть мати нелінійну форму.

Слід вказати, що широке використання задач цілочислового програмування в економічних дослідженнях полягає в тому, що необхідно отримувати цілочислове рішення. Цілочислове програмування виникло в 50-60-ті роки 20 століття на основі робіт Дж. Данцига і Р. Гомори.

Задача цілочислового програмування записується так:

, (5.1)

за умов того, що х_і є цілим числом і позитивним.

Для знаходження оптимального вирішення цілочислових задач застосовують відповідні методи. Найпростішим методом вирішення цілочислової задачі є знаходження її оптимального роз в'язку як задачі, що має лише неперервні змінні, з подальшим округленням останніх.

Для знаходження оптимальних планів задач цілочислової програмування застосовують дві групи методів:

- методи відтинання;

- комбінаторні методи.

Сутність методів відтинання полягає у поступовому «звуженні» області допустимих напрямів вирішення задачі. Пошук цілочислового оптимального вирішення задачі починають з розв'язування задачі з так званими послабленими обмеженнями, тобто без урахування вимог цілочисленності змінних. Далі введенням у модель спеціальних додаткових обмежень, що враховують цілочисленність змінних, багатокутник допустимих рішень послабленої задачі поступово зменшується з отриманням змінних оптимального вирішення до отримання цілочислових значень. До цієї групи належать:

Ø методи розв'язування повністю цілочислових задач (дробовий
алгоритм Гоморі);

Ø методи розв'язування частково цілочислових задач (другий
алгоритм Гоморі, або змішаний алгоритм цілочислового програмування).

Комбінаторні методи цілочислової оптимізації базуються на повному переборі всіх допустимих цілочислових рішень, тобто вони реалізують процедуру цілеспрямованого перебору, під час якої розглядається лише частина розв’язків (досить невелика), а решта враховується одним із спеціальних методів. Найпоширенішим у цій групі методів є метод віток і меж.

Рекомендації з формулювання і вирішення задач цілочислового програмування:

1. Кількість цілочисельних змінних зменшувати наскільки можливо. Наприклад, цілочисельні змінні, значення яких повинно бути не менше 20, можна розглядати як безперервні.

2. На відміну від загальних задач лінійного програмування, додавання нових обмежень, особливо включених цілочисельних змінних, звичайно зменшує час вирішення задач цілочислового програмування.

3. Якщо немає необхідності в знаходженні точного оптимального цілочисельного рішення, відмінного від безперервного рішення, наприклад, 3%. Тоді реалізацію методу гілок і меж для задачі максимізації можна закінчувати, якщо відношення різниці між верхньої і нижньої межою до верхньої межі менше 0,03.