Математичні моделі розміщення, упаковки і розподілу з умовою інваріантності щодо груп перетворень

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

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

Інститут кібернетики імені В.М. Глушкова

Автореферат

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

доктора фізико-математичних наук

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

МАТЕМАТИЧНІ МОДЕЛІ РОЗМІЩЕННЯ, УПАКОВКИ, РОЗПОДІЛУ З УМОВОЮ ІНВАРІАНТНОСТІ ЩОДО ГРУП ПЕРЕТВОРЕНЬ

КОЗІН Ігор Вікторович

Київ-2010

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

Робота виконана в ДВНЗ «Запорізький національний університет»

Науковий консультант: доктор фізико-математичних наук, професор

Перепелиця Віталій Опанасович,

ДВНЗ «Запорізький національний університет»,

професор кафедри економічної кібернетики

Офіційні опоненти: доктор фізико-математичних наук,

старший науковий співробітник

Донець Георгій Панасович

Інститут кібернетики ім. В.М.Глушкова НАН України,

завідувач відділу,

доктор фізико-математичних наук, професор

Новожилова Марина Володимирівна

Харківський державний технічний університет

будівництва та архітектури

завідувач кафедри комп'ютерного моделювання

та інформаційних технологій,

доктор фізико-математичних наук, професор

Макаренко Олександр Сергійович

ННК «Інститут прикладного системного аналізу»

НТУУ «КПІ» МОН України та НАН України, завідувач відділу

Захист відбудеться 26.11. 2010р. о (об) 11 годині

на засіданні спеціалізованої вченої ради Д 26.194.02 в Інституті кібернетики імені В.М. Глушкова НАН України за адресою:

03680, МСП, Київ 187, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомиться в науково технічному архіві інституту кібернетики імені В.М. Глушкова НАН України за адресою:

03680, МСП, Київ 187, проспект Академіка Глушкова, 40.

Автореферат розісланий 21.10. 2010р.

Вчений секретар спеціалізованої вченої ради ВАГІС О.А.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Математичні моделі розміщення, упаковки, розподілу ресурсів використовуються в різних галузях людської діяльності і привертають постійну увагу дослідників. У більшості своїй загальні постановки задач, які пов'язані з пошуком оптимальних рішень у моделях даного класу, важко розв'язуються, а самі задачі часто важко формалізуються. Тому актуальною є розробка підходів, що дозволяють побудувати і дослідити математичні моделі цього класу за деяких природних умов, які певною мірою звужують клас досліджуваних задач, залишаючи його достатньо широким для численних практичних застосувань. Однією з таких умов є умова інваріантності рішень щодо дії певних груп перетворень, тобто умова симетрії. Властивості симетрії та їх вплив на розв'язання задач завжди представляли значний інтерес для прикладних і теоретичних досліджень. Вимога симетрії (інваріантності відносно певних груп перетворень) може дозволити досягти простого представлення розв'язку задачі, а іноді призводить до нових співвідношень, що мають самостійний інтерес. В оптимізаційних задачах цей принцип дає можливість апріорі вказати структуру розв'язку задачі, зменшити трудомісткість пошуку цього розв'язку. Починаючи з класичних робіт Є.С. Федорова, А. Шенфліса, Г. Вейля, поняття симетрії, властивості інваріантності відносно груп перетворень міцно увійшли в математику, механіку, фізику. Ідеї симетрії виступають з одного боку як необхідні умови розв'язку складних задач, а з іншого як принципово важливий евристичний принцип під час побудови математичних моделей.

Сфера застосування математичних моделей та методів розв'язання задач, що важко формалізуються, в останній час стрімко розширюється. Математичне моделювання активно застосовується під час вивчення процесів та явищ економіки, менеджменту, соціології. У сферу дії математичних моделей потрапляють такі суто людські поняття, як «краса», «правильність», «справедливість», «рівномірність». Формальний опис критеріїв такого типу пов'язаний з поняттям симетрії та потребує кількісних оцінок ступеня симетрії. Тому дослідження класів математичних моделей, в яких можуть бути присутні певні умови інваріантності, мають значний теоретичний інтерес. До таких класів математичних моделей і відносяться класичні дискретні задачі розміщення, упаковки та розкрою, розбиття та покриття, розподілу ресурсів та інші.

Дискретні та неперервні оптимізаційні моделі вказаних класів досліджувались у численних роботах. В Україні вагомий внесок у розвиток теоретичних основ побудови таких моделей внесли В.С. Михалевич, І.В. Сергієнко, Н.З. Шор, В.О. Трубін, Ю.Ю. Червак, В.П. Шило, О.І. Кукса, В.Л. Волкович, В.О. Перепелиця, Ю.Г. Стоян та інші дослідники.

