Цілочислове програмування

Постановка задачі

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

До цілочислового програмування відносять задачі про призначення, найкоротший шлях і т. ін. У реальних задачах часто цілочислових значень набувають не всі, а одна чи кілька змінних. Такі задачі називають частково цілочисловими.

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

, (1)

за умов

; (2)

(3)

(4).

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

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

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

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

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

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

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

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

Найпоширенішим у цій групі методів є метод віток і меж.

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

Для розв'язування задач із бульовими змінними застосовують комбіновані методи, причому оскільки змінні є бульовими, то методи пошуку оптимуму значно спрощуються.

Метод Гоморі

Нехай маємо задачу цілочислового програмування (1) – (4). Для її розв'язування можна скористатися ітеративним методом Гоморі. Суть його полягає ось у чому:

1.Знаходять розв'язок послабленої, тобто задачі без вимог ці-
лочисловості змінних — (1) - (3).

Якщо серед елементів умовно-оптимального плану немає дробових чисел, то цей план є оптимальним планом задачі цілочислового програмування (1) - (4).

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

таблиці, в якому вона міститься) будується додаткове обмеження Гоморі:

де символ {} позначає дробову частину числа.

Для визначення дробової частини будь-якого числа від цього числа віднімають цілу його частину — найбільше ціле число, що неперевищує даного Цілу частину числа позначають символом [] .

Наприклад :

[1,3] = 1; [-1,3] =-2;

{1,3} = 1,3 - 1 = 03; {-1,3} = -1,3 - (-2) =2 - 1,3 = 0,7.

3. Додаткове обмеження після зведення його до канонічного вигляду і введення базисного елемента приєднується до остан­ньої симплексної таблиці, яка містить умовно-оптимальний план. Здобуту розширену задачу розв'язують, а далі перевіряють її розв'язок на цілочисювість. Якщо він не цілочисловий, то про­цедуру повторюють повертаючись до пункту 2.

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

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