Представление суммы минковского для двух полиэдров системой линейных неравенств

Любой выпуклый полиэдр представим как множество решений некоторой системы линейных неравенств. Алгебраическая сумма по Минковскому выпуклых полиэдров $X,Ysubset mathbb{mathbb{R}}^n$ также является выпуклым полиэдром, и, следовательно, также представим как множество решений некоторой системы линейных неравенств. В статье предложен полиномиальный алгоритм решения указанной задачи, основанный на формировании ряда избыточных ограничений в представлении слагаемых и их трансляции в результирующее представление. Предложен эффективный способ использования параллельных и распределенных вычислений для реализации алгоритма.

Ключевые слова

полиэдр, сумма множеств по Минковскому, система линейных неравенств, линейное программирование.

Литература

1. 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.
2. Куржанский, А.Б. Управление и наблюдение в условиях неопределенности / А.Б. Куржанский. - М.: Наука, 1977. - 392 с.
3. Черноусько, Ф.Л. Оценивание фазового состояния динамических систем. Метод эллипсоидов / Ф.Л. Черноусько. - М.: Наука, 1988. - 320 с.
4. Кунцевич, В.М. Синтез оптимальных и адаптивных систем управления: игровой подход / В.М. Кунцевич, М.М. Лычак. - Киев: Наукова думка, 1985. - 245 с.
5. Лычак, М.М. Идентификация и оценивание состояния объектов управления на основе множественного подхода / М.М. Лычак // Проблемы управления и информатики. - 1999. - № 5. - С. 34-41.
6. Ширяев, В.И. Минимаксная фильтрация в реальном времени многошаговых систем / В.И. Ширяев // Проблемы управления и теории информации. - 1991. - № 5. - С. 805-812.
7. Шестаков, А.Л. Динамическое измерение как задача оптимального управления / А.Л. Шестаков, Г.А. Свиридюк, Е.В. Захарова // Обозрение прикл. и пром. математики. - 2009. - Т. 16, №4. - С. 732.
8. Уханов, М.В. Алгоритмы построения информационных множеств для реализации минимаксного фильтра // М.В. Уханов, В.И. Ширяев // Вестн. Юж-Урал гос. ун-та. Серия ' Математика, физика, химия'. - 2002. - Вып. 2, № 3. - С. 19-33.
9. Черникова, Н.Б. Алгоритм для нахождения общей формулы неотрицательных решений системы линейных неравенств / Н.Б. Черникова // Журн. вычисл. математики и мат. физики. - 1965. - Т. 5, № 2. - С. 334-337.
10. Черников С.Н. Линейные неравенства. - М.: Наука, 1968. - 488 с.
11. Уханов, М.В. Алгоритм построения суммы многогранников / М.В. Уханов // Вестн. Юж-Урал гос. ун-та. Серия 'Математика, физика, химия'. - 2001. - Вып. 1, № 7. - С. 39-44.
12. Лукацкий, А.М. Конструктивный алгоритм свертывания систем линейных неравенств высокой размерности / А.М. Лукацкий, Д.В. Шапот // Журн. вычисл. математики и мат. физики. - 2008. - Т. 48, №7. - С. 1167-1180.
13. Панюков, А.В. Применение массивно-параллельных вычислений для решения задач линейного программирования с абсолютной точностью / А.В. Панюков, В.В. Горбик // Автоматика и телемеханика. - 2012. - №2. - C. 73-88.
14. Панюков А.В., Тычинин С.А. Применение дополнений паросочетаниями для решения задачи max tsp // Вестн. Юж-Урал гос. ун-та. Серия 'Математическое моделирование и программирование'. - 2008. - №27 (127), вып. 2. - С. 78-99.
15. Панюков, А.В. Алгоритм дополнения паросочетаниями для ассиметричной задачи коммивояжера / А.В. Панюков, В.А. Пьянков // Математическое и статистическое исследование социально-экономических процессов / под ред. А.В. Панюкова. - Челябинск: Изд-во ЮУрГУ, 2008. - С. 115-122.
16. Бушенков, И.Ф. Алгоритм анализа независимости неравенств в линейной системе / В.А. Бушенков, А.В. Лотов// Журн. вычисл. математики и мат. физики. - 1980. - Т. 20, №3. - С. 562-572.
17. Емеличев, В.А. Многогранники, графы, оптимизация / В.А. Емеличев, М.М. Ковалев, М.К. Кравцов. - М.: Наука, 1981.