Нелинейные оптимизационные модели

8. НЕЛИНЕЙНЫЕ ОПТИМИЗАЦИОННЫЕ МОДЕЛИ

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

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

При этом возможны задачи, в которых  ограничений на область значений переменных нет, и задачи, в которых область значений переменных ограничена.

Задачи без ограничений.

Решение такой задачи читателю знакомо из курса дифференциального исчисления, поэтому ограничимся кратким напоминанием.

Пусть max(min) z = f(x₁, x₂, … , x_n) – целевая функция.

В точке экстремума функции z её первые производные, если они существуют, равны нулю. Найдем производные z по всем переменным и приравняем их нулю. Получим систему n уравнений с неизвестными x₁, x₂, … , x_n

=0, =0, … , =0.                  (8.1)

В случае выпуклой или вогнутой функции (см. ниже) решение этой системы уравнений сразу укажет точку x₁, x₂, … , x_n экстремума функции. В более сложных случаях необходимо выполнить исследование на отсутствие в найденной точке минимакса функции z, то есть такого положения, что относительно одних x_i функция имеет максимум, а относительно других – минимум.

Задачи с ограничениями.

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

Запишем  задачу математического программирования в общем виде

max (min) z =  f();                                                                                               (8.2)

                                                                                                            (8.3)

i₁ = 1, 2, … , m₁;   i₂ = m₁ +1, m₁+2, … , m₂;   i₃ = m₂ +1, m₂+2, … , m;

j = 1, 2, … , n;

 = (x₁, x₂, … , x_n)

Если целевая функция (8.2) или ограничения (8.3) нелинейны, то задача называется задачей нелинейного программирования.

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

Функцию f(x) называют выпуклой, если для любых точек  и справедливо неравенство

.

Функцию f(x) называют вогнутой, если для любых точек  и справедливо неравенство

.

Иначе говоря, выпуклая функция - такая, у которой все точки отрезка, соединяющего две ее точки, лежат выше точек функции. У вогнутой функции все точки такого отрезка лежат ниже точек функции.

Двухмерный случай иллюстрируется рисунком, где в варианте а) показана выпуклая, а в варианте б) – вогнутая функция.

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

В качестве основной в теории выпуклого программирования рассматривают задачу минимизации выпуклой функции n переменных z = f() при ограничениях  (i = 1, 2, … ,m), ,где функции  предполагаются выпуклыми.

Если f() и   являются вогнутыми функциями, то имеем задачу максимизации f() при ограничениях  (i = 1, 2, … ,m), .

8.2. Коррелатное уравнивание результатов геодезических измерений – задача выпуклого программирования

Целью уравнивания измерений является минимизация целевой функции

min z = p₁v₁² + p₂v₂² + … + p_nv_n²  где p_i – веса и v_i – поправки к результатам измерений (i = 1, 2, … , n). Поправки должны соответствовать ограничениям – условным уравнениям:

a₁₁v₁ + a₁₂v₂ + … + a_1nv_n + w₁ = 0,

a₂₁v₁ + a₂₂v₂ + … + a_2nv_n + w₂ = 0,

…………………………………...

a_m1v₁ + a_m2v₂ + … + a_mnv_n + w_m = 0.

Имеем выпуклую целевую функцию с линейными ограничениями.

Перепишем систему условных уравнений в матричной форме

AV + W = 0,                                                                                                     (8.4)

где А – матрица коэффициентов, V – вектор поправок и W – вектор свободных членов.

Составим функцию Лагранжа, введя вспомогательные множители – коррелаты:

L = p₁v₁² + p₂v₂² + … + p_nv_n²  + 2 l₁(w₁ - a₁₁v₁ - a₁₂v₂ - … - a_1nv_n) +

+ 2 l₂(w₂ - a₂₁v₁ - a₂₂v₂ - … - a_2nv_n) +

……………………………………….

+ 2 l_m(w _m - a _{m 1}v₁ - a _{m 2}v₂ - … - a _{m n}v_n).

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

2 (p₁v₁ - l₁a₁₁ - l₂a₂₁- … - l_ma_m1) = 0

2 (p₂v₂ - l₁a₁₂ - l₂a₂₂- … - l_ma_m2) = 0

……………………………………………

2 (p_nv_n - l₁a_1n - l₂a_2n- … - l_ma_mn) = 0

Полученную систему уравнений для сокращения последующих записей также перепишем в матричном виде:

PV - A^ТL = 0.                                                                                                  (8.5)

Из (8.5) находим

V = P^-1A^ТL.                                                                                                     (8.6)

и подставим полученное выражение для вектора поправок в условное уравнение (8.4). Получаем систему нормальных уравнений

A P^-1A^ТL + W = 0.                                                                                            (8.7)

Получили известные формулы коррелатного метода уравнивания.

Поправки к результатам измерений, минимизирующие целевую функцию, находим в следующем порядке. Решением нормальных уравнений (8.7) определяем вектор коррелат L. Подставляя коррелаты в (8.6), вычисляем вектор поправок к результатам измерений.