Най-приемливият вариант на решението, който се взема на управленско ниво по всеки въпрос, се счита за оптимален, а процесът на намирането му се счита за оптимизация.

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

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

Оперативните изследователски методи се използват за намиране на оптимални решения в такива области на управление като организация на производствени и транспортни процеси, планиране на мащабно производство, материално-техническо снабдяване.

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

Същност на методите за изследване на операциите

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

Списъкът с въпроси, които играят важна роля за непосредствените ръководители на производството и които се решават в хода на използването на разглежданите методи:

  • степента на валидност на избраните решения;
  • Колко по-добри са те от алтернативите?
  • степен на отчитане на определящите фактори;
  • какъв е критерият за оптималност за избраните решения.

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

Методи на експертни оценки

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

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

Разгледаните методи за оптимизиране на редица управленски решения (експертни оценки) са ефективни при решаването на следните управленски задачи в производствения сектор:

  1. Изучаването на сложни процеси, явления, ситуации, системи, които се характеризират с неформализирани, качествени характеристики.
  2. Класиране и определяне по даден критерий на съществени фактори, които са решаващи по отношение на функционирането и развитието на производствената система.
  3. Разгледаните оптимизационни методи са особено ефективни в областта на прогнозирането на тенденциите в развитието на производствената система, както и нейното взаимодействие с външната среда.
  4. Повишаване на надеждността на експертната оценка на предимно целеви функции, които имат количествен и качествен характер, чрез осредняване на мненията на квалифицирани специалисти.

И това са само част от методите за оптимизиране на редица управленски решения (peer review).

Класификация на разглежданите методи

Методите за решаване на оптимизационни проблеми, въз основа на броя на параметрите, могат да бъдат разделени на:

  • Едномерни методи за оптимизация.
  • Многоизмерни методи за оптимизация.

Наричат ​​се още „числови методи за оптимизация“. За да бъдем точни, това са алгоритмите за неговото търсене.

Като част от прилагането на производните методи има:

  • директни методи за оптимизация (нулев ред);
  • градиентни методи (1-ви ред);
  • Методи от 2-ри ред и др.

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

Едномерни методи за оптимизация

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

Има следните методи за решаване на оптимизационни проблеми (едномерни):

  • метод на Фибоначи;
  • дихотомии;
  • златно сечение;
  • стъпка удвояване.

Метод на Фибоначи

Първо трябва да зададете координатите на точка x на празнината като число, равно на съотношението на разликата (x - a) към разликата (b - a). Следователно a има координата 0 спрямо интервала, а b - 1, средната точка - ½.

Ако приемем, че F0 и F1 са равни един на друг и приемем стойността 1, F2 ще бъде равен на 2, F3 - 3, ..., тогава Fn = Fn-1 + Fn-2. И така, Fn са числа на Фибоначи, а търсенето на Фибоначи е оптималната стратегия на така нареченото последователно търсене на максимума поради факта, че е доста тясно свързано с тях.

Като част от оптималната стратегия е обичайно да се избира xn - 1 = Fn-2: Fn, xn = Fn-1: Fn. За всеки от двата интервала ( или ), всеки от които може да действа като стеснен интервал на неопределеност, (наследената) точка спрямо новия интервал ще има или координати , или . Освен това като xn - 2 се взема точка, която има една от представените координати спрямо новия интервал. Ако използвате F(xn - 2), стойността на функцията, която е наследена от предишния интервал, става възможно да се намали интервалът на несигурност и да се прехвърли една стойност на функцията към наследяването.

В последната стъпка ще се окаже, че преминава към такъв интервал на несигурност като , докато средната точка е наследена от предишната стъпка. Като x1 се задава точка, която има относителна координата ½ + ε и крайният интервал на неопределеност ще бъде или [½, 1] по отношение на .

На 1-ва стъпка дължината на този интервал беше намалена до Fn-1: Fn (от една). При довършителните стъпки намаляването на дължините на съответните интервали се представя с числата Fn-2: Fn-1, Fn-3: Fn-2, …, F2: F3, F1: F2 (1 + 2ε). Така че дължината на такъв интервал като крайната версия ще вземе стойността (1 + 2ε): Fn.

Ако пренебрегнем ε, тогава асимптотично 1: Fn ще бъде равно на rn, с n→∞ и r = (√5 - 1) : 2, което е приблизително равно на 0,6180.

Трябва да се отбележи, че асимптотично, за значително n, всяка следваща стъпка от търсенето на Фибоначи значително стеснява разглеждания интервал с горния коефициент. Този резултат трябва да се сравни с 0,5 (коефициентът на стесняване на интервала на неопределеност в рамките на метода на разполовяване за търсене на нулата на функцията).

