О моделировании симметрии в комбинаторной оптимизации

Показано, что симметрия в комбинаторной оптимизации проявляется в зависимости от структуры входных данных и способа моделирования целевой функции. В ее основе лежит симметрия комбинаторных множеств и комбинаторных конфигураций (аргумента целевой функции). Ее математическая модель представлена конечн...

Повний опис

Збережено в:

Бібліографічні деталі
Опубліковано в: :	Проблемы управления и информатики
Дата:	2018
Автор:	Тимофеева, Н.К.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2018
Теми:	Оптимальное управление и методы оптимизации
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/180581
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	О моделировании симметрии в комбинаторной оптимизации / Н.К. Тимофеева // Проблемы управления и информатики. — 2018. — № 3. — С. 15-27. — Бібліогр.: 10 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-180581
record_format	dspace
spelling	Тимофеева, Н.К. 2021-10-04T10:17:39Z 2021-10-04T10:17:39Z 2018 О моделировании симметрии в комбинаторной оптимизации / Н.К. Тимофеева // Проблемы управления и информатики. — 2018. — № 3. — С. 15-27. — Бібліогр.: 10 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/180581 519.14+519.816 Показано, что симметрия в комбинаторной оптимизации проявляется в зависимости от структуры входных данных и способа моделирования целевой функции. В ее основе лежит симметрия комбинаторных множеств и комбинаторных конфигураций (аргумента целевой функции). Ее математическая модель представлена конечными последовательностями, которые характеризуются приближенной или точной симметрией. Показано, що симетрія в комбінаторній оптимізації проявляється в залежності від структури вхідних даних і способу моделювання цільової функції. В її основі лежить симетрія комбінаторних множин та комбінаторних конфігурацій (аргументу цільової функції). Її математичну модель подано скінченними послідовностями, які характеризуються наближеною або точною симетрією. It is shown that symmetry in combinatorial optimization manifests itself depending on the structure of the input data and the method of modeling of the objective function. It is based on the symmetry of combinatorial sets and combinatorial configurations (the objective function argument). Its mathematical model is represented by finite sequences, which are characterized by approximate or exact symmetry. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Оптимальное управление и методы оптимизации О моделировании симметрии в комбинаторной оптимизации Про моделювання симетрії в комбінаторній оптимізації Modeling of symmetry in combinatorial optimization Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	О моделировании симметрии в комбинаторной оптимизации
spellingShingle	О моделировании симметрии в комбинаторной оптимизации Тимофеева, Н.К. Оптимальное управление и методы оптимизации
title_short	О моделировании симметрии в комбинаторной оптимизации
title_full	О моделировании симметрии в комбинаторной оптимизации
title_fullStr	О моделировании симметрии в комбинаторной оптимизации
title_full_unstemmed	О моделировании симметрии в комбинаторной оптимизации
title_sort	о моделировании симметрии в комбинаторной оптимизации
author	Тимофеева, Н.К.
author_facet	Тимофеева, Н.К.
topic	Оптимальное управление и методы оптимизации
topic_facet	Оптимальное управление и методы оптимизации
publishDate	2018
language	Russian
container_title	Проблемы управления и информатики
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
format	Article
title_alt	Про моделювання симетрії в комбінаторній оптимізації Modeling of symmetry in combinatorial optimization
description	Показано, что симметрия в комбинаторной оптимизации проявляется в зависимости от структуры входных данных и способа моделирования целевой функции. В ее основе лежит симметрия комбинаторных множеств и комбинаторных конфигураций (аргумента целевой функции). Ее математическая модель представлена конечными последовательностями, которые характеризуются приближенной или точной симметрией. Показано, що симетрія в комбінаторній оптимізації проявляється в залежності від структури вхідних даних і способу моделювання цільової функції. В її основі лежить симетрія комбінаторних множин та комбінаторних конфігурацій (аргументу цільової функції). Її математичну модель подано скінченними послідовностями, які характеризуються наближеною або точною симетрією. It is shown that symmetry in combinatorial optimization manifests itself depending on the structure of the input data and the method of modeling of the objective function. It is based on the symmetry of combinatorial sets and combinatorial configurations (the objective function argument). Its mathematical model is represented by finite sequences, which are characterized by approximate or exact symmetry.
issn	0572-2691
url	https://nasplib.isofts.kiev.ua/handle/123456789/180581
citation_txt	О моделировании симметрии в комбинаторной оптимизации / Н.К. Тимофеева // Проблемы управления и информатики. — 2018. — № 3. — С. 15-27. — Бібліогр.: 10 назв. — рос.
work_keys_str_mv	AT timofeevank omodelirovaniisimmetriivkombinatornoioptimizacii AT timofeevank promodelûvannâsimetríívkombínatorníioptimízacíí AT timofeevank modelingofsymmetryincombinatorialoptimization
first_indexed	2025-11-25T23:31:16Z
last_indexed	2025-11-25T23:31:16Z
_version_	1850581899674648576
fulltext	© Н.К. ТИМОФЕЕВА, 2018 Международный научно-технический журнал «Проблемы управления и информатики», 2018, № 3 15 ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ И МЕТОДЫ ОПТИМИЗАЦИИ УДК 519.14+519.816 Н.К. Тимофеева О МОДЕЛИРОВАНИИ СИММЕТРИИ В КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ Введение Симметрия в комбинаторной оптимизации проявляется в зависимости от структуры входных данных и способа моделирования целевой функции. Это свойство показано на примере подклассов разрешимых задач, в которых входные данные заданы прямыми и обратными функциями натурального аргумента. Для последовательности значений целевой функции, которые изменяются от макси- мума к минимуму в прямой задаче, существует симметричная последовательность решений для обратной, значения которых изменяются от минимума к максимуму. В основе этого свойства комбинаторной оптимизации лежит симметрия аргумента целевой функции (комбинаторных множеств и комбинаторных конфигураций). Постановка задачи Как правило, симметрию изучают в геометрии, но она проявляется также и в отношении негеометрических объектов в других областях математики и иных науках. В математике это свойство изучается с помощью теории групп. Достаточно основательно выделяют и исследуют группы симметрии на перестановках и гра- фах, определяют их порядок [1–3]. В литературе рассматривают симметрии раз- биения n -элементного множества на подмножества [1]. Эта комбинаторная кон- фигурация является аргументом целевой функции в различных задачах разбиения, в частности в задачах классификации и кластеризации. В оптимизации рассмат- ривают такое свойство, как двойственность [4–7]. Когда двойственная задача оп- тимизации совпадает с начальной, то в задачах линейного программирования это называют симметричной двойственностью. Но природа данного свойства в лите- ратуре не исследуется. В комбинаторике симметрия присуща как комбинаторным конфигурациям, так и их множествам. В [8] описана симметрия комбинаторных множеств. Симметрия в комбинаторной оптимизации и способы ее выявления в литературе освещены недостаточно. Предлагаемый подход Для исследования целевой функции и выявления симметрии в комбина- торной оптимизации использованы подклассы разрешимых задач из разных классов с различной структурой входных данных. Анализируются задачи , входные данные в которых заданы прямыми и обратными функциями нату- рального аргумента, которые симметричны по отношению друг к другу. Также исследуется симметрия комбинаторной оптимизации для целевых функций, выражения которых сформулированы по-разному. 16 ISSN 0572-2691 Общая математическая постановка задачи комбинаторной оптимизации Задачи комбинаторной оптимизации, как правило, задаются на одном или нескольких множествах, например }...,,{ 1 naaA и }...,,{ ~1 nbbB  , элементы которых имеют различную природу [9]. Назовем эти множества базовыми. Имеется два типа задач. В первом типе каждое из этих множеств представле- но в виде графа, вершинами которого являются его элементы, а каждому реб- ру поставлено в соответствие число Rclt  , которое называют весом ребра ( R — множество действительных чисел); },...,,1{ nl  },~...,,1{ nt n — ко- личество элементов множества A , n~ — количество элементов множества .B Положим, что .~nn  Между элементами этих множеств существуют связи, числовое значение которых является весами. Величины ltc назовем входными данными и зададим их матрицами. Во втором типе задач между элементами заданного множества связей не существует, а весами являются числа ,Rv j  },...,,1{ nj  которым в соответствие поставлены некоторые свойства этих элементов, числовые значения которых задаются конечными последователь- ностями, именуемыми входными данными. Эти величины определяют значе- ние целевой функции. Для обоих типов задач из элементов одного или нескольких базовых множеств, например Aal  , }...,,1{ nl , образуется комбинаторное множе- ство W — совокупность комбинаторных конфигураций определенного типа (перестановки, выборки различных типов, разбиения и т.д.). На элементах w комбинаторного множества W вводится целевая функция ).(wF Необходимо найти элемент w множества ,W для которого )(wF принимает экстремаль- ное значение при выполнении заданных ограничений. Комбинаторные конфигурации Под комбинаторной конфигурацией понимаем любую совокупность эле- ментов, которая образуется из всех или некоторых элементов заданного базо- вого множества }...,,{ 1 naaA [9]. Обозначим ее упорядоченным множе- ством )...,,( 1 kkk www  , где }...,,1{η n — количество элементов в kw (в даль- нейшем η будем обозначать и как kη ), qkwW 1}{ — множество комбинаторных конфигураций, k — порядковый номер kw в упорядоченном множестве ,W },...,,1{ qk  q — количество kw в .W Комбинаторную конфигурацию kw бу- дем обозначать как с верхним индексом ,kw так и без него. Рекуррентным комбинаторным оператором назовем совокупность пра- вил, по которым из элементов базового множества A образуется комбина- торная конфигурация kw . Различные типы комбинаторных конфигураций об- разуются с помощью трех рекуррентных комбинаторных операторов: выби- рание, транспозиция и арифметический [9]. Определение 1. Две нетождественные комбинаторные конфигурации kw )...,,( 1 kk kww   и )...,,( 1 iii iwww   назовем изоморфными, если .ηη ik  Международный научно-технический журнал «Проблемы управления и информатики», 2018, № 3 17 Определение 2. Подмножество WW k  назовем подмножеством изоморф- ных комбинаторных конфигураций, если ее элементы — изоморфные комбина- торные конфигурации. Множество W состоит из подмножеств изоморфных комбинаторных конфигураций. Если комбинаторные конфигурации множества W образованы несколь- кими рекуррентными комбинаторными операторами, то они могут быть как изоморфными, так и неизоморфными, а W состоит из подмножеств WW  . Поскольку операция транспозиции в перестановке меняет только порядок следования элементов в ,Wwk  множество перестановок W является множе- ством изоморфных комбинаторных конфигураций. Множества комбинаторных конфигураций одного и того же типа имеют разнообразные упорядочения. Их количество для разных типов — различное. Моделирование входных данных функциями натурального аргумента Для задания целевой функции в явном виде и сведения ее к одному выражению для различных классов задач комбинаторной оптимизации смоделируем входные данные конечными последовательностями. Для первого типа задач представим элементы h наддиагоналей симметричной комбинаторной матрицы )( kwQ ком- бинаторной функцией )),)((β...,,),)1((β(\|),)((β 11 k m kmk wmfwfwjf  , а элементы h наддиагоналей симметричной матрицы C — функцией натурального аргумента ))(...,),1((\|)( 1 mj m  , где 2 )1(   nn m — количество элемен- тов h наддиагоналей матриц C и )( kwQ , 1,1  nh . Если матрицы )( kwQ и C несимметричные, то mkwjf 1\|),)((β и mj 1\|)( содержат все их элементы, а 2nm  (или nnm ~ ). Функцию цели запишем как ).(),)((β)( 1 jwjfwF k m j j k    (1) Введем системы комбинаторных функций H и 'H , где Hwjf mk 1\|),)((β — комбинаторная функция, аргументом которой является перестановка ,Wwk  образо- ванная из элементов базового множества }...,,{ 1 nn aaA  , ' 1 ' \|)),(( Hwjf mi  — комбинаторная функция, аргументом которой является перестановка ,'' Ww i  образованная из элементов базового множества }~...,,~{ ~ 1 mm aaA  . Если mm wjfwjf 1 1' 1 1 \|),)((\|),)((  , где 1'1, ww — первые перестановки в ,W ,'W и Hwjf m  1 1 \|),)(( , ' 1 1' \|),)(( Hwjf m  , то 'HH  . Задачу комбинаторной оптимизации, входные данные в которой заданы функциями mkwjf 1\|),)(( и mj 1\|)( , назовем базовой (или задачей системы H ). Задачу, входные данные в ко- торой заданы функциями ' 1 ' \|),)(( Hwjf mi  и mj 1\|)( , образованными из mkwjf 1\|),)(( и mj 1\|)( , — упорядоченной (или задачей системы 'H ). 18 ISSN 0572-2691 Симметрия в комбинаторной оптимизации В зависимости от типа преобразований различают разные виды симметрии. В комбинаторике имеется как точная, так и приближенная симметрия, в част- ности, она свойственна комбинаторным множествам и конфигурациям. Кроме того, симметрия проявляется и в комбинаторной оптимизации. Ее математиче- скую модель представим с использованием конечной последовательности чи- сел, которая строится по определенным правилам. Комбинаторную конфигурацию представим упорядоченной последова- тельностью, для которой существует ей симметричная. Полагаем, что kw симметричная, если она совпадает сама с собой при движении без деформа- ций. Существует единственный способ переместить симметричную последо- вательность так, чтобы она совпадала с исходной. Это — ее поворот на .180 Введем такое определение. Определение 3. Инверсией комбинаторной конфигурации )...,,( 1  www , ps ww  , назовем )~...,,~(~ 1  www , ps ww ~~  , ps  , т.е. Ww и Ww~ симмет- ричны относительно друг друга. Для перестановки ),1...,,2,1( nnw  симмет- ричной является )1,2...,,1,(~  nnw . Лемма 1. Симметричные перестановки Ww и Ww~ принадлежат одному множеству .W Доказательство очевидно. Лемма 2. Если множество W упорядочено подмножествами ,W то попарно симметричные комбинаторные конфигурации принадлежат разным множествам, которые имеют разное упорядочение. Иными словами, если для Ww симмет- рична Ww ~~ , то W и W ~ имеют разное упорядочение. Доказательство очевидно. Пример 1. Для подмножества неупорядоченного разбиения натурального числа )3,3;4,2;5,1(W , WW  , симметричным является подмножество )1,5;2,4;3,3( ~ W , которое принадлежит множеству . ~ W Лемма 3. Комбинаторная функция ' 1 ' \|),)(( Hwjf mi  имеет свою симмет- рию в .'H Доказательство очевидно. Лемма 4. Если перестановка '' Ww t  симметрична '' Ww l  , то комбинаторная функция ' 1 ' \|),)(( Hwjf mt  симметрична ' 1 ' \|),)(( ~ Hwjf ml  , }.!...,,1{, mlt  Доказательство очевидно. Теорема 1. Ни одна комбинаторная функция Hwjf mk  1\|),)(( не имеет во множестве H своей симметрии Hwjf mi  1\|),)(( ~ , !}...,,1{, nik  . Доказательство теоремы 1 приведено в [10]. Симметрия в комбинаторной оптимизации определяется по-разному, в том числе особой структурой входной информации, которую представим функциями натурального аргумента. Определение 4. Назовем функции, которые симметричны относительно линии, параллельной оси абсцисс или оси ординат, прямой и обратной. Если эти функции изменяются как монотонные или линейные , то параллельная ли- ния проходит через точку их пересечения. Международный научно-технический журнал «Проблемы управления и информатики», 2018, № 3 19 Прямая и обратная функции имеют одинаковые множества определения и значений. Например, для прямой функции натурального аргумента  m j 1\|)( )...,,1( m обратной является )1...,,(\|)( 1 mj m  . Иными словами, эти функции симметричны относительно друг друга. В комбинаторной оптимизации закономерность изменения значений целевой функции зависит от упорядочения комбинаторных конфигураций. Поэтому оценку симметрии для различных классов задач рассматриваем для определенного упо- рядочения комбинаторного множества (аргумента целевой функции). Симметрию в комбинаторной оптимизации смоделируем двумя конечными последовательно- стями. Эти последовательности содержат значение решений )...,,( 1 qFFF  , 1 jj FF , полученных для задач, входные данные в которых моделируются пря- мой функцией натурального аргумента (или для задач, в которых целевая функ- ция смоделирована как прямая), и значение решений ) ~ ...,, ~ ( ~ 1 qFFF  , 1 ~~  jj FF , 1,1  qj , полученных для задач, входные данные в которых моделируются об- ратной функцией натурального аргумента (или для задач, в которых целевая функция смоделирована как обратная). Если для прямых функций значения этих последовательностей увеличиваются (или уменьшаются), а для обратных — уменьшаются (или увеличиваются), то они характеризуются приближенной симмет- рией. Если на следующем интервале комбинаторного множества значение целевой функции больше предыдущего, но оно изменяется как неубывающая или невозраста- ющая функция, то такую функцию назовем кусочно-монотонной. Приближенной симметрией также характеризуются кусочно-монотонные последовательности. Симметрия в комбинаторной оптимизации, определяемая способом моделирования целевой функции Этот вид симметрии рассмотрим на примере задач, аргументом целевой функции в которых является разбиение n-элементного множества на подмноже- ства и перестановки. К задачам разбиения относятся компоновка, кластеризация, классификация, самообучение, покрытие геометрической поверхности, разреза- ние графов и т.д. Рассмотрим разбиение на непересекающиеся классы. Разбиени- ем n-элементного множества }...,,{ 1 naaA на  подмножеств (блоков) назо- вем множество подмножеств ),...,,( 1 kkk kwww   такое, что Aww kk k   ...1 , k rw , k r k p ww  , rp  , }...,,1{, krp  , }...,,1{ nk  — количество подмножеств в kw . Подмножество )...,,( 1 k r aawk r   , Aa  , }...,,1{ n , мо- жет иметь от 1 до n элементов ( }...,,1{ nk r  ). Два разбиения kw и iw назо- вем изоморфными, если ik  и для любого подмножества kk p ww  найдется подмножество ii r ww  , для которого i r k p  . Задачу, аргументом целевой функции в которой является разбиение n-эле- ментного множества на подмножества, назовем основной, а целевую функцию (1) — прямой, если в ней нахождение оптимального решения производится по количе- ству связей между элементами одного и того же подмножества. Задачу из класса разбиения назовем обратной к основной, в которой целевая функция )(1 kwF  обратная прямой (1), т.е. результат вычисляется по количеству связей между 20 ISSN 0572-2691 элементами, находящимися в разных подмножествах ii r ww  . В этом случае ,1),)((  k j wjf если элементы Aaa ls  находятся в разных подмноже- ствах заданного разбиения, и 0),)((  k j wjf — в другом случае. Если це- левая функция (1) в основной задаче принимает наибольшее глобальное зна- чение, то в обратной для того же аргумента — наименьшее глобальное значе- ние, и наоборот. Множество W разбиения n-элементного множества на подмножества состо- ит из подмножеств W . Упорядочим W подмножествами W так, что для 1W 1 , для 2W 2 , для nW n и для kw и iw ki  .ki  Поиск опти- мального значения целевой функции в задачах разбиения в зависимости от задан- ных условий проводится или на всем множестве ,W или на подмножествах изо- морфных разбиений. Теорема 2. Для подмножеств изоморфных разбиений WW k  значение це- левой функции (1) находится в пределах ),(max)()(min '' '''' i Ww kt Ww wFwFwF lt   }...,,1{ qk , }!...,,1{, mit  , it  , kWwk   , q — количество разбиений в .W Теорема 3. Если в подмножествах kW  упорядочение kw такое, что целевая функция для kW  — дискретная монотонная (неубывающая или невозрастаю- щая), а во множестве W упорядочение подмножеств изоморфных разбиений та- кое, что ki  , а ik  или ik  , то целевая функция для такого упорядочения подмножеств — дискретная кусочно-монотонная функция (соответственно, не- убывающая или невозрастающая). Доказательство теорем 2–3 проводится с использованием комбинаторных функций [9]. Для этого упорядочения для прямой )( kwF и обратной )(1 kwF задач получим две последовательности решений, которые характеризуются при- ближенной симметрией. Пример 2. Задано множество },5,4,3,2,1{A ,5n функция натурального аргумента равна ),109,8,7,6,5,4,3,2,,1(\|)( 1  mj значение комбинаторной функции Hwjf mk  1\|),)(( и }.1,0{),)((  kwjf В табл. 1 приведены только те разбиения, для которых )( kwF для подмножеств kW  принимают наиболь- шее и наименьшее значения .52,1k Из табл. 1 видно, что целевые функции для прямой )( kwF и обратной )(1 kwF  задач изменяются как кусочно-монотонные. Две последовательно- сти решений характеризуются приближенной симметрией. Рассмотрим упорядоченную задачу (система 'H ), которая решается на множестве перестановок. Прямую целевую функцию для этого класса зада- дим выражением )(),)(()( ' 1 ' jwjfwF t j m j t    , (2) Международный научно-технический журнал «Проблемы управления и информатики», 2018, № 3 21 Таблица 1 k k k )(1 kwF )( kwF 1 1 (1, 2, 3, 4, 5) 0 55 2 2 (1, 2, 3, 4), (5) 30 25 3 2 (5, 2, 3, 4), (1) 10 45 7 2 (1, 2, 3), (4, 5) 35 18 10 2 (4, 1, 2), (3, 5) 36 19 16 2 (3, 4, 5), (1, 2) 27 28 17 3 (1, 2, 3), (4), (5) 47 8 26 3 (4, 5, 3), (1), (2) 28 27 28 3 (3, 2), (1, 4), (5) 47 8 39 3 (2, 3), (4, 5), (1) 40 15 42 4 (1, 2), (3), (4), (5) 45 1 51 4 (5, 4), (1), (2), (3) 54 10 52 5 (1), (2), (3), (4), (5) 55 0 а обратную — выражением ))()),((()( ' 1 '1 jwjfwF t j m j t    для 0))()),((( '  jwjf t j , nj 1, . (3) Сформулируем следующие теоремы, доказательства которых приведены в [9]. Входные данные зададим прямыми и обратными функциями натурального аргумента. Теорема 4. Если )...,,1(\|),)(( 1 1' mwjf m  , ),...,,1(\|)( 1 mj m  то наибольшее значение целевая функция (2) принимает для перестановки )...,,1(1' mw  , а наименьшее — для перестановки )1,...,(~ ' mw t  . Теорема 5. Если )...,,1(\|)( 1 mj m  , )...,,1(\|),)(( 1 1' mwjf m  , то наибольшее значение целевая функция (3) принимает для перестановки )1,...,(~ ' mw t  , а наименьшее — для перестановки )...,,1(1' mw  и    m j m j jm 11 2)1( , где    m j t mwF 1 '1- max )1()~( , а     m j jwF 1 1'1 min .2)( Пример 3. Положим, )3,2,1(\|),)(( 1 1'  m wjf , ),3,2,1(\|)( 1  m j 3n . Результаты вычислений для упорядо- ченной задачи, приведенные в табл. 2, характеризуются приближенной сим- метрией. Приведены значения прямой )( 'kwF и обратной )( '1 kwF  целевых функций для упорядоченной задачи, аргументом которой является перестановка. Симметрия в комбинаторной оптимизации, определяемая структурой входных данных Зададим структуру входных данных прямыми и обратными функциями нату- рального аргумента и исследуем, как они влияют на изменение значений целевой функции. Сначала рассмотрим упорядоченную задачу оптимизации и изменение Таблица 2 k Перестановка kw ' )( 'kwF )( '1 kwF 1 3, 2, 1 10 64 2 2, 3, 1 11 60 3 3, 1, 2 11 60 4 2, 1,3 13 54 5 1, 3, 2 13 50 6 1 ,2, 3 14 48 22 ISSN 0572-2691 значений целевой функции в зависимости от транспозиции ),)(( 'k j wjf функ- ции ' 1 ' \|),)(( Hwjf mk  . Комбинаторные функции, аргументом которых является перестановка, обра- зуются рекуррентным комбинаторным оператором транспозиции. Две транспози- ции ),( '' k r k l ww и ),( '' k s k g ww перестановки '' Ww k  назовем независимыми, ес- ли все элементы в них имеют разные значения, )...,,1{,,, mrgsl  . Соответствен- но, две траспозиции функции mkwjf 1 ' \|),)(( независимые, если значения этой функции в них разные. Определение 5. Дефицитом функции mkwjf 1 1' \|),)((  относительно транс- позиции назовем величину ),)((),)(()( '' g ' k s kk wsfwgfw  , значения ),)((,),)(( '' g k s k wsfwgf  которой операцией транспозиции ),( '' k s k g ww в mkwjf 1 1' \|),)((  поменялись местами. Дефицитом функции m j 1\|)( относительно транспозиции назовем величи- ну )()(' sg  , )(,)( sg  которой перемножаются на значения ),)(( ' g kwgf , ),)(( 'k s wsf функции mkwjf 1 ' \|),)(( . Для упорядоченной задачи рассмотрим, как меняется в зависимости от транспо- зиции значений ),)(( 'k j wjf целевая функция (1), если  m wjf 1 1' \|),)(( )...,,1( m и )...,,1(\|)( 1 mj m  . Теорема 6. Если в функции )...,,1(\|),)(( 1 1' mwjf m  провести транспози- цию двух значений ),)(( 1' g wgf , ),)(( 1'wsfs , то )( 'kwF для полученной перестановки '' Ww k  равна 21'1'' ))(()()( wwFwF k  . (4) Следствие 1. Если )...,,1(\|),)(( 1 1' mwjf m  и )...,,1(\|)( 1 mj m  , то целевая функция '' 1 ' min 1' max )~()~()( l k l l k wwFwF     , где        2 m , а       ,если},...,,6,4,2{ ,если},1...,,5,3,1{ )~( 1 ' Zmn Zmn w k l }2...,,4,2{ jZ  , }12...,,3,1{1  jZ . Следствие 2. Если Rwjfj  ),)(( 1' , Rj  )( ,  1 1' ),)(( jj wjf ),)1(( 1'wjf  , )1()(  jj , а целевая функция для '' Ww t  принимает наибольшее значение, то наименьше ее значение для перестановки '' Ww k  равно .)()()( 1 ''' max ' min     l l t l tk wwFwF Если Rwjfj  ),)(( 1' , Rj  )( , ),)1((),)(( 1' 1 1' wjfwjf jj   , )1()(  jj , а целевая функция для '' Ww k  принимает наименьшее значе- Международный научно-технический журнал «Проблемы управления и информатики», 2018, № 3 23 ние, то наибольшее ее значение для перестановки '' Ww t  равно '' 1 ' min ' max )()()( l k l l kt wwFwF     , R — множество действительных чисел. Последовательность решений для упорядоченной задачи комбинаторной оптимизации, входные данные в которых задаются прямыми функциями натурального аргумента, имеет вид: ),(),(...,),(),( ' min ''' max kt wFwFwFwF )()( *'' wFwF  . Если в упорядоченной задаче входные данные заданы об- ратными функциями натурального аргумента, то для этого же порядка для некоторых структур входных данных получаем симметричную последова- тельность ),(),(...,),(),( ' max ''' min tk wFwFwFwF образованную одним и тем же количеством транспозиций одинаковых значений комбинаторной функции. Это свойство характерно и для базовой задачи. На примере некоторых разрешимых задач комбинаторной оптимизации из разных классов рассмотрим, как изменяется целевая функция в зависимости от прямых и обратных функций натурального аргумента, которыми задаются вход- ные данные (в подклассах разрешимых задач — известный способ аналитическо- го нахождения глобального оптимума). Из выражения (1) видно, что для фиксированного аргумента последователь- ность величин произведения значений числовой и комбинаторной функций — комбинации элементов заданной матрицы. Если одна из них — бинарная после- довательность, то из матрицы выбираются не все элементы. Эту последователь- ность назовем вариантом решения задачи. По способу образования множество ва- риантов решения разделяется на подмножества. В подмножестве 1K находятся варианты решения задачи, значения которых выбраны из матрицы начиная с эле- мента по адресу 1, во втором 2K — начиная с адреса 2 и т.д. Количество таких подмножеств для различных классов задач разное. Соответственно упорядочива- ется подмножествами 221 ...,,, nKKK множество комбинаторных конфигураций (перестановки). Образованные подмножества состоят из меньших подмножеств. Такое упорядочение множества комбинаторных конфигураций проводим по двум, трем и более значениям этой последовательности. Оно не зависит от входных данных. Для некоторых прикладных задач рассмотрим изменение значений целе- вой функции при упорядочении перестановок подмножествами, начиная с 1K и заканчивая 2nK . Задача размещения объектов формулируется следующим образом. Множе- ство одногабаритных или произвольной формы объектов необходимо разместить в области размещения так, чтобы смоделированная по заданным критериям целе- вая функция принимала оптимальное значение, а расстояние между объектами было равно определенной величине. Задача коммивояжера: задано n городов, расстояния между которыми известны. Координаты входа и выхода каждого города совпадают. Необходимо найти кратчайший путь, который проходит через все города один раз и возвращается в исходный пункт. Сформулируем следующие теоремы, доказательства которых приведены в [9]. 24 ISSN 0572-2691 Теорема 7. Если в задаче размещения входные данные задаются )...,,1(\|),)(( 1 1 mwjf m  , )...,,1(\|)( 1 mj m  , то наибольшее значение функ- ция цели (1) принимает для 1 1 ),...,1( Knw  , а наименьшее — для kw~ .)1...,,( mKn  Наибольшее значение целевой функции равно )( 1wF 6 )12()1(   mmm , а наименьшее — соответственно )~( kwF 6 )2()1(   mmm или '1 1 )~( 6 )12()1( )~( jj p j k w mmm wF      ,        4 n p . Следствие 3. Если в задаче размещения входные данные  m wjf 1 1 \|),)(( )1...,,(m , )...,,1(\|)( 1 mj m  , то наименьшее значение целевая функция (1) принимает для перестановки 1 1 ),...,1( Knw  , а наибольшее — для m k Knw  )1,...,(~ . Наибольшее значение целевой функции равно '1 1 )( 6 )2()1( )~( j p j j k w mmm wF      , а наименьшее — соответственно 6 )2()1( )( 1   mmm wF . Теорема 8. Если в задаче коммивояжера значение комбинаторной функции bjkwjf  01),)(( , }1,0{)(  j , где mj ,1 , 0,0 bk — целые произ- вольные числа и ,10 k то наибольшее значение функция цели (1) принимает для перестановки 1Kw i  , а наименьшее значение — для перестановки 2 n k Kw . Следствие 4. Если в задаче коммивояжера значение комбинаторной функции )()()(),)(( 0001 bkbjkbmkwjf  , }1,0{)(  j , где mj ,1 , 0,0 bk — целые произвольные числа и 10 k , то наименьшее значение функ- ция цели (1) принимает для перестановки 1Kw i  , а наибольшее — для переста- новки 2 n k Kw . Теорема 9 (справедлива для 6n ). Если входные данные в задаче ком- мивояжера заданы прямой функцией ),,,...,,,,(\|),)(( '' 11 1 mm m bcbcbcwjf  }1,0{)(  j и bc  , то для наименьшего значения )( kwF перестановка s k Kw  , где 1Zs . Для наибольшего значения )( iwF перестановка ,t i Kw  где .Zt Если входные данные в задаче коммивояжера заданы обратной функцией ),,...,,,,(\|),)(( '' 11 1 mm m bcbcbcwjf  , }1,0{)(  j и bc  , то в задаче комми- вояжера для наибольшего значения )( kwF перестановка t i Kw  , где 1Zt . Для наименьшего значения )( kwF перестановка s k Kw  , где Zs ,       ,если, ,если, 1 ' Zmb Zmc c .       .если, ,если, 1' Zmb Zmc b . Пример 4. Задача размещения. Положим, 4n , Международный научно-технический журнал «Проблемы управления и информатики», 2018, № 3 25 задача а) )6,5,4,3,2,1(\|),)(( 1 1  mwjf , );6,5,4,3,2,1()\|( 1  mj задача б) )1,2,3,4,5,6()\|( 1  mj , ).6,5,4,3,2,1(\|),)(( 1 1  mwjf Результаты решения для задач а) и б) приведены в табл. 3, значения )( kwF (задача а) и )( ~ kwF (задача б) для задачи размещения одногабаритных объектов. Пример 5. Задача коммивояжера. Задано 5n ; а) ),10,9,8,7,6,5,4,3,2,1(\|),)(( 1 1  mwjf )1,0,1,0,0,1,1,0,0,1(\|)( 1  mj ; б) )1,0,1,0,0,1,1,0,0,1(\|)( 1  mj , ).1,2,3,4,5,6,7,8,9,10(\|),)(( 1 1  mwjf Результаты решения для задач а) и б) приведены в табл. 4. Поскольку в задаче коммивояжера количество нетождествен- ных маршрутов равно 2 )!1( n , приведены только те перестановки, которые требуют исследования. Для задачи коммивояжера и задачи о назначениях одна из функций натурально- го аргумента принимает значения }1,0{ . Поэтому для некоторых структур входных данных, которые заданы прямыми и обрат- ными функциями, последовательность ре- шений для этих классов задач может быть одинаковая. Пример 6. Задача коммивояжера. Положим 4n ; задача а) )64,32,16,8,4,2(\|),)(( 1 1  mwjf , )1,0,1,1,0,1(\|)( 1  mj ; задача б) )2,4,8,16,32,64(\|),)(( 1 1  mjf , ).1,0,1,1,0,1(\|)( 1  mj Результаты решения обеих задач занесены в табл. 5. Таблица 4 Подмножество ,tK }2...,,1{  nt Перестановка ,kw }!...,,1{ nk Функция )( ~ kwF для задачи а) Функция )( kwF для задачи б) 2, 1, 3, 4, 5 27 28 3, 1, 2, 4, 5 27 28 1K 3, 2, 1, 4, 5 27 28 3, 4, 1, 2, 5 27 28 1, 2, 3, 4, 5 27 28 1, 2, 4, 3, 5 27 28 2, 3, 1, 4, 5 28 27 Таблица 3 k kw Значе- ния )( kwF Значе- ния )~( kwF 1 2 3 4 1 1,2,3,4 56 91 2 1,3,2,4 58 89 3 1,2,4,3 58 89 4 1,3,4,2 62 85 5 1,4,2,3 62 85 6 2,1,3,4 64 83 7 1,4,3,2 64 83 8 2,1,4,3 66 81 9 2,3,1,4 70 77 10 3,1,2,4 70 77 11 3,2,1,4 74 73 12 3,1,4,2 74 73 13 2,4,1,3 74 73 14 4,1,2,3 78 69 15 2,3,4,1 78 69 16 4,1,3,2 80 67 17 2,4,3,1 80 67 18 3,4,1,2 82 65 19 4,2,1,3 82 65 20 3,2,4,1 82 65 21 4,3,1,2 86 61 22 3,4,2,1 86 61 23 4,2,3,1 88 59 24 4,3,2,1 91 57 26 ISSN 0572-2691 2K 3, 1, 4, 2, 5 28 27 1, 3, 2, 4, 5 28 27 1, 3, 4, 2, 5 28 27 3K 1, 4, 3, 2, 5 28 27 — 1, 4, 2, 3, 5 28 27 Таблица 5 Подмножество ,tK }2...,,1{  nt Перестановка ,kw }!...,,1{ nk )( kwF для задачи а) )( ~ kwF для задачи б) 1K 2, 1, 3, 4 102 102 1, 2, 3, 4 90 90 2K 2, 3, 1, 4 60 60 Для особых структур входных данных и определенного упорядочения ком- бинаторных множеств (аргумента целевой функции) последовательность решений )...,,( 1 qFFF  , 1 jj FF , полученных для прямой функции натурального аргу- мента, является симметричной к последовательности решений ), ~ ...,, ~ ( ~ 1 qFFF  1 ~~  jj FF , полученных для обратной функции натурального аргумента. При этом значения jF и jF ~ вычислены для одного и того же аргумента .Wwk  Заключение Свойство симметрии в комбинаторной оптимизации зависит от симмет- рии комбинаторных множеств и комбинаторных конфигураций. Оно проявля- ется благодаря специальному моделированию целевой функции и особой структуре входной информации. Если входные данные для некоторых классов задач заданы прямыми или обратными функциями натурального аргумента, то последовательность решений )...,,( 1 qFFF  , полученная для прямой функции натурального аргумента, симметрична последовательности ), ~ ...,, ~ ( ~ 1 qFFF  по- лученной для обратной функции натурального аргумента. Знание свойств комбинаторных функций позволяет устанавливать изменение значений целе- вой функции в зависимости от транспозиции элементов в перестановке и от упорядочения комбинаторных конфигураций. Полученные результаты можно использовать при решении задач комби- наторной оптимизации различных классов для анализа изменения значений целевой функции в зависимости от структуры входных данных с учетом сим- метрии комбинаторных конфигураций. Международный научно-технический журнал «Проблемы управления и информатики», 2018, № 3 27 Н.К. Тимофієва ПРО МОДЕЛЮВАННЯ СИМЕТРІЇ В КОМБІНАТОРНІЙ ОПТИМІЗАЦІЇ Показано, що симетрія в комбінаторній оптимізації проявляється в залеж- ності від структури вхідних даних і способу моделювання цільової фун к- ції. В її основі лежить симетрія комбінаторних множин та комбінаторних конфігурацій (аргументу цільової функції). Її математичну модель подано скінченними послідовностями, які характеризуються наближеною або точ- ною симетрією. N.K. Tymofijeva MODELING OF SYMMETRY IN COMBINATORIAL OPTIMIZATION It is shown that symmetry in combinatorial optimization manifests itself de- pending on the structure of the input data and the method of modeling of the objective function. It is based on the symmetry of combinatorial sets and com- binatorial configurations (the objective function argument). Its mathematical model is represented by finite sequences, which are characterized by ap- proximate or exact symmetry. 1. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. — М. : Наука, 1981. — 543 с. 2. Фрид Э. Элементарное введение в абстрактную алгебру. Пер. с венгерского. — М. : Мир, 1979. — 230 с. 3. Loeschner K. Symmetry in combinatorial optimization // A thesis in the Departament of Mathematics and Statistics. — Canada : Concordia University. — 2002. — 67 p. 4. Карманов В.Г. Математическое программирование. — М. : Наука, 1986. — 288 с. 5. Еремин И.И. Теория двойственности в линейной оптимизации. — Челябинск: Изд-во ЮУрГУ, 2005. — 195 с. 6. Еремин И.И. Симметричная двойственность для задач последовательного линейного программирования // Докл. АН СССР. — 1991. — 317, № 5. — C. 1045–1048. 7. Медвежонков Д.С. Симметричная двойственность в выпуклой оптимизации и модели потокораспределения: Автореф. дис. ... канд. физ.-мат. наук. — Ин-т систем энерге- тики им. Л.А. Мелентьева СО РАН, Иркутск. — 2013. — 19 с. 8. Тимофієва Н.К. Про симетрію комбінаторних множин // УСиМ. — 2017. — № 1. — С. 3–16. 9. Тимофієва Н.К. Теоретико-числові методи розв’язання задач комбінаторної оптимі- зації: Дис. … докт. техн. наук. — Ін-т кібернетики ім. В.М. Глушкова НАН України. — 2007. — 374 с. 10. Тимофеева Н.К. Матрицы в задачах комбинаторной оптимизации // Проблемы управ- ления и информатики. — 1996. — № 3. — С. 104–113. Получено 12.01.2018 Статья представлена к публикации членом редколлегии академиком НАН Украины А.А. Чикрием. https://spectrum.library.concordia.ca/view/creators/Loeschner=3AKristina=3A=3A.html

О моделировании симметрии в комбинаторной оптимизации

Репозитарії

Схожі ресурси