Методы Оптимизации Систем Автоматизированного Проектирования

Общие сведения.

Задача условной оптимизации (нелинейного программирования) заключается в поиске минимального значения скалярной функции f(x) n-мерного векторного аргумента х:

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

где какие то из функций, все или несколько нелинейны. Здесь

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

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

Пример 1.

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

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

Стр.: ..., 2