КАТЕГОРИЯ:


Астрономия- (809) Биология- (7483) Биотехнологии- (1457) Военное дело- (14632) Высокие технологии- (1363) География- (913) Геология- (1438) Государство- (451) Демография- (1065) Дом- (47672) Журналистика и СМИ- (912) Изобретательство- (14524) Иностранные языки- (4268) Информатика- (17799) Искусство- (1338) История- (13644) Компьютеры- (11121) Косметика- (55) Кулинария- (373) Культура- (8427) Лингвистика- (374) Литература- (1642) Маркетинг- (23702) Математика- (16968) Машиностроение- (1700) Медицина- (12668) Менеджмент- (24684) Механика- (15423) Науковедение- (506) Образование- (11852) Охрана труда- (3308) Педагогика- (5571) Полиграфия- (1312) Политика- (7869) Право- (5454) Приборостроение- (1369) Программирование- (2801) Производство- (97182) Промышленность- (8706) Психология- (18388) Религия- (3217) Связь- (10668) Сельское хозяйство- (299) Социология- (6455) Спорт- (42831) Строительство- (4793) Торговля- (5050) Транспорт- (2929) Туризм- (1568) Физика- (3942) Философия- (17015) Финансы- (26596) Химия- (22929) Экология- (12095) Экономика- (9961) Электроника- (8441) Электротехника- (4623) Энергетика- (12629) Юриспруденция- (1492) Ядерная техника- (1748) Arhitektura- (3434) Astronomiya- (809) Biologiya- (7483) Biotehnologii- (1457) Военни бизнесмен (14632) Висока technologies- (1363) Geografiya- (913) Geologiya- (1438) на държавата (451) Demografiya- ( 1065) Къща- (47672) журналистика и смирен (912) Izobretatelstvo- (14524) външен >(4268) Informatika- (17799) Iskusstvo- (1338) историята е (13644) Компютри- (11,121) Kosmetika- (55) Kulinariya- (373) културата е (8427) Lingvistika- (374) Literatura- (1642) маркетинг-(23702) математиците на (16968) Механична инженерно (1700) медицина-(12668) Management- (24684) Mehanika- (15423) Naukovedenie- (506) образователна (11852) truda- сигурност (3308) Pedagogika- (5571) Poligrafiya- (1312) Politika- (7869) Лево- (5454) Priborostroenie- (1369) Programmirovanie- (2801) производствено (97 182 ) индустрия- (8706) Psihologiya- (18388) Religiya- (3217) Svyaz (10668) Agriculture- (299) Sotsiologiya- (6455) на (42831) спортист строително (4793) Torgovlya- (5050) транспорт ( 2929) Turizm- (1568) физик (3942) Filosofiya- (17015) Finansy- (26596) химия (22929) Ekologiya- (12095) Ekonomika- (9961) Electronics- (8441) Elektrotehnika- (4623) Мощност инженерно ( 12629) Yurisprudentsiya- (1492) ядрена technics- (1748)

градиента методи




Лекция номер 8

Градиента методи за решаване на задачи на линейното програмиране. Методи за наказателни функции. Прилагане на нелинейни програмиране на проблемите на изследователската дейност.

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

Нека разгледаме проблема за максимизиране на нелинейни диференцируема функция е (х). Същността на градиент търсенето на максимален брой точки х * е съвсем проста: да вземе произволна точка х 0 и градиент Изчислено на този етап за определяне на посоката, в която е (х) се увеличава с най-голяма скорост (фиг. 7.4)

Фиг. 7.4

и след това се прави една малка стъпка в посока на резултатите, да отидете на нова точка х аз. След това отново, за да се определи най-добрата посока да се премине към следващата точка и х 2 m. ж. Фиг. 7.4 пътя за търсене е счупен х 0, X 1, X 2 ... Така, че е необходимо да се изгради последователност от точки х 0, X 1, X 2, ..., К х, ..., за да се доближи до точка максималната х *, т. е. последователност от точки на следните условия

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