Викликає особливий інтерес принцип симетрії як принцип побудови математичних моделей задач теорії багатокритеріальної оптимізації. На відміну від класичної теорії оптимізації, теорія багатокритеріальної оптимізації (ТБО) в якості «розв'язку» пропонує не один, а множину недомінуючих розв'язків. До цього часу залишається відкритим питання про те, які об'єктивні характеристики дозволяють у множині альтернатив обрати єдиний варіант розв'язку, та який розв'язок можна вважати «найкращим» для даної конкретної задачі. Причому питання полягає не у методі пошуку, а в принципі вибору єдиного оптимального розв'язку. Однією з найважливіших таких характеристик може виступати умова інваріантності відносно дії окремих груп перетворень. Задача пошуку та дослідження альтернативних розв'язків та побудови правил вибору в ТБО привела до створення цілих наукових напрямів, наукових шкіл. Цій проблемі присвячено значну кількість публикацій. Географія досліджень різноманітна - США (Chernoff H., Saaty T.L.), Франція (Moulin H., Sen A.K.), Ізраїль (Aumann R.J.), Росія (Айзерман М.А., Юдін Д.Б.), Україна (Сергієнко І.В., Перепелиця В.О.), Білорусь (Ємєлічев В.О.) та інші.

У багатьох практичних задачах властивості симетрії виникають як певні наближення. Тому необхідне визначення міри симетрії та способу її обчислення. Актуальним на сьогодні є питання про спосіб вимірювання симетрії та вибір критерію або умови «наближеної симетрії» у класичних моделях. Як правило, на відміну від умови строгої симетрії, додання таких умов значно ускладнює задачу, збільшує множину альтернативних розв'язків, призводить до необхідності використання наближених методів пошуку розв'язків та залучення до вибору остаточного варіанта розв'язку особи, що приймає рішення (ОПР). На базі моделей, що включають ОПР, створюються діалогові системи підтримки прийняття розв'язків. Залучення ОПР до процесу прийняття рішень накладає низку вимог до моделей і методів, які використовуються для пошуку наближених рішень. Зокрема, набувають значення питання розмежування повноважень у діалогових системах та побудови алгоритмів, орієнтованих на використання в таких системах. Найбільш зручними для використання в системах підтримки прийняття рішень є підходи, засновані на «жадібних» алгоритмах пошуку оптимальних розв'язків, які визначаються високою швидкістю їх отримання. Однак лише у виключних випадках (матроїди, грідоїди) «жадібні» алгоритми призводять до точного розв'язку оптимізаційної задачі. Особливий інтерес викликають дослідження фрагментарних моделей, для яких у принципі є можливим застосуванням «жадібних» алгоритмів. Формальною основою подібних моделей є теорія фрагментарних структур (accesible sets). Дослідження властивостей таких структур є основою побудови математичних моделей та систем підтримки прийняття рішень у відповідних практичних задачах.

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася відповідно до планів наукових досліджень на кафедрі економічної кібернетики ДВНЗ «Запорізький національний університет» МОНУ в межах наукових д/б тем:

«Дослідження екстремальних задач в умовах невизначеності та розробка методів їх розв'язування» (1997-1999 рр., № Держ. реєстрації 0197U012777);

«Розробка алгоритмів та комп'ютерних систем прийняття рішень з різними правилами вибору» (2000 р., № Держ. реєстрації 0198U004673);

