Представление суммы Минковского для двух полиэдров системой линейных неравенств
Автор: Панюков Анатолий Васильевич
Рубрика: Математическое моделирование
Статья в выпуске: 40 (299), 2012 года.
Бесплатный доступ
Любой выпуклый полиэдр представим как множество решений некоторой системы линейных неравенств. Алгебраическая сумма по Минковскому выпуклых полиэдров X, Y С R n также является выпуклым полиэдром, и, следовательно, также представим как множество решений некоторой системы линейных неравенств. В статье предложен полиномиальный алгоритм решения указанной задачи, основанный на формировании ряда избыточных ограничений в представлении слагаемых и их трансляции в результирующее представление. Предложен эффективный способ использования параллельных и распределенных вычислений для реализации алгоритма.
Полиэдр, сумма множеств по минковскому, система линейных неравенств, линейное программирование
Короткий адрес: https://sciup.org/147159157
IDR: 147159157
Список литературы Представление суммы Минковского для двух полиэдров системой линейных неравенств
- 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.
