Представление суммы Минковского для двух полиэдров системой линейных неравенств
Автор: Панюков Анатолий Васильевич
Рубрика: Математическое моделирование
Статья в выпуске: 40 (299), 2012 года.
Бесплатный доступ
Любой выпуклый полиэдр представим как множество решений некоторой системы линейных неравенств. Алгебраическая сумма по Минковскому выпуклых полиэдров X, Y С R n также является выпуклым полиэдром, и, следовательно, также представим как множество решений некоторой системы линейных неравенств. В статье предложен полиномиальный алгоритм решения указанной задачи, основанный на формировании ряда избыточных ограничений в представлении слагаемых и их трансляции в результирующее представление. Предложен эффективный способ использования параллельных и распределенных вычислений для реализации алгоритма.
Полиэдр, сумма множеств по минковскому, система линейных неравенств, линейное программирование
Короткий адрес: https://sciup.org/147159157
IDR: 147159157 | УДК: 513.71
The linear inequalities set representation of Minkowski's sum for two polyhedrons
A convex polyhedron is represented as a set of the linear inequalities solutions. Minkowski’s sum of two convex polyhedrons X, Y С R n is polyhedron as well is represented as a set of the linear inequalities solutions. Polynomial algorithm of solving this problem based of forming number of extra inequalities in the summands representation and them translation to resultant representation is presented in the paper. Usage of parallel and distributed computation for effective algorithm Implementation is suggested.
Список литературы Представление суммы Минковского для двух полиэдров системой линейных неравенств
- Schweppe, F.C. Recursive state estimalion: unknown but bounded errors and systems inputs/F.C. Schweppe//IEEE Tram. Autom. Control. -1968. -V. 13, № 1. -P. 22-28.
- Куржанский, А.Б. Управление и наблюдение в условиях неопределенности/А.Б. Куржанский. -М.: Наука, 1977. -392 с.
- Черноусько, Ф.Л. Оценивание фазового состояния динамических систем. Метод эллипсоидов/Ф.Л. Черноусько. -М.: Наука, 1988. -320 с.
- Кунцевич, В.М. Синтез оптимальных и адаптивных систем управления: игровой подход/В.М. Кунцевич, М.М. Лычак. -Киев: Наукова думка, 1985. -245 с.
- Лычак, М.М. Идентификация и оценивание состояния объектов управления на основе множественного подхода/М.М. Лычак//Проблемы управления и информатики. -1999. -№ 5. -С. 34-41.
- Ширяев, В.И. Минимаксная фильтрация в реальном времени многошаговых систем/В.И. Ширяев//Проблемы управления и теории информации. -1991. -№ 5. -С. 805-812.
- Шестаков, А.Л. Динамическое измерение как задача оптимального управления/А.Л. Шестаков, Г.А. Свиридюк, Е.В. Захарова//Обозрение прикл. и пром. математики. -2009. -Т. 16, №4. -С. 732.
- Уханов, М.В. Алгоритмы построения информационных множеств для реализации минимаксного фильтра/М.В. Уханов, В.И. Ширяев//Вестн. Юж-Урал гос. ун-та. Серия «Математика, физика, химия». -2002. -Вып. 2, № 3. -С. 19-33.
- Черникова, Н.Б. Алгоритм для нахождения общей формулы неотрицательных решений системы линейных неравенств/Н.Б. Черникова//Журн. вычисл. математики и мат. физики. -1965. -Т. 5, № 2. -С. 334-337.
- Черников С.Н. Линейные неравенства. -М.: Наука, 1968. -488 с.
- Уханов, М.В. Алгоритм построения суммы многогранников/М.В. Уханов//Вестн. Юж-Урал гос. ун-та. Серия «Математика, физика, химия». -2001. -Вып. 1, № 7. -С. 39-44.
- Лукацкий, А.М. Конструктивный алгоритм свертывания систем линейных неравенств высокой размерности/А.М. Лукацкий, Д.В. Шапот//Журн. вычисл. математики и мат. физики. -2008. -Т. 48, №7. -С. 1167-1180.
- Панюков, А.В. Применение массивно-параллельных вычислений для решения задач линейного программирования с абсолютной точностью/А.В. Панюков, В.В. Горбик//Автоматика и телемеханика. -2012. -№2. -C. 73-88.
- Панюков А.В., Тычинин С.А. Применение дополнений паросочетаниями для решения задачи max tsp//Вестн. Юж-Урал гос. ун-та. Серия «Математическое моделирование и программированием -2008. -№27 (127), вып. 2. -С. 78-99.
- Панюков, А.В. Алгоритм дополнения паросочетаниями для ассиметричной задачи коммивояжера/А.В. Панюков, В.А. Пьянков//Математическое и статистическое исследование социально-экономических процессов/под ред. А.В. Панюкова. -Челябинск: Изд-во ЮУрГУ, 2008. -С. 115-122.
- Бушенков, И.Ф. Алгоритм анализа независимости неравенств в линейной системе/В.А. Бушенков, А.В. Лотов//Журн. вычисл. математики и мат. физики. -1980. -Т. 20, №3. -С. 562-572.
- Емеличев, В.А. Многогранники, графы, оптимизация/В.А. Емеличев, М.М. Ковалев, М.К. Кравцов. -М.: Наука, 1981.
