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

Задача построения двойственного описания полиэдра является одной из центральных в теории систем линейных неравенств и имеет важные приложения. Рассматривается динамический алгоритм построения двойственного описания полиэдра. Его реализация на языке Python. Задача состоит в выполнении операции добавления вершин. Метод двойственного описания, известный также как алгоритм Моцкина–Бургера, является одним из методов нахождения общего решения системы линейных неравенств. Каждый выпуклый полиэдр может быть представлен в одном из двух видов: как множество решений конечной системы линейных неравенств и как сумма выпуклой и конической оболочек конечных систем векторов. Данные способы задания полиэдра называются, соответственно, фасетным и вершинным описанием. Построение двойственного описания полиэдра заключается в переходе от одного из указанных описаний полиэдра к другому: построение вершинного описания полиэдра по заданному фасетному описанию или построение фасетного описания полиэдра по заданному вершинному описанию. В силу двойственности эти задачи сводятся друг к другу.