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

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




НазваПро властивості деяких задач евклідової комбінаторної оптимізації на переставленнях та методи їх розв’язування
Дата19.11.2012
Розмір78.8 Kb.
ТипДокументи

УДК 519.85

ПРО ВЛАСТИВОСТІ ДЕЯКИХ ЗАДАЧ

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


О. Ємець, Н. Романова, О. Роскладка

Полтавський державний технічний університет ім. Ю.Кондратюка


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

^ Ключові слова:

1. Деякі нові властивості загального багатогранника переставлень

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

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

Як відомо [1], кількість гіперграней, які інцидентні довільній вершині загального багатогранника переставлень , що його описує незвідна система

(1)

де ,

дорівнює

. (2)

Теорема 1. Багатогранник , що його описує незвідна система (1), є невиродженим тоді і тільки тоді, якщо .

Доведення.

Достатність. Нехай . Тоді за формулою (2)

.

Оскільки , то багатогранник є простим [2]. А оскільки система (1) не містить надлишкових обмежень, то достатність доведено.

Необхідність. Нехай багатогранник є невиродженим [2]. Тоді  – простий. Отже, . Використавши (2), маємо:

.

Оскільки , то

.

Звідси , отже,

. (3)

Проаналізуємо розв’язки рівняння (3) відносно змінної . Кількість доданків у лівій частині (3) дорівнює . Очевидно, що і різниця є цілим числом. Тоді сума додатних цілих чисел дорівнює їх кількості. Це можливо в єдиному випадку, якщо . Теорему доведено.

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

Теорема 2. Нехай  – невироджений багатогранник в . Якщо , то також є невиродженим.

Доведення. Оскільки  – невироджений, то за теоремою 1 для маємо , тобто . За умови . Отже, за теоремою 1 також є невиродженим, що і треба було довести.

Нехай система обмежень, що задає багатогранник , така:

. (4)

Розглянемо еквівалентність багатогранників при фіксованій матриці . Позначимо багатогранник, що його описує (4), .

Не обмежуючи загальності міркувань, можна вважати, що елементи мультимножини задовольняють умову .

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

Доведення. Позначимо вектор правих частин нерівностей багатогранника через , а для  – через . Тоді, для еквівалентності цих багатогранників [2] треба довести, що багатогранник з вектором

, (5)

де

, (6)

є невиродженим.

Спираючись на теорему 2, достатньо довести, що перетворення (5) дає багатогранник , який можна розглядати як опуклу оболонку загальної множини переставлень , причому , де елементи визначені так: , оскільки, як видно з (1), праві частини системи обмежень багатогранника переставлень є лінійними комбінаціями елементів мультимножини. Рівність первинних специфікацій означає таке:

; (7)

. (8)

Тут .

Доведемо (7). Розглянемо рівність

(9)

Оскільки і , то , і рівність (9) виконується для будь-яких значень . Доведемо (8) від супротивного.

Нехай

. (10)

Тоді , . Позначимо .

Нехай для визначеності . Тоді з (8) та упорядкованості елементів мультимножини за неспаданням випливає і , а величина . Знайдемо :

(11)

Очевидно, що не може дорівнювати –1. Розглянемо два можливі випадки оцінки значень у виразі (11):

1) якщо , то ;

2) якщо , то .

Отже, жодне із значень не належить інтервалу (0; 1). Тому виконання умови (10) суперечить (6). Теорему доведено.

2. Розв’язування лінійних умовних задач евклідової комбінаторної оптимізації на переставленнях

Розглянемо розв’язування лінійних умовних евклідових комбінаторних задач оптимізації на множинах, що збігаються з множинами вершин своїх опуклих оболонок, на основі поєднання ідей відтинання [3-4] та перебору [5].

У разі моделювання та розв’язування багатьох задач в економіці та інших галузях виробництва виникає потреба розв’язувати лінійні умовні комбінаторні задачі евклідової комбінаторної оптимізації [3], тобто задачі вигляду

, (12)

(13)

за умови

(14)

