НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ

ІНСТИТУТ КІБЕРНЕТИКИ ІМ. В. М. ГЛУШКОВА

РОСКЛАДКА ОЛЕНА ВОЛОДИМИРІВНА

УДК 519. 85

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

01.05.01 – теоретичні основи інформатики та кібернетики

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

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

Київ – 2005

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

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

імені Юрія Кондратюка Міністерства освіти і науки України

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

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

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

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

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

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

Турчина Валентина Андріївна,

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

Провідна установа: Київський національний університет імені Тараса Шевченка, факультет кібернетики, кафедра математичних методів еколого-економічних досліджень, м. Київ.

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

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

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

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

Учений секретар

спеціалізованої вченої ради Синявський В. Ф.

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

Актуальність теми. Дослідження задач дискретної оптимізації є передумовою успішного моделювання важливих економічних, природних, соціальних та інших процесів. Велика кількість публікацій, що з’явилася останнім часом і присвячена дискретній оптимізації, свідчить про необхідність та важливість подібних досліджень. В Україні серед вчених, роботи яких присвячені різним аспектам дискретної оптимізації, в першу чергу слід виділити І. В. Сергієнка, Н. З. Шора (Інститут кібернетики НАН України), Ю. Г. Стояна (Інститут проблем машинобудування НАН України), О. О. Ємця (Полтавський університет споживчої кооперації України), О. А. Павлова (Національний технічний університет України (КПІ)), С. В. Яковлєва (Національний університет внутрішніх справ, м. Харків) та інших.

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

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

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

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

Зв’язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалась в період з 1998 по 2004 роки на кафедрі прикладної математики, інформатики та математичного моделювання Полтавського національного технічного університету імені Юрія Кондратюка згідно з індивідуальним планом аспірантської підготовки, держбюджетною темою № 59/03 „Методи відсікання в евклідовій комбінаторній оптимізації та розвиток її теорії” та планами науково-дослідної роботи університету.

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

Об’єктом дослідження є евклідові полікомбінаторні множини.

Предмет дослідження – властивості цих множин та задачі оптимізації на них.

Методами досліджень є методи дискретної та евклідової комбінаторної оптимізації, а також методи комбінаторної теорії многогранників.

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

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

-

-

-

-

-

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

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

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

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

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

[1] – доведення леми про надлишкові обмеження та теореми про незвідність системи обмежень загального многогранника розміщень;

[2] використання методів динамічного програмування для знаходження розв’язку задачі розміщення об’єктів обслуговування і поширення викладеного алгоритму для випадку інших полікомбінаторних множин;

[3] – застосування методу гілок і меж до розв’язування задачі розміщення об’єктів обслуговування, обґрунтування алгоритму та проведення чисельних експериментів.

[4] доведення критерію невиродженості загального переставного многогранника, доведення теореми про еквівалентність опуклих оболонок загальних множин переставлень із спільною первинною специфікацією;

[6] використання властивостей евклідової множини полірозміщень для побудови математичної моделі задачі розміщення об’єктів обслуговування;

[7] – визначення надлишкових обмежень загального многогранника розміщень;

[8] – узагальнення результатів досліджень в області оптимізації на полікомбінаторних множинах.

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

-

-

-

-

-

-

-

д. ф.-м. н., проф. Донець Г.П. (Київ, 2004).

Публікації. Результати дисертаційної роботи опубліковані у 9 наукових працях, з них 5 статей у фахових наукових виданнях, 4 матеріалів і тез конференцій.

Структура та обсяг роботи. Дисертація складається зі вступу, п’яти розділів, висновків, списку використаних джерел із 168 найменувань, 3 додатків. Усього 163 сторінки.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

У другому розділі досліджені фундаментальні властивості переставних і поліпереставних многогранників невиродженість та еквівалентність. Доведені необхідні та достатні умови невиродженості загальних многогранників переставлень та поліпереставлень, а також достатні умови еквівалентності опуклих оболонок евклідових комбінаторних і полікомбінаторних множин одного типу.

Позначимо через кількість повторень елемента основи в мультимножині .

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

- при ;

- при .

Теорема 3. (Наслідок з теореми 2). Нехай і , , де , – кількості повторень елемента в мультимножинах і відповідно, ; . Тоді, якщо – невироджений многогранник в , що описується незвідною системою вигляду (2), і , то також є невиродженим.

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

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

Теорема 6. (Наслідок з теореми 5). Нехай і , , , де , – кількості повторень елемента в мультимножинах і відповідно, ; . Тоді, якщо – невироджений многогранник в , що описується незвідною системою вигляду (4), і , то також є невиродженим.

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

. (8)

Означення 7. Дві евклідові комбінаторні множини і назвемо евклідовими комбінаторними множинами одного типу, якщо системи обмежень вигляду (8), що описують і , мають одну й ту ж матрицю .

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

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

Теорема 9. Якщо в первинній специфікації мультимножини , або , то надлишковими обмеженнями системи (9), (10) многогранника є:

- серед нерівностей підсистеми (9) при - усі нерівності і-спілок, де і задовольняє умовам: , ;