«Дослідження економіко-математичних моделей та систем підтримки прийняття рішень» (2000-2002 рр., № Держ. реєстрації 0100U001723;

«Дослідження методів нелінійного, дискретного аналізу та нечіткої математики, їх використання в економіко-математичному моделюванні» (2004-2005 рр., № Держ. реєстрації 0103U00719);

«Розробка методів і моделювання процесів взаємодії в багатоагентних соціально-економічних системах» (2004 р., № Держ. реєстрації 0104U010162);

«Комбіновані підходи до використання ігрових методів та методів нелінійної динаміки у передпрогнозному аналізі та прийнятті рішень» (2007 р., № Держ. реєстрації 0107U001357).

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

Досягнення цієї мети пов'язано з постановкою та розв'язанням таких завдань:

-визначення кількісних характеристик властивості симетрії, означення міри симетрії для дискретних задач, дослідження задач, пов'язаних з мірою симетрії;

-побудова математичних моделей задач з умовою інваріантності відносно груп перетворень;

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

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

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

-формулювання принципу симетрії в термінах груп перетворень;

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

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

-використання запропонованих математичних моделей та методів для розв'язання прикладних задач.

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

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

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

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

У рамках цих досліджень одержано наступні наукові результати:

-вперше введено поняття мір симетрії скінченних множин відносно скінченних груп перетворень, досліджено властивості мір симетрій;

-удосконалено математичну модель задачі розміщення блоків реклами на сторінках рекламних видань з критеріями симетрії. Запропоновано нові наближені алгоритми пошуку розв'язків цієї задачі;

-досліджено екстремальні задачі на скінченних множинах з критерієм симетрії, отримано оцінки складності цих задач;

-побудовано математичну модель задачі розподілу ресурсів з критерієм симетрії;

-вперше розроблено універсальну фрагментарно-еволюційну модель пошуку наближених оптимальних розв'язків дискретних оптимізаційних задач;

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

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

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

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

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

-встановлено властивості симетрії правил прийняття рішень, заснованих на відношенні парнодомінантності.

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

На основі запропонованих підходів створено та впроваджено такі системи підтримки прийняття рішень:

«Фінанси» _ планування та контроль виконання місцевих бюджетів, впроваджено в практику управління фінансами у районних фінансових відділах Запорізької області;

«Земля» _ управління земельними ресурсами території, впроваджено у відділі земельних ресурсів Пологівського району Запорізької області;

«Населення» _ система обліку та аналізу структури населення регіону впроваджено в сільських, селищних та міських радах Запорізької області;

«Кафедра-Деканат-Ректорат» _ система управління навчальним процесом ВНЗ, впроваджено в Запорізькому національному університеті;

«Медіа» _ інформаційна система обліку та управління для рекламних видань. Система впроваджена и використовується при підготовці видань: «Теленеделя», «Комсомольская правда в Украине», «Рекламная неделя», «Удача», «Остров свободы», «Мрія», «Истеблишмент» та ін.;

«Преса» _ інформаційна система управління розповсюдженням друкованих видань, а також ряд інших інформаційних систем для технологічних та економічних застосувань. Система впроваджена в управлінні ТОВ «Запоріжжя - Медіа».

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

Автором отримано патент на корисну модель №37839 «Спосіб розмітки плоского матеріалу».

Особистий внесок здобувача. Всі наукові результати дисертаційної роботи отримано особисто. З робіт, виконаних із співавторами, на захист виносяться лише результати, одержані особисто здобувачем. У роботах, виконаних сумісно, автору дисертації належать такі результати: у монографії [2] дисертант є автором першої глави роботи та приймав участь у написанні глав 3-4; у роботі [4] дисертанту належить розробка схеми загального методу класифікації рівнів часового ряду; у роботі [5] - оцінки обчислювальної складності задач; у роботах [7,11,16] -постановка задачі та алгоритми розв'язання; у роботах [12,13,19] - постановка задачі, методологія, доведення окремих теорем; у роботі [14]- розробка моделі, опис програмного забезпечення; у роботах [15, 20] - постановка задачі класифікації, алгоритми класифікації.

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

X,XI,XII Всеросійські конференції «Математическое программирование и приложения» (м. Єкатеринбург, Інститут математики та механіки УрВ РАН, Росія 1995 р., 1999 р., 2003 р.), Всеукраїнська наукова конференція «Розробка та застосування математичних методів у науково-технічних дослідженнях» (м. Львів, 1995 р.), 17th IFIP TC7 Conference on System Modelling and Optimization (Прага, 1995 р.), Перша Міжнародна конференція "Нелокальные краевые задачи и родственные проблемы математической биологии, информатики, физики" (м. Нальчик, Росія, 3-7 грудня 1996 р.), Перша, третя та четверта Всеросійські конференції «Проблемы оптимизации и экономические приложения» (м. Омськ, Росія, 1-5 липня 1997 р., 2006р., 2009р.), Науково-методична конференція «Использование компьютерных технологий в учебном процессе» (м. Харків, 18-20 листопада 1997 р.), Перша міжнародна науково-практична конференція «Проблемы становления рыночной экономики. информационное и финансовое обеспечение деятельности предпринимательских структур» (м. Севастополь, 6-8 травня 1998 р.), VII Міжнародна конференція «Математика. Экономика. Экология. Образование», (м. Ростов -на -Дону, Росія, 26 травня-1 червня 1999 р.), Міжнародна конференція «Дискретный анализ и исследование операций» (м. Новосибірськ, Росія, 2000 р.), Друга міжнародна конференція «Математичні моделі та інформаційні технології в соціально-економічних та екологічних системах» (м. Луганськ 18-19 квітня 2001 р.), Перша Всеукраїнська науково-практична конференція «Информационные технологиии в экономике и на предприятии» (м. Запоріжжя, 2002 р.), Міжнародна наукова школа «Моделирование и анализ безопасности и риска в сложных системах» (м. С.-Петербург, Росія, 2002 р.), Всеросійська конференція «Дискретный анализ и исследование операций» (м. Новосибірськ, Росія, 2002 р.), Міжнародна школа-семінар «Теорія прийняття рішень» (м. Ужгород, 2002 р.), Друга Всеросійська конференція "Проблемы оптимизации и экономические приложения"(м. Омськ, Росія, 2003 р.), Перша Всеукраїнська науково-практична конференція «Математичне та програмне забезпечення інтелектуальних систем» (м. Дніпропетровськ, 2003 р.), Сьома міжнародна науково-технічна конференція «Системний аналіз та інформаційні технології» (м. Київ, 2005 р.), Третя Всеукраїнська науково-практична конференція «Математичне та програмне забезпечення інтелектуальних систем» (м. Дніпропетровськ, 2005 р.), VIII Міжнародна науково-практична конференція «Экономико-организационные проблемы проектирования и применения информационных систем» (м. Кисловодськ, Росія, 2005 р.), XIII Байкальська міжнародна школа-семінар «Методи оптимизации и их использование» (м. Іркутськ, Росія, 2005 р.), Четверта Міжнародна науково-практична конференція «Математичне та програмне забезпечення інтелектуальних систем», (м. Дніпропетровськ, 2006 р.), III Міжнародна школа-семінар «Теорія прийняття рішень»(м. Ужгород, 2006 р.), Internetional Workshop “Problems of decision making under uncerteines” (смт. Східниця, 2006 р.), Міжнародний симпозіум «Питання оптимізації обчислень (ПОО- XXXIII), (м. Київ, 2007 р.), IX Міжнародний семінар «Дискретная математика и ее приложения» (м. Москва, МГУ, Росія, 2007 р.), Третя науково-практична конференція «Інформаційні технології в управлінні туристичною та курортно-рекреаційною економікою» (м. Бердянськ, 2007 р.), Шоста Міжнародна науково-практична конференція «Математичне та програмне забезпечення інтелектуальних систем» (м. Дніпропетровськ, 2008 р.), Шостий та сьомий міжвузівські семінари «Комбінаторні конфігурації та їх застосування» (м. Кіровоград, 2008 р., 2009р.), Міжнародний симпозіум «Питання оптимізації обчислень (ПОО-XXXVI), (м. Київ, 2009 р.).

Публікації. Основні результати дисертаційної роботи опубліковано в 41 науковій роботі, серед яких 2 монографії, 1 патент на корисну модель, 17 статей у наукових фахових виданнях із переліку затвердженого ВАК України для спеціальності «Інформатика», 3 статті в журналах та збірниках наукових робіт із переліку ВАК для інших спеціальностей, 18 робіт у матеріалах наукових конференцій.

Структура та обсяг роботи. Дисертаційна робота складається з вступу, шести розділів, висновків, додатків та списку використаних джерел. Загальний обсяг роботи складає 298 сторінок, основний зміст роботи викладено на 275 сторінках.

ОСНОВНИЙ ЗМІСТ ДИСЕРТАЦІЇ

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

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

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

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

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

Третя задача - один з варіантів задачі упаковки, який полягає в наступному: провести обробку N деталей на деякому числі верстатів протягом часу T. Кожна деталь потребує на обробку час t_i, i=1,2,…,N. Треба розподілити обробку деталей, щоб, по-перше, загальний час її не перевищував T, по-друге, завантаження верстатів було найбільш рівномірним, тобто, у будь-які два моменти часу на проміжку [0,T] максимальна різниця числа верстатів, зайнятих обробкою у ці моменти часу, була мінімальною. Запропоновано три критерії рівномірності завантаження. Доведена NP-повнота задачі про рівномірне навантаження. Для пошуку наближених розв'язків задачі пропонується використовувати фрагментарний алгоритм.

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

Означення 2.2. Нехай задана скінченна множина X і група G оборотних перетворень цієї множини. Зовнішньою мірою симетрії непорожньої підмножини відносно дії підгрупи групи перетворень множини X називається відношення числа елементів цієї множини до числа елементів її орбіти, тобто , де орбіта підмножини . Для порожньої підмножини будемо вважати за визначенням . Очевидно, що для будь-якої підмножини Y?X справедлива нерівність . Інваріантні відносно дії групи перетворень G множини - це множини з максимальною мірою симетрії, тобто множини, для яких . Цілком асиметричною щодо групи симетрії A будемо називати таку підмножину Y?X, що перетинається з орбітою будь-якого свого елемента в єдиній точці. Кожний елемент y цілком асиметричної множини Y задовольняє такій властивості: . Іншими словами, для довільного елемента y?Y та будь-якого перетворення g?G, відмінного від тотожного, g(y)?Y.

Означення 2.4. Ядром симетрії або S_A-ядром множини називається будь-яка його максимальна за включенням цілком асиметрична підмножина.

Доведена

Теорема 2.3. Нехай Y - довільна підмножина скінченної множини X, A - підгрупа групи G перетворень множини X. Припустимо, що _ два довільних S_A -ядра множини Y. Тоді потужності (число елементів) цих множин однакові: .

Означення 2.5. Внутрішньою мірою симетрії непорожньої підмножини відносно дії підгрупи групи перетворень множини X будемо називати відношення потужності максимальної за числом елементів цілком симетричної підмножини до потужності множини Y.

Оптимізаційна задача з критерієм симетрії формулюється наступним чином: для скінченної множини X та її групи симетрії S знайти підмножину заданої потужності m з максимальною зовнішньою мірою симетрії. У дисертаційній роботі доведена NP -повнота цієї задачі.

Доведено також, що задача пошуку підмножини заданої потужності m з мінімальною зовнішньою мірою симетрії є поліноміально розв'язною.

Поняття міри симетрії поширено на множини з достатньо складною структурою. Зокрема, введено поняття міри симетрії для графів та для вимірних за Лебегом множин у евклідовому просторі . Показано, що задача пошуку підграфу з максимальною (мінімальною) мірою симетрії відносно групи зводиться до класичної задачі про досконале паросполучення.

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

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

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

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

Одна з головних проблем створення високопродуктивних систем підтримки прийняття рішень _ розробка алгоритмів розв'язання задач орієнтованих на взаємодію ОПР та комп'ютера. Основними вимогами до таких алгоритмів є:

а) невелике число кроків алгоритму з можливістю зміни параметрів пошуку розв'язку на кожному кроці;

