9899

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

Реферат

Математика и математический анализ

Классификация задач оптимизации оптимизируемая функция (целевая функция, целевой функционал, критерий качества и т.п.), численно выражает степень достижения целей функционирования оптимизиру...

Русский

2013-03-18

70 KB

146 чел.

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

 

  F(X)  

F = {f1, f2, . . . , fk} - оптимизируемая функция (целевая функция, целевой функционал, критерий качества и т.п.), численно выражает степень достижения целей функционирования оптимизируемого объекта

X = (x1, x2, ..., xn)T - вектор независимых переменных, его компоненты - неизвестные задачи оптимизации (переменные оптимизации) - являются управляемыми входами объекта оптимизации  

D - множество допустимых значений неизвестных, определяемое налагаемыми на неизвестные ограничениями (допустимая область, допустимое множество)

S - пространство оптимизации

  min F(X) = - max(-F(X))

F = {f1, f2, ..., fk}

k = 1 - задача однокритериальной или скалярной оптимизации,  

k > 1 - задача многокритериальной или векторной оптимизации

 

F(X)  

X = (x1, x2, ..., xn)T 

n = 1 - задача одномерной (иногда - линейной) оптимизации,

n > 1 - задача многомерной оптимизации или задача оптимизации со многими переменными.

Допустимая область

D = S  - задача безусловной оптимизации или задача оптимизации без ограничений (какие-либо ограничения на неизвестные отсутствуют)

D S - задача условной оптимизации или задача с ограничениями (т.е. в задаче не все значения переменных допустимы)

Пространство оптимизации

S = Rn - задача оптимизации с непрерывными переменными

S = Zn - задача целочисленной оптимизации

S = Bn - задача булевой оптимизация (частный случай задачи целочисленной оптимизации, при которой переменные могут принимать только два значения - ноль и единица). Если при этом f(X) принимает значения из Rn, то - задача псевдобулевой оптимизации

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

Задачи целочисленной и комбинаторной оптимизации объединяются понятием задач дискретной оптимизации 

В задачах смешанной оптимизации могут одновременно присутствовать переменные нескольких или даже всех типов (наиболее известный частный случай - задачи смешанного целочисленного программирования с целочисленными и непрерывными переменными)

Свойства функций, входящих в постановку задачи оптимизации

Целевая функция имеет более одного локального экстремума - задача глобальной или многоэкстремальной оптимизации (если требуется найти все локальные экстремумы или наилучший из них)

В задачах локальной оптимизации требуется найти один локальный экстремум (единственный для одноэкстремальной целевой функции или любой для многоэкстремальной)

Целевая функция и/или функции, описывающие ограничения, заданы не аналитически (в виде компьютерных программ, имитационных моделей, человеко-машинных процедур или как выход реальной системы) - задачи оптимизации с неявными функциями (поисковые задачи оптимизации)

Все функции, входящие в постановку задачи, записываются в явном аналитическом виде - задача математического программирования

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

 f(X)   ,

при ограничениях                

 hi(X) = 0, i = 1, . . . , m,

 gi(X) 0, i = m+1, . . . , p.

Все функции, входящие в постановку, являются непрерывно дифференцируемыми - задача дифференцируемой оптимизации, иначе – задача недифференцируемой оптимизации

 

Целевая функция выпукла, функции-ограниче-ния образуют выпуклую допустимую область - задача выпуклой оптимизации 

Целевая функция сепарабельна, ограничения линейны - задача сепарабельного программирования 

Целевая функция квадратичная, ограничения – линейны - задача квадратичного программирования 

Все функции общего вида - общая задача нелинейного программирования

Целевая функция и функции-ограничения являются линейными относительно независимых переменных - задача линейного программирования 

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


Примеры задач ЛП

Задача использования сырья. Для использования двух видов продукции Р1 и Р2 используют три вида сырья S1, S2 и S3. Запасы сырья в количество единиц сырья, затрачиваемых на изготовление единицы продукции, и прибыль от единицы продукции приведены в таблице. Необходимо составить план выпуска продукции, максимизирующий прибыль.

Вид сырья

Запасы

Затраты сырья

Р1

Р2

S1

20

2

5

S2

40

8

5

S3

30

5

6

Прибыль от единицы

продукции

50

40

x1  0, x2  0,

z = 50x1 + 40x2   max.


Задача составления рациона ("оптимальной смеси"). При откорме каждое животное ежедневно должно получать не менее 9 единиц питательного вещества S1, не менее 8 единиц вещества S2 и не менее 12 единиц вещества S3. для составления рациона используют два вида корма. Содержание количества единиц питательных веществ в 1 кг корма приведены в таблице. Необходимо составить дневной рацион нужной питательности, причем затраты на него должны быть минимальными.

