Стабильность неопределённых задач оптимизации

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

Известно три различных подхода к решению недетерминированных задач математического программирования: детерминированный, вероятностный [1] и интервальный [2]. Детерминированный подход заключается в решении задачи для определенных значений ее параметров, выбранных внутри заданных областей неопределенности. Вероятностный подход состоит в решении задачи для усредненных (ожидаемых, в смысле математического ожидания) значений ее параметров, что предполагает задание вероятностной меры внутри их областей неопределенности. Оба указанных подхода объединяет предварительная детерминизация параметров задачи, выполняемая перед ее оптимальным решением. В отличие от них, интервальный подход не предполагает никакой детерминизации параметров, которые задаются в ин- тервальной форме. В данном подходе оптимальное решение задачи проводится на основе прямого сравнения недетерминированных значений целевой функции, соответствующих различным значениям вектора аргументов, и выбора оптимального значения данной функции. Достоинства и недостатки указанных подходов рассмотрены в [1-8]. Соответствующий краткий обзор дан в работе [9].

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

1    Постановка задачи

В процессе постановки настоящей задачи мы отталкиваемся от постановки задачи в нашей работе [9].

Пусть задана некоторая непрерывная функция n вещественных переменных

• ⁽¹⁾                                   y — F ⁽ x 1 ,..., x n ),

где параметры (коэффициенты) ее явного представления P k , к — 1, l , известны точно. Будем рассматривать функцию (1) в ограниченной области, определяемой системой ограничений

• (2)                                      Ф i ( x i ,..., X n ) <  b i , i — 1, m } ,

имеющей точные параметры q s , s — 1, t , явного представления функций ограничений Ф i и правые части b i . Тогда относительно функции (1) можно сформулировать полностью определенную задачу условной оптимизации (математического программирования)

• (3)                                   F ( X 1 ,..., x n ) — max,

при условии

• (4)                                      Ф i ( X 1 ,..., X n ) <  b i , i — 1, m } .

Теперь предположим, что в задаче оптимизации (3), (4) параметры явного представления целевой функции F и функций ограничений Ф i , а также правые части ограничений b i известны не точно, а приближенно. Тогда, в соответствии со сказанным в Ведении, мы должны вместе с задачей условной оптимизации (3), (4) рассматривать еще задачу проверки устойчивости решения задачи (3), (4) относительно небольших изменений ее параметров.

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

Итак, совместно с полностью определенной задачей (3), (4) мы должны рассмотреть производную от нее интервальную задачу условной оптимизации

• (5)                                   F ( x 1 ,..., x n ) = max,

при условии

• (6)                                      Ф i ( x 1 ,..., x n ) <  b i , i = 1, m } .

Целевая функция F интервальной задачи оптимизации (5), (6) получается из целевой функции F искомой, полностью определенной задачи оптимизации (3), (4) путем замены ее точных параметров P k , к = 1, l , соответствующими интервальными параметрами Pk = [ P k 1 , P k 2 ], к = 1, l . Аналогично, любая функция ограничений Ф i , i = 1, m , интервальной задачи (5), (6) получается из соответствующей функции Ф i , i = 1, m , исходной полностью определенной задачи (3), (4) заменой ее точно известных параметров q_si , s = 1, t , i = 1, m , соответствующими интервальными параметрами р si = [ q si 1 , q_{si 2}], s = 1, t , i = 1, m . Так же интервальные параметры bpi = 1, m , в ограничениях интервальной задачи (5), (6) заменяют собой соответствующие точно известные параметры b i ,i = 1, m в ограничениях исходной, детерминированной задачи оптимизации (3), (4).

Будем называть полностью определенную задачу условной оптимизации (математического программирования) (3), (4) макроустойчивой, если она имеет решение и, кроме того, имеет решение производная от нее интервальная задача оптимизации (5), (6).