Движението на точка х к в новата точка х К + 1 се извършва по права линия, минаваща през точка х к, и като уравнението

(7.29)

където λ K - цифров параметър, който зависи от размера на стъпката. След като стойността на параметъра в уравнение (7.29) се избира: λ к = λ к 0, така че става известно редовен точка да търсите прекъснатата линия.

Градиента методи се различават един от друг начин, за да изберете размера на стъпката - стойност λ к 0 параметър λ к. Можете, например, да се движат от една точка до друга с постоянна стъпка λ к = λ, т. Е. За всеки к

,

Ако се окаже, че Необходимо е да се върне до точка и намаляване на стойността на параметъра, например до ламбда / 2.

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

Ако се установи приблизително разтвор, търсенето може да бъде спряна основава на следните съображения. След всяка серия от определен брой стъпки сравняват със стойностите, постигнати от обективна функция F на (х). Ако след следващата серия от промени в е (х) не надвишава предварително определена малък брой , Търсенето се спира, и F (X) достигна стойност счита за необходима приблизително максималната и съответните X взети за X *.



Ако целевата функция F на (х) е вдлъбната (изпъкнали), а след това е необходимо и достатъчно условие за оптималност на х * е изчезването на градиента на функцията в този момент.

Общ вариант е градиент търсене, наречен метод на стръмните изкачване. Същността му е, както следва. След определяне на градиента в точка х да се движи по права линия Той се състои от х к + 1, при което се постига максималната стойност на функцията F (X), в посока на наклона , След това в този момент наскоро определен наклон, и движението се извършва по права линия в посока на нов градиент до точката х + 2, в което максималната стойност на F (X) в тази посока. Движението продължава, докато, докато стигнете до точка х *, съответстващ на най-високата стойност на целевата функция F на (х). Фиг. 7.5 показва модела на трафика към оптималната точка х * метода на най-стръмните изкачване. В този случай, по посока на градиента в х к се допира до нивото на повърхността на плодовете на линия (х) в точка х к + 1, като по този начин градиента при х + 1 е перпендикулярна на наклона (Сравни фиг. 7.4).

Преминаването от точка X до точка К придружено от е увеличение функция (X) със стойността

(7.30)

От израза (7.30) показва, че увеличаването на Това е функция на променливата , Т. Е. , В намирането на максимума на F на функция (х) по посока на градиента ) Трябва да бъде избрана стъпка изместване (фактор ), Което осигурява най-голямо увеличение на нарастване на функцията, името на функцията , стойност На което най-голямата стойност достигна Тя може да бъде определена от необходимо условие за екстремум :

(7.31)

Нека да намери израз за дериват, диференциране на уравнение (7.30) в като сложна функция:

Заместването на този резултат в (7.31), получаваме

(7.32)

Това уравнение има проста геометрична интерпретация: градиента в следващата точка х К + 1, е перпендикулярна на наклона на по-предишната точка х к.


Пример 7.4. Определя максимума на функцията , като се започне оптимизация условия за търсене ,

Solution. Ние ще придружава решението на графичен илюстрацията (фиг. 7.6). Според това уравнение на параболоид на въртене


конструирана ниво линия на тази повърхност. За тази цел, уравнението се намали до формата (1 х 1) 2 + (х 2 -2) 2 = 5-0,5 F, от които е видно, че линиите на пресичане с равнини параболоид успоредни на равнината Х О 1 х 2 (линии ниво) е кръг с радиус , Когато F = -150, -100, -50, съответно, са равни на техните радиуси И един общ център, разположен в (1, 2). Намери наклона на тази функция:

,

I етап. Изчисляват се:

Фиг. 7.6 започващи от х = 0 (5; 10), конструиран вектор 1/16, показва посоката на стръмните увеличаване на функцията на х 0. В тази област, се следната точка , В този момент ,

Използване на (7.32), получаваме

