Математическое моделирование комбинаторных конфигураций и применение в задачах оптимизации
В работе предложен подход к построению функционально-аналитических представлений конечных точечных конфигураций, являющихся образами множеств комбинаторных конфигураций в арифметическом евклидовом пространстве. Построен ряд таких представлений множеств евклидовых конфигураций перестановок. Предложен...
Збережено в:
| Опубліковано в: : | Математичні машини і системи |
|---|---|
| Дата: | 2018 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут проблем математичних машин і систем НАН України
2018
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/132017 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Математическое моделирование комбинаторных конфигураций и применение в задачах оптимизации / О.С. Пичугина // Математичні машини і системи. — 2018. — № 1. — С. 123-137. — Бібліогр.: 30 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860161330405703680 |
|---|---|
| author | Пичугина, О.С. |
| author_facet | Пичугина, О.С. |
| citation_txt | Математическое моделирование комбинаторных конфигураций и применение в задачах оптимизации / О.С. Пичугина // Математичні машини і системи. — 2018. — № 1. — С. 123-137. — Бібліогр.: 30 назв. — рос. |
| collection | DSpace DC |
| container_title | Математичні машини і системи |
| description | В работе предложен подход к построению функционально-аналитических представлений конечных точечных конфигураций, являющихся образами множеств комбинаторных конфигураций в арифметическом евклидовом пространстве. Построен ряд таких представлений множеств евклидовых конфигураций перестановок. Предложена схема построения эквивалентной модели к задаче оптимизации на общем евклидовом множестве перестановок векторов в виде задачи дискретного программирования. Показано применение полученных результатов к задачам размещения объектов произвольной размерности.
У роботі запропоновано підхід до побудови функціонально-аналітичних представлень скінченних точкових конфігурацій, що є образами множин комбінаторних конфігурацій в арифметичному евклідовому просторі. Побудовано ряд таких представлень множин евклідових конфігурацій перестановок. Запропоновано схему побудови еквівалентної моделі до задачі оптимізації на загальній евклідовій множині перестановок векторів у вигляді задачі дискретного програмування. Показано застосування отриманих результатів до задач розміщення об'єктів довільної вимірності.
In the paper, an approach to the construction of functional-analytic representations of finite point configurations being the images of sets of combinatorial configurations’ sets in the arithmetic Euclidean space is presented. A number of the representations for the Euclidean permutation configuration sets is constructed. A scheme of forming an equivalent model of an optimization problem on the general Euclidean permutation of vectors set as a discrete problem is proposed. Applicability of the results to placement problems for arbitrary dimension objects is demonstrated.
|
| first_indexed | 2025-12-07T17:55:05Z |
| format | Article |
| fulltext |
© Пичугина О.С., 2018 123
ISSN 1028-9763. Математичні машини і системи, 2018, № 1
УДК 519.85
О.С. ПИЧУГИНА
*
МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ КОМБИНАТОРНЫХ
КОНФИГУРАЦИЙ И ПРИМЕНЕНИЕ В ЗАДАЧАХ ОПТИМИЗАЦИИ
*
Харьковский национальный университет радиоэлектроники, г. Харьков, Украина
Анотація. У роботі запропоновано підхід до побудови функціонально-аналітичних представлень
скінченних точкових конфігурацій, що є образами множин комбінаторних конфігурацій в арифме-
тичному евклідовому просторі. Побудовано ряд таких представлень множин евклідових конфігу-
рацій перестановок. Запропоновано схему побудови еквівалентної моделі до задачі оптимізації на
загальній евклідовій множині перестановок векторів у вигляді задачі дискретного програмування.
Показано застосування отриманих результатів до задач розміщення об'єктів довільної вимірнос-
ті.
Ключові слова: конфігурація, евклідова комбінаторна конфігурація, загальна множина перестано-
вок, функціонально-аналітичне представлення, евклідова комбінаторна множина, задача розмі-
щення, метричні характеристики, параметри розміщення.
Аннотация. В работе предложен подход к построению функционально-аналитических представ-
лений конечных точечных конфигураций, являющихся образами множеств комбинаторных конфи-
гураций в арифметическом евклидовом пространстве. Построен ряд таких представлений мно-
жеств евклидовых конфигураций перестановок. Предложена схема построения эквивалентной
модели к задаче оптимизации на общем евклидовом множестве перестановок векторов в виде за-
дачи дискретного программирования. Показано применение полученных результатов к задачам
размещения объектов произвольной размерности.
Ключевые слова: конфигурация, евклидова комбинаторная конфигурация, общее множество пере-
становок, функционально-аналитическое представление, евклидово комбинаторное множество,
задача размещения, метрические характеристики, параметры размещения.
Abstract. In the paper, an approach to the construction of functional-analytic representations of finite
point configurations being the images of sets of combinatorial configurations’ sets in the arithmetic
Euclidean space is presented. A number of the representations for the Euclidean permutation
configuration sets is constructed. A scheme of forming an equivalent model of an optimization problem on
the general Euclidean permutation of vectors set as a discrete problem is proposed. Applicability of the
results to placement problems for arbitrary dimension objects is demonstrated.
Keywords: configuration, Euclidean combinatorial configuration, the general permutation set, functional-
analytic representation, Euclidean combinatorial set, placement problem, metric characteristics,
placement parameters.
1. Введение
Конфигурации в разных контекстах встречаются в различных теоретических областях.
Наиболее распространенным является понятие конфигурации как множества прямых на
плоскости или в пространстве в совокупности с их точками пересечения [1, 2]. Это поня-
тие конфигурации в смысле Т. Рейе, часто называемой геометрической, было обобщено в
нескольких направлениях. На сегодняшний момент они подразделяются на топологиче-
ские, геометрические и комбинаторные [3]. Конфигурацию называют топологической, ес-
ли она задает некоторое размещение псевдолиний в проективной плоскости с соответ-
ствующим множеством их пересечения. Конфигурации относят к геометрическим, если
линии рассматриваются в евклидовой или проективной плоскости, а точки формируются в
результате пересечения этих линий. Наиболее распространенными являются комбинатор-
ные конфигурации, в которых в качестве точек и линий рассматриваются абстрактные
множества. Именно в последнем контексте конфигурации рассматривались К. Бержем [4]
124 ISSN 1028-9763. Математичні машини і системи, 2018, № 1
для решения задач комбинаторного анализа и было введено строгое математическое поня-
тие конфигурации как отображение
: A B (1)
некоторого исходного множества A элементов произвольной природы в конечное аб-
страктное результирующее множество
1{ }kB b ,...,b (2)
определенной структуры при выполнении заданного набора ограничений . Хотя фор-
мально Берж не накладывал ограничений на мощность исходного множества, фактически
он рассматривал их конечный случай, полагая
1{ }nA a ,...,a . (3)
Именно в этом контексте конфигурации рассматривались в дальнейшем, например,
в [5–8], с применением для этого случая понятия комбинаторной конфигурации или кон-
фигурации в смысле К. Бержа.
Комбинаторная конфигурация (1) осуществляет структурирование результирующе-
го множества (2), а ее результат представляет собой упорядоченную последовательность
элементов из B :
1 2
1
1
n
n
n
j j j
j j
a a
b ,b ,...,b
b b
, (4)
которую можно также представить четвѐркой:
A,B, , . (5)
Рассмотрим задачу комбинаторной оптимизации в следующей постановке. Пусть на
множестве комбинаторных конфигураций (4) задана функция 1f : R . Требуется
найти
( )*
P
arg min f , (6)
где P – множество допустимых решений задачи.
Отобразим множество в пространство 'n'R , n n так, что для образа E множе-
ства выполнено
1 ( ) ( ): E , E , (7)
после чего перейдем к рассмотрению задачи вида
( )*
x X E
x arg min h x . (8)
(8) представляет собой задачу оптимизации на множестве n'E R евклидовых
комбинаторных конфигураций размерности n' или e-конфигураций [9–11], каждая из ко-
торых представима в виде 1 x ( ) ( )x E : , x и задается пятеркой:
A,B, , , . (9)
Целью данной работы является поиск подходов: а) к математическому моделирова-
нию множества комбинаторных конфигураций и множества E e-конфигураций в зави-
симости от параметров четверки (5) и пятѐрки (9) соответственно; б) к эквивалентному
ISSN 1028-9763. Математичні машини і системи, 2018, № 1 125
формулированию задачи (6) как задачи дискретной оптимизации, то есть к построению за-
дачи (6) такой, что
1( )* *x ; (10)
в) к решению задачи (6). Также будут указаны возможные приложения полученных ре-
зультатов в геометрическом проектировании.
2. Теоретические сведения и обозначения
Приведем некоторые сведения из [9]. Пусть E – конечное и не вырожденное в точку мно-
жество точек в nR , а ( ){ }
mj j Jf x – множество функций, определенных на E , где
{1 }mJ ,...,m .
Представление множества E с помощью функциональных зависимостей
( ) 0j mf x , j J , (11)
0 ( )j m mf x , j J \ J (12)
называется функционально-аналитическим или f -представлением множества E .
Система (11) называется строгой частью f -представления, система (12) – нестро-
гой частью, а количество ограничений – его порядком. Так, m будет порядком f -
представления (11), (12), а m ,m m m – порядком его строгой и нестрогой частей соот-
ветственно.
Геометрически f -представление (11), (12) задает E как пересечение m' поверхно-
стей: { 0}( )n
j j mxS x R : f , j J , после чего из образованного надмножества множе-
ства E выделяется непосредственно E при помощи ограничений (12), задающих некото-
рые подобласти nR : ({ 0) } n
j j m mC x R : f x , j J .
Классификация f -представлений может быть произведена в зависимости от вида
входящих в них функций, а также порядка строгой и нестрогой его частей и f -
представления в целом. Так, по виду функций (4), (12) f -представления множества E мо-
гут быть линейные и нелинейные, непрерывные, дифференцируемые, гладкие, выпуклые,
полиномиальные, тригонометрические и т.п.
В свою очередь, для этих видов может быть введена дальнейшая классификация.
Например, (11), (12) – полиномиальное f -представление E , если все функции семейства
– полиномы. Введя понятие степени полиномиального f -представления как наивысшей
степени этих полиномов, можно выделить линейные, квадратичные, кубические, биквад-
ратичные и полиномиальные представления высших степеней.
Общая задача построения функционального представления множества E состоит в
нахождении некоторой системы ограничений (11), (12), задающей множество E . Посколь-
ку E конечно, существует бесчисленное множество его f -представлений, поэтому данная
задача всегда разрешима. Более того, теоретически разрешимой является также задача по-
строения полиномиального f -представления [12].
Классификация f -представлений в зависимости от соотношения параметров
m,m ,m осуществляется следующим образом: система (11), (12) называется:
• строгим представлением E , если в нем присутствует только строгая часть, то есть
0m m,m ;
126 ISSN 1028-9763. Математичні машини і системи, 2018, № 1
• нестрогим – если в f -представлении есть только нестрогая часть, то есть
0m ,m m ;
• общим f -представлением, если присутствуют строгая и нестрогая части, то есть
( ) 0m m m .
Если 1 nA a ,...,a – мультимножество, то символами 1 nA a ,...,a ,
1[ ] [ ]nA a ,...,a будем обозначать упорядоченную последовательность элементов A . Если
к тому же A – числовое мультимножество, то 1( ) ( )na A a ,...,a будет вектором из его
элементов. И, наоборот, если 1[ ]nx x ,...,x – кортеж элементов, в частности, вектор
1( )nx x ,...,x , то 1{ } { }nX x x ,...,x будет мультимножеством его элементов.
x E G( x ) G , g G x E :G( x ) G\{ g } .
Если множество A состоит из упорядоченных последовательностей элементов, то
индуцирующим его мультимножеством называется A такое, что
1
11{ } ; { } : { } { }knn
k k ik
A a ,...,a : a ... a a A a A; i J a A a A\ a .
Основа 1( ) { }kS A a ,...,a индуцирующего мультимножества называется образую-
щим множеством для A .
3. Математическая модель
Заметим, что, исходя из (4), каждой конфигурации можно поставить во взаимно-
однозначное соответствие некоторый вектор 1( ) : 1 n i nj ,..., j j n, i J . Для того же,
чтобы отобразить произвольную конфигурацию как элемент множества , далее будем
использовать обозначения:
1[ ] ( )
m
T
n j ij ni J
,..., , , j J . (13)
Будем также считать, что вся необходимая информация о задаче оптимизации со-
средоточена в комбинаторной конфигурации, а именно в таких параметрах четверки (5),
как исходное множество (3) и результирующее множество (2).
Остановимся на случае, когда множества A, B представляют собой совокупность
векторов одинаковой размерности, то есть существуют s,m N :
1( ) T
i si
s
i na ,... Ja R,a , i , (14)
1( ) T
l ml
m
l kb ,... Jb R,b , l . (15)
Перепишем задачу (6) в следующем виде:
( )* arg min f ,a , (16)
( )P ,a b , (17)
где ( ) { ( ) ( ) 0 }i tP ,b : f , , i Ja b a , (18)
[ ] [ ]
n ki i J jj Ja , ba b . (19)
ISSN 1028-9763. Математичні машини і системи, 2018, № 1 127
Учитывая (18), представим условие (17) в виде
( )b , (20)
( ) 0 i tf , , i Ja (21)
и перейдем к рассмотрению задачи (16), (20), (21).
Положим теперь, что элементы исходного множества могут быть переменными, а
элементы результирующего множества – фиксированными. Условимся использовать обо-
значение a и a для числовой величины или вектора, рассматриваемого как константа и
как переменная соответственно, в результате чего формулы (14), (19) преобразуются в
1( ) T
i si
s
i na ,... Ja R,a , i , [ ] [ ]
n k
i i J jj Ja , ba b , а задача (16), (20), (21) приобре-
тает форму (20),
( )* arg min f ,a , (22)
( ) 0 i tf , , i Ja . (23)
При этом (5) переходит в четверку A,B, , , где 1{ }nA a ,...,a .
Пусть множество содержит все комбинаторные конфигурации вида (4), удовле-
творяющие условию
{ { } }: G , (24)
где 1
11{ } knn
kk
b ,...,b , n ... n nG , то есть
1 21 { } { }
nn j j jj ,..., j : b ,b ,...,b G .
По построению видно, что множество включает все перестановки из мультим-
ножества G , состоящего из n элементов, k из которых различны. Иначе говоря, это об-
щее евклидово множество перестановок или общее e-множество перестановок [13] из
мультимножества числовых векторов G :
( )nkP G . (25)
Тогда наша цель состоит в решении задачи оптимизации вида (20), (22), (23), (25).
Сформулируем ее как задачу (33) на множестве e-конфигураций. С этой целью зададим
биективное отображение между элементами результирующего множества B и множе-
ством действительных чисел:
1 11{ } i kk ie ,...,e , e ie , J , (26)
такое, что 1 = ( ) jj j j ke , e , j Jb b . Тогда множество
1 1( ) { ( ) = ( ) ( ( ),..., ( ))}n
n nE x x ,...,x R : x (27)
будет представлять собой общее множество евклидовых конфигураций перестановок раз-
мерности n' n или общее -множество перестановок [9]:
( )nkE E G , (28)
индуцирующим мультимножеством которого является числовое мультимножество:
1
1 1 11{ } { } knn
n i i nk
G e ,...,e g ,...,g , g g , i J ,
а образующим – числовое множество вида (26).
128 ISSN 1028-9763. Математичні машини і системи, 2018, № 1
Представим задачу (20), (22), (23) в эквивалентной форме:
1 ( ( ))*x arg min f , xa , (29)
1( ( )) 0 i th , x , i Ja , (30)
x E , (31)
где E – множество вида (28).
Задача (29–31) представляет собой задачу евклидовой комбинаторной оптимизации
[13] на -множестве E вида (28), решив которую и учитывая (10), мы одновременно
найдем оптимальное решение * исходной задачи.
Для того, чтобы представить (29–31) как задачу математического программирова-
ния, рассмотрим возможные пути аналитического описания условия (31) принадлежности
допустимого решения x дискретному множеству E . Иначе говоря, перейдем к задаче по-
строения функционально-аналитического представления множества ( )nkE G .
4. Функционально-аналитические представления ( )nkE G
Рассмотрим случай, когда
n k , (32)
то есть мощности исходного и результирующего множеств для рассматриваемого нами
множества комбинаторных конфигураций совпадают. Соответственно, множество яв-
ляется евклидовым множеством перестановок без повторений из G [13, 14]: ( )nP G , а
его образ E – это -множество перестановок без повторений [9]:
( ) ( )n nE E EG .
В этом случае условие (31) имеет форму ( )nx E G и может быть представлено
двумя условиями: а) координаты вектора x принимают значения из (далее Ограниче-
ние 1); б) координаты вектора x попарно различны (далее Ограничение 2).
Ограничение 1 можно записать в виде
i nx , i J (33)
или в векторном виде nx .
В качестве функционально-аналитического представления Ограничения 1 можно
предложить следующее равенство:
1
( ) 0
n
i j n
j
x e , i J . (34)
Ограничение 2 представим в виде
1i jx x , i j n
или
1
r r
i jx x , i j n , (35)
где
1r R ,
1
1= min { }
n
i i
i J
e e .
ISSN 1028-9763. Математичні машини і системи, 2018, № 1 129
Перемножив левые и правые части ограничений (35), имеем еще одну форму Огра-
ничения 2 – 2
1
r
i j n
i j n
x x С .
Это неравенство можно ужесточить до вида
1
r
i j r
i j n
x x , (36)
где
1
r
r i j
i j n
e e , поскольку функция
1
( )
r
i j
i j n
u x,r x x (37)
принимает единственное значение r на ( )nE G .
Так, например, при 2r равенство (36) принимает вид квадратичного ограничения:
2 2
1 1
( ) ( )i j i j
i j n i j n
x x e e , (38)
а неравенства (35) обращаются в систему квадратичных ограничений
2 2( ) 1i jx x , i j n . (39)
В результате имеем ряд f -представлений множества ( )nE G таких, как (34), (38)
(далее ( ( )nE G .FR1)) и (34), (39) (далее ( ( )nE G .FR2)). Оба они – невыпуклые полиноми-
альные f -представления ( )nE G степени 2
nC . При этом ( ( )nE G .FR1) – строгое f -
представление порядка 1n , а ( ( )nE G .FR2) – общее порядка 2 2
1n nC n C .
Предположим теперь, что условие (32) не выполнено. Это означает, что
n k . (40)
Для этого случая на множестве E Ограничение 1 также выполнено и может быть
записано в формах (33), (34), чего нельзя сказать об Ограничении 2. Действительно, по-
скольку, в силу (40), индуцирующим для E является мультимножество, произвольная e-
конфигурация из E будет содержать кратные координаты, следовательно,Ограничение 2
не выполняется. А это означает, что для функционально-аналитического представления
условия
( )nkx E G
необходимо найти другие признаки элементов данного множества e-конфигураций пере-
становок, обеспечивающие повторение координат его элементов заданное число раз.
Теорема 1. Если функция ( )f x – симметрична, то она принимает постоянное зна-
чение на множестве e-конфигураций перестановок, индуцированных одним и тем же муль-
тимножеством G , а именно,
( ) ( )
E'
f x f g , (41)
где ( )nkE' E G , 1g=( )=(g ,...,g )nG .
130 ISSN 1028-9763. Математичні машини і системи, 2018, № 1
Доказательство. Пусть x E' , тогда y E', y x 1 1 { }n n ni ,...,i : i ,...,i J ,
ji j ny x , j J , то есть e-конфигурация y получена из x перестановкой ее координат. А
поскольку по условию ( )f x – симметричная функция, то для любого y E' ( ) ( )f x f y ,
то есть на всем множестве E' e-конфигураций перестановок ( )f x принимает постоянное
значение и 0 0( )
E'
f : f x f .
Более того, ( )f x принимает значение 0f на всем множестве ( )nkE G :
( )
0( )
nkE G
f x f . (42)
Определим 0f , выбирая в (42) в качестве x вектор ( )nkg E G , получая
)
0
(
( ) ( )
nkE G
f x f f g и, в частности, (41).
Заметим, что функция (37) принимает постоянное значение на множестве (28). Дей-
ствительно, она симметрична, а согласно теореме 1, произвольная симметричная функция
принимает постоянное значение на множестве e-конфигураций перестановок, индуциро-
ванных одним мультимножеством, а именно
( )
0 ( ) ( )
nkE G
r u x,r u g,r . Таким образом,
все точки ( )nkE G удовлетворяют ограничению (36), где r определяется по формуле
1
r
r i j
i j n
g g .
В частности, аналогом квадратичного уравнения (38) будет
2 2
1 1
( ) ( )i j i j
i j n i j n
x x g g . (43)
Итак, построено f -представление множества ( )nkE G вида (34), (43) (далее
( ( )nkE G .FR1)). Подобно ( ( )nE G .FR1), это представление строгое, невыпуклое, полино-
миальное степени 2
nC и имеет порядок 1 n .
Возникает вопрос о возможности построения полиномиальных представлений
( )nkE G низших степеней, в том числе выпуклых.
Для того, чтобы построить такие f -представления множества ( )nkE G , перепишем
условие (24) в эквивалентной форме { ={ } }: X x G или ( )nkx E G :
1 1{ } { }n nx ,...,x g ,...,g . (44)
Представим условие (44) в эквивалентной форме:
1( ) ( ) 0nx g ... x g , x R . (45)
Действительно, решение уравнения (45) по переменной x предполагает нахождение
множества 1 nx ,...,x его корней, которые в точности образуют мультимножество G , обес-
печивая тем самым выполнение условия (44). Перепишем уравнение (45) в терминах его
корней, воспользовавшись формулой Виета:
1 2
1 1 2 1 1 2( ) ( ) ( 1)n n n n
n n n nx g ... g x g g ... g g x ... g g ...g =0.
ISSN 1028-9763. Математичні машини і системи, 2018, № 1 131
В результате имеем систему из n уравнений:
n n
i i n
J , j J , ji i
x g , j J , (46)
решением которой будет множество n действительных чисел 1 nx ,...,x вида (44) и только
они. С другой стороны, рассматривая каждое из уравнений системы (46) как уравнение по-
верхности в nR , связывающее координаты вектора 1( )nx x ,...,x , получаем, что полным
решением этой системы будет в точности общее -множество перестановок ( )nkE G . Со-
ответственно, (46) – это строгое полиномиальное представление этого множества (далее
( )nkE G .FR2)), степень и порядок которого совпадают с размерностью пространства и
равно n .
Введем обозначения для элементарных симметрических полиномов
( )
n
j i n
J , j i
u x x , j J (47)
и перепишем ( ( )nkE G .FR2) в виде
( ) ( )j ju x u g n, j J . (48)
Заметим, что для больших размерностей преставление ( ( )nkE G .FR2) становится
неприменимым из-за трудоемкости вычисления значений функций (47). В самом деле,
пусть, к примеру, n – четно и рассматривается
2
n
j -ое уравнение этой системы. Оно со-
держит 2n /
nC слагаемых, каждое из которых, в свою очередь, состоит из
2
n
множителей,
то есть вычисление значения функции
2
( )nu x в точке требует выполнения неполиномиаль-
ного по n числа операций.
Построим еще одно функциональное представление множества ( )nkE G на базе
( ( )nkE G .FR2), основанное на известных соотношениях элементарных симметрических
полиномов (47) со степенными суммами:
0
1
( )
n
j
j ni
i
q x x , j J , (49)
устанавливаемыми с помощью тождеств Ньютона-Жирарда [15]:
1
1 1
1
( ) ( 1) ( ) ( 1) ( ) ( )
j
j i j
j j i j i
i
q x j h x q x h x n, j J . (50)
Применяя рекуррентно формулу (50) к обеим частям (48), получаем
( ) ( )j jq x q g n, j J или, учитывая (49),
1 1
n n
j j
ni i
i i
x g , j J . (51)
132 ISSN 1028-9763. Математичні машини і системи, 2018, № 1
Подобно (46), система уравнений (51) может быть рассмотрена в двух контекстах:
первый – как система для определения множества решений уравнения (45); второй – как
система, задающая множество поверхностей в пространстве nR , в пересечении которых
образуется в точности множество ( )nkE G . Таким образом, найдено еще одно f -
представление (51) множества ( )nkE G (далее ( ( )nkE G .FR3)). Как и ( ( )nkE G .FR2), оно
строгое, полиномиальное, а его степень и порядок равны n . В то же время оно обладает
видимыми преимуществами по сравнению с ( ( )nkE G .FR2), а именно, простотой входящих
в него функций и его выпуклостью в ортанте nR .
Использование понятия евклидовых комбинаторных конфигураций и свойства (44)
e-конфигураций перестановок позволило предложить новое, значительно более простое,
доказательство следующей теоремы, представленной в [16].
Теорема 2. Каждая из систем уравнений (46), (51) задает строгое функционально-
аналитическое представление множества ( )nkE G .
Сформулируем обобщение теоремы 2.
Теорема 3. Если -биективное отображение между элементами образующего
( )nkE G множества и множеством 1{ }' '
k' e ,...,e действительных чисел, то каждая из
систем уравнений
1 1
( ) ( )
n n
j j
i i n
i i
x g , j J , (52)
( ) ( )
n n
i i n
J , j J , ji i
x g , j J (53)
задает строгое функционально-аналитическое представление множества ( )nkE G .
Доказательство. Введем в рассмотрение мультимножество
1
1 1{ } { }k' n' n' '
n k
G' g ,...,g e ,...,e : ( ) '
i i ng g , i J и осуществим в (52), (53) следующую
замену переменных:
( ) ( ) ; ( ) ' ' '
i i i i n j j kx x , g g , i J e e , j J . (54)
В результате получим две системы уравнений:
1 1
n n
' j ' j
ni i
i i
x g , j J , (55)
n n
' '
i i n
J , j J , ji i
x g , j J . (56)
Согласно теореме 2, система (55) представляет собой ( ( )nkE G' .FR2), а (56) –
( ( )nkE G' .FR3). С учетом того, что (52), (53) формируется (55), (56) заменами перемен-
ных, обратными к (54):
1 1 1( ) ( ) ; ( ) ' ' '
i i i i n j j kx x , g g , i J e e , j J , имеем
( ) ( )nk nkx GE x' EG' ,
ISSN 1028-9763. Математичні машини і системи, 2018, № 1 133
а (52), (53) – это записанные в терминах координат e-конфигурации x представления
( ( )nkE G' .FR2), ( ( )nkE G' .FR3).
Следствие 1. 1a R каждая из следующих систем уравнений
1 1
( ) ( ) 0
n n
j j
i i n
i i
x a g a , j J ,
( ) ( ) 0
n n
j j
i i n
J , j J , ji i
x a g a , j J
является строгим f -представлением множества ( )nkE G .
Наконец, введя в рассмотрение функцию 1 1( )r r r Tx x ,...,x покоординатного возве-
дения вектора в степень 1r R , f -представление (51) может быть записано в векторной
форме:
e e
jT jT
nx g , j J , (57)
где e – единичный вектор. Тогда, возвращаясь к исходной задаче (20), (22), (23), (25) на
комбинаторных конфигурациях, получаем, что условие (20) может быть записано в виде
( ) jT jT
ng , j Je e . (58)
В результате исходная задача сводится к поиску экстремума функции ( )f ,a в об-
ласти, заданной функциональными ограничениями (23), (58). Переменными в ней по усло-
вию являются n s координат векторов исходного множества A , а также n m координат
векторов (13), составляющих конфигурацию . В целом эта задача оптимизации имеет
размерность ( )n s m . В то же время задача евклидовой комбинаторной оптимизации (29),
(30), (57) имеет размерность ( 1)n s , поскольку переменными в ней являются координаты
векторов исходного множества и координаты x . Также она сформулирована как задача
математического программирования, решив которую одним из методов дискретного про-
граммирования [17–20] будет найдена не только оптимальная e-конфигурация *x , но и оп-
тимальная комбинаторная конфигурация * вида (10).
5. Применение результатов в задачах размещения
Пусть множество m -мерных объектов { }
ni i JO с известными метрическими характери-
стиками размещаются в области 0
mO R с фиксированными параметрами размещения.
Необходимо найти параметры размещения объектов iO , ni J , а также метрические ха-
рактеристики области размещения, при которых достигается экстремум функции f и при
этом объекты размещения попарно не пересекаются и расположены в области размещения.
Построим математическую модель данной задачи как задачи на множестве евкли-
довых конфигураций перестановок. Исходным множеством будут служить векторы пара-
метров размещения, а результирующим – различные векторы метрических характеристик
объектов размещения. Пусть 1( )Ti i mi,..., – вектор метрических характеристик объ-
екта ( )i nO i J , тогда для построения результирующего множества B вида (2) выделим
134 ISSN 1028-9763. Математичні машини і системи, 2018, № 1
основу из мультимножества { }
ni i JG метрических характеристик объектов размеще-
ния и осуществим присвоение (B )B S ' .
Учитывая наличие области размещения 0O , нумерацию объектов будем осуществ-
лять с нуля – 0{ }
n
i i J
O , где
0 {0}n nJ J , и именно они будут служить исходным множе-
ством для формирования конфигураций. Параметрами векторов (14) будут параметры раз-
мещения объектов, иначе говоря, координаты их полюсов.
Согласно условию задачи, параметры размещения области 0O заданы, остальные
должны быть найдены, таким образом формула (14) приобретает вид
10 10 0( ) ( ) T T
i sis
s s
i na a a R , a,..., ,...,a a R , i J ,
где s – число параметров размещения, 0 0a O – полюс области размещения, { }
ni i Ja –
полюса объектов размещения. В то же время формула (15) преобразуется в
10 0 0 1 s mT T
m i kmii,..., ,.b b b R , b b b R ,. l. J, ,
где m – количество метрических характеристик, которые должны быть найдены только
для области размещения, остальные фиксированы.
Задача (16), (20), (21) преобразуется в
0 ( )* arg min f a , ,a , (59)
0( )b ,b , (60)
0 0 ai tf a , , , i J , (61)
где
0 1
1
10
0
n
n
n
j j j
j j
a a ... a
b ,b ,...,b
b b ... b
.
Здесь система ограничений (61) включает два блока – условия попарного непересе-
чения объектов размещения:
0 1 '< ''i' i''O O
, i i n (62)
и условия их размещения в области 0O :
0 0
*
i'O O
n, i' J , (63)
где 0
*
O – дополнение области размещения, [.] – фи-функция [21]. В терминах метриче-
ских характеристик и параметров размещения условия (62), (63) могут быть представлены
в виде
( ) 0 1 '< ''i' i''i' i''a ,b ,a ,b , i i n , (64)
00( ) 0 i' i' n' a ,b ,a ,b , i' J . (65)
Формализуем ограничение (60), переписав его следующим образом:
( )nkP G , (66)
00 0
min maxb b b , (67)
ISSN 1028-9763. Математичні машини і системи, 2018, № 1 135
где G – мультимножество метрических характеристик, а 0 0
min max mb ,b R – параллеле-
пипед, в пределах которого могут изменяться метрические характеристики области 0O .
Теперь можно осуществить переход к рассмотрению общего множества e-
конфигураций перестановок по вышеприведенной схеме и задаче евклидовой комбинатор-
ной оптимизации на нем. Мы же предложим математическую оптимизационную модель на
евклидовом комбинаторном множестве ( )nkP G с использованием его f -представления
вида (58), которое, с учетом (27), представим в виде
1 1
( ) ( ) j j
i
n
n
i i
i
n
, j J . (68)
Получили модель оптимизации (59), (64), (65), (67), (68) смешанно-комбинаторного
типа, в которой переменными являются и метрические характеристики, и параметры раз-
мещения объектов, а также метрические характеристики области. За счет условия (68) до-
пустимым решением этой задачи будет допустимое размещение объектов заданных изна-
чально размеров. Искусственное его добавление позволяет существенно, а именно в
1
( )nk
k
n!
P
n ! ... n !
G раз, увеличить область поиска оптимального решения по сравнению
с традиционными постановками задач размещения, в которых метрические характеристики
объектов фиксированы [14, 21], и, соответственно, увеличить вероятность получения более
точного решения при применении приближенных методов. Также это демонстрирует, как
практически может быть применен метод искусственного расширения пространства [22–
24] для решения реальных задач.
Предложенный подход к построению оптимизационных моделей на множествах
комбинаторных конфигураций как задач оптимизации на множествах евклидовых комби-
наторных конфигураций может быть применен к другим классам e-конфигураций, таким
как множества евклидовых конфигураций размещений и перестановок со знаком, а также
специальным классам множеств e-конфигураций перестановок, размещений, перестановок
со знаком [9] и др. При этом для построения f -представлений этих множеств могут быть
применены результаты работ [16, 25–30].
6. Выводы
В данной статье предложен новый подход к построению функционально-аналитических
представлений образов евклидовых комбинаторных множеств, основанный на применении
понятия евклидовой комбинаторной конфигурации как отображения конечного множества
в точку евклидова арифметического пространства. Данный подход применен к общему ев-
клидову множеству перестановок и его отдельным классам для построения непрерывных
функциональных представлений, что позволяет применение методов непрерывной опти-
мизации к решению дискретных задач на этих множествах.
Построена обобщенная модель оптимизации на множествах комбинаторных конфи-
гураций в смысле Бержа с участием как исходного, так и результирующего множества.
Для тех из них, результирующие множества которых представляют собой векторы одной
размерности, построена эквивалентная модель на множестве евклидовых комбинаторных
конфигураций с использованием полученных непрерывных функциональных представле-
ний.
Построена модель размещения геометрических объектов с одинаковым числом мет-
рических характеристик как задача оптимизации на множестве евклидовых комбинатор-
136 ISSN 1028-9763. Математичні машини і системи, 2018, № 1
ных конфигураций, где исходным множеством выступают векторы параметров размеще-
ния, а результирующим – векторы метрических характеристик. Данная модель позволяет
варьирование множества переменных характеристик, в результате чего она охватывает как
традиционную модель размещения объектов, где метрические характеристики объектов
размещения фиксированы, так и случай, когда все или часть из них переменные, где схо-
димость к допустимой точке обеспечивается дополнительными ограничениями, а оптими-
зация проводится на образе общего евклидова множества перестановок.
Область применения результатов работы может быть расширена на другие классы
евклидовых комбинаторных множеств, а также другие задачи геометрического проектиро-
вания и оптимального планирования.
СПИСОК ИСТОЧНИКОВ
1. Reye T. Die Geometrie der Lage / Reye Т. – Leipzig: Baumgärtnerś Buchhandlung, 1892. – 343 p.
2. Gropp H. Configurations between geometry and combinatorics / H. Gropp // Discrete Applied Mathe-
matics. – 2004. – Vol. 138, N 1. – P. 79 – 88.
3. Grunbaum B. Configurations of Points and Lines / Grunbaum B. – Providence, R.I: American Mathe-
matical Society, 2009. – 399 p.
4. Berge C. Principes de combinatoire / Berge C. – Paris: Academic Press, 1968. – 146 p.
5. Гуляницкий, Л.Ф. До формалізації та класифікації задач комбінаторної оптимізації / Л.Ф. Гуля-
ницкий // Теорія оптимальних рішень. – 2008. – № 7. – С. 45 – 49.
6. Донець Г.П. Екстремальні задачі на комбінаторних конфігураціях / Г.П. Донець, Л.М. Колєчкіна.
– Полтава, 2011. – 328 с.
7. Сачков В.Н. Комбинаторные методы дискретной математики / Сачков В.Н. – М.: Наука, 1975. –
319 с.
8. Стоян Ю.Г. Описание классов комбинаторных конфигураций на основе отображений /
Ю.Г. Стоян, И.В. Гребенник // Доклады НАН Украины. – 2008. – № 10. – С. 28 – 31.
9. Стоян Ю.Г. Евклидовы комбинаторные конфигурации: монография / Стоян Ю.Г., Яковлев С.В.,
Пичугина О.С. – Харьков: Константа, 2017. – 404 с.
10. Яковлев С.В. Задачи оптимизации на евклидовых комбинаторных конфигурациях и их свойства
/ С.В. Яковлев, О.С. Пичугина // Питання прикладної математики і математичного моделювання. –
2017. – Вип. 17. – С. 278 – 263.
11. Яковлев С.В. Свойства задач комбинаторной оптимизации на полиэдрально-сферических мно-
жествах / С.В. Яковлев, О.С. Пичугина // Кибернетика и системный анализ. – 2018. – № 1. – С. 111
– 124.
12. Harris J. Algebraic Geometry: A First Course, 1st ed. / Harris J. – N.Y.: Springer-Verlag, 1992. –
328 p.
13. Стоян Ю.Г. Теорія і методи евклідової комбінаторної оптимізації / Ю.Г. Стоян, О.О. Ємець. –
К., 1993. – 188 с.
14. Стоян Ю.Г. Математические модели и оптимизационные методы геометрического проектиро-
вания / Ю.Г. Стоян, С.В. Яковлев. – К., 1986. – 268 с.
15. Seroul R. Programming For Mathematicians / Seroul R. – Berlin, New York: Springer, 2000. – 431 p.
16. Пичугина О.С. Функционально-аналитические представления общего перестановочного мно-
жества / О.С. Пичугина, С.В. Яковлев // Восточно-Европейский журнал передовых технологий. –
2016. – № 4 (79). – С. 27 – 38.
17. Баранов В.И. Экстремальные комбинаторные задачи и их приложения / В.И. Баранов,
Б.С. Стечкин. – [2-е изд.]. – Москва: Физматлит, 2004. – 240 с.
18. Korte B. Combinatorial Optimization: Theory and Algorithms / B. Korte, J. Vygen. – Heidelberg, New
York: Springer, 2012. – 660 p.
19. Pardalos P.M. Handbook of combinatorial optimization / Pardalos P.M, Du D-Z., Graham R.L. – New
York, 2013. – 3409 p.
20. Сергиенко И.В. Задачи дискретной оптимизации: проблемы, методы решения, исследования /
И.В. Сергиенко, В.П. Шило. – К.: Наукова думка, 2003. – 261 с.
21. Chernov N. Mathematical model and efficient algorithms for object packing problem / N. Chernov,
ISSN 1028-9763. Математичні машини і системи, 2018, № 1 137
Y. Stoyan, T. Romanova // Comput. Geom. – 2010. – Vol. 43, N 5. – P. 535 – 553.
22. Pichugina O.S. On Lifting Approaches To Geometric Design Problems / O.S. Pichugina, T.E. Roma-
nova, S.V. Yakovlev // Тези доповідей XIV міжнар. наук.-практ. конф. «Математичне та програмне
забезпечення інтелектуальних систем (MPZIS-2016)», (Дніпропетровськ, 16–18 листопада 2016 р.).
– Дніпропетровськ, 2016. – С. 154 – 155.
23. Yakovlev S. V. The Method of Artificial Space Dilation in Problems of Optimal Packing of Geometric
Objects / S.V. Yakovlev // Cybern. Syst. Anal. – 2017. – Vol. 53, N 5. – P. 725 – 731.
24. Яковлев С.В. О комбинаторной структуре задач оптимального размещения геометрических
объектов / С.В. Яковлев // Доклады НАН Украины. – 2017. – № 9. – С. 26 – 32.
25. Pichuginа O. Convex extensions and continuous functional representations in optimization, with their
applications / O. Pichuginа, S. Yakovlev // J. Coupled Syst. Multiscale Dyn. – 2016. – N 2 (4). – P. 129 –
152.
26. Pichuginа O. Continuous Representations and Functional Extensions in Combinatorial Optimization /
O. Pichuginа, S. Yakovlev // Cybernetics and Systems Analysis. – 2016. – N 6 (52). – P. 921 – 930.
27. Pichuginа O. Continuous Approaches to the Unconstrained Binary Quadratic Problems / O. Pichuginа,
S. Yakovlev // Mathematical and Computational Approaches in Advancing Modern Science and Engineer-
ing. – Switzerland: Springer, 2016. – P. 689 – 700.
28. Pichuginа O. Continuous representation techniques in combinatorial optimization / O. Pichuginа,
S. Yakovlev // IOSR Journal of Mathematics. – 2017. – N 2 (13), Ver. V. – P. 12 – 25.
29. Pichuginа O. Optimization on Polyhedral-Spherical Sets: Theory and Applications / O. Pichuginа,
S. Yakovlev // IEEE First Ukraine Conference on Electrical and Computer Engeneering (UKRCON). –
2017. – P. 1167 – 1174.
30. Пичугина О.С. Оптимизация на общем множестве перестановок со знаком / О.С. Пичугина //
Системні дослідження та інформаційні технології. – 2017. – № 4. – С. 74 – 96.
Стаття надійшла до редакції 10.01.2018
|
| id | nasplib_isofts_kiev_ua-123456789-132017 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1028-9763 |
| language | Russian |
| last_indexed | 2025-12-07T17:55:05Z |
| publishDate | 2018 |
| publisher | Інститут проблем математичних машин і систем НАН України |
| record_format | dspace |
| spelling | Пичугина, О.С. 2018-04-08T18:36:04Z 2018-04-08T18:36:04Z 2018 Математическое моделирование комбинаторных конфигураций и применение в задачах оптимизации / О.С. Пичугина // Математичні машини і системи. — 2018. — № 1. — С. 123-137. — Бібліогр.: 30 назв. — рос. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/132017 519.85 В работе предложен подход к построению функционально-аналитических представлений конечных точечных конфигураций, являющихся образами множеств комбинаторных конфигураций в арифметическом евклидовом пространстве. Построен ряд таких представлений множеств евклидовых конфигураций перестановок. Предложена схема построения эквивалентной модели к задаче оптимизации на общем евклидовом множестве перестановок векторов в виде задачи дискретного программирования. Показано применение полученных результатов к задачам размещения объектов произвольной размерности. У роботі запропоновано підхід до побудови функціонально-аналітичних представлень скінченних точкових конфігурацій, що є образами множин комбінаторних конфігурацій в арифметичному евклідовому просторі. Побудовано ряд таких представлень множин евклідових конфігурацій перестановок. Запропоновано схему побудови еквівалентної моделі до задачі оптимізації на загальній евклідовій множині перестановок векторів у вигляді задачі дискретного програмування. Показано застосування отриманих результатів до задач розміщення об'єктів довільної вимірності. In the paper, an approach to the construction of functional-analytic representations of finite point configurations being the images of sets of combinatorial configurations’ sets in the arithmetic Euclidean space is presented. A number of the representations for the Euclidean permutation configuration sets is constructed. A scheme of forming an equivalent model of an optimization problem on the general Euclidean permutation of vectors set as a discrete problem is proposed. Applicability of the results to placement problems for arbitrary dimension objects is demonstrated. ru Інститут проблем математичних машин і систем НАН України Математичні машини і системи Моделювання і управління Математическое моделирование комбинаторных конфигураций и применение в задачах оптимизации Математичне моделювання комбінаторних конфігурацій і застосування в задачах оптимізації Mathematical modeling of combinatorial configurations and application in optimization problems Article published earlier |
| spellingShingle | Математическое моделирование комбинаторных конфигураций и применение в задачах оптимизации Пичугина, О.С. Моделювання і управління |
| title | Математическое моделирование комбинаторных конфигураций и применение в задачах оптимизации |
| title_alt | Математичне моделювання комбінаторних конфігурацій і застосування в задачах оптимізації Mathematical modeling of combinatorial configurations and application in optimization problems |
| title_full | Математическое моделирование комбинаторных конфигураций и применение в задачах оптимизации |
| title_fullStr | Математическое моделирование комбинаторных конфигураций и применение в задачах оптимизации |
| title_full_unstemmed | Математическое моделирование комбинаторных конфигураций и применение в задачах оптимизации |
| title_short | Математическое моделирование комбинаторных конфигураций и применение в задачах оптимизации |
| title_sort | математическое моделирование комбинаторных конфигураций и применение в задачах оптимизации |
| topic | Моделювання і управління |
| topic_facet | Моделювання і управління |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/132017 |
| work_keys_str_mv | AT pičuginaos matematičeskoemodelirovaniekombinatornyhkonfiguraciiiprimenenievzadačahoptimizacii AT pičuginaos matematičnemodelûvannâkombínatornihkonfíguracíiízastosuvannâvzadačahoptimízacíí AT pičuginaos mathematicalmodelingofcombinatorialconfigurationsandapplicationinoptimizationproblems |