Моделі та методи розв'язування векторних задач дискретної оптимізації на комбінаторних конфігураціях - Двірна, О. А. (ХНУРЕ, 2019)
Дисертацію присвячено актуальному завданню розробки методів розв’язування векторних задач оптимізації на комбінаторних конфігураціях. Актуальним є підхід до розв’язування комбінаторних задач з використанням теорії графів, що є підґрунтям для пошуку нових методів розв’язування та удосконалення існуючих. У роботі розглядається векторна задача оптимізації на евклідових комбінаторних конфігураціях. Для її розв’язування запропоновано методи з використанням графів комбінаторних конфігурацій. Означено та досліджено властивості грід-графів і структурного графа е-конфігурацій. Одержані результати дозволили розробити нові методи розв’язування векторних задач на комбінаторних конфігураціях. Розроблено координатний та горизонтальний методи розв’язування векторних оптимізаційних задач. Побудовані моделі прикладних задач, що є векторними задачами на комбінаторних конфігураціях, які свідчать про необхідність подальшого розвитку векторної оптимізації на комбінаторних конфігураціях. The dissertation is devoted to the actual problem of developing methods for solving vector problems of discrete optimization on combinatorial configurations. A number of practical tasks in the fields of economics, management, planning, designing of complex systems include the search for an extreme value of the magnitude and value of the variables in which it is achieved, which can be presented as models of vector problems of combinatorial optimization, since many applications have a multicriterial condition. There is a problem of combining extreme problems in combinatorial configurations with vector problems. For each separate class of tasks, scientists have carried out fundamental research, but in aggregate, the above problem is complicated and poorly investigated. An approach to solving combinatorial problems using the graph theory is grounded, which is the basis for finding methods for solving and improving existing ones. The properties of combinatorial configurations in connection with graph theory are studied. New definitions and theorems concerning the connection of combinatorial configurations with the theory of graphs are proposed, which allow to provide a combinatorial configuration in the form of structural graphs and grid graph, which is the basis for developing algorithms for solving problems in combinatorial configurations. The basis of these methods is a breakdown of the combinatorial configuration graph, which allows you to perform a directed search and draw conclusions about the whole group of points, united by certain features. Also it is considered the combinatorial optimization methods designed to solve combinatorial optimization problems. Existing methods cover a wide range of applications, presented by precise, approximate and heuristic algorithms, but the underdeveloped apparatus of combinatorial optimization for solving problems with a vector criterion. The paper proposes new methods based on the horizontal and coordinate methods of localizing the value of the function. The methods of solving vector extreme problems on combinatorial configurations, among which the combined method, the modified method of sequential introduction of constraints, the coordinate method and the horizontal method are developed. The combined method and the modified method of sequencing constraints combine combinatorial methods of clipping with vector optimization methods. However, the result of the algorithms according to these methods is only one solution, which belongs to the set of optimal Pareto, and not the whole set of effective solutions. In turn, coordinate and horizontal methods allow the formation of a set of points satisfying the restriction of the problem. The search for optimal values is performed on the resulting set. The constructed models of applied problems, which are vector problems in combinatorial configurations, such as the model of the problem of determining the efficiency of real estate investments; model of the task of production domination; model of the task of ensuring the effective work of the site; model of the task of selecting modules in the development of programs; model of the problem of optimal distribution of arrays on the levels of memory of the computer; model of the task of choosing an optimal set of measuring devices. These mathematical models of tasks from various applications indicate the need for
Keywords: векторна оптимізація; горизонтальний метод; грід-граф; евклідові комбінаторні конфігурації; комбінаторна оптимізація; комбінаторні конфігурації; координатний метод; модель векторної задачі на комбінаторних конфігураціях; структурний граф; vector optimization; horizontal method; grid graph; Euclidean combinatorial configurations; combinatorial optimization; combinatorial configurations; coordinate method; vector problem’s model on combinatorial configurations; structural graph