і додаткових обмежень

, i, (15)

де E – евклідова комбінаторна множина, – множина перших k натуральних чисел,  – натуральні константи (),  – задані дійсні числа .

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

Прикладом такої задачі може бути задача кольорового упакування прямокутників з урахуванням похибок початкових даних на множині поліпереставлень [6]. Розв’язування таких задач за достатньо великої кількості змінних є трудомістким. Перебір допустимих розв’язків великий, на це не вистачає ресурсів ЕОМ. З іншого боку, метод відтинання в евклідовій комбінаторній оптимізації на проміжних кроках дає розв’язки релаксованої задачі, що ще не є допустимими для задачі вихідної. Збіжність значень цільової функції в релаксованій задачі та на допустимому розв’язку в переборному методі доводить оптимальність цього методу.

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

Нехай ^ E – множина переставлень. Зазначимо, що опукла оболонка множини E – загальний переставний багатогранник П=convE. Система лінійних обмежень багатогранника відома (див. наприклад [7]).

Під час застосування методу гілок та меж до задачі (12-15) маємо при кожному проходженні дерева розв’язків деяку точку, що належить множині вершин переставного багатогранника, однак не знаємо, чи є ця точка оптимальною. Водночас у разі застосування методу відсікання [3, 4] до задачі (12-15) маємо на кожній ітерації оптимальне значення цільової функції в точці, що не належить множині вершин переставного багатогранника. Якщо за одночасного розв’язування задачі (12-15) обома методами на якійсь ітерації виявиться, що значення цільових функцій однакові, то це означає, що оптимальний розв’язок у вершині переставного багатогранника, яка знайдена під час перебору.

Зробимо релаксацію задачі (12-15), замінивши (14) на умову П. Нехай задача в канонічному вигляді. Знайти

; (16)

; (17)

за умов

П (18)

, i. (19)

Розглянемо схему алгоритму.

Перша задача лінійного програмування (ЗЛП), яку розглядають, це задача (16-19).

Крок 1. Симплекс-методом розв’язуємо ЗЛП. (Практично це роблять із застосуванням методу послідовного приєднання обмежень [7] та модифікованого чи двоїстого симплекс–методу). Якщо задача нерозв’язна, то нерозв’язна й вихідна. Зупинка алгоритму. Інакше знаходимо розв’язок, який позначимо . Перехід на крок 2.

Крок 2. За точкою формуємо . Перевіряємо умову (14): . Якщо умова (14) виконується для , то задача (12-15) розв’язана. Зупинка алгоритму. Інакше йдемо на крок 3.

Крок 3. Переборним методом (наприклад методом гілок та меж) знаходимо допустимий розв’язок задачі (12-15) . Порівнюємо значення цільової функції зі значенням . Якщо значення однакові, то задача (12-15) розв’язана. Розв’язком є ; зупинка алгоритму. Інакше перехід на крок 4.

Крок 4. Додаємо до ЗЛП сформовану нерівність – відтинання [3-4], що виконано через суміжні з вершини допустимої області задачі (16-19). Перехід на крок 1.

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

ЛІТЕРАТУРА

  1. Ємець О.О., Колєчкіна Л.М., Недобачій С.І. Дослідження областей визначення задач евклідової комбінаторної оптимізації на переставних множинах. Полтава, 1999.

  2. Емеличев В.А., Ковалев М.М., Кравцов М.К. Багатогранники, графы, оптимизация. М.: Наука, 1981.

  3. Ємець О.О., Ємець Є.М. Відсікання в лінійних частково комбінаторних задачах евклідової комбінаторної оптимізації// Доп. НАН України. 2000. №9. С.105-109.

  4. Емец О.А., Емец Е.М. Отсечения в линейных частично комбинаторных задачах оптимизации на перестановках // Экономика и математические методы. 2001. Т.37, №1. С.118-121.

  5. Корбут А.А., Сигал И.Х., Финкельштейн Ю.Ю. Метод ветвей и границ (обзор теории, алгоритмов, программ, приложений) // Math. Operationforsh. Statist., Ser, Optimization. 1977. Bd. 8, N 2. S.253-280.

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

  7. Стоян Ю.Г., Ємець О.О. Теорія і методи евклідової комбінаторної оптимізації. К.: ІСДО, 1993.




