Функционально-аналитические представления общего перестановочного множества

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

17. Towards Unbiased Evaluation of Uncertainty Reasoning: The URREF Ontology: Information Fusion (FUSION), 2012 15th International Conference [Text]. — IEEE, 2012. — P. 2301−2308.
18. Krause, P. Representing Uncertain Knowledge: An Artificial Intelligence Approach [Text] / P. Krause, D. Clark. — Kluwer Academic Publishers, 1993. doi: 10. 1007/978−94−011−2084−5
19. Bouchon-Meunier, B. Les incertitudes dans les systemes intelligents [Text] / B. Bouchon-Meunier, H. T. Nguyen. — Press Universitaires de France, Paris, 1996.
20. Klir, G. Uncertainty-Based Information: elements of generalized information theory. Vol. 15 [Text] / G. J. Klir, M. J. Wierman- 2nd edition. — Verlag Berlin Heidelberg, 1999. — 178 p.
21. Smets, P. Imperfect information: Imprecision and uncertainty [Text] / P. Smets. — Uncertainty Management in Information Systems, 1997. — P. 225−254. doi: 10. 1007/978−1-4615−6245−08
22. Olive, A. Conceptual Modeling of Information Systems [Text] / A. Olive. — Springer Berlin Heidelberg, 2007. — P. 471. doi: 10. 1007/978−3-540−39 390−0
23. Литвин, В. В. Використaння aдaптивних онтологш в iнтeлeктуaльних систeмaх прийняття ршень [Текст] / В. В. Литвин,
B. Я. Крaйовський, Н. Б. Шaховськa // Схщно-бвропейський журнaл передових технологш. — 2009. — Т. 4, № 3 (40). -
C. 1−12. — Режим доступу: http: //journals. uran. ua/eejet/article/view/20 838/18477
-? ?-
Вводиться поняття функционального пред-ставлення множини, описуються тдходи до побу-дови таких представлень на прикладi загальног множини перестановок. Запропоновано класиф^ кацю функцюнальних представлень i побудовано строгi представлення загальног перестановоч-ног множини на базi спещальних властивостей симетричних функцш. Наведено вiзуалiзацiю та аналiз строгих представлень перестановок малог вимiрностi
Ключовi слова: функцюнальне представлен-ня множини, загальна множина перестановок, перестановочний многогранник, комбтаторна
оптимiзацiя
?-?
Вводится понятие функционального представления множества, описываются подходы к построению таких представлений на примере общего множества перестановок. Предложена классификация функциональных представлений и построены строгие представления общего перестановочного множества на основе специальных свойств симметричных функций. Приведена визуализация и анализ строгих представлений для перестановок малой размерности
Ключевые слова: функциональное представление множества, общее множество перестановок, перестановочный многогранник, комбинаторная оптимизация -? ?-
1. Введение
Одним из основных направлений исследований в области полиэдральной комбинаторики является построение выпуклых оболочек комбинаторных множеств и аналитическое описание соответствующих комбинаторных многогранников. При этом комбинаторные множества рассматриваются как свои образы при соответствующих отображениях (погружениях) в
(c)
УДК 519. 85
|РР1: 10. 15 587/1729−4061. 2016. 58 550|
ФУНКЦИОНАЛЬНО-АНАЛИТИЧЕСКИЕ ПРЕДСТАВЛЕНИЯ ОБЩЕГО ПЕРЕСТАНОВОЧНОГО МНОЖЕСТВА
О. С. Пичугина
Кандидат физико-математических наук Кафедра прикладной математики Харьковский национальный университет радиоэлектроники пр. Науки, 14, г. Харьков, Украина, 61 166 Е-mail: pichugina_os@mail. ru С. В. Яковлев Доктор физико-математических наук, профессор Кафедра информационных технологий и защиты информации Харьковский национальный университет внутренних дел пр. 50-летия СССР, 27, г. Харьков, Украина, 61 080
Е-mail: svsyak@mail. ru
арифметическое евклидово пространство. Такой класс множеств в литературе часто называется евклидовыми комбинаторными множествами [1, 2].
В настоящее время получены аналитические описания таких комбинаторных многогранников как многогранник перестановок и четных перестановок [3], общий перестановочный многогранник [1, 2], общий многогранник размещений [2], модульный многогранник [4], многогранник булевого множества [5],
многогранник Биркгофа [6] перестановочных матриц, многогранники некоторых классов сочетаний [7] и соответствующих полимножеств [2].
Особый интерес в задачах комбинаторной оптимизации вызывают вершинно-расположенные множества, т. е. множества, совпадающие с крайними точками (вершинами) своих выпуклых оболочек (многогранников).
Одним из наиболее интересных классов вершин-но-расположенных множеств является общее множество перестановок [1, 3]. Именно поэтому актуальной задачей является исследование подходов к его функционально-аналитическому описанию, что и является предметом настоящей статьи. Решение такой задачи существенно расширяет возможности применения как классических, так и специальных методов непрерывной оптимизации к решению дискретных оптимизационных задач.
2. Анализ литературных данных и постановка задачи
Рассмотрим задачу дискретной оптимизации в следующей постановке:
f (x) ^ min, x eE с Rn, где Е — дискретное множество:
1 & lt-.
(1) (2)
(3)
Будем считать, что множество Е вершинно-распо-ложенное, т. е.
E = vert conv E.
(4)
Осуществим эквивалентную формулировку дискретной задачи (1)-(4) как задачу нелинейного программирования, представив множество Е системой соответствующих уравнений и неравенств.
Таким образом, исходная дискретная задача формулируется в непрерывной постановке [8−10]. При этом возникает необходимость аналитического описания условия дискретности, т. е. явного задания аналитического вида функций, входящих в систему уравнений и неравенств.
Введем следующие обозначения. Пусть — Р — выпуклая оболочка Е (Р = сопу Е, комбинаторный многогранник множества Е):
P = {x: Ax & lt- b} ,
(5)
— S — описанная вокруг Е выпуклая поверхность, т. е. Е с S ,
S = {x: f1 (x) = 0}, f1 (x) — выпуклая.
(6)
Множество Е представим в виде пересечения многогранника (5) и поверхности (6):
Таким образом, для аналитического задания Е достаточно, с одной стороны, получить систему многогранника (5), а с другой стороны, — явный вид поверхности (6).
В результате исходная задача сводится к описанию комбинаторного многогранника Р и аналитическому описанию поверхности S.
Замечание 1. Формирование комбинаторных многогранников — это основная задача, решаемая в полиэдральной комбинаторике [11, 12]. На сегодняшний день она решена для таких евклидовых комбинаторных множеств как множество перестановок [1, 3, 13] и его обобщений, таких как общие перестановочное и полиперестановочное множества [1, 2, 14]- для общих множеств размещений и полиразмещений [2], отдельных классов сочетаний [7], некоторых 0−1-множеств [5] таких как множество перестановочных матриц [6] и т. п.
Вторая задача состоит в поиске выпуклых функций, принимающих постоянные значения на Е. Для однозначного описания множества S можно сформулировать дополнительные условия, такие как [1, 14, 15]:
— выбор сферы минимального радиуса-
— поиск поверхности минимальной площади-
— поиск поверхности, ограничивающей выпуклое тело минимального объема и т. п.
Заметим, что многообразие выбора поверхностей (6) приводит к различным представлениям (5)-(7). Например, дискретные множества можно представить пересечением нескольких поверхностей.
Продемонстрируем такую возможность на примере булевого множества Вп ={0,1}. Известно, что его многогранником является единичный гиперкуб, вписанный в сферу с центром (0. 5) радиуса т. е. его представление (5)-(7) имеет вид:
Bn =]xeRn: 0& lt-x<-1 x, -1] = 4f,
(8)
С другой стороны, данное множество можно представить в виде [10]:
Bn ={xeRn: xf-x, = 0, ie Jn}, Jn ={1,…, n} ,
(9)
E = P n S.
(7)
т. е. (9) — еще один способ аналитического задания комбинаторного множества Вп.
Заметим, что (9) может быть переписано в виде:
Е = {х еГ: ^(х) = 0, ] е ]а }, (10)
где
Е = ^ ^(хКЧ ]е]п.
Оба приведенных представления Вп находят широкое применение в булевой оптимизации [10]. Так представление (8) используется в вогнутых методах [10], а представление (9) — в методах штрафных функций [16] решения задачи (1), (2) на Е = Вп.
Поставленная задача функционально-аналитического (или просто функционального) представления дискретного множества (4) является непосредственным обобщением обоих приведенных способов.
Все вышеперечисленные в замечании 1 комбинаторные множества вершинно расположены и вписаны в сферу за исключением общего множества размещений. Среди множеств ЕПк^) п-размещений из мультимножества G из п элементов, к из которых различны, существует два подкласса вершинно расположенных, один из которых — ЕП2^) — вписан в сферу, другой — ЕЩ+1к^) — в эллипсоид. Таким образом, поскольку аналитический вид соответствующих многогранников известен, для этих вершинно расположенных множеств представления (5)-(7) известны.
Заметим, что число ограничений в системах уравнений и неравенств комбинаторных многогранников может быть достаточно большим. Это затрудняет применение в вычислительных схемах представлений (5)-(7) и требует разработки специальных приемов, позволяющих использовать число ограничений системы (5), сравнимое с размерностью пространства. Среди них метод последовательного подсоединения ограничений [2] и полиэдрально-сферическом метод [17], в котором используется подсистема ограничений многогранника, служащих правильными отсечениями точек на описанной сфере.
Данная особенность касается, в частности, общего перестановочного множества Епк^), число ограничений которого достигает 2п -1 [3]. В то же время, представление (10) содержит всего п ограничений, и было бы интересно получить его для как для Епк^), так и для других евклидовых комбинаторных множеств.
3. Цель и задачи исследования
Целью работы является построение различных функциональных представлений дискретного множества на примере общего перестановочного множества.
Для достижения указанной цели были поставлены следующие задачи:
— обобщение аналитических представлений дискретных множеств евклидового пространства, в т. ч. евклидовых комбинаторных множеств-
— классификация функциональных представлений-
— описание оригинальных подходов функционального представления общего перестановочного множества-
— анализ и визуализация полученных представлений перестановок.
4. Функциональные представления множеств
Функциональным назовем представление множества Е с помощью функциональных зависимостей вида
$(х) = 0,] е. 1 т, $(х) & lt- о, ] е
В зависимости от типа функций (11), (12) функциональные представления могут быть линейные и нелинейные, непрерывные, дифференцируемые, гладкие, выпуклые и т. п.
В обозначениях
I оп К (х) = 0, ]е^ I
М- = --хеЯп:^ },
] I Н (х) & lt- 0, ] е ^ и
представление (11), (12) может быть переписано в виде:
Е= п М,. (14)
Т 1
Введем еще несколько типов таких представлений. (11)-(12) назовем:
а) строгим представлением, если
т = т ,
(15)
иначе нестрогим-
б) неизбыточным представлением Е, если извлечение любого из ограничений (11)-(12) приводит к нарушению (14):
V ]е Т пМ, *Е,
1* -
(16)
(11) (12)
иначе избыточным-
в) ограниченным представлением Е, если среди (13) есть ограниченные множества:
3] е. т, ^& gt-0, е Я& quot-: М] с С (а-) = conv (а-), (17)
иначе неограниченным-
Замечание 2. Функциональное представление может обладать теми или иными свойствами в разных областях Яп, поэтому, в случае необходимости, указывается его тип и область.
5. Подходы к построению функциональных представлений множеств
Приведем два таких подхода, в первом из которых используются, прежде всего, свойства линейных функций на ЕКМ, во втором — нелинейных.
Полиэдрально-поверхностный подход — это построение представления (5)-(7) в результате формирования системы комбинаторного многогранника (7) и произвольной описанной поверхности (6). В результате строится нестрогое, нелинейное, выпуклое представление. Если при этом система (7) неизбыточна, то (5)-(7) будет также неизбыточным представлением данного комбинаторного множества.
Данный подход называется полиэдрально-поверхностным, поскольку основным его этапом является аналитическое задание комбинаторного полиэдра, второстепенным — поиск выпуклой поверхности.
Как видно, полиэдрально-поверхностный подход основан на свойствах линейных функций на евклидовых комбинаторных множествах. Следующий подход, напротив, основан на исследовании свойств нелинейных функций на этих множествах и возможности формирования дискретных множество в результате пересечения этих поверхностей.
Мультиповерхностный подход состоит в формировании дискретного множества из строгой части (11) функционального представления с последующим от-
сечением, в случае необходимости, недопустимых точек при помощи ограничений нестрогой части (13).
Если, к примеру, известен класс функций, обладающий специфическими свойствами на Е, то возникает вопрос, достаточно ли функций в нем, чтобы сформировать функциональное представление Е. Если да, какие из них задают неизбыточное представление.
При ответе на первый вопрос наиболее сложным является доказательство, что в результате формируется именно данное множество, т. е. выполнено (14). В противном случае сформированная часть функциональных представлений дополняется функциями других классов.
Продемонстрируем применимость перечисленных подходов к построению функциональных представлений и возможность с их помощью построения строгих функциональных представлений вида (10) на обобщении множества перестановок [1, 3, 13] - общем перестановочном множестве [1, 2, 14].
6. Непрерывные представления общих перестановок
Пусть Л = Л и|0}, Sr (а) — сфера радиуса г с центром в точке а.
Рассмотрим в качестве Е евклидово множество общих перестановок [1, 2, 14] из мультимножества —
Е = Епк:
вочного многогранника [2, 18] и семейство описанных вокруг него сфер известны [1].
Утверждение 1. При выполнении условия (18) следующая система задает нестрогое неизбыточное функ-
циональное представление множества
Епк
IX?=? g?,
IX, = 1 а,
(21)
(2?)
Iха_ & gt-1 У|а,}, = гас
1=1 1=1
с АА ||2,…, п1 — 1},{п — пк,…, п — 2}}.
(23)
Доказательство. С одной стороны, (22)-(23) представляет собой неизбыточную систему многогранника Рпк (G) [18]. С другой стороны, (21) — это уравнение сферы Sr (О) радиуса
I g?
½
V 1=1
с центром в начале координат, описанной вокруг Епк (G) [1]. В совокупности, (21)-(23) задают функциональное представление (7) множества Епк (G):
G = |g'- },. -п =1епк е'- & lt- е'-+1, 1 е •]к-1.
Будем полагать, что (3) выполнено, откуда к & gt- 1.
Епк И = Sr (О)п Рпк.
(24)
(18)
6. 1. Одно функциональное представления Еп
Частным случаем Епк^) является множество Еп = ЕпОп) перестановок из первых п натуральных чисел [1, 3, 13], для которого в [15] предложено следующее функциональное представление:
I (1 — соз (2^)) = 0 ,
1 & lt- х, & lt- п, (X, — хр2 & gt- 1, 1 & lt- 1,] е А
(19)
(20)
Здесь (19) задает целочисленную решетку, а (20) обеспечивает выбор векторов с различными координатами в пределах [1,п], поэтому обобщение данного представления на общий случай Епк невозможно.
Представление (19), (20) — пример применения мультиповерхностного подхода (п. 5) к построению функциональных представлений, когда дискретное множество задается при помощи (19), а потом недопустимые точки Еп отсекаются нелинейными ограничениями (20).
Назовем это полиэдрально-поверхностное представление Епк его полиэдрально-сферическим представлением. Представление (24) неизбыточное, поскольку:
— извлечение (21) приводит, в силу (18), к рассмотрению невырожденного многогранника вместо дискретного множества-
— извлечение любого из ограничений системы (22)-(23) также невозможно без изменения допустимой области в силу ее неизбыточности.
Утверждение доказано.
Поскольку п — 2-сфера, описанная вокруг Епк задается неединственным образом [1], найдено целое семейство подобных функциональных представлений:
Следствие 1. Уа е Я система (22)-(23), (25):
I (х, — а)2 = ^ (& amp- - а
(25)
задает неизбыточное представление Епк
В данном семействе особый интерес представляет, наряду с базовым представлением (21)-(24), представление, содержащее сферу Smln минимального радиуса [1], соответствующую параметру а:
1 А
а = -! g1.
(26)
6. 2. Полиэдрально-поверхностный подход к построению функциональных представлений Епк
Данный подход применим для общего множества перестановок, поскольку система общего перестано-
6. 3. Мультиповерхностный подход к построению функциональных представлений Епк
Следующие теоремы показывают применимость поверхностно-многогранного подхода (п. 5) к постро-
ению представлений множества Епк ©, а именно обосновывают существование двух непрерывных строгих функциональных представлений, одно из которых также является выпуклым в Яп+ для генерирующего мультимножества С:
G & gt- 0.
I П х,
jеN
принимающие на Епк © значения
!, 1 I Пе. !
,=1jеN [^п'-Ж1™ ] jеN
соответственно.
Выдвинем гипотезу, что как из
I х. = 18. !
1=1 1=1 ^
I П х, = I П
(c)с.п 1ею (c)с.п 1ею
jеN
I xj = I 81, ] е. п-
1=1 1=1
I П х = I П j е .п.
(c)с.п ,|ю|=j 1ею & gt-1 ®Н 1е®
8 = (81
а также системы функций:
а (х) ={^(х)^е.п ,
где
(27)
Итак, известно, что симметричные многочлены принимают постоянное значение на общих перестановках [19], т. е. они могут потенциально служить основой для построения функциональных представлений Епк©. Попробуем сформировать такие представления из этих функций. Остановимся на классе симметричных полиномов, в котором рассмотрим два подкласса
I х1!
1=1jеN
можно сформировать строгие представления. Соответственно, следующим предположением будет то, что первые п уравнений данных систем задают эти представления.
Итак, предположение состоит в том, что каждая из следующих систем задает функциональное представление Епк (С):
(28) (29)
Введем в рассмотрение вектор 8, соответствующий мультимножеству С:
^(х)=! xj, -?-
1=1
Н (х) ={^(х)}, е,0 ,
где
Ц (х) = I П е. п- Ьс (х) = 1.
(31)
(32)
(33)
(34)
В этих обозначениях системы (28), (29) переписываются, соответственно, следующим образом:
А (х^) = {^(х) =
в (х, 8) = {^(х) =
(35)
(36)
Лемма 1. Система функций (33) может быть получена рекуррентно с использованием функций (31) следующим образом:
Ц (х) =1 ^(-1)1−1Я1(х)-Ьн (х), ] е .п J 1=1
(37)
с базой Ь0(х), я1(х), где я1(х) определяется из (32). Доказательство.
а. При ] = 1 формула (37) приобретает вид:
Ь1(х) = ! Ч1(х)'- Ь1−1(х) = Ч1(х)
1=1
и справедлива, поскольку, согласно (31), (33):
^(х) = Ь^х) = IП х- I х1 = ^ = ^(х). (38)
(c)с.п 1е© 1=1
Ы=1 Ы=1
Ь. Для ] = 2 (34) имеет вид:
Ц (х) = Ь2(х) =IП Xl=I х^.
Ы=2
Формула (37) приобретает форму:
Ь2(х) = 1 ^(-1)1−1Я1(х)-^2−1 (х) = 2 1=1
1
= 2 Ых)'- Ь1(х) — Ч2(х)-Ь0(х)) = 1
=2 Ых)-Ь1(х) — Ч2(х)).
(39)
(40)
Покажем, что (40) справедлива. С учетом (32), (38), (39), имеем:
так и из
2 Ых) Ь1(х) — q2(x))= = 12(Ых))2 -q2(x)) = 12
/ (п ^ 2
XX -^х2
к 1=1 1=1
Цх2 + 2^ х, хг]-]Гх21 = X х, х,. = Ь2(х), V 1=1 1& lt-1'- у 1=1 у 1& lt-1'-
Следствие 2. Система функций (31) может быть получена из системы (33) с помощью рекуррентного соотношения:
^(х) = (-1)^"+