Далее, будем называть полностью определенную задачу условной оптимизации (математического программирования) (3), (4) микроустойчивой, если она макроустойчива и, сверх того, существует пара решений ( x ‘ , x ") , где x' = ( x J ,..., x'_n ) - некоторая точка решения задачи оптимизации (3), (4), а x" = ( x 1' ,..., x П ) - некоторая точка решения задачи (5), (6), расстояние между которыми D ( x' , x" ) не превосходит заданной достаточно малой величины d . Задача настоящего исследования - разработать алгоритмы определения макро- и микроустойчивости полностью определенных задач условной оптимизации типа (3), (4).

2    Математический аппарат

В основу решения поставленной задачи положим аппарат интервальной математики [10], где алгебраические операции над интервальными числами ^р = [ a 1 ,a ₂ ], b = [ b 1 , b ₂ ] ,... вводятся как следующие теоретико-множественные конструкции P              P P              P

• (7)    a + b = { a + b | a e a , b e b }, a - b = { a - b | a e a , b e b }, ka = { ka | a e a } ,...

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

^[ a i , a ₂] + ^[ b i , b ₂] = ^[ a i + b i , a 2 + b ₂],

[ a 1 , a 2 ] - [ b y , b 2 ] = [ a i - b 2 , a 2 - b i ];

• f [ ka_A , ka^ ], k >  0,

k [ a ,, a ₂ ] =       ^{1    2}

• ^{1    2}      [ [ ka ₂, ka _i], k <  0;

[ a i , a 2 ] • [ b i , b 2 ] = [min( a i • b j ),max( a i • b j )];

i 2 i 2 _{i , j} i j _{i , j} i j

[ a i , a 2 ]/[ b i , b 2 ] = [ a i - a 2 ] • [i/ b 2,H b i ]-

Введем теперь операции сравнения интервальных чисел. Единственное разумное здесь, согласно [2, 8, i0] - реализовать операцию сравнения интервалов на теоретико-множественном уровне, подобно алгебраическим операциям над интервалами (7). Так, введем операции взятия максимума v и минимума л интервальных чисел ~ = [ a_i , a ₂] и b = [ b_i,b ₂] в виде конструкций

~                     ~.       ~                     ~.

• (9)                 a v b = { a v b | a e a , b e b }, a л b = { a л b | a e a , b e b } .

Свойства введенных операций сравнения интервальных чисел (9) определяются нижеследующими теоремами (подробнее см. [2, 8, i0]).

Теорема 1. Для сравнимости двух интервалов ~ = [ a _i , a ₂ ] и b = [ b _i, b ₂] и их нахождения между собой в отношении ~ >  b необходимо и достаточно, чтобы одноименные границы этих интервалов удовлетворяли условиям

• (i0)                                 a _i > b _i , a ₂ >  b ₂ ,

а для сравнимости этих интервалов и их нахождения между собой в отношении ~ <  b - чтобы удовлетворялись следующие условия:

• ^{(ii)                                 a} i <  b i , ^a 2 <  ^b 2 -

• Теорема 2. Для несравнимости двух интервалов ~ = [ai,a2] и b = [bi,b2], т.е. для того, чтобы они не находились ни в отношении ~ > b , ни в отношении ~ < b , необходимо и достаточно, чтобы одноименные границы интервалов удовлетворяли условиям

• (i2)                         a _i <  b _i , a ₂ >  b ₂ или b _i <  a _i , b ₂ >  a ₂ .

Теорема 3. Для существования в системе интервалов ~(i) = [ a _i(i), a ₂(i)], ~(2) = [ a _i(2), a ₂(2)],... максимального интервала необходимо и достаточно, чтобы его границы располагались относительно одноименных границ всех остальных интервалов согласно следующим условиям

• (i3)                  a _i (i) >  a _i (2), a _i (i) >  a _i (3),...; a ₂ (i) >  a ₂ (2), a ₂ (i) >  a ₂ (3),...

Условия-неравенства (13) записаны для конкретного случая, когда максимальным является интервал ~(i), что не ограничивает общности.

Теорема 4. Для существования в системе интервалов й(1) = [ a _i(i), a ₂(i)], ~(2) = [ a _i(2), a ₂(2)],... минимального интервала необходимо и достаточно, чтобы его границы были расположены относительно одноименных границ всех остальных интервалов согласно условиям

• (i4)                  a i (i) <  a i (2), a i (i) <  a i (3),...; a 2 (i) <  a 2 (2), a 2 (i) <  a 2 (3),...

Условия (14), аналогично условиям (13), записаны для случая, когда минимальным является интервал ~(i), что не ограничивает общности.

Теоремы 1-4 примечательны тем, что сводят сравнение интервальных чисел к сравнению границ соответствующих интервалов.

3 Макроустойчивость задачи условной оптимизации

Обратимся к полностью определенной задаче условной оптимизации (3), (4) и опишем метод установления макроустойчивости этой задачи. Задача (3), (4) по определению (см. раздел 1) является макроустойчивой, если она сама и производная от нее интервальная задача условной оптимизации (5), (6) имеют решения. Существование решения полностью определенной задачи условной оптимизации (3), (4) обычно можно установить с помощью общеизвестных методов решения задач математического программирования, решая соответствующую задачу [11-13]. Сложнее обстоит дело с проверкой существования решения неполностью определенной (интервальной) задачи условной оптимизации (5), (6). Здесь эффективным оказывается применение детерминизационного метода решения задач интервальной оптимизации [2, 8, 14].

Интервальная задача условной оптимизации (5), (6) имеет интервальную целевую функ-

—, цию F ( X 1,

...

—

, xn), интервальные функции ограничений Ф i, 1, m, в левых частях ограничений и интервальные параметры bi, i = 1, m, в правых частях. Используя формулы элементарных преобразований интервалов (8), функции F и Фi можно представить явно в интервальной форме. Так же можно представить и параметры bi. Все эти представления записываются в виде

— , F ( x 1 ,.

—

^Ф i ^{( X} 1

—

...,

^xn ) = ^{[ F} 1^{( x}1 ^,...^{, x}n ), ^F 2^{( x}1 ^,...^{, X}n ^)] ,

,...,

x n ) = ^[Ф i 1^{( X} 1

,...,

x n ), Ф i 2^{( X} 1

,...,

bi = ^[ bH, bi 2^] ,

X n )], i = 1, m , i = 1, m .

Алгоритм получения представлений (15) покажем на примере одной достаточно общей задачи оптимизации типа (5), (6).

Пример 1. Рассмотрим сначала частный случай общей интервальной задачи условной оптимизации (5), (6) - интервальную задачу линейного программирования:

■—'

■—'

c 1 x 1 + ... + c_nx_n = max,

— 1 x 1 + ... + ^— _inx_n <  b i , i = 1, m , x 1 >  0,

...

, x_n >  0.

_          _       ---- ^,     _            _      ----- ---- — cj =[cj 1,cj2],j = 1,n; aij =[aij,1,aij,2],i = 1,m,j = 1,n;   b =[bi,bi-2].

—

Здесь интервальная целевая функция F ( X 1 ,

...

, x_n ) = c 1 x 1 + ... + c_nx_n , интервальные функции

— ограничений Ф i ( x 1 ,

I ...

—

, x_n ) = a_iXx 1 + ... + a_inx_n , i = 1, m , и наконец, интервальные параметры b i в

—

—■ —

правых частях ограничений: b i = [ b i 1 , b i ₂]. Подставляя в выражения F , Ф i параметры — j , a ij в явной форме интервалов и умножая эти интервалы на неотрицательные переменные

X 1 ,...

, x_n , согласно формуле (8), получим необходимые явные интервальные представления

вида (15) для рассматриваемой нами задачи линейного программирования

— , F ( X 1 ,.

—

^Ф i ^{( X} 1

—

...,

x n ) = ^[ F 1 ^{( X} 1

,...,

x n ) = ^—11 ^X 1 + - + ^— n 1 x n , F 2^{( X} 1

,..., ^Xn ) ^[Ф i 1^{( x} 1 ,...,

,...,

= c 12 x 1 + ... + c n 2 x n ],

^Xn ) = ^— i 1,1 ^X 1 ⁺ ... ^{+ —} in ,1 ^Xn , ^Ф i 2 ^{( X} 1

,...,

^Xn ) = ^— i 1,2 ^x 1 ⁺ ... ^{+ —} in ,2 ^Xn 1» i = ^{1 m} ,

bi = ^[ bi 1 , bi 2^] , i = ¹ m .

Учитывая полученные представления (15), всю интервальную задачу (5), (6) также можно записать в явном интервальном виде

[ F 1 ( X 1 ,..., X n ), F 2 ( X 1 ,

...

, X n )] = max,

^[Ф i 1^{( x} 1 ^,...^{, x} n X Ф i 2^{( X} 1

,...,

x n ^)] <  ^[ b i 1 , b i 2^] , i = ¹ m ^} .

Согласно представлению (16), (17), задача (5), (6) заключается в том, чтобы найти максимум интервальной функции в области, ограниченной системой интервальных неравенств.

От интервального представления задачи (16), (17) перейдем к ее эквивалентному представлению в виде пары полностью определенных (детерминированных) задач условной оптимизации, которое уже поддается решению. Для этого сначала по теореме 3 представим интервальное уравнение (16) в виде эквивалентной пары детерминированных уравнений

• (18)                F₁( x ! ,..., x n ) = max, F ₂ ( x ₁ ,..., x n ) = max.

Далее, по теореме 1 представим систему интервальных неравенств (17) в виде эквивалентной системы обычных детерминированных неравенств

• ⁽¹⁹⁾                  Ф i i ⁽ x i ,..., x n ) <  b ^ Ф i 2 ⁽ x i ,..., x n ) <  b i 2 ,   i = ¹ m .

Соединив пару уравнений оптимизации (18) с системой неравенств-ограничений (19), получаем совокупность двух полностью определенных задач условной оптимизации вида (3), (4)

F ₁ ( x₁ ,..., x _n ) = max,

• ⁽²⁰⁾                            Ф ii ( x i ,..., x n ) <  b i 1 , i = 1, m , ,

Ф i2 ( x 1 ,..., x n ) <  b i 2 , i = 1, m ,

F ₂ ( x ₁ ,..., x _n ) = max,

• ⁽²¹⁾                            Ф i1 ( x 1 ,..., x n ) <  b i, i = 1, m , ,

Фi2 (x1,..., xn) < bi2, i = 1, m, эквивалентную исходной интервальной задаче условной оптимизации (5), (6). Задачу (20) будем называть нижней граничной задачей интервальной задачи (5), (6), а задачу (21) - ее верхней граничной задачей. Для получения решения интервальной задачи (5), (6) нам нужно решить ее нижнюю (20) и верхнюю (21) граничные задачи. В общем случае решение нижней граничной задачи имеет вид {Mн (x), F[,max}, а верхней граничной задачи - вид {Mв (x), F2,max}.

При этом M _н ( x ), M _в ( x ) - множества точек решения x = ( x 1 ,..., x n ) нижней и верхней граничных задач, а F_{1 max} , F _{2 max} - полученные максимальные значения целевых функций этих задач. Решение интервальной задачи оптимизации (5), (6) формируется из решений ее нижней и верхней граничных задач и имеет вид

• (22)    { x * е M н (. x ) A M _в (. x ); T ?max = [ F lmax , F ^max l } .

Согласно (22), в качестве точки решения x ^* интервальной задачи оптимизации (5), (6) выбирается любая точка из пересечения множеств точек решения ее нижней и верхней граничных задач, а в качестве максимального значения интервальной целевой функции F _max - интервал от максимального значения целевой функции нижней граничной задачи F _1,max до максимального значения целевой функции верхней граничной задачи F _2,max .

Из выполненного процесса построения решения интервальной задачи вида (5), (6) и определения макроустойчивости полностью определенной задачи условной оптимизации (3), (4) вытекает следующая основная теорема.

Теорема 5. Для того чтобы полностью определенная задача условной оптимизации (3), (4) была макроустойчива, необходимо и достаточно, чтобы: 1) она имела решение; 2) интер- вальная задача оптимизации (5), (6), производная от задачи (3), (4), имела нижнюю и верхнюю граничные задачи, обладающие решениями; 3) множества решений нижней граничной задачи и верхней граничной задачи интервальной задачи оптимизации (5), (6) пересекались.

Доказательство теоремы 5 содержится непосредственно в полученном общем решении (22) интервальной задачи условной оптимизации (5), (6), при учете определения макроустойчивости полностью определенной задачи оптимизации (3), (4).

Теорема 5 определяет следующий алгоритм для проверки произвольной полностью определенной задачи условной оптимизации (3), (4), на макроустойчивость.

Шаг 1. Применяя подходящие для конкретного типа целевой функции методы решения полностью определенных задач условной оптимизации [11-13], ищем решение x' = ( x ‘ ,..., x'n ) задачи (3), (4). Одновременно проверяется и существование (несуществование) решения задачи.

Шаг 2. Задаваясь некоторыми подходящими значениями интервальных параметров целевой функции F , функций ограничений Ф_t, i = 1, m , и правых частей ограничений b i , i = 1, m полностью определенной задачи условной оптимизации (3), (4), строим производную от нее интервальную задачу условной оптимизации (5), (6).

Шаг 3. Используя формулы интервальной математики (8), выражающие результаты элементарных преобразований интервалов, представляем целевую функцию F , функции ограничений Ф i , i = 1, m , а также правые части ограничений b i , i = 1, m , интервальной задачи условной оптимизации (5), (6) в интервальной форме (15).

Шаг 4. По найденным на шаге 3 интервальным представлениям функций F , Ф i , i = 1, m , и параметров b i , i = 1, m , формируем нижнюю (20) и верхнюю (21) граничные задачи интервальной задачи условной оптимизации (5), (6).

Шаг 5. Используя те же самые методы, что и на шаге 1 , ищем решения оптимизационных задач (20) и (21). Одновременно с этим проверяем существование или несуществование решений указаных задач. Полные решения задач условной оптимизации вида (20, (21) имеют соответственно вид { M _н ( x ), F [,_max },{ M _в ( x ), F ₂,_max } , где M _н( x ) - множество точек x решения нижней, M _в ( x ) - множество точек x решения верхней граничной задачи.

Шаг 6. Проверяется наличие (отсутствие) пересечения найденных в результате решения задач (20) и (21) множеств M _н ( x ), M _в ( x ).

Итог. Если в результате работы алгоритма выяснилось, что полностью определенная задача условной оптимизации (3), (4) имеет решение, а производная от нее интервальная задача условной оптимизации (5), (6) имеет нижнюю и верхнюю граничные задачи, обладающие решениями, причем множества этих решений пересекаются, то задача оптимизации (3), (4) является макроустойчивой. В противном случае задача (3), (4) не является макроустойчивой.

Пример 2 (задача о назначениях). Имеется 3 работы и 3 исполнителя. Заданы доходы a_ij от выполнения любой j -й работы любым i -м исполнителем ( i , j = 1,3) . Требуется распределить работы между исполнителями так, чтобы каждый из них выполнял ровно одну работу, и, кроме того, суммарный доход от выполнения всех работ был максимальным. Введя множество неизвестных матриц назначений X = || x j ||, x ij е {0,1}, где x ij = 1 , если i -й исполнитель выполняет j -ю работу, и x ij = 0 в противном случае, задачу можно записать математически в виде

3 3 3 3

F ( x j ) = ЕЕ ^ay x y = max, при условии Ф 1 ( x j ) = Е x j = 1, j = 1,3; Ф 2 ( x j ) = Е x j = 1, i = 1,3.

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

Видим, что наша задача - частный случай полностью определенной задачи условной оптимизации (3), (4). Проверим эту задачу на макроустойчивость, используя изложенный алгоритм.

Шаг 1. Для определенности конкретизируем матрицу доходов A = Ца^ в виде матрицы с точно известными параметрами

A =

2 3 3

4 4 3

3 4 4

и решим нашу задачу при этих условиях. Имеется 6 различных матриц назначений X , удов- летворяющих ограничениям задачи:

X 1 =

1 0 0

0 0 1

, X 2 =

, X 3 =

1 0 0

, X 4 =

1 0 0

, X 5 =

1, X, 0

6 =

которым соответствуют значения целевой функции F 1 = 9, F ₂ = 10, F ₃ = 11, F ₄ = 11, F ₅ = 9, F ₆ = 10 .

Так что решение задачи существует, достигается на матрицах назначений X ₃ , X ₄ и равно

F ax = Fx 3 , X 4 = 11 .

Шаг 2. Согласно описанию данного шага алгоритма (см. выше), задаемся подходящими значениями интервальных параметров целевой функции F нашей недетерминированной задачи о назначениях в виде заданной неполностью (с точностью до интервалов возможных значений) матрицы доходов A = | \a_y 11 = |[ a 1 i , a 2 _y ]||:

A = ^{[ A} 1 , A 2 ^] , ^гд^е A 1 =| |~ 1 у||

12 2

₂ ² ₂ , A 2 =| j

4 4

Имеем производную от решенной полностью определенной задачи условной оптимизации интервальную задачу условной оптимизации типа (5), (6)

~         3 3

^{F (} x ij ) XX ~ y x y = ^max ,

= 1 j = 1

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

Шаг 3. С помощью формул (8) элементарных преобразований интервалов представляем целевую функцию производной задачи F в интервальной форме (15)

~ X j ) =

3 3                            3 3

^F 1 ⁽ x j ) = X X ^a 1ij ^X ij , ^F 2 ⁽ x j ) = X X ^a 2ij x ij