метод на дихотомия

Ако си представим определена целева функция, тогава първо трябва да намерим нейния екстремум на интервала (a; b). За да направите това, оста на абсцисата е разделена на четири еквивалентни части, след което е необходимо да се определи стойността на въпросната функция в 5 точки. След това се избира минимумът от тях. Екстремумът на функцията трябва да лежи в интервала (a"; b"), който е в съседство с минималната точка. Границите на търсене се стесняват 2 пъти. И ако минимумът се намира в точка a или b, тогава той се стеснява и четири пъти. Новият интервал също е разделен на четири равни сегмента. Поради факта, че стойностите на тази функция в три точки бяха определени на предишния етап, тогава е необходимо да се изчисли целевата функция в две точки.

метод на златното сечение

За значими стойности на n координатите на точки като xn и xn-1 са близки до 1 - r, равни на 0,3820 и r ≈ 0,6180. Натискът от тези стойности е много близо до желаната оптимална стратегия.

Ако приемем, че F(0.3820) > F(0.6180), тогава интервалът се очертава. Въпреки това, поради факта, че 0,6180 * 0,6180 ≈ 0,3820 ≈ xn-1, тогава в този момент F вече е известен. Следователно на всеки етап, започвайки от 2-ри, е необходимо само едно изчисление на целевата функция и всяка стъпка намалява дължината на разглеждания интервал с коефициент 0,6180.

За разлика от търсенето на Фибоначи, този метод не изисква фиксиране на числото n преди началото на търсенето.

„Златното сечение“ на сечението (a; b) е сечение, в което съотношението на дължината му r към по-голямата част (a; c) е идентично на съотношението на по-голямата част от r към по-малката, т.е. е, (а; в) до (в; б). Лесно е да се предположи, че r се определя от горната формула. Следователно, за значително n, методът на Фибоначи става даден.

Метод на удвояване

Същността е търсенето на посоката на намаляване на целевата функция, движение в тази посока в случай на успешно търсене с постепенно нарастваща стъпка.

Първо определяме началната координата M0 на функцията F(M), минималната стойност на стъпката h0 и посоката на търсене. След това дефинираме функцията в точка M0. След това правим стъпка и намираме стойността на тази функция в дадена точка.

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

Многовариантни методи за оптимизация

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

Групата от методи от 1-ви порядък се нарича още градиент, тъй като градиентът на тази функция се използва за установяване на посоката на търсене – вектор, чиито компоненти са частични производни на минимизираната функция по отношение на съответните оптимизирани параметри.

В групата методи от 2-ри ред се използват 2 производни (употребата им е доста ограничена поради трудностите при изчисляването им).

Списък с неограничени методи за оптимизация

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

  • Хук и Джийвс (изпълнение на 2 вида търсене – по модел и изследване);
  • минимизиране чрез правилния симплекс (търсете минималната точка на съответната функция, като сравнявате нейните стойности във върховете на симплекса при всяка отделна итерация);
  • циклично координатно спускане (използване като референтни точки за търсене на координатни вектори);
  • Розенброк (на базата на използването на едномерна минимизация);
  • минимизиране чрез деформирания симплекс (модификация на метода за минимизиране чрез обикновения симплекс: добавяне на процедурата на компресия, разтягане).

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

Има и методи, които използват конюгирани посоки (метод на Дейвидън-Флетчър-Пауъл). Неговата същност е представянето на посоките за търсене като Dj*grad(f(y)).

Класификация на математическите оптимизационни методи

Обикновено, въз основа на измерението на функциите (целта), те са:

  • с 1 променлива;
  • многоизмерен.

В зависимост от функцията (линейна или нелинейна) съществуват голям брой математически методи, насочени към намиране на екстремум за решаване на задачата.

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

  • методи за изчисляване на 1 производна на целевата функция;
  • многоизмерен (1-ва производна-векторна величина-градиент).

Въз основа на ефективността на изчислението има:

  • методи за бързо изчисляване на екстремум;
  • опростено изчисление.

Това е условна класификация на разглежданите методи.

Оптимизация на бизнес процесите

Тук могат да се използват различни методи в зависимост от решаваните проблеми. Обичайно е да се отделят следните методи за оптимизиране на бизнес процесите:

  • изключения (намаляване на нивата на съществуващия процес, премахване на причините за смущения и входен контрол, намаляване на транспортните маршрути);
  • опростяване (улеснена обработка на поръчки, намалена сложност на структурата на продукта, разпределение на работата);
  • стандартизация (използване на специални програми, методи, технологии и др.);
  • ускоряване (паралелно проектиране, стимулиране, оперативно проектиране на прототипи, автоматизация);
  • промяна (промени в суровините, технологиите, методите на работа, персонала, работните системи, обема на поръчките, процедурите за обработка);
  • осигуряване на взаимодействие (по отношение на организационни звена, персонал, работна система);
  • подбор и включване (относно необходимите процеси, компоненти).