б) відносно висока швидкість виконання алгоритму. Низькі швидкості для діалогу «Людина-машина» приводять до небажаних результатів. При великому часі очікування відгуку змінюються пріоритети цільових функцій виконавця. Тому критерій швидкості виконання розрахунку може отримати вирішальну роль на противагу іншим критеріям якості.

в) можливість виконання різних варіантів розрахунку (з різними обмеженнями та цільовими функціями). На будь-якому кроці можуть змінитися як система обмежень задачі, так і цільова функція ОПР. Тому необхідно передбачити можливість переходу як на попередні кроки розрахунку, так і на нові обмеження пошуку розв'язку, починаючи з поточного кроку.

Поліноміально трудомісткими алгоритмами такого класу є «жадібні» алгоритми (greedy algorithms), що за порівняно невелике число кроків призводять до оптимального розв'язку оптимізаційних задач. На жаль, «жадібних» алгоритмів, що дають точний розв'язок задачі дискретної оптимізації, існує не так вже й багато. Для наближених алгоритмів з апріорною оцінкою доведено, що їх трудомісткість не нижче трудомісткості алгоритмів точних. Тобто такі алгоритми призводять до повного перебору допустимих розв'язків задачі.

Таким чином, найбільш прийнятними алгоритмами діалогу «Людина-машина» для складних задач є евристичні алгоритми, які дозволяють зменшити множину розв'язків, що перевіряються.

