Algorithm for Adding Inequalities in the Dynamic Double Description Methods

The problem of constructing a dual description of a polyhedron is one of the central in the theory of systems of linear inequalities and has important applications. A dynamic algorithm for constructing a dual description of a polyhedron its implementation in Python are under research. The problem is to perform the operation of adding vertices. The dual description method, also known as the Motzkin – Burger algorithm, is one of the methods for finding a general solution of a system of linear inequalities. Each convex polyhedron can be represented in one of two types: as a set of solutions of a finite system of linear inequalities and as a sum of convex and conical hulls of finite systems of vectors. These methods for specifying polyhedra are called, respectively, a facet and vertex description. The construction of a dual description of a polyhedron consists in the transition from one of these descriptions of the polyhedron to another: the construction of a vertex description of a polyhedron according to a given facet description or the construction of a facet description of a polyhedron according to a given vertex description. Due to duality, these tasks are reduced to each other. The main goal of this paper is to study the dynamic algorithm for dual description of a polyhedron and its implementation.