Вещества

Кол-во ед. питат. вещ-в в 1 кг

корм 1                  

корм 2

S1

     3

     1

S2

     1

     2

S3

     1

     6

Стоимость 1 кг корма

     4

     6

Z=4x1+6x2 min

x1  0, x22 0.


Общий вид задачи ЛП:

 Z = c1x1 + c2x2 + . . . + cnxn   min (max)

при условиях:

 x1  0, x2  0, . . . , xn  0,

a11x1 + a12x2 + . . . + a1nxn   (=, ) b1,

a21x1 + a22x2 + . . . + a2nxn   (=, ) b2,

.    .    .    .   .    .    .   .    .    .    .   .

am1x1 + am2x2 + . . . + amnxn   (=, ) bm.

Значения bi, cj, aij - известны (выявлены на стадии анализа реальной ситуации)

В матричных обозначениях

.

Задача ЛП записывается в виде:

 z = CTX  min (max),

при условиях:

 X 0,  

 AX   (=, ) B.

Параметрические задачи оптимизации (параметрическое программирование) - функции и коэффициенты, входящие в постановку задачи зависят от некоторого параметра или параметров

Вся исходная информация задачи оптимизации определена однозначно – детерминированные задачи оптимизации

Все или некоторые параметры модели носят вероятностный характер - принятие решения в условиях риска (стохастические задачи, стохастическое программирование, стохастическая аппроксимация)

Неопределенность данных имеет не вероятностный характер - оптимизация в условиях неопределенности (нечеткое математическое программирование или нечеткая оптимизация)

 

Конечномерные (матпрограммирование) и бесконечномерные (вариационное исчисление)

      На плоскости xOy даны две точки А1(x1, y1) и А2(x2, y2). Найти кривую кратчайшей длины, соединяющую эти точки.

 

y(x1) = y1, y(x2) = y2.


Статические и динамические (оптимальное управление)

Задача оптимального управления:

дана система, поведение которой описывается дифференциальным уравнением

,

где x- вектор фазовых координат, u- вектор управления, t- время.

На вектора x и u наложены ограничения: x X, uU.

Система рассматривается на интервале t[0, T].

Требуется определить вектор-функции u(t), x(t) доставляющие минимум функционалу J=J(x, u) при переводе из начального состояния (x(0), 0) в конечное состояние (x(T), T).

F – дифференцируемая функция своих аргументов.


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

Один из способов классификации методов оптимизации состоит в соотнесении их оптимизационным задачам, для решения которых они предназначены

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

- методы нулевого порядка, требующие только вычислений значений функции в точках пространства оптимизации и не требующие аналитического вида производных;

- методы первого порядка (градиентные), требующие кроме значений функции в точке еще и аналитическое задание производных первого порядка для вычисления градиента;

- методы второго порядка (ньютоновские), для работы которых требуются еще и производные второго порядка

Другая классификация:

- методы прямого поиска,

- методы линейной аппроксимации,

- методы квадратичной аппроксимации,

 

По степени математической обоснованности методы делят на эвристические и рациональные.

Методы оптимизации подразделяют на детерминированные и стохастические. Стохастические алгоритмы используют элементы случайности при выборе направления или длины шага в процессе оптимизации.

Оптимизирует не компьютер и даже не алгоритм, введенный в этот компьютер. Оптимизирует всегда человек. Он и несет ответственность за результат.

10

PAGE  8


 

А также другие работы, которые могут Вас заинтересовать

23058. Загрози національній безпеці України у політичній сфері та шляхи їх нейтралізації 40 KB
  Загрози національній безпеці України у політичній сфері та шляхи їх нейтралізації. Загрози у внутрішньополітичній сфері: порушення з боку органів державної влади та органів місцевого самоврядування Конституції і законів України прав і свобод людини і громадянина в тому числі при проведенні виборчих кампаній недостатня ефективність контролю за дотриманням вимог Конституції і виконанням законів України; можливість виникнення конфліктів у сфері міжетнічних і міжконфесійних відносин радикалізації та проявів екстремізму в діяльності деяких...
23059. Загрози національній безпеці України в економічній сфері та шляхи їх подолання 38 KB
  Загрози в економічній сфері: істотне скорочення внутрішнього валового продукту зниження інвестиційної та інноваційної активності і науковотехнічного та технологічного потенціалу скорочення досліджень на стратегічно важливих напрямах інноваційного розвитку; ослаблення системи державного регулювання і контролю у сфері економіки; нестабільність у правовому регулюванні відносин у сфері економіки в тому числі фінансової фіскальної політики держави; відсутність ефективної програми запобігання фінансовим кризам; зростання...
