Полная версия

Главная arrow Психология arrow Искусство решать сложные задачи. Системный подход

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Нелинейное программирование

  • 1. Область применения. Используется для решения однокритериальных задач оптимизации с детерминированной целевой функцией при накладываемых ограничениях в виде равенств или неравенств. Для данного класса задач снимается условие линейности функций или ограничений.
  • 2. Сущность. Задачу нелинейного программирования в общем виде можно записать следующим образом: минимизировать (или максимизировать) целевую функцию Y—F(X) при ограничениях G(X) < О, Х> 0, при этом по крайней мере одна из функций, f(x) или g(x), является нелинейной. Нелинейность целевой функции f(x) требует исследования условий (необходимых и достаточных) наличия экстремума. Для этого надо уметь получить аналитические выражения по меньшей мере первых двух производных этой функции. При наличии линейных ограничений эти производные ищутся только в точках, удовлетворяющих данным ограничениям. Нелинейность ограничений может привести к тому, что пространство возможных решений становится невыпуклым, и тогда оптимальному решению не всегда будет соответствовать одна из угловых точек этого пространства (что характерно для задач линейного программирования).
  • 3. Особенности использования. Универсальных алгоритмов решения нелинейных задач не существует из-за большого разнообразия видов нелинейности. Методы решения принято делить на две большие группы: прямые и непрямые. Прямые используются, когда нелинейные функции непрерывны и заданы в явном виде, что позволяет применить градиентные методы поиска экстремума вдоль направления наискорейшего изменения целевой функции. В основном используются итерационные процессы решения систем нелинейных уравнений, сходимость которых зависит от выбора начального приближения.

При этом задачи с ограничениями преобразуются в задачи безусловной оптимизации.

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

4. Наиболее употребительные методы. В случаях, когда можно преобразовать задачу с ограничениями в задачу безусловной оптимизации, выразить нелинейную функцию в явном виде, получить выражение для первой и второй производных (а ещё лучше и для производных более высоких порядков), используются прямые методы оптимизации. Наиболее употребительные градиентные методы — метод наискорейшего спуска, метод Ньютона — Рафсона /59/. В противном случае имеют место непрямые методы (сепарабельное программирование, квадратичное программирование) /59/. Разработка новых методов ведётся непрерывно, в основном путём модификации уже известных с учетом особенностей решаемой задачи.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>