Моделі, методи і алгоритми в задачах евклідової комбінаторної оптимізації

Размещено на http://www.allbest.ru/

Національна академія наук україни

Інститут проблем машинобудування імені А.М. Підгорного

Автореферат

дисертації на здобуття наукового ступеня кандидата фізико-математичних наук

01.05.02 - математичне моделювання та обчислювальні методи

Моделі, методи і алгоритми в задачах евклідової комбінаторної оптимізації

Недобачій Станіслав Іванович

Харків - 1999

Дисертацією є рукопис.

Робота виконана в Полтавському державному технічному університеті імені Юрія Кондратюка Міністерства освіти України

Науковий керівник:

доктор фізико-математичних наук, професор Ємець Олег Олексійович, Полтавський державний технічний університет імені Юрія Кондратюка, завідувач кафедри прикладної математики та математичного моделювання.

Офіційні опоненти:

доктор фізико-математичних наук, професор Яковлв Сергій Всеволодович, Харківський державний університет внутрішніх справ, начальник факультету управління та інформатики;

кандидат фізико-математичних наук, доцент Гребеннік Ігор Валерійович, Харківський державний технічний університет радіоелектроніки, доцент кафедри системотехніки.

Провідна установа:

Інститут кібернетики імені В.М. Глушкова НАН України, відділ методів розв'язування складних задач оптимізації, місто Київ.

Учений секретар спеціалізованої вченої ради Б.П. Зайцев

Анотація

лінійний евклідовий прямокутний множина

Недобачій С.І. Моделі, методи і алгоритми в задачах евклідової комбінаторної оптимізації.

Дисертацією є рукопис, поданий на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальнастю 01.05.02 математичне моделювання та обчислювальні методи. Інститут проблем машинобудування імені А.М. Підгорного НАН України, Харків, 1999.

Розглядаються опуклі оболонки областей визначення оптимізаційних задач, моделями яких є задачі евклідової оптимізації на переставних множинах. Визначено незвідні системи лінійних обмежень загального переставного і загального поліпереставного многогранників та їх нові властивості. Одержано нові властивості переставного многогранника. Викладено новий метод точного розв'язування задачі мінімізації зваженої довжини зв'язуючої сітки при лінійному розташуванні прямокутних елементів, розроблено алгоритм його реалізації на ПЕОМ.

Ключові слова: комбінаторна оптимізація, евклідові комбінаторні множини, переставлення, поліпереставлення, опуклі оболонки, комбінаторні многогранники.

Аннотация

Недобачий С.И. Модели, методы и алгоритмы в задачах евклидовой комбинаторной оптимизации.

Диссертация является рукописью, представленной на соискание ученой степени кандидата физико-математических наук по специальности 01.05.02 математическое моделирование и вычислительные методы. Институт проблем машиностроения имени А.Н. Подгорного НАН Украины, Харьков, 1999.

Рассматриваются выпуклые оболочки областей определения оптимизационных задач, моделями которых являются задачи евклидовой оптимизации на перестановочных множествах. Получены неприводимые системы линейных ограничений выпуклой оболочки множества перестановок с повторениями общего перестановочного многогранника и выпуклой оболочки множества полиперестановок с повторениями общего полиперестановочного многогранника. Для каждого из этих многогранников определены уравнения гиперграней, выраженные через неизбыточные ограничения, установлено их количество, сделано описание вершин уравнениями гиперграней. Определено количество гиперграней, сходящихся в одной и той же вершине.

Получено новое доказательство теоремы о совпадении вершин общего перестановочного многогранника с множеством перестановок с повторением, индуцирующем этот многогранник.

Установлена связь между количеством гиперграней произведения многогранников и количеством гиперграней многогранников-сомножителей, образующих это произведение. То же сделано и для вершин произведения многогранников.

Для перестановочного многогранника определено r-расстояние между двумя произвольными его вершинами наименьшее количество рёбер, соединяющих эти вершины. Изложен алгоритм построения пути между двумя произвольными вершинами, состоящего из наименьшего количества рёбер. Определено количество вершин, находящихся на одном и том же r-расстоянии от произвольной фиксированной вершины и установлена несмежность этих вершин.

Установлены свойства одного отображения множества перестановок первых n натуральных чисел в множество перестановок с повторениями, элементами которых являются абсолютные величины всех возможных пар этих чисел, возникающего в задаче минимизации взвешенной длины связующей цепи при линейном расположении прямоугольных элементов, а именно: доказано необходимое и достаточное условие существования прообраза; изложен алгоритм построения прообраза или установления его отсутствия; определено наименьшее количество рёбер, соединяющих две вершины многогранника, являющегося выпуклой оболочкой рассматриваемого множества перестановок с повторениями, прообразы которых есть смежные вершины многогранника выпуклой оболочки множества перестановок первых n натуральных чисел. Определены гиперплоскости, для которых отношение количества всех вершин многогранника выпуклой оболочки множества перестановок с повторениями, лежащих в этих гиперплоскостях, к количеству его прообразных вершин, принадлежащих этим же гиперплоскостям, есть постоянной величиной для данного n. Вычислено значение этой величины. Установлено, что оно равно отношению количества всех вершин рассматриваемого многогранника к количеству его прообразных вершин.

