Удаление неравенств в динамическом методе двойного описания

Общеизвестно, что каждый полиэдр в многомерном пространстве может быть представлен любым из двух эквивалентных способов: как множество решений некоторой системы линейных неравенств (так называемое фасетное описание) и как сумма выпуклой и конической оболочек некоторых систем векторов (вершинное описание). Переход от одного описания к другому и обратно является одной из ключевых проблем теории систем линейных неравенств. Теоретический интерес к данной проблеме подкрепляется наличием приложений, в которых описанная выше проблема появляется. Этими приложениями являются : биологическая кинетика, анализ, оптимизация и верификация компьютерных программ. Также очень часто используется в задачах линейного программирования при поиске множества всех решений. Стоит отметить эквивалентность задач перехода от первого описания ко второму и наоборот. Основываясь на этом, сосредоточимся на одной из них. В работе будет рассматриваться переход от описания полиэдра как множества решений к вершинному описанию. Также заметим, что начальный набор ограничений может быть уточнён, например, новые ограничения могут как удаляться из описания, так и добавляться в него. Проблема добавления ограничений на данный момент изучена более глубоко, чем эквивалентная ей проблема устранения неравенств. Постановка задачи. Темой данной исследовательской работы является анализ следующей задачи: с учетом вершинного и фазового представлений выпуклого многогранника вычислить вершинное представление многогранника, определяемого подсистемой неравенства исходного многогранника. Целью является реализация алгоритма двойного описания многогранника с замечанием об удалении ребер из описания. Задачи исследования: - изучение метода двойного описания - изучение инкрементного метода двойного описания - подготовка к реализации удаления неравенств в методе двойного описания -реализация, численный эксперимент, сравнение с существующими алгоритмами