кандидат технических наук;
candidate of technical sciences;
Важным этапом в проектировании инженерных сетей является разработка конфигурации сети, отвечающая наперед заданным условиям. Основным для построения оптимизационных геометрических моделей является построения кратчайших линий связующих заданное дискретное множество точек пространства. Такие модели также выявляют геометрические факторы и определют те или иные свойства конфигурации сети в рассматриваемом физическом пространстве. Геометрические модели определяют образ проектируемого объекта, поэтому можно построить различные конфигурации трассировки сети, которые и позволяют выбрать оптимальную сеть. Для решения данной инженерной задачи в статье исследованы и разработаны оптимальные геометрические модели на плоскостях с евклидовой, ортогональной, полярной метрикой и алгоритмы для них. Разработан единый алгоритм трассировки разветвленных инженерных сетей на плоскостях с различной метрикой. Поставленная цель достигается применением и обобщением метода Штейнера. Как известно, проблема Штейнера связана с задачами построения минимального связующего дерева и в общем виде не решена. Практическое решение задачи трассировки заключается в поиске конфигурации разветвленной сети, имеющей наименьшую протяженность, что значительно влияет на ее стоимость. На первом этапе проектирования разрабатываются геометрические модели инженерных сетей, затем решаются оптимизационные задачи, которые сводятся к решению проблемы Я. Штейнера в общем виде [5; 27]. Алгоритм для решения задачи Штейнера основан на разбиении заданных дискретных точек плоскости на локальное подмножество, при этом применяется принцип наименьшего удлинения и сравнительный анализ различных геометрических моделей, которые позволяют выбрать и построить сеть требуемой конфигурации. Сформулирован единый алгоритм трассировки для построения конфигурации евклидовой, ортогональной и полярной сети. Сложность решения задачи Штейнера и инженерных задач трассировки обусловлена тем, что эти задачи принадлежат к экстремальным и к классу NP-трудных задач дискретной оптимизации.
An important stage in the design of engineering networks is the development of network configurations that meet pre-defined conditions. The main thing for constructing optimization geometric models is to construct the shortest connecting lines for a given discrete set of points in space. The specified points have different weights. Such models also identify geometric factors and determine certain properties of the network configuration in the considered physical space. Geometric models define the image of the projected object and you can build various network tracing configurations that allow you to choose the optimal network. To solve this engineering problem, the article investigates and develops optimization geometric models on planes with Euclidean, orthogonal, polar metrics and algorithms. A unified algorithm for tracing extensive engineering networks on planes with different metrics has been developed. This goal is achieved by applying and generalizing the Steiner method. As you know, the Steiner problem related to the tasks of constructing a minimal spanning tree has not been solved in a general way. The practical solution to the tracing problem is to find the configuration of an extensive network with the smallest length, which has a greater impact on its cost. At the first stage of design, geometric models of engineering networks are developed, then optimization problems are solved, which are reduced to various generalizations of the problem J. Steiner [5,27]. The algorithm for solving the Steiner problem is based on dividing the given discrete points of the plane into a local subset, using the principle of least elongation and a comparative analysis of various geometric models, which allows you to select and build a network of the required configuration. A unified tracing algorithm is formulated for constructing the configuration of a Euclidean, orthogonal, and polar network. The complexity of solving the Steiner problem and engineering tracing problems is due to the fact that these problems belong to the extreme and to the class of NP-hard discrete optimization problems.