РОЗДІЛ 2
ЕВКЛІДОВА КОМБІНАТОРНА МНОЖИНА ПОЛІРОЗМІЩЕНЬ
ТА ЇЇ ОПУКЛА ОБОЛОНКА
В математичних моделях у вигляді задач оптимізації на комбінаторних множинах та
при розробці методів їх розв'язування важливими виявляються властивості
комбінаторних множин, що є допустимими в цих задачах, а також їх опуклих
оболонок. Ця проблематика достатньо добре досліджена для множин розміщень,
сполучень, переставлень та поліпереставлень [52, 111]. В цьому розділі
викладені результати досліджень комбінаторної множини полірозміщень, яка дає
можливість розглядати одержані раніше результати з більш загальних позицій.
2.1 Постановка задачі
Розглянемо множину полірозміщень.
Нехай - мультимножина пронумерованих дійсних чисел з основою , первинною
специфікацією , , . Розглянемо упорядковане розбиття множини на s множин , що
задовольняє умовам , , а також упорядковане розбиття числа k на s доданків , що
задовольняють умовам , де . Очевидно, що . Позначимо .
Нехай H - множина всіх k-вибірок з множини вигляду
де - довільна -вибірка з множини . Множину
називають множиною полірозміщень з повтореннями.
Після занурення [111] множини в (тобто розглядаючи її точки як точки з ) її
образ позначають і називають евклідовою комбінаторною множиною полірозміщень з
повтореннями або загальною множиною полірозміщень.
Розглянемо опуклу оболонку загальної множини полірозміщень , позначимо її .
Назвемо загальним многогранником полірозміщень. Поставимо задачу: дослідити
властивості та .
2.2. Доведення допоміжних тверджень
Нехай -елементна мультимножина (), що утворена елементами з номерами з множини
, . Тобто . Упорядкуємо, не порушуючи загальності подальших міркувань,
компоненти мультимножини :
. (2.1)
Покладемо
. (2.2)
Розглянемо многогранник П, що визначається сукупністю всіх розв'язків системи
. (2.3)
Якщо зафіксуємо , то з системи (2.3) одержимо систему
, (2.4)
яка, очевидно, описує многогранник розміщень [111, с.51] , де - кількість
елементів основи мультимножини
Лема 2.1. Многогранник П є добутком многогранників , тобто
. (2.5)
Доведення. За означенням добутку многогранників
, (2.6)
де . Очевидно, що
, (2.7)
Але права частина рівності (2.6) означає, що довільне x задовольняє систему
(2.4), тобто x є розв'язком системи (2.3), тобто . Це й означає виконання
рівності (2.5), яку і треба було довести.
Зауваження 2.1. Точку з (2.7) можна ще описати як , де у вигляді (2.2), та .
Лема 2.2. Точка , де визначається співвідношенням (2.7), - вершина
многогранника П тоді і тільки тоді, коли компоненти вектора є переставленням
чисел
де
. (2.8)
Доведення. Як відомо (див., наприклад, лему 1.1 (п.3)) вершини многогранника
утворюють множину , де є -вимірна грань многогранника
та . Отже . Таким чином, якщо - вершина многогранника П, то - вершина
многогранника , і навпаки. (Оскільки за лемою 1.1 (п.2)
).
А за теоремою 1.2 (див. також теорему 2 з [109] або теорему 3.3 з [52]) точка є
вершиною многогранника для фіксованого тоді і тільки тоді, коли її координати є
переставленням чисел
де . Що і доводить лему.
Лема 2.3. Якщо , то .
Доведення. За означенням опуклої оболонки (див., наприклад, [132, с.24]) є
перерізом всіх опуклих множин , що містять , тобто .
Оскільки , то за означенням перерізу множин виконується співвідношення , в тому
числі і для , при якому , тобто . Тобто , а значить
А це за означенням опуклої оболонки і дає
Що і треба було довести.
2.3. Опис опуклої оболонки евклідової множини полірозміщень
Теорема 2.4. Многогранник збігається з многогранником П.
Доведення. Спершу доведемо, що вершини П належать множині .
Згідно з лемою 2.2 точка тоді і тільки тоді, коли компоненти є переставленням
чисел
і виконується умова (2.8). Але за означенням множини точки x належать .
Покажемо, що довільні точки множини (а не тільки ті, що є вершинами
многогранника П) належать П. Нехай , , де задовольняє умову (2.7). Розглянемо з
x , тобто елементи . За означенням точка - це - вибірка з мультимножини , , для
елементів якої виконується умова (2.1). Тому виконуються нерівності
. (2.9)
Співвідношення (2.9) - це не що інше, як підставлення координат довільної точки
в нерівності (2.3), які описують многогранник П. Отже, оскільки (2.3) в
довільній точці загальної множини полірозміщень виконуються, одержали, що.
Далі скористаємося лемою 2.3, прийнявши: , - підмножина множини , така, що , .
Тоді дійсно,
Многогранник П, що визначається системою (2.3), збігається з опуклою оболонкою
своїх вершин: (дивись, наприклад, теорему 2.2 [22, с.19]). Доведено вище, що .
Отже, згідно з лемою 2.3, , що за означенням загального многогранника
полірозміщень і означає: . Таким чином, теорема доведена.
З теореми 2.4 та означення многогранника П одержуємо таке твердження.
Теорема 2.5. Загальний многогранник полірозміщень описується системою (2.3).
2.4. Властивості многогранника полірозміщень
Як наслідки з теореми 2.4 та означення многогранника П леми 2.2 та леми 2.1
відповідно маємо наступні твердження.
Теорема 2.6. (Критерій вершини многогранника .) Точка , де визначається
співвідношенням (2.7), є вершиною загального многогранника полірозміщень тоді і
тільки тоді, коли компоненти вектора є переставленням чисел
при виконанні умови (2.8).
Теорема 2.7. Загальний многогранник полірозміщень є добутком многогранників
розміщень .
. (2.10)
Наслідок 2.7.1. Якщо , то загальна множина полірозмі
- Київ+380960830922