Тема 3. Нелінійне програмування.
3.1. Загальна характеристика методів розв’язування задач нелінійного програмування.
Під час моделювання реальних економічних процесів слід враховувати складні й переважно нелінійні взаємозв’язки між параметрами досліджуваних систем. Методи розв’язування задач оптимізації із нелінійними цільовими функціями й нелінійними обмеженнями розглядаються у спеціальному розділі математичного програмування –нелінійному програмуванні. До типових сфер його застосування можна віднести задачі планування й управління промисловим виробництвом, товарними ресурсами й капіталовкладеннями, в яких передбачається, що ефективність виробництва або використання ресурсів змінюється не пропорційно до його обсягів. Наприклад, у задачах транспортного типу вартість перевезень одиниці вантажу часто має значні коливання залежно від обсягу транспортування.
Математична модель задачі нелінійного програмування (НЛП) має такий вигляд:
(3.1)
за умов обмежень
(3.2)
У загальному
випадку цільова функція задачі і /або/
функції і системи обмежень можуть бути
нелінійними відносно змінних
Отже, задача лінійного програмування
є окремим випадком щойно розглянутої
задачі.
Для розв’язування задач нелінійного програмування не існує єдиного універсального методу, аналогічного до симплексного методу в лінійному програмуванні. Підходи до пошуку методів розв’язування задач НЛП визначаються типами нелінійних залежностей і обмежень задачі. Істотно, що в цих задачах область допустимих розв’язків не завжди є опуклою, а точка оптимуму, на відміну від випадку лінійного програмування, може бути не лише кутовою, а й міститися на межі або всередині даної області.
Широка сукупність методів розв’язування задач нелінійного програмування базується на використанні диференційного числення для знаходження точок екстремумів функцій.
Сутність згаданих щойно методів розв’язування нелінійних задач розкриємо в межах їх класифікації, згідно з якою вирізняють такі методи:
класичної математики знаходження екстремумів функцій;
для задач з обмеженнями-рівностями;
для задач з обмеженнями-нерівностями.
Методи першої групи грунтуються на дослідженнях необхідних і достатніх умов існування екстремумів функцій з використанням їх частинних похідних першого і другого порядків. Це означає, що всі міркування виконуються за припущення про неперервність та диференційованість, а також відсутність умов невід’ємності і цілочисельності змінних задачі.
До методів другої групи можна віднести метод зведеного градієнта (метод Якобі), який є узагальненням симплексного методу лінійного програмування, а також найпоширеніший метод множників Лангранжа, який докладніше буде розглянуто далі.
Методи третьої групи переважно базуються на використання умов Куна-Таккера (метод Франка-Вульфа) існування екстремумів функцій. Але в загальному випадку для задач цього типу не можна сформулювати достатніх умов існування екстремуму, через що не можна точно визначити тип знайденого оптимуму, тобто встановити, який він – локальний чи глобальний. Тому використання даних умов є найефективнішим для задач з опуклими цільовими функціями, оскільки будь-який їх локальний екстремум є одночасно і глобальним.
Кожний з градієнтних методів розв’язування нелінійних задач з обмеженнями у вигляді нерівностей являє собою ітеративний процес послідовних наближень, в результаті якого формується послідовність точок –розв’язків задачі у напрямі найшвидшого зростання (спадання) цільової функції. Нагадаємо, що градієнтом функції є вектор її частинних похідних у певній точці, який визначає напрям і швидкість зростання функції. Істотно, що оптимум задачі, який знайдено градієнтними методами, є лише локальним.
Для розв’язування деяких класів задач нелінійного програмування застосовуються методи, які передбачають певний вид цільової функції.
Так, для задач з опуклими цільовими функціями у вигляді квадратичної форми
використовуються методи квадратичного програмування, які ґрунтуються на теоремі Куна-Таккера про існування екстремуму функції Лагранжа для досліджуваної задачі.
Нехай цільова функція задачі як функція багатьох змінних є сепарабельною, тобто її можна подати у вигляді алгебраїчної суми однорідних функцій відносно однієї змінної (аргументу):
Тоді наближені екстремуми функцій визначаються методами лінійно-кускової апроксимації. Їх основна ідея полягає в кусково-лінійній апроксимації початкової нелінійної функції лінійними залежностями, які розглядаються для кожної складової сепарабельної функції в інтервалах, що визначені точками сітки. Досліджуючи зміни цих функцій на кінцях інтервалів, можна перетворити початкову нелінійну задачу на задачу лінійного програмування, яка оперує з приростами цільової функцій та обмежень.