Baranov O. Mathematical models and methods of combinatorial optimization on classes of permutations sets in geometric design

Research object - the process of placing geometrical object in an identified area. Research target is working out new mathematical models and methods and improving the existing ones for solving the combinatorial and optimization problems of placing geometrical objects on the classes of permutations sets by means of decreasing redundancy in the descriptions of the acceptable ranges of solutions and taking into account the properties of the objective functions of the problems belonging to the given class. Research methods: the methods of multidimensional geometry and linear algebra - for investigation the properties of the classes of permutation sets reflected into the Euclidean space; convex analysis - for constructing the estimates of the minimum convex extensions of the functions, given on the classes of permutation sets; optimization methods - for optimization problems of geometric design solving; methods of geometric design for mathematical models of the geometrical objects placement problems construction. Research apparatus: personal computer. Theoretical and practical results - the developed mathematical models and the worked out methods and algorithms may serve as a ground for constructing systems of solving of combinatorial optimization problems in geometric design in various domains such as cutting lay-out designing in metal-working and textile branches of industry, in the process of loading freight for transportation, containers warehousing, equipment layout, etc. Scientific novelty - for the first time the method of optimization of linear functions with linear restrictions on combinatorial sets, in the basis of which lie the search of the fundamental system of solutions of the system of linear restrictions-inequalities in combination with the scheme of random search and additional extremal problems on combinatorial sets solving, is developed. The estimates of the solutions got with the help of the developed method are formed. This allows solving the problems of combinatorial optimization with linear goal functions and linear restrictions on classes of combinatorial sets; the mathematical model of two-criteria package problem of n-dimensional parallelepipeds in an n-dimensional parallelepiped is built. An approach to solving the problem built on the basis of successive criterion optimization and bounds and branches method is worked out. This allows taking into account the position of the system weight center while solving packing problems of the n-dimensional parallelepipeds in an n-dimensional parallelepiped. Further developed: the method of investigation of extremal properties of convex and strongly convex functions, given on discrete sets. The estimates of the minimum of convex and strongly convex functions with linear restrictions on combinatorial permutation sets are proposed. The estimates and sufficient conditions of the minimum of convex and strongly convex functions on the new classes of permutation sets, namely tuple permutation sets and permutation compositions are formed. This allows developing methods of bounds and branched type and estimations of the approximate solutions for the optimization problems on the mentioned classes of sets; the method of optimization of the estimates of the minimum of convex and strongly convex functions on the classes on combinatorial permutation sets based on the methods on nondifferentiable optimization. This allows building more efficient estimates that are used in the bounds and brunches methods; mathematical model of the problem of placing n-dimensional parallelepipeds in an n-dimensional parallelepiped which allows taking into account the orthogonal orientation of n-dimensional parallelepipeds with the help of their linear dimensions permutation were further developed. This allows receiving more efficient solutions of the packing problems. The research results were used for solving the problems of rational blanks placement on the metal sheets at "Kharkovmetall-2" (the certificate of implementation from 12.01.2010). The developed complex of mathematical models and software was used for automation of the process of placing rectangular stickers on the sheets of material at the stage of printed matter preparation at "Ranok" Publishing House (the certificate of implementation from 01.03.2010) The results of the research are implemented into the learning process of Kharkiv National University of Radio Electronics at the system engineering department (the certificate of implementation from 30.09.2010). The worked out mathematical models, methods, and software may be used at the enterprises, the activity of which is connected with various objects warehousing and transportation, material cutting, in printing industry, etc.