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

В настоящей работе рассматривается метод решения конечномерных оптимизационных задач, формулируемых для комплексов математических моделей (ММ), описывающих функционирование отдельных подсистем этого комплекса ¹ . В прикладной математике задачи данного класса применяются при моделировании экономических, социальных, технических и других систем. Постановка задачи, рассматриваемая в нашей работе, заключается в следующем. Предположим, что необходимо связать в единый комплекс N ММ, для каждой из которых формулируется задача математического программирования (МП): минимизировать по x s Е R n s функцию f s ( x s ) при условиях

V s ( x s ) ^ 0 , i = 1 , m s , s = 1 , N,                                 (1)

где R ^{n s} – евклидово n ^s -мерное пространство ² .

В более краткой записи задача (1) имеет вид fs (xs) ^ ill in ,s = 1 ,N,                                 (2)

xs ∈Gs где Gs = {xs Е Rns : Vs (xs) ^ 0, i = 1, ms}.

Система ММ (СММ) представляет собой объединение N ММ (1), (2), связанных логически для всех моделей условиями (ограничениями) и функцией цели, представляющей собой линейную комбинацию их целевых функций. Математические формулировки СММ могут иметь различный вид [6].

Рассмотрим СММ в виде минимизировать по всем xs Е Gs, s = 1, N,

N

Е “f s ( x s )                                  (3)

s =1

при условиях

N

X ^s Е G s , s = I N E h j ( x s ) C V j , j = VM ; a s >  0 , s = I N s =1

В задаче (3) числа V j , j = 1 ,M , при других постановках могут быть параметрами. Весовые коэффициенты a s в (3) назначаются экспертами; часто a s = 1 , s = 1 , N. Введем вектор x = {x ¹ ,x ² , ...,x ^N } размерности n = m ¹ + m ² + ... + m N и множества G j = {x Е R n : ^ N =i h j ( x ^s ) C V j }, j = 1 , M, тогда задачу (3) можно записать в виде

N

E a s f ^s ( x s ) ^         min  ___ .                       (4)

j =1               x ^s E G s ,x E G ^j ,s =1 ,N,j =1 ,M

Для решения оптимизационной задачи (3) модифицируем ее и задачи (1). Задачи (1) будем рассматривать в виде минимизировать по xs Е Rns функцию fs (xs) при условиях

^j(xs) C 0, i = 1, ms, и hj(xs) C Vs, j = 1, M, s = 1 ,N,(5)

где V _j ^s – параметры, удовлетворяющие условию

N

E vs c vj ,j = 1m.(6)

j =1

Обозначим

Gs = {xs Е Rns : Vs(xs) C 0, i = 1ms; hj(xs) C Vs, j = 1M, s = I?N}.(7)

Тогда задача (5) будет иметь вид fs(xs) ^   ^in .(8)

x s E G s , s =1 ,N

Учитывая (6) и (7), модифицированную задачу (4) представим в виде

N

E asfs(xs) ^ min s=1

при условиях

N x ^s е G j , s = 1 ,N, R j ( V ) = ^E V^s - V j C 0 , j = Tj M. s =1

Условия Rj (V) в (9) - это условия (6). Максимальная размерность вектора параметров V равна (N + 1)M. Как отмечалось ранее, не все Vj могут быть параметрами, некоторые из них могут быть фиксированными числами, и наоборот, в ограничения задачи (1) могут быть также быть введены параметры. Кроме того, возможны и ограничения на Vj . Поэтому будем считать, что размерность вектора V равна некоторому числу L : V Е RL, а размерность вектора R(V) равна числу M, не обязательно совпадающему с (6). Таким образом, задача (9) будет иметь вид

N

£ a s f s ( x s ) s =1

^ min , x ∈ R ⁿ , V ∈ R ^L

где x s E G s , s = 1 ,N, R j ( V ) С 0 ,j = 1 ,M.

Переменными задачи (10) являются векторы x и V ; ее размерность n + L может оказаться большой. Рассмотрим метод ее решения, учитывающий структуру этой задачи.

Предпо лож им, что задача (10) имеет локальное изолированное решение ( x * ^s , s = 1 ,N ; V * ) , а также имеют решения задачи (8) для всех параметров V, т.е. можно рассматривать их решения как функции x * ^s ( V ) . Подставив x * ^s ( V ) в (10), получим

N min ^^ asfs (x*s (V)) по V E RL s=1

при условии

У ( x * s ( V )) С 0 ,i = 1 , m s ; h s ( x * ^s ( V )) С V s ,R j ( V ) С 0 ,j = 1 , M.          (11)

