Файл: Сахарова Людмила Викторовна, Лукьянова Галина Викторовна Методы оптиизации для машинного обучения учебное пособие.doc

оптимальная) ситуация, и представляет собой задачу оптимизации.Одни и те же величины, в зависимости от выбранных границ оптимизируемой системы и уровня детализации её описания, могут оказаться либо управляемыми переменными, либо нет. Например, в упомянутой ситуации с оптимизацией работы цеха объем поставок какого–либо сырья из другого цеха в одних случаях следует считать фиксированным или не зависящим от нашего выбора, а в других случаях – регулируемым, т.е. управляемой переменной.

1.3. ОПРЕДЕЛЕНИЕ ОГРАНИЧЕНИЙ НА УПРАВЛЯЕМЫЕ ПЕРЕМЕННЫЕ

В реальных условиях на выбор значений управляемых переменных, как правило, наложены ограничения, связанные с ограниченностью имеющихся ресурсов, мощностей и других возможностей. При построении математической модели эти ограничения обычно записывают в виде равенств и неравенств или указывают множества, которым должны принадлежать значения управляемых переменных. Совокупность всех ограничений на управляемые переменные определяет так называемое допустимое множество задачи оптимизации.Например, если годовой объем выпускаемой цехом продукции данного вида является управляемой переменной, то ее значения, во–первых, не могут быть отрицательными и, во–вторых, ограничены сверху максимальной производительностью оборудования цеха.

1.4. ВЫБОР ЧИСЛОВОГО КРИТЕРИЯ ОПТИМИЗАЦИИ

Обязательной составной частью математической модели объекта оптимизации является числовой критерий, минимальному или максимальному значению которого (в зависимости от конкретной задачи) соответствует наилучший вариант поведения исследуемого объекта. Величина этого критерия полностью определяется выбранными значениями управляемых переменных, т.е. он является функцией этих переменных и называется целевой функцией.В инженерной практике используется широкий спектр критериев оптимизации. Это могут быть критерии экономического характера, например, себестоимость, прибыль, капитальные затраты и т.д., технические или физические параметры системы – продолжительность технологического процесса, потребляемая энергия, максимальная механическая нагрузка, достигнутая скорость движения и другие.Следует отметить, что во многих случаях выбор критерия оптимизации не является очевидным и однозначным. Часто бывает трудно поставить в соответствие всей совокупности целей функционирования системы какой–либо один критерий. Это объясняется различными причинами такими, как сложность целевой функции, описывающей большую совокупность разнородных целей, неопределенность формулировок некоторых целей, препятствующая описанию их с помощью количественных характеристик, наличие противоречивых целей, важность каждой из которых зависит от точки зрения и т.д. Например, невозможно найти решение, обеспечивающее одновременно минимальные затраты,

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

Выход из этого положения определяется в каждом конкретном случае. Например, из многих критериев, характеризующих различные цели оптимизации, выбирают один, считая его основным, а остальные – второстепенным. Далее второстепенные критерии либо не учитываются, либо учитываются частично с помощью дополнительных ограничений на управляемые переменные. Эти ограничения обеспечивают изменение второстепенных критериев в заданных диапазонах приемлемых значений.

Другой путь состоит в формулировке комплексного критерия, т.е. целевой функции, включающей с разумно выбранными весовыми коэффициентами целевые функции, соответствующие различным целям.

1.5. ФОРМУЛИРОВКА МАТЕМАТИЧЕСКОЙ ЗАДАЧИ ОПТИМИЗАЦИИ

Объединяя результаты предыдущих этапов построения математической модели, ее записывают в виде математической задачи оптимизации, включающей построенную целевую функцию и найденные ограничения на управляемые переменные. В достаточно общем виде математическую задачу оптимизации можно сформулировать следующим образом; минимизировать (максимизировать) целевую функцию с учетом ограничений на управляемые переменные.Под минимизацией (максимизацией) функции п переменных f (x)=(x₁ ,.., x_n) на заданном множестве Un–мерного векторного пространства Е_n понимается определение хотя бы одной из точек минимума (максимума) этой функции на множестве U, а также, если это необходимо, и минимального (максимального) на множестве U значения f (x). При записи математических задач оптимизации в общем виде обычно используется следующая символика:f (x) min (max),хUгде f (x) – целевая функция, а U – допустимое множество, заданное ограничениями на управляемые переменные.

Глава 2

ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ

В этой главе рассматривается простейшая математическая модель оптимизации, в которой целевая функция зависит от одной переменной, а допустимым множеством является отрезок вещественной оси:

f (x) min, (2.1)хab.Как уже отмечалось, максимизация целевой функции (f (x)  max)эквивалентна минимизации противоположной величины (–f (x)  min), поэтому мы будем рассматривать только задачи минимизации.К математическим задачам вида (2.1) приводят прикладные задачи оптимизации с одной управляемой переменной. Кроме того, необходимость в минимизации функций одной переменной возникает при реализации некоторых методов решения более сложных задач оптимизации.

2.1. ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ

2.1.1. МИНИМУМ ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ

Пусть функция f (x) определена на множестве U вещественной оси R. Напомним некоторые основные понятия.1. Число х*Uназывается точкой глобального (абсолютного) минимума или просто точкой минимума функции f (x) на множестве U, еслиf (x*) f (x) для всех хU. Значение f * = f (x*) = называют глобальным (абсолютным) минимумом или просто минимумом функции f (x) на множестве U.Множество всех точек минимума f (x) на U будем в дальнейшем обозначать через U*.2. Число Uназывается точкой локального минимума функции f (x), если для всех xU, достаточно близких к , т.е. если существует  > 0 такое, что это неравенство выполняется для любого .3. Пусть функция f (x) ограничена снизу на множестве U, т.е. f (x)  А >–∞ для всех хU. Число f _ называется точной нижней гранью функции f (x)на множестве U ( ), если f (x)f _ при всех хU и для любого  > 0 найдется точка x_ Uтакая, что f (x_) <f _ +  (т.е. среди значений f (x) на множестве U найдутся как угодно близкие к f _).Для неограниченных снизу функций f (x) полагают f _ = – ∞.Замечания:1. Глобальный минимум f (x)является и локальным минимумом, а обратное, неверно.