+Х (-1)1-Ц-,(х) ,]е]".
(43)
что и требовалось доказать. с. ] = 3:
Ц (х) = Ь3(х) = X Пх1 = X х1×1'-х1& quot-.
(c)=3
(41)
Докажем справедливость (37) в этом случае. Для этого покажем, что выполнено:
Ьэ (х) = 1 Х (-1)'--1lqi (x)¦ Ь3−1(х) =
3 1=1
1
= 3 Ых)-Мх) — q2(x)¦ Ь1(х)+q3(x)¦ Ь0(х)) = = 3 (ql (x)¦ Ь2(х) — ^(х) ^(х) + q3(x)). (42)
и базы q0(x), Ь1(х).
Доказательство. Сформируем систему (31), выражая из (37) функцию qj (x) через {Ь1,:
0 = ^ Ц (х) — 1)1−1Ч (х& gt- Ьн (х) =
1=1
= ^(х) + 1)1^(х)^ Ц-?(х) =
1=1
= Цх) + ХХ (-1)Ч (х& gt- Ц-1(х)+(-1)^(х& gt- Ьо (х) =
1=1
= Цх) + ХХ (-1)Ч (х)-Ц-1(х)+(-1)^(х).
Поделив обе части на (-1)-1, получим в точности (43), что и требовалось.
Преобразуем правую часть (42) с учетом (32), (41): Теорема 1. Системы А (х^), В (х^) вида (35), (36)
эквивалентны, т. е. х* - решение (28) ^ х* - решение (29).
Доказательство.
Необходимость. Покажем, что если х* -решение (28), то х* - решение (29). В обозначениях (35), (36) это выглядит следующим образом:
1
^Ых)-Ь2(х)-q2(x)¦ Ь1(х)+qз (x))=
3
X х1ХП X х2 ХП *+Х х3
1=1 (c)^п Ге© 1=1 (c)^п Ге© 1=1
(c)=2 |(c)=1
X х1 ¦X х, хг -X х2 X Xi'- + X х3
V 1=1 Г& lt-Г 1=1 1=1 1=1 у
X х
X х1'-х1& quot-+X х1'-х1& quot-
-X х2
/
^ +X хг
-X х3
V 154 /
?
^(х*) = (]е Jn) ^
=& gt-Ц (х*) = hj (g) (] е Jn). (44)
Перепишем системы (35), (36) в виде:
X х X х1'-х1& quot-"-
X х X хх--Xх2 X хг
-X х3 +X х3
V 1=1 1=1 у
А (х^) = {А. Хх^)}^ ,
A. j (x, g) = {^(х) = qj (g)}, j е Jn- (45)
X X х1×1'-х1. + X х1×1'-х1. + X х1×1'-х1.
V 1=1 1& lt-г<-г г& lt-кг 1'-& lt-1"-<-1 /
/ / Л Л
X *
1=1
V, к '-='- 1
X х1'-х1-+X хх-
& lt-1 1 & lt-1
-X х2 X х.
3 ¦ X х^х,. -
X х2 X х- +X хг -X х2 X хг
1-. П
= X х1×1×1& quot- х2 ¦ X х-X хг =X х1×1'-х1& quot-=Ь3(х). 31=1
V1 я 1 я у
В (х^) = {В. Хх^)^,
B. j (x, g) = {Ц (х) = hj (g)}, j е Jn. (46)
Заметим, что, учитывая обозначения (31), (33), левая часть (45), (46) совпадает с Ц (х), Н (х), правая — с Ц^), Н^), соответственно.
Введем в рассмотрение уравнения: (I) Цх) = а, (II) ^(х) = Ь,
Получена левая часть (42), что и требовалось доказать. а также операции умножения уравнения на число и Для 3 & lt- ] & lt- п доказательство аналогично. умножения двух уравнений:
к ¦ (I): к ¦ Цх) = к ¦ а-
х еЕ = Епк© ^ х еБ,
(I) (II): fI (x)¦ ^(х) = а¦ Ь.
Б =]х еЯп: I ^ = ! 81'-
1=1 1=1
Будем формировать систему В (х, 8) по системе А (х, 8), осуществляя над уравнениями рекуррентные подстановки (37) при х = 8 ((30)).
Поскольку последовательность преобразований (37) не зависит от х, для обеих частей уравнений (36) и над самими уравнений она идентична. С учетом (45)-(47) получаем, что система (36) может быть получена рекуррентно из системы (35) следующим образом:
В. Хх, 8) =1 ^(-1)1−1А. 1(х, 8) ¦ В.(] - 1)(х, 8), ] е .п. (48) J 1=1
База В. 0(х, 8), А. 1(х, 8) системы (48) определяется из (45), (46):
В. 0(х, 8) = {1 = 1}-
А. 1(х, я) = ^ (х) = ,
откуда имеем — если х* удовлетворяет А (х*, 8) = х* удовлетворяет В (х*, 8). Учитывая обозначения (45), (46), получаем (44), что и требовалось доказать.
Достаточность. Если х* - решение (29), то х* -решение (28).
В обозначениях (35), (36) это означает необходимость показать, что
Ц (х*) = ^(8) (] е. п) =1 ^(х*) = ^(8) (] е. п).
Аналогично вышеприведенному и согласно (43), формируем систему (45) рекуррентно, используя (46):
А. Хх, 8) = ] ¦ (-1)-^В. Хх, 8) +
±Ц (-1)1^+1А. 1(х, 8)¦ В. а- 1)(х, 8),]е.п. (49)
1=1
База системы (49), согласно (45), (46):
A. 0(х, 8) = {1 = 1},
B. 1(х, 8) = {^(х) = Ь^)}.
Аналогично вышесказанному, получаем — если х* удовлетворяет В (х*, 8) = х* удовлетворяет А (х*, 8), т. е. в обозначениях (45), (46) это означает справедливость (43).
Теорема доказана.
Теорема 2. Точка является элементом общего множества перестановок Епк© тогда и только тогда, когда она является решением (28), т. е.
Доказательство. С учетом теоремы 1, можно перейти к рассмотрению эквивалентной к (28) системы (29) и доказать:
хеЕ = Епк (С)^ хеБ'-,
(51)
Б'- =
: е Яп: I П х =!П 8
мс.п 1ем
1мИ
мс.п 1ем
1мН
jеJn
= {х еГ: Н (х) = Н (8)}.
Необходимость:
?
х еЕ = Епк© = х еБ'-.
(52)
(53)
Согласно [19], произвольный симметричный полином Р (х) на Епк© принимает постоянное значение, равное Р (8), Р (х) = Р (8).
Епк (С)
Поскольку (34) — система симметричных многочленов, имеем:
УхеЕпк© ^(х) = ^(8) (е. п)
Епк (С)
или, в обозначениях (33), Н (х) = Н (8).
Епк (С)
Откуда, учитывая (52), получаем (53). Достаточность. Проверим справедливость:
х еБ'- = х еЕ = Епк©.
(54)
Доказательство проводится в 2 этапа. На Этапе 1 показываем, что координаты допустимых векторов хеБ'- являются элементами мультимножества С — на Этапе 2 — что координаты этих векторов в точности образуют С, т. о. эти вектора — элементы евклидового комбинаторного множества общих перестановок из С.
Этап 1. Перепишем систему (46) в явном виде, используя (34):
В (х, 8) = {В. Хх, 8)}