Так как функции x * ^s ( V ) , s = 1 ,N , удовлетворяют ограничениям задачи (11), то из (11) получаем задачу

N min £ as fs(x*s(V)), V E RL и Rj(V) С 0, j = IM,              (12)

s =1

т.е. получили задачу (12) значительно меньшей размерности, чем за дач а (10), особенностью которой является то, что неизвестны вектор-функции x * ^s ( V ) , s = 1 , N.

Функции x * ^s ( V ) , s = 1 ,N , являются негладкими, что затрудняет построение методов решения задачи (12).

Идея предлагаемого метода состоит в замене функций x * ^s ( V ) другими, которые: а) достаточно гладкие;

• б)    достаточно близкие к x * ^s ( V );

• в)    определены ∀ V ∈ R ^L .

Указанным требованиям удовлетворяют решения задач (8), полученные методом гладких штрафных функций (ШФ), [2]. Ограничения задач математического программирования (2) в задаче (5) или (8) обозначим:

■ ₍ s V ) = / ^ i ⁽ x s ) , i = ¹ ’m s ,________________ _____

^ i^ ,       ( h j ( x ^s ) — V j , i = m s + 1 , m s + j, j = 1 , M.

Таким образом, получаем ограничения ^ i ( x s , V ) С 0 , i = 1 , m s , где m s = m s + M, и задача (8) имеет теперь вид

fs (xs) ^ min_, xs∈Gs где Gs = {xs E Rns : ys(xs, V) С 0, i = 1, ms}.

Более краткая по форме запись (13) задачи (8) нужна далее для удобной формулировки метода ее решения.

Метод ШФ для задачи (13) заключается в последовательной безусловной минимизации вспомогательной функции ms

E ^s ( x s , V ) = f ^s ( x s ) + 52 P ( T, y s ( x s , V )) , i =1

где штрафная функция P ( T, X ) определена для всех А и удовлетворяет условию из [3]:

lim P (T, X) = I °, А 5 °, п 4i+0 v 7    [ + то, X > ° причем при некоторых условиях на fs, ϕi, P имеет место равенство lim argminEs(xs,V)= x*s(V).                          (15)

T i +0     X ^s

Можно показать, что xs(T, V) = arg min Es(T, xs, V) обладает всеми указанными выше xs свойствами [2].

Рассмотрим задачу (10) в следующей форме: найти

N min ^ asf s(xs) по x £ Rn, V £ RL(16)

s =1

при условиях ^ s ( x s , V ) <  ° , i = 1 , m s , R j ( V ) <  ° , j = 1 , M.

Вспомогательная функция E ( x, V ) для нее имеет вид

N          MN m

E(x, V) = £ asfs(xs) + £ P(T, R3 (V)) + £ £ P(T, ^s (xs, V)),(17)

s =1              j =1                  s =1 i =1

которую можно переписать также в виде

N          M             Nm

E(x, V) = £ asfs(xs) + £ P(T, Rj (V)) + £ as £ P(T, ^s(xs, V)).(18)

s=1             j=1                 s=1

Множитель a s >  ° , введенный в третье слагаемое, не изменит свойств ШФ. Напомним, что вектор x в E ( x,V ) равен x = {x ¹ , x ² , ...,x ^N } . Используя (14), из (18) получим более краткую форму представления E ( x,V ) :

N

E ( x,V ) = W ( T,V ) + ^ a ^s E ^s ( x s , V ) ,                     (19)

s =1

где W ( T, V ) = £ M =1 P ( T,R j ( V )) .

Приближенные значения оптимального решения x ^∗ ,V ^∗ задачи (10) можно найти, решив задачу безусловной минимизации (БМ):

min E ( x,V ) ,x £ R ⁿ ,V £ R L ,                          (20)

однако мы предложим другой метод ее решения.

При решении N задач БМ: найти min E s ( x s , V ) получаем решения x s ( T, V ) , s = 1 , N. x ^s ∈ R ^ns

Подставляя x s ( T, V ) в (19), получим функцию от переменной V :

N

E ( x, V ) = W ( T, V ) + ^ a ^s E ^s ( x s ( T, V ) , V ) ,                    (21)

s =1

где x = ( x ¹ ( T, V ) ,x ² ( T,V ) , ...,x N ( T,V_ )) .

Решение задачи БМ: найти min E(x, V) при некоторых условиях, накладываемых на fs, ^s, P, [3] обладает следующим свойством: lim arg min E(x, V) = V*, где V* — компонента оптимального решения (x*, V*) задачи (10).

Итерационная схема решения задачи (10) методом ШФ.

• 1)    Пусть задан начальный вектор V q G R L .

• 2)    Для к = 0 , 1 , 2 ,... находим приближение V k :

