Математическое Программирование в Примерах и Задачах

Оптимизация — в математике, информатике и исследовании операций задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного пространства, ограниченной набором линейных и/или нелинейных равенств и/или неравенств.

Теорию и методы решения задачи оптимизации изучает математическое программирование.

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

В процессе проектирования ставится обычно задача определения наилучших, в некотором смысле, структуры или значений параметров объектов. Такая задача называется оптимизационной. Если оптимизация связана с расчётом оптимальных значений параметров при заданной структуре объекта, то она называется параметрической оптимизацией. Задача выбора оптимальной структуры является структурной оптимизацией.

Стандартная математическая задача оптимизации формулируется таким образом. Среди элементов χ, образующих множества Χ, найти такой элемент χ*, который доставляет минимальное значение f(χ*) заданной функции f(χ). Для того, чтобы корректно поставить задачу оптимизации, необходимо задать:

1. Допустимое множество — множество X={x→|gi(x→)≤0, i=1, …, m}⊂Rn{\displaystyle \mathbb {X} =\{{\vec {x}}|\;g_{i}({\vec {x}})\leq 0, \;i=1, \ldots, m\}\subset \mathbb {R} ^{n}};
2. Целевую функцию — отображение f:X→R{\displaystyle f:\;\mathbb {X} \to \mathbb {R} };
3. (max или min).

Тогда решить задачу f(x)→minx→∈X{\displaystyle f(x)\to \min _{{\vec {x}}\in \mathrm {X} }} означает одно из:

1. Показать, что X=∅{\displaystyle \mathbb {X} =\varnothing }.
2. Показать, что целевая функция f(x→){\displaystyle f({\vec {x}})} не ограничена снизу.
3. Найти x→∗∈X:f(x→∗)=minx→∈Xf(x→){\displaystyle {\vec {x}}^{*}\in \mathbb {X} :\;f({\vec {x}}^{*})=\min _{{\vec {x}}\in \mathbb {X} }f({\vec {x}})}.
4. Если ∄x→∗{\displaystyle \nexists {\vec {x}}^{*}}, то найти infx→∈Xf(x→){\displaystyle \inf _{{\vec {x}}\in \mathbb {X} }f({\vec {x}})}.

Если минимизируемая функция не является выпуклой, то часто ограничиваются поиском локальных минимумов и максимумов: точек x0{\displaystyle x_{0}} таких, что всюду в некоторой их окрестности f(x)≥f(x0){\displaystyle f(x)\geq f(x_{0})} для минимума и f(x)≤f(x0){\displaystyle f(x)\leq f(x_{0})} для максимума.

• Учебник по Программированию для Начинающих
• Динамическое Программирование Задачи
• Динамическое Программирование Примеры Решения Задач
• Динамическое Программирование в Примерах и Задачах