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

Для порядку Лоренса знайдено максимальну групу перетворень, що зберігає даний порядок.

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

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

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

Означення 6.11. Відношення парнодомінування на множині X називається повним, якщо для всіх пар (a,b), в яких a ? b, є справедливим одне і тільки одне з двох тверджень або .

Граф повного відношення парнодомінування є турнір, тобто його основа _ повний граф K_n, де n - число варіантів вибору. Відношення має числову характеристику (ступінь домінування). У цьому випадку граф, що представляє відношення, буде зваженим: кожній дузі, що відповідає відношенню , буде приписана вага .

Означення 6.12. Циклом Кондорсе називається така підмножина A?X, що

.

Теорема 6.22. Для будь-якого повного відношення парнодомінування існує цикл Кондорсе.

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

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

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

Теорема 6.23. Множина обраних за правилом Копленда елементів міститься в циклі Кондорсе, тобто Kp(X)?Kn(X).

Нехай граф G, що представляє повне відношення парно домінування, є зваженим графом. Занумеруємо вершини графа числами 1,2,…,n. Кожній наявній у графі G дузі, що з'єднує вершину i з вершиною j, поставлено у відповідність додатне число - вага цієї дуги. Припустимо, що не існує елементів, для яких одночасно xy і yx, тобто в графі G не існує орієнтованих циклів довжини 2. Доповнимо множину ваг {w_ij} до квадратної матриці, поклавши w_ji=-w_ij. Нехай .

Означення. Оцінкою Сімпсона для вершини i будемо називати величину

Узагальнене правило вибору Сімпсона: на множині X зі зваженим відношенням парнодомінування у якості оптимального обирається елемент з максимальною оцінкою Сімпсона.

Доведено наступна властивість

Група перетворень ваг, що зберігають правило вибору Сімпсона, містить усі перетворення вигляду .

Додаток A містить описи систем підтримки прийняття рішень, в яких використовувались розроблені математичні моделі та методи. Зокрема, наведено описи таких систем:

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

Інформаційна система «Земля». Формування плану ділянки на основі неповної або неточної інформації щодо вимірювань виконується на основі фрагментарного алгоритму.

Інформаційна система «Медіа». Під час автоматичного розміщення блоків реклами на аркуші друкованого видання реалізовано фрагментарний алгоритм задачі розміщення з критерієм симетрії.

Інформаційна система «Преса». Фрагментарний алгоритм використовано в задачі формування нових заявок розповсюджувачів друкованих видань на основі наявної інформації про попередні заявки.

Інформаційна система «Населення регіону». Застосовано фрагментарний підхід до розв'язання задачі класифікації та розбитті на групи населення за різними критеріями;

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

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

У додатку Б наведено опис програмного комплексу «Еволюційно-фрагментарні моделі» та результати чисельних експериментів.

ВИСНОВКИ

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

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

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

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

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

4. Запропоновано фрагментарну модель для створення діалогових систем підтримки прийняття рішень класу «Людина-машина» з використанням фрагментарного алгоритму.

5. Доведено властивість досяжності для фрагментарной моделі задачі симетричного розміщення, встановлено зв'язок між фрагментарними структурами і матроїдами.

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

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

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

9. Запропоновано новий метод вибору інтегрального критерію в оптимізаційних моделях з багатьма критеріями на основі принципу інваріантності щодо заданої групи перетворень.

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

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

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

Основні положення дисертації надруковано в таких працях:

1. Козин И.В. Принципы симметрии в теории принятия решений : монография / И.В. Козин. - Запоріжжя : Поліграф, 2007. - 164 с.

2. Перепелиця В.О. Задачи класифікації: підходи, методи, алгоритми : монографія / В.О. Перепелиця, І.В. Козін, Е.В. Терещенко. - Запоріжжя : Поліграф, 2008. - 188 с.

3. Пат. № 37839 Україна, МПК (2006) В41В 23/00 С14В 5/00. Спосіб розмітки плоского матеріалу / І.В. Козін ; заявник і власник ДВНЗ «Запорізький національний університет» МОН України. - № u 2008 08866; заяв. 07.07.2008 ; опубл. 10.12.2008, Бюл. № 23.

4. Перепелица В.А. Использование модели клеточных автоматов и методов классификации для прогнозирования временных рядов с памятью / В.А. Перепелица, Н.К. Максишко, И.В. Козин // Кибернетика и системный анализ. - 2006. - № 6. - С. 43-54.

5. Перепелица В.А. Задачи оптимизации на графах с интервальными параметрами / В.А. Перепелица, И.В. Козин, Н.К. Максишко // Кибернетика и системный анализ. - 2009. - № 2. - С. 3-14.

6. Козін І.В. Про оцінки потужності повної множини альтернатив для деяких двокритеріальних задач на графах / І.В. Козін // Доповіді Академії наук України. - 1993. - № 10. - С. 108-111.