В. Хх, 8) = {Ц (х) = Ц (8)} =
!П х = !П ^
(c)с.п 1ем 1е®
М= мн
,]е. п
Учитывая, что Шс .п содержит лишь различные индексы, а также выражение (34), запишем эту систему в форме:
В. 1(х, 8) = ^? х1 = hl (g)J- В. 2(х, 8) = |X ^х^ h2(g)J- B. 3(x, g) ={X ХХх, = Ь3^)
В. (п — 2)(х, 8) =
XП х1 =
в. (п-l)(x, g)=|XП х = Ч^" —
B. n (x, g) = |п ЬпЦ.
о = hn (g) — х1 —
-Х1×1 (к^ - х1 (Ьп-э^ - х1 (… (Ь1^ - х1)))
= к^) — х1 + К^) х42 —
-hn-3(g) ¦ х? + … + (-1)п-1хп.
С учетом (55), имеем: хп — хп-1 +
+Ь2^)-хп-2 -… + (-1)п-1 ¦ hl (g) = 0.
(58)
Корни х (к), к е Jn, уравнения (58) определяются по формуле Виета и, в силу (34), они в точности образуют мультимножество G:
{х'-к1. ={81 к = G.
т. о. первая координата х1 принимает п значений
х1 е{х& lt-к)}

