Нелінійне програмування в математичному програмуванні

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

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

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

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

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

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

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

Відео: Урок 1. Рішення завдання лінійного програмування в Excel за допомогою надбудови "пошук рішення"

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

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

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

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

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

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