или 1-4 = 0, = 1/4. тъй като , Стойността намерен Това е максималната точка , 1 находка X = (5-16 / 4; 10-32 / 4) = (1, 2).

II етап. Отправна точка за втората стъпка х 1 = (1, 2). пресмятам = (- 1 4 4 ∙; -4 ∙ 2 + 8) = (0, 0). Така х 1 = (1, 2) е неподвижна точка. Въпреки това, тъй като тази функция е вдлъбната, намерената точка (1; 2) глобален максимум се достига.

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

Да разгледаме проблема с изпъкнала програмиране с линейни ограничения:

(7.33)

(7.34)

(7.35)

където ,

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

Нека да започнем с геометрична илюстрации решаване на проблеми процес (фиг. 7.7). Нека началната точка х 0 е в рамките на допустимото региона. От гледна точка X 0 може да се движи по посока на наклона Докато е (х) достига максимума. В този случай, е (х) се увеличава през цялото време, така че е необходимо да се спре в точка X на границата. Както се вижда от фигурата, той продължава да се движи по посока на наклона невъзможно, тъй като ще излезе от допустимата площ. Поради това е необходимо да се намери друга посока на движение, което от една страна, изходи от допустимото региона, а от друга - осигурява най-голямото увеличение в е (х). Това ще определи посоката на вектора Съставляващи вектор най-малкия остър ъгъл в сравнение с всеки друг вектор, като се започне от точка х Аз и лежи в осъществимо региона. Аналитично, там е вектор от състоянието на максимизиране на скаларна продукта , В този случай, векторът показва най-предпочитаната посока съвпада с гранична линия.


Следователно, следващата стъпка е необходимо да се премине към граничната линия, докато увеличението е (х); в този случай - до точка Х 2. Може да се види, че това, което следва да се придвижи в посоката на вектора Кое е условието за максимизиране на скаларна продукта , Т. Е. На граничната линия. Движението завършва х 3, тъй като в този момент търсенето се прекратява оптимизация защото функция е (х) има локален максимум. Тъй като в този момент вдлъбнатината на F (X) също достига глобален максимално допустимото област. Градиент максимум при х = 3 * х е тъп ъгъл с вектора на всеки на възможно региона, минаваща през х 3, така скаларен продукт ще бъде отрицателно за всяко допустимо К R, R 3, в допълнение към директор на границата. За него, вътрешният продукт = 0, тъй и перпендикулярни една на друга (гранична линия докосва повърхността F на ниво ред (х), минаваща през точката на максимално х *). Това уравнение е аналитичен индикация, че точка х 3, F функцията (X) е достигнала своя максимум.

Нека сега разгледаме аналитичната решение на задачата (7.33) - (7.35). Ако оптимизация започва от точка, разположена в допустимия регион (всички задачи се изпълняват чрез ограничаване колко строг неравенство), в движение трябва да бъде, както е посочено по-горе в посока на наклона. Сега обаче, изборът на λ к в уравнение (7.29) се усложнява от изискването следващата точка Той остава в приемливи района. Това означава, че тя координира, трябва да отговарят на ограниченията (7.34), (7.35), т.е., неравенствата ..:

(7.36)

Решаване на система от линейни неравенства (7.36), ние откриваме сегмента Допустимите стойности на параметъра λ к, в който момент х к +1 ще принадлежат към осъществимо региона.

Стойността на λ К *, се определя чрез решаване на уравнение (7.32):

Къде е (х) има локален максимум по посока λ к Трябва да принадлежи към сегмента , Ако получената стойност λ к е извън сегмента, след като λ к * приет , В този случай, следващата точка от пътя за търсене е на границата hyperplane съответстващ на системата на неравенството (7.36), в които полето крайната точка, получена чрез решаване на системата , интервал на приемливи стойности на параметъра λ к.

Ако оптимизация започва с точка на границата hyperplane, или друга точка на пътя за търсене е на hyperplane на границата, след това да се продължи движението на максималната точка, първо трябва да се намери най-добрата възможна посока тази цел трябва да бъде да се реши спомагателни проблема с математически програмиране и максимизиране imenno- функция