Данъчна оптимизация: методи

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

Общите методи за данъчна оптимизация са както следва:

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

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

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

5. Многоизмерна оптимизация

Линейно програмиране

Оптимизация е целенасочена дейност, състояща се в получаване на най-добри резултати при подходящи условия.

Извиква се количествено определяне на качеството, което се оптимизира критерий за оптималност или целева функция .Може да се запише като:

(5.1)

където x 1 , x 2 , … , x nса някои параметри на обекта за оптимизация.

Има два вида оптимизационни проблеми - безусловни и условни.

Безусловна задача оптимизацията се състои в намиране на максимума или минимума на реалната функция (5.1) нандействителни променливи и определяне на подходящите стойности на аргументите.

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

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

Думата "програмиране" тук отразява крайната цел на изследването - да се определи оптималният план или оптимална програма, според която се избира най-добрият, оптимален вариант от многото възможни варианти за изследвания процес.

Пример такава задача е проблем за оптимално разпределение на суровините между различни индустрии при максимални производствени разходи.

Нека два вида продукти се правят от два вида суровини.

Означете: x 1 , x 2 - броят на единиците продукти съответно от първи и втори тип; c 1 , c 2 са единичните цени на продуктите съответно от първи и втори вид. Тогава общата цена на всички продукти ще бъде:

(5.2)

В резултат на производството е желателно общите производствени разходи да бъдат максимални.R (x 1, x 2 ) е целевата функция в този проблем.

b 1 , b 2 - количеството налични суровини от първи и втори тип;aij– брой единици и th тип суровина, необходима за производството на единицаjти вид продукт.

Като се има предвид, че потреблението на този ресурс не може да надвишава общото му количество, ние записваме ограничителните условия за ресурсите:

(5.3)

Относно променливитех 1 , х 2 можем също да кажем, че те са неотрицателни и безкрайни.:

(5.4)

Сред набора от решения на системата от неравенства (5.3) и (5.4) е необходимо да се намери такова решение (х 1 , х 2 ), за което функциятаРдостига най-високата си стойност.

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

Графичен метод за решаване на задача за линейно програмиране.

Нека се изисква да се намерих 1 и х 2 , удовлетворяващосистема от неравенства:

(5.5)

и условия неотрицателност:

(5.6)

за коя функция

(5. 7 )

достига максимум.

Решение.

Нека изградим системата от правоъгълни координатих 1 вол 2 област на възможните решения на проблема (фиг. 11). За да направим това, заменяйки всяко от неравенствата (5.5) с равенство, построяваме релевантнонего гранична линия:

(и = 1, 2, … , r)

Ориз. единадесет

Тази линия разделя цялата равнина на две полуравнини. За координатих 1 , х 2 всяка точка НОедна полуравнина, важи следното неравенство:

и за координатите на която и да е точка ATдругата полуравнина, обратното неравенство:

Координатите на всяка точка от граничната линия удовлетворяват уравнението:

За да се определи от коя страна на граничната линия се намира полуравнината, съответстваща на даденото неравенство, достатъчно е да се „тества“ една точка (най-простата точка О(0;0)). Ако при заместване на координатите му в лявата страна на неравенството то е изпълнено, тогава полуравнината се обръща към тестовата точка, ако неравенството не е изпълнено, тогава съответната полуравнина се обръща в обратна посока. Посоката на полуравнината е показана на чертежа чрез щриховане. неравенства:

съответстват на полуравнината, разположена вдясно от оста на ординатите и над оста на абсцисата.

На фигурата изграждаме гранични линии и полуравнини, съответстващи на всички неравенства.

Общата част (пресечната точка) на всички тези полуравнини ще бъде областта на възможните решения на този проблем.

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

Ориз. 12. Площта на възможните решения е празна, което съответства на несъответствието на системата от неравенства; няма решение

Ориз. 13. Площта на допустимите решения е представена с една точка A, която съответства на единственото решение на системата

Ориз. 14. Площта на възможните решения е ограничена, изобразена като изпъкнал многоъгълник. Има безкраен брой възможни решения

Ориз. 15. Площта на допустимите решения е неограничена, под формата на изпъкнала многоъгълна област. Има безкраен брой възможни решения

Графично представяне на целевата функция

на фиксирана стойностРопределя права линия, а при промянаР- семейство успоредни линии с параметърР. За всички точки, лежащи на една от правите, функцията Рприема една определена стойност, така че тези редове се наричат линии на ниво за функцията R.

Градиентен вектор:

