Модели, методи и алгоритми на нелинейното програмиране
Изтегляне 268.41 Kb.
|
|
МОДЕЛИ, МЕТОДИ И АЛГОРИТМИ НА НЕЛИНЕЙНОТО ПРОГРАМИРАНЕ За разлика от симплекс-метода на ЛП, не съществува универсален метод или алгоритъм, който може да решава ефективно всякакви специфични задачи на НЛП. Съществуват обаче ефективни алгоритми за важни специални класове нелинейни задачи, които са създадени на базата на определени предположения за вида и свойствата на целевата функция и ограниченията. По-нататък се представят някои важни класове нелинейни задачи и избрани работоспособни методи и алгоритми за безусловна и условна оптимизация. 10.1. МЕТОДИ ЗА БЕЗУСЛОВНА ОПТИМИЗАЦИЯ Разглеждат се представители на две основни групи: методи на пряко търсене и градиентни методи. Алгоритмите от двете групи се използуват самостоятелно или като елементи на по-сложни процедури за условна оптимизация. 10.1.1. МЕТОД НА ПРЯКОТО ЕДНОМЕРНО ТЪРСЕНЕ Методите на пряко търсене са разработени основно за функции от една променлива. Те се използуват и като елементи на алгоритми за функции от няколко променливи. Предполага се, че оптимизираната функция е строго унимодална върху интервала на търсене. Основната идея на тези методи се състои в идентифицирането на начален интервал - интервал на неопределеност, който съдържа точката на екстремума x* и в последователно свиване на този интервал, докато точката х* бъде определена с желана точност. Широко известии са ме-тодът на дихотомното търсене и методът на средната точка. Тук се разглежда първият от тях, като се предполага задача за максимизация.
п  равилата за намаляване на на-
чалния интервал: а) f(x1) > f(x2), точката х* е между а и х2, а < х* < х2; б)f(x1) < f(x2 ), точката х* е между x1 и b, x1 < х* < b; в) f(x1) = f(x2), точката х* е между x1 и х 2, x1< х* < х2. На всяка стъпка се отстранява интервалът, който не съдържа х*, така че накрая интервалът на неопределеност може да се намали до е. Точките x1 и х2 се определят по следния начин. Нека хл и хд са лявата и дясната граница на текущия интервал, като в началото хл = а , а хд = 6. Припокриващите се интервали хл < х < х2 и x1 < х < хд са построени така, че x 1 — хл = хд — х2 и е = х2 - x1. Оттук 
Пример 10.1. 
 Нека = 0,002.