7. Козин И.В. Механизм ключевых агентов для принятия решений в транспортной задаче / И.В. Козин, Н.Е. Титаренко // Питання прикладної математики і математичного моделювання : зб. наук. праць ; [ред. кол.: О. М. Кісельова (відп. редактор) та ін.]. - Д. : Вид-во Дніпропетр. ун-ту, 2004. - С. 117-122.

8. Козин И.В. Фрагментарные алгоритмы в системах поддержки принятия решений / И.В. Козин // Питання прикладної математики і математичного моделювання : зб. наук. праць ; [ред. кол.: О.М. Кісельова (відп. редактор) та ін.]. - Д. : Вид-во Дніпропетр. нац. ун-ту, 2006. - С. 131-137.

9. Козин И.В. Условия инвариантности правил выбора / И.В. Козин // Питання прикладної математики і математичного моделювання : зб. наук. праць ; [ред. кол.: О.М. Кісельова (відп. редактор) та ін.]. - Д. : Вид-во Дніпропетр. нац. ун-ту, 2007. - С. 160-170.

10. Козин И.В. Фрагментарные структуры и эволюционные алгоритмы / И.В. Козин // Питання прикладної математики і математичного моделювання : зб. наук. праць ; [ред. кол.: О.М. Кісельова (головний редактор) та ін.]. - Д. : Вид-во Дніпропетр. нац. ун-ту ім. Олеся Гончара, 2008. - С. 138-146.

11. Козин И.В. Использование ЭВФ-алгоритмов для решения задачи прямоугольного раскроя / И.В. Козин, С.И. Полюга // Питання прикладної математики і математичного моделювання : зб. наук. праць; [ред. кол. О.М. Кісельова (голов. ред.) та ін.]. - Д. : Вид-во Дніпропетр. нац. ун-ту ім. Олеся Гончара,. - Дніпропетровcьк, 2009. - С. 199-208.

12. Kozin I. V. Evolutionary fragmentary algorithm for permutation flow shop problem / I.V. Kozin, O.S. Bondarenko // Таврійський вісник інформатики та математики. - 2009. - № 2. - С. 47-51.

13. Козин И.В. Оптимизационные задачи на графах с динамическими параметрами / И.В. Козин, Г.Л. Козина // Динамические системы. - 2001. - Вып. 17. - Сімферополь : КФТ. - С. 228-233.

14. Козин И.В. Автоматизированная система «Деканат» / И.В. Козин, Т. В. Заховалко, С.В. Курапов // Вісник Запорізького державного університету. Фізико-математичні науки. - 2003. - № 1. - С. 48-55.

15. Козин И.В. Алгоритмы оптимальной классификации / И.В. Козин, С.В. Курапов // Вісник Запорізького національного університету. Фізико-математичні науки. - 2005. - № 1. - 25-29.

16. Козін І.В. Розв'язок задачі поділу за відсутності ядра в кооперативних іграх за допомогою системи штрафів / І.В. Козін, С.О. Осипов // Вісник Запорізького національного університету. Фізико-математичні науки. - 2006. - № 1. - С. 74-77.

17. Козин И.В. Правила принятия решений на основе отношения парнодоминантности / И.В. Козин // Вісник Запорізького національного університету. Фізико-математичні науки. - 2008. - № 1. - С. 97-104.

18. Козин И.В. Об оценке мощности шарового покрытия пространства перестановок/ И.В. Козин, А.С. Бондаренко, С.И. Полюга // Вісник Запорізького національного університету. Фізико-математичні науки. - 2009. - № 1. - С. 134-138.

19. Козін І.В. Дослідження міри нестійкості вибору в моделях матричних ігор / І.В. Козін, С.О. Осипов // Вісник Донецького університету, Сер. А : Природничі науки. - 2007. - Вип. 1. - С. 46-48.

20. Перепелица В.А. Методы классификации и алгоритмы раскраски графа / В.А. Перепелица, И.В. Козин, С.В. Курапов // Вісник Дніпропетровського університету, серія : Математика. - 2008. - Т. 16, № 6/1. - Bип. 13. - С. 135-143.

21. Maliar S. Solving Capability of LCA / Serguei Maliar, Igor Kozin, Vitali Perepelitsa. - Economics Working Papers 119, Department of Economics and Business, Universitat Pompeu Fabra, June 1995. - P. 1-11.

22. Козин И.В. Фрагментарный алгоритм для задачи симметричного размещения / И.В. Козин // Радіоелектроніка, інформатика, управління. - 2006. - № 1. - C. 69-73.

23. Козин И.В. Эволюционный и фрагментарный подходы к задаче о равномерной нагрузке / И.В. Козин, А.С. Бондаренко // Искусственный интеллект. - 2009. - № 4. - С. 248-252.

