close

Вход

Забыли?

вход по аккаунту

?

Об одном дискретном аналоге полунепрерывности по Хаусдорфу лексикографического отображения в векторной булевой задаче минимизации модулей линейных функций.

код для вставкиСкачать
ВЕСНІК МДПУ імя І. П. ШАМЯКІНА
6
===========================================================================
Выводы
В заключение можно сказать, что приведенные здесь основные принципы корреляционноспектрального анализа нисколько не означают отказа от существующих методов анализа
и расчета, а лишь дополняют и уточняют их.
Метод корреляционно-спектрального анализа в исследованиях нагруженности механизмов
позволяет выявить величину колебаний и их частоту с целью их снижения, что в итоге
увеличивает надежность механизмов.
Литература
1. Бидерман, В. Л. Теория механических колебаний / В. Л. Бидерман. – М. : Высшая школа, 1980.
2. Гмурман, В. Е. Теория вероятностей и математическая статистика / В. Е. Гмурман. – М. : УРСС, 2002.
3. Гриценок, П. А. Разработка и обоснование технических средств, повышающих производительность
и надежность фрезерных машин, взаимодействующих с закустаренными почвами : дис. … канд. техн. н. :
05.20.01 / П. А. Гриценок. – Горки, БСХА, 1985.
4. Кремер, Н. Ш. Теория вероятностей и математическая статистика / Н. Ш. Кремер. – М. : ЮНИТИ,
2004. – 573 с.
Summary
Using the methods of statistical dynamics, particularly correlation spectral analysis, we can
receive full structural description of any occasional stationary machine loading process.
Поступила в редакцию 14.06.07
УДК 519.8
Е. Е. Гуревский, В. А. Емеличев
ОБ ОДНОМ ДИСКРЕТНОМ АНАЛОГЕ ПОЛУНЕПРЕРЫВНОСТИ ПО ХАУСДОРФУ
ЛЕКСИКОГРАФИЧЕСКОГО ОТОБРАЖЕНИЯ В ВЕКТОРНОЙ БУЛЕВОЙ ЗАДАЧЕ
МИНИМИЗАЦИИ МОДУЛЕЙ ЛИНЕЙНЫХ ФУНКЦИЙ
Введение
В работе [1] получено необходимое и достаточное условие устойчивости векторной
лексикографической задачи целочисленного линейного программирования. В данной статье этот
результат распространяется на лексикографическую булеву задачу минимизации абсолютных
уклонений от нуля линейных функций. Выявлены все случаи устойчивости этой задачи.
Пусть m – число критериев, n – число булевых переменных, x = ( x1 , x2 , K, xn )T Î X Í En =
= {0,1}n , | X |³ 2,
Ci – i -я строка матрицы
C = [cij ]m´n Î R m´n ,
m ³ 1, n ³ 2,
i Î Nm =
= {1, 2, K , m}. Пусть на множестве решений X задана векторная функция, состоящая из модулей
линейных функций:
f ( x , C ) = (| C1 x |, | C 2 x |, K , | Cm x |).
m
В критериальном пространстве R введем бинарное отношение лексикографического
порядка p между различными векторами y = ( y1 , y 2 , K , y m ) и y ¢ = ( y1¢ , y 2¢ , K , y m¢ ), полагая, что
y p y ¢ Û y k < y ¢k ,
где k = min{i Î N m : yi ¹ y¢i }.
Под лексикографической булевой задачей оптимизации
m
Z (C ) : lex min { f ( x , C ) : x Î X }, m ³ 1
будем понимать задачу поиска множества лексикографических оптимумов [1], которое задается
формулой:
m
L ( C ) = { x Î X : " x ¢ Î X ( f ( x ¢, C ) p f ( x , C ))},
где p – отрицание лексикографического отношения p .
МАТЭМАТЫКА. ФІЗІКА
7
===========================================================================
Очевидно следующее:
m
Свойство 1. Для любых двух решений x , x ¢ Î L ( C ) справедливо равенство f ( x , C ) = f ( x¢, C ).
Поэтому множество векторных лексикографических оценок
m
m
m
f ( L ( C )) = { y Î R : y = f ( x , C ), x Î L ( C )}
всегда состоит из одного вектора.
Очевидно, что векторная функция f ( x , C ) характеризует меру несовместности
(абсолютных уклонений) следующей системы линейных булевых уравнений:
T
Cx = 0( m ) , x Î X ,
(1)
m
где 0 ( m ) = (0, 0, K , 0) Î R . Легко видеть, что эта система совместна тогда и только тогда,
m
когда f ( L (C )) = {0 ( m ) }. Кроме того, нетрудно понять, что частным случаем однородной системы
(1) может быть неоднородная система вида
T
Ax + b = 0 ( m ) , x Î X ,
где X Í E
n -1
, AÎR
m´( n -1)
T
m
, b = (b1 , b2 , K , bm ) Î R .
m
Известно (см., например, [2], [3]), что множество L ( C ), являясь подмножеством
множества Парето, может быть определено как результат решения последовательности m
скалярных задач:
m
m
Li (C ) = Arg min {| Ci x |: x Î Li -1 (C )}, i Î N m ,
где
(2)
m
L0 (C )
= X.
Таким образом, имеем последовательность множеств
m
m
m
m
X Ê L1 (C ) Ê L2 (C ) Ê K Ê Lm (C ) = L (C ).
(3)
Результаты исследования и их обсуждение
m
Будем исследовать устойчивость задачи Z ( C ) к независимым возмущениям параметров
векторного критерия
произвольной
f ( x , C ), т. е. элементов матрицы C . Для этого в пространстве R
размерности
kÎN
зададим
метрику
l¥ ,
т. е.
под
нормой
k
вектора
k
z = ( z1 , z 2 , K , z k ) Î R будем понимать число
|| z ||= max | z j |,
jÎN
k
а под нормой матрицы – норму вектора, составленного из всех ее элементов.
m
Как обычно [1], [4–6], задачу Z ( C )
назовем устойчивой (в терминологии [7]
T3 -устойчивой), если
m
m
X := {e > 0 : " C ¢ Î W ( e ) ( L ( C + C ¢) Í L ( C ))} ¹ Æ ,
где
W ( e ) = {C ¢ Î R
m´ n
: || C ¢ ||< e}.
m
Тем самым, устойчивость задачи Z ( C ) является дискретным аналогом свойства
полунепрерывности сверху по Хаусдорфу в точке C многозначного оптимального отображения
m
L :R
m´ n
X
®2 ,
m
m
которое каждой матрице C ставит в соответствие множество L ( C ). Задачу Z ( C + C¢) будем
называть возмущенной, а матрицу C¢ Î W ( e ) – возмущающей.
ВЕСНІК МДПУ імя І. П. ШАМЯКІНА
8
===========================================================================
Понятно, что при выполнении равенства
m
m
задача
L (C ) = X
Z (C )
устойчива.
m
В дальнейшем этот случай будем исключать из рассмотрения, а задачу Z ( C ) , для которой
m
m
множество L (C ) := X \ L (C ) непусто, называть нетривиальной.
Отметим, что в [6] были получены нижняя и верхняя оценки радиуса устойчивости
векторной булевой задачи с паретовским принципом оптимальности и частными критериями
вида | Ai x + bi | .
Следующее свойство очевидно.
T
m
Свойство 2. При 0 ( n ) Î X решение x принадлежит множеству L (C ) тогда и только
тогда, когда существует такой индекс k Î N m , что | Ck x | > 0.
T
m
Теорема 1. Если 0 ( n ) Î X , то нетривиальная задача Z ( C ), m ³ 1 устойчива при любой
m´ n
.
матрице C Î R
Доказательство. При выполнении условий теоремы 1, согласно свойству 2, выполняется
формула
m
" x Î L (C ) $ k Î N m (| Ck x | > 0).
Тогда существует такое число e ( x ) > 0, что для любой возмущающей матрицы
C ¢ Î W ( e ( x )) справедливо неравенство
| (Ck + Ck¢ ) x | > 0,
где C¢k – k -я строка матрицы C ¢ . Поэтому, вновь учитывая свойство 2, заключаем, что
m
x Î L (C + C¢) при C ¢ Î W (e ( x )).
Резюмируя, получаем
*
m
m
" C ¢ Î W (e ) ( L (C ) Í L (C + C ¢)),
*
m
где e = min{e ( x ) : x Î L (C )}.
Тем самым, имеем
*
*
m
m
$ e > 0 " C ¢ Î W ( e ) ( L ( C ) Ê L ( C + C ¢)),
m
и поэтому задача Z ( C ) устойчива.
Теорема 1 доказана.
T
m
Теорема 2. Если 0 ( n ) Ï X , то нетривиальная задача Z ( C ), m ³ 1 устойчива в том
и только в том случае, когда
m
m
L (C ) = L1 (C ).
(4)
m
m
Доказательство. Необходимость докажем методом от противного. Пусть L (C ) ¹ L1 (C )
m
m
m
m
при условии, что задача Z ( C ) устойчива. Тогда множество S (C ) := L1 (C ) Ç L (C ) непусто.
Покажем, что справедлива следующая формула:
*
m
m
*
" e > 0 $ C Î W ( e ) ( L ( C ) Ç L ( C + C ) = Æ ).
0
m
0
T
Пусть x Î S ( C ). Тогда x ¹ 0 ( n ) и
m
0
" x Î L ( C ) ( f ( x , C ) p f ( x , C )).
(5)
МАТЭМАТЫКА. ФІЗІКА
9
===========================================================================
0
m
Это вместе с x Î L1 (C ) дает формулу
m
0
0
" x Î L (C ) $ k = k ( x ) Î N m \ {1} " i Î N k -1 (| Ci x | = | Ci x | & | Ck x | < | Ck x |),
которая, согласно свойству 1, может быть записана в виде
m
0
0
$ k Î N m \ {1} " i Î N k -1 " x Î L (C ) (| Ci x | = | Ci x | & | Ck x | < | Ck x |).
(6)
Отсюда следует, что C k ¹ 0 ( n ) , т. е.
|| Ck || > 0.
(7)
*
Пусть e > 0. Займемся построением необходимой возмущающей матрицы C . В связи
с (6) возможны два случая.
m
Случай 1. Для любого решения x Î L ( C ) справедливы равенства
0
C1 x = C1 x = 0.
(8)
Поскольку никакая пара различных ненулевых булевых векторов не является
n
0
коллинеарной, то в R существует гиперплоскость H , проходящая через точки 0 ( n ) и x , но не
m
n
содержащая ни одной точки множества L ( C ). Поэтому вектор a = ( a1 , a2 , K , an ) Î R , || a || = 1,
ортогональный к H , обладает свойством
m
0
" x Î L ( C ) (0 = ax ¹ ax ).
*
Далее построим строки матрицы C Î R
*
Ci =
m´ n
(9)
по правилу
ìda , если i = 1,
í0 , если ¹ 1,
i
î (n)
где число d удовлетворяет неравенствам
0 < d < e.
*
Отсюда, учитывая равенство || a || = 1, выводим C Î W ( e ). Кроме того, из (8) и (9)
m
вытекает, что при любом решении x Î L ( C ) выполняются соотношения
*
0
0
*
| (C1 + C1 ) x | = | dax | = 0 < | dax | = | (C1 + C1 ) x | .
(10)
m
Случай 2. Для любого решения x Î L ( C ) справедливы соотношения
0
| C1 x | = | C1 x | > 0.
*
В этом случае возмущающую матрицу C Î R
*
Ci =
ìdCk ,
í
î0 ( n ) ,
m´ n
(11)
определим по правилу:
если i = 1,
если i ¹ 1
(здесь и далее индекс k из (6)), а число d ¹ 0 зададим так, чтобы выполнялись условия
|| dCk ||< e ,
(12)
ВЕСНІК МДПУ імя І. П. ШАМЯКІНА
10
===========================================================================
ìï1,
sign d = í
ïî-1,
0
0
0
0
если sign(C1 x ) ¹ sign(Ck x ),
(13)
если sign(C1 x ) = sign(Ck x ),
0
| d |<
| C1 x |
0
| Ck x |
.
(14)
Согласно (7), число, стоящее в левой части неравенства (12), положительно. Поэтому,
*
*
принимая во внимание строение возмущающей матрицы C , имеем C Î W ( e ). Кроме того,
0
0
учитывая, что оба числа C1 x и C k x отличны от нуля (см. (6) и (11)), из (13) и (14) выводим
0
0
0
0
| C1 x + dCk x | = | C1 x | - | d | × | C k x | .
Отсюда ввиду (6), (11) и строения матрицы C
*
следует, что для любого решения
m
x Î L ( C ) справедливы соотношения
*
0
*
0
0
*
| (C1 + C1 ) x | - | (C1 + C1 ) x | = | C1 x + dC k x | - | (C1 + C1 ) x | £
0
0
*
0
£ | C1 x | - | d | × | C k x | - | C1 x | + | C1 x | = - | d | × | C k x | + | d | × | Ck x | < 0,
которые вместе с (10) дают формулу
*
*
m
0
*
$ C Î W (e ) " x Î L (C ) (| (C1 + C1 ) x | < | (C1 + C1 ) x |).
Поэтому имеем
m
m
*
L (C ) Ç L1 (C + C ) = Æ ,
и, как следствие, учитывая включение
m
*
m
*
L (C + C ) Í L1 (C + C ),
m
справедливое в силу (3), заключаем, что верна формула (5). Это означает, что задача Z ( C )
не является устойчивой. Полученное противоречие доказывает необходимость равенства (4).
m
Достаточность. Пусть выполняется равенство (4). Тогда никакое решение x Î L (C )
m
не может принадлежать множеству L1 (C ). Поэтому, согласно (2), (при i = 1 ) для любого решения
m
x Î L (C ) справедливо неравенство
0
| C1 x | < | C1 x |,
0
m
если x Î L (C ). Отсюда в силу непрерывности функции C1 x на множестве параметров C1 Î R
n
существует такое число e = e ( x ) > 0, что для любой возмущающей матрицы C¢ Î W ( e )
справедливо неравенство
0
| (C1 + C1¢ ) x | < | (C1 + C1¢ ) x |,
т. е.
решение
x
не
является
лексикографическим
оптимумом
m
(15)
возмущенных
задач
m
Z (C + C ¢ ), C ¢ Î W ( e ). Очевидно, что неравенство (15) верно при любом решении x Î L (C ),
*
если C¢ Î W ( e ), где
*
m
e = min{e ( x ) : x Î L (C )}.
Из приведенных рассуждений следует, что
МАТЭМАТЫКА. ФІЗІКА
11
===========================================================================
*
*
m
m
$ e > 0 " C ¢ Î W ( e ) ( L (C ) Í L (C + C ¢)),
m
и потому задача Z (C ) устойчива.
Теорема 2 доказана.
Выводы
1
1
Поскольку при переходе к однокритериальному случаю ( m = 1) равенство L (C ) = L1 (C )
n
выполняется при любой строке C Î R , то из теорем 1 и 2 вытекает
1
n
Следствие. Скалярная задача Z ( C ) устойчива при любой строке C Î R .
Литература
1. Емеличев, В. А. О регуляризации лексикографической векторной задачи целочисленного
программирования / В. А. Емеличев, О. А. Янушкевич // Кибернетика и системный анализ. – 1999. – № 6. –
С. 125–130.
2. Еремин, И. И. О задачах последовательного программирования / И. И. Еремин // Сибирский
матем. журнал. – 1973. – Т. 14. – № 1. – С. 53–63.
3. Червак, Ю. Ю. Оптимiзацiя. Непокращуваний вибiр / Ю. Ю. Червак. – Ужгород : Ужгородський
Нацiональний унiверситет, 2002. – 312 с.
4. Stability and regularization of vector problems of integer linear programming / V. A. Emelichev [et al.]
// Optimization. – 2002. – V. 51, № 4. – P. 645–676.
5. Емеличев, В. А. Об устойчивости векторной булевой задачи минимизации пороговых функций
/ В. А. Емеличев, К. Г. Кузьмин // Веснiк Мазырскага дзяржаўнага педагагiчнага унiверсiтэта. – 2005. – № 1. –
С. 6–10.
6. Гуревский, Е. Е. Об устойчивости векторной булевой задачи минимизации абсолютных
уклонений от нуля линейных функций / Е. Е. Гуревский, В. А. Емеличев // Известия вузов. Математика. –
2006. – № 12. – С. 27–32.
7. Сергиенко, И. В. Задачи дискретной оптимизации. Проблемы, методы решения, исследования
/ И. В. Сергиенко, В. П. Шило. – Киев : Наук. думка, 2003. – 261 c.
Summary
A criterion of stability for the vector nontrivial boolean lexicographic problem of minimizing
absolute value of linear functions is obtained.
Поступила в редакцию 02.03.07
УДК 519.8
В. А. Емеличев, А. А. Платонов
О РАДИУСЕ КВАЗИУСТОЙЧИВОСТИ ВЕКТОРНОЙ ЗАДАЧИ
ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
С ПАРАМЕТРИЧЕСКИМ ПРИНЦИПОМ ОПТИМАЛЬНОСТИ В МЕТРИКЕ ГЁЛЬДЕРА
Введение
В
статье
рассматривается
векторная
задача
целочисленного
линейного
программирования, принцип оптимальности которой задается способом разбиения частных
критериев на группы так, что внутри каждой группы действует паретовский принцип
оптимальности, а между группами – лексикографический. Исследуется квазиустойчивость задачи,
т. е. дискретный аналог свойства полунепрерывности снизу по Хаусдорфу многозначного
отображения, задающего функцию выбора. Получена формула радиуса квазиустойчивости задачи
в случае нормы l p , 1 £ p £ ¥, заданной в пространстве параметров векторного критерия. Ранее
подобные формулы были выведены лишь для комбинаторных (булевых) задач с разнообразными
видами параметризации принципов оптимальности в случаях метрик l1 и l ¥ [1–4], а также для
некоторых задач теории игр [5–8].
1/--страниц
Пожаловаться на содержимое документа