The Method of Artificial Space Dilation in Problems of Optimal Packing of Geometric Objects
- PDF / 118,940 Bytes
- 7 Pages / 594 x 792 pts Page_size
- 102 Downloads / 164 Views
THE METHOD OF ARTIFICIAL SPACE DILATION IN PROBLEMS OF OPTIMAL PACKING OF GEOMETRIC OBJECTS
S. V. Yakovlev
UDC 519.85
Abstract. The problem of optimal packing of geometric objects with specified shape and physical-metric parameters is considered. The combinatorial structure of the problem is defined. An equivalent problem is formulated based on the artificial expansion of space dimension with physical-metric parameters being independent variables. The proposed approach is illustrated by the solution of balanced circular packing problem. Keywords: optimal packing problem, combinatorial set, balanced packing. INTRODUCTION Problems of optimal packing of geometrical objects generate permanent interest of contributors [1–9]. An important research trend is specification and formalization of special classes of problems for which it is possible to use both new efficient solution techniques and classical mathematical programming methods to solve problems in rather general statement. Creation of Stoyan’s F-functions theory [10, 11] was an impulse for the development of this direction. Formalization of F-functions for various classes of objects considerably expanded the application domain of this tool for description of conditions of mutual nonintersection of objects and their arrangement inside the domain. In the paper, we propose a new insight in formalization and solution techniques for packing problems as mathematical programming problems by specifying their combinatorial structure. We propose an approach to constructing an equivalent mathematical model of the problem, based on artificial expansion of the dimension of space of variables in the original statement. PROBLEM STATEMENT Consider the problem of packing geometrical objects in the following statement. Given the objects S 0 , S 1 , ..., S n of fixed form, each of which in the corresponding space is characterized by packing parameters p i = ( p1i , p2i .., pai ) and physical-metric parameters w i = ( w1i , w2i , ..., w bi ) , i Î{0} È J n , J n = {1, 2, ..., n}, i Î{0} È J n . Let us divide physical-metric parameters into groups of physical u i = ( u1i , u2i , ..., u bi ) and metric r i = ( r1i , r2i , ..., rbi ) parameters, i.e., 1 2
w i = ( u i , r i ) , i Î{0} È J n , b = b 1 + b 2 . Packing parameters describe position of object in the space, and physical-metric parameters specify linear dimensions of the object, its mass, etc. National Aerospace University “Kharkiv Aviation Institute,” Kharkiv, Ukraine, [email protected]. Translated from Kibernetika i Sistemnyi Analiz, No. 5, September–October, 2017, pp. 82–89. Original article submitted April 10, 2017. 1060-0396/17/5305-0725 ©2017 Springer Science+Business Media New York
725
We will call object S 0 packing domain. Let us fix its position in the space by assuming p 0 = (0, 0, ..., 0) . We will call objects S i with packing parameters p i the objects being packed and denote them by S i ( p i ) , i Î J n . We will consider that physical-metric parameters of the objects being packed take fixed values, i.e.,
Data Loading...
