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

Харківській національний університет радіоелектроніки

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

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

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

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

Романова Наталія Гавриілівна

Харків 2007

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

Робота виконана в Полтавському університеті споживчої кооперації України

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

Офіційні опоненти: доктор фізико-математичних наук, професорНовожилова Марина Володимирівна,Харківський державний технічний університет будівництва та архітектури, завідувач кафедри комп'ютерного моделювання і інформаційних технологій;

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

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

Захист відбудеться „ 12” квітня 2007 р. о 1400 годині на засіданні спеціалізованої вченої ради К 64.052.07 при Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, просп. Леніна, 14

З дисертацією можна ознайомитися у бібліотеці Харківського національного університету радіоелектроніки за адресою: 61166, м. Харків, просп. Леніна, 14

Автореферат розісланий „ 7 ” березня 2007 р.

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

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

математичний упакування обслуговування евклідовий

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалась на кафедрі математичного моделювання та соціальної інформатики Полтавського університету споживчої кооперації України згідно з планами науково-дослідної роботи університету та бюджетною темою № 213/04 „Евклідова комбінаторна оптимізація”.

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

Для досягнення поставленої мети були сформульовані наступні задачі:

1) Розробка нових математичних моделей комбінаторних задач геометричного проектування та дослідження їх властивостей.

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

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

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

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

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

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

Наукова новизна одержаних результатів:

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

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

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

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

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

Практичне значення одержаних результатів. Отримані результати мають практичне значення при розв'язуванні широкого кола задач геометричного проектування (розміщення, упакування, покриття). Розвинуті та реалізовані математичні моделі задачі кольорового упакування прямокутників в досить довгій смузі із зонами заборони з урахуванням похибок початкових даних та задачі про визначення порядку обслуговування замовлень для максимізації рентабельності системи як задач евклідової комбінаторної оптимізації на множині поліпереставлень. Ці моделі можуть бути використані при математичному моделюванні та розв'язанні відповідних прикладних задач. Комбінований метод розв'язування лінійних задач оптимізації на вершинно розташованих евклідових комбінаторних множинах дає точний розв'язок і може бути практично застосований до розв'язування задач з відповідною моделлю. Результати дисертаційного дослідження впровадженні в навчальний процес Полтавського університету споживчої кооперації України та використані в курсовому проектуванні з дисциплін „Інформатика”, „Програмування”, „Методи оптимізації та дослідження операцій” (акт від 21.12.2006 р.).

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

- для задачі кольорового упакування прямокутників в досить довгій смузі із зонами заборони з урахуванням похибок початкових даних, яка є комбінаторною оптимізаційною задачею, побудовано інтервальну математичну модель та виконано її реалізацію [1, 2, 12, 15], сформульовано правила відсікання безперспективних вершин [1, 12, 15];

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

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

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

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

- отримані оцінки кількості арифметичних операцій при побудові опуклого продовження многочленів, що задані на поліпереставленнях модифікованим методом Стояна-Яковлева [3, 13].

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

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

- Міждержавній науково-методичній конференції “Проблеми математичного моделювання” (28-30 травня 2003 р., м. Дніпродзержинськ);

- VIII Міжнародній науково-практичній конференції “Наука і освіта'2005” (м. Дніпропетровськ).

- 50 - 54-тій наукових конференціях професорів, викладачів, наукових працівників та студентів Полтавського національного технічного університету імені Юрія Кондратюка ( Полтава 1998-2002 р. р.).

Публікації. Основні результати дисертації опубліковано у 15 наукових працях (5 статей у наукових журналах; 5 - у збірниках наукових праць, 4 - у матері-алах та тезах конференцій; 1 депонована робота), з них 6 статей у виданнях, що включені ВАК України до переліку фахових, 2 у журналах Російської академії наук.

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

2. Основний зміст роботи

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

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

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

Розглянемо упорядковану -вибірку з мультимножини:

. (1)

Вибірки вигляду (1) вважаються різними, якщо таке, що . Множину , елементами якої є упорядковані -вибірки вигляду (1) з мультимножини , називають евклідовою комбінаторною множиною.

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

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

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

, . (2)

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

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

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

Розглянемо задачу знаходження пари , де

; ; (4)

; (5)

. (6)

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

