Разлика между версии на „Оптимизация“

Текуща версия към 18:46, 29 март 2014

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

Същност

Оптимизация е термин, свързан с подобряването на изпълнението, който най-често намира приложение в сферата на: математиката - намиране на максимум или минимум на дадена функция за решаване на проблеми; компютърните науки- подобряване на една система, така че да се намали натоварването ѝ, пропускателната способност, изискванията по отношение на паметта или друга характеристика; програмирането - подобряване на системата за намаляване на времето за изпълнение, трафик, изисквания за памет или друго имущество на системата, наречено Оптимизация за търсещи сайтове (SEO - Search Engine Optimization)

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

Избор т.е. реалните възможности за постигане на главната цел;
За постигане на целта при удоволетворяване на ограниченията.

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

Вижте още

Източници

Юрий Данаилович Зубенко, А. А. Ильин, Оптимизация решений производственных задач: На примере АСУ
Златка Иванова, Красимира П. Стоилова, Тодор А. Стоилов, Портфейлна оптимизация - информационна услуга в Интернет
Семен Ефимович Ильюшонок ; Отг. ред. А. И. Тянутов, Оптимизация темпов и пропорций развития аграрно-промышленного комплекса
Прев. от англ. Ю. Н. и др. Печерский, Оптимизация и обработка данных:Математические исследования
Прев. от англ. В. Л. Марков, Оптимизация планов производства
Андрей Станиславович Плещинский, Оптимизация межфирменных взаимодействий и внутрифирменных управленческих решений
Станислав С. Скрипниченко, Оптимизация режимов полета по экономическим критериям
Стоян К. Стоянов, Методи и алгоритми за оптимизация

Външни препратки

Разлика между версии на „Оптимизация“

Текуща версия към 18:46, 29 март 2014

Съдържание

Същност

Вижте още

Източници

Външни препратки

Навигация

Търсене

@@ Ред 1: / Ред 1: @@
-'''Оптимизацията''' е '''целенасочена [[дейност]] за намиране на [[алтернатива]],  която да е с най-голям ефект или с най-голяма възможна производителност, осъществена при дадени ограничения чрез увеличаване на желан фактор или намаляване на нежелан такъв'''. Оптимизация е термин, свързан с подобряването на изпълнението, който най-често намира приложение в сферата на :  математиката - намиране на максимум или минимум на дадена функция за решаване на проблеми; компютърните науки-  подобряване на една система, така че да се намали натоварването ѝ, пропускателната способност, изискванията по отношение на паметта или друга характеристика; програмирането - подобряване на системата за намаляване на времето за изпълнение, трафик, изисквания за памет или друго имущество на системата, наречено [[СЕО]] (SEO - Search Engine Optimization)
+'''Оптимизацията''' е '''целенасочена дейност за намиране на [[алтернатива]],  която да е с най-голям ефект или с най-голяма възможна производителност, осъществена при дадени ограничения чрез увеличаване на желан фактор или намаляване на нежелан такъв'''.
+==Същност==
+Оптимизация е термин, свързан с подобряването на изпълнението, който най-често намира приложение в сферата на:  математиката - намиране на максимум или минимум на дадена функция за решаване на проблеми; компютърните науки-  подобряване на една система, така че да се намали натоварването ѝ, пропускателната способност, изискванията по отношение на паметта или друга характеристика; програмирането - подобряване на системата за намаляване на времето за изпълнение, трафик, изисквания за памет или друго имущество на системата, наречено [[Оптимизация за търсещи сайтове]] (SEO - Search Engine Optimization)
 Обект на може да бъде както производствен процес или част от него, намирайки се в стадий на или , така  и човешката дейност, разглеждана в определен период от време. За осъщесвяване на ефективна оптимизация трябва да се спазят следните :
