SOLVING OF THE LINEAR OPTIMIZATION PROBLEM ON POLYARRANGEMENTS WITH THE CONSTANT SUM OF COORDINATES IN THE ARRANGEMENTS - Iemets, О. О.; Yemets` , O. O. (Computer Science and Applied Mathematics, 2018)
One of the optimization problems is considered in the article, namely, the linear conditionally complete combinatorial problem of Euclidean optimization on polyarrangements, in which the sum of coordinates in arrangements is constant. This problem is to minimize the linear objective function for linear constraints, which express the condition that those coordinates of the admissible point, which are included in a single arrangement of polyarrangements, in the sum equal to a constant, which can be considered as one. The combinatorial constraint of this problem is that the admissible point is a polyarrangement. To solve the problem, the branch and bound method is proposed and substantiated. The rules of the branching of admissible subsets, the estimation of subsets and the cutting are proposed for the method. A rule for estimating admissible sets and a theorem that establishes the estimate of an admissible subset are proposed in the work. The principle of estimation, which is realized in the theorem, consists of the fact that the sum of two items is taken as an estimate, one of items is the sum of those elements of the objective function, that correspond to those defined in the admissible estimable set, and the second is the minimum on the combinatorial set of polyarrangement, which is formed in a special way, of linear objective function, which is the part of the original objective function, which includes variables that are not defined in an admissible set that is evaluated. Some properties of estimations are proved, namely: 1) for the introduced method of estimation and branching of admissible subsets, the estimation of the next subset on the branch of the tree branch from the root to the leaf will be not less than the estimate of the previous subset; 2) at one level of depth from the root of the branch tree, the estimation of admissible subsets, which are subsets of one and the same admissible subset, when moving from the upper branches to the lower branches of the subset, located below subsets have higher estimates. The article presents an illustrative example that improves perception of the material.