V k +i = V k + t k W k , где W k — вектор направления убывания функции E ( x ( V ) , V ) в точке V k ; t k — шаг по направлению W k .

• 3)    Проверка условия окончания метода для функции E ( x ( V ) , V ) в точке V = V k . Если условие выполнено - stop , не выполнено - к ^ к + 1 и переходим к пункту 2.

Замечание

• 1)    Условие остановки метода ШФ для решения задач min E ^s ( x s , V ) , x s G R n s , и задачи (20) следующие:

• а)    выбирается достаточно малое значение коэффициента штрафа Т _mi_n ;

• б)    значения градиентов на k -м шаге целевых функций должны быть достаточно малы:

  ∂E ^s ∂x ^s

  
  

  ^ е, s = 1 ,N ; x ^s = x k

  
  

  ∂E ∂V

  
  

  < Е. v = V k

  
  

• 2)    В качестве штрафной функции P ( Т, а ) могут быть взяты, например, функции Тет или ^^а2 T 4 + ^а . Помимо бесконечной дифференцируемости по а и Т >  0 , эти функции, как показано в [3], обеспечивают погрешность решения задач порядка малости T. Причем вторая из них, как показывает опыт решения тестовых задач, более удобна, поскольку сходимость численных методов может нарушаться из-за ограниченности области допустимых значений аргумента экспоненты.

Как указывалось выше, функция P ( Т,Х ) - гладкая, поэтому для применения метода ШФ необходимо знать значения grad v E ( x ( V ) , V ) = dV и матрицу вторых производных { dV dV - } , r,j = 1 , S. Дифференцируя сложную функцию ( x ( V ) , V ) по V, получим

∂E ∂E ∂ x ∂E

∂V

dV ⁺ dV ' dx

_ dE ^U dxs dE = dv +   dV ‘ dxs, s=1

s где dv , s = 1 ,N — матрицы составлена из N матриц ∂∂Vx s .

∂E

∂V r

∂E ^{N n} ∂E ∂ x ^s

= dV r ⁺^ ^ dx f ’ dV r ,r = , .

s =1 i =1 ⁱ

Так как grad xs Es (T,xs,V) = 'Ж- | x=xs = 0, то из (22) (или (23)) получим dE dE

dV = dV, т.е. для вычисления первых производных от вспомогательной функции (T,xs (V), V) не требуются значения матриц чувствительности dV-, s = 1, N.

Продифференцируем dE по V j , r,j = 1 , L :

d ² E _ d ² E I ^V N ^V n s d ² E dV _r dV j = dV r dV j ⁺ 2^ s =1 Z^i =1 dV r dx s

I ^V N ^V ns ^dx s / ⁺ Z^s =1 Z^i =1 dV

∂ ² E

∂x _i ^s ∂V r

, V n s    d ² E , dx s

⁺ j =1 =1 dx S dx s dV j .

dx S I ^V N ^V n s dE   d ² x S ,

’ dV j ⁺ S =i =1 Z^i =1 dx s ‘ dV _r dV j ⁺

Так как ddE = 0 , s = 1 , N, то третье слагаемое в (24) равно нулю. Продифференцируем Es = 0 , s = 1 ,N , по V j , получим

Е + £     .j = 0,s = 1N,j =iS.(26)

∂Vj∂xs      ∂xs∂xs ∂Vj i     j = 1

Таким образом, и четвертое слагаемое в (26) равно нулю. Из (25) в итоге получим

• a ² e = a ² e + А ^Л d ² e dx s

dVr dVj dVr dVj + ^ ^ dVr dxs dVj ’ s—1 i—1

где для вычисления dVly j надо знать N матриц чувствительности dx ^ , значения которых определяются из системы уравнений (26). Итак, имея в своем распоряжении формулы (24) и (27), можно для решения задач БМ найти:

min Е ^s ( x ^s , V ) , x ^s € R n , s = 1 ,N ;

min E ( X, V ) , V € R L , (29) применять численные методы 1-го и 2-го порядков и тем самым находить приближенные значения согласующих параметров V j , j = 1 , L и соответствующие им значения X ^s , s = 1 ,N , и f ^s ( X ^s ) и Е s = a s f ^s ( X ^s ) .