перпендикулярнодо линиите на нивото, показва посоката на нарастванеР.

Проблемът за намиране на оптимално решение на системата от неравенства (5.5), за която целевата функцияР(5.7) достига максимум, геометрично се свежда до определяне в областта на възможните решения на точката, през която ще премине линията на нивото, съответстваща на най-голямата стойност на параметъраР

Ориз. шестнадесет

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

Ако екстремната стойностРсе достига в два върха, тогава същата екстремна стойност се достига във всяка точка на сегмента, свързващ тези два върха. В този случай се казва, че задачата има алтернативен оптимум .

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

Пример.

Нека се изисква да се намерят стойноститех 1 и х 2 , удовлетворяващи системата от неравенства:

и условия неотрицателност:

за коя функция:

достига максимум.

Решение.

Нека заменим всяко от неравенствата с равенство и да построим граничните линии:

Ориз. 17

Нека определим полуравнините, съответстващи на тези неравенства, като „тестваме” точката (0;0). С обмисляне неотрицателностх 1 и х 2 получаваме площта на възможните решения на този проблем под формата на изпъкнал многоъгълник OAVDE.

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

показваневъзходяща посокаР.

Оптималното решение съответства на точката AT, чиито координати могат да бъдат определени или графично, или чрез решаване на система от две уравнения, съответстващи на граничните линии AB и VD:

Отговор: х 1 = 2; x 2 \u003d 6; Rmax = 22.

Задачи. Намерете позицията на точката на екстремум и екстремалната стойност на целевата функция

при дадени ограничения.

Таблица 9

номер на опцията

екстремум
Ограничения

М брадва

; ;

; ;

Макс

; ; ;

;

; ;

; ;

; ;

; ; ;

;

; ;


Класически методи за неограничена оптимизация

Въведение

Както е известно, класическият проблем за неограничената оптимизация има формата:

Съществуват аналитични и числени методи за решаване на тези проблеми.

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

Неограничените методи за оптимизация заемат значително място в курса по МО. Това се дължи на прякото им приложение при решаване на редица оптимизационни задачи, както и при реализацията на методи за решаване на значителна част от условните оптимизационни задачи (МТ задачи).

1. Необходими условия за локална минимална (максимум) точка

Нека m доставя минималните стойности на функцията. Известно е, че в този момент приращението на функцията е неотрицателно, т.е.

Нека намерим разширенията на функцията в редицата на Тейлър в околност на m.

където, е сборът от членовете на поредицата, чийто ред е по отношение на нараствания (два) и по-високи.

От (4) ясно следва, че

Да предположим, че тогава

Като се вземе предвид (6) имаме: . (7)

Да приемем, че е положителен, т.е. . В този случай избираме продукта, който противоречи на (1).

Така че наистина е очевидно.

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

Лесно е да се докаже, че необходимите условия за локална максимална точка са точно същите като за локална минимална точка, т.е. условия (8).

Ясно е, че резултатът от доказателството ще бъде неравенство от вида: - условието за неположително нарастване на функцията в околността на локалния максимум.

Получените необходими условия не отговарят на въпроса: стационарната точка е минимална или максимална точка.

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

2. Достатъчни условия за локален минимум (максимум).

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

Разширението (1) може да бъде представено по-накратко, като се използва концепцията: „скаларен продукт на вектори“ и „векторно-матричен продукт“.

Матрица от две производни на целевата функция по отношение на съответните променливи.

Инкрементът на функцията, базиран на (1"), може да бъде записан като:

Имайки предвид необходимите условия:

Заменяме (3) във формата:

Квадратната форма се нарича диференциална квадратична форма (DQF).

Ако DCF е положително определен, тогава стационарната точка също е локална минимална точка.

Ако DCF и матрицата, която го представлява, са отрицателно определени, тогава стационарната точка също е точка на локален максимум.

По този начин необходимите и достатъчни условия за локална минимална точка са

(тези необходими условия могат да бъдат записани, както следва:

Достатъчно състояние.

Съответно необходимото и достатъчно условие за локален максимум има формата:

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

3. Критерий Силвестър

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

Нарича се матрица на Хес.

Главен детерминант на матрицата на Хес

и DCF, който представлява, ще бъде положително определен, ако всички главни детерминанти на матрицата на Hessian () са положителни (т.е. валидна е следната схема със знаци:

Ако обаче има друга знакова схема за главните детерминанти на матрицата на Хес, например, тогава матрицата и DCF са отрицателно определени.

4. Метод на Ойлер – класически метод за решаване на задачи на неограничена оптимизация

Този метод се основава на необходимите и достатъчни условия, изследвани в 1.1 - 1.3; ние прилагаме за намиране на локални екстремуми само непрекъснати диференцируеми функции.

Алгоритъмът на този метод е доста прост:

1) използвайки необходимите условия, ние формираме система в общия случай на нелинейни уравнения. Забележете, че е невъзможно тази система да се реши аналитично в общия случай; трябва да се прилагат числени методи за решаване на системи от нелинейни уравнения (НУ) (виж "FM"). Поради тази причина методът на Ойлер ще бъде аналитично-числен метод. Решавайки посочената система от уравнения, намираме координатите на неподвижната точка.;

2) разгледайте DCF и матрицата на Hessian, която го представлява. Използвайки критерия на Силвестър, определяме дали стационарната точка е точка минимална или максимална точка;

3) изчисляване на стойността на целевата функция в крайната точка