- серед нерівностей підсистеми (10) при - усі нерівності і-спілок, де і таке: , , і тільки вони.

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

має надлишкові обмеження:

при – усі нерівності спілок серед нерівностей (12), а при – усі нерівності спілок серед нерівностей (13).

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

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

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

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

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

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

Нехай E – полікомбінаторна множина з елементів , де , тобто . Тоді математична модель задачі, що розглядається, буде мати вигляд: знайти

(14)

при обмеженнях:

. (15)

Для сформульованої задачі розглянуто методи її розв’язування, які ґрунтуються на використанні властивостей евклідових комбінаторних та полікомбінаторних множин: метод гілок і меж та аналог методу Дальтона–Ллевеліна для розглянутої вище полікомбінаторної множини .

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

Розглянуто застосування методу динамічного програмування для отримання точного розв’язку задачі розміщення об’єктів обслуговування.

Проведено аналіз застосування різних методів з метою оцінки ефективності їх програмної реалізації для отримання розв’язку цієї задачі. Так, метод гілок і меж є найбільш універсальним, однак витрати програмних ресурсів при його реалізації на ЕОМ суттєво залежать від кількості елементів на рівнях галуження. Аналог методу Дальтона?Ллевеліна для задач евклідової комбінаторної оптимізації має найбільш просту постановку. Проте стрімке зростання складності задачі внаслідок зростання числа змінних і обмежень задачі при збільшенні кількості пунктів обслуговування та кількості різних ємностей відділень ставить під сумнів ефективність програмної реалізації даного методу, тому в дисертаційній роботі представлено програми розв’язування задачі розміщення об’єктів обслуговування за іншими алгоритмами.

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

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

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

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

У додатку А розміщені текст модуля програми мовою Object Pascal реалізації в середовищі візуального програмування Delphi методів гілок і меж та динамічного програмування для евклідової полікомбінаторної задачі розміщення об’єктів обслуговування. Детальний вивід результатів роботи програми для деяких тестових прикладів представлений у додатку Б (метод гілок і меж) та у додатку В (метод динамічного програмування).

ВИСНОВКИ

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

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

Методи дослідження полікомбінаторних множин, що використовуються в дисертації, ґрунтуються на розвинутих раніше теорії та методах евклідової комбінаторної оптимізації, а також на інших відомих методах дискретної оптимізації.

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

В дисертації вперше доведені фундаментальні властивості евклідових комбінаторних переставних і поліпереставних многогранників невиродженість та еквівалентність. Доведені необхідні та достатні умови невиродженості опуклих оболонок загальних множин переставлень та поліпереставлень. Обґрунтовані достатні умови еквівалентності опуклих оболонок евклідових комбінаторних і полікомбінаторних множин переставлень.

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

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

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

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

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

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

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

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

1.

2.

3.

4.

5.

6.

7.

8.

9.

АНОТАЦІЯ

Роскладка О. В. Задачі оптимізації на полікомбінаторних множинах: властивості та розв’язування. – Рукопис.

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

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

Побудована нова математична модель задачі розміщення об’єктів обслуговування як задачі евклідової полікомбінаторної оптимізації і отримано її точний розв’язок. Обґрунтовано поширення методу динамічного програмування для спеціального класу задач полікомбінаторної оптимізації.

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

ABSTRACT

Roskladka O. V. The tasks of optimization on polycombinatorial sets: properties and solutions. – Manuscript.

Dissertation for a candidate’s scientific degree of physical and mathematical sciences by speciality 01.05.01 – theoretical bases of informatics and cybernetics. – The V. M. Glushkov Institute of cybernetics of National Academy of Sciences of Ukraine, Kyiv, 2004.

In dissertation the general task of polycombinatorial optimization is posed, are detected and the properties of a general polycombinatorial set, and also it of special cases – Euclidean combinatorial sets of polypermutations and polyarrangements are proved. Are proved necessary and sufficient conditions for fundamental properties of Euclidean combinatorial polyhedrons of permutations and polypermutations – nondegeneracy and equivalence. For convex envelopes of sets of the arrangements and polyarrangements the surplus restrictions in systems of linear inequalities are detected and the systems of nonreducible restrictions are obtained.

The new mathematical model of the task of the arrangement of plants of a upkeep as the tasks of Euclidean polycombinatorial optimization is constructed and the exact solution is obtained it. The distribution of a method of a dynamic programming for a special class of the tasks of polycombinatorial optimization is justified.

Key word: a polycombinatorial set, combinatorial polyhedrons, permutation, arrangement, irreducibility of a system of restrictions, combinatorial optimization, Euclidean combinatorial sets.

АННОТАЦИЯ

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

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

Диссертация посвящена исследованию задач оптимизации на евклидовых поликомбинаторных множествах.

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

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

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

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

Обосновано распространение метода динамического программирования для специального класса задач поликомбинаторной оптимизации с линейной целевой функцией. Свойства исследованного класса задач использованы для получения точного решения задачи размещения объектов обслуживания методом динамического программирования.

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

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

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