Изложен новый метод решения задачи минимизации взвешенной длины связующей цепи при линейном расположении прямоугольных элементов и построен алгоритм его реализации на ПЭВМ. Этот алгоритм дает возможность, в случае недопустимо больших затрат времени для нахождения точного решения задачи, находить ее приближенное решение. Приведены примеры, илюстрирующие полученные результаты.

Ключевые слова: комбинаторная оптимизация, евклидовы комбинаторные множества, перестановки, полиперестановки, выпуклые оболочки, комбинаторные многогранники.

Annotation

Nedobachiy S.I. Models, methods and algorithms in Euclidean combinatorial optimization problems.

This dissertation is a manuscript, which is submitted to obtain a scientific degree of a candidate of physics-mathematics sciences on the 01.05.02 speciality mathematical modelling and calculating methods. Machinebuilding Problem A. N. Podgorni-Institute of Ukraine NAS, Kharkiv, 1999.

The convex hull covers domains of determination of optimization problems, models of which are Euclidean optimization problems on permutable sets, were examined. The irreducible systems of linear restrictions for the general permutable and the general polypermutable polihedrons were obtained. The new properties of permutable polyhedron were obtained.

The new method of exact solving of minimization problem of a weighted length of a linking net in linear disposition of rectangular elements was given and algorithm of its realization on PC was eleborated.

Key words: combinatorial optimization, Euclidean combinatorial sets, permutation, polypermutation, convex hull, combinatorial polyhedrons.

1. Загальна характеристика роботи

Актуальність теми. Багато задач проектування, планування, розміщення, класифікації, управління зводиться до оптимізації на комбінаторних множинах. Серед наукових праць, в яких ставляться та розв'язуються проблеми, пов'язані з зазначеними задачами, у першу чергу треба назвати праці В.О. Ємелічева, Ю.І. Журавльова, М.М. Ковальова, В.К. Леонтьєва, І.М. Ляшенка, В.С. Михалевича, В.О. Перепелиці, І.В. Сергієнка, Ю.Г. Стояна, В.С. Танаєва, В.О. Трубіна, Н.З. Шора, С.В. Яковлєва.

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

Отже, тема дисертаційної роботи “Моделі, методи і алгоритми в задачах евклідової комбінаторної оптимізації” є актуальною.

Дослідження задач евклідової комбінаторної оптимізації, в тому числі задач геометричного проектування, проводяться, зокрема, в Інституті проблем машинобудування імені А.М. Підгорного НАН України під керівництвом члена-кореспондента НАН України Ю.Г. Стояна, на кафедрі прикладної математики і математичного моделювання Полтавського державного технічного університету імені Юрія Кондратюка під керівництвом доктора фізико-математичних наук, професора О.О. Ємця, в Харківському державному технічному університеті радіоелектроніки, Харківському державному університеті внутрішніх справ та інших наукових закладах.

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалась на кафедрі прикладної математики та математичного моделювання Полтавського державного технічного університету імені Юрія Кондратюка (раніше Полтавський технічний університет) згідно з індивідуальним планом аспірантської підготовки та держбюджетною темою “Розробка теорії моделей, методів і алгоритмів евклідової комбінаторної оптимізації” (ДР № 0196U006063).

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

Основними задачами дослідження є:

1. Одержання незвідних системи лінійних обмежень опуклих оболонок областей визначення задач, моделями яких є евклідові задачі оптимізації на загальній переставній та загальній поліпереставній множинах.

2. Одержання нових властивостей переставної, загальної переставної, загальної поліпереставної множин та їх опуклих оболонок переставного, загального переставного та загального поліпереставного многогранників.

3. Одержання властивостей одного відображення множини переставлень перших n натуральних чисел у множину переставлень із повтореннями, елементами якої є абсолютні величини різниць усіх пар перших n натуральних чисел, яке виникає в задачі мінімізації зваженої довжини зв'язуючої сітки при лінійному розташуванні прямокутних елементів; побудова алгоритму установлення прообразу або його відсутності та визначення зв'язків між структурами опуклих оболонок названих множин при зазначеному відображенні;

4. Розроблення нового методу точного розв'язування задачі мінімізації зваженої довжини зв'язуючої сітки при лінійному розташуванні прямокутних елементів.

Наукова новизна одержаних результатів. Новими результатами, які викладено в дисертації є:

1. Установлення незвідної системи лінійних обмежень загального переставного многогранника; визначення рівнянь усіх його гіперграней через ненадлишкові обмеження та їх кількості; опис вершин рівняннями гіперграней; визначення кількості гіперграней, що збігаються в одній і тій же довільній вершині; нове доведення теореми про збіжність вершин з множиною переставлень із повтореннями, якою індукується зазначений многогранник.

2. Установлення незвідної система лінійних обмежень загального поліпереставного многогранника; опис його гіперграней ненадлишковими обмеженнями; визначення залежності між кількістю гіперграней зазначеного многогранника і кількістю гіперграней загальних переставних многогранників, добутком яких він є; це ж стосовно вершин;

3. Виявлення залежності між кількістю гіперграней добутку многогранників і кількістю гіперграней многогранників-співмножників, які утворюють цей добуток: це ж стосовно вершин.