Използвайки метода на Ойлер, решете следната задача за неограничена оптимизация: намерете 4 стационарни точки на функция от вида:

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

5. Класическа задача за условна оптимизация и методи за нейното решаване: Метод на елиминиране и метод на множител на Лагранж (MLM)

Както е известно, класическият проблем за условната оптимизация има формата:

Графика, обясняваща постановката на задача (1), (2) в пространството.

Уравнения на линията на нивото

И така, ODE в разглеждания проблем е определена крива, представена от уравнение (2").

Както се вижда от фигурата, точката е точката на безусловния глобален максимум; точка - точка на условен (относителен) локален минимум; точка - точка на условен (относителен) локален максимум.

Задача (1"), (2") може да се реши чрез метода на елиминиране (заместване), решаване на уравнение (2") по отношение на променливата и заместване на намереното решение (1").

Първоначалният проблем (1"), (2") по този начин се трансформира в задача за оптимизация на неограничена функция, която лесно се решава чрез метода на Ойлер.

Метод на изключване (заместване).

Нека целевата функция зависи от променливите:

се наричат ​​зависими променливи (или променливи на състоянието); съответно можем да въведем вектора

Останалите променливи се наричат ​​независими променливи за решение.

Съответно можем да говорим за вектор колона:

и вектор.

В класически условен оптимизационен проблем:

Система (2), в съответствие с метода на елиминиране (заместване), трябва да бъде разрешена по отношение на зависими променливи (променливи на състоянието), т.е. трябва да се получат следните изрази за зависими променливи:

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

не е равно на нула (вижте съответната теорема в магистърския курс)

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

Заместваме от (3) в целевата функция (1), имаме:

Изследваната функция може да бъде доведена до екстремум чрез метода на Ойлер - метода за безусловна оптимизация на непрекъснато диференцируема функция.

И така, методът на елиминиране (заместване) ви позволява да използвате проблема за класическата условна оптимизация, за да се трансформира в проблем за безусловна оптимизация на функция - функция на променливи при условие (4), което ви позволява да получите система от изрази (3).

Недостатък на метода на елиминиране: трудности, а понякога и невъзможност за получаване на система от изрази (3). Свободен от този недостатък, но изискващ изпълнение на условие (4) е MML.

5.2. Метод на множителите на Лагранж. Необходими условия в класическата условна оптимизационна задача. Функция на Лагранж

MML позволява оригиналния класически условен оптимизационен проблем:

Трансформирайте в проблем за безусловна оптимизация на специално проектирана функция - функцията на Лагранж:

където, - множители на Лагранж;

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

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

Използване на концепцията за зависими и независими променливи - зависими променливи; са независими променливи, тогава представяме (5) в разширен вид:

От (2) е очевидно, че следва система от уравнения от вида:

Резултатът от изчисляването на общия диференциал за всяка от функциите

Нека представим (6) в "разширена" форма, използвайки концепцията за зависими и независими променливи:

Имайте предвид, че (6"), за разлика от (5"), е система, състояща се от уравнения.

Умножаваме всяко -то уравнение на системата (6") по съответния -ти множител на Лагранж. Събираме ги заедно и с уравнение (5") и получаваме израза:

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

Терминът "разпореждам" на множителите на Лагранж по горния начин означава, че е необходимо да се реши някаква система от уравнения по отношение на.

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

Нека препишем (8) във формата

Система (8") е система от линейни уравнения по отношение на известните: . Системата е разрешима, ако (затова, както при метода на елиминиране, условието трябва да бъде изпълнено в разглеждания случай). (9)

Тъй като първата сума в ключовия израз (7) е равна на нула, лесно е да се разбере, че втората сума също ще бъде равна на нула, т.е. се изпълнява следната система от уравнения:

Системата от уравнения (8) се състои от уравнения, а системата от уравнения (10) се състои от уравнения; общи уравнения в две системи и неизвестни

Липсващите уравнения са дадени от системата от ограничителни уравнения (2):

И така, има система от уравнения за намиране на неизвестни:

Полученият резултат - системата от уравнения (11) е основното съдържание на MML.

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

Наистина ли

Така че системата от уравнения (11) може да бъде представена като (с помощта на (12), (13)):

Системата от уравнения (14) представлява необходимо условие в класическата условна оптимизационна задача.

Стойността на вектора, намерен в резултат на решението на тази система, се нарича условно неподвижна точка.

За да се установи естеството на условно неподвижна точка, е необходимо да се използват достатъчни условия.

5.3 Достатъчни условия в класическата условна оптимизационна задача. MML алгоритъм

Тези условия позволяват да се установи дали една условно неподвижна точка е точка на локален условен минимум или точка на локален условен максимум.

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

Резултатът от това проучване:

където е локалната условна минимална точка.

където е точката на локалния условен максимум, е хесовата матрица с елементи

Хесовата матрица има измерение.

Размерността на хесианската матрица може да бъде намалена, като се използва условието, че якобианът не е равен на нула: . При това условие е възможно да се изразят зависими променливи чрез независими променливи, тогава матрицата на Хес ще има измерение, т.е. трябва да се говори за матрица с елементи

тогава достатъчните условия ще бъдат:

Точка на местния условен минимум.

Точка на локален условен максимум.

Доказателство: MML алгоритъм:

1) съставете функцията на Лагранж: ;

2) използвайки необходимите условия, ние формираме система от уравнения:

