Экспериментальный задачи

Задачи отыскания наибольших или наименьших величин часто возникают в науке, технике и экономике. Чтобы применять математические методы для их решения и анализа, необходимо уметь переходить от содержательной к математической постановке задачи. Для этого нужно определить целевую функцию f, множество допустимых решений Q для функции f и критерий оптимизации extr ϵ {min, max}. Таким образом, тройка вида (f,Q, extr) задает экстремальную или оптимизационную задачу. Формально математическая постановка выглядит следующим образом: . Учитывая равенство min f (x) = - max(-f (x)) при , в дальнейшем ограничимся рассмотрением только задач минимизации. Будем говорить, что задача минимизации решена, если

1) либо найдено ее оптимальное решение, то есть точка такая, что f (x*) ≤ f (x) для всех . Символически это записывается в виде равенства при

2) либо найден конечный инфинум при целевой функции на множестве Q в случае, когда оптимального решения не существует;

3) либо доказано, что целевая функция неограниченна снизу на множестве допустимых решений;

4) либо установлено, что множество допустимых решений пусто.

Далее будем рассматривать экстремальные задачи, в которых допустимое множество задается в следующем виде: Q = { x ϵ S | φ_i (x) ≤ 0, i = 1,…,m }, где S является либо подмножеством пространства Rⁿ, либо подмножеством Zⁿ,либо – Bⁿ. Функции φ_i(x), i = 1, …,m, – скалярные функции со значениями в R. Выражения x ϵ S, φ_i(x) ≤ 0, i = 1, …,m – называются ограничениями оптимизационной задачи. Ограничения вида φ_i(x) ≤ 0, i = 1, …,m, называются функциональными, а ограничение x ϵ S называется ограничением типа включения. Различие между функциональными и нефункциональными ограничениями условно, так как каждое включение можно записать как функциональное ограничение и, наоборот. Одновременное использование этих ограничений делает постановку задачи более структурированной и, следовательно, более наглядной. Формально экстремальная задача в этом случае записывается в следующем виде: , φ_i(x) ≤ 0, i = 1, …,m

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

· дискретные или комбинаторные, если множество S конечно или счетно;

· целочисленные, если S Z ⁿ;

· булевы, если S Bⁿ;

· вещественные, если S Rⁿ;

· бесконечномерные, если S – подмножество гильбертова пространства.

Если S = Rⁿ, или S = Z ⁿ, или S = Bⁿ и отсутствуют ограничения φ_i(x) ≤ 0, i = 1, …,m, то есть m = 0, тогда экстремальная задача называется задачей безусловной оптимизации. В противном случае говорят о задаче условной оптимизации.

Если принять во внимание свойства целевой функции f и ограничений φ_i(x) ≤ 0, i = 1,…,m, то возникает более тонкое деление конечномерных экстремальных задач на классы:

· непрерывное (математическое) программирование (f, φ_i(x), i = 1,…,m, – непрерывные, произвольные, нелинейные функции, S – связное, компактное подмножество Rn);

· дискретное (математическое) программирование (f, φ_i(x), i = 1,…,m, – нелинейные функции, S – дискретное множество);

· нелинейное целочисленное программирование (f, φ_i(x), i = 1,…,m, – нелинейные функции, S Z ⁿ);

· непрерывная нелинейная оптимизация без ограничений (f – непрерывная, произвольная, нелинейная функция, m = 0, S = Rⁿ);

· целочисленная нелинейная оптимизация без ограничений (f – произвольная, нелинейная функция, m = 0, S = Z ⁿ);

· выпуклое программирование (f, φ_i(x), i = 1,…,m, – произвольные, выпуклые функции, S – выпуклое подмножество Rⁿ);

· линейное программирование (f, φ_i(x), i = 1,…,m, – произвольные, линейные функции, S = Rⁿ );

· целочисленное линейное программирование (f, φ_i(x), i = 1,…,m, – произвольные, линейные функции, S Z ⁿ).

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

Теорема 1 (Вейерштрасса). Если функция f (x) определена и непрерывна на замкнутом ограниченном множестве X, то она достигает на этом множестве своих точных верхней и нижней границ.

Условие компактности множества X, использованное в теореме, является довольно жестким. И неприменимо для таких часто встречающихся множеств, как S = Rⁿ или S = . Однако, ослабляя ограничения на множество X и накладывая дополнительные требования на функцию f, из теоремы Вейерштрасса можно получить следующие два следствия.

Следствие 1. Если функция f(x) определена и непрерывна на непустом замкнутом множестве X и для некоторой фиксированной точки v из X множество Лебега M(v) = { x ϵ X | f (x) ≤ f (v) } ограничено, то функция достигает на множестве X своей точной нижней границы.

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

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

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

Не нашли, что искали? Воспользуйтесь поиском: