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


 

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

15265. ЭКСПЕРИМЕНТАЛЬНОЕ ПОСТРОЕНИЕ ОБЛАСТЕЙ УСТОЙЧИВОСТИ ЛИНЕЙНОЙ СИСТЕМЫ НА ПЛОСКОСТИ ДВУХ ПАРАМЕТРОВ. МЕТОДИЧКА 84.95 KB
  ЛАБОРАТОРНАЯ РАБОТА № 8 ЭКСПЕРИМЕНТАЛЬНОЕ ПОСТРОЕНИЕ ОБЛАСТЕЙ УСТОЙЧИВОСТИ ЛИНЕЙНОЙ СИСТЕМЫ НА ПЛОСКОСТИ ДВУХ ПАРАМЕТРОВ Цель работы. Ознакомление с экспериментальными методами построения областей устойчивости линейных динамических систем и изучение влияния на...
15266. ЭКСПЕРИМЕНТАЛЬНОЕ ПОСТРОЕНИЕ ОБЛАСТЕЙ УСТОЙЧИВОСТИ ЛИНЕЙНОЙ СИСТЕМЫ НА ПЛОСКОСТИ ДВУХ ПАРАМЕТРОВ 69.47 KB
  Лабораторная работа №8 ЭКСПЕРИМЕНТАЛЬНОЕ ПОСТРОЕНИЕ ОБЛАСТЕЙ УСТОЙЧИВОСТИ ЛИНЕЙНОЙ СИСТЕМЫ НА ПЛОСКОСТИ ДВУХ ПАРАМЕТРОВ Вариант №1 1. Цель работы. Ознакомление с экспериментальными методами построения областей устойчивости линейных динамических систем и изуче...
15267. ЭКСПЕРИМЕНТАЛЬНОЕ ПОСТРОЕНИЕ ЧАСТОТНЫХ ХАРАКТЕРИСТИК ТИПОВЫХ ДИНАМИЧЕСКИХ ЗВЕНЬЕВ 1.98 MB
  ЛАБОРАТОРНАЯ РАБОТА № 9 ЭКСПЕРИМЕНТАЛЬНОЕ ПОСТРОЕНИЕ ЧАСТОТНЫХ ХАРАКТЕРИСТИК ТИПОВЫХ ДИНАМИЧЕСКИХ ЗВЕНЬЕВ Цель работы. Изучение частотных характеристик типовых динамических звеньев и способов их построения. Методические рекомендации. До начала работы студенты д
15268. Экспериментальное построение частотных характеристик типовых динамических звеньев 160.34 KB
  Лабораторная работа №9 Экспериментальное построение частотных характеристик типовых динамических звеньев Вариант 1 Цель работы. Изучение частотных характеристик типовых динамических звеньев и способов их построения. Исследуемые звенья: 1. Апериодическ...
15269. ИССЛЕДОВАНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ЭЛЕКТРОМЕХАНИЧЕСКОГО ОБЪЕКТА УПРАВЛЕНИЯ 2.5 MB
  ЛАБОРАТОРНАЯ РАБОТА № 10 ИССЛЕДОВАНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ЭЛЕКТРОМЕХАНИЧЕСКОГО ОБЪЕКТА УПРАВЛЕНИЯ Цель работы. Изучение математических моделей и исследование характеристик электромеханического объекта управления построенного на основе электродвигателя пос...
15270. Построение математической модели электромеханического объекта управления 332 KB
  Лабораторная работа №10 Построение математической модели электромеханического объекта управления по курсу Теория управления вариант 1 Цель работы: изучение математических моделей и исследование характеристик электромеханического объекта управления пост...
15271. Исследование механических характеристик АД с короткозамкнутым ротором 317.01 KB
  2 ОТЧЁТ ПО ЛАБОРАТОРНОЙ РАБОТЕ №1 Тема: Исследование механических характеристик АД с короткозамкнутым ротором Цель работы: с помощью приложений ActiveASMA и DynAMA исследовать механические характеристики АД с короткозамкнутым ротором; исследовать зависимости...
15272. Исследование механических характеристик ДПТ с независимым возбуждением в двигательном режиме 904.83 KB
  ОТЧЁТ ПО ЛАБОРАТОРНОЙ РАБОТЕ №2 Тема: Исследование механических характеристик ДПТ с независимым возбуждением в двигательном режиме Цель работы: с помощью приложений ActiveASMA и DynAMA исследовать механические характеристики ДПТ с независимым возбуждением получить иск...