-# Избор т.е. реалните възможности за постигане на главната цел;
+* Избор т.е. реалните възможности за постигане на главната цел;
-# За постигане на целта при удоволетворяване на ограниченията.
+* За постигане на целта при удоволетворяване на ограниченията.
 За намирането на се използват които могат да бъдат наречени още и екстремни задачи. За решаването на този тип задачи се използват точно определени , които се наричат оптимизационни методи . Различните методи за оптимизация са ориентирани към решаване на определени класове от задачи, сложността на които се определя от  размите на параметрите, структурата на ограниченията и свойствата на целевата функция.
-==Локална оптимизация==
-===Оптимизационен модел===
-В най-общ смисъл изследователските модели се делят на две групи – експериментални (натурни) и теоритични (умозрителни). Теоритичните модели са изестни и като математичен. Математичният модел на конкретен обект е неговото описание със средствата на математиката и използване на закономерностите от една или няколко науки в съответствие с избрания аспект на разглеждане. Възможно е моделът да бъде коригиран и допълван до тогава, докато получените чрез него резултати съответстват в желана степен на реалния обект. Теоритичните модели се делят на два вида – детерминирани (класически) и стахостически ( експериментално - статистически).
-===Едномерна оптимизация===
-Оптимизационните задачи, при които трябва да се определи минимума на целевата функция, която зависи само от една променлива, се наричат едномерни. Това са най-простият тип оптимизационни задачи, но в практиката те се срещат много рядко.
-Едномерните методи от своя страна се делят на преки и непреки такива.
-Особеност на преките методи е това, че при тях се взима само стойностите на целевата функция намиращи се в интервала [a,b], без да се взимат нейните производни.
-Към преките едномерни методи за оптимизация спадат следните методи:
-# Сканиране с постоянна стъпка-при този метод интервалът се разделя на равни части, а постоянната стъпка е δ = (b-a)/n;
-# Метод на дихотомията - последователно търсене, при което при всяко повторение на процеса областта на търсене се намалява два пъти;
-# Метод на “златното сечение”-минимумът на целевата функция може да се намери с по-малко изчисления, ако интервалъ [a,b] е разделен на части, които спазват правилото за „златното сечение”, (отношението на първата част на дадена отсечка към втората част, трябва да е както отношението на цялата отсечка към първата част )
-# Полиномна апроксимация- изпозлва се, когато целевата функция може да се прогнозира достатъчно точно чрез [[полином]], в близост до [[минимум]]а.
-Непреките едномерни методи се използват, когато целевата функция е неопределена или два пъти диференцируема, при намирането на минимума й и се използват нейните производни. Непреките методи включват:
-# Метод на средната точка - използва се връзката между знака на първата производна на целевата функция и характера на изменението на самата функция;
-# Метод на [[Нютон]] - изпозва се за намирането на корените на реални функции;
-# Метод на [[кубична апроксимация|кубичната апроксимация]] - за определянето на апроксимиращия полином се изпозлват както стойностите на целевата функция, така и на нейните производни
-Намирането на локален минимум на функция на една променлива в зададен интервал с помощта на ''Matlab ''се извършва с програмата ''fmin''. [[Алгоритъм]]ът, използван в тази програма, съчетава методите на златното сечение и на квадратичната интерполация. Целевата функция трябва да бъде непрекъсната.
-Повикващият израз на програмата е
-[x,opt]=fmin(‘fun’,x1,x2,options,p1,p2,…)
-===Многомерна оптимизация===
-(''x k ''= ''x k-1 ''+ ''skd k'', ''k ''= 1, 2, … ,)
-Многомерната оптимизация представлява задача, за минимизация на целевата функция, зависеща от много променливи. Към големият брой управляващи параметри и сложността на целевата функция, се добавяр многобройни ограничения.
-Методите за многомерна оптимизация се делят на преки и непреки.
-Голяма част от преките безусловни методи не се обосновават на теоритична обосновка, а на евристични съображения. Този вид методи използват информация само за целевата функция, стойностите на която се изчисляват в следствие на ясно дефинирана стратегия. Методите, които спадат към групата на преките безусловни такива са:
-* Метод на покоординатното спускане - последователна едномерна минимизация на целевата функция по всяка от координатите на n- мерното пространство
-* Методи на случайното търсене - това е голяма група от методи, в която стойностите на целевата функция се изчисляват в точки, генерирани по някакъв случаен закон
-* Симплекс метод - едновременно изследва и премества към минимума чрез точки, които образуват симплекс в управляващо параметрите пространство Непреките безусловни методи се отличават от преките по това, че при тях освен стойностите на целевата функция се използват и нейните първа и втора производни. Съществуват четири метода, които спадат към тази група:
-* Метод на най-стръмното спускане - при този метод се изчислява антиградиентът на целевата функция в една точка, което превръша задачата в едномерна минимизационна такава, а посоката на търсене се задава от антиградиентът (нейното най-голямо намаляване)
-* Метод на спрегнатите градиенти - стъпката от всяко повторение не е в посоката на антиградиентите, а се изчислява от антиградиентите от предходното и текущо повторение
-* Метод на Нютон - намирането на минимума на целева функция с непрекъснати първа и втора производни, чрез използването на градиент ∇f (x) и Хесиан H(x).
-* Квазинютонови методи- група методи, съчетаващи предимствата на [[метод]]а на най-стръмното спускане и метода на Нютон
-==Глобална оптимизация==
-Определянето на най-малката (или най-голямата) стойност на многоекстремална  функция се осъществява със специализирани методи за глобална(многоекстремална) оптимизация. Несъществуването на универсален ефективен метод за решаване на задачите за глобална оптимизация е причина за създаването на множество методи, ориентирани към определени [[тип]]ове задачи. Като правило никой метод не може да гарантира успешно решаване на многоесктремани задачи със сложна [[структура]]. Глобалната оптимизация също както и локалната се дели едномерна и многомерна.
-===Методи за едномерна глобална оптимизация===
-Характерна особеност на ефективните методи за [[глобална оптимизация]] е, че в околностите на глобалния минимум и на локалните минимуми с близки стойности до търсения оптимум, плътността на точките от минимизиращите редици {''x k''} и {''y k''} е по-висока.
-* Обобщен алгоритъм
-* Метод на случайното търсене
-* Метод на глобалното търсене
-===Методи за многомерна глобална оптимизация===
-* Методи на случайното търсене- различава се от другите методи с това, че при него се въвежда [[елемент]] на случайност в [[процедура]]та на търсене;
-* [[Метод Монте Карло]] -  основава се на предположението, че локалните екстремуми на целевата функция са разпределени равномерно в допустимото пространство П. Чрез този метод се осъществява сондиране и изследване на цялото допустимо множество;
-* Метод на детерминираното сондиране
-===Многокритериална оптимизация===
-По - голямата част от съвременните изследователски и приложни оптимизациони задачи са многокритериални и принципно конфликтни. Изборът на система от критерии за оценка и ранжирането им по степен на важност няма еднозначно тълкуване и поражда субективни решения. Друга важна особеност на многокритериалните задачи е, че те нямат само едно единствено решение. Обикновено резултатът от решаването им е множество от т. нар. Парето- оптимални решения, получени в следствие на предложения от Вилфред Парето принцип за съгласувана оптималност. Тъй като никое от получените Парето-оптимални решения не е по-добро от другото е необходимо да се намери еднозначно решение, за което е нужна допълнителна информация и нечие субективно виждане за компромис.
-Две са главните цели при многокритериалната оптимизация:
-*да се намерят решения, близки до действителните Парето-оптимални решения;
-*определените решения да се различават съществено едно от друго.
-Постигането на първата цел означава, че се удовлетворяват условията за съгласувана оптималност, а на втората – че няма смесване на различните критерии.
-===Методи за многокритериална оптимизация===
-Най-общо съществуващите методи за многокритериална оптимизация могат да бъдат разделени на две групи:
-* Методи, основани на оптимизирането на обобщен критерий, определен в рамките на предварително избрана компромисна стратегия
-* Методи, основани на определянето на приблизително Парето-оптимално множество Тегловен метод
-Методът, предложен от ''L. Zadeh'' през 1963 година, реализира линейна компромисна схема . Многокритериалната задача се трансформира в еднокритериална с помощта на линейна комбинация от отделните критерии с предварително избрани коефициенти w (тегловни коефициенти):
-minx∈X F(x),
-* Метод на ε-ограниченията
-Това е процедура предложена от Haimes'', Lasdon, Wismer'' през 1971 година с цел да преодолява недостатъците на тегловните методи, които се дължат на неизпъкналост на Парето-множеството. При тази компромисна схема един от критериите се избира за основен и се минимизира, а останалите критерии се приемат за ограничения от вида
-<center>fν (x) ≤ εν , ν = 1, 2, ..., r, ν ≠ μ.</center>
-<center></center>
-Методът позволява да бъдат определени [[Вилфредо Парето|Парето]] - оптимални решения и по неизпъкнал участък от границата
-* Метод на достигане на [[цел]]та
-Този метод включва задаване на цел z° = [z1°, …, zr°]T, която съответства на критерия f(x) = [f1(x), …, fr(x)]T. Доближаването  до целта да бъде двупосочно – отдолу или отгоре. Процесът се управлява от тегловен вектор w = [w1,w2, …, wr]T.
-Тегловният вектор w позволява въвеждането на мярка за относителния компромис между целите. Задачата за векторна оптимизация се преобразува в еднокритериална задача от вида
-<center>minγ, ''x''∈''D ''γ,</center>
-* Минимаксен метод
-За да се избегнат случаи с недопустимо лоши стойности на някои критерии е препоръчително в структурата на задачата за векторна оптимизация да се въведат и критериални ограничения
-* Метод на глобалния критерий
-При метода на глобалния критерий се минимизира разстоянието между някаква зададена точка в критериалното пространство и точките от достижимото множество. Обикновено за точка ''z''осе избира утопичната точка ''U''. Ако всички критерии са еднакво важни, тегловните коефициенти се приемат еднакви ''w''v= 1.
-* Метод с нелинейна компромисна схема
-Компромисната схема, предложена от [[А. Н. Воронин]] през 1984 година, свежда задача за векторна оптимизация до еднокритериална задача
-Обобщеният [[критерий на Воронин]]
-<center>F(x) = Σ rv=1  (1 /ρν)</center>
-<center></center>
-има адаптивни свойства при различна “напрегнатост” на компромисните ситуации в зависимост от стойностите на събираемите 1/ρν . Когато стойността на някой от частните критерии започне да се доближава до своята граница (напрегнат компромисен режим), критерият F рязко нараства и минимизирането на цялата сума се свежда до минимизиране на най-лошото събираемо.  Ако частните критерии са далече от пределно допустимите им стойности (спокоен компромисен режим) схемата реализира принципа на интегрална оптималност.
-* PSI-метод
-PSI-методът (съкратено от ''Parametric Space Investigation'') е в основата на универсална изчислителна технология за решаване на приложни многокритериални задачи, които намират приложение в оптималното проектиране на технически обекти и процеси.
-За прилагането на  PSI-метода е необходимо наличието на математичен модел симулатор на оптимизируемия обект, в който освен обичайните за нелинейното оптимиране ограничения могат да се въвеждат и вариращи ограничения върху изменението на критериите. Решената по този начин оптимизационна задача изисква формирането на допустимото параметрично множество да става в процеса на решаване на оптимизационната задача.
-Програмно реализирания PSI-метод предлага :
-*информация за интервалите на изменение на отделните критерии;
-*вариране на управляващите параметри в зависимост от наложените ограничения;
-*възможност за обоснован избор на областни и критериални ограничения;
-*възможност за интерпретиране на ограниченията като псевдокритерии;
-*диалогов режим на вземане на решения от излъчено приблизително
-Парето-оптимално множество;
-*възможност за открояване на зависими критерии;
-*таблично оформяне и лесно сортиране на резултатите по различни признаци.
-==Оптимизационни задачи==
-===Необходими предпоставки за оптимизационните задачи===
-# Обект за оптимизация
-# Критерий за оптималност - Числен показател, по който се оценява [[ефективност]]та от функционирането на обекта за оптимизация
-# Управляемост на обекта'' -  ''Наличие на управляващи параметри (температура, [[налягане]], [[концентрация]]), които се изменят независимо един от друг,   вследствие на което се получават множество варианти на състоянието на [[обект]]а, от които се избира най-добрият.
-# Метод за оптимизация -  Методът за оптимизация е най-важната предпоставка за решение на оптимизационните задачи, тъй като той осъществява процеса на търсене на най-добрия резултат, независимо от характера на обекта за оптимизация.
-В най-общ вид една оптимизационна [[задача]] се дефинира по следния начин. Търси се максимум на целевата функция maxQ(x) = maxQ(x1, x2,…,xn) в пространството определено от управляващите параметри x ∈ Гx и наложените ограничения от други функции:
-φ i (x1, x2,…,xn) = φ 0il , i = 1,2,…,ml &lt; n
-ψ j (x1, x2, …,xn) ≥ ψ 0j , j = 1,2,…,m2
-Целта на задачата за оптимизация е да се намерят такива [[стойност]]и на управляващите параметри  x* ''= ''(''x1*, x2*,…, xn*'')'', ''за които се изпълнява условието:
-<center>Q(x*) = Q(''x1*, x2*,…, xn''*) = Qmax &gt; Q(''x1, x2,…, xn'')</center>
-при спазване на ограниченията
-x* ∈ Гx
-φ ''i ''(''x1*, x2*,…,xn''*) =  0''i '', ''i ''= 1,2,…,''m''l &lt; ''n''
-ψ ''j ''(''x1*, x2*, …,xn''*) = 0''j '', ''j ''= 1,2,…,''m''2 ,
-т.е. x* ∈Г''x, φ, ψ''
-Множеството от точки, които удовлетворяват наложените ограничения, се нарича множество на допустимите решения за целевата функция Q(x) или за
-краткост [[допустима област]] -  x* ∈ Г''x, φ, ψ''
-===Видове   оптимизационни  задачи===
-Поради голямото разнообразие от обекти, с които са свързани оптимизационните задачи, последните могат да се класифицират по много признаци. Някои от тях са:
-*Според характера на решавания проблем:
-:*задача за структурна оптимизация на разглеждания обект – се иска да се проектира съд с минимална повърхнина при зададен обем и няколко за дадени възможни геометрични форми.
-:*задача за параметрична оптимизация – Търсят се параметрите на обекта така, че критерият да получи оптимална стойност
-*Според типа на математичния модел:
-:*статична оптимизационна задача – възниква, когато обектът се разглежда в стационарно (равновесно) състояние. Изменението  на управляващите параметри води до мигновена промяна в стойността на критерия. Ограниченията в нея се описват с алгебрични уравнения и неравенства. Целевата функция е възможно да се формира като интегрална оценка или въз основа на избрана стойност на някоя характеристика на обекта.
-:*динамична оптимизационна задача – възниква, когато състоянието на обектa, който се оптимизира, се моделира с помощта на диференциални уравнения, (освен пространствено се изменя и времево).  Обектът, подлежащ на оптимизация, притежава способността да натрупва енергия или вещество, в резултат на което той не реагира мигновено на изменението на управляващите параметри. В тези случаи диференциалните уравнения представляват ограничения от тип равенство, а целевата функция обикновено е интегрална оценка.
-*Според броя на управляващите параметри:
-:*едномерна (еднопараметрична) оптимизационна задача – тя има само един управляващ параметър, т.е. x∈Ε 1.
-:*многомерна (многопараметрична) оптимизационна задача – броят на управляващите параметри е ξ &gt;1, т.е. x∈Ε ξ.
-*Според характера на зависимостта на критерия или/и на ограниченията от параметрите:
-:*нелинейни оптимизационни задачи – целевата функция или поне едно от наложените функционални ограничения е нелинейна функция на управляващите параметри.
-:*линейни оптимизационни задачи – критерият и всички ограничения в задачата са линейни функции на управляващите параметри.
-:*квадратични оптимизационни задачи – критерият е квадратична функция на управляващите параметри, а ограниченията са линейни.
-*Според наличието на ограничения:
-:*задача за условна оптимизация. Тази задача съдържа освен интервални и други
-ограничения.
-:*задача за безусловна оптимизация. Тази задача не съдържа никакви ограничения или съдържа само интервални ограничения. От гледна точка на математиката задачата за безусловна оптимизация без интервални ограничения се характеризира с неограничено изме нение на управляващите параметри, т.е. u − → −∞ и u + → +∞. В практическите задачи обаче, винаги се задават някакви интервални ограничения.
-Задачите за условна оптимизация е възможно да се преобразуват в задачи за безусловна оптимизация. Това става чрез подхода на “наказателните” функции. Той се състои в изграждане на обобщена целева функция, която съдържа както целевата функция, така и всички ограничения.
-Честа практика е пренебрегването на някои ограничения с цел оптимизиране на задачата.За да има решение една оптимизационна задача трябва всички ограничения да са съвместими, т.е. да съществува непусто допустимо параметрично множество Du и целевата функция да е дефинирана в него.
-*Според вида на търсения минимум:
-:*задача за локална оптимизация – свързана е с определяне на локален минимум на целевата функция.
-:*задача за глобална оптимизация – изисква се определяне на глобален минимум на целевата функция.
-*Според броя на критериите:
-:*еднокритериална задача – притежава само един критерий, подлежащ на оптимизиране.
-:*многокритериална задача – съдържа няколко критерия.
-===Графично онагледяване на оптимизационни задачи===
-Онагледяването на една оптимизационна задача (когато това е възможно) изисква изображението на нейната целева функция да се допълни с графично представяне на наложените ограничения.
-==Избор на алгоритъм за нелинейна оптимизация ==
-Избор на алгоритъм за оптимизация
-#Задачи за едномерно търсене (n = 1);
-#Задачи за многомерно търсене (с малка n = 4 ÷ 5, средна 5&lt;n&lt;20 и голяма размерност n &gt; 20);
-#Задачи с пълна и непълна информация за параметрите в математичния модел;
-#Задачи в барицентрично, Декартово или смесено пространство на управляващите параметри;
-#Задачи с непрекъснати, дискретни и смесени управляващи параметри;
-#Задачи със зададена или незададена начална точка при търсене на оптимума;
-#Задачи със зададена абсолютна или относителна точност на локализация на екстремума по всеки управляващ параметър.
-В зависимост от целевата функция
-#Методи за едноцелева оптимизация;
-#Методи за многоцелева оптимизация;
-#Със зададени и незададени производни на целевата функция;
-#Зададена или незададена точност на локализация на екстремума по целева функция;
-#Оптимизация при едноекстремални или многоекстремални целеви функции;
-#Оптимизация при експериментално определена или аналитично зададена целева функция.
-В зависимост от ограниченията
-#Без ограничения;
-#С факторни ограничения;
-#С функционални и смесени ограничения;
-#Оптимизация в изпъкнали, неизпъкнали и несвързани допустими области
-Основни изисквания към оптимизационните алгоритми
-#Сходимост.
-#Бърза сходимост - получаване на решение за кратко време с малък брой изчисления на целевата функция.
-#Малка заемана памет от програмата на ИМ.
-#Лесна подготовка на условията на задачата за алгоритъма и минимална входна информация за работата на програмата.
-#Сигурно изпълнение на критерия за спиране на търсенето съобразно зададената точност.
-#Изпълнение на всички ограничения, наложени от задачата.
-#Универсалност.
 ==Вижте още==
@@ Ред 310: / Ред 19: @@
 *[[Избор на алгоритъм за нелинейна оптимизация]]
 *[[Предпоставки за оптимизационна задача]]
+*[[Методи за решение при многокритериална оптимизация]]
+*[[Многокритериална оптимизация]]
 *[[Производство]]
 *[[Продукция]]