О динамической задаче построения остова полиэдрального конуса

Сергей Иванович Бастраков; Николай Юрьевич Золотых

doi:10.14529/mmph170101

Авторы

Сергей Иванович Бастраков Нижегородский государственный университет, Нижний Новгород
Николай Юрьевич Золотых Нижегородский государственный университет, Нижний Новгород

DOI:

https://doi.org/10.14529/mmph170101

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

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

Аннотация

Рассматривается динамическая задача построения остова полиэдрального конуса. Задача состоит в последовательном выполнении операций добавления или удаления неравенств из фасетного описания полиэдрального конуса с соответствующим перестроением остова. Обсуждается возможность применения метода двойного описания для выполнения обеих операций, приводятся оценки трудоемкости. Для операции удаления неравенства анализируется зависимость размера выхода от размера входа.