SIMPLEX FORM OF POLYHEDRON OF COMBINATIONS WITH UNLIMITED REPETITIONS - IemetsО. О.; Yemets` O. O.; Vanzha, S. V. (Computer Science and Applied Mathematics, 2017)
Within combinatorial optimization it is important to study combinatorial sets and their polyhedrons as the basis for the development of combinatorial optimization methods. For a group of such methods one of the stages is the linear relaxation using combinatorial polyhedrons. Karmarkar`s polynomial algorithm should be used for solving received problems, but for this purpose feasible polyhedron must have a so-called simplex form prescribed by Karmarkar`s algorithm at the input. Simplex forms of permutable polyhedrons with reducible and irreducible systems of constraints are known from the literature. In this paper, the simplex form of the convex hull of Euclidean combinatorial set of combinations with unlimited repetitions is derived. The paper consists of four parts. The statement of problem, the definition of combinations with unlimited repetitions (i.e. from 0 to k) every element as ordered k-samples, elements of each are arranged by not descending order are given in the first part. The definition of the set of the combination with unlimited repetitions as the set of all these k-samples and the polyhedron of combinations with unlimited repetitions as the convex hull of the set of the combination with unlimited repetitions are given. The description of this polyhedron in the form of the system of linear inequalities is given. The second part is devoted to the transformation algorithm of feasible area of linear programming problem to polyhedron having the simplex form. The algorithm has five steps. In the first step constraints of linear programming problem are reduced to the so-called canonical form. In the second step the inequality that defines the half-space containing all admissible points of the linear programming problem is recorded. In the third step the system of equations in the canonical form is reduced to a homogeneous system. In the fourth step, the bound of the introduced half-space, by introducing new variables, is transformed into a hyperplane that cuts the unit on coordinate axes. This completes the construction of simplex forms of polyhedron by introducing additional variables that provide the satisfaction of the point having the same coordinates (the center) of simplex obtained conditions of the problem. In the third part this algorithm is applied to the polyhedron of combinations with unlimited repetitions. The fourth part of the article provides the illustrative example.