= G.
Сформируем из В. п (х, 8) уравнение п -го порядка по отношению к переменной
х = х1,
(55)
Выбирая в (55) вместо переменной х1 остальные переменные, х = Xj, j е Jn {1}, получим идентичные результаты. В итоге имеем:
исключая последовательно оставшиеся переменные с помощью В. Хх, 8), ] е Jn-1 и используя следующее свойство:
VIе Jn ХеНк) Ц = G.
(59)
Vi, е Jn П Х= - х^ПX.
(56)
Таким образом, показано, что координаты векторов-решений (52) суть элементы G, т. е.
Гги
хеО'- ^ ^ еС, ]е Jn.
(60)
В качестве Г используем 1, в результате чего (56) приобретет вид:
Этап 2. Покажем, что точка х = (х1). еО'- не только удовлетворяет (60), но и является перестановкой из С, т. е.
П X = - х XПх1, е Jn
(57)
1ега, 1 1=j
(c)И- 1ега
^ ^ М *п = С.
(61)
Индекс ] в В. Хх, 8) меняем последовательно, начиная с п и заканчивая 1. Так для ] = п рассматривается уравнение В. п (х, 8), которое может быть переписано, с использованием (57), в виде:
0 = Ьп (8) — П Х=Ьп (8) —
-хП х1 = А*^ - х1 1 п 1
Ьп-1(8) — X X Пх1