Вимога застосовності «жадібного» алгоритму для пошуку розв'язків дискретних задач призводить до поняття фрагментарної структури.

Означення 3.4. Фрагментарною структурою на скінченній множині X називається сімейство її підмножин Е з такими властивостями:

1.;

2. .

Елементи множини E називаються припустимими фрагментами.

Будь-який припустимий фрагмент фрагментарної структури може бути побудований з порожньої множини «жадібним» алгоритмом, на кожному кроці якого додається один елемент до вже побудованої підмножини таким чином, що знову утворена підмножина належить фрагментарній структурі.

Фрагментарні структури тісно пов'язані з такими комбінаторними об'єктами як матроїди та гридоїди. Зокрема, будь-який гридоїд та будь-який матроїд є фрагментарною структурою.

Означення 3.5. Рангом підмножини називається величина rg(A), що дорівнює максимальній з потужностей припустимих фрагментів, які містяться у множині A.

Теорема 3.4. Для того щоб фрагментарна структура була матроїдом, необхідно і достатньо, щоб для будь-яких підмножин виконувалась нерівність

.

Показано, що конструктивно фрагментарну структуру можна задавати інакше. Фрагментарною структурою будемо називати пару , де X - множина, - бінарне відношення на множині X, що відповідає таким властивостям:

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

