ICA Spur 3 курс 1 семестър

В повечето инженерни проблеми изграждането на математически модел не може да се сведе до проблем с линейно програмиране.

Математическите модели в проблемите на проектирането на реални обекти или технологични процеси трябва да отразяват реалните физически и, като правило, нелинейни процеси, протичащи в тях. Променливите на тези обекти или процеси са свързани помежду си чрез физически нелинейни закони, като например законите за запазване на масата или енергията. Те са ограничени до екстремни диапазони, които гарантират физическата осъществимост на даден обект или процес. В резултат на това повечето проблеми с математическото програмиране, срещани в изследователски проекти и проблеми с дизайна, са проблеми с нелинейно програмиране (NP).

Нека непрекъснатата функция в математическия модел на проектирания обект или процес е целевата функция (функция на качеството),

задайте ограничения под формата на равенства

задайте ограничения под формата на неравенства, където е векторът на параметрите на проектирания обект, процес или система, оптималните стойности на които трябва да бъдат намерени.

Тогава проблемът с нелинейното програмиране може да се формулира по следния начин:

намерете вектора, който осигурява минимум (максимум) на целевата функция при m линейни и (или) нелинейни ограничения под формата на равенства

и (p-m) линейни и (или) нелинейни ограничения под формата на неравенства

0, \qquadj=\overline.">

През последните две десетилетия от нелинейното програмиране се появиха независими секции:

изпъкнало програмиране,
квадратично програмиране,
целочислено програмиране,
стохастично програмиране,
динамично програмиране и др.

Задачите на изпъкнало програмиране са задачи, при които се определя минимумът на изпъкнала функция (или максимумът на вдлъбната), дадена върху изпъкнало затворено множество. Тези проблеми сред проблемите на нелинейното програмиране са най-изследвани.

Сред проблемите на изпъкналото програмиране по-подробно са изследвани проблемите на квадратичното програмиране. В тези задачи целевата функция е квадратна, а ограниченията са линейни.

При проблеми с целочислено програмиране неизвестните параметри могат да приемат само цели числа.

В проблемите на стохастичното програмиране целевата функция или ограничителните функции съдържат случайни променливи, които се подчиняват на законите на теорията на вероятностите.

В проблемите на динамичното програмиране ограниченията съдържат време като параметър и се описват с диференциални уравнения. Процесът на намиране на решения в задачите на динамичното програмиране е многоетапен.

2. Класификация на методите за нелинейно програмиране

За решаване на проблема с нелинейното програмиране са предложени много методи, които могат да бъдат класифицирани според различни критерии.

Според броя на локалните критерии в целевата функция методите за нелинейно програмиране се разделят на:

Според дължината на вектора методите се делят на:

еднопараметричен или едномерен (n=1),
мултивариантен или многомерен (n>1).

Според наличието на ограничения методите за нелинейно програмиране се разделят на:

без ограничения (безусловна оптимизация),
с ограничения (условна оптимизация).

Според вида на информацията, използвана в алгоритъма за търсене на екстремум, методите се разделят на:

методи за директно търсене, т.е. методи, при които при търсене на екстремум целтафункции се използват само нейните стойности;
градиентни методи от първи ред, при които стойностите на първите му производни се използват при търсене на екстремума на функция;
градиентни методи от втори ред, при които при търсене на екстремума на функция наред с първите производни се използват и вторите производни.

Нито един метод на нелинейно програмиране не е универсален. Във всеки конкретен случай е необходимо прилаганият метод да се адаптира към спецификата на решавания проблем.

3. Класическият метод за определяне на условния екстремум

Проблемът с нелинейното програмиране (NP проблем) обикновено се формулира, както следва:

където функциите са нелинейни.

За разлика от проблема с LP, няма универсален метод за решаване на проблеми с LP.

В задачата LP допустимото множество R винаги е изпъкнало с краен брой крайни точки. Следователно, използвайки симплексния метод и сортирайки само екстремните точки, е възможно да се намери оптималното решение в краен брой стъпки. В NP задачи, напротив, изпъкналостта на допустимото множество и крайността на броя на неговите крайни точки са напълно незадължителни. Това е причината за основната трудност при решаването на NP задачи.

За да определите условния екстремум (т.е. екстремума при ограничения), можете да използвате методите на диференциалното смятане, когато функцията има поне втората производна. Нека разгледаме някои важни концепции и теореми на класическия анализ, които са в основата на класическите методи за намиране на условен екстремум.

Теорема 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) \край

И така нататък, това е, ако знаците на детерминантите се редуват, започвайки от