Алгоритъмът на метода на Лагранжевите множители
Начало | За нас | обратна връзка
метод на Лагранж множител.
метод на Лагранж множител е една от техниките, които ни позволяват да се реши нелинейно програмиране проблем.
Нелинейна програмиране е клон на математическото програмиране, методи за решаване на оптимизационни проблеми с нелинейна функция цел и е възможно област, определена от нелинейни ограничения учене. В икономиката, това съответства на факта, че резултатите (ефективност) се увеличи или намали непропорционално промяна в използване на ресурсите везни (или, което е същото, производство скала) напрежение. поради разделянето на цената на производствените предприятия в променливите и условно-константа; поради насищане на търсенето на стоки, когато всеки следващ единица да продават по-трудно в сравнение с предишните, и така нататък. г.
Проблемът е формулиран като нелинеен програмиране проблем намери оптималното специфична целева функция
когато условията
където х е векторът на неизвестни;
г (х) - ограничение функция (непрекъснато диференцируема);
б - вектора константи ограничения.
Решение на нелинейни програмиране проблем (глобално максимална или минимална) могат да принадлежат към някоя границата или вътрешността на възможно комплекта.
За разлика от задачата на линейното програмиране, в проблема с нелинейно програмиране оптимална не е задължително да лежи на границата на зоната, определена от ограниченията. С други думи, предизвикателството е да се избере такива неотрицателни променливи са предмет на ограничения под формата на система от неравенства, с което максимално (или минимум) на функцията. В този случай, формата не уточнява целевата функция или неравенство. Могат да бъдат различни случаи: целевата функция е нелинейна и линейни ограничения; обективната функция е линейна и ограничен (най-малко един от тях) са нелинейна; и целевата функция и нелинейни ограничения.
Нелинейна програмиране проблем се намира в областта на природните науки, инженерство, икономика, математика, в областта на бизнес отношения в науката за управление.
Нелинейна програмиране, например, е свързана с основната икономическа задача. Така че проблемът с разпределението на оскъдните ресурси или максимална ефективност, или, ако изследването за потребителите, консумацията на наличието на ограничения, които изразяват в условията на липса на ресурси. В такъв общо твърдение на математическа формулировка на проблема не може да бъде възможно, но в специфичното приложение на количествена гледна точка на всички функции може да се определи директно. Например, завод произвежда пластмасови изделия. Ефективността на производството се оценява печалби и парични ограничения се тълкуват като труд, производствени мощности, производителността оборудване и т.н.
Методът на "разходи - ефективност" също се вписва в схемата на нелинейни програмиране. Този метод е разработен за използване при вземането на решения в управлението. Общата функция на ефективността е богатство. Това поражда два проблема на нелинейни програмиране: първият - за да се постигне максимален ефект при ограничени разходи, а вторият - минимизиране на разходите, при условие, че ефектът е над определена минимална степен. Обикновено тази задача е добре моделирано от нелинейно програмиране.
Нелинейни проблеми са сложни, те често са опростени от факта, че те водят до линейни. За тази цел, обикновено се приема, че в определена част на функционални увеличава целеви или намалява пропорционално на независимите променливи. Този подход се нарича от приближените по части линейни, то се прилага, обаче, само за някои видове нелинейни проблеми.
Нелинейни проблеми в определени условия, се решават чрез функцията на Лагранж: намирането й точка на седлото, и по този начин да намерят решение. Сред изчислителни алгоритми Н. п. Голяма място се заема от градиентни методи. Universal същия метод за нелинейни проблеми там и, както изглежда, не може да бъде, защото те са изключително разнообразни. Особено трудно се решават проблеми multiextremal.
Един от методите, които ви позволяват да се намали проблема с нелинейно програмиране за решаване на системата уравнения е методът на Лагранж множители.
С помощта на метода на множител на Лагранж, необходимите условия са установени и по същество, която позволява идентифицирането на оптималната точка на оптимизационни задачи с ограничения във формата РА равенства. По този начин проблемът с ограничения превръщат в еквивалент-валентна проблем на непринуден оптимизация, който включва някои от най-неизвестните параметри, наречена Ла Гранж множители.
Lagrange метод формиращи се състои в намаляването на условно екстремум до проблеми безусловно екстремум допълнителна функция - т п .. функция на Лагранж.
множители # 955; 1. # 955; 2. # 955 М наречен. Лагранж множители.
Ако стойността на x1. x2. хп. # 955; 1. # 955; 2. # 955; m са разтвори на уравнения определящи неподвижна точка на функцията Lagrange, а именно, за диференцируеми функции са разтвори на системата от уравнения
тогава, когато достатъчно общи x1 предположения. x2. хп достави крайната стойност е.
Да разгледаме проблема за свеждане до минимум на функцията на наш променливи, подлежащи на ограничения във формата на половете:
В съответствие с метода на Лагранж множители, задачата се превръща в следващата непринуден проблема оптимизация:
минимизиране L (х, # 955) = F (х) - # 955; * Н (х) (3)
където L функция (х; # 955) се нарича Лагранж,
# 955; - неизвестен константа, която се нарича Lagrange множител. от знака # 955; не се налагат никакви изисквания.
Да предположим, че за дадена стойност # 955 = # 955 0 абсолютен минимум на функция L (х, # 955) по отношение на X се постига при х = x0 и Х0 удовлетворява уравнението h1 (x0) = 0. След това, както се вижда лесно, Х0 минимизира (1) с (2), тъй като всички стойности на х отговарят (2), h1 (х) = 0 и L (х, # 955) = мин е (х).
Разбира се, вие трябва да изберете стойност # 955 = 955 # 0, така че абсолютен минимум точка координира x0 удовлетворяват уравнение (2). Това може да стане като се вземат предвид # 955; като променлива, намери абсолютния минимум на функцията (3), като функция на # 955; и след това изберете # 955; в която равенство (2). Ние се убедите в това като пример.
Минимизиране е (х) = x1 2 + 2 х2 = 0
Съответните непринуден оптимизация е написано, както следва:
Решение. Приравняването на два компонента L градиент до нула, получаваме
За да се провери дали неподвижна точка х съответства ° до минимум, се изчислява Хесенски матрични елементи на функция L (х; U) считат като функция на х,
което оказва положително определено.
Това означава, че L (х, ф) - изпъкнала функция на х. Следователно, координатите x1 = 0 # 955; Х2 = 0 # 955; / 2 се определя глобален минимум точка. Оптималната стойност # 955; Установено е, чрез заместване на стойностите на X1 и X2 0 0 uravnenie2x1 + х2 = 2, от 2 # 955 + # 955; / 2 = 2, или # 955; 0 = 4/5. По този начин, относителната минимум се постига, когато Х1 = 0 4/5 0 и Х2 = 2/5 и равно мин е (х) = 4/5.
При решаването на проблема с примера разгледахме L (х; # 955) като функция на две променливи х1 и х2, и в допълнение, се приема, че стойността на параметъра # 955; подбира така, че да отговарят на ограничение-chenie. Ако решението на системата
като целеви функции # 955; не може да се получи, след това на стойностите на х и # 955; Те са открити чрез решаване на следната система, състояща се от N + 1 уравнения с N + 1 неизвестни:
За да намерите всички възможни решения на тази система, можете да използвате числени методи за търсене (като метод на Нютон). За всеки от разтворите () е необходимо да се изчисли елементите на Hessian матрични функции L, считани като функция на х, и се установи дали това е положително определена матрица (локален минимум) или отрицателен определен (локален максимум).
Lagrange метод мултипликатори може да бъде удължен до случая, когато задачата има няколко ограничения под формата на уравнения. Помислете за един общ проблем, който изисква
под ограничения HK = 0, к = 1, 2 К.
функция на Лагранж се следния вид:
тук # 955; 1. # 955; 2. # 955; К е коефициент Lagrange, т.е. неизвестни параметри, чиито стойности трябва да се определят. Чрез равнява частични производни по отношение на х към нула, ние получаваме следната система от уравнения п с п неизвестни:
Ако се намери решение на горното под формата на векторни функции # 955; Трудно е, че е възможно да се разшири системата от включването на ограничения във формата на равенства
Разтвор разширена система, състояща се от N + к уравнения с п + K неизвестна функция определя фиксирана точка процедура за проверка L. се реализира След минимум или максимум, който се основава на изчисляване на елементите на Hessian функция L, се разглежда като функция на х, просто както това е направено в случай на проблем с едно ограничение. За някои проблеми, разширените система N + к уравнения с п + неизвестни К не могат да имат решения и метод на Лагранж множител е неприложимо. Трябва да се отбележи, обаче, че тези проблеми в практиката са рядкост.
Ние считаме, че специалния случай на общото нелинейно програмиране проблема, като се предполага, че системата съдържа само ограничения на уравнението, няма условия неотрицателност и променливи, и - функцията е непрекъсната заедно с частни производни
Този проблем се нарича проблема с условна екстремум или класически проблем оптимизация.
За да се намери решение на този проблем, да се въведе набор от променливи, наречени на Лагранж множители. съставляват Лагранж
са частични производни на системата и обмислят п + т уравнения
с N + м неизвестни Всеки разтвор от уравнения (7) определя точка, която може да се осъществи екстремум на функцията. Следователно решаването на системата от уравнения (7) за получаване на всички точки, при които функцията (6) могат да имат крайни стойности.
Алгоритъмът на метода на Лагранжевите множители
функция 1.Sostavlyaem Lagrange.
2.Nahodim частични производни на Лагранж функция по отношение на променливи XJ, # 955; и и ги равнява на нула.
3.Reshaem система от уравнения (7), ние откриваме, точката, в която целевата функция на проблема може да бъде изключителна.
4. Сред точките, които са съмнителни екстремум намери онези, при достигане на екстремум, и изчисляване на стойностите на функцията (6) в тези точки.
Предистория: Според плана на продуцентска компания трябва да произвежда 180 продукти. Тези продукти могат да бъдат направени две технологични начини. В методите на производство, производствените разходи 1 x1 са 4x1 + x1 2 RUB. , и при производството на изделия 2 x2 начин те правят 8x2 + 2 бр 2 рубли. Определяне на броя на елементите на всеки метод трябва да направят, за да себестойността на производството е било минимално.
Целевата функция на този проблем е дадено от
®min при условия x1 + х2 = 180, Х2 ≥0.
1.Sostavlyaem Лагранж
.
2. Изчисляване на частични производни по отношение на x1. x2, # 955; и да ги приравняваме на нула:
3. Чрез решаването на получената система от уравнения, ние получаваме x1 = 91, Х2 = 89
4.Sdelav заместване в обективната функция х2 = 180-X1. получаване на функция на една променлива, а именно f1 = 4x1 + x1 2 + 8 (180-х1) + (180-х1) 2
Изчисляват или 4x1 -364 = 0,
A: Броят на продуктите, произведени от първия метод е равна x1 = 91, Х2 = втория метод 89, където цел стойността на функцията е равна на 17 278 втриване.