4. Визначення найменшої кількості ребер (r-віддалі), з яких складається шлях від довільної вершини переставного многогранника до будь-якої іншої його вершини та побудова алгоритму знаходження такого шляху; доведення несуміжності вершин многогранника, які знаходяться на одній і тій же r-віддалі від будь-якої його фіксованої вершини й визначення кількості таких вершин.

5. Знаходження критерію існування прообразу при одному відображенні множини переставлень перших n натуральних чисел у спеціальну множину переставлень із повтореннями, яке виникає при дослідженні задачі мінімізації зваженої довжини зв'язуючої сітки при лінійному розташуванні прямокутних елементів і виявлення властивостей зазначених множин, пов'язаних з цим відображенням.

6. Розроблення нового методу розвязування задачі мінімізації зваженої довжини звязуючої сітки при лінійному розташуванні прямокутних елементів, побудова алгоритму його реалізації на ПЕОМ.

Теоретичне та практичне значення одержаних результатів. Дисертаційна робота має теоретичний характер. Одержані результати можуть застосовувутися для проведення подальших досліджень евклідових комбінаторних множин і задач оптимізації на них. Установлення незвідних систем лінійних обмежень загального переставного та загального поліпереставного многогранників можна застосовувати для одержання незвідних систем лінійних обмежень опуклих оболонок областей визначення задачі евклідової оптимізації на інших комбінаторних множинах. Це дає можливість виявляти невідомі на цей час їх властивості, які можуть використовуватися при розв'язуванні відповідних задач. Викладений метод і алгоритм точного розв'язування задачі мінімізації зваженої довжини зв'язуючої сітки при лінійному розташуванні прямокутних елементів можна використовувати при розв'язуванні задач, які мають відповідну модель.

Результати роботи впроваджені в Полтавському державному технічному університеті імені Юрія Кондратюка при виконанні держбюджетної теми “Розробка теорії моделей, методів і алгоритмів евклідової комбінаторної оптимізації” (ДР № 0196U006063) у розділах звіту про виконання указаної теми.

Особистий внесок здобувача. Усі результати дисертаційної роботи, які подані до захисту, одержані особисто дисертантом. У роботах, написаних у співавторстві, дисертанту належать: [1] перший та другий розділи, а в частині 2 пункт 4; [2] формулювання теореми про ненадлишкові обмеження загального переставного многогранника та її доведення, опис усіх його гіперграней ненадлишковими обмеженнями, визначення кількості гіперграней указаного многогранника; [6] теорема про ненадлишкові обмеження загального переставного многогранника; [7] теорема про найменшу кількість ребер між довільними вершинами переставного многогранника і її наслідки, алгоритм знаходження найменшого шляху між двома заданими вершинами переставного многогранника;

Апробація результатів дисертації. Основні положення роботи доповідалися і обговорювалися на:

46-51-ій наукових конференціях професорів, викладачів, наукових працівників, аспірантів та студентів Полтавського державного технічного університету імені Юрія Кондратюка (м. Полтава, 1994-1999 рр.);

Всеукраїнській науковій конференції ”Розробка та застосування математичних методів у науково-технічних дослідженнях”, присвяченій 70-річчю від народження професора П.С. Казі-мірського (м. Львів, 1995 р.);

5-7-ій Міжнародних наукових конференціях імені академіка М. Кравчука (м. Київ, 1995-1998 рр.);

Семінарах наукової ради НАН України (Харківська секція “Мате-матичні методи геометричного проектування”, м. Харків, Інститут проблем машинобудування ім. А.М. Підгорного НАН України, 1997, 1998, 1999 рр.);

Міжнародній науковій конференції “Розробка та застосування математичних методів у науково-технічних дослідженнях” (м. Львів, 1998 р.).

Публікації. Основні результати дисертаційної роботи опубліковані в 8 наукових працях, серед них брошура 1, статті в журналах 2, статті в збірниках наукових праць 2, матеріали міжнародних наукових конференцій 2, тези міжнародної наукової конференції 1.

Структура та обсяг дисертації. Дисертація написана українською мовою, складається зі вступу, чотирьох розділів, висновку, списку використаних джерел з 109 найменувань, 3-х додатків. Усього 150 сторінка. Список використаних джерел та додатки займають 19 сторінок.

2. Зміст роботи

У вступі обгрунтовано актуальність теми, проведено огляд близьких за напрямком праць, визначено мету й задачі дослідження, вказано новизну одержаних результатів та їх теоретичне й практичне значення.

У першому розділі зроблено огляд методів розв'язування задач комбінаторної оптимізації. Викладено основні поняття теорії евклідової комбінаторної оптимізації, які використовуються в наступних розділах роботи, та відомі властивості областей визначення задач евклідовоі оптимізації на переставних множинах і властивості опуклих оболонок цих множин. Вказано праці, в яких наведені основні результати досліджень із зазначених питань.

У роботі використовуються позначення: J_n={1, ..., n}, |S| потужність множини S,

,

де x=( x₁, ..., x_n ), y=( y₁, ..., y_n ) точки простору Rⁿ, dimL вимірність підпростору LRⁿ, convM опукла оболонка множини M, vertП множина вершин многогранника П.

