close

Вход

Забыли?

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

?

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

код для вставкиСкачать
1999
ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ
МАТЕМАТИКА
Є 12 (451)
УДК 519.8
В.А. ЕМЕЛИЧЕВ, О.А. ЯНУШКЕВИЧ
О РЕГУЛЯРИЗАЦИИ МНОГОКРИТЕРИАЛЬНОЙ ЗАДАЧИ
ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Как обычно (напр., [1]{[5]), под устойчивостью многокритериальной (векторной) задачи дискретной оптимизации будем понимать свойство непоявления новых оптимумов Парето при \малых" возмущениях параметров исходной задачи, т. е. дискретный аналог свойства полунепрерывности сверху в смысле Хаусдорфа [1], [6]{[8] точечно-множественного отображения, характеризующего зависимость множества Парето от исходных данных задачи.
Известно [1], [2], [4], [5], [8], что скалярные (однокритериальные) линейные задачи дискретной
оптимизации всегда являются устойчивыми. Cуществование неустойчивых (некорректно поставленных по Адамару) векторных задач дискретной оптимизации (напр., [1]{[5]) естественно приводит к необходимости создания (если это возможно) регуляризирующего оператора, представляющего собой конкретный вид возмущений исходных данных дискретной задачи с тем, чтобы,
как и в случае задачи линейного программирования [6], [9], заменить возможно неустойчивую
задачу серией возмущенных устойчивых. Первый результат в этом направлении был получен в
работе [10] (см. также монографию [1]), где на основе аппарата выпуклых конусов предложена
регуляризация и по векторному критерию и по ограничениям векторной задачи целочисленного линейного программирования (ЦЛП) поиска множества Парето на ограниченном множестве
допустимых решений. При этом в [10] регуляризация по векторному критерию предполагает
замену векторной задачи ЦЛП возмущенной задачей с множеством Cлейтера, содержащимся в
множестве Парето исходной задачи.
В данной статье этот результат обобщается в том смысле, что здесь указан видоизмененный
регуляризирующий оператор, воздействующий на векторный критерий и переводящий возможно
неустойчивую исходную векторную задачу ЦЛП в серию не только устойчивых, но одновременно и эквивалентных задач, т. е. задач с первоначальным множеством Парето. Предложен также
прием "-регуляризации векторной задачи ЦЛП, позволяющий заменить возможно неустойчивую задачу возмущенными "-устойчивыми задачами.
Пусть матрица C = [cij ] 2 Rmn , m 1, n 1. На конечном множестве (допустимых)
решений X Zn зададим векторный линейный критерий Cx, компоненты которого (частные
критерии), не ограничивая общности, считаем минимизируемыми
Cix ! min
; i 2 Nm :
x2X
Здесь Nm = f1; 2; : : : ; mg, x = (x1 ; x2 ; : : : ; xn )T , Ci = (ci1 ; ci2 ; : : : ; cin ) и в дальнейшем нижний
индекс у матрицы (вектора) будет указывать на соответствующую строку матрицы (компоненту
вектора).
Под векторной (m-критериальной) задачей ЦЛП Z m (C ) будем понимать задачу нахождения
множества Парето (множества эффективных решений)
P (C ) = fx 2 X : (x; C ) = ;g;
Работа выполнена при поддержке Белорусского республиканского фонда фундаментальных исследований (грант Ф97-266).
38
где
(x; C ) = fx0 2 X : Cx Cx0; Cx 6= Cx0g:
Введем также традиционное множество Cлейтера (слабо эффективных решений)
S (C ) = fx 2 X : (x; C ) = ;g;
где
(x; C ) = fx0 2 X : 8i 2 Nm Ci x > Ci x0 g:
Для любой матрицы C 2 Rmn очевидно включение
P (C ) S (C ):
(1)
Ясно, что в частном случае, когда m = 1, множество Парето совпадает с множеством Cлейтера и превращается в множество всех оптимальных решений, а наша задача | в обычную
(скалярную) задачу ЦЛП Z 1 (c) на ограниченном множестве, где c 2 Rn .
В дальнейшем будем предполагать, что число частных критериев m 2, поскольку, как уже
отмечалось, всякая задача ЦЛП Z 1 (c) устойчива.
Введем обозначение P (C ) := X n P (C ). Методом от противного легко доказывается
Лемма 1. Пусть C; B 2 Rmn . Если для всякого решения x 2 P (C ) справедливо включение
(x; C ) (x; B ), то S (B ) P (C ).
Для любого натурального числа k в пространстве Rk зададим полярные друг к другу нормы
l1 и l1
k
X
kyk = maxfjyi j : i 2 Nk g; kyko = jyij:
i=1
= [cij ] 2 Rmn
Под нормой матрицы C
будем понимать норму вектора (c11 ; c12 ; : : : ; cmn ).
В дальнейшем понадобятся следующие очевидные неравенства для матрицы C и ее строк
8i 2 Nm jCi xj kCi k kxko kC k kxko :
(2)
Cледуя [1]{[5], задачу Z m(C ) назовем устойчивой (по векторному критерию), если существует
такое число " > 0, что
8C 0 2 (") P (C + C 0) P (C );
(3)
где множество возмущающих матриц (") задается равенством
(") = fC 0 2 Rmn : kC 0 k < "g:
Очевидно, что в случае, когда P (C ) = ;, задача Z m (C ) устойчива.
Лемма 2 ([1], [10]). Для любой матрицы C 2 Rmn справедлива формула
9" > 0 8C 0 2 (") S (C + C 0) S (C ):
Иными словами, лемма 2 утверждает, что векторная задача ЦЛП нахождения множества
Cлейтера всегда устойчива.
Пусть A 2 Rmn . Отображение ' : Rmn ! Rmn , которое определяется по правилу
8C 2 Rmn '(C ) = C + A;
назовем A-оператором. Тем самым A-оператор всякую задачу Z m (C ) переводит в задачу Z m(C +
A). Будем говорить, что A-оператор стабилизирует задачу Z m(C ), если существует такое число
" > 0, что справедлива формула
8C 0 2 (") P (C + A + C 0) P (C ):
(4)
39
Пусть матрица M = [ij ] 2 Rm> m , вектор t 2 Rm> , где R> = fu 2 R : u > 0g. Для матрицы
m
C 2 Rmn введем матрицу A(C; M; t) = (A1 ; A2 ; : : : ; Am )T со строками Ai = ti P ik Ck , i 2 Nm.
k=1
C2
m 2, n 1. Для любой матрицы M 2 Rm> m и всякого
t2
A(C; M; t)-оператор стабилизирует векторную задачу ЦЛП Z m (C ), причем
S (C + A(C; M; t)) P (C ):
m
m
Доказательство. Пусть M 2 Rm
> , t 2 R> . Если P (C ) = ;, то любой A-оператор стабиm
лизирует задачу Z (C ).
Пусть x 2 P (C ) 6= ;. Тогда (x; C ) 6= ; и для любого решения x0 2 (x; C ) на основании
определения множества (x; C ) справедливы неравенства
Теорема 1.
вектора
Rm
>
Пусть
Rmn ,
m
X
8i 2 Nm (Ci + Ai )(x ; x0) ti ik Ck (x ; x0) > 0:
k=1
Поэтому cогласно определению множества (x; C + A(C; M; t)) имеем x0 2 (x; C + A(C; M; t)).
Таким образом, справедливы соотношения
8x 2 P (C ) (x; C ) (x; C + A(C; M; t)):
Отсюда с учетом леммы 1 выводим
S (C + A(C; M; t)) P (C ):
(5)
Далее в силу леммы 2 получаем
9" > 0 8C 0 2 (") S (C + A(C; M; t) + C 0) S (C + A(C; M; t)):
Учитывая (1) и (5), заключаем, что
9" > 0 8C 0 2 (") P (C + A(C; M; t) + C 0) P (C );
т. е. A(C; M; t)-оператор стабилизирует задачу Z m(C ).
Из теоремы 1, в частности, вытекает следующий ранее известный результат.
Cледствие [10] (см. также [1]). Пусть C 2 Rmn , m 2, n 1, и строки матрицы
A 2 Rmn вычисляются по формулам
m
X
Ai = k Ck ; i 2 Nm ;
k=1
m
P
где > 0, k = 1, i > 0, i 2 Nm . Тогда A-оператор стабилизирует векторную задачу ЦЛП
k=1
Z m (C ), и любое слабо эффективное решение возмущенной задачи Z m (C +A) будет эффективным
решением исходной задачи Z m (C ).
Пусть C; D 2 Rmn . Задачи Z m(C ) и Z m(D) назовем эквивалентными, если P (C ) = P (D). В
этом случае будем писать Z m (C ) Z m (D).
Будем говорить, что A-оператор регуляризирует задачу Z m (C ), если Z m (C ) Z m (C + A)
и задача Z m (C + A) устойчива. Ясно, что всякий A-оператор, который регуляризирует задачу
Z m (C ), одновременно ее стабилизирует.
m существуТеорема 2. Пусть C 2 Rmn , m 2, n 1. Для всякой матрицы M 2 Rm
>
m
ет такой вектор t 2 R> , что A(C; M; t )-оператор регуляризирует векторную задачу ЦЛП
Z m (C ).
40
Доказательство.
Если := jfCx : x 2 X gj = 1, то, очевидно, A(C; M; t )-оператор регуляпри любом векторе t 2 Rm> . Если > 1, то существует положительное
ризирует задачу Z m(C )
число
fCi (x ; x0) > 0 : x; x0 2 X; i 2 Nmg :
= min
mkM k kC k maxfkx ; x0 ko : x; x0 2 X g
Пусть компоненты вектора t удовлетворяют неравенствам
0 < ti < ; i 2 Nm :
(6)
Cначала докажем, что Z m(C + A(C; M; t )) Z m (C ). В силу включения (5) имеем P (C +
A(C; M; t )) P (C ). Далее доказательство проведем методом от противного. Предположим, что
существует решение x 2 P (C ) n P (C + A(C; M; t )). Тогда множество (x; C + A(C; M; t )) непусто.
Если x0 | один из элементов этого множества, то (ввиду x 2 P (C )) Cx Cx0 , и найдется такой
индекс i 2 Nm , что Ci x < Ci x0 . Поэтому на основании (2) и (6) выводим
(Ci + Ai )(x ; x0 ) = Ci (x ; x0 ) + ti
m
X
m
X
k=1
ik Ck (x ; x0 ) Ci (x ; x0 ) + ti jik Ck (x ; x0)j Ci (x ; x0) + ti mkM k kC kkx ; x0ko <
k=1
< Ci (x ; x0) + minfCk (x ; x0) > 0 : x; x0 2 X; k 2 Nmg Ci (x ; x0 ) + jCi(x ; x0 )j = 0;
т. е. x0 2= (x; C + A(C; M; t )). Полученное противоречие доказывает, что Z m (C + A(C; M; t )) Z m (C ). Таким образом, P (C + A(C; M; t )) = P (C ). Отсюда согласно теореме 1 для всякой
матрицы M 2 Rm> m задача Z m(C + A(C; M; t )) устойчива.
Отметим, что доказательство теоремы носит конструктивный характер, поскольку неравенствами (6) указана верхняя граница для положительных координат вектора t .
Пусть " > 0, A; C 2 Rmn . Будем говорить, что A-оператор "-стабилизирует задачу Z m(C ),
если выполняется (4).
Теорема 3. Пусть C 2 Rmn , m 2, n 1. Для любого числа " > 0 и всякой матрицы
M 2 Rm> m существует такой вектор t 2 Rm> , что A(C; M; t )-оператор "-стабилизирует
m
векторную задачу ЦЛП Z (C ), причем S (C + A(C; M; t )) P (C ).
Доказательство. Если P (C ) = ;, то любой A-оператор "-стабилизирует задачу Z m (C ).
Пусть P (C ) 6= ;, M = [ij ] 2 Rm> m , " > 0 и t | любой вектор с компонентами
ti ; i 2 Nm ;
(7)
i
где
i = min
X
m
k=1
= " maxfkx ; x0 ko : x; x0 2 X g;
ik Ck (x ; x0 ) : x 2 P (C ); x0 2 (x; C ) ; i 2 Nm :
Тогда для любой возмущающей матрицы C 0 2 ("), любых решений x 2 P (C ), x0 2 (x; C ) и
всякого индекса i 2 Nm справедливы неравенства
X
m
0
0
0
(Ci + Ai + Ci )(x ; x ) ti ij Cj + Ci (x ; x0 ) > toi i ; 0:
j =1
Поэтому 8C 0 2 (") S (C + A(C; M; to ) + C 0 ) P (C ). Для завершения доказательства осталось
воспользоваться включением (1).
41
Заметим, что в отличиe от доказанной теоремы 3 в работе [9] "-стабилизация задачи Z m (C )
достигается лишь при достаточно малом " > 0. Задачу Z m (C ) назовем "-устойчивой, если выполняется формула (3). Пусть " > 0. Будем говорить, что A-оператор "-регуляризирует задачу
Z m (C ), если он регуляризирует ее и задача Z m (C + A) "-устойчива.
Путем непосредственного обращения к доказательству теорем 2 и 3 с учетом неравенств (6)
и (7) после несложных преобразований получается
Теорема 4. Пусть C 2 Rmn , m 2, n 1, jfCx : x 2 X gj > 1. Тогда для любой матрицы
M = [ij ] 2 Rm> m, всякого числа ", удовлетворяющего неравенствам
n
o
m
P
minfCi (x ; x0 ) ik Ck (x ; x0 ) > 0 : x; x0 2 X; i 2 Nm
k=1
0<"<
;
mkM k kC k maxf(kx ; x0 ko )2 : x; x0 2 X g
t 2 Rm> , компоненты которого подчинены неравенствам
" maxfkx ; x0 ko : x; x0 2 X g
ti nP
o ; i 2 Nm ;
m
min
ik Ck (x ; x0) > 0 : x; x0 2 X; i 2 Nm
и любого вектора
A(C; M; t )-оператор
k=1
"-регуляризирует векторную задачу ЦЛП Z m(C ).
Литература
1. Cергиенко И.В., Козерацкая Л.Н., Лебедева Т.Т. Исследование устойчивости и параметрический анализ дискретных оптимизационных задач. { Киев: Наук. думка, 1995. { 169 c.
2. Козерацкая Л.Н., Лебедева Т.Т., Cергиенко И.В. Исследование устойчивости задач дискретной оптимизации // Кибернетика и системн. анализ. { 1993. { Є 3. { C. 78{93.
3. Бакурова А.В., Емеличев В.А., Перепелица В.А. Об устойчивости многокритериальных
задач на системах подмножеств // Докл. АН Беларуси. { 1995. { Т. 39. { Є 2. { C. 33{35.
4. Емеличев В.А., Кравцов М.К. Об устойчивости в траекторных задачах векторной оптимизации // Кибернетика и системн. анализ. { 1995. { Є 4. { C. 137{143.
5. Емеличев В.А., Подкопаев Д.П. О количественной мере устойчивости векторной задачи
целочисленного программирования // Журн. вычисл. матем. и матем. физ. { 1998. { Т. 38. {
Є 11. { C. 1801{1805.
6. Дубов Ю.А., Травкин C.И., Якимец В.Н. Многокритериальные модели формирования и выбора вариантов систем. { М.: Наука, 1986. { 296 c.
7. Молодцов Д.А. Устойчивость принципов оптимальности. { М.: Наука, 1987. { 280 c.
8. Белоусов Е.Г., Андронов В.Г. Разрешимость и устойчивость задач полиномиального программирования. { М.: Изд-во МГУ, 1993. { 272 с.
9. Ашманов C.А. Линейное программирование. { М.: Наука, 1981. { 340 с.
10. Козерацкая Л.Н., Лебедева Т.Т., Cергиенко Т.И. О регуляризации задач целочисленной векторной оптимизации // Кибернетика и системн. анализ. { 1993. { Є 3. { C. 172{176.
Белорусский государственный университет
Институт технической кибернетики
Национальной академии наук Беларуси
42
Поступила
05.03.1999
Документ
Категория
Без категории
Просмотров
6
Размер файла
144 Кб
Теги
целочисленное, регуляризация, линейного, задачи, программирование, многокритериальной
1/--страниц
Пожаловаться на содержимое документа