= 1 j = 1                          i = 1 j = 1

Шаг 4. По найденному на шаге 3 интервальному представлению целевой функции F и заданным условиям-ограничениям формируем нижнюю (20) и верхнюю (21) граничные задачи исходной интервальной задачи условной оптимизации

3 3 1

F1( xij)  XX a 1 ijxij = max, i=1 j=1

3                                           3                  ___ при условии Ф1(Xij ) = X Xy = 1, j = 1,3; Ф 2(Xy ) = X X j = 1, i = 1,3 i=1                                            j=1

3 3

. ^F 2⁽ x j ) XX ^a 2 ij x ij = ^max ,

I;                1=1И при тех же самых условиях

Шаг 5. Тем же методом, что и на шаге 1, находим решения нижней и верхней граничных задач. В нашем случае решение нижней граничной задачи существует, достигается на матрицах назначений X 1, X2, X3, X4 и равно F1,max = F[(X1,X2.X3,X4) = 5. Решение верхней граничной задачи тоже существует, достигается на матрицах назначений X 3, X 4 и равно F2,max = F2(X3,X4) = 14 •

Шаг 6. Проверяем наличие пересечения множеств точек решения нижней и верхней граничных задач интервальной задачи

M Н п M В = { X 1 , X ₂, X ₃, X ₄} п { X ₃, X ₄} = { X ₃, X ₄} ^ 0 , т.е. пересечение непусто.

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

4 Микроустойчивость задачи условной оптимизации

Снова обратимся к полностью определенной задаче условной оптимизации (3), (4) и опишем метод установления ее микроустойчивости. Из определения микроустойчивости (раздел 1) вытекает следующий алгоритм проверки задачи (3), (4) на микроустойчивость.

Шаг 1. С помощью 6-шагового алгоритма, изложенного в п. 4, проверяем задачу (3), (4) на макроустойчивость. В случае отрицательного результата (задача (3), (4) не макроустойчива) конец алгоритма, с выводом: задача (3), (4) не является микроустойчивой. При положительном результате проверки (задача (3), (4) макроустойчива) переход к шагу 2.

Шаг 2. Выбираем некоторую произвольную точку решения x' = ( x " ,..., x'n ) задачи (3), (4), найденную на шаге 1. После этого добавляем к ней какую-либо точку решения x" = ( x ^ ,...,x П ) соответствующей интервальной задачи (5), (6), также найденную на шаге 1. В результате получаем пару решений ( x', x ") указанных двух задач.

