Eng | Rus | Ukr
Исследование операций
04.10.2008

<< prev | ^up^ | next >>

5 КЛАССИЧЕСКИЙ  МЕТОД  ОПРЕДЕЛЕНИЯ  УСЛОВНОГО экстремума

Задача нелинейного программирования (задача НП) в общем виде формулируется так [18; 2]:

максимизировать 

при ограничениях  

где функции ,  нелинейны.

В отличие от задачи ЛП для задач НП нет универсального метода решения.

В задаче ЛП допустимое множество R всегда является выпуклым с конечным числом крайних точек. Поэтому воспользовавшись симплекс-методом и перебрав только крайние точки, можно за конечное число шагов найти оптимальное решение. В задачах НП, наоборот, выпуклость допустимого множества и конечность числа его крайних точек совсем необязательны. Это и служит причиной основной трудности решения задач НП.

Рассмотрим некоторые примеры.



     Рис 1                                             Рис2                                                   Рис3

Пример 5.1. Пусть допустимое множество  определяется такими ограничениями (см.рис. 5.1):

Допустимое множество решений является невыпуклым.

Пример 5.2. Пусть 

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

Пример 5.3.

Максимизировать

при ограничениях 

Построим допустимое множество решений (рис.5.3). Задаваясь , строим семейство эллипсов с общими осями. На рисунке видно, что точка максимума  попадает на границу множества решений.

Для определения условного экстремума (то есть экстремума при ограничениях) можно воспользоваться методами дифференциального исчисления, когда функция  имеет не ниже второй производной. Рассмотрим некоторые важные понятия и теоремы классического анализа, которые лежат в основе классических методов поиска условного экстремума [18].

Теорема 5.1 (теорема существования экстремума).  Если  - непрерывная функция, определенная на замкнутом и

                         Рис.5.4.                                         Рис. 5.5.

ограниченном множестве , то она достигает на этом множестве, по крайней мере один раз, своих максимального и минимального значений.

Следующая теорема определяет возможные местоположения максимума (или минимума).

Теорема 5.2.  Если  является непрерывной функцией нескольких переменных, определенной на допустимом множестве , то максимальное значение , если оно существует, достигается в одной или нескольких точках, которые принадлежат одному из следующих множеств:     1)  - множество стационарных точек; 2) - множество точек границы; 3) - множество точек, где функция  недифференцируема.

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

                               (5.1.1)

Определение 5.2. Функция  достигает локального максимума в точке , если для всех точек , лежащих в малой окрестности точки  имеет место неравенство

                    (5.1.2)

Определение 5.3. Функция  достигает глобального (абсолютного) максимума в точке , если для всех точек  справедливо неравенство

Для нахождения стационарных точек функции  можно использовать следующую теорему.

Теорема 5.3. Пусть  дифференцируема в некотором допустимой области . Если в некоторой внутренней точке  области  функция  достигает относительного максимума, то

                              (5.1.3)

Пример 5.4. Пусть  определена на множестве  (то есть на всей плоскости ).

Для нахождения относительного экстремума этой функции имеем два уравнения:

Решив их, находим

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

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

                     (5.1.4)

Если

                     (5.1.5)

то функция называется выпуклой (рис.5.5).

Если (5.1.4) или (5.1.5) выполняются как строгие неравенства, то функция называется строго вогнутой или строго выпуклой соответственно.

Кртерий выпуклости и вогнутости функции -переменных можно сформулировать в виде следующей теоремы.

Теорема 5.4. Дифференцируемая функция  строго вогнутая в некоторой окрестности точки , если выполняются следующие условия:

          (5.1.6)

И так далее, то есть если знаки определителей чередуются начиная с < 0, где

Text Box: 
Рис. 5.6
Функция  строго выпукла в окрестности точки , если все определители (выписанные выше) положительные.

Имеет место следующая теорема.

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

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

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

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

Рассмотрим некоторую вогнутую функцию . Выберем две произвольных точки  и  (рис.5.6). Тогда                              . Поскольку , то и точка  принадлежит . Из условия вогнутости  следует, что  

Следовательно, множество  содержит отрезок  ,и поэтому оно выпукло (рис.5.6).

Справедливое такое утверждение: если функции - выпуклы (вогнуты) на множестве , то функция - также выпукла (вогнута) при условии, что все .

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

Рассмотрим метод поиска условного экстремума. Он состоит из следующих процедур.

1.Отыскивают множество всех стационарных точек  функции  на выпуклом допустимом множестве . Найденные точки далее исследуют на максимум (минимум) и определяют точку наибольшего максимума .

2. Переходят к исследованию точек границы  и отысканию тех из них, где  достигает максимума. Этот процесс состоит в следующем. Выбирают произвольную границу, определяемую, например, условием . Если функция 

                               (5.1.7)

является сепарабельной, то можно, определив из (5.1.7) переменную

           

подставить ее в выражение для . Тим самым задача сведется к поиску безусловного экстремума, для чего можно использовать процедуру, описанную в п.1.

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

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

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

Обобщение понятия выпуклой функции. Рассмотрим некоторые классы функций, которые не являются полностью выпуклыми, но обладают лишь отдельными их свойствами.

Определение 5.5. Пусть функция  определена на непустом и выпуклом множестве . Функция  квазивыпукла, если для любых  и  выполняется неравенство

                (5.1.8)

Функция  называется квазивогнутой, если  - квазивыпуклая функция.

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

Text Box: 
Рис. 5.7
На рис. 5.7 приведены примеры квазивыпуклых и квазивогнутых функций, где а - квазивыпуклая, б - квазивогнутая функции.

Введем понятия строгой квазивыпуклости  и квазивогнутости.

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

                (5.1.9)

Функция  называется строго квазивогнутой, если  - строго квазивыпуклая функция. На рис. 5.8 изображены: а, б - строго квазивыпуклые функции, в - квазивогнутая функция. Из приведенного определения следует, что любая выпуклая функция является в тоже время и строго квазивыпуклой.

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

Text Box: 
Рис. 5.8

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

Рис. 5.8

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

                      (5.1.11)

для всех  для некоторого .

Поскольку  - квазивыпуклая функция и выполняется неравенство , то мы получим, что  при всех . Однако это соотношение противоречит (5.1.11).

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

<< prev | ^up^ | next >>

 
     
  Copyright © 2002-2004