Економічна постановка цілочисельної задачі математичного програмування

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

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

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

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

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

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

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

1) точні методи:

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

• комбінаторні методи;

2) наближені методи.

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

До цієї групи належать:

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

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

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

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

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

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

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

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

.*

*

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

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