Главная | Случайная
Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






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




Задачи отыскания наибольших или наименьших величин часто возникают в науке, технике и экономике. Чтобы применять математические методы для их решения и анализа, необходимо уметь переходить от содержательной к математической постановке задачи. Для этого нужно определить целевую функцию 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 является либо подмножеством пространства Rn , либо подмножеством Zn ,либо – Bn . Функции φ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 n ;

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

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

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

Если S = Rn , или S = Z n , или S = Bn и отсутствуют ограничения φ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 n);

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

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

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

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

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

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

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

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

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

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

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

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

 


 

 

vikidalka.ru - 2015-2017 год. Все права принадлежат их авторам!