Шаг 3. Вычисляем величину расстояния D ( x' , x ") между точками решения x' , x " указанных двух задач, используя для этого формулу

• (23)                         D ( x' , x ") = ^( x " - x " )² + ... + ( x П - x П )² •

Шаг 4. Проверяем выполнение неравенства, сравнивающего расстояние D ( x " , x " ) с некоторой изначально заданной достаточно малой величиной d :

• (24)                                 D ( x " , x " ) <  d ,

Если условие (24) выполнено, задача оптимизации (3), (4) объявляется микроустойчивой и конец алгоритма. В противном случае совершается переход к шагу 2, в котором теперь к точке решения x' = ( x 1 ,..., x ' n ) задачи (3), (4), найденной на шаге 1, добавляется какая-то другая точка решения x " = ( x [ ,..., x П ) задачи (5), (6) из числа найденных на шаге 1. В результате получаем новую пару решений ( x ', x ") и т.д.

Итог. Если в результате работы алгоритма после некоторого достаточного числа шагов получена пара решений ( x ', x "), удовлетворяющая неравенству (24), процедура останавливается и задача (3), (4) объявляется микроустойчивой. В противном случае процедура также останавливается, но задача (3), (4) признается не обладающей свойством микроустойчивости.

Заключение

В статье показано, что проблема оптимизации неполностью определенных функций не может ограничиться только отысканием точки оптимума и значения в ней нашей функции, но и должна включать в себя задачу определения устойчивости найденного оптимума. Последнее означает, что при небольшом варьировании параметров оптимизируемой функции ее оптимум должен по-прежнему существовать и находиться в точке, близкой к точке исходного оптимума. Для установления устойчивости оптимума неполностью определенных функций предложена специальная эффективная методика, которая основана на аппарате интервальной математики. Несколько иные подходы к решению рассмотренной проблемы можно найти в [16–24].