PROBLEMS OF CUTTING AND PACKING IN SOLUTION OF APPLIED TASKS

Abstract

One of the problems today is the organization of the controlled evacuation of people from buildings for the required time, calculated on the basis of their space-planning decisions. During the simulation of the movement of people who are approximated by a set of ellipses, the problem arises of their dense placement with different local density, which arises in connection with taking into account the various minimum allowable distances between them. Observance of such distances is caused by taking into account a number of restrictions, among which we can distinguish the movement of people at different speeds, taking into account their maneuverability, comfort, etc. The problems of optimum ellipse packing belong to the class of NP-hard problems. The issues of development of efficient algorithms based on application of local optimization methods, construction of adequate mathematical models based on the analytical description of the ellipse interrelations taking into account their continuous translations and rotations are of vital importance. A generalized model of optimal placement of unoriented ellipses according to a given quality criterion and taking into account different, according to given technological limitations, minimum allowable distances between them, has been built and its features studied. The proposed mathematical model of the problem of optimizing the placement of ellipses in terms of taking into account norms and technological constraints on the parameters of placing objects, which allowed the problem of modeling the movement of people approximated by ellipses to be presented as a geometric design problem. A method for mathematical modeling of the movement of ellipses in a simplyconnected area was developed according to the criterion of the maximum of their aggregate movement, taking into account different, according to given technological limitations, minimum allowable distances between them, which made it possible to expand the class of actual practical problems. Developed algorithmic and software, carried out a computer simulation of the optimal placement of ellipses in rectangular areas for a given quality criterion. This made it possible to solve a wide range of practical problems, which in their statements can be reduced to problems of optimal placement of ellipses, taking into account the minimum allowable distances between them and their continuous broadcasts and rotations.