ФОРМУЛИРОВКА МАТЕМАТИЧЕСКОЙ ЗАДАЧИ ОПТИМИЗАЦИИ
Оценка 4.7

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

Оценка 4.7
doc
математика
08.05.2020
ФОРМУЛИРОВКА МАТЕМАТИЧЕСКОЙ ЗАДАЧИ ОПТИМИЗАЦИИ
37. ФОРМУЛИРОВКА МАТЕМАТИЧЕСКОЙ ЗАДАЧИ ОПТИМИЗАЦИИ.doc

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

В общем виде математическую задачу оптимизации можно сформулировать следующим образом:

Минимизировать (максимизировать) целевую функцию с учетом ограничений на управляемые переменные.

Под минимизацией (максимизацией) функции n переменных f(x) = f(x1,...,xn) на заданном множестве U n-мерного векторного пространства En понимается определение хотя бы одной из точек минимума (максимума) этой функции на множестве U, а также, если это необходимо, и минимального (максимального) на U значения f(x).

При записи математических задач оптимизации в общем виде обычно используется следующая символика:

f(x)min (max), x U, где f(x) – целевая функция, а U – допустимое множество, заданное ограничениями на управляемые переменные.

Многие задачи как практического, так и теоретического характера касаются выбора «наилучшей» конфигурации или множества параметров для достижения некоторой цели. Сложилась иерархия таких задач вместе с соответствующим набором методов их решения. Объектом иерархии является общая задача нелинейного программирования (НЛП):

                                                                    (1.1)

 i = 1,2,… r,                                                     (1.2)

 i = r + 1, r + 2,… m,                                       (1.3)

где f, gi – произвольные функции параметра x Î Rn.

От задачи максимизации, производя замену  перейдем к задаче минимизации. Поэтому почти всегда будем говорить о задаче минимизации.

В задачах (1)–(3), x Î Rn, f: Rn ® R1 – целевая функция, а множество точек x Î Rn, удовлетворяющих ограничениям (1.2), (1.3), – это допустимое множество, будем обозначать его X.

В теории НЛП изучаются:

1)       проблемы существования решения;

2)       проблемы установления признаков оптимальности, т.е. установления характерных свойств, присущих точкам минимума;

3)       методы вычисления оптимальных решений.

1.1 Примеры оптимизационных задач

Рассмотрим некоторые из примеров задач оптимизации.

1 Оценка параметров и структуры математической модели. Задачи поиска оптимума возникают, например, при построении математических моделей. Когда для изучения какого-либо явления конструируется математическая модель, к оптимизации прибегают для того, чтобы определить ее структуру и параметры, которые обеспечивают наилучшее согласование с реальностью.

Пусть результат измерения случайной величины у зависит от x Î Rp, причем

,

где у – результат измерения;

h(x,q) – функция, вид которой известен;

q Î Rm – неизвестные параметры функции.

Оценка неизвестных параметров q при определенных условиях может быть произведена, например, по методу наименьших квадратов посредством минимизации суммы квадратов

по q.

Здесь N – количество наблюдений.

Для определения структуры модели, т.е. определение ее вида, создается множество альтернативных моделей, среди которых выбирается одна из моделей по некоторому критерию. В качестве критерия может выступать либо сумма квадратов S(q), либо оценка дисперсии модели.

2 Распределение ресурсов в условиях неполной информации. Пусть имеется m ресурсов в количествах, задаваемых компонентами bj, 1 £ j £ m, вектора b Î Rm. Обозначим А=[a1,…,an] матрицу размера m × 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.

Для некоторых практических задач такая детерминированная модель не адекватна реальности, так как 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 на величину Dz более существенно реагирует на уменьшение дохода.

1.2 Понятие локального и глобального экстремума.

Существование решения

В задачах (1.1–1.3) различают точки минимума двух видов.

Точка x* Î X называется точкой локального минимума, если

f (x*) £ f(x) "x Î Оe (x*), где Оe (x*) = {x Î Rn |  ||x* x|| £ e},

e окрестность точки x*, e > 0.

Точка х*  называется точкой глобального минимума, если

f(x*) £ f(x) " x Î X.

Множество x Î Rn называется компактным, если любая последовательность {xk} Î X имеет хотя бы одну предельную точку x* Î X. Известно, что всякая ограниченная последовательность имеет хотя бы одну предельную точку. Поэтому в Rn компактным является любое замкнутое ограниченное множество.

Как известно из курса математического анализа, внутренние точки локального и глобального минимума функции f(x) являются стационарными точками критерия оптимальности f(x) (рис. 1) или решениями уравнения

f(x) = 0.                                                         (1.4)

 Стационарными точками критерия оптимальности f(x), где x – скаляр, называются точки, в которых первая производная функции f(x) равна нулю (стационарными точками критерия оптимальности f(x), где x – вектор, называются точки, в которых градиент функции f(x) равен нулю).

 

 

 

 

 

 

 

 

 

 

 

Рис. 1.1. Локальные минимумы (x1*, x3*), локальный максимум (x2*)           и точка перегиба (xc*) функции f(x)

Но решениями уравнения (1.4) являются не только точки минимума, но и точки максимума и точки перегиба функции f(x) (рис. 1.1). Следовательно, уравнение (1.4) является только необходимым условием минимума, но не является достаточным условием.

Если существует вторая производная функции f′′(x), то для отыскания достаточных условий минимума f(x) можно привлечь эту производную. Из курса математического анализа известно, что если в точке х0 значение первой производной функции f(x) равно нулю, а второй производной – положительно, то в этой точке функция f(x) имеет минимум (локальный или глобальный).

Следующая теорема даёт достаточные условия существование оптимального решения задачи (1.1–1.3).

Теорема 1 (Вейерштрасса). Для того чтобы в задаче (1.11.3) существовала точка глобального минимума, достаточно, чтобы допустимое множество X было компактно, а целевая функция f непрерывна на X.

В силу сложности проверки ограниченности множества X, а зачастую в силу его неограниченности на практике, часто применяется:

Следствие (теоремы Вейерштрасса). Если функция f непрерывна в Rn и , то f достигает своего глобального минимума в любом замкнутом подмножестве Rn.


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

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

Оценка параметров и структуры математической модели

Оценка параметров и структуры математической модели

Для некоторых практических задач такая детерминированная модель не адекватна реальности, так как

Для некоторых практических задач такая детерминированная модель не адекватна реальности, так как

D z более существенно реагирует на уменьшение дохода

D z более существенно реагирует на уменьшение дохода

Рис. 1.1. Локальные минимумы ( x 1 * , x 3 * ), локальный максимум ( x 2 * ) и точка перегиба ( x…

Рис. 1.1. Локальные минимумы ( x 1 * , x 3 * ), локальный максимум ( x 2 * ) и точка перегиба ( x…
Скачать файл