(7.37)

с ограничения

(7.38)

за Т, в които

(7.39)

(7.40)

където ,

В резултат, разтвор на (7.37) - (7.40) се намира вектор Конституиране градиент малката малък ъгъл.

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

След определяне на посоката на е λ к * стойност за следващата точка Търсене път. Той използва необходимо условие за екстремум във форма, подобна на уравнение (7.32), но заменяйки вектор , Т. Е.

(7.41)

Оптимизация спира, когато стигна до точка х к *, които ,

Пример 7.5. Увеличете функция с ограничения

,

Solution. Ние ще придружава своята графична илюстрация за визуално представяне на процеса на оптимизация. Фигура 7.8 показва по-голяма степен линии на повърхността и допустима област OABC, в която да се намери точката х *, доставя максимума на тази функция (вж. Пример 7 4).

За да започне оптимизация на уеб, например от гледна точка х = 0 (4, 2.5), който се намира на границата AB 4 х 1 х 2 = 14. В този случай е 0) = 4.55.

Нека да се намери стойността на градиента

0 в точка х , Освен това, и фигурата може да се види, че в възможно област са кривите на ниво с марка високи от F (X 0) = 4.55. Накратко, това е необходимо да се търси по посока на R 0 = (R 01, R 02) се движат към следващата точка х 1 е по-близо до оптимума. С цел решаване на този проблем (7.37) - (7.40) функция максимизиране с ограничения


Тъй като точката х 0 е само един (първи) гранична линия (I = 1) х 1 4 х 2 = 14, условието (7.38) е написана под формата на собствен капитал.

Рестриктивна система от уравнения на този проблем има само две решения (-0.9700, 0.2425) и (0.9700, -0.2425) директна замяна на тяхната функция T 0, ние се установи, че максималната Т 0 е различно от нула и постига в разтвора (-0,9700; 0.2425) по този начин се движи от 0 X трябва да бъде в посока на вектора R 0 = (0.9700, 0.2425), т.е. на границата VA.

За определяне на координатите на следващата точка X 1 = (X 11; 12 х)

(7.42)

трябва да се намери стойността на параметъра В която F функция (х) при х 1 достига до възможно най-голямата стойност. Но първо, намерете диапазона на приемливи стойности на параметъра В този момент х 1 ще принадлежат към осъществимо региона. System (7.36) в този случай има формата

(7.43)

Първото ограничение пропуснахме, тъй като точката х 1 лежи на линията AB. Решаването на системата (7.43), ще видим, че да се намери в интервала (0, 4.1237] (имайте предвид, че ние не се интересуваме само от отрицателната стойност на параметъра ). Нека да се намери стойността на Това се постига най-голямото увеличение на стъпки от функция, можете заглавието на движението от точка X 0 до х 1. В съответствие с условието (7.41)

,

отгдето = 2,0618. по този начин = -0.3999 <0. Следователно, = 2,0618. Според формулата (7.42) намираме координатите на новата точка х 1 (2, 3).

Ако продължим търсенето на оптимизация, а след това на следващия решението на спомагателни проблема (7.37) - (7.40) се установи, че T 1 = Това предполага, че точката X 1 е висока точка X * на обективната функция в региона възможно. Това се вижда от фигурата в точката X 1 е един от нивото докосва гранични линии на възможно региона. Ето защо, на точка х 1 е точката на максимално х *. В това е макс = F (X *) = 5,4.


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

начини за преместване, за да се гарантира изграждането на серия от точки, в близост до границата и в рамките на допустимото региона, или зиг-заг движение по протежение на границата с пресичането на последния. Както се вижда от фигурата, връщането от точка X 1 в допустимата област трябва да се извършва по наклон на границата функция Което се оказа счупен. Това ще гарантира, че след като отклонението на X 2 в посока на точката X екстремум *. Признак на екстремум в този случай ще бъде колинеарни вектори и ,