Отметим также одну важную специфику решения задачи (29). Дело в том, что процедура поиска минимума состоит из поиска направления W k движения к минимуму в пространстве R ^L и выбора величины шага t k по этому направлению. Использование стандартных алгоритмов оценки величины шага может потребовать затрат больших вычислительных ресурсов, поскольку для каждой пробной точки в R ^L потребуется решать N задач (28). Это следует обязательно учитывать, т.к. процедуры выбора шага t _k и построения направления W k могут быть зависимыми. Одним из способов решения указанной проблемы является выбор такого метода решения задачи БМ (29), в котором число пробных шагов для выбора t k невелико. К таким методам относится метод Ньютона, у которого в его области сходимости t k = 1 .

Чувствительность оптимальных решений для систем ММ

Под чувствительностью решений ММ обычно понимают скорость измерения исследуемой функции в зависимости от значения параметров модели [4]. В нашем случае – это dxs (V)          , v • ё     dfs (Xs (V))               д EN- aSsfs (Xs (V)) • ғ производные dVj ', s = 1 ,N, j = 1 ,S, и J d)Vj^ ", а также     s-1 dV, v v ", j = 1 ,S.

Для определения матрицы чувствительности ^dx djVV ⁾ , s = 1 , N, j = 1 , S , необходимо решить систему линейных уравнений ЛУ (26).

Очевидно, значение dfs(Xs(V)) = .n^ dfs(Xs). dxss (V) j = ∂Vj              ∂xi      ∂Vj ,       ,

i —1

f ^s ( X ^s )                                        , ,                                                    dx ^s ( V )

В (23) значение _{∂E i} находится прямым дифференцированием, а значения _{∂V j} берутся из решения систем ЛУ (26).

Значение производной (чувствительности) целевой функции составной ММ очевидно равно линейной комбинации производных N функций f ^s ( X ^s ) :

а Е ^ =1 a s f ^s ( X ^s ( V )) = Л г df s ( X ^s ) ^ dX s ( V ) j

∂V j                          ∂x i        ∂V j ^{,       , .}

s —1 i —1

Наше определение чувствительности решений (ЧР) является частным случаем ЧР, рассматриваемой в [5].

Для иллюстрации практического использования описанного подхода приведем пример. Необходимо связать в одну систему следующие ММ.

Модель 1. Минимизировать ( — 3 x 1 — x 2 ) при условиях:		(32)
	0 ^ x 4 ^ 2; 0 ^ x 2 ^ 4 , 2 x 4 + x 2 ^ V l , x 1 + x 2 <  V > •
Модель	2. Минимизировать (2 x 2 — x 2 ) при условиях:
	0 <  x 2 <  3; 0 <  x 2 <  3 , x 2 + 4 x 2 <  V 3 , x 2 + x 2 <  V 4 •	(33)
Модель	3. Минимизировать ( — 2 x 3 — 3 x 2 ) при условиях:
	0 ^ x 3 ^ 5; 0 ^ x 2 ^ 3 , 3 x 3 + x 2 <  V 5 , x 2 + x 2 <  V 6 •	(34)

Модель 4. Минимизировать ( x⁴ — 2 x 2 ) при условиях:

0 ^ x⁴ ^ 4; 0 ^ x 2 ^ 5 ,

2 x 4 + 3 x 2 ^ V 7 ,                                         (35)

x 4 + x 2 ^ V 8 •

Модели 1, 2, 3, 4 сформулированы в виде задачи (5).

Составная модель имеет вид min(—3 x1 — x 2 + 2 x4 — x 2 — 2 x 4 — 3 x 2 + x4 — 2 x 2)

при условиях на x S , s = 1 , 4 , i = 1 , 2 , удовлетворяющих (30) - (34) и условию

^ V j ^ 19 •                                (36)

j =1

Штрафная функция P ( T, a ) = ^ ^a 2 + T 4 + ^a и T min = 0 , 01 •

Для решения задач БМ был применен метод Ньютона. Решение было получено на 9-й итерации. Согласно оценкам из [2], погрешность решения составила 2%. Приведем решение задачи (36) в табл. 1.

Итоговое решение

Общее число выполненных итераций: 9.

Общая вспомогательная функция : –19,10.

Норма вектора направления : 2 , 10 e 6 .

Величина шага по направлению : 0.

Таблица1

Модель	1	2	3	4
Значения пере-	1,00	0	0	0
менных x i s	0	0,30	1,83	0,5
Целевая функция	3	0,30	5,50	1,00
Вспомогательная функция	–3,01	–0,33	–5,55	–1,03
Согласующие па-	2,00	1,20	1,83	1,50
раметры V j	1,00	1,00	1,83	1,00
Вектор направле-	0,23	0,03	0,23	0,14
ния	0,12	0	0,23	0

Заключение

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