Методы условной оптимизации диспетчерского управления восстановлением и модернизацией летательных аппаратов

словной оптимизации, в которой фигурируют некоторые неизвестные параметры, называемые множителями Лагранжа.

Рассмотрим задачу с одним ограничением-неравенством:

f(x) ^ min , x G R" ,

h 1 (x) = 0 .

В соответствии с методом множителей Лагранжа эта задача преобразуется в следующую задачу безусловной минимизации:

L(x; X) = f(x)-Xh 1 (x) ^ min , x G R " .                                   (3)

Функция L ( x ;X) называется функцией Лагранжа. Здесь X - множитель Лагранжа.

Тогда при заданном значении Х=Х⁰ безусловный минимум функции L ( x ;X) по переменной x достигается в точке x=x⁰ и х⁰ удовлетворяет уравнению h 1 ( x ⁰)=0.

Необходимо подобрать значение Х=Х⁰ таким образом, чтобы координата точки безусловного минимума x⁰ удовлетворяла равенству (2). Это можно сделать, если, рассматривая X как переменную, найти безусловный минимум функции Лагранжа (3) в виде функции λ, а затем выбрать значение λ, при котором выполняется равенство (2).

Метод множителей Лагранжа можно распространить на случай, когда задача имеет несколько ограничений в виде равенств:

f(x) ^ min , x G Rⁿ ,                                            (4)

h_k(x) = 0 , k=1,2, .... K.

к

Функция Лагранжа принимает вид L(x;X) = f(x)- 2^ X _k h _k .

k=1

В этом случае Х 1 ,...,Х_К - множители Лагранжа, т.е. неизвестные параметры, значения которых нужно определить [2]. Приравнивая частные производные L по x нулю, получаем следующую систему:

дL(х, X) _ дL(х, X)

дх 1

9 x ₂

ЭL(x, X) = ₀

^{9 x} n         '

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

^h 1 ⁽x) = ⁰ , ^h 2 ⁽x) = ⁰ , ^, h k ⁽x) = ⁰ .                                    (7)

Решение расширенной системы, состоящей из N+K уравнений с N+K неизвестными, определяет стационарную точку функции L . Затем реализуется процедура проверки на минимум или максимум, которая проводится на основе вычисления элементов матрицы Гессе функции Лагранжа, рассматриваемой как функция от x .

Рассмотрим задачу с ограничениями в виде неравенств:

/(х) ^ min , х G R", с ограничениями-неравенствами:

S , (^x) — °, j=l>²> —> J •                                                    (9)

Пусть область (9) (обозначим ее D ) - не пустое, ограниченное замкнутое множество. Функция Лагранжа для задачи (8) с ограничениями (9) определяется формулой

L(x; X) = f(x)- Ь X j g j (x) = f(x)- X^Tg(x),                       (10)

'j 1

где X - вектор множителей Лагранжа: X = (X , ,...,X j )^T , g = (g , ,...,g j )^T .

В точке локального минимума задачи (8), (9) каждое из ограничений (9) выполняется либо в виде равенства g j ( х )=0, либо в виде неравенства g j ( х )<0. Ограничения первого вида называются активными ограничениями. Остальные ограничения – неактивные ограничения.

Если точка X * С D и ограничения g jk ⁽ x * )<0, ^„„ssJактивны, то условие линейной независимости градиентов функций g_jk ( х*),j_k=1,,,s,sактивных ограничений в точке х* называется условием регулярности ограничивающих функций в точке х*. Это условие означает, что, например, при n=2 количество ограничивающих функций, проходящих через точку x^*, не должно превышать 2 и в точке х*векторы ^g,(x),^g₂(x) не должны быть коллинеарны [3].

Большое значение в теории и вычислительной практике имеет следующая теорема Куна-Таккера для задачи условной оптимизации с ограничениями типа неравенств.

Пусть функция /(х) и функция gj(х*)<0, j=1,2,,,J имеют непрерывные частные производные в некоторой окрестности точки х*, и пусть эта точка является точкой локального минимума функции /(х) при ограничениях gj(х )<0, удовлетворяющих в точке х условию регулярности ограничивающих функций. Тогда существуют такие неотрицательные множители Лагранжа Xb,;Xj, что для функции Лагранжа L(х;X) точка х* является стационарной точкой, т.е.VxL(x;X) = Vf(x)- 2XjVgjfx) = 0.

j - 1

Своеобразным и очень эффективным методом оптимизации признан метод факторов (или множителей), который основан на санкции типа «квадрат срезки» для ограничений-неравенств [2].

Такая санкция определяется следующим образом:

S = R^g(x)² ,                                                      (11)

где срезка t определяется так:

_ Г ^t, если t > 0,                                                         /1оч

^^C? 10, если t < 0.                                                             ⁽ )

Эта санкция внешняя и стационарные точки функции Q(x,R) могут оказаться недопустимыми. С другой стороны, недопустимые точки не создают в данном случае дополнительных сложностей по сравнению с допустимыми. Различие между ними состоит лишь в том, что в допустимых точках санкция равна нулю.

В методе факторов на каждой итерации производится безусловная минимизация функции

Q (x , O , T ) = f (x ) + R

2 {( g j (x ) + ст j У - ст ² } + R E ^{[ h k (x ) + т ] ² j = 1                                               k = 1

+ ^T k } ,

где R - постоянный весовой коэффициент, а угловые скобки обозначают операцию срезки. Параметры (факторы) о , и т_к осуществляют сдвиг санкционных слагаемых. Компоненты векторов σ и τ меняются по ходу вычислений, однако в процессе решения каждой вспомогательной безусловной задачи оба эти вектора остаются постоянными. Начальные значения факторов о и т можно выбрать нулевыми. Обозначим через x m точку минимума функции Q ( x , о m , т m ), используемой на m –й итерации.

При переходе к (m+1)– й итерации факторы пересчитываются по формулам

σ^m_j ^{+ 1} = g_j(x^m) + σ^m_j , j=1,…,J, τ^m_j ^{+ 1} = h_k(x^m) + τ_k^m , k=1,…,K.

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

Для контроля сходимости метода используют последовательности x^m, σ^m, τ^m, f(x^m), g(x^m), h(x^m) . Прекращение основного процесса происходит, когда члены по крайней мере одной из этих последовательностей перестают изменяться при пересчете факторов и последующей безусловной минимизации. Заметим, что величина положительного параметра R влияет на свойства метода, но конструктивного алгоритма его выбора не существует.

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

Построение адекватной математической модели для оптимизации загрузки системы диспетчерского управления восстановлением и модернизацией летательных аппаратов на авиационном ремонтном предприятии может быть осуществлено как комплекс задач с ограничениями в виде равенства и в виде неравенств [1].