Поскольку, согласно теореме 1, области (50) и (52) совпадают (О = О'-), вместо (61) можно показать справедливость
?
х еО ^ х еЕпк©.
Доказательство проведем от противного. Предположим, х* еО, х* еС, 1 е Jn, при этом х* ^пк^Х т. е.
1=П-2
{х* }Ип ^ С.
(62)
= Ьп (8)-х1
Ьп-1(8) — х1

Ьп-2(8) — х1 X Пх1
|=п-3 1ега V 1ега у
= Ьп (8) — х1 V Ьп-^) — х1 (Ьп-2(8) — х1 (Ьп-3(8) — х1 (… (Ь^) — Упрощая последнее выражение, получаем:
Сформируем мультимножество координат х*: Х* = {x*}iеJ. С учетом предположения (62), имеем:
|С'-| = |С п Х*| = п'- & lt- п- |С& quot-| = |СС'-| = п& quot- = п — п'-& gt- 0.
Не ограничивая общности, считаем, что последние п'- координат х* являются подмножеством С, иначе переменные перенумеровываются.
Условие (62) теперь можно переписать в виде:
х* еБ, х* еС, 1 е. п,
^(х) = !П Х^П 81 = 0, ^ е. п
(67)
Зп& quot-е. п: {х1}
= С'-с С {х }. = С& quot- Ч0}.

Рассмотрим подсистему первых п& quot- уравнений (28):
I х? + ! x*j = I 81, j е. п"-.
х* еС& quot- х* еС'- 1=1
Учитывая (63), имеем:
I х? + ! = I + I 81, j е. п
х* еС& quot- еС'- 81 еС& quot- 81 еС'-
I х*]= I j е. п"-,
х* еС& quot- еС& quot-
Iх? = !j е. п"-.
1=1 1=1
Согласно первой части теоремы, примененной к С& quot- и х& quot- еЯп, имеем:
Ух& quot-еБ"- =Цxjj = Igjj, jе! = х& quot- еС& quot-, 1 е.
=1 1=1
Возьмем в качестве х& quot- = (х*)1е., откуда, в силу (64), получаем:
х* еС& quot-, 1 е.п.
^(х) = I х1 -181= 0, j е. п
мс.п 1ем
1мН
мс.п 1ем
1мН
(63)
т. е. получаем систему вида (28) для мультимножества С& quot- = & lt-&-}.
(64)
(65)
(65) противоречит (63), что и доказывает вторую часть теоремы 2.
Объединяя результаты теорем 1,2, получаем:
хеЕпк (С)^хеБ^ хеБ'-,
где Б, Б'- определяется из (50), (52), соответственно.
Как видно, получено два строгих представления (28) и (29) множества Епк©, которые в обозначениях (11) записываются следующим образом:
(66)
Отметим, что в оба этих представления входит (22), выражающее известное свойство точек Епк© расположенности на данной гиперплоскости. Помимо этого, в представление (66) входит также уравнение (21), выражающее вписанность Епк © в гиперсферу.
Остановимся детальнее на представлении (66) и проклассифицируем его (п. 4): по типу функций {^(х)} это нелинейное, непрерывное, дифференцируемое, более того гладкое представление.
Четные степени представления (66) {^(х)}
[п]
выпуклые функции- нечетные степени {^^(х)}
Ьт]
выпуклые Яп+ при выполнении (27), откуда видно, что
(66) — выпуклое представление Епк © в двух случаях:
a) при п = 2 УС в Яп-
b) при п & gt- 2 УС вида (27) в Яп+ (замечание 2). Поскольку т = т'- = п, представление (66) — строгое ((15)).
Замечание 3. На вопрос о неизбыточности (66) нельзя дать однозначный ответ, т.к., с одной стороны, для С = .4 оно будет таковым и Е4. С другой стороны, для С = {0,0,0,1} поверхности М3, М4 вида (13) вписаны в сферу М2. В свою очередь, М4 вписана в М3, т. о. (66) — избыточное, из которого может быть сформированы неизбыточные представления исключением некоторых ограничений (67).
Подобно следствию 1, на базе представлений (66),
(67) могут быть построены целые семейства строгих представлений заменой х1 ^ х1 — а, 1 е .п.
Следствие 3. Уа е Я каждая из следующих систем:
!(х-аУ-!(81 -аУ=0, j е. п, (68)
I П (х1 — а/-
мс.п ,| м= 1ем
— I П (81 — аУ= 0, — е. п, (69)
мс.п ,| м= 1ем
задает строгое представление Епк ©.
В частности, в (68) содержит уравнение Smln при, а, определяемом из (26).
6. 4. Анализ функциональных представлений Епк (С)
Все четыре представления — (19), (20) (П1), (21)-(24) (П2), (66) (П3) и (67) (П4) — непрерывные, нелинейные, дифференцируемые, гладкие. Среди них два, П1-П2, нестрогие, остальные, П3-П4, строгие. Ограниченными являются П2, П3, т. к. они содержат уравнение ограниченного множества (21). Они же выпуклые представления, причем П2 выпукло в Яп, а П3 выпукло в Яп+ (п. 6. 3). Неизбыточными являются П1-П2, неизбыточность П3-П4 требует дальнейшего исследования.
Продемонстрируем представления П3, П4 для множества п=3-перестановок
E33(G) = E3 (G), G= {0,1,3} ,
(70)
на следующих примерах.
Пример 1. Функциональное представление (66) множества (70) —
? x, = 4-? x2 = 10-? x3 = 28.
Как видно на рис. 1, Е3 © образовано в пересечении трех поверхностей, т. е. данное представление неизбыточное и пересекающееся. Также видно, что
f (x) =? x3 — 28
и, соответственно, все представление выпукло в Я3+. Это представление также включает уравнение сферы, т. е. является ограниченным.
Пример 2. Представление (67) множества (70) —
Рис. 2. Представление П4 для Ез (С)
3
X х1 = 4- х1×2 + х1×2 + х1×2 = 3- х1×2×3 = 0 1=1
изображено на рис. 2. Как видно, Е3 © также образовано в пересечении трех поверхностей, плоскости и двух невыпуклых поверхностей второго и третьего порядков, соответственно. Таким образом, оно невыпуклое и неизбыточное. В отличие от предыдущего (пример 1), данное представление неограниченно, поскольку не включает ни одного уравнения ограниченного множества.
Рис. 1. Представление П3 для E3(G)
Анализ результатов примеров 1−2 позволяет предположить, что, по крайней мере, для множества перестановок Еп © непрерывные представления (66), (67) и, соответственно, (68), (69) — неизбыточные.
7. Обсуждение результатов исследования
Данная работа продолжает и развивает два направления в евклидовой комбинаторной оптимизации — исследование свойств евклидовых комбинаторных множеств и изучение свойств функции на них. При этом связь между этими двумя направлениями устанавливается в понятии функционального представления множеств точек евклидового пространства, при помощи которых эти множества задаются аналитически. А именно, статья посвящена исследованию свойств симметричных полиномов на общем множестве перестановок и получению на их основе новых тополого-метрических свойств Enk (G).
В результате построен ряд функциональных представлений множества Enk (G), каждое из которых может служить основой для множества непрерывных релаксаций исходной задачи и имеет свою область применения.
Так полиэдрально-сферическое представление (24) может быть использовано как для решения безусловных нелинейных задач на Enk (G) при помощи таких методов как полиэдрально сферический метод [17], так и для решения условных линейных задач:
cx ^ min, x е M={x: Ax & lt- b}, (71)
Enk (G)
такими методами как метод комбинаторных отсечений [21]. Оба эти метода относятся к классу точных релаксационных. Так, например, в полиэдрально сферическом методе используются полиэдральная,
f (x) ^min, и сферическая, f (x)min, релаксации.
В то же время, метод комбинаторных отсечений для решения задач на вершинно расположенных множествах [21] основан на отсутствии допустимых точек внутри многогранника и его граней произвольной размерности и использует полиэдральную релаксацию задачи (71) вида cx ^ min. Рассмотрение представления
Pnk (G)nM
(24) приводит к сферической релаксации сх ^ т1п,
8 г (а)пМ
применение которой, в совокупности с отсутствием допустимых точек внутри шара Сг (а), позволяет формировать как комбинаторные, так и сферические отсечения и, тем самым, усовершенствовать метод комбинаторных отсечений [21].
Отметим, что главный недостаток практического применения представления (24) состоит в сравнимом с мощностью Епк © количестве ограничений системы Рпк ©. Одним из способов его преодоления является разработка подходов, позволяющих использование несущественного числа ограничений многогранника, например метод последовательных подсоединений ограничений [2]. Полиэдрально-сферический метод [17] -еще один подход к частичному использованию системы ограничений многогранника в вычислительных схемах.
Строгие представления (66), (67) множества Епк ©, полученные в данной работе, позволяют взглянуть на данную проблему с другой точки зрения — они содержат число ограничений, равное размерности пространства, при этом все эти ограничения, за исключением одного, нелинейны. Таким образом, основной сферой применения строгих представлений видятся
нелинейные задачи f (х) ^ т1п, которые могут быть
^ Епк (С)
эквивалентно переформулированы как непрерывные в пространстве Я2п:
F (x, X) = ^х) + Щ (х)^т1п ,
(72)
где определяются из (66) или (67), соответ-
ственно. Тот факт, что при этом размерность задачи увеличивается несущественно, является явным преимуществом (72) по сравнению с другими эквивалентными переформулировками, в которых размерность задачи может быть увеличена до
может быть решена методом множителей Лагранжа и его модификациями [9], а также служит основой для применения метода штрафных функций [16].
Полу ченные строгие представления служат также основой для новых релаксационных методов, основанных на использовании части ограничений этих представлений. В этой связи интересным направлением дальнейшего исследования является получение неизбыточных представлений Епк © в зависимости от мультимножества С. Это задача является обобщением задачи поиска неизбыточной системы ограничений с комбинаторного многогранника на случай произвольного множества точек пространства, в т. ч. евклидовых комбинаторных множеств. Так, например, неизбыточное полиэдрально-сферическое сферическое представление Епк © получено ((24)) и содержит от п + 2 до 2п ограничений, т. е. его использование снимает в отдельных случаях проблему размерности системы ограничений комбинаторного многогранника. Решение задачи формирования неизбыточных представлений из (66), (67) тоже может снизить размерность задачи (72), достигая нижней границы п + 2, если комбинаторное множество Епк (С формируется в результате касания двух поверхностей (замечание 3). Неизбыточные функциональные представления множеств не только позволяют сократить в отдельных случаях размерность задачи (72), но они и
гарантируют, что извлечение различных наборов ограничений из этих представлений дает разные релаксации исходной задачи, что может быть использовано в новых релаксационных алгоритмах.
Основным же направлением дальнейших исследований нам представляется получение новых функциональных представлений комбинаторных множеств, в частности, таких обобщений общего перестановочного множества, аналитический вид многогранников которых неизвестен, как перестановки перестановок, перестановки кортежей и т. п.
Теоретические результаты, приведенные в статье, имеют широкое практическое применение, поскольку множество задач размещения, расписания, упаковки и т. п. формулируются как задачи на перестановках [1−3, 8, 15, 20].
8. Выводы
1. Введено понятие функциональных представлений евклидовых комбинаторных множеств в виде нелинейных систем уравнений и неравенств. Приведена классификация этих представлений: по типу составляющих их функций (выпуклые, непрерывные, ограниченные и т. п.) — по соотношению числа уравнений и неравенств (строгие и нестрогие) — в зависимости от наличия несущественных ограничений (неизбыточные и избыточные).
2. Представлено два подхода — полиэдрально-поверхностный и поверхностно-многогранный — к построению функциональных представлений комбинаторных множеств. Проведен их сравнительный анализ, очерчены области применения в оптимизации и продемонстрированы преимущества неизбыточных и строгих функциональных представлений евклидовых комбинаторных множеств. Оба подхода продемонстрированы на примере общего перестановочного множества Епк©, в частности приведено его неизбыточное полиэдрально-сферическое представление и построено два строгих представления на основе анализа свойств симметричных полиномов на этом множестве.
3. Основным результатом работы является представление множества Епк© системой нелинейных уравнений и обоснование, тем самым, возможности его строгих представлений. Это открывает широкие возможности использования непрерывной, в т. ч. выпуклой, оптимизации к решению традиционно считающихся сложными задач на общем перестановочном множестве. Полученные строгие представления позволяют новые эквивалентные непрерывные переформулировки задач оптимизации на Епк©, в которых решена проблема размерности. Также они порождают множество непрерывных релаксаций Епк©, которые могут быть положены в основу новых релаксационных методов на этом множестве.
4. Представленная методология функционально-аналитического представления множеств может быть применена к другим евклидовым комбинаторным множествам. Это будет способствовать всестороннему развитию евклидовой комбинаторной оптимизации, поскольку позволит решать в комплексе основные ее задачи: исследование свойств евклидовых комбинаторных множеств и функций на них с последующим построением на их основе комбинаторных методов.
Литература
1. Стоян, Ю. Г. Математические модели и оптимизационные методы геометрического проектирования [Текст] / Ю. Г. Стоян, С. В. Яковлев. — К.: Наук. Думка, 1986. — 268 с.
2. Стоян, Ю. Г. Теорiя i методи евклщово!'- комбшаторно!'- оптимiзацii [Текст] / Ю. Г. Стоян, О. О. бмець. — К.: 1н-т системн. дослщж. освiти, 1993. — 188 с.
3. Емеличев, В. А. Многогранники, графы, оптимизация (комбинаторная теория многогранников) [Текст] / В. А. Емеличев, М. М. Ковалев, М. К. Кравцов. — М.: Наука. Главная редакция физико-математической литературы, 1981. — 344 с.
4. Elte, E. L. The semiregular polytopes of the hyperspaces [Text] / E. L. Elte. — Groningen: Gebroeders Hoitsema, 1912. — 136 p.
5. Polytopes — combinatorics and computation [Text]: Proceedings of DMV Seminar, 29. — Basel: Birkhauser Verlag, 2000. — 225 p. doi: 10. 1007/978−3-0348−8438−9
6. Brualdi, R. A. Combinatorial matrix classes [Text] / R. A. Brualdi. — Cambridge: Cambridge University Press, 2006. — 544 p.
7. Пичугина, О. С. Методы и алгоритмы решения некоторых задач оптимизации на множествах сочетаний и размещений [Текст]: дис. … канд. физ. -мат. наук / О. С. Пичугина. — Х., 1996. — 169 с.
8. Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems [Text] / P. M. Pardalos (Ed.). -Springer, 2000. — 581 p. doi: 10. 1007/978−1-4757−3145−3
9. Пападимитриу, Х. Комбинаторная оптимизация. Алгоритмы и сложность [Текст] / Х. Пападимитриу, К. Стайглиц- пер. с англ. — НД.: Прентис-Холл- М.: Мир, 1984. — 512 с.
10. Hillier, F. S. Continuous Approaches for Solving Discrete Optimization Problems [Text] / F. S. Hillier, G. Appa, L. Pitsoulis, H. P. Williams, P. M. Pardalos, O. A. Prokopyev, S. Busygin. — Handbook on Modelling for Discrete Optimization, 2006. — P. 1−39.
11. Balinski, M. L. Polyhedral Combinatorics: Dedicated to the Memory of D. R. Fulkerson [Text] / M. L. Balinski, A. J. Hoffman. -New York: Elsevier Science Ltd, 1978. — 242 p.
12. Pulleyblank, W. R. Edmonds, matching and the birth of polyhedral combinatorics [Text] / W. R. Pulleyblank // Documenta Mathematica. — 2012. — Extra Volume ISMP. — P. 181−197.
13. Henk, M. Basic properties of convex polytopes [Text] / M. Henk, J. Richter-Gebert, G. M. Ziegler. — Handbook of Discrete and Computational Geometry. — FL, USA: CRC Press, Inc, 1997. — P. 243−270.
14. Postnikov, A. Permutohedra, Associahedra, and Beyond [Text] / A. Postnikov // IMRN: International Mathematics Research Notices. — 2009. — Vol. 6. — P. 1026−1106. doi: 10. 1093/imrn/rnn153
15. Косолап, А. И. Методы глобальной оптимизации [Текст]: монография / А. И. Косолап. — Днепропетровск: Наука и образование, 2013. — 316 с.
16. Murray, W. An algorithm for nonlinear optimization problems with binary variables [Text] / W. Murray, K. -M. Ng // Computational Optimization and Applications. — 2008. — Vol. 47, Issue 2. — P. 257−288. doi: 10. 1007/s10589−008−9218−1
17. Пичугина, О. С. Полиэдрально-сферический подход к решению некоторых классов комбинаторных задач [Текст]: пр. VI Мiжн. школи-семшару / О. С. Пичугина, С. В. Яковлев // Теорiя прийняття ршень. — Ужгород: УжНУ, 2012. -С. 151−153.
18. бмець, О. О. Загальний переставний многогранник: незвщна система лшшних обмежень та рiвняння вах гшерграней [Текст] / О.О. бмець, С. I. Недобачш // Наую^ вют НТУУ «КП1». — 1998. — № 1. — С. 100−106.
19. Стоян, Ю. Г. Квадратичная оптимизация на комбинаторных множествах в Rn [Текст] / Ю. Г. Стоян, С. В. Яковлев, О. В. Паршин // Кибернетика и системный анализ. — 1991. — № 4. — С. 97−104.
20. Яковлев, С. В. Математичш методи оптимiзацii та штелектуальш комп'-ютерш технологи моделювання складних процеав i систем з урахуванням просторових форм об'-еклв: монографiя [Текст] / С. В. Яковлев, В. В. Грицик, А. I. Шевченко, О. М. Кюельова, С. В. Яковлев та ш. — Донецьк: Наука i осв™, 2012. — 480 с.
21. бмець, О. О. Вщакання в лшшних частково комбшаторних задачах евклщово!'- комбшаторно!'- оптимiзацii [Текст] / О. О. бмець, б. М. бмець // Доп. НАН Укра! ни. — 2000. — № 9. — С. 105−109.

ПоказатьСвернуть
Заполнить форму текущей работой