О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ

Донизу

О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ Empty О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ

Створювати по Admin на тему Пн Лист 14, 2016 4:46 pm

О. А. Емец, проф., д. ф.-м. н., заведующий кафедрой математического моделирования и социальной информатики; А. О. Емец, доц., к. ф.-м. н., доцент кафедры математического моделирования и социальной информатики
Полтавский университет экономики и торговли

ПОДСЧЕТ ВЕРШИН
В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ

Исследование задач в евклидовой комбинаторной оптимизации проводится в двух аспектах (см., например, [1-10]): исследование допустимых областей и изучение свойств оптимизируемых функций, заданных на комбинаторных множествах [2, 3, 11]. Первый аспект предполагает исследование, в том числе, выпуклой оболочки евклидовых комбинаторных множеств – так называемых комбинаторных многогранников, в частности, общего многогранника размещений [1-6], что объясняется актуальностью исследований, в частности, задач на множестве размещений [2-6, 8-10, 12-14].
Исследования общего многогранника вершин изложены, в частности, в [2, 3, 9, 45], однако не ставилась задача определения количества его вершин. Данная задача решается далее.
Постановка и решение задачи подсчета количества вершин общего многогранника размещений. Используется терминология согласно [3].
Рассмотрим общее множество размещений О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ 08e2c035135f, общий многогранник размещений
О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ 6268653c4033, где мультимножество О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ 6c7b04b478e0; считаем, что О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ 46302cd3b59d  ; основа  G –  это О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ Ef7e745fefc4 , где О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ C403dbf219bb
; первичная спецификация G  обозначена так: О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ 70fc5e3afbdd.
Как известно [2, 3],  О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ 6268653c4033 записывается так: О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ 1ec28bcc8447
Перепишем эту систему в эквивалентном виде:
О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ 85c4c5a5d6b3
Как известно [2, 3], вершиной  О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ 13520efc1f31 является точка, у которой координаты – это такие элементы из  О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ Ffe0e17fc7db; и только они, стоящие в любом порядке в X . Таким образом, одной из вершин является точка  О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ 83af951cc70d, а другие получаются перестановкой этих элементов или выбором другого О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ 3dbe909553f5 , а значит и О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ 6454ed45f8b6 .
Количество  L перестановок из элементов g  можно определить при  О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ A54e4c7d2406 по формуле
О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ Ec7130f575c0, (1)
где параметр О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ D7f94928dd3c определяется так:О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ 581539039285 (2)
а константы  О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ 42fdd20ef87c задаются следующим образом:
О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ 15ec1110ba8a (3)
при  О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ F4f3a5a04b06; параметр  p в (1) определяется так:
О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ D616b58967ff (4)
а константы  О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ 43c7f0d52646 задаются следующим образом:
О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ 30f8d7092768 (5)
О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ 53088adce294.
В случае   О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ 2ac1b8feac7f перестановок из элементов можно определить согласно формуле
О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ C794c752c12e
где параметры  О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ Dd3e9660ef28 определяются в (2)-(5) как и для формулы (1), а О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ 7a8069360bee.
Учтем, что есть повторяющиеся выборки при разных  s (и  r), т. е. случаи, в частности, когда О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ 02a5df2a1f5c .
Если при О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ D085528fa590 ,   имеем О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ A3fdbf50aa53, тогда в первом случае  О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ 2935bff1fb53 . Если О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ 0b12d097a6f2 , выполняются соотношения (2)-(5), а О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ E5bf752c77ba, что при этом  О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ 0ac65e929772, существуют одинаковые выборки. Это может быть и в случае существования   О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ 10761f1546ec. При подсчете вершин надо эти выборки отследить и взять только раз.
О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ 98b29cb6d188
Заключение. Рассмотрен подсчет количества вершин в общем многограннике размещений – выпуклой оболочке множества размещений, образованных из мультимножества, каждый элемент основы которого имеет в мультимножестве свою кратность повторений.
Приведены примеры определения количества вершин общего множества размещений.
Результаты могут быть полезны для разработки методов оптимизации на размещениях. В дальнейшем целесообразно изучить структуру этого многогранника и провести их типизацию, выявив все возможные комбинаторные типы.

Список использованных источников

