Нелінійне програмування - одна зі складових математичного програмування

Нелінійне програмування - одна зі складових математичного програмування

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


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


Класифікується нелінійне програмування в залежності від різновиду функції F (x), функції обмежень та розмірності вектора рішень x. Так, назва завдання залежить від кількості змінних. При використанні однієї змінної нелінійне програмування може бути виконано за допомогою безумовної однопараметричної оптимізації. Серед змінних понад одну можна використовувати безумовну багатопараметричну оптимізацію.

Для вирішення завдань лінійності використовують стандартні методи лінійного програмування (наприклад, симплекс-метод). А ось при нелінійному спільного способу рішення не існує, вибирається в кожному окремому випадку своє і воно також залежить від функції F (x).

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

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

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

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


Існують такі методи нелінійного програмування:

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

- Метод Монте-Карло, при якому визначається паралелепіпед n-ої розмірності, що включає в себе безліч планів, для подальшого моделювання випадкових N-точок з рівномірним розподілом в даному паралелепіпеді.

- Метод динамічного програмування зводиться до багатовимірного завдання оптимізації завдань до меншої розмірності.

- Метод випуклого програмування реалізується в пошуку мінімального значення випуклої функції або максимального значення увігнутої на випуклій частини безлічі планів. У випадку, коли безліч планів являє собою випуклий багатогранник, тоді може бути застосований симплексний метод.