Нехай задано мультимножину

G={g₁, ..., g}=,

де e_iR¹ iJ_n, r₁+...+ r_n=. Вважатимемо, що g₁ ... g, e₁< ... <e_n.

Нехай kJ. Упорядкованою k-вибіркою з мультимножини G називається набір

, (1)

де g_{i j}G i_jJ_k, jJ_k, i_s i_t , якщо st sJ_k, tJ_k .

Можина E, елементи якої є k-вибірки вигляду (1) з мультимножини G, називається евклідовою комбінаторною множиною або е-множиною, якщо для довільних елементів e= (a₁, ..., a_k), e =(b₁, ..., b_k) цієї множини виконується умова: (e e) (jJ_k : a_j b_j).

Множина переставлень без повторень з k різних дійсних чисел позначається P_k(G). Загальна переставна множина з k дійсних чисел, серед яких n різних позначається P_kn(G).

Нехай k=, і множина J_k подана у вигляді упорядкованого розбиття на s підмножин K₁, K₂, ..., K_s , які задовольняють умови: K_i K_j = , K_i iJ_s, jJ_s, a H множина всіх елементів вигляду =((1), (2), ..., (k))=(¹, ..., ^s), де ⁱ довільне переставлення елементів множини K_i iJ_s .

Поліпереставною множиною з повтореннями або загальною поліпереставною множиною називається множина (G, H) ={(g₍₁₎, g₍₂₎, ..., g_(k))| | g_(i)G iJ_k ,H}.

Нехай E евклідова комбінаторна множина, а e, в зображенні (1) елемент E. Відображення f: EE_f R^k називається зануренням множини E в арифметичний евклідів простір, якщо f ставить множину E у взаємно однозначну відповідність множині E_fR^k за правилом: для E, x=f (e), x=(x₁, ..., x_k)E_f , маємо x_j = g_{i j} jJ_k . Множина E_f називається спеціальною комбінаторною множиною, або c- комбінаторних множиною.

Для розглянутих вище e-комбінаторних множин застосовуються такі позначення відповідних їм c-комбінаторних множин:

E _k (G) = f (P_k (G)),

E_kn(G) = f (P_{k n} (G)),

(G, H) = = f ( (G, H)).

Система обмежень

(2)

де _jJ_k, _{j t}, jJ_i, tJ_i, iJ_k , визначає многогранник П_kn(G)=convE_{k n}(G), який називається загальним переставним многогранником.

Сукупність нерівностей системи (2), що мають однакове значення величини i, називається спілкою i нерівностей цієї системи, а верхня нерівність системи (3) нерівністю спілки 0.

Многогранник П(G, Н)=convE(G,Н) називається загальним поліпереставним многогранником. Позначимо мультимножину, яка складається з k_i =|K_i| елементів g_uG, де uK_i, а її елементи , де vJ iJ_s, тобто

,

де = k_i iJ_s. Нехай

iJ_s.

За умови многогранник П(G,Н) визначається системою обмежень:

(3)

Спілкою нерівностей системи (3) називається сукупність не-рівностей із фіксованим значенням пари чисел i, | ⁱ | ⁱ N_i iJ_s.

Добутком многогранників M₁, ..., M_s , вимірності d₁, ..., d_s називається множина

.

Має місце теорема: П (G, Н)= П().

У другому розділі встановлено незвідні системи лінійних обмежень загального переставного та загального поліпереставного многогранників, викладено ряд їх нових властивостей, нове доведення теореми про збіжність вершин загального переставного многогранника з множиною переставлень із повтореннями, якою він індукується. Одержано нові властивості переставного многогранника.

Нехай

G = {g₁, ..., g_k} = , де e_iR¹ iJ_n, g₁ ... g_k, e₁< ... <e_n.

Позначимо k₁ = r₁, k₂ = r₁ + r₂, ..., k _n = r₁ + ... + r_n = k.

Твердження 2.1.1 У системі (2) лінійних обмежень многогранника П_{k n}(G) надлишковими обмеженнями є: при r₁ >1 усі нерівності спілок

2, 3, ..., r₁, (4)

при r_n >1 усі нерівності спілок

k - r_n, k - r_n +1 , ..., k - 2, (5)

і тільки вони.

Виключивши з системи (2) нерівності спілок (4) і (5), як надлишкові, та замінивши нерівності спілок 0 та k рівністю

, (6)

одержимо незвідну систему лінійних обмежень многогранника П_{k n} (G):

 (7)

де _jJ_k, _{j t} j t, jJ_i, tJ_i, iJ_{k - 1} \ .

Будь-яка нерівність системи (7), якщо її записати у вигляді рівності у системі з рівністю (6), описує гіпергрань многогранника П_{k n} (G).

Якщо n = 2 і r₁ > 1 та r_n > 1, то кількість (Г_{k - 2}) гіперграней многогранника П_{k n} (G) дорівнює 2k.

Якщо n > 2 або n = 2 і принаймні одне з чисел r₁ або r_n рівне одиниці, то

(Г_k-2) = =,

i_jJ_{k - 1} \ jJ_s , s=k+1-(r₁+r_n).