24. Региональная информационная система управления финансами / О.И. Баштанник, И.В. Козин, Н.К. Максишко, С.Н. Медведь // Сб. тр. Первой междунар. науч.-практ. конф. [«Проблемы становления рыночной экономики : информационное и финансовое обеспечение деятельности предпринимательских структур»], (Севастополь, 1998). - (Часть II). - С. 176-180.

25. Козин И.В. Взаимодействие экономических агентов с различным отношением к риску / И.В. Козин // Моделирование и Анализ Безопасности и Риска в Сложных Системах : Труды Междунар. Науч. Школы МА БР-2002 (Санкт-Петербург, 2-5 июля, 2002 г.). - Спб. : Издательство «Бізнес-Пресса» 2002. - С. 212-214.

26. О создании автоматизированной системы учета и управления земельными ресурсами Запорожской области / О. Баштанник, И. Козин, Н. Максишко, С. Медведь // Модели управления в рыночной экономике : (сб. науч. тр. / общ. ред. Ю.Г. Лысенко ; Донецкий национальный университет). - Донецк : ДонНУ, 2002. - Спец. выпуск. - C. 309-313.

27. Козин И.В. Неманипулируемые механизмы принятия кооперативных решений / И.В. Козин // Праці міжнар. школи-семінару [«Теорія прийняття рішень»], (Ужгород, 7-12 жовт. 2002 р.). - Ужгород, УжНУ, 2002. - С. 43.

28. Козин И.В. Моделирование сделок на финансовом рынке одного товара / И.В. Козин // Материалы VIII Междунар. науч.-практ. конф. [«Экономико-организационные проблемы проектирования и применения информационных систем»], (Кисловодск, 27-29 окт., 2005 р.) / Ростовский гос. экон. ун-т «РИНХ». - Ростов н/Д, 2006. - С. 51-54.

29. Козин И.В. Проект «Университет».Об особенностях разработки и внедрения. Автоматизация задач управления университетом / И.В. Козин, С.В. Курапов, В.А. Перепелица // Материалы VIII Междунар. науч.-практ. конф. [«Экономико-организационные проблемы проектирования и применения информационных систем»], (Кисловодск, 27-29 окт., 2005 р.) / Ростовский гос. экон. ун-т «РИНХ». - Ростов н/Д, 2006. - С. 279-284.

30. Козин И.В. Неманипулируемые механизмы принятия решений. Равновесные модели экономики и энергетики / И.В. Козин // Труды Всерос. конф. и секции математ. экономики XIII Байкальской междунар. школы-семинара «Методы оптимизации и их приложения». - Иркутск : Изд -во ИСЭМ СО РАН, 2005. - С. 303-307.

31. Козин И.В. Модели принятия решений, инвариантные относительно групп преобразований / И.В. Козин // Праці III-ї міжнар. школи-семінару [«Теорія прийняття рішень»], (Ужгород, 2-7 жовт. 2006 р.). - Ужгород, УжНУ, 2006. - С. 59-60.

32. Козин И.В. Фрагментарный подход в задачах оптимизации с трудноформализуемыми критериями / И.В. Козин // Праці Міжнар. симп. «Питання оптимізації обчислень (ПОО-XXXIII). - Київ : Інститут кібернетики ім. В.М. Глушкова НАН України 2007. - С. 132-133.

33. Козин И.В. Экстремальные задачи с критерием симметрии на конечных множествах / И.В. Козин // Материалы IX Междунар. семинара [«Дискретная математика и ее приложения»], (Москва, 18-23 июня 2007 р.). - Москва : МГУ, 2007. - С. 319-321.

34. Козин И.В. Фрагментарный подход к трудноформализуемым задачам поиска оптимальных решений / И.В. Козин, С.И. Полюга // Праці IV-ї міжнар. школи-семінару [«Теорія прийняття рішень»], (Ужгород, 29 верес.-7 жовт. 2008 р.). - Ужгород, УжНУ, 2008. - С. 94-95.

35. Перепелица В.А. Эволюционные модели в задачах теории расписаний / В.А. Перепелица, И.В. Козин, А.С. Бондаренко // Материалы IV Всерос. конф. [«Проблемы оптимизации и экономические приложения»] (Омськ, 29 июня-4 июля 2009 г.) / Омский филиал Института математики им. С.Л.Соболева СО РАН. - Омск : Полиграфический центр КАН, 2009. - С. 155.

36. Козин И.В. Фрагментарно-эволюционный подход в задачах дискретной оптимизации / И.В. Козин, В.А. Перепелица // Праці Міжнар. симп. «Питання оптимізації обчислень (ПОО-XXXV). - Київ : Інститут кібернетики ім. В.М. Глушкова НАН України 2009. - Т. 1. - С. 333-335.