Максимальним припустимим фрагментом фрагментарної структури є такий припустимий фрагмент, що не є власною підмножиною жодного іншого припустимого фрагменту.

«Жадібний» алгоритм на фрагментарній структурі при заданому порядку фрагментів дозволяє отримати максимальний припустимий фрагмент за число кроків, що не перевищує числа елементів множини X.

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

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

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

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

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

Базова множина B кодів розв'язків, на якій здійснюється пошук оптимального розв'язку. Скінченні непорожні підмножини множини B називаються популяціями.

Оператор побудови початкової популяції: оператор, що виділяє на множині B її непорожню підмножину Y₀ ?B.

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

Кросовер, який задається оператором та за двома розв'язками-батьками будує новий розв'язок з множини B.

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

Оператор відбору - правило вибору, що дозволяє отримати нову популяцію з об'єднання множин батьків та нащадків. Зазвичай це правило задається за допомогою зазначення розміру (числа елементів) популяції та лінійного порядку або функції - критерію селекції. Елементи об'єднання множин батьків та нащадків упорядковуються та відбираються найкращі за значенням критерію.

Правило зупинки - правило, що визначає умову зупинки алгоритму.

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

Властивістю на базовій множині B будемо називати будь-яке відображення . Будемо говорити, що елемент має властивість P, якщо Для запропонованої еволюційно-фрагментарній моделі можна оцінити якість еволюційного алгоритму за допомогою наступної теореми

Означення 4.3. Властивість P називається спадковою, якщо за умови її наявності у двох розв'язках-батьках , цю властивість буде мати і результат кросоверу .

Теорема 4.2. Для числа розв'язків у , що мають властивість P у поколінні з номером k, при рівномірному правилі відбору справедлива така оцінка:

,

де - середня потужність множини розв'язків у поколінні з номером k+1, _ кількість елементів з властивістю P, що з'являються у проміжній популяції, _ середнє значення критерію на елементах поточної популяції, які мають властивість P, _ середнє значення критерію для всіх елементів поточної популяції, _ ймовірність зникнення властивості P у результаті дії оператора мутації.

Якщо властивість P є спадковою, то в межах запропонованої моделі має місце така теорема

Теорема 4.3. При рівномірному правилі відбору і умові, що потужність кожної популяції дорівнює N, а пари для кросоверу, число яких дорівнює M, вибираються незалежно з рівними ймовірностями, на кожному кроці еволюційного алгоритму має місце наступне співвідношення:

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

Означення 4.8. Система спадкових властивостей називається повною, якщо для будь-яких двох різних розв'язків з множини розв'язків B існує хоча б одна властивість , в якій ці розв'язки розрізнюються.

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

Опуклою підмножиною у метричному просторі називають підмножину, яка разом з будь-якими двома своїми точками містить всі точки геодезичної, що ці дві точки з'єднує. З теореми 4.7 випливає твердження, яке вказує на обмеженість еволюційного пошуку:

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

Таким чином, показано, що проблема пошуку початкових популяцій для реалізації еволюційно-фрагментарної моделі зводиться до задачі покриття (або розбиття) простору перестановок опуклими множинами.

Для оцінки якості еволюційних алгоритмів використовувалися наступні методики, засновані на чисельних експериментах, а саме порівняння:

1) з відомим точним алгоритмом (для задач невеликої розмірності);

2) з відомими наближеними алгоритмами;

3) з методом випадкового пошуку на множині перестановок фрагментів;

4) з точними та наближеними розв'язками з відомих баз даних тестових задач.

Для чисельного експерименту та порівняння результатів було розроблено комп'ютерну програмну систему «Еволюційно-фрагментарне моделювання». Система містить генератор різних типів задач дискретної оптимізації. В ній реалізовано відомі точні та наближені алгоритми пошуку розв'язку для модельних задач, реалізовано еволюційно-фрагментарні моделі з різними параметрами та використовуються деякі відомі бази даних тестових задач. Проведено чисельний експеримент для таких відомих дискретних оптимізаційних задач, як задача комівояжера, задачі розкрою, низка задач теорії розкладів, та ін.

П'ятий розділ присвячено проблемі вибору оптимального розв'язку в математичних моделях з багатьма критеріями.

Досліджено задачу класифікації та різні підходи до її розв'язання. Проведено аналіз методів розв'язання подібних проблем. У загальному випадку задача класифікації - це задача розбиття множини із заданими властивостями на основі відношення еквівалентності.

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