Виходячи з незвідної системи лінійних обмежень многогранника П_kn(G), робиться опис його вершин рівняннями гіперграней та визначається кількість гіперграней, що збігаються в одній і тій же довільній вершині.

Одержані результати дають можливість викласти нове доведення теореми, про збіжність вершин загального переставного многогранника П_kn(G) з множиною E_kn(G).

Для многогранника П(G, Н) мають місце такі твердження.

Твердження 2.2.1 Виключення з системи (3) при >1 усіх нерівностей спілок

(i, 2), (i, 3), ..., (i, ), (8)

при >1 усіх нерівностей спілок

(i, k _i -), (i, k _i - +1), ..., (i, k_i -2), (9)

та всіх нерівностей спілок (i, k_i), iJ_s перетворює її в незвідну систему обмежень.

Кожна із нерівностей системи (3), за винятком нерівностей спілок (8), (9) та (i, k_i) iJ_s, записана як рівняння у системі з рівняннями системи (3), описує гіпергрань загального поліпереставного многогранника П(G, Н).

Твердження 2.2.2 Кількість гіперграней загального поліпереставного многогранника П(G, Н) дорівнює сумі кількостей гіперграней многогранників П(), де iJ_s.

Твердження 2.2.3 Кількість вершин загального поліпереставного многогранника П(G, Н) дорівнює добутку кількостей вершин кожного з многогранників П(), де iJ_s.

Останні твердження поширюються на довільний многогранника M= M_i.

Далі викладено деякі властивості опуклої оболонки множини E_n (J_n) перепереставного многогранника П_n (J_n).

Нехай I() число інверсій у переставленні E_n(J_n). Оскільки vertП_n(J_n) = E_n (J_n), то довільне переставлення E_n(J_n) будемо також називати вершиною многогранника П_n (J_n).

Назвемо r-віддаллю між довільними вершинами ₁ та ₂ многогранника П_n (J_n) найменшу кількість ребер, що з'єднує вершини ₁ та ₂; r-віддаль між вершинами ₁ та ₂ позначатимемо r(₁, ₁). Віддаль (₁, ₂) на відміну від r-віддалі називатимемо e-віддаллю. Мають місце такі твердження.

Твердження 2.4.3 Між будь-якими вершинами ₁ та ₂ многогранника П_n (J_n) r-віддаль дорівнює числу інверсій у другому рядку підстановки , яка одержується з підстановки таким упорядкуванням її стовпців, при якому перший рядок утворює переставлення = (1, 2, ..., n).

Твердження 2.4.4 Серед вершин многогранника П_n (J_n), які знаходяться на однаковій r-віддалі від однієї й тієї ж довільної його вершини, суміжних між собою немає.

