Условная оптимизация


В классической теории экстремумов рассматриваются задачи математической оптимизации без ограничений. Однако такие задачи имеют чисто теоретическое значение. Это понятно из физической интерпретации целевой функции и ограничений. Т. к. оптимизационные задачи имеют истоки из экономики, то иногда целевую функцию называют функцией дохода, а балансовые уравнения – ресурсными ограничениями. В силу того, что любые практические задачи решаются в условиях ограниченности ре­сурсов, то становится понятным, что они относятся к задачам нахождения условного экстремума.

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

Отрезком, соединяющим две точки F1 и F2, называется множество точек с координатами ji=aji1 + (1–а)ji2, (0£а £1, i = ), где ji1, ji2 – координаты точек F1 и F2 соответственно; а – изменяемый параметр, определяющий положение точки F на отрезке. Если а=1, то точка F совпадает с точкой F1, а если а=0, то точка F совпадает с точкой F2.

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

Определение. Множество называется выпуклым, если для любых выполняется

,

то есть вместе с любыми двумя точками а и b оно содержит все точки соединяющего их отрезка .

выпуклое
невыпуклое
 

Определение. Функция , заданная на выпуклом множестве , называется выпуклой (вогнутой) на А, если для любых двух точек и Î А выполняется условие

Замечание. В частном случае , когда (как следует из определения, отрезок всегда выпуклое множество), понятие выпуклости (вогнутости) функции одной переменной допускает наглядную геометрическую иллюстрацию. На рис. приведена выпуклая функция ( ).

 

Пример.В качестве целевой функции принята вероятность решения задачи где u – потенциал решения. Проверить, является ли принятая функция вогнутой.

Решение Вычислим первую и вторую производные функции , получим: , следовательно, функция является вогнутой.

Ответ. Да.

Если во всех точках интервала (a, b) вторая производная функции f(x) отрицательна, то кривая y = f(x) обращена выпуклостью вверх (вогнута).

Определение. Кривая обращена выпуклостью вверх на интервале (а, b), если все ее точки лежат ниже любой ее касательной на этом интервале. Кривая, обращенная выпуклостью вверх, называется вогнутой, а кривая, обращенная выпуклостью вниз – называется выпуклой.

 

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

ТеоремаЕсли во всех точках интервала (a, b) вторая производная функции f(x) отрицательна, то кривая y = f(x) обращена выпуклостью вверх (вогнутая).

Область называется замкнутым полупространством, если ее множество точек удовлетворяет неравенству вида:

а1j12j2+…+ аnjn£ b,

где ji – оценки альтернатив по i-му критерию (i-я координата вектора свойств альтернатив); аi – коэффициенты, позволяющие приводить значения jI к одной шкале. Данное полупространство обладает свойством выпуклости.

Точка F, принадлежащая выпуклой области, называется крайней, если в данной об­ласти нет других двух точек F1 и F2, что ji=aji1 + (1–а)ji2 таких, что F лежит на этом от­резке. Крайняя точка области не может находиться на отрезке между двумя точками, при­надлежащими той же области.

На рис. приведены геометрические иллюстрации сделанных определений.

Фундаментальная теорема математического программирования –теорема Вейерштрасса –формулирует условия существования глобального максимума.

Необходимое условие существования условного относительного экстремума аналогично условию существования безусловного относительного экстремума. Об условном экстремуме говорят, когда целевая функция W(j) ограничена областью F (j Î F) возможных векторов.

Область F задается равенствами или неравенствами функций gj(j){£,=, ³}bj и областью определения (допустимых значений) jiÎQi, для i = . В данной ситуации внутри области F может не оказаться точки j0 с координатами (j10,..., jn0), в которой, градиент функцииW(j) обращается в ноль в ее e - окрестности; либо таких точек может оказаться несколько. Однако, значения W(j) в крайних точках области F могут быть наибольшими (наименьшими), даже больше (меньше), чем в точках относительного экстремума.

Таким образом, условный относительный экстремум может находиться в одной или нескольких точках безусловного относительного экстремума j0ÎF, (если они есть) либо в одной или нескольких крайних точек.

Отметим, что условие ÑW(j) = 0 является необходимым, но не достаточным условием существования относительного экстремума. Он определяет стационарные точки функции.

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

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

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

Теорема (локально-глобальная). Пусть допустимое множество не пусто и является компактным и выпуклым, а непрерывная целевая функция является вогнутой на . Тогда:



Дата добавления: 2016-05-28; просмотров: 2153;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.01 сек.