Условия оптимальности решения.



Условия оптимальности решения бывают двух типов: необходимые и достаточные.

Необходимые условия оптимальности.

Общая формулировка необходимых условий: если из утверждения А всегда следует утверждение В, то В необходимо для А.

Применительно к задаче оптимизации: из утверждения А (  - лучший элемент множества D) следует утверждение В (  - лучший элемент множества L, принадлежащего D и образующего окрестность ) (рис.1.7).

 

 


                                        Рис. 1.7

Таким образом локальная неулучшаемость (  - лучший элемент среди допустимых элементов своей окрестности) является необходимым условием для того, чтобы  был оптимальным решением. Иными словами, для того чтобы был оптимальным решением на множестве D, необходимо, чтобы был оптимальным решением на множестве L, принадлежащем D и образующим окрестность точки X°. Как правило, множество L выбирают так, чтобы на нем критерий и ограничения исходной задачи точно совпадали с критерием и ограничениями вспомогательной упрощенной задачи, для которой решение можно выделить с помощью некоторых уравнений. В этом случае уравнения, выделяющие локально неулучшаемое решение, оказываются необходимыми условиями оптимальности исходной задачи. Обычно упрощенную задачу строят посредством линеаризации исходной в окрестности искомого оптимального решения.

 

Достаточные условия оптимальности.

Общая формулировка достаточных условий: если из утверждения В всегда следует утверждение А, то В достаточно для А. Применительно к задаче оптимизации из утверждения В (решение  является лучшим на множестве V, включающем множество D, причем  принадлежит D) всегда следует утверждение А (  - лучший элемент множества D) (рис.1.8)).

 

 


Рис. 1.8

 

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

Иными словами, для того, чтобы был оптимальным решением на множестве D, достаточно чтобы был оптимальным решением на множестве V, включающем множество D, и принадлежал множеству D.

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

Например множество D, представленное на рис. 1.8 целесообразно заменить областью V, которая представляет собой прямоугольник, включающий в себя область D и может быть описана автономными ограничениями вида  (см. рис. 1.8)

 

2. Определение максимума функции одной переменной.


Дата добавления: 2018-02-15; просмотров: 394; ЗАКАЗАТЬ РАБОТУ