O. Yemets, N. Romanova, O. Roskladka

State Technical University of Poltava


Necessary and sufficient conditions of equivalence of permutation's polyhedrons with the identical primary specification of multisets in the given work are considered . It enables to classify general polyhedrons of permutations with the purpose of further study of their combinatorial properties. The method of a solution of the linear conditional task of optimization on permutations , in which the solutions turn out by some search method, and the optimality is checked by a method of cuts is considered.

Keywords: polynomial method, parametric optimization, combinatorial sets

Стаття надійшла до редколегії дд.мм.рррр

Прийнята до друку

Схожі:

Про властивості деяких задач евклідової комбінаторної оптимізації на переставленнях та методи їх розв’язування iconДо питання про нелінійну та параметричну оптимізацію на комбінаторних множинах
Наведено метод відшукання кількості різних розв’язків задачі, дано верхню оцінку цього числа. Розглянуто клас нелінійних задач, до...
Про властивості деяких задач евклідової комбінаторної оптимізації на переставленнях та методи їх розв’язування iconМетодичні вказівки для проведення практичних занять та виконання курсової роботи з дисципліни «математичні методи розв’язування задач надійності вк систем»
«Математичні методи розв’язування задач надійності вк систем» (для студентів 2 курсу денної І заочної форм навчання напряму підготовки...
Про властивості деяких задач евклідової комбінаторної оптимізації на переставленнях та методи їх розв’язування iconІнформації про нього та типу обмежень вибрати метод, побудувати алгоритм та скласти програму розв'язку задачі оптимізації; застосувати середовище matlab для математичного моделювання та розв'язку задач оптимізації об'єктів та систем керування
Вища математика, Теорія автоматичного керування, Числові методи І моделювання на еом
Про властивості деяких задач евклідової комбінаторної оптимізації на переставленнях та методи їх розв’язування iconМіжнародний чемпіонат з розв’язування логічних математичних задач
Міністерства освіти і науки України (у відповідності до наказу Міністерства освіти і науки України від 23. 02. 2009 №159 «Про участь...
Про властивості деяких задач евклідової комбінаторної оптимізації на переставленнях та методи їх розв’язування iconМіжнародний чемпіонат з розв’язування логічних математичних задач
Міністерства освіти і науки України (у відповідності до наказу Міністерства освіти і науки України від 23. 02. 2009 №159 «Про участь...
Про властивості деяких задач евклідової комбінаторної оптимізації на переставленнях та методи їх розв’язування iconОписи модулів назва модуля
Внаслідок вивчення дисципліни студенти повинні знати методи розробки алгоритмів I програм розв’язку прикладних задач, а також методи...
Про властивості деяких задач евклідової комбінаторної оптимізації на переставленнях та методи їх розв’язування iconМіністерство освіти і науки України Чернівецький національний університет імені Юрія Федьковича
...
Про властивості деяких задач евклідової комбінаторної оптимізації на переставленнях та методи їх розв’язування iconФормат опису модуля назва модуля: Системи штучного інтелекту Код модуля
Засвоїти: методи набуття знань, формування моделей знань І побудови баз знань; знати методи І алгоритми розв'язування задач, діагностики,...
Про властивості деяких задач евклідової комбінаторної оптимізації на переставленнях та методи їх розв’язування iconОпис модуля назва модуля
У результаті вивчення модуля студент повинен знати методи розробки алгоритмів I програм розв’язку прикладних задач, а також методи...
Про властивості деяких задач евклідової комбінаторної оптимізації на переставленнях та методи їх розв’язування iconНаближене розв’язування двовимірних рівнянь ВінераХопфа
Побудовано та обґрунтувано методи наближеного розв’язування рівнянь Вінера-Хопфа на четвертину площини
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи