Модели, методи и алгоритми на нелинейното програмиране
Изтегляне 268.41 Kb.
|
Решението на тази система е у*1 = 15/29, у*2 = 3/29, у*3 = 2/29, у*4 = 9/29, откъдето О P1 =5x1x2-1x32 = (15/29). 10,273  5,314 Р2 =
х12x3-1 = (3/29).10,273  1,063 Р3 = 10x23 = (2/29) .10,273 0,708 Р4 = 2x1-1x2x3-3 = (9/29).10,273 3,188,
Решението на тази система, което е оптималното решение на пря-ката задача, е х*1 (То може да бъде определено в следната последователност: от уравне-нието за Р3 —> х2, от произведението P1P4 —> x3 и от Р2 --> x1). Пример 10.6. Да се минимизира позиномът J min J = 2х13х23 + 4х1-2х2 + x1x2 + 8x1x2l , x1,x2 > 0. В случая N = 4,п = 2, N > п + 1 и условията за ортогоналност и нормалност не определят единствено решение за уj. За намирането на такова решение се използуват дуалната задача и допълнителна оптимизационна процедура по следния начин. Условията за ортогоналност и нормалност са 
Тъй като броят на променливите e с l по-голям от броя на уравне-нията, три от променливите, например у1,у2,у3 могат да бъдат опреде-лени чрез четвъртата у4. От условията по-горе непосредствено се получава системата 
чието решение е 
Съответната дуална задача е да се максимизира 
Максимизирането на W е еквивалентно на максимизирането на W, но преобразуването на ln W е облекчено. Затова се определят 
Тъй като пряката задача е изпъкнала, стойността на у4, която максимизира W, е единствена и се определя от условието 
След несложни преобразувания се получава 
или
откъдето у*4 
Оптималната стойност J* e 
Следователно Р3 = 0,1819.(13,069)  2,3772 = х1х2 Р4 = 0,4088(13,069)  5,3426 = 8х1х2-1
Решението на тази система е 
МЕТОД НА ПОСЛЕДОВАТЕЛНАТА ЛИНЕЙНА АПРОКСИМАЦИЯ (АЛГОРИТЪМ НА ФРАНК-УОЛФ) Методите на последователната апроксимация се подразделят на методи с линейна апроксимация и методи с квадратична апроксимация. При тях нелинейната целева функция се заменя с последователност от линейни или квадратични приближения, което при линейни ограничения позволява повтарящо се използуване на метода на линейното или квадратичното програмиране. Някои от алгоритмите обхващат и случаи на нелинейни ограничения чрез използуване на подходяща линери-зация. Тук е представен алгоритъм на Франк-Уолф, който е последователен метод с линейна апроксимация, в който се съчетава използуването на симплекс-метода и на процедурата за едномерно търсене от раздел -10.12. Задачата е да се максимизира J J = f(X) при ограниченията АХ < b, Х > 0. Ако Xk e допустимо решение, за целева функция се използува линейно приближение около Xk 
Тъй като f(Xk) и  f(Xk)Xk ca константи, те могат да бъдат от-странени, при което се получава следната задача на ЛП Да се максимизира g(Х) = f(Xk )Х
при ограниченията: АХ < b,X > 0. Чрез използуването на симплекс-метода се определи оптималното решение XL, на линейната задача, което е на границата на допустима-та облает. Очевидно стойностите на g(X) непрекъснато нарастват при движение по линейния сегмент от Xk към ХL, (ако Xk не е най-доброто възможно решение). Ако обаче XL е далеч от Xk , линейната апрокси-мация може да не е добра, така че нелинейната функция f(X) може да не нараства непрекъснато при движението от Xk към ХL,. Затова като ново допустимо решение Xk+1 за следващата итерация се избира не ХL, а точката от линейния сегмент (Xk,X L), в която f(X) има максимална стойност. Тази точка се определя чрез процедура за едномерно търсе-не, подобна на тази от раздела 10.1.2., в която единствената променлива, по която се търси максимум, е частта  от вектора [ХL — Xk ]. Новото допустимо решение Xk+1 се представя във вида
Xk+1 = Xk +  [XL-Xk], където е
стойността на  която максимизира
Процедурата се прекратява на к-та итерация, когато Xk и Xk-1 са достатъчно близки, или когато се удовлетвори условието g (XL) < g(Хk). В последния случай по-нататъшни подобрения на решението не са възможни. Задачите на ЛП на всяка итерация се различават само по коефици-ентите на целевата функция. Затова, от гледна точка на изчислителни загуби, може да бъде полезно използуването на процедурите за анализ на чувствителността от раздел 4.4.1. Пример 10.7. Разглежда се задачата на квадратичното програми-ране Да се максимизира f(х) = 6x1 + 9х2 - Зх12 - 4х1х2 - 3х22 при ограниченията 2x1 +3x2 < 3, х1х2 > 0. За начално допустимо решение се избира Х° = [1/2,1/2]. Определя се  f(X) = [6 - x1 - 4x2 ,9 - 4x1 - 6х2].
Итерация 1  f(X0) = [1,4]
Новата линейна задача е да се максимизира g(Х) = x1 + 4х2 при ограниченията на началната задача. Оптималното решение е ХL = (0,1), а стойностите на g(Х) в точките Х° и XL са съответно 21/2 и 4. Следователно има смисъл да се определи ново допустимо решение 
   