На първата стъпка хл = 0, хд = 4. Резултатите от пресмятанията са представени в табл.10.1. Означенията л (д) в таблицата показват, че на следващата стъпка хл (хд) е равно на х1 (х2). На последната стъпка хл = 2,9985 и хд = 3,0043. Следователно точката х* е в интервала 2,9985 < х * < 3,0043. Като оценка на х* често се приема средната точка  = 3,0014. Тази стойност е твърде близка до стойността на точния оптимум, която е х* = 3,0.
10.1.2. ГРАДИЕНТНИ МЕТОДИ Предполага се, че функцията /(X) е два пъти непрекъснато ди-ференцируема по компонентите на X и че е вдлъбната или изпъкнала върху областта на търсене на екстремум, съответно при задачите за максимизация или минимизация. Разглежданите методи са итерационни. На всяка итерация от те-кущата точка X се извършва стъпка в посоката на най-бързото на-растване (намаляване) на /(X), с определена големина. Тъй като тази
посока се определя от вектора на градиента (антиградиента), методи-те се наричат градиентни методи. Сред тях широко приложение има методьт на най- стрьмното изкачване (спускане), при който големина-та на стъпката се избира така, че да се максимизира изменението на функцията f(X). Именно този метод се представя по-нататък. Нека f(X) се максимизира и Х0 е началната точка, от която за-почва търсенето. Ако  f(X ) означава градиента в точката Xk, после-дователността от точки се определя от рекурентното съотношение
 
      
От необходимите условия лесно се намират х* 1 = 1/9 За да се реши задачата по метода на най-стръмното изкачване, се задава X0 = [1,1] и се записва градиентът 
Итерация 1  
Следователно Итерация 2 
Фиг. 10.2. 
Итерация 3 
След заместване в израза за 
Итерация 4 
След извършване на изчисленията по схемата от предишните итерации се определят: 
Итерация 5  /(X4) [-0,0648,0,0178].
Тъй като  f(X4) [0,0], изчисленията може да се прекратят. Прибли-зителното оптимално решение е
X4  [0,1275,0,4333], X4 X*.
Процесът на търсене е показан на фиг.10.2. 10.2. МЕТОДИ ЗА УСЛОВНА ОПТИМИЗАЦИЯ Методите за условна оптимизация се класифицират на непреки и преки методи. Непреките методи използуват преобразуване на начал-ната нелинейна задача в една или няколко линейни задачи, конто се ре-шават като задачи на ЛП. От този клас тук се разглеждат методите на сепарабелното, квадратичното и геометричното програмиране. При преките методи нелинейната условна задача се решава непо-средствено, като се преобразува в безусловна задача и се използуват мо-дификации на градиентните методи. Към този клас се отнасят ал-горитъмът на Франк- Уолф и методът на последователната безусловна оптимизация, конто са представени по-нататък. Предполага се, че целевата функция f(X) и ограниченията g(X) са непрекъснато диференцируеми, като ограниченията g(X) < 0 обхващат и условията X > 0. 10.2.1. СЕПАРАБЕЛНО ПРОГРАМИРАНЕ Сепарабелното програмиране е специален случай на НЛП, при конто целевата функция и ограниченията са сепарабелни функции. Една функция f ( x 1 , x 1 , . . . , x n ) e сепарабелна, ако може да бъде представена като сума от п функции от една променлива f1 (x 1 ), f2 (x 2 ), ... , fn(x n ) 
Именно поради това, че функцията f ( x 1 , x 2 , ... , х п) е разделена на части fj, (xj), всяка от които включва само едно хj и конто се сумират, тази функция се нарича сепарабелна. Най-прост пример на сепарабелна функция е целевата функция в за.дачата на ЛП. Някои нелинейни функции, които не са сепарабелни, се преобразуват в такива чрез подходяща субституция. Например за-дачата за максимизиране на J = x1x2,x3 чрез полагането и = x1x2x3 се преобразува в следната задача: Да се максимизира J = и при ограниченията lп и = ln x1+ ln х2 + lпх3, x 1 , х2,х3 > 0. Ако променливите x 1 ,х 2 и х3 могат да имат неотрицателни стойности (x 1 > 0, i = 1,2,3), се дефинират нови строго положителни променливи 
откъдето
Полагат се и1 = z1z2z3, и2 = z1z2, и3 = z1z3, u4 = z2z3 и началната задача се преобразува в еквивалентната сепарабелната задача 
Да се максимизира , при ограниченията
cx1+x2+x3 и X1x2xЗ Решаването на сепарабелни задачи се основава на апроксимира-нето на функциите от една променлива fj(xj) с линейни по участъци функции и използуването на метод на СЦП или на симплекс-метода на ЛП. Нека сепарабелната задача е от вида Да се максимизира (минимизира) при ограниченията 
Апроксимацията на функцията fi(хi) (или на gji(хi)) върху интервала [аi,bi] се извършва по следния начин. Задават се L, точки на прекъсване xi1 < хi2 < ... < xiLi, така че х i1 = xi, и xiLi = bi, конто определят Li - 1 линейни участъци на fi(xt) (или на gji(хi)). На фиг.10.3 е показан случай с Li = 5. Тогава коя и да е точка xi 
където  е тегловният коефициент на k-та точка на прекъсване на i-та променлива и
ФИГ. 10.3 При това, тъй като точката xi е в един от подинтервалите на [аi,bi] или
 
където за стойностите на са справедливи току-що изложените огра-ничения. Например линейният сегмент над интервала [xi3, xi4] на 
фиг.10.3 се задава от 
където
Каталог: lib lib -> Преводач Елена Атанасова Коректор Ива Данева Формат 84/108/32 Печатни коли 15 дф „абагар" Велико Търново ик „сова" Варна как да се използва тази книга lib -> За медитацията ошо въведение lib -> Поредица ние обичаме животните lib -> Тайната на скорпион lib -> Разчупване на оковите Победа над: Отрицателните мисли lib -> Въведение Изтегляне 268.41 Kb. Сподели с приятели:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
0,1111 x*2 = 4/9
0,4444. Тъй като хесиановата матрица Н < 0, X* е точка на максимум.
от условието 
= 0 се определи
0.19707, на 
[аi, bi] може да се представи във вида