23060. Загрози національній безпеці України в соціальній сфері та шляхи їх подолання 22 KB
  Загрози у соціальній та гуманітарній сферах: невідповідність програм реформування економіки країни і результатів їх здійснення визначеним соціальним пріоритетам; неефективність державної політики щодо підвищення трудових доходів громадян подолання бідності та збалансування продуктивної зайнятості працездатного населення; криза системи охорони здоров'я і соціального захисту населення і як наслідок небезпечне погіршення стану здоров'я населення; поширення наркоманії алкоголізму соціальних хвороб; загострення демографічної кризи;...
23061. Загрози національній безпеці України у воєнній сфері та шляхи їх нейтралізації. Воєнна доктрина України 39 KB
  Воєнна доктрина України. Загрози у воєнній сфері та сфері безпеки державного кордону України: поширення зброї масового ураження і засобів її доставки; недостатня ефективність існуючих структур і механізмів забезпечення міжнародної безпеки та глобальної стабільності; нелегальна міграція; можливість втягування України в регіональні збройні конфлікти чи у протистояння з іншими державами; нарощування іншими державами поблизу кордонів України угруповань військ та озброєнь які порушують співвідношення сил що склалося; небезпечне...
23062. Загрози національній безпеці України в екологічній сфері та шляхи їх нейтралізації 24 KB
  Загрози в екологічній сфері: значне антропогенне порушення і техногенна перевантаженість території України зростання ризиків виникнення надзвичайних ситуацій техногенного та природного характерів; нераціональне виснажливе використання мінеральносировинних природних ресурсів як невідновлюваних так і відновлюваних; неподоланність негативних соціальноекологічних наслідків Чорнобильської катастрофи; погіршення екологічного стану водних басейнів загострення проблеми транскордонних забруднень та зниження якості води; загострення...
23063. Чорнобильська катастрофа як загроза екологічній безпеці України 53 KB
  Україну на цій зустрічі представив Міністр з питань надзвичайних ситуацій та у справах захисту населення від наслідків Чорнобильської катастрофи Василь Дурдинець який виступив із промовою. Також він наголосив на основних аспектах Чорнобильської проблематики. Це було сказано Президентом України Леонідом Даниловичем Кучмою у зверненні з нагоди закриття Чорнобильської АЕС 15 грудня 2000 року. За останні десять років коли Україна самостійно фінансує витрати на ліквідацію наслідків Чорнобильської катастрофи питома вага витрат на ці цілі не...
23064. Роль регіонального співробітництва в забезпеченні НБУ 36 KB
  Роль регіонального співробітництва в забезпеченні НБУ. Зміцнюючи двосторонні зв’язки з країнами цих регіонів Україна водночас налагоджує і взаємовигідну співпрацю на багатосторонньому рівні в рамках регіональних організацій співробітництва ЦЄІ ОЧЕС ГУУАМ СНД ЄврАзЕС що надає їй можливість стверджувати себе як впливову регіональну державу. Ідея БалтоЧорноморської системи співробітництва і безпеки: ініційована Президентом Польщі ще в 19921993 роках. Намагалися визначити шляхи розвитку регіонального співробітництва в політичній...
23065. Співробітництво України з регіональними та субрегіональними організаціями в сфері безпеки 35 KB
  Україна – НАТО. Україна не забарилася з приєднанням до Ради Північноатлантичного співробітництва РПАС і залишалась активною учасницею протягом усієї історії існування цього органу. Україна бере активну участь у заходах ПЗМ як у штабквартирі НАТО так і в країнах членах Альянсу і партнерах а також влаштовувала ряд навчань в рамках ПЗМ на своїй території яворівський полігон. Налагодженно співробітництво між НАТО і Україною в галузі інформації створено Центр інформації та документації НАТО в Києві створено Державну міжвідомчу комісію з...
23066. Поняття ядерної держави, роль ядерного та без'ядерного статусу в забезпеченні національної безпеки країни 32 KB
  Безядерний статус мають ті країни які підписали договір ДНЯЗ і зобов’язалися при цьому не виробляти не придбавати ядерну зброю або інші ядерні вибухові пристрої не домагатися і не приймати допомоги у виробництві ЯЗ. Статья II ДНЯЗ: Каждое из государствучастников настоящего Договора не обладающих ядерным оружием обязуется не принимать передачи от кого бы то ни было ядерного оружия или других ядерных взрывных устройств а также контроля над таким оружием или взрывными устройствами ни прямо ни косвенно; не производить и не приобретать...