3) намираме точка от решението на тази система;

4) използвайки достатъчни условия, определяме дали точката е точка на локален условен минимум или максимум, след което намираме

1.5.4. Графоаналитичен метод за решаване на класическата задача за условна оптимизация в пространството и нейната модификация при решаване на най-простите задачи на IP и AP

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

B е обща допирателна за функцията и функцията, представляваща ODR.

Както се вижда от фигурата, точката е точката на безусловния минимум, точката е точката на условния локален минимум, точката е точката на условния локален максимум.

Нека докажем, че в точките на условни локални екстремуми кривата и съответните линии на ниво

От курса на МА е известно, че условието е изпълнено в точката на контакт

където е наклонът на допирателната, начертан от съответната линия на нивото; - наклон на допирателната, начертана към функцията

Изразът (MA) за тези коефициенти е известен:

Нека докажем, че тези коефициенти са равни.

защото необходимите условия „казат” за това

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

1) изграждаме семейство от линии на ниво целева функция:

2) ние изграждаме ODS, използвайки уравнението за ограничаване

3) за да коригираме увеличението на функцията, намираме и изясняваме естеството на крайните точки;

4) изучаваме взаимодействието на нивата и функциите, като намираме от системата от уравнения координатите на условно стационарни точки - локални условни минимуми и локални условни максимуми.

5) изчисли

Специално трябва да се отбележи, че основните етапи на метода HFA за решаване на класическата задача за условна оптимизация съвпадат с основните етапи на метода HFA за решаване на LP и LP проблеми, разликата е само в ODT, както и в намиране на местоположението на екстремни точки в ODT (например, в LP задачи, тези точки задължително се намират във върховете на изпъкнал многоъгълник, представляващ ODT).

5.5. Относно практическото значение на MML

Представяме класическия проблем за условна оптимизация във формата:

където са променливите, представляващи променливи ресурси в приложените технически и икономически проблеми.

В пространството проблемът (1), (2) приема формата:

