Development the methods of optimum placement undirected planar objects with piecewise non-linear boundaries in the multiply area

Abstract

In this paper the statement of the problem is formulated and the mathematical model of optimization the placement of the undirected planar geometrical objects with piecewise non-linear boundaries in the multiply area is developed. It is shown the geometrical interpretation and derived the estimate of the number of restrictions in the model. On the basis of a mathematical model for finding the global extremum of the objective function was proposed modified method of branches and boundaries. It is also shown the solutions tree that takes into account the problems of optimal placement of undirected planar geometrical object with piecewise non-linear boundaries in the multiply area, and received the complexity of this method. For locally optimal solutions of the problem modified simulated annealing method has been developed. Thus the analytical expressions for the function of energy system were received, the function, that describes the decrease of temperature over time, function that forms a new state of system. The method of formation the new state of the system was investigated in more detail, which is based on a random permutation of numbers the pair of the objects, it is also based on a consistent placement of objects according to reshuffle their numbers and determining the probability of transition to a new state. It is shown the example of determining permissible points of placement the local coordinate system of the specific geometrical object. The conclusion is that to solve practical optimization problems of placement of the undirected planar geometrical objects with piecewise non-linear boundaries in the multiply area should be used the modified simulated annealing method.