Твердження 2.4.5 Кількість вершин многогранника П_n (J_n), які знаходяться на одній і тій же r-віддалі, рівній k, де k n(n-1)/2, від будь-якої його фіксованої вершини, визначається k-им коефіцієнтом твірної функції G(z) = =(1-zⁿ) ... (1-z²) (1-z)/( (1-z)ⁿ.

Твердження 2.4.6 Нехай є шлях, що проходить ребрами многогранника П_n (J_n) від довільної його вершини ₁ до іншої довільної вершини ₂, у якого кожна наступна вершина знаходиться на меншій e-віддалі від ₂, порівняно з попередньою. Тоді цей шлях має кількість ребер рівну r(₁, ₂ ).

У третьому розділі викладені результати дослідження одного відображення, яке виникає в моделі задачі мінімізації зваженої довжини зв'язуючої сітки при лінійному розташуванні прямокутних елементів, множини E_n (J_n) у множину

E_k(n-1)(G),

G ={ |i-j| : jJ_n\J_i , iJ_{n - 1} }={1^{n -1}, 2^{n -2}, ..., (n-2)², n-1}, k = | G |= n(n-1)/2.

Задамо вдображення : E_n(J_n)E_k(n-1)(G). Нехай =(a₁, ..., a_n) довльний елемент множини E_n (J_n). Позначимо _ij = |a_i - a_j| iJ_n, jJ_n. Вважатимемо, що за визначенням ()=^*, де ^*=(₁₂, ..., _1n, ₂₃, ..., _2n, ..., _(n-1)n )E_k(n-1)(G). Матрицю (_{i j}) назвемо вдповдною елементу ^*.

Нехай ^*E_k(n-1)(G). Розглянемо матрицю (_ij), вдповдну елементу ^*, як матрицю сумжност мультиграфа Г із вершинами, як мають номери k(1), k(2), ..., k(n). Нехай Г₀ мультиграф із вершинами, пронумерованими числами 1, 2, ..., n, у якого кратнсть ребра, нцидентного вершинам i та j, дорвнює i - j iJ_n, jJ_n.

Твердження 3.1.1 Для того, щоб елемент ^*E_k(n-1)(G) при вдобра-женн мав прообраз E_n(J_n), необхдно достатньо, щоб мультиграфи Г та Г₀ були зоморфними.

Це твердження дає можливість побудувати викладений у дисертаційній роботі алгоритм знаходження прообразу або установлення його відсутності при заданому відображенні .

Твердження 3.2.1 Якщо вершини ^* та многогранника П_k(n-1)(G) при вдображенн мають прообрази, як є сумжними мж собою вершинами многогранника П_n(J_n), то найменша кльксть ребер, що з'єднують вершини ^* та , дорвнює n - 2.

Вершина многогранника П_k(n-1)(G), яка при відображенні має прообраз, назвається прообразною вершиною.

Твердження 3.2.2 Відношення кількості вершин многогранника П_k(n-1)(G), що належать довільній гіперплощині x_i =j, де jJ_n-1 iJ_k, до кількості прообразних вершин цієї ж гіперплощини, дорівнює відношенню кількості всіх вершин многогранника П_k(n-1)(G) до кількості всіх його прообразних вершин.

У четвертому розділі викладено новий метод точного розв'язування задачі мінімізації зваженої довжини зв'язуючої сітки при лінійному розташуванні прямокутних елементів та алгоритм його реалізації на ПЕОМ.

Ця задача має модель евклідової задачі комбінаторної оптимізації: знайти

Ф(x*) = Ф(x), x* = arg Ф(x), (10)

Ф(x) = c_{i j} | x_i - x_j |, c_{i j} =c _{j i}, c _{i i}=0 , c_{i j} R¹ iJ_n, jJ_n.

Запишемо наддіагональні елементи матриці С = (с_{i j})_{n n} у вигляді переставлення

(с ₁₂, с ₁₃, ..., с _{1 n}, ..., с ₂₃, с ₂₄, ..., с _{2 n}, ..., с_{( n -1) ( n -1)}, с_{( n -1) n}) (11)

(с₁, ..., с _k ), де k=n(n-1)/2, c = с_ij, =j - i + (i - 1)(2n - i)/2, iJ_{n -1}, jJ_n\ J_i .

Множину вершин многогранника П_k(n-1)(G), які при відображенні мають прообрази, позначимо V(). Нехай

x=(x₁, ..., x_n)vertП_n (J_n),

=(₁, ..., _k)V() і (x)=.

Задачу (10) можна розглядати як задачу: знайти

(*) = (), * = arg (), де () =с .

Запишемо множину перших n натуральних чисел у вигляді упорядкованого масиву M=(1, n, 2, n-1, ..., [n/2]+1), де [n/2] ціла частина числа n/2. Мультимножину, елементами якої є перші m, 2m n, чисел масиву M, а інші n-m елементів є нулі, позначимо M_m. Із множини всіх переставлень елементів мультимножини M_m mJ_n\{1} виберемо лише ті переставлення x^(m)=(x^(m)₁, ..., x^(m)_n), для яких за умови x^(m)_i=1, x^(m)_j=n виконується нерівність i<j. Множину таких переставлень позначимо E(M_m). Позначимо E(M*)=E(M_m). Введемо відображення ^c: E(M*)E_k(n-1)(G). Нехай x^(m)=(x^(m)₁, ..., x^(m)_n)E(M_m) E(M*). Якщо x^(m)_i 0, x^(m)_j 0, де ij, то позначимо r_ij =|x^(m)_i - x^(m)_j| і назвемо це число відповідним елементу c_ijC=(c_ij), де c_ij=c_ji, c_ii=0 iJ_n, jJ_n,. Сукупність чисел r_ij утворює мультимножину, яку позначимо G(r_ij). Виберемо всі елементи c_ij з такими індексами, для яких виконується принаймні одна з умов: x^(m)_i =0 або x^(m)_j = 0, і упорядкуємо їх за неспаданням:

... , (12)

де s =(n(n-1)-m(m-1))/2. Елементи мультимножини G\ G( r_ij ) упорядкуємо за незростанням, записавши їх у вигляді послідовності

r₁ ... r_s. (13)

Число r_t tJ_s послідовності (13) назвемо відповідним елементу послідовності (12). Замінивши в переставленні (11) усі елементи c_ij відповідними їм елементами мультимножини G, одержимо переставлення =(₁₂, ₁₃, ..., _1n, ..., ₂₃, ₂₄, ..., _2n, ..., _(n-1)(n-1), _(n-1)n), яке належить множині E_k(n-1)(G). За означенням приймемо: ^c(x)=. За умови m=n маємо: {^c(x⁽ⁿ⁾)} = =V().

Нехай x^(m)E(M_m)E(M*), де mJ_n\{1}, ^c(x^(m))=, =(₁, ...,_k). Позначимо F(x^(m))=()=с. Якщо m=n, то F(x⁽ⁿ⁾) =Ф(x). Для послідовності переставлень x⁽²⁾E(M₂), ..., x⁽ⁿ⁾E(M_n), у якої переставлення x⁽ⁱ⁺¹⁾ одержано з переставлення x⁽ⁱ⁾ iJ_n-1\{1} заміною в ньому одного із нулів (i+1)-м елементом масиву M, виконується співвідношення F(x⁽²⁾)... F(x⁽ⁿ⁾).

Переставлення, які будемо розглядати, записуватимемо у таблицю TP, а обчислені на них значення функції F(x^(m)) у таблицю TF. Кожному переставленню x^(m)E(M_m) mJ_n\{1} при формуванні таблиці TP надається відповідний номер NP.

Нехай у таблицю TP записані переставлення множини E(M_m) mJ_n-1\{1}. Для кожного з цих переставлень x^(m)(NP) обчислимо значення функції F(x^(m)(NP))=(R^c(x^(m)(NP))) і запишемо його в масив TF. Серед усіх записаних у масив TF значень F(x^(m)(NP)) виберемо найменше. Якщо таких значень декілька, то виберемо довільне з них. За його номером NP установимо відповідне йому переставлення x^(m)(NP). Таке переставлення називатимемо вихідним переставленням множини E(M_m).

Опишемо алгоритм знаходження точного розв'язку задачі (10).

Нехай задано число n, матриця С=(с_ij)_{n n}, де с_ij=с_ji, с_ii=0 iJ_n, jJ_n, і переставлення xE(M_n)=E_n(J_n) із найменшим серед відомих до початку розв'язування задачі значенням цільової функції FC*=Ф(x).

Формуємо покроково всі переставлення множини E(M₂). Для кожного із них знаходимо ^c(x⁽²⁾) й обчислюємо значення функції F(x⁽²⁾)=(R^c(x⁽²⁾). Порівнюємо ці значення з FC*. Ті з них, які менші від FC*, записуємо в таблицю TF, а відповідні їм переставлення в таблицю TP. Якщо кількість записаних переставлень множини E(M₂) дорівнює нулю, то маємо розв'язок: x* = x, Ф(x*) = FC*. Якщо ж кількість записаних переставлень множини E(M₂) не дорівнює нулю, то переходимо до наступного етапу.

Вибираємо серед значень F(x⁽²⁾) найменше і за його номером знаходимо відповідне переставлення =x⁽²⁾, яке є вихідним для множини E(M₂). За переставленням та масивом M формуємо переставлення множини E(M₃), замінюючи в переставленні нулі третім елементом масиву M. Для кожного із сформованих переставлень x⁽³⁾ обчислюємо F(x⁽³⁾) і порівнюємо його з FC*. Ті переставлення, в яких значення функції F менші від FC*, записуємо в таблицю TP, а відповідні їм значення функції в таблицю TF. Якщо кількість зроблених на цьому кроці записів дорівнює нулю, то із переставлень множини E(M₂) виключаємо вихідне переставлення і: а) якщо кількість переставлень множини E(M₂) після виконаного виключення стала рівною нулю, то покладаємо x* = x, Ф(x*) = =FC*; б) якщо ця кількість відмінна від нуля, то в множині E(M₂) визначаємо нове вихідне переставлення і за ним формуємо переставлення множини E(M₃).

