10. Классификация задач нлп:

Классификация задач НЛП.

Классификация приведена на рис.4.

Рис.4.

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

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

В современных системах САПР используются только численные (вычислительные) методы решения, однако они базируются на аналитических методах.

Рис.5.

11.Аналитический способ решения нелинейных задач оптимизации:

Аналитический (классический) способ решения задач НЛП.

Пример 1. Найти безусловный минимум функции:

(3)

Решение:

1. Находим первую производную f’(x).

2. Приравниваем значение первой производной нулю и ищем значения x*, при которых функция имеет экстремум.

3. Ищем вторую производную f’’(x*) и проверяем вид экстремума: если f’’(x*)<0, то в точке x* имеется максимум, если f’’(x*)>0, то в точке x* имеется минимум.

Пример 2. Решить задачу о проектировании бака объемом 2000 л классическим способом.

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

В общем случае, если имеется n параметров и задача оптимизации формулируется следующим образом:

(4)

Решение находят приравнивая нулю n частных производных и решая систему из n уравнений:

(5)

Это есть признак экстремума функции n переменных. По-другому его можно записать следующим образом:

(6)

или:

(7)

Значение выражения будет равно нулю, только при выполнении условий (5), т.е. соблюдения условия экстремума.

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

12.Численные методы решения задач нлп, их классификация:

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

Численные методы используются при решении большинства практических задач оптимизации. Это связано с тем, что для использования классического метода необходимо иметь аналитическое выражение для целевой функции, удовлетворяющее требованиям непрерывности и дифференцируемости. В настоящее время, целевые функции как правило являются сложными, требующими применения численных методов дифференцирования, либо они являются результатом смежного расчета на ЭВМ, выполненного с использованием метода конечных элементов (МКЭ), либо являются результатом эксперимента. Такие функции не удовлетворяют приведенным выше условиям (рис.1.).

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

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

Во-первых, в зависимости от того, как ведется поиск различают методы направленного и ненаправленного поиска. Методы направленного поиска являются пошаговыми (итерационными). Решение находится путем построения серии «шагов» - направленного изменения значения параметров, при этом на каждом шаге решение улучшается. К методам ненаправленного поиска относится например, метод простого перебора (однофакторного или многофакторного эксперимента), золотого сечения, метод Фибоначчи и т.д. Основное достоинство этих методов – простота. Недостаток – большой объем вычислений. Поэтому данные методы применяются при числе независимых переменных в задаче не более 2-х.

Методы направленного поиска используются наиболее широко. Их также можно поделить на несколько групп в зависимости от того, как на каждом шаге выбираются величина шага и его направление. В методах простого поиска или методах нулевого порядка решение о направлении и величине шага принимается на основании расчета значений целевой функции. В градиентных методах или методах первого порядка в расчет принимают значение первой производной целевой функции. В методах второго порядка или в методах Ньютона учитывается значение второй производной. Чем выше порядок метода, тем меньше требуется итераций (шагов) для получения оптимального решения. Однако, по причине, приведенной выше, использование методов порядка выше нулевого является проблематичным. В то же время методы простого поиска демонстрируют более высокую надежность и простоту. К ним относят, например метод покоординатного спуска, симплекс-метод (метод комплексов) и т.д. К градиентным методам, например, относится метод наискорейшего спуска (подъема).

Главное достоинство численных методов – простой учет ограничений и граничных условий.

Главным недостатком численных методов является то, что они позволяют найти лишь локальные оптимумы.