Умовна оптимізація лінійної функції на перестановках

Розглянуто підхід до розв’язання комбінаторних оптимізаційних задач з лінійною функцією цілі та додатковими обмеженнями на комбінаторній множині перестановок, представленої у вигляді графа. Приведено числовий приклад задачі....

Повний опис

Збережено в:

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

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-111505
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1115052025-02-23T18:29:43Z Умовна оптимізація лінійної функції на перестановках Условная оптимизация линейной функции на перестановках Constrained optimization of linear functions on combinatorial configurations permutations Донець, Г.П. Нагірна, А.М. Розглянуто підхід до розв’язання комбінаторних оптимізаційних задач з лінійною функцією цілі та додатковими обмеженнями на комбінаторній множині перестановок, представленої у вигляді графа. Приведено числовий приклад задачі. Рассмотрен подход к решению оптимизационных задач с линейной функцией цели и дополнительными ограничениями на комбинаторном множестве перестановок, представленном в виде графа. Приведен числовой пример с учетом свойства множества перестановок и структурных моделей графа. Approach to the solution of optimization problems with linear function of the purpose is considered and additional restrictions on the combinatorial set of permutations, represented as a graph. The numerical example is given. 2014 Article Умовна оптимізація лінійної функції на перестановках / Г.П. Донець, А.М. Нагірна // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 16-23. — Бібліогр.: 6 назв. — укр. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/111505 519.8 uk Теорія оптимальних рішень application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
description	Розглянуто підхід до розв’язання комбінаторних оптимізаційних задач з лінійною функцією цілі та додатковими обмеженнями на комбінаторній множині перестановок, представленої у вигляді графа. Приведено числовий приклад задачі.
format	Article
author	Донець, Г.П. Нагірна, А.М.
spellingShingle	Донець, Г.П. Нагірна, А.М. Умовна оптимізація лінійної функції на перестановках Теорія оптимальних рішень
author_facet	Донець, Г.П. Нагірна, А.М.
author_sort	Донець, Г.П.
title	Умовна оптимізація лінійної функції на перестановках
title_short	Умовна оптимізація лінійної функції на перестановках
title_full	Умовна оптимізація лінійної функції на перестановках
title_fullStr	Умовна оптимізація лінійної функції на перестановках
title_full_unstemmed	Умовна оптимізація лінійної функції на перестановках
title_sort	умовна оптимізація лінійної функції на перестановках
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2014
url	https://nasplib.isofts.kiev.ua/handle/123456789/111505
citation_txt	Умовна оптимізація лінійної функції на перестановках / Г.П. Донець, А.М. Нагірна // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 16-23. — Бібліогр.: 6 назв. — укр.
series	Теорія оптимальних рішень
work_keys_str_mv	AT donecʹgp umovnaoptimízacíâlíníjnoífunkcíínaperestanovkah AT nagírnaam umovnaoptimízacíâlíníjnoífunkcíínaperestanovkah AT donecʹgp uslovnaâoptimizaciâlinejnojfunkciinaperestanovkah AT nagírnaam uslovnaâoptimizaciâlinejnojfunkciinaperestanovkah AT donecʹgp constrainedoptimizationoflinearfunctionsoncombinatorialconfigurationspermutations AT nagírnaam constrainedoptimizationoflinearfunctionsoncombinatorialconfigurationspermutations
first_indexed	2025-11-24T10:12:34Z
last_indexed	2025-11-24T10:12:34Z
_version_	1849666206215176192
fulltext	16 Теорія оптимальних рішень. 2014 ТЕОРІЯ ОПТИМАЛЬНИХ РІШЕНЬ Розглянуто підхід до розв’язання комбінаторних оптимізаційних задач з лінійною функцією цілі та додатковими обмеженнями на комбінаторній множині перестановок, представленої у вигляді графа. Приведено числовий приклад задачі.  Г.П. Донець, А.М. Нагірна, 2014 УДК 519.8 Г.П. ДОНЕЦЬ, А.М. НАГІРНА УМОВНА ОПТИМІЗАЦІЯ ЛІНІЙНОЇ ФУНКЦІЇ НА ПЕРЕСТАНОВКАХ Вступ. Важливу роль у множині обчислень відіграють задачі, де необхідно встановити попарний зв’язок між елементами. Для моделювання таких ситуацій використовують абстракту математичну модель – графи. До типових задач теорії графів можна віднести наступні: проектування найкоротшої комунікаційної мережі, синтез структурно-надійної мережі циркуляційного зв'язку, аналіз надійності стохастичних мереж зв'язку, задачу про найкоротший ланцюг, складання розкладу руху транспортних засобів, розміщення пунктів швидкої допомоги, розміщення телефонних станцій, задачу про максимальний потік, задачу про розміщення й покриття, розфарбування в графах, покриття схеми заданим набором типових підсхем та ін. Основні властивості графа досить часто необхідні для розуміння різних алгоритмів, які використовуються для розв’язання широкого класу комбінаторних задач [1]. На підставі встановленого взаємозв’язку між задачами на комбінаторних конфігураціях і їх графами вивчаються деякі структурні властивості допустимої області. Графічне представлення комбінаторних множин у вигляді графів дозволяє отримати нові підходи та методи вирішення. Дана работа продовжує дослідження робіт [2 – 6]. У роботі описується застосування нового підходу до розв’язання екстремальних комбінаторних задач із лінійною функцією цілі з урахуванням тісного взаємозв’язку між комбінаторними множинами і графами комбінаторних конфігурацій. УМОВНА ОПТИМІЗАЦІЯ ЛІНІЙНОЇ ФУНКЦІЇ НА ПЕРЕСТАНОВКАХ Теорія оптимальних рішень. 2014 17 1. Постановка задачі. Розглянемо задачу комбінаторної оптимізації у якій задана цільова функція ( ) :F x X R , допустима комбінаторна множина { }X x , та додаткові лінійні обмеження, які утворюють опуклу многогранну множину nD R наступного вигляду: { \| }nD x R Gx d   , де m nG R  , md R . Запишемо лінійні обмеження у вигляді нерівностей: 1 , n ij j i j Gx g x d    mi N , nj N . (1) Необхідно знайти альтернативу, 0 ,x X на якій цільова функція приймає екстремальне значення 0( ) ( ) x X f x extrf X   , {min,max}extr . Розглянемо задачу на комбінаторній множині перестановок ( )nP A , кількість елементів якої рівна !n . Послідовність перестановок, згідно методу їх генерування, інтерпретується як граф nG , вершини якого відповідають точкам множини перестановок ( )nP A . У графі вершини розміщуються згідно деякої визначеної властивості, тому спочатку можна визначити крайні вершини графа, а потім розкласти граф на підграфи. Властивість представлення графа у вигляді графів меншої розмірності, тобто більш простої структури, є важливою для розв’язання екстремальних задач. Для задачі ( ) ( )F x f x , без додаткових обмежень екстремальне значення лінійної функції 1 1 2 2( ) ... n nf x c x c x c x    , 1,...n i , при упорядкуванні коефіцієнтів за зростанням на графі перестановок ( )nG P досягається в перестановці (1,2,..., )n , а мінімальне – ( , 1,...,2,1)n n  . Призначимо кожному коефіцієнту відповідний індекс з множини натуральних чисел {1,2,..., }mN m , тоді для множини коефіцієнтів 1 2( , ,..., )nC c c c розглянемо дворядковий запис відображення : :u N C 1 2 ... , (1) (2) ... ( ) m u u u u m        де ( ) ,u i C .mi N Означення 1. Нормалізацією функції 1 ( ) n i i i f x c x   називається відображення перестановки : ,u N C що встановлює впорядкування коефіцієнтів 1 2, ,..., nc c c цільової функції за зростанням (спаданням) [3]. Г.П. ДОНЕЦЬ, А.М. НАГІРНА 18 Теорія оптимальних рішень. 2014 Щоб повернутися до початкової форми лінійної функції, необхідно зробити обернене відображення: 1 : .u N C  Сформулюємо нову підзадачу, де необхідно визначити множину зв’язних пар перестановок ( , ),x x для яких при id , mi N має місце: argmin ( ), iGx d x G x   (2) argmax ( ). iGx d x G x   (3) Для розв’язування задачі скористаємося методом локалізації значення лінійної функції заданої на перестановках [4]. Оскільки метод локалізації застосовувався до екстремальної задачі без додаткових обмежень, то враховуючи умову нашої задачі (1) – (3) даний метод необхідно застосувати до кожного додаткового обмеження. Потім нормалізувати розв’язки за допомогою перестановки iu і знайти загальний розв’язок. Для знаходження екстремуму цільової функції ( )F X впорядкуємо елементи отриманої множини в лексикографічному порядку, користуючись наступним означенням. Означення 2. Перестановку 1 2... ng g g називають лексикографічно наступну за 1 2... ng g g   , якщо не існує перестановки 1 2... ng g g   такої, що 1 2... ng g g    1 2... ng g g   і 1 2 1 2... ...n ng g g g g g    [5]. Алгоритм побудови лексикографічно впорядкованої перестановки. 1. Необхідно знайти такі числа jg і 1jg  , що 1( )j jg g   1 2( ... )j j ng g g     . Для цього треба знайти в перестановці першу справа пару сусідніх чисел, у якій число, що ліворуч, менше від числа, що праворуч. 2. Записати у j -ту позицію таке найменше з чисел 1 2, ,...,j j ng g g  , яке водночас більше, ніж .jg 3. Записати у висхідному порядку число jg і решту чисел 1 2, , ...,j j ng g g  у позиції 1,..., .j n З лексикографічно впорядкованої множини вибираємо елемент найвищого порядку і знаходимо екстремальне значення цільової функції. 2. Алгоритм розв’язування екстремальної задачі з додатковими обмеженнями на комбінаторній множині перестановок. Алгоритм складається із наступної послідовності кроків: УМОВНА ОПТИМІЗАЦІЯ ЛІНІЙНОЇ ФУНКЦІЇ НА ПЕРЕСТАНОВКАХ Теорія оптимальних рішень. 2014 19 1) нехай дано цільову функцію 1 1 2 2( ) ... n nf x c x c x c x    , нормалізовану на множині перестановок nP . Тоді для кожної обмежуючої функції граф перестановок ( )nG P має стандартний вигляд; 2) розв’язуємо задачу локалізації для кожного обмеження id , mi N і отримуємо допустимі множини перестановок iG ; 3) за допомогою перестановок 1 2, ,..., iu u u нормалізуємо множини 1 2, ,..., ;iG G G 4) знаходимо загальний розв’язок, що задовольняє всі обмеження, 1 2 ... iG G G G  , де 1,..., ;i n 5) впорядкуємо елементи множини G лексикографічним способом в порядку зростання. Елемент множини найвищого порядку буде оптимальним розв’язком, який забезпечує знаходження екстремального значення цільової функції ( ).F X Підграф графа ( )nG P , у якого зафіксовано останній елемент i , будемо називати гранню графа ( )nG P і позначатимемо iG . Всі грані будемо зображати у вигляді ребра, інцедентними вершинами якого є початкова і кінцева вершини відповідного підграфа. Структурна схема графа ( )nG P має вигляд (рис. 1). РИС. 1. Структурна схема графа ( )nG P Аналогічно як на рис. 1 будуються структурні схеми підграфів iG , в яких фіксуються два індекси і т. д. За рахунок декомпозиції структурної схеми підграфів обмежуючих функцій ig знаходимо допустиму множину перестановок для ig у вигляді підграфів з різною кількістю індексів. Користуючись оберненою перестановкою індексів підграфів 1 iu  знаходимо 1nG nG ... 1G Г.П. ДОНЕЦЬ, А.М. НАГІРНА 20 Теорія оптимальних рішень. 2014 відповідні індекси підграфів у базовій множині, тобто в множині цільової функції [6]. 3. Приклад. Знайти максимальне значення цільової функції ( )f x  1 2 3 4 52 3 5 6 7 ,x x x x x     при обмеженні 1 2 3 45 8 4g x x x x     52 45x  на множині перестановок (1, 2, 3, 4, 5). Розв’язання. Граф множини перестановок (1, 2, 3, 4, 5) складається із 120 вершин і 5 підграфів. Тому для простоти викладу матеріалу зображуватимемо відповідний підграф при фіксованому останньому елементі на 5-у місці, потім 4-у і т. д. Розглянемо додаткове обмеження 1 2 3 4 55 8 4 2 45g x x x x x      та нормалізуємо його у порядку зростання за допомогою перестановки 1 1 2 3 4 5 4 1 5 3 2 u        . Отримуємо обмежуючу функцію вигляду 1 2 3 4 52 4 5 8 45.g x x x x x       Користуючись методом локалізації, представимо граф перестановок для нормалізованих функцій, вершини якого генеруються методом переміщення максимального елемента. Визначимо макси- мальне і мінімальне значення обмежуючої функції на множині перестановок: max ( ) 1 1 2 2 4 3 5 4 8 5 77;g x            min ( ) 1 5 2 4 4 3 5 2 8 1 43.g x            Аналогічно визначаємо мінімальне і максимальне значення в інших крайніх вершинах підграфа. Структурний граф переставного многогранника буде мати вигляд, показаний на рис. 2. РИС. 2. Структурний граф переставного многогранника 57 63 56 50 46 (5,4,2,1,3) (5,4,3,2,1) (5,3,2,1,4) (4,3,2,1,5) (1,2,4,5,3) (1,2,3,4,5) (1,2,3,5,4) (1,3,4,5,2) (2,3,4,5,1) (5,4,3,1,2)64 70 74 77 43 УМОВНА ОПТИМІЗАЦІЯ ЛІНІЙНОЇ ФУНКЦІЇ НА ПЕРЕСТАНОВКАХ Теорія оптимальних рішень. 2014 21 На структурних графах зображено крайні точки підграфів (гіперплощин). Максимальне значення обмежуючої функції знаходиться в точках зліва, а мінімальне – справа. Основною умовою існування допустимого розв’язку є задоволення нерівності 45,g  тому пошук здійснюємо лише на останньому підграфі, де 43 57.g  Фіксуємо останню координату перестановки 5 1x  і розглядаємо підграф, при 4,n  рангу 1,r  де остання координата фіксована (рис. 3). РИС. 3. Структурний граф при 4n  Два нижні підграфи, що показані на рис. 3, задовольняють умову, де 44 53,g  43 49.g  Тому розглядаємо верхній підграф, зафіксувавши 4 3,x  відповідно структурний граф матиме вигляд показаний на рис. 4. РИС. 4. Структурний граф при 3n  Оскільки нижній підграф задовольняє умову, то 1 (4,5,2,3,1)x  , 2 (5,4,2,3,1)x  . Розглянемо підграф, зафіксувавши 4 2x  (рис. 5). РИС. 5. Структурний граф при 3n  (5,3,2,4) (5,4,2,3) (5,4,3,2) (2,3,5,4) (2,4,5,3) (3,4,5,2) (2,3,4,5) (4,3,2,5) 4453 4756 5157 4349 (5,2,4) (5,4,2) (2,5,4) (4,5,2) (2,4,5) (4,2,5)53 51 51 48 4445 (5,3,4) (5,4,3) (3,5,4) (4,5,3) (3,4,5) (4,3,5)49 47 48 45 4344 Г.П. ДОНЕЦЬ, А.М. НАГІРНА 22 Теорія оптимальних рішень. 2014 Враховуючи умову 45,g  отримаємо розв’язки 3 (5,4,3,2,1),x  4 (4,5,3,2,1),x  5 (5,3,4,2,1).x  Отже, допустима множина, що визначається обмеженням 45,g  буде складатися із наступних точок: 1 (4,5,2,3,1),x  2 (5,4,2,3,1),x  3 (5,4,3,2,1),x  4 (4,5,3,2,1),x  5 (5,3,4,2,1).x  Користуючись перестановкою нормалізації 1 1 2 3 4 5 2 5 4 1 3 u        знаходимо базову множину: 1 (3,4,1,2,5),x  2 (3,5,1,2,4),x  3 (2,5,1,3,4),x  4 (2,4,1,3,5),x  5 (2,5,1,4,3).x  Впорядкуємо елементи множини в лексикографічному порядку. Тоді еле- менти множини будуть мати наступний порядок слідування: 1 (2,4,1,3,5),x  2 (3,4,1,2,5),x  3 (2,5,1,3,4),x  4 (3,5,1,2,4),x  5 (2,5,1,4,3).x  Найвищий порядок слідування у базовій множині має точка 1 (2,4,1,3,5)x  . Отже, максимальне значення цільової функції при підстановці у 1 2 3 4 5( ) 2 3 5 6 7f x x x x x x     рівно 1( ) 74.f x  УМОВНА ОПТИМІЗАЦІЯ ЛІНІЙНОЇ ФУНКЦІЇ НА ПЕРЕСТАНОВКАХ Теорія оптимальних рішень. 2014 23 Висновок. Побудовано та описано підхід до розв’язання оптимізаційної задачі з лінійною функцією цілі та додатковими обмеженнями на комбінаторній множині перестановок із застосуванням теорії графів та многогранників. Де- тально досліджено числовий приклад з урахуванням властивостей множини перестановок, лексикографічного упорядкування її елементів та структурних моделей графа та підграфів. Подальша робота буде направлена на реалізацію й адаптацію нових алго- ритмів на інших комбінаторних конфігураціях, при ширшому використанні властивостей графів з урахуванням зростання потужності множини та проведення числових експериментів у сучасних системах програмування. Г.А. Донец, А.Н. Нагорная УСЛОВНАЯ ОПТИМИЗАЦИЯ ЛИНЕЙНОЙ ФУНКЦИИ НА ПЕРЕСТАНОВКАХ Рассмотрен подход к решению оптимизационных задач с линейной функцией цели и дополнительными ограничениями на комбинаторном множестве перестановок, представленном в виде графа. Приведен числовой пример с учетом свойства множества перестановок и структурных моделей графа. G.A. Donets, A.N. Nagornaja CONSTRAINED OPTIMIZATION OF LINEAR FUNCTIONS ON COMBINATORIAL CONFIGURATIONS PERMUTATIONS Approach to the solution of optimization problems with linear function of the purpose is considered and additional restrictions on the combinatorial set of permutations, represented as a graph. The numerical example is given. 1. Роберт Седжвик, Кевин Уейн. Алгоритмы на java. – М.: Питер, 2013. – 848 с. 2. Донец Г.А., Колечкина Л.Н. Об одной задачи оптимизации дробно-линейной функции цели на перестановках // Проблемы управления и информатики. – 2010. − № 2. – С. 12−16. 3. Донец Г.А., Колечкина Л.Н. Локализация значений линейной функции заданной на перестановках // Радиоэлектроника и информатика. – 2009. – № 1. – С. 50 – 61. 4. Донец Г.А., Колечкина Л.Н. Об одном подходе к решению комбинаторной задачи оптимизации на графах // Управляющие системы и машины. – 2009. − № 4. – С. 36 − 42. 5. Донец Г.А., Колечкина Л.Н. Алгоритм поиска значений линейной функции на лексикографически упорядоченных перестановках // Теорія оптимальних рішень. – 2009. – № 8. – С. 3−8. 6. Донец Г.А., Колечкина Л.Н. Построение гамильтонова пути в графах перестановочных многогранников // Кибернетика и системный анализ. – 2010. – № 1. – С. 10 – 16. Одержано 20.03.2014

Умовна оптимізація лінійної функції на перестановках

Репозитарії

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