Реферат: Цілочислове програмування - Refy.ru - Сайт рефератов, докладов, сочинений, дипломных и курсовых работ

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

Рефераты по математике » Цілочислове програмування

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

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

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

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