Постановка задачі
Існує доволі широкий клас задач математичного програмування, в економіко – математичних моделях яких одна або кілька змінних мають набувати цілих значень, наприклад, коли йдеться про кількість верстатів у цеху, тобто коли така вимога випливає з особливостей технології виробництва. До цілочислового програмування належать також задачі оптимізації, в яких змінні набувають лише двох значень – 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.
Так діють доти, доки не буде знайдено цілочислового розв'язку або доведено, що задача не має допустимих розв'язків у множині цілих чисел.
Досвід показує, що процес розв'язування задач великої розмірності методом Гоморі повільно збіжний. Істотними є також похибки округлення, які можуть призвести до того, що отриманий цілочисловий план не буде оптимальним .