стойност при  /(Х1) = [2,3]
Новата задача на ЛП е с целева функция g(Х) = 2x1 + Зx2. Тя има безкрайно много оптимални решения, тъй като правите на целевата функция и ограничението имат еднакъв наклон. Следователно, ако се избере XL = [0,1] или на някаква друга точка от правата 2х1 + 3х2 = 3 в допустимата облает, g(Х1) = g(XL) и решението X1 = [0,1] не може да бъде подобрено. Поради това, приблизителното оптимално решение на началната задача е X1 = [0,1], за което f(X1) = 6. То съвпада с точното оптимално решение, определено за същата задача в примера 4. < НЕИЗПЪКНАЛО ПРОГРАМИРАНЕ. МЕТОД НА ПОСЛЕДОВАТЕЛНАТА БЕЗУСЛОВНА МАКСИМИЗАЦИЯ задачите на изпъкналото програмиране определеният локален екстремум е и глобален екстремум. Често обаче в практически задачи предположенията за изпъкналост не се изпълняват. Един разпро-странен подход в такива случаи е да се използува алгоритъм на тър-сене, като определя локален екстремум, като процедурата на търсене се повтаря неколкократно, започвайки всеки път от различии начални условия. Най-добрият сред тези локални екстремуми се избира като приблизително оптимално решение. Широко разпространение е получил алгоритъмът на търсене, известен като метод на последователната безусловна максимизация (МПБМ). Той се основава на решаването на последователност от бе-зусловни задачи, получени след преобразуване на началната условна задача, чийто решения се схождат към локалния максимум на усло-вната задача. Основната идея е близка до тази за използуване на множи-телите на Лагранж. Съществуват два алгоритъма на МПБМ. Първият от тях, известен като алгоритьм на външната точка или алгоритъм на наказателните функции, използува наказателни функции, конто при-нуждават последователно получаваните недопустимы решения на безу- словните задачи да клонят към допустимата област. При втория алгоритъм, наричан алгоритьм на вътрешната точка или алгоритьм на бариерните функции,
изяснява по-нататък. За всяка от безусловните задачи се дефинира целева функция J(X,r) от вида
където г е параметър, г > 0, а В(Х) е бариерна функция със следните свойства: 
— В(Х.) е малко (голямо), когато X е далеч от (близо до) грани-цата на допустимата облает — -В(Х) —> Най-често В(Х) се избира във вида 
където втората сума отразява изискванията за неотрицателност хj > 0, записани като - xj < 0, в каквато форма са и ограниченията gj (X) — bj < 0, j = l,т. Ако f(X) е вдлъбната функция, a gi(X) - изпъкнала, l/gi(X) е вдлъбната, п Търсенето започва със задаване на произволна стойност на r, r° > 0 и на начална точка Х°, която трябва да бъде вьтрешна, т.е. разпо-ложена вьтре в допустимата област, а не върху границата. При зада-деното r0, като се използува методът на най-стръмното изкачване, се определя точката на максимума Х*(r°) на J(X,r°). Оптималното решение е в допустимата област, тъй като в точките X близо до границата B(Х) ще има голяма отрицателна стойност и максимизиращият алгоритъм ще отстрани такива решения. Възможно е обаче оптималното решение X* на началната задача да е разположено върху границата на допустимата област. Именно по-ради тази причина се решава последователност от безусловни задачи, с последователно намаляващи стойности на r, r —> 0, при което оптималното решение на i- та задача е начална точка за (г + 1)-та задача. Ако ri е стойността на r, използувана в r- та безусловна задача,  , където 0 <  < 1, например  = 0,05. По такъв начин последователните решения Х*(ri) са вътрешни точки и те клонят към X*.
Изчисленията се прекратяват, когато се постигне достатъчна бли-зост на две последователни решения. Ако началната задача е изпъкнала, може да се покаже, че f[Х*(ri)] < f(X*) < f[X*(ri)] + riВ[X(ri)], т.е. riВ[X(ri)] е максималната грешка, с която се определя f(X*). Широкото приложение на метода, което се дължи на неговата про- стота, показва, че точността и числената устойчивост на резултатите, както и скоростта на сходимост, зависят в значителна степен от стой-ностите на параметрите r и а, както и от избора на началната точка Х° (вж. например [8]). 10.3. ЗАКЛЮЧЕНИЕ Представени бяха преки и непреки методи и алгоритми на НЛП. Преките методи решават нелинейната задача непосредствено, без ме-ждинно преобразуване в линейна задача. Типични техни представители са градиентните методи, конто се използуват за решаването на задачи без и със ограничния. В последния случай условните задачи предварително се трансформират в безусловни задачи. Непреките методи използуват преобразуване на нелинейната задача в спомагателна линейна задача. Непреки са например методите на сепарабелното, квадратичното и геометричното програмиране, кои-то решават ефективно специфични класове нелинейни задачи с важно значение за практиката. Решението на спомагателната задача може да представлява точно или приблизително решение на началната задача, както това беше показано съответно за задачите на квадратичното и сепарабелното програмиране. Изследванията в областта на НЛП са много интензивни. Особено внимание се отделя на създаването на надеждни програмни продукти за решаване на задачи с голяма размерност, предназначени за общо и индивидуално ползуване, за големи изчислителни системи и персоналии компютри. Каталог: lib lib -> Преводач Елена Атанасова Коректор Ива Данева Формат 84/108/32 Печатни коли 15 дф „абагар" Велико Търново ик „сова" Варна как да се използва тази книга lib -> За медитацията ошо въведение lib -> Поредица ние обичаме животните lib -> Тайната на скорпион lib -> Разчупване на оковите Победа над: Отрицателните мисли lib -> Въведение Изтегляне 268.41 Kb. Сподели с приятели:
| ||||||||||||
т условията Р*j = y j* J * , j =
се съставя нелинейната система
1,264, x*2 =0,414, х*3
0,590.
0,4088. Следователно
= 1. Следователно X1 = [0,1],f(X1) = 6. Итерация 2
, когато разстоянието между X и границата на до-пустимата облает —> 0. 
ри което J(X, r) e вдлъбната функция.