37. Козин И.В. Применение ЭВФ-алгоритмов в задачах теории расписаний / И.В. Козин, А.С. Бондаренко // Праці Міжнар. симп «Питання оптимізації обчислень (ПОО-XXXV). - Київ : Інститут кібернетики ім. В.М. Глушкова НАН України 2009. - Т. 1. - С. 73-77.

38. Козин И.В. Использование методов визуализации для решения задачи классификации в моделях управления регионом / О.И. Баштанник, И.В. Козин, Н.К. Максишко // Матеріали ІІ міжнар. конф. [«Математичні моделі та інформаційні технології в соціально-економічних та екологічних системах»], (Луганськ, 18-19 квіт. 2001 р.). - С. 95-97.

39. Козин И.В. О структуре множества слабых решений интервальных задач на графах / И.В. Козин, Г.Л. Козина // 12 Всерос. конф. [«Математическое программирование и приложения»], (Екатеринбург, 24-28 февр. 2003 г.), информ. бюл. : тезисы докладов. - Екатеринбург : Ур РАН, 2003. - С. 147-148.

40. Козин И.В. Механизмы выбора решения в многокритериальной задаче о назначениях / И.В. Козин // Междунар. конф. [«Дискретный анализ и исследование операций DAOR'2000»], (Новосибирск, 26 июня-1 июля 2000 г.). - Новосибирск : Изд-во Ин-та математики, 2000. - С. 127.

41. Козин И.В. Задачи дискретной оптимизации с критерием симметрии / И.В. Козин, Т.В. Заховалко // Матеріали Всеукр. наук.-практ. конф. [«Інформатика та системні науки (ІСН-2010)»], (Полтава, 18-20 берез. 2010 р.). - Полтава : РВВ ПУСКУ, 2010. - С. 85-86.

АНОТАЦІЇ

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

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

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

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

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

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

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

Ключові слова: моделі прийняття рішень, міра симетрії, фрагментарні моделі, матроїди, еволюційні моделі, аксіоматична теорія опуклості, системи підтримки прийняття рішень, діалогові системи класу «людина-машина», багатокритеріальна оптимізація, групи Лі.

Козин И.В. Математические модели размещения, упаковки и распределения с условием инвариантности относительно групп преобразований. - Рукопись

Диссертация на соискание ученой степени доктора физико-математических наук по специальности 01.05.02 - математическое моделирование и вычислительные методы. - Институт кибернетики имени В.М. Глушкова НАН Украины, Киев, 2010.

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

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

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

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

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

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

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

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

Ключевые слова: модели принятия решений, мера симметрии, фрагментарные модели, матроиды, эволюционные модели, аксиоматическая теория выпуклости, системы поддержки принятия решений, диалоговые системы класса «человек-машина», многокритериальная оптимизация, группы Ли.

Kozin I.V. Mathematical models of placing, packing and distributing with the condition of invariance in relation to the groups of transformations. - Manuscript

Thesis submitted for a Doctor's degree in physical and mathematical sciences by speciality 01.05.02 - mathematical modeling and numerical methods. - V.M.Glushkov Institute of Cybernetics of National Academy of Science of Ukraine, Kyiv, 2010.

Dissertation is devoted to the questions of substantiation and testing of new mathematical models and methods of search of approximate solutions in discrete optimization problems, in problems with the criterion of symmetry, methods of search of Pareto-optimal solutions of multi-criteria problems with the conditions of invariance in relation to the groups of transformations, research of fragmentary structures and evolutionary models for the search of optimal solutions, application of the developed methods.

The concept of measure of symmetry is introduced, the set of problems of discrete optimization is formulated with the criterion of symmetry, computational complexity of these problems is set.

For the search of approximate solutions in the problems of discrete optimization with hard-to-formalize criteria fragmentary approach is suggested which is perspective for the use in the decision support systems of «man-machine» class. Relationship of fragmentary model with the matroid theory is set.

An universal evolutionary-fragmentary model is proposed for the search of approximate solutions in discrete optimization problems. Relationship of property of heredity in an evolutionary model with the axiomatic theory of convex sets in permutations space is set. The performance bound of evolutionary algorithm is generalized to the case of evolutionary-fragmentary model.

For the substantiation of choice of solution in the multi-criteria optimization problems it is suggested to use principle of invariance of solution in relation to the certain groups of transformations. Application of such approach is given by possibility a priori to build equations of choice for an integral criterion in the problem of multi-criteria optimization. For the simplest groups of transformations it is succeeded to get the analytical solution of these equations.

On the basis of principle of symmetry the pair domination methods of optimum choice by majority voting are generalized for the arbitrary relations.

Keywords: decision making models, measure of symmetry, fragmentary models, matroids, evolutionary models, axiomatic theory of convexity, decision support systems, interactive systems of class «man-machine», multi-criteria optimization, Lie groups.

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