Якщо кількість записаних у таблицю TP переставлень множини E(M₃) більша від нуля, то серед цих переставлень визначаємо вихідне переставлення і формуємо переставлення множини E(M₄), замінюючи в переставленні нулі четвертим елементом множини M.

Продовжуючи формувати таким чином за вихідним переставленням множини E(M_s), де 2 s< <n, переставлення множини E(M_s+1), кожного разу у випадку, коли кількість записаних у таблицю TP переставлень множини E(M_t) tJ_n\{1, 2} стає рівною нулю, із записаних у таблицю TP переставлень множини E(M_t-1) виключаємо вихідне для цієї множини переставлення. Цей процес закінчиться або встановленням переставлення x⁽ⁿ⁾E(M_n)E_n(J_n), для якого F(x⁽ⁿ⁾)<FC*, або тим, що кількість записаних у таблицю TP переставлень множини E(M₂) виявиться рівною нулю. В останньому випадку маємо розв'язок: x*=x, Ф(x*)=FC*.

Припустимо, що встановлено x⁽ⁿ⁾E(M_n)E_n(J_n), для якого F(x⁽ⁿ⁾)<FC*. У такому випадку покладаємо x=x⁽ⁿ⁾, FC*=F(x⁽ⁿ⁾) і виключаємо із таблиці TP усі переставлення із значеннями функції F, меншими від FC*. При цьому із таблиці TF виключаємо відповідні їм значення функції F.

Після виконаного виключення таблиця TP або буде порожньою, і тоді розв'язком задачі є x*=x, Ф(x*)=FC*, або знайдуться записані в таблицю TP переставлення множини E(M_t), такі, що кількість записаних переставлень множини E(M_t+1) буде дорівнювати нулю. В останньому випадку серед переставлень множини E(M_t) визначаємо переставлення з найменшим серед F(x^(t)) значенням. Якщо це переставлення було вихідним у множині E(M_t) до встановлення x⁽ⁿ⁾, для якого F(x⁽ⁿ⁾)<FC*, то його виключаємо з таблиці TP. У іншому випадку це переставлення набуває статусу вихідного переставлення множини E(M_t) і за ним починаємо формувати, як і раніше, переставлення множини E(M_t+1). Такий процес закінчиться виключенням із таблиці TP усіх переставлень, і при цьому буде знайдено розв'язок задачі x* =x, Ф(x*)=FC*.

Розв'язування задачі (10) за допомогою описаного алгоритму дає можливість знаходити послідовність переставлень множини E(M_n) = E_n (J_n), у якої значення цільової функції, обчислене на кожному наступному переставленні, менше від значення цільової функції, обчисленому на попередньому переставленні. Це дає змогу у випадках, коли знаходження точного розв'язку вимагає значних затрат часу, знаходити наближений її розв'язок, який за певних умов може задовольнити споживача.