Запропоновано низку методів побудови класифікацій, а саме:

- метод «послідовно за утворюючими»;

- метод «по утворюючими з передачею мітки»;

- метод «по повному незалежному набору утворюючих»;

- «метод спадкування»;

- «метод послаблення та посилення».

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

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

.

Вимагається зіставити кожному елементу підмножину об'єктів , які обслуговуються пунктом обслуговування y. При цьому повинні виконуватися наступні властивості:

За умови вимірності множин, критерій обслуговування можна визначити рівністю:

Задача розподілу _ задача пошуку розбиття множини Х, інваріантного щодо дії деякої групи перетворень множини Y, тобто умовою розбиття є наступне: математичний модель перетворення упаковка

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

У шостому розділі досліджено принцип симетрії відносно дії груп перетворень як додаткова умова в математичних моделях з багатьма критеріями. Розглянуто групу диференційних перетворень евклідового простору . Інваріантність вибору відносно будь-якої підгрупи означає наступне: якщо елемент належить множині вибору , то цій же множині належатиме будь-який елемент орбіти . Іншими словами , тобто множина вибору інваріантна відносно дії підгрупи .

Теорема 6.1. Для того щоб множина була інваріантною відносно деякої групи диференційних перетворень G необхідно і достатньо, щоб існувала підмножина B?X, така, що . Тобто, множина X інваріантна відносно групи G в тому і тільки в тому випадку, коли ця множина є об'єднанням орбіт деяких своїх елементів.

В якості груп перетворень досліджено гладкі параметричні групи Лі на множині припустимих розв'язків X. Серед таких груп особливої уваги заслуговують однопараметричні групи Лі. Це множина гладких перетворень вигляду , P?R, причому для кожного дійсного числа ??P відображення F(x,?) - взаємно-однозначне відображення множини X на себе і має місце тотожність: F(F(x,?),?)=F(x, ???), де ? - групова операція на множині P. Такі групи перетворень однозначно визначаються векторними полями на Rⁿ . Іншими словами, знайдеться таке векторне поле ?(y) на множині X, що функція F(x,?) є розв'язком диференційного рівняння Лі

.

Для багатопараметричних груп перетворень система рівнянь Лі має наступний вигляд:

.

Ця система рівнянь є сумісною. Її розв'язок задає r-параметричну групу перетворень у тому і тільки в тому випадку, коли векторний простір L_r, натягнутий на оператори , є r-вимірною алгеброю Лі з оператором комутування

.

Принцип симетрії полягає в наступному: для відокремлення підмножин множини альтернатив треба використовувати властивість інваріантності правила вибору відносно деякої групи Лі, яка є підгрупою перетворень максимальної групи, що зберігає порядок Парето на (групи Парето).

Означення 6.5. Лінійний порядок на Rⁿ називається анонімним, якщо він інваріантний відносно перестановок координат. Іншими словами з умови випливає, що для будь-якої перестановки (i₁,i₂,…i_n) чисел 1,2,…n є справедливим співвідношення

.

Якщо відношення порядку задається критерієм , то властивість анонімності може бути сформульована в термінах критерію. Анонімність рівносильна симетричності функції F відносно будь-яких перестановок її аргументів, тобто

.

Тут U(F) _ область визначення функції F.

Для кожного вектора x?Rⁿ визначимо вектор lm(x)=(lm₁(x), lm₂(x),…, lm_n(x)), координати якого є координати вектора x, впорядковані за зростанням. Нехай - довільне лінійне відношення порядку на Rⁿ. Визначимо новий порядок наступним чином. Вважатимемо, що в тому і тільки в тому випадку, коли . Побудований таким чином порядок називатимемо лексимінною симетризацією порядку .

Означення 6.6. Лінійний порядок (квазіпорядок) на Rⁿ називається ефективним, якщо з умови «точка x* є максимальною за цим порядком» випливає, що точка x* належить множині Парето.

Поряд з поняттям ефективності для лінійних порядків в Rⁿ використовуватимемо поняття слабкої ефективності.

Означення 6.7. Лінійний порядок (квазіпорядок) на Rⁿ називається слабко ефективним, якщо з умови випливає, що .

Нехай задана задача багатокритеріальної оптимізації на множині X, де . Припустимо, що - слабко ефективний лінійний порядок на Rⁿ , Y* множина максимальних за цим порядком векторів на критеріальному просторі F(X).

Зв'язок між слабкою ефективністю та оптимальністю за Парето встановлюється теоремами

Теорема 6.6. Якщо множина Y*??, то її прообраз Ф^-1(Y*) містить точки множини Парето , тобто .

