close

Вход

Забыли?

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

?

О радиусе устойчивости эффективного решения векторной комбинаторной задачи разбиения.

код для вставкиСкачать
ВЕСНІК МДПУ
10
===========================================================================
будем иметь
1
1
ál , f ( t , D% ) ñ = min{ál , f ( t , D% ) ñ : i Î N } = 5.8,
1
i
2
4
2
ál , f ( t 2 , D% ) ñ = min{ál , f ( t i , D% ) ñ : i Î N 4 } = 17.6,
3
3
ál , f ( t 3 , D% ) ñ = min{ál , f ( t i , D% ) ñ : i Î N 4 } = 3.
2
Следовательно, задача Z 5´2 (T , D% ) разрешима с помощью АЛС.
Литература
1. Подиновский, В. В. Парето-оптимальные решения многокритериальных задач / В. В. Подиновский,
В. Д. Ногин. – М. : Наука, 1982. – 256 с.
2. Ногин, В. Д. Принятие решений в многокритериальной среде. Количественный подход
/ В. Д. Ногин. – М. : Физматлит, 2002. – 176 с.
3. Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес. – М. : Мир, 1978. – 432 c.
4. Замбицкий, Д. К. Алгоритмы решения оптимизационных задач на сетях / Д. К. Замбицкий,
Д. Д. Лозовану. – Кишинев : Штиинца, 1983. – 115 c.
5. Емеличев, В. А. Многокритериальные задачи об остовах графа / В. А. Емеличев, В. А. Перепелица
// Доклады АН СССР. – 1988. – Т. 298, № 3. – С. 544–547.
6. Emelichev, V. A. Complexity of vector optimization problems on graphs / V. A. Emelichev,
V. A. Perepeliza // Optimization. – 1991. – V. 22, № 6. – P. 903–918.
7. Емеличев, В. А. О неразрешимости с помощью алгоритмов линейной свертки векторных задач
на графах / В. А. Емеличев, В. А. Перепелица // В сб. : IV Тираспольский симпозиум по общей топологии
и ее приложениям. – Кишинев. – 1991. – C. 82–83.
8. Емеличев, В. А. Сложность дискретных многокритериальных задач / В. А. Емеличев, В. А. Перепелица
// Дискр. математика. – 1994. – Т. 6, вып. 1. – С. 3–33.
9. Емеличев, В. А. О неразрешимости векторных задач дискретной оптимизации на системах
подмножеств в классе алгоритмов линейной свертки критериев / В. А. Емеличев, М. К. Кравцов // Доклады
РАН. – 1994. – Т. 334, № 1. – С. 9–11.
10. Емеличев, В. А. О задачах векторной дискретной оптимизации на системах подмножеств,
неразрешимых с помощью алгоритмов линейной свертки / В. А. Емеличев, М. К. Кравцов // Журнал вычисл.
матем. и матем. физики. – 1994. – Т. 34, № 7. – С. 1082–1094.
11. Кравцов, М. К. О разрешимости векторной задачи с помощью алгоритма линейной свертки критериев
/ М. К. Кравцов, О. А. Янушкевич // Мат. заметки. – 1997. – Т. 62, вып. 4. – С. 502–509.
12. Условия разрешимости векторных задач с помощью линейной свертки критериев / Э. Гирлих [и др.]
// Кибернетика и системный анализ. – 1999. – № 1. – С. 81–95.
13. Емеличев, В. А. Разрешимость векторной траекторной задачи на «узкие места» с помощью алгоритма
линейной свертки критериев / В. А. Емеличев, М. К. Кравцов, О. А. Янушкевич // Докл. АН Беларуси. – 1996. –
Т. 40, № 4. – С. 29–33.
14. Кнут, Д. Э. Искусство программирования. Сортировка и поиск / Д. Э. Кнут. – СПб. : Вильямс,
2000. – Т. 3. – 832 c.
Summary
A translation algorithm of possible insoluble problem to solvable and equivalent problem
is produced.
Поступила в редакцию 10.10.06.
УДК 519.8
В. А. Емеличев, Е. Е. Гуревский
О РАДИУСЕ УСТОЙЧИВОСТИ ЭФФЕКТИВНОГО РЕШЕНИЯ
ВЕКТОРНОЙ КОМБИНАТОРНОЙ ЗАДАЧИ РАЗБИЕНИЯ 2
Практически любая задача, относящаяся к проблемам проектирования, планирования
и управления в технических и организационных системах, носит ярко выраженный
многокритериальный характер. Во многих случаях возникающие при этом многоцелевые модели
1
Работа выполнена при финансовой поддержке Межвузовской программы Республики Беларусь
«Фундаментальные и прикладные исследования» (грант 492/28).
МАТЭМАТЫКА
11
===========================================================================
сводятся к выбору лучших, в каком-то смысле, значений параметров из некоторой дискретной
совокупности заданных величин. Поэтому интерес математиков к векторным задачам дискретной
оптимизации не ослабевает, что подтверждается частым появлением публикаций в этой области
(см., например, библиографию в [1], содержащую 234 наименования). Одним из актуальных
направлений исследования таких задач является анализ устойчивости решений к возмущениям
исходных данных (параметров задачи). Разнообразные постановки проблемы устойчивости
порождают многочисленные направления исследований. Не задерживаясь на описании всего
спектра вопросов, возникающих в этой области, отсылаем читателя к обширной библиографии [2],
а также к монографиям [3–6].
В настоящей статье продолжаются исследования [7–13] меры устойчивости парето-оптимальных
решений комбинаторных задач с разнообразными типами векторных критериев. Здесь рассматривается
многокритериальный вариант задачи разбиения множества чисел, знакомой широкому кругу
специалистов по дискретной оптимизации. Получена формула радиуса устойчивости эффективного
решения в случае чебышевской нормы l ¥ , заданной в пространстве возмущающих параметров.
Задача о равномерном разбиении множества чисел на два подмножества является
классической комбинаторной экстремальной задачей. Она состоит в следующем. Набор из
нескольких положительных чисел требуется разбить на два подмножества таким образом, чтобы
суммы элементов в подмножествах отличались минимальным образом. Эта задача эквивалентна
задаче теории расписаний, состоящей в распределении независимых работ по двум идентичным
процессорам так, чтобы время, когда заканчивается последняя выполненная работа, было
минимальным [14]. В теории расписаний эта задача обозначается P | × | Cmax .
Рассмотрим векторный (m-критериальный) вариант задачи разбиения.
n
Пусть на множестве n-векторов (разбиений) Q , n ³ 2, Q = {-1,1} задана векторная
функция (векторный критерий)
f ( x , C ) = (| C1 x |,| C2 x |, K ,| Cm x |) ® min ,
xÎQ
где
Ci – i -ая
строка
матрицы
C = [cij ]m´n Î R
m´ n
n
, i Î N m = {1, 2, K , m},
m ³ 1,
T
x = ( x1 , x2 , K , xn ) .
Векторную задачу разбиения, т. е. задачу поиска множества эффективных (оптимальных,
по Парето [15]) разбиений,
m
n
P ( C ) = { x Î Q : p ( C ) = Æ},
где
n
p ( C ) = { x ¢ Î Q : f ( x , C ) ³ f ( x ¢, C ) & f ( x , C ) ¹ f ( x ¢, C )},
m
будем обозначать Z ( C ).
Для всякого натурального числа k в пространстве R
соответственно:
|| z ||1 =
k
зададим нормы l1 и l ¥
å | z j |, || z ||¥ = max | z j |,
jÎN
jÎN k
k
где z = ( z1 , z 2 , K , z k ) Î R . Под нормой матрицы будем понимать норму вектора, составленного
из всех ее элементов. Для любого числа e > 0 введем множество возмущающих матриц
k
W ( e ) = {C ¢ Î R
m´ n
:|| C ¢ ||¥ < e}.
0
m
Следуя [8–12], радиусом устойчивости эффективного разбиения x Î P ( C ) назовем число
ВЕСНІК МДПУ
12
===========================================================================
m
ì0,
í
îsup X ,
0
r (x , C) =
где
если X = Æ,
если X ¹ Æ ,
X = {e > 0 : " C ¢ Î W ( e ) ( x Î P (C + C ¢))}.
0
m
Таким образом, радиус устойчивости эффективного разбиения x0 задает предел возмущений
m´n
с метрикой l ¥ , при которых эффективность
элементов матрицы С в пространстве R
0
разбиения x сохраняется.
Для любого числа z Î R будем использовать обозначение
sg z =
{
1, если z ³ 0,
-1, если z < 0.
Будем также пользоваться импликацией
$q Î Q "q¢ Î Q ( qz > q ¢z ¢) Þ| z |>| z ¢ |,
(2)
которая с очевидностью выполняется для любых чисел z , z¢ Î R.
Положим,
K ( x , x ) = {i Î N m : | Ci x | £ | Ci x |}.
0
0
0
0
m
0
Очевидно, что K ( x , x ) ¹ Æ, если x Î P ( C ). Для любого i Î K ( x , x ) введем
обозначения
a i ( x , x ) = min{bi ( x , x , q ) : q Î Q},
0
0
0
0
bi ( x , x , q ) =
| Ci ( qx + x ) |
0
|| qx + x ||1
.
Теорема. Для радиуса устойчивости любого эффективного разбиения x
0
векторной
m
задачи Z (C ), m ³ 1 справедлива формула
m
0
r (x , C) =
n
min
0
0
max a i ( x , x ).
0
(2)
0
xÎQ \{ x , - x } iÎK ( x , x )
Доказательство. Для краткости правую часть формулы (2) обозначим через j. Нетрудно
видеть, что число j ³ 0 конечно.
m
0
Переходя к доказательству неравенства r ( x , C ) ³ j, будем предполагать, что j > 0
(в
противном
случае
неравенство
m
0
r (x ,C) ³ j
в соответствии с определением числа j
очевидно).
Пусть
заключаем, что для любого
C¢ Î W (j).
n
Тогда
0
0
x Î Q \ {x , - x }
0
существует такой индекс k Î K ( x , x ), что
|| C ¢ ||¥ < j £ a k ( x , x ).
0
Учитывая неравенство a k ( x , x ) > 0, легко выводим
0
| Ck x 0 | < | Ck x | .
Отсюда, полагая
s k = sg Ck x ,
(3)
МАТЭМАТЫКА
13
===========================================================================
убеждаемся в справедливости равенств
C k ( qx + s k x ) = | Ck ( s k qx + x ) |, q Î Q.
0
0
Поэтому, используя (3), имеем
0
0
0
0
(Ck + Ck¢ )( qx + s k x ) = | Ck (s k qx + x ) | +C k¢ s k (s k qx + x ) ³ | Ck ( s k qx + x ) | - || C ¢ ||¥ × || s k qx + x ||1 >| Ck ( x + s k qx ) | -b k ( x , x , s k q ) || s k qx + x ||1 = 0.
0
0
0
0
Таким образом, находим
(Ck + Ck¢ )s k x > (Ck + Ck¢ ) qx , q Î Q.
0
Откуда, вследствие указанной выше импликации (1), получаем
| (Ck + Ck¢ ) x |>| (Ck + C k¢ ) x |,
0
0
m
что влечет x Î P ( C + C¢).
Резюмируя вышесказанное, заключаем, что для всякой матрицы C¢ Î W ( j) разбиение
0
m
0
m
x Î P ( C + C¢). Следовательно, r ( x , C ) ³ j.
0
m
Остается доказать неравенство r ( x , C ) £ j. Согласно определению числа j , существует
*
n
0
0
0
*
такое разбиение x Î Q \ { x , - x }, что для всякого индекса i Î K ( x , x ) выполняются
неравенства
0 £ a i ( x , x ) £ j.
0
*
(4)
0
m
Пусть e > j. Тогда докажем существование матрицы C¢ Î W ( e ) с условием x Ï P ( C + C¢).
Будем использовать обозначения
0
*
0
*
N ( x , x ) =| { j Î N n : x j = 1 Ù x j = -1} |,
0
*
0
*
M ( x , x ) =| { j Î N n : x j = x j } |,
*
s i = sg Ci x
*
.
Легко видеть, что выполняются неравенства
0
*
*
0
M ( x , x ) = M ( x , x ),
2( N ( x , x ) + N ( x , x )) = || x - x ||1 ,
0
*
*
0
0
*
2 M ( x , x ) = || x + x ||1 .
0
*
0
*
(5)
(6)
Для построения всех строк Ci¢ , i Î N m необходимой матрицы C ¢ рассмотрим четыре
возможных случая.
Случай 1: i Î K ( x , x ), bi ( x , x , -1) < bi ( x , x ,1). Тогда из (4) следует, что
0
*
0
*
0
*
| Ci ( x + x ) | > 0,
0
*
bi ( x , x , -1) £ j < e.
0
*
ВЕСНІК МДПУ
14
===========================================================================
Откуда, полагая
¢ ),
Ci¢ = ( ci¢1 , ci¢2 , K , cin
где
ìs*i di ,
ï *
= í -s i di ,
ï0
î
ci¢j
0
*
если x j = 1, x j = -1,
0
*
если x j = -1, x j = 1,
в противном случае,
j < d i < e,
имеем || Ci¢ ||¥ = d i и, согласно равенству (5), выводим
*
0
*
*
*
0
*
*
0
0
*
s i (Ci + Ci¢ ) x - s i (Ci + Ci¢ ) x = s i Ci ( x - x ) + 2d i ( N ( x , x ) + N ( x , x )) ³
³ - | Ci ( x - x ) | +di || x - x ||1 > - | Ci ( x - x ) | +bi ( x , x , -1) || x - x ||1 = 0,
0
*
0
*
0
*
0
*
0
*
s i (Ci + Ci¢ ) x + s i (Ci + Ci¢ ) x = si Ci ( x + x ) =| Ci ( x + x ) |> 0.
*
0
*
*
*
0
*
0
*
Поэтому справедливы неравенства
s i (Ci + Ci¢ ) x > s i (Ci + Ci¢ ) qx , q Î Q.
*
0
*
*
Отсюда с учетом (1) находим, что
| (Ci + Ci¢ ) x | > | (Ci + Ci¢ ) x | .
0
*
(7)
*
n
0
0
Заметим, что неравенство (7) согласуется с условием x Î Q \ { x , - x }.
Случай 2: i Î K ( x , x ), bi ( x , x , -1) > bi ( x , x ,1). Тогда, согласно (4), имеем
0
*
0
*
0
*
| Ci ( x - x ) | > 0,
0
*
bi ( x , x ,1) £ j < e.
0
*
Поэтому, конструируя строку C¢i по правилу
ci¢j
ì -s*i di , если x 0j = x*j = 1,
ï *
0
*
= ís i d i ,
если x j = x j = -1,
ï 0 в противном случае,
î
где j < di < e, получаем || Ci¢ ||¥ = di и, воспользовавшись (6), выводим
*
0
*
*
*
0
*
0
*
-s i (Ci + Ci¢ ) x - s i (Ci + Ci¢ ) x = -s i Ci ( x + x ) + 2d i M ( x , x ) >
> - | Ci ( x + x ) | +bi ( x , x ,1) || x + x ||1 = 0,
0
*
0
*
0
*
*
*
*
0
*
*
0
*
0
-s i (Ci + Ci¢ ) x + si (Ci + Ci¢ ) x = s i Ci ( x - x ) =| Ci ( x - x ) |> 0 .
Итак, верны неравенства
-s i (Ci + Ci¢ ) x > s i (Ci + Ci¢ ) qx , q Î Q , в
*
0
*
*
МАТЭМАТЫКА
15
===========================================================================
которые благодаря (1) приводят к (7).
0
*
0
*
0
*
0
*
Случай 3: i Î K ( x , x ), bi : = bi ( x , x , -1) = bi ( x , x ,1) = a i ( x , x ).
Рассмотрим два варианта.
Пусть сначала bi = 0. Тогда
Ci x = Ci x = 0.
0
*
*
(8)
0
Имея в виду x ¹ ± x , легко видеть, что можно выбрать два индекса k , p Î N n
с условием
*
0
*
0
xk = xk , x p ¹ x p .
¢ ) по правилу
Поэтому, задавая компоненты вектора Ci¢ = ( ci¢1 , ci¢2 , K , cin
cij¢
ì xk0 di ,
ï 0
= í x p di ,
ï0
î
если j = k ,
если j = p ,
в противном случае,
где
0 £ j < d i < e,
убеждаемся, что || Ci¢ ||¥ = di и ввиду (8) верно неравенство (7).
Пусть теперь bi > 0. Тогда, повторяя все рассуждения первого случая, получаем (7).
0
*
Случай 4: i Î N m \ K ( x , x ). Тогда, полагая C¢i = 0
( n)
, вновь имеем (7).
В результате всех этих построений получаем матрицу C ¢ с нормой
|| C ¢ ||¥ = max{di : i Î N m } < e.
Резюмируя, заключаем, что в случае, когда e > j, существует матрица C¢ Î W ( e )
0
m
m
0
с условием x Ï P ( C + C¢). Следовательно, r ( x , C ) £ j.
Теорема доказана.
Замечание 1. Если элементами матрицы C = [cij ] Î R
m´ n
являются положительные числа
и в процессе возмущений они остаются положительными, то радиус устойчивости эффективного
0
m
разбиения x Î P ( C ) равен числу
min{j, cmin },
где j – правая часть формулы (2), cmin = min{cij : (i , j ) Î N m ´ N n } .
Эффективное разбиение x
0
m
m
0
из P ( C ) назовем устойчивым, если r ( x , C ) > 0,
n
0
0
и особым, если в Q не существует такого вектора x ¹ ± x , что f ( x , C ) £ f ( x , C ) .
Следующий критерий с очевидностью вытекает из теоремы.
0
m
m
Следствие. Разбиение x Î P ( C ) задачи Z ( C ) устойчиво в том и только в том
случае, когда оно особое.
Замечание 2. Как правило (см., например, [7, 11]), строгая эффективность (оптимальность,
по Смейлу [16]) решения векторной дискретной задачи) является достаточной, а в случае
линейной – задачи и необходимым условием устойчивости эффективного решения. Однако легко
ВЕСНІК МДПУ
16
===========================================================================
m
видеть, что никакое эффективное разбиение задачи Z ( C ) не является строго эффективным.
Тем не менее такие разбиения могут быть устойчивыми (см. следствие).
Литература
1. Ehrgott, M. A survey and annotated bibliography of multiobjective combinatorial optimization
/ M. Ehrgott, X. Gandibleux // OR Spectrum. – 2000. – V. 22, № 4. – P. 425–460.
2. Greenderg, N. J. An annotated bibliography for post-solution analysis in mixed integer and combinatorial
optimization / N. J. Greenderg // D. L. Woodruff editor, Advances in Computational and Stochastic Optimization, Logic
Programming and Heuristic Search. – Boston : Kluwer Acad. Publ. – 1998. – P. 97–148.
3. Сергиенко, И. В. Математические модели и методы решения задач дискретной оптимизации
/ И. В. Сергиенко. – Киев : Наукова думка, 1988. – 471 с.
4. Сергиенко, И. В. Исследование устойчивости и параметрический анализ дискретных
оптимизационных задач / И. В. Сергиенко, Л. Н. Козерацкая, Т. Т. Лебедева. – Киев : Наукова думка, 1995. – 172 c.
5. Сергиенко, И. В. Задачи дискретной оптимизации. Проблемы, методы решения, исследования
/ И. В. Сергиенко, В. П. Шило. – Киев : Наукова думка, 2003. – 261 c.
6. Сотсков, Ю. Н. Теория расписаний. Системы с неопределенными числовыми параметрами
/ Ю. Н. Сотсков, Н. Ю. Сотскова. – Минск : НАН Беларуси, 2004. – 290 с.
7. Емеличев, В. А. Устойчивость в векторных комбинаторных задачах оптимизации / В. А. Емеличев,
К. Г. Кузьмин, А. М. Леонович // Автоматика и телемеханика. – 2004. – № 2. – С. 79–92.
8. Emelichev, V. A. The stability radius of an efficient solution in minimax Boolean programming problem
/ V. A. Emelichev, V. N. Krichko, Yu. V. Nikulin // Control and Cybernetics. Warszawa. – 2004. – Vol. 33,
№ 1. – P. 127–132.
9. Емеличев, В. А. О радиусе устойчивости лексикографического оптимума одной векторной задачи булева
программирования / В. А. Емеличев, К. Г. Кузьмин // Кибернетика и системный анализ. – 2005. – № 2. – С. 71–81.
10. Емеличев, В. А. Анализ чувствительности эффективного решения векторной булевой задачи
минимизации проекций линейных функций на R + и R - / В. А. Емеличев, К. Г. Кузьмин // Дискретный анализ
и исследование операций. Сер. 2. – 2005. – Т. 12, № 2. – С. 24–43.
11. Emelichev, V. A. Stability analysis of the Pareto optimal solution for some vector boolean optimization
problem / V. A. Emelichev, K. G. Kuz'min, Yu. V. Nikulin // Optimization. – 2005. – Vol. 54, № 6. – P. 545–561.
12. Емеличев, В. А. О радиусе устойчивости эффективного решения одной векторной задачи булева
программирования в метрике l1 / В. А. Емеличев, К. Г. Кузьмин // Доклады РАН. – 2005. – Т. 401, № 6. – C. 733–735.
13. Емеличев, В. А. Конечные коалиционные игры с параметрической концепцией равновесия в
условиях неопределенности / В. А. Емеличев, К. Г. Кузьмин // Известия РАН. Теория и системы управления.
– 2006. – № 2. – С. 96–101.
14. Lawler, E. L. Sequencing and scheduling : Algorithms and complexity / E. L. Lawler // Handbook of
Operations Research. Amsterdam. – 1993. – Vol. 4. – P. 445–452.
15. Pareto, V. Manuel d'économie politique / V. Pareto. – Paris : Giard, 1909.
16. Smale, S. Global analysis and economics. V. Pareto theory with constraints / S. Smale // J. Math. Econ. –
1974. – Vol. 1. – P. 213–221.
Summary
A formula of the stability radius of efficient solution for the vector combinatorial partition
problem is obtained.
Поступила в редакцию 28.03.06.
УДК 517.986
М. А. Романова
ВЫЧИСЛЕНИЕ ПРОСТРАНСТВА МАКСИМАЛЬНЫХ ИДЕАЛОВ И ГРАНИЦЫ ШИЛОВА
НЕКОТОРЫХ АЛГЕБР ОБОБЩЕННЫХ АНАЛИТИЧЕСКИХ ФУНКЦИЙ
Впервые рассмотрев в работе [1] обобщенные аналитические функции на пространствах
полухарактеров полугрупп, американские математики Р. Аренс и И. Р. Зингер положили начало
интересной теории, которая в дальнейшем не осталась незамеченной многими авторами (см., например,
монографии [2], [3], а также обзоры [4], [5] и [6]). Целью данной работы является вычисление
Документ
Категория
Без категории
Просмотров
4
Размер файла
266 Кб
Теги
решение, векторное, комбинаторные, радиус, эффективного, разбиение, устойчивость, задачи
1/--страниц
Пожаловаться на содержимое документа