Якщо, розв'язавши задачу (4), (6) і отримавши мінімаль, маємо виконання умови (5) для неї, то задача (4)?(6) розв'язана. Інакше будується нерівність відсікання, яка проходить через суміжні з вершини. Після цього знову розв'язується задача лінійного програмування вигляду (4), (6), для її мінімалі перевіряється умова (7). Цей процес продовжується поки умова (7) не виконається.

Комбінований метод для лінійної комбінаторної задачі оптимізації на вершинно розташованих евклідових комбінаторних множинах.

1. Розв'язується за методом комбінаторного відсікання перша допоміжна задача лінійного програмування методом, що дає вершину допустимої області (симплекс-методом тощо). Якщо для її мінімалі виконалась умова (7), то задача (4) ? (6) розв'язана. Інакше ? перехід на п. 2.

2. Знаходиться поточне значення екстремалі методом гілок та меж (чи будь-яким іншим переборним методом).

3. Перевіряється умова:

. (8)

Якщо умова (8) виконалась, то задача (4) ? (6) розв'язана. Екстремаллю є . Якщо ? ні, то перевіряється, чи не є єдиною допустимою точкою допустимої області поточної допоміжної задачі лінійного програмування. Якщо так ? то задача (4) ? (6) не має розв'язку. Інакше ? перехід на п. 4.

4. Будується обмеження-відсікання точки , ця рівність додається до системи (6). Таким чином, формується нова допоміжна задача лінійного програмування вигляду (4), (6), (7) в методі комбінаторного відсікання. Шукається її розв'язок . Перехід на п. 2.

Теорема 2.2. Комбінований метод для задачі (4) ? (6) є точним і скінченим.

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

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

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

Досліджуючи задачу (9)-(10), перейдемо до задачі з лінійною цільовою функцією, здійснивши відображення за правилом. Образ в при відображенні множини має вигляд. Тоді при відображенні (11), (12) задача (9) набуває вигляду: знайти.

Теорема 3.1. Якщо точка, що задовольняє (13), то, яка отримана при підстановці в (11), задовольняє умову (9).

Для побудови методів розв'язування задачі (13) - (14) важливо дослідити опуклу оболонку множини. Для множини поліпереставлень опукла оболонка це многогранник поліпереставлень. Отримаємо образ многогранника при відображенні, яке визначається (11) множина точок з, що задається системою (15)-(17). Розглянемо деякі властивості многогранника.

Теорема 3.2. .

Теорема 3.3. а) Нехай грань многогранника. Тоді знайдуться такі підмножини, для яких нерівності в (16) обертаються у рівності при будь-якому, тобто відповідні обмеження є жорсткими для. При цьому множина розв'язків системи, одержаної з (15) - (17) заміною рівностями нерівностей, що містять ; б) Якщо для підмножин нерівності в (16), що містять, замінити рівностями, то множина розв'язок одержаної системи є гранню многогранника, де, а і підсумовування в (18) проводиться за всіма тими індексами, для кожного з яких знайдеться таке, що.

Теорема 3.4. Відображення, що визначається співвідношенням (11) задає взаємно однозначну відповідність між точками та точками.

Теорема 3.5., де множина визначається (12).

Отже, згідно з теоремою 3.5 вершина многогранника точка при застосуванні відображення (13) перейде в точку, де.

Теорема 3.6. Вершинами многогранника, суміжними з вершиною, що визначена (20). є усякі вершини, які одержані з вершини переставленням нерівних координат за умови.

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

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

Модифікація методу Стояна-Яковлева для знаходження в поставленій задачі. Кожній функції поставимо у відповідність опуклу функцію, яка задовольняє умову. На накладемо також умову.

Процес побудови опуклої функції, що задовольняє умови (21), (22), здійснемо рекурентно. При маємо лінійну невідємну на функцію, де. Нехай для будь-яких існують опуклі функції, що задовольняють (21), (22). Треба вказати вигляд функції, при деякому фіксованому наборі. Виберемо для деякого. Введемо у розгляд, де та для; точку, де; точку, де, для та, для. Але утворимо множини за наступним алгоритмом. Переглянемо всі множини. Якщо для, що розглядається, що та, тоді не змінюємо на цьому етапі алгоритма. Якщо для, що розглядається, для всіх виконується, тоді підмножину виключаємо з, з множини виключаємо підмножину, число зменшуємо на, число зменшуємо на 1. Наприкінці алгоритма серед чисел, які утворюють множину, визначимо кількість різних . Введемо у розгляд точку, що утворюється з координат, які попали у множину, та точку, що утворюється координат точки, індекси яких попали у множину. При функція у правій частині співвідношення (23) опукла.