Теорема 6.7. Якщо лінійне відношення порядку є ефективним або слабко ефективним на Rⁿ, то його лексимінна симетризація буде слабко ефективним відношенням порядку.

Нехай функціональний порядок задано функцією F(x₁,x₂,…,x_n) область визначення якої в Rⁿ симетрична відносно перестановок координат. Симетризацією функції F будемо називати функцію

.

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

Означення 6.8. Будемо говорити, що підгрупа перетворень G має властивість нейтральності, якщо кожне перетворення цієї групи комутує (є перестановочним) з будь-якою перестановкою координат. Іншими словами, нехай елемент g групи G переводить вектор у вектор . Це перетворення має властивість нейтральності до перестановки координат (i₁,i₂,…,i_n), якщо

.

Доведено наступний критерій:

Теорема 6.7. Нехай однопараметрична група G визначається інфінітезимальним оператором . Для того, щоб перетворення групи G мали властивості нейтральності, необхідно і достатньо, щоб мали місце рівності .

Перетин групи, що зберігає порядок вибору, та групи Парето є деякою підгрупою групи Парето, яку називатимемо групою вибору. З теореми 6.7 випливає

Теорема 6.8 (про структуру групи вибору). Всяка група вибору в Rⁿ ізоморфна прямому добутку A?G, де A - підгрупа групи перестановок, а G - підгрупа діагональної групи оборотних монотонних перетворень. Тобто дію будь-якого елемента g?G на елемент x=(x₁,x₂,…,x_n)?Rⁿ можна представити у вигляді , де ?_i(t) - оборотні монотонно зростаючі функції однієї змінної, а (i₁,i₂,…,i_n) - деяка перестановка чисел 1,2,…,n. Для однопараметричних груп перетворень умова інваріантності правила вибору призводить до рівняння, що практично однозначно (з точністю до монотонної функції) визначає інтегральний критерій . Теорема 6.9 (про рівняння вибору). Для того щоб критеріальне правило прийняття рішень з інтегральним критерієм було інваріантним відносно дії групи перетворень G, достатньо щоб ?x?X виконувалося співвідношення

,

де - довільна неспадна функція однієї змінної.

Доведено наступне: якщо обмежитися тільки групами перетворень, що зберігають порядок Парето, то є справедливим канонічне рівняння для правил прийняття рішення на основі інтегрального критерію F, інваріантних відносно групи Парето,

,

де .

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

Теорема 6.10. Єдиними інваріантними відносно дії групи зсувів критеріальними правилами прийняття рішень з диференційним критерієм є правила, побудовані на основі критеріїв

,

де - загальний розв'язок однорідного рівняння , , . Умови, що гарантують ефективність критерію, мають вигляд:

.

Теорема 6.11. Єдиними інваріантними відносно дії групи гомотетій критеріальними правилами прийняття рішень з диференційним критерієм є правила, побудовані на основі критеріїв вигляду:

;

де - загальний розв'язок однорідного рівняння , . Умови, що гарантують ефективність розв'язання рівняння вибору, мають вигляд:

.

Позначимо P_i координатну функцію, яка кожному вектору x?Rⁿ ставить у відповідність його i-у координату, i=1,2,…,n. Ранговим критерієм порядку k називається функція . Критеріальне правило вибору, засноване на ранговому критерії, має вигляд: .

Доведено наступні основні властивості рангових критеріїв та лінійних порядків на Rⁿ, що ними породжуються:

Будь-який ранговий критерій є кусково-лінійною функцією. Тобто, весь простір Rⁿ можна представити у вигляді об'єднання замкнених множин з неперетинними внутрішностями, на кожній з яких ранговий критерій є лінійною функцією, більш того, збігається з однією з координатних функцій.

Будь-який ранговий критерій відповідає властивості анонімності, тобто в результаті перестановки координат вектора x значення цього критерія для вектора не зміниться.

Рангові критерії симетричні відносно дії однопараметричної групи зсувів у напрямі вектора a=(1,1,…,1).

Рангові критерії є симетричними відносно дії групи гомотетій.

Правила вибору, засновані на рангових критеріях, в загальному випадку, не мають властивості ефективності. Однак для будь-якого рангового критерію справедлива наступна теорема

Теорема 6.12 (про слабкоефективність рангових критеріїв). Для будь-якої компактної множини X?Rⁿ та жовільного рангового критерію r_k(x) перетин множини Парето з множиною точок, максимальних за критерієм r_k(x), не є порожнім.

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

Два вектори і порівнювані за Лоренсом у тому і тільки в тому випадку, коли виконуються нерівності

...