1 Постановки экстремальных задач

1.1.Предмет методов оптимизации1.1.1. Постановки экстремальных задач Многие задачи, как практического, так и теоретического характера касаются выбора «наилучшей» конфигурации или множества параметров для достижения некоторой цели. Сложилась иерархия таких задач вместе с соответствующим набором методов их решения. Объектом иерархии является общая задача нелинейного программирования (НЛП): (1)i=1,2,……r (2)i=r+1, r+2, ….m (3) где f, gi – произвольные функции параметра x  Rn. От задачи максимизации, производя замену перейдем к задаче минимизации. Поэтому почти всегда будем говорить о задаче минимизации. В задаче (1)-(3), x  Rn , f: Rn R1 - целевая функция, а множество точек x  Rn, удовлетворяющих ограничениям (2),(3) – это допустимое множество, будем обозначать его X. В теории НЛП изучаются: проблемы существования решения; проблемы установления признаков оптимальности, т.е. установления характерных свойств, присущих точкам минимума; методы вычисления оптимальных решений.^ 1.1.1. Примеры оптимизационных задач Рассмотрим некоторые из примеров задач оптимизации.1) Оценка параметров и структуры математической модели. Задачи поиска оптимума возникают, например, при построении математических моделей. Когда для изучения какого-либо явления конструируется математическая модель, к оптимизации прибегают для того, чтобы определить ее структуру и параметры, которые обеспечивают наилучшее согласование с реальностью. Пусть результат измерения случайной величины у зависит от x  Rp, причем, где у - результат измерения, (x,) - функция, вид которой известен,   Rm - неизвестные параметры функции. Оценка неизвестных параметров  при определенных условиях может быть произведена, например, по методу наименьших квадратов посредством минимизации суммы квадратов по . Здесь N- количество наблюдений. Для определения структуры модели, т.е. определение ее вида, создается множество альтернативных моделей, среди которых выбирается одна из моделей по некоторому критерию. В качестве критерия может выступать либо сумма квадратов S(), либо оценка дисперсии модели.^ 2) Распределение ресурсов в условиях неполной информации. Пусть имеется m ресурсов в количествах, задаваемых компонентами bj, 1  j  m, вектора b  Rm. Обозначим А=[a1,…,an] матрицу размера m x n. Столбец aj – матрицы A характеризует затраты ресурсов на единицу интенсивности j-го способа производства. Обозначим x  Rn вектор, компоненты которого xj, 1  j  n, j-го способа производства, а с  Rn вектор, компоненты которого сj, j=1,…,n, доход от единицы продукции j-го способа производства. Обозначим z = (c,x) - общий доход. В принятых обозначениях задача распределения ресурсов между способами производства с целью максимизации дохода имеет вид:(c,x)  Ax  b, x  0. (4) Для некоторых практических задач такая детерминированная модель не адекватна реальности, так как Cj, j=1,2,…,n случайные величины. Предположим, что с - случайный вектор с математическим ожиданием и ковариационной матрицей ^ V. Тогда значение целевой функции z будет случайной величиной с математическим ожиданием и дисперсией (x,Vx). Для максимизации ожидаемого значения z следует решить задачу(c,x)  Ax  b, x  0. Если требуется минимизировать дисперсию показателя z, то необходимо решить задачу (x,Vx)  min, Ax  b, x  0. В реальных задачах возникает потребность получения максимального дохода при малых значениях дисперсии. Это многокритериальная задача, которая в некоторых постановках может быть сведена к однокритериальной задаче. В следующей постановке требуется достигнуть лишь заданного уровня дохода при минимуме дисперсии . (х, Vx) min, Аx  b, (, х)  , х  0. Другой подход может состоять в минимизации вероятности недостижения заданного уровня дохода. =P. Пусть с=d+yf, где d, f -детерминированные векторы, а y - случайная составляющая. Тогда Максимизация сводится к решению задачи:Ax  b, х  0. В том случае, когда с - случайный вектор в зависимости от степени неприятия риска k производится максимизация ожидаемого значения полезности, Ax  b, х  0. Приведенная функция полезности учитывает степень риска, связанную со случайным характером величины вектора дохода с, и основана на функции полезности индивида и предположении нормального закона распределения вектора c. Последняя функция при увеличении или уменьшении дохода z на величину z более существенно реагирует на уменьшение дохода.1.1.3. Понятие локального глобального экстремума. Существование решения. В задаче (1) – (3) различают точки минимума двух видов.Точка x*  X называется точкой локального минимума, если f (x*)  f(x) x  О (x*), где О (x*) = {x  Rn | //x* - x//  } -  - окрестность точки x*,   0.Точка х* называется точкой глобального минимума, если f(x*)  f(x) x  X. Множество x  Rn называется компактным, если любая последовательность {xk}  X имеет, хотя бы одну предельную точку x* X. Известно, что всякая ограничённая последовательность имеет хотя бы одну предельную точку. Поэтому в Rn компактным является любое замкнутое ограниченное множество. Следующая теорема даёт достаточные условия существование оптимального решения задачи (1)-(3).Теорема 1 (Вейерштрасса). Для того чтобы в задаче (1)-(3) существовала точка глобального минимума, достаточно, чтобы допустимое множество X было компактно, а целевая функция f непрерывна на X. В силу сложности проверки ограниченности множества X, а зачастую, в силу его неограниченности на практике часто применяется:Следствие (теоремы Вейерштрасса). Если функция f непрерывна в Rn и , то f достаёт своего глобального минимума в любом замкнутом подмножестве Rn.