където е променлива. (2")

Нека е условна точка на екстремум:

Промени при смяна

Стойността на целевата функция ще се промени съответно:

Нека изчислим производната:

От (3), (4), (5). (6)

Заместете (5") в (3) и получете:

От (6), че множителят на Лагранж характеризира "реакцията" на стойността (ортогонална на стойността на целевата функция) на промени в параметъра.

В общия случай (6) приема формата:

От (6), (7), който е множител, характеризира промяната, когато съответният -ти ресурс се промени с 1.

Ако - максималната печалба или минималната цена, тогава характеризира промените в тази стойност при промяна с 1.

5.6. Класическият проблем за условна оптимизация, като проблемът за намиране на седалната точка на функцията на Лагранж:

Една двойка се нарича седловина, ако неравенството е изпълнено.

Очевидно от (1). (2)

От (2) това. (3)

Както можете да видите, системата (3) съдържа уравнения, подобни на тези уравнения, които представляват необходимо условие в класическата задача за условна оптимизация:

където е функцията на Лагранж.

Във връзка с аналогията на системите от уравнения (3) и (4), класическата задача за условна оптимизация може да се разглежда като задача за намиране на седловината на функцията на Лагранж.

Подобни документи

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

    тест, добавен на 26.11.2011

    Характеризиране на класическите методи за неограничена оптимизация. Определяне на необходимите и достатъчни условия за съществуване на екстремум от функции на една и няколко променливи. Правило за множител на Лагранж. Необходими и достатъчни условия за оптималност.

    курсова работа, добавена на 13.10.2013

    Методи и характеристики за решаване на оптимизационни проблеми, по-специално разпределение на инвестициите и избор на път в транспортната мрежа. Специфика на моделирането по методите на Хаминг и Браун. Идентифицирането, стимулирането и мотивацията като управленски функции.

    контролна работа, добавена на 12.12.2009г

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

    наръчник за обучение, добавен на 07/11/2010

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

    курсова работа, добавена на 21.06.2014

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

    тест, добавен на 15.10.2010 г

    Оптимизиращи методи за решаване на икономически проблеми. Класическа постановка на оптимизационния проблем. Оптимизация на функциите. Функционална оптимизация. Многокритериална оптимизация. Методи за свеждане на многокритериален проблем до еднокритериален. метод на концесия.

    резюме, добавен на 20.06.2005

    Прилагане на методи за нелинейно програмиране за решаване на задачи с нелинейни функции на променливи. Условия за оптималност (теорема на Кун-Тъкър). Методи за условна оптимизация (метод на Wulff); градиентен дизайн; наказателни и бариерни функции.

    резюме, добавен на 25.10.2009

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

    курсова работа, добавена на 21.01.2012 г

    Основни понятия за моделиране. Общи понятия и определение на модела. Постановка на оптимизационните проблеми. Методи за линейно програмиране. Общ и типичен проблем в линейното програмиране. Симплексен метод за решаване на задачи за линейно програмиране.

Задача 1.Да намеря

Задача 1 се свежда до решаване на системата от уравнения:

и изследване на стойността на втория диференциал:

в точките на решение на уравнения (8.3).

Ако квадратичната форма (8.4) е отрицателно определена в дадена точка, тогава тя достига максималната си стойност там, а ако е положително определена, тогава нейната минимална стойност.

пример:

Системата от уравнения има решения:

Точката (-1/3.0) е максималната точка, а точката (1/3.2) е минималната точка.

Задача 2.Да намеря

при условия:

Задача 2 се решава по метода на множителя на Лагранж. За да направим това, намираме решение на системата (t + p)уравнения:

Пример.Намерете страните на правоъгълник с максимална площ, вписан в кръг: . Площта A на правоъгълник може да се запише като: A = 4xyтогава

Задача 3.Да намеря:

при условия:

Тази задача обхваща широк спектър от задачи, дефинирани от функции еи .

Ако те са линейни, тогава проблемът е проблем с линейното програмиране.

Задача3 а.

при условия

Решава се по симплексния метод, който с помощта на апарата на линейната алгебра извършва целенасочено изброяване на върховете на полиедъра, дефиниран от (8.13).

Симплексен метод (състои се от два етапа):

Етап 1. Намиране на еталонното решение x (0) .

Опорното решение е една от точките на полиедъра (8.13).

Етап 2. Намиране на оптималното решение.

Оптималното решение се намира чрез последователно изброяване на върховете на полиедъра (8.13), при което стойността на целевата функция z не намалява на всяка стъпка, т.е.

Специален случай на проблем за линейно програмиране е така нареченият транспортен проблем.

транспортна задача. Нека точките съдържат складове, в които стоките се съхраняват в количества, респ. В точките са потребители, които трябва да доставят тези стоки в количества, респ. Означете ° С ij разходите за транспортиране на единица товар между точките

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

За да се задоволят нуждите на консуматора, е необходимо стойностите х ij отговаря на условията:

В същото време от склад а; не можете да вадите продукти в по-големи количества от наличните. Това означава, че търсените стойности трябва да отговарят на системата от неравенства:

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

Проблемът с критерия се решава независимо от изследването на операцията - критерият трябва да бъде зададен от оперативната страна. В този проблем един от възможните критерии ще бъде цената на транспорта. Дефинира се както следва:

Тогава транспортната задача се формулира като задача за линейно програмиране: определят се количествата, които удовлетворяват ограниченията (8.14), (8.15) и дават на функцията (8.16) минималната стойност. Ограничението (8.15) е условие за баланс; условие (8.14) може да се нарече цел на операцията, тъй като смисълът на операцията е да задоволи нуждите на потребителите.

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

Един от добре познатите методи за решаване на транспортния проблем е методът на потенциалите.

На първия етап от решаването на проблема се съставя първоначален транспортен план, който удовлетворява

ограничения (8.14), (8.15). Ако (т.е. общите изисквания не съвпадат с общите наличности на продукти в складовете), тогава се въвежда фиктивна точка на потребление или фиктивен склад с транспортна цена, равна на нула. За новата задача общото количество стоки в складовете съвпада с общото им търсене. След това по някакъв метод (например най-малкият елемент или северозападният ъгъл) се намира оригиналният план. На следващата стъпка от процедурата на получения план се изгражда система от специални характеристики - потенциали. Необходимо и достатъчно условие за оптимален план е неговата потенциалност. Процедурата за усъвършенстване на плана се извършва, докато стане потенциален (оптимален).

Задача 3б.В общия случай задачата (8.10 - 8.11) се нарича проблем за нелинейно програмиране. Разгледайте го в по-приета форма:

при условия

За решаването на този проблем се използват така наречените методи за релаксация. Процесът на конструиране на последователност от точки се нарича релаксационен, ако:

Методи за спускане (обща схема). Всички методи за спускане за решаване на задачата за неограничена оптимизация (8.17) се различават или по избора на посоката на спускане, или по начина на движение по посоката на спускане. Методите за спускане се състоят от следната процедура за изграждане на последователност { х к }.

За начално приближение се избира произволна точка х 0 . Последователните приближения се изграждат по следната схема:

Точка х к посоката на спускане е избрана - с к ;

Намерете (k + 1) -то приближение по формулата:

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

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

В повечето методи за спускане стойността на  to се избира равна на единица. По този начин, за да се определи  k, трябва да се реши задачата за едномерното минимизиране.

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

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

Схема на метода:

Ако = 0, тогава тази схема се превръща в схемата на метода за най-стръмно спускане. Подходящ избор на количество т к гарантира сближаването на метода на конюгираните посоки със скорост от същия порядък, както при методите за градиентно спускане и гарантира, че броят на итерациите в квадратичното спускане е краен (например ).

Координатно спускане.При всяка итерация като посока на спускане − с k се избира посоката по една от координатните оси. Методът има степен на сближаване на процеса на минимизиране от порядък 0(1/m). Освен това по същество зависи от размерите на пространството.

Схема на метода:

където е координатният вектор

Ако в точката х к има информация за поведението на градиента на функцията е(х), Например:

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

В началния етап на процеса на минимизиране може да се използва методът на цикличното координатно спускане, когато спускането се извършва първо в посоката д 1 , след това на e 2 и т.н. до д П , след което целият цикъл се повтаря отново. По-обещаващо от предишното е координатното спускане, при което посоките на спускане се избират на случаен принцип. При този подход към избора на посока има априорни оценки, които гарантират функцията е(х) с с вероятност, клоняща към единица като , конвергенцията на процеса със скорост от порядъка на 0(1/m).

Схема на метода:

На всяка стъпка от процеса произволно се избира число от n числа (1, 2, ..., n) j(к) и като с k е избран единичният координатен вектор д j ( к ) , след което се извършва спускането:

Метод на произволно спускане.с к, което се подчинява на равномерно разпределение върху тази сфера, а след това според елемента, изчислен на k-тата стъпка от процеса х да се дефиниран:

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

Релаксационни методи на математическото програмиране.Да се ​​върнем на задача 36 ((8.17) – (8.18)):

при условия

При оптимизационни проблеми с ограничения изборът на посоката на спускане е свързан с необходимостта постоянно да се проверява дали новата стойност х к +1 трябва да е същото като преди х к отговарят на система от ограничения х.

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

По този начин, за да се намери посоката - s k, трябва да се реши задачата за минимизиране на линейна функция върху множеството х. Ако х от своя страна се задава от линейни ограничения, тогава се превръща в проблем за линейно програмиране.

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

Посока - с в точката хх се нарича възможно, ако съществува число такова, че за всички. За да се намери възможна посока, е необходимо да се реши задача за линейно програмиране или най-простата задача за квадратично програмиране:

При условия:

Нека бъде решението на този проблем. Условието (8.25) гарантира, че посоката е възможна. Условието (8.26) осигурява максимална стойност (т.е. сред всички възможни посоки - с, посока - осигурява най-бързото намаляване на функцията е(х). Условието (8.27) елиминира неограничеността на решението на задачата. Методът на възможните посоки е устойчив на възможни изчислителни грешки. Въпреки това е трудно да се оцени скоростта на нейната конвергенция в общия случай и този проблем все още остава нерешен.

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

Схема на метода:

Върху n-мерната единична сфера, центрирана в началото, се избира произволна точка r к, което се подчинява на равномерно разпределение върху тази сфера, а след това посоката на спускане е с к от условията

се избира като начално приближение. Според точката, изчислена при всяка итерация х к се строи ( к+ 1)та точка х к +1 :

Всяко число от =, което удовлетворява неравенството, се избира като:

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