Викладений алгоритм є досить ефективним у випадку, коли розв'язок Ф(x*) задачі (10) є близьким до розв'язку задачі: знайти

(*) = =(), де () = с.

Це пояснюється тим, що у такому випадку кількість переставлень кожної з множин E(M_m), де mJ_n \ {1}, які при розв'язуванні задачі записуються в таблицю TP, через близькість значень Ф(x*) та (*), буде відносно невеликою. Швидкість знаходження розв'язку залежить також від того, наскільки близьким до точного розв'язку є початкове значення FC*.

Висновки

1. Одержано незвідні системи лінійних обмежень опуклих оболонок областей визначення задач, моделями яких є евклідові задачі оптимізації на загальній переставній та загальній поліпереставній множинах.

2. Визначено нові властивості загального переставного та загального поліпереставного многогранників, які випливають із їх незвідних систем лінійних обмежень, та нове доведення теореми про збіжність вершин загального переставного многогранника з множиною переставлень із повтореннями, якою він індукується.

3. Установлено зв'язок між кількістю гіперграней добутку многограннків і кількістю гіперграней многогранників-співмножників, які утворюють цей добуток. Те ж зроблено і стосовно вершин добутку многограннків.

4. Одержано нові властивості переставного многогранника.

5. Визначено властивості одного відображення множини переставлень перших n натуральних чисел у множину переставлень із повтореннями, елементами яких є абсолютні величини різниць усіх можливих пар цих чисел, яке виникає в моделі задачі мінімізації зваженої довжини зв'язуючої сітки при лінійному розташуванні прямокутних елементів. Обгрунтовано необхідну і достатню умову існування прообразу при зазначеному відображенні; побудовано алгоритм знаходження прообразу або установлення його відсутності.

6. Розроблено новій метод точного розв'язування задачі мінімізації зваженої довжини зв'язуючої сітки при лінійному розташуванні прямокутних елементів.

Утановлення незвідних систем лінійних обмежень загального переставного та загального поліпереставного многогранників може застосовуватися для одержання незвідних систем лінійних обмежень опуклих оболонок областей визначення задач, моделями яких є евклідові задачі оптимізації на інших комбінаторних множинах. Це, в свою чергу, дозволяє розкривати нові їх властивості, які можуть використовуватися при дослідженні задач оптимізації на цих множинах та при побудові методів і алгоритмів їх розв'язування.

Викладений алгоритм розв'язування задачі мінімізації зваженої довжини зв'язуючої сітки при лінійному розташуванні прямокутних елементів може використовуватися при розв'язуванні задач з відповідною моделлю. Даний алгоритм дозволяє, у випадку недопустимо великих затрат часу для знаходження точного розв'язку задачі, знаходити її наближений розв'язок.

Основні праці

1. Ємець О.О., Колєчкіна Л.М., Недобачій С.І. Дослідження областей визначення задач евклідової комбінаторної оптимізації на переставних множинах // Полтава: Полт. держ. техн. ун-т ім. Юрія Кондратюка, ЧПКП “Легат”. 1999. 64 с. Частина 2. 32 с.

2. Ємець О.О., Недобачій С.І. Загальний переставний многогранник: незвідна система лінійних обмежень та рівняння всіх гіперграней // Наук. вісті Нац. техн. ун-ту України “Київський політехнічний інститут”. 1998. № 1(2). С. 100-106.

3. Недобачій С.І. Про незвідні системи обмежень деяких комбінаторних многогранників // Вісник держав. ун-ту ”Львівська політехніка”. № 337. Прикладна математика. Т. 2. Зб. наук. пр. Львів: Львівська політехніка. 1998. С. 362-365.

4. Недобачій С.І. Про одне відображення множини переставлень E_n(J_n) E_k(n-1)(G) та деякі його властивості // Математичне моделювання в інженерних і фінансово-економічних задачах: Зб. наук. пр. Дніпропетровськ: Січ. 1998. С. 99-105.

5. Недобачій С.І. Опис вершин загального переставного многогранника рівняннями його гіперграней // Зб. наук. пр.: Вісник Полтавського держ. пед. ін-ту ім. В.Г. Короленка: Полтава, 1998. Серія “ Фіз. - мат. науки”. Випуск 3. С. 53-59.

6. Ємець О.О., Недобачій С.І. Знаходження всіх гіперграней в алгебраїчному описі загального переставного многогранника // П'ята міжнародна наук. конференція ім. ак. М. Кравчука (16-18 травня 1996 р., Київ): Тези доповідей. Киів. 1996. С. 141.

7. Ємець О.О., Недобачій С.І. Деякі нові властивості переставного многогранника // Шоста міжнародна наук. конференція ім. ак. М. Кравчука (15 - 17 травня 1997р., Київ): Матеріали конференції. Киів. 1997. С. 161.

8. Недобачій С.І. Про задачу мінімізації зваженої довжини зв'язуючої сітки при лінійному розташуванні прямокутних елементів // Сьома міжнародна наук. конференція ім. ак. М. Кравчука (14-16 травня 1998 р., Київ): Матеріали конференції. Киів. 1998. С. 361-363.

Размещено на Allbest.ru