1. Емеличев В. А. Многогранники, графы, оптимизация / В. А. Емеличев, М. М. Ковалев, М. К. Кравцов. – М.: Наука, 1981. – 344 с.
2. Емец О. А. Евклидовы комбинаторные множества и оптимизация на них. Новое в математическом программировании: учеб. пособие / О. А. Емец. – К.: УМК ВО, 1992. – 92 с. – Режим доступу: http://dspace.uccu.org.ua/handle/ 123456789/489.
3. Стоян Ю. Г. Теорія і методи евклідової комбінаторної оп-тимізації / Ю. Г. Стоян, О. О. Ємець. – К.: Ін-т системн. досліджень освіти, 1993. – 188 с. – Режим доступу: http://dspace.uccu.org.ua/handle/123456789/487.
4. Стоян Ю. Г. Оптимізація на полірозміщеннях: теорія та методи / Ю. Г. Стоян, О. О. Ємець, Є. М. Ємець. – Полтава: РВЦ ПУСКУ, 2005. – 103 с. – Режим доступу: http://dspace.uccu.org.ua/ handle/123456789/376.
5. Ємець О. О. Задачі оптимізації на полікомбінаторних множинах: властивості та розв’язування: Монографія / О. О. Ємець, О. В. Роскладка. – Полтава: РВЦ ПУСКУ, 2006. – 129 с. – Режим доступу: http://dspace.uccu.org.ua/handle/123456789/377.
6. Емец О. А. Комбинаторная оптимизация на размещениях / О. А. Емец, Т. Н. Барболина. – К.: Наук. думка, 2008. – 159 с. – Режим доступу: http://dspace.uccu.org.ua/handle/123456789/473.
7. Емец О. А. Оптимизация на полиперестановках / О. А. Емец, Н. Г. Романова. – К.: Наук. думка, 2010. – 105 с. – Режим доступу: http://dspace.uccu.org.ua/handle/123456789/474.
8. Ємець О. О. Розв’язування задач комбінаторної оптимізації на нечітких множинах: монографія / О. О. Ємець, Ол-ра О. Ємець. – Полтава: ПУЕТ, 2011. – 239 с. – Режим доступу: http://dspace.uccu.org.ua/handle/123456789/352.
9. Емец О. А. Оптимизация дробно-линейных функций на размещениях: монография / О. А. Емец, О. А. Черненко. – К.: Наук. думка, 2011. – 154 с. – Режим доступу: http://dspace.uccu.org.ua/ handle/ 123456789/467.
10. Ємець О. О. Транспортні задачі комбінаторного типу: властивості, розв’язування, узагальнення: монографія / О. О. Ємець, Т.О. Парфьонова. – Полтава: ПУЕТ, 2011. – 174 с. – Режим доступу: http://dspace.uccu.org.ua/handle/ 123456789/353.
11. Ємець О. О. Дискретна математика: Навч. посібник. Вид. 2-ге, допов. / О.О. Ємець, Т.О. Парфьонова. – Полтава: РВВ ПУСКУ, 2009. – 287 с. – Режим доступу: http://dspace.uccu.org.ua/handle/ 123456789/552.
12. Ємець О. О. Моделі евклідової комбінаторної оптимізації: монографія / О. О. Ємець, О. О. Черненко. – Полтава: ПУЕТ, 2011. – 204 с. – Режим доступу: http://dspace.uccu.org.ua/handle/ 123456789/354.
13. Стоян Ю. Г. Множини полірозміщень в комбінаторній оп-тимізації / Ю. Г. Стоян, О. О. Ємець, Є. М. Ємець // Доповіді НАНУ. – 1999. – № 8. – С. 37-41.
14. Emets O. A. Solving Linear Optimization Problems on Arrangements by the Truncation Method / O. A. Emets, T. N. Barbolina // Cybernetics and Systems Analysis – 2003 – V. 39, № 6. – P. 889–896.
15. Ємець О. О. Про кількість елементів в загальних множинах розміщень та полірозміщень / О. О. Ємець, Т. В. Чілікіна // Вісник Черкаського університету. Серія Прикладна математика. Інформатика. – № 18 (351). – 2015. – С. 3-10.

Admin
Admin

Кількість повідомлень : 38
Дата реєстрації : 08.11.2016

Переглянути профіль користувача http://economsugod.ukrainianforum.net

На початок Донизу

О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ Empty Re: О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ

Створювати по kozody6313 на тему Вт Лист 15, 2016 10:23 am

Як би ви оцінили метод цього підрахунку по 10 бальній шкалі?

kozody6313

Кількість повідомлень : 3
Дата реєстрації : 15.11.2016

Переглянути профіль користувача

На початок Донизу

О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ Empty Re: О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ

Створювати по Yemets на тему Ср Лист 16, 2016 7:45 pm

На 10 балів)

Yemets

Кількість повідомлень : 2
Дата реєстрації : 16.11.2016

Переглянути профіль користувача

На початок Донизу

О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ Empty Re: О. А. Емец ПОДСЧЕТ ВЕРШИН В ОБЩЕМ МНОГОГРАННИКЕ РАЗМЕЩЕНИЙ

Створювати по Спонсируемый контент


Спонсируемый контент


На початок Донизу

На початок


 
Права доступу до цього форуму
Ви не можете відповідати на теми у цьому форумі