Шпора з МЧА 3 курс 1 семестр
У більшості інженерних завдань побудова математичної моделі не вдається звести до задачі лінійного програмування.
Математичні моделі в задачах проектування реальних об'єктів або технологічних процесів повинні відображати реальні фізичні, що протікають в них, і, як правило, нелінійні процеси. Змінні цих об'єктів чи процесів пов'язані між собою фізичними нелінійними законами, як-от закони збереження маси чи енергії. Вони обмежені граничними діапазонами, що забезпечують фізичну реалізація даного об'єкта або процесу. В результаті більшість задач математичного програмування, які зустрічаються в науково-дослідних проектах і в задачах проектування – це завдання нелінійного програмування (НП).
Нехай у математичній моделі проектованого об'єкта чи процесу безперервна функція є функцією мети (функцію якості),
задають обмеження у вигляді рівностей
задають обмеження у вигляді нерівностей, де вектор параметрів проектованого об'єкта, процесу або системи, оптимальні значення яких повинні бути знайдені.
Тоді завдання нелінійного програмування може бути сформульовано так:
знайти вектор , що доставляє мінімум (максимум) цільової функції при m лінійних та (або) нелінійних обмежень у вигляді рівностей
та (p-m) лінійних та (або) нелінійних обмежень у вигляді нерівностей
0, \qquad j=\overline.">
Протягом останніх двох десятиліть із нелінійного програмування виділилися самостійні розділи:
- опукле програмування,
- квадратичне програмування,
- цілісне програмування,
- стохастичне програмування,
- динамічне програмування та ін.
Завдання опуклого програмування – це завдання, в яких визначається мінімум опуклої функції (або максимум увігнутої), заданої на опуклій замкнутій множині. Ці завдання серед задач нелінійного програмування найбільше вивчені.
Серед задач опуклого програмування докладніше вивчені завдання квадратичного програмування. У ці завдання цільова функція – квадратична, а обмеження – лінійні.
У задачах цілісного програмування невідомі параметри можуть набувати лише цілих.
У завданнях стохастичного програмування цільової функції чи функціях обмежень містяться випадкові величини, які підпорядковуються законам теорії ймовірностей.
У задачах динамічного програмування обмеження містять параметр час і у своїй описуються диференціальними рівняннями. Процес знаходження рішень у задачах динамічного програмування є багатоетапним.
2. Класифікація методів нелінійного програмування
Для вирішення задачі нелінійного програмування було запропоновано багато методів, які можна класифікувати за різними ознаками.
За кількістю локальних критеріїв цільової функції методи нелінійного програмування діляться на:
По довжині вектора методи поділяються на:
- однопараметричні або одновимірні (n=1),
- багатопараметричні або багатовимірні (n>1).
За наявності обмежень методи нелінійного програмування поділяються на:
- без обмежень (безумовна оптимізація),
- з обмеженнями (умовна оптимізація).
За типом інформації, що використовується в алгоритмі пошуку екстремуму, методи поділяються на:
- методи прямого пошуку, тобто. методи, у яких при пошуку екстремуму цільовоїфункції використовуються лише її значення;
- градієнтні методи першого порядку, у яких під час пошуку екстремуму функції використовуються значення перших похідних;
- градієнтні методи другого порядку, у яких під час пошуку екстремуму функції поруч із першими похідними використовують і другі похідні.
Жоден метод нелінійного програмування перестав бути універсальним. У кожному конкретному випадку необхідно пристосовувати метод до особливостей розв'язуваної задачі.
3. Класичний метод визначення умовного екстремуму
Завдання нелінійного програмування (завдання НП) у загальному вигляді формулюється так:
де функції нелінійні.
На відміну завдання ЛП для завдань НП немає універсального методу решения.
У задачі ЛП допустима множина R завжди є опуклим з кінцевим числом крайніх точок. Тому, скориставшись симплекс-методом і перебравши тільки крайні точки, можна за кінцеве число кроків знайти оптимальне рішення. У завданнях НП, навпаки, опуклість допустимої множини та кінцівка числа його крайніх точок зовсім необов'язкові. Це і є причиною основної проблеми вирішення завдань НП.
Для визначення умовного екстремуму (тобто екстремуму при обмеженнях) можна скористатися методами диференціального обчислення, коли функція має не нижче другої похідної. Розглянемо деякі важливі поняття та теореми класичного аналізу, які лежать в основі класичних методів пошуку умовного екстремуму.
Теорема 3.1 (теорема існування екстремуму). Якщо - безперервна функція, визначена на замкнутій і обмеженій множині, то вона досягає на цій множині, принаймні один раз, своїх максимального та мінімального значень.
Наступна теоремавизначає можливі розташування максимуму (або мінімуму).
Теорема 3.2. Якщо є безперервною функцією кількох змінних, визначеної на допустимій множині R, то максимальне значення, якщо воно існує, досягається в одній або декількох точках, які належать одному з таких множин: 1) S1 - множина стаціонарних точок; 2) S2 - безліч точок кордону; 3) S3 - безліч точок, де функція недиференційована.
Визначення 3.1. Безліч точок S1(x1, x2, .xn) функції f(x) називається безліччю стаціонарних точок, якщо вони задовольняють умові
Визначення 3.2. Функція f(x) досягає локального максимуму в точці , якщо для всіх точок x, що лежать у малій околиці точки має місце нерівність
Визначення 3.3. Функція f(x) досягає глобального (абсолютного) максимуму в точці x 0 якщо для всіх точок справедлива нерівність
Для знаходження стаціонарних точок функції f(x) можна використовувати таку теорему.
Теорема 3.3. Нехай диференційована в деякій допустимій області R. Якщо в деякій внутрішній точці області R функція f(x) досягає відносного максимуму, то
Щоб визначити, чи є знайдені стаціонарні точки точками максимуму чи мінімуму, необхідно досліджувати функцію в околиці стаціонарних точок і визначити, є вона опуклою чи увігнутою.
Визначення 3.4. Нехай R - опукле безліч точок n - мірного простору. Функція f, визначена на R, називається опуклою вгору, якщо для будь-якої пари точок та довільного виконується нерівність
то функція називається увігнутою.
Якщо (3.4) або (3.5) виконуються як суворі нерівності, то функція називається суворо увігнутою або строго опуклоювідповідно.
Критерій опуклості та увігнутості функції n-змінних можна сформулювати у вигляді наступної теореми.
Теорема 3.4. Функція f(x), що диференціюється, суворо увігнута в деякій околиці точки , якщо виконуються такі умови:
0; \quad \begin f_(x_0) & f_(x_0) & f_(x_0) \\ f_(x_0) & f_(x_0) & f_(x_0) \\ f_(x_0) & f_(x_0) & f_(x_0) \end
І так далі, тобто якщо знаки визначників чергуються починаючи з