Задачи нелинейного программирования

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

Задачи Нелин-о программ-я можно классиф-ь в соответствии с видом функции F(x), функ-и огран-й и размерностью вектора х (вектора реш-й).

В самом общем виде классификация представлена в таблице.

Общих способов реш-я, аналогичных симплекс-методу лин-о программ-я, для нелинейного программирования не существует. В каждом конкретном случае способ выбирается в зав-и от вида фун-ии F(x).

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

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

Общая формулировка нелинейных задач:

Найти переменные х1, х2, …, хn, удовлетворяющие системе уравнений

Ψ(х1, х2,…,хn) = bi, i = 1, 2, …, m

и обращающие в макс (мин) целевую функцию Z = f (х1, х2,…,хn)

Задачи безусловной однопараметрической оптимизации.

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

Численный метод решения задачи.

Задачи одномерной минимизации представляют простейшую математ-ю модель оптимизации,в кот-ой целевая фу-ия зав-т от одной переменной, а допустимым множеством является отрезок вещественной оси:

f(x) -> min, x принадлежит [a, b].

Максимизация целевой фу-ии эквивалента минимизации (f(x)->max) эквивалентна минимизации противоположной вел-ы (-f(x)->min), поэтому, не умаляя общности можно рассматривать только задачи миним-ии.

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

Для решения задачи минимизации функции f(x) на отрезке [a, b] на практике, как правило, применяют приближенные методы. Они позволяют найти решения этой задачи с необходимой точностью в результате определения конечного числа значений функции f(x) и ее производных в некоторых точках отрезка [a, b]. Методы, использующие только значения функции и не требующие вычисления ее производных, называются прямыми методами минимизации.

Большим достоинством прямых методов является то, что от целевой функции не требуется дифференцируемости и, более того, она может быть не задана в аналитическом виде. Единственное, на чем основаны алгоритмы прямых методов минимизации, это возможность определения значений f(x) в заданных точках.

Рассмотрим наиболее распространенные на практике прямые методы поиска точки минимума. Самым слабым требованием на функцию f(x), позволяющим использовать эти методы, является ее унимодальность. Поэтому далее будем считать фу-ию f(x) унимодальной на отрезке [a, b].

Решаются методами: перебора, метод поразрядного поиска, метод деления попалам, метод золотого сечения.

Многошаговые задачи.

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

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