Оцінка числа арифметичних операцій в модифікованому методі Стояна-Яковлева. - це кількість змінних, які утворюють поліном, - число, оцінка зверху, - число, оцінка знизу для числа арифметичних операцій, які необхідно здійснити при опуклому продовженні функції з множини в ,- точне число операцій, які необхідно здійснити при опуклому продовженні функції з множини в . Формули для оцінки зверху числа арифметичних операцій виведемо індукцією по числу . 1) якщо - парне,; 2) якщо -непарне. Аналогічно, оцінка знизу. Аналогічно, для опуклого продовження функції з множини в отримаємо формули для оцінки точного числа арифметичних операцій. Отримано оцінки числа операцій, які показують корисність даної модифікації у порівнянні з вихідним методом.

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

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

Математична модель (26)-(27) дає можливість застосувати при реалізації моделі (24)-(25) відомі методи комбінаторної оптимізації і врахувати похибки початкових даних. Розроблено алгоритм методу гілок та меж для розв'язування поставленої задачі. Проведено числові експерименти.

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

Висновки

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

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

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

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

Для методу Стояна-Яковлева опуклого продовження многочленів з перестав-лень в арифметичний евклідів простір в роботі розроблена та обґрунтована модифікація для випадку опуклого продовження з поліпереставлень, проведена оцінка числа арифметичних операцій.

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

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

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

Список опублікованих праць за темою дисертації

1. Емец О.А., Евсеева Л.Г., Романова Н.Г. Задача цветной упаковки прямоугольников с учетом погрешностей исходных данных и ее решение // Экономика и матем. методы.-2000.-Т.36, - №3.-С.149-152.

2. Емец О.А., Евсеева Л.Г., Романова Н.Г. Интервальная математическая модель комбинаторной задачи цветной упаковки прямоугольников // Кибернетика и системный анализ. - 2001. - №3. - С.131 - 138.

3. Валуйская О.А., Емец О.А., Романова Н.Г. Выпуклое продолжение многочленов, заданных на полиперестановках, модифицированным методом Стояна-Яковлева // Журн. вычислит.математ и матем. физики. - 2002. - Т. 42, - №4. - С.591- 596.

4. Ємець О.О., Романова Н.Г., Чілікіна Т.В. Задачі оптимізації на вершинно розташованих евклідових комбінаторних множинах // Математичне моделювання. - 2003. - №2 (10). - С. 13-15.

5. Ємець О.О., Романова Н.Г. Безумовна задача оптимізації дробово-лінійної цільової функції на поліпереставленнях: зведення до лінійної умовної на спеціальній комбінаторній множині // Радиоэлектроника и інформатика.- 2005. - №1. - С. 70-74.

6. Ємець О.О., Романова Н.Г. Комбінований метод розв'язування лінійних комбінаторних задач оптимізації на вершинно розташованих евклідових комбінаторних множинах //Динамические системы (межвед. науч. сб.) - Симферополь: Тавр. нац. ун-т., 2004. Вып. 17. - С. 166-170.

7. Ємець О., Євсеєва Л., Романова Н. Результати численних експериментів по розв'язуванню задачі кольорового упакування прямокутників з урахуванням похибок початкових даних// Зб. наук. праць: Вісник Полтав. держ. пед. ін-ту ім. В.Г. Короленка. - Сер. "Фіз.-матем. науки" - 1998 - Вип. 3.- С.16-18.

8. Ємець О.О., Романова Н.Г., Роскладка О.В. Про властивості деяких задач евклідової комбінаторної оптимізації на переставленнях та методи їх розв'язування // Вісник Львів. нац. ун-ту . Сер. приклад. математика та інформатика. - 2002. - Вип. № 5. - С. 89 - 94.

9. Ємець О.О., Романова Н.Г. Моделювання задачами оптимізації з дробово-лінійною цільовою функцією на поліпереставленнях // Вісник нац. ун-ту “Львівська політехніка” Сер. Фіз.-мат. науки. - 2005. - Вип. № 540. - С. 65 - 68.

10. Романова Н.Г. Задача оптимізації дробово-лінійної цільової функції на поліпереставленнях: властивості її комбінаторного многогранника // Журн.”Волинський математичний вісник” Сер. Прикладна математика. - 2004. - Вип. № 2 (11). - С. 223-233.

11. Ємець О.О., Романова Н.Г., Чілікіна Т.В. Задачі оптимізації на вершинно розташованих евклідових комбінаторних множинах // В кн.: Міждержавна науково-методична конференція “Проблеми математичного моделювання” (28 -30 травня 2003 р.). - Дніпродзержинськ, 2003.- С. 32-33.

12. Ємець О.О., Євсеєва Л.Г., Романова Н.Г. Реалізація інтервальной моделі задачі кольорового упакування // Матеріали VII міжнар. наук. конф. ім. ак. М. Кравчука (14-16 травня 1998р.).- К., 1998.- С. 166.

13. Ємець О.О., Пічугіна О.С., Романова Н.Г. Про поширення на поліпереставлення методу Стояна-Яковлева опуклого продовження функції та його ефективність // Матеріали VIII міжнар. наук. конференції ім. ак. М.Кравчука (11-14 травня 2000 р.).- К., 2000. - С. 278

14. Романова Н.Г. Властивості множини допустимих розв'язків в дробово-лінійній задачі оптимізації на поліпереставленнях // Матеріали VIII міжнар. наук.-практ. конференція “Наука і освіта'2005”. . - Дніпропетровськ: Наука і освіта, 2005, Том 23. Математичне моделювання, - С. 57-58.

15. Ємець О.О., Євсеєва Л.Г., Романова Н.Г. Розв'язування задачі кольорового упакування прямокутників з урахуванням похибок початкових даних/ -Київ, 1998.- 19 с.-Укр.- Деп. в ДНТБУ 02.02.1998, №90.

Анотація

Романова Н.Г. Задачі евклідової комбінаторної оптимізації на поліпереставленнях та методи їх розв'язування. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.02 - математичне моделювання та обчислювальні методи (фіз.-мат. науки). - ХНУРЕ, Харків, 2007.

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

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

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

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

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

Аннотация

Романова Н.Г. Задачи евклидовой комбинаторной оптимизации на полиперестановках и методы их решения. - Рукопись.

Диссертация на присвоение научной степени кандидата физико-математических наук по специальности 01.05.02 - математическое моделирование и вычислительные методы (физ.-мат. науки). - ХНУРЭ, Харьков, 2007.

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

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

Реализована математическая модель цветной упаковки (при этом: построена математическая модель зоны запрета с учетом погрешностей исходных данных, определено максимальное количество прямоугольников данного цвета, которые могут быть упакованы в полосе между соседними зонами запрета с учетом погрешностей, введено определение интервальной полиперестановки), проведены числовые эксперименты. На ПК Pentium проведены числовые эксперименты для случаев, когда длины прямоугольников и соответствующие погрешности будут случайными величинами, которые распределены по равномерному или нормальному законам. Сформулированы правила отсекания бесперспективных вершин для комбинаторной оптимизационной задачи цветной упаковки прямоугольников в достаточно длинной полосе с зонами запрета с учетом погрешностей исходных данных.

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

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

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

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

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

Abstract

Romanova N.G. The Euclidean Combinatorial Optimization Problems on the Polyarrangements and Methods of their Solving. - Manuscript.

Thesis for Candidate Degree in Physical and Mathematical Sciences, specialty 01.05.02. - Mathematical Simulation and Computational Methods. - Kharkiv National University of Radio Electronics, Kharkiv, 2007.

Mathematical models were researched and developed: for the problems of color packing of rectangles and the problem to denote the order of order services for maximization of profitability of service system.

The mathematical model of color packing was realized. Number experiments were conducted.

New complex method for solving linear combinatorial optimization problems on top-situated Euclidean combinatorial sets was developed and grounded.

The method of Stoyan-Yakovlev of convex function extensions with arrangements was extended on the set of polyarrangements.

The properties of combinatorial set and combinatorial polyhedron for the optimization problem with linear conditional function on E and one linear restriction to which unconditional optimization problem on polyarrangement set is led were considered. The theorem about polyhedron sides was proved. The criterion of its tops, the criterion of combination of polyhedron tops were received and grounded, and their number was counted.

The theorem about the equivalence of solving for the linear fractional problem with conditional function on polyarrengements and conditional optimization problem with linear conditional function on Euclidean combinatorial set E of special kind was proved.

Key words: poly combinatorial set, combinatorial polyhedrons, arrangements, polyarrangements, combinatorial optimization, Euclidean combinatorial sets, linear fractional conditional function.

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

...