Choice of Solutions in the Design of Complex Energy Systems Based on the Analysis of Variants with Interval Weights

Abstract

Ensuring high-quality and uninterrupted power supply to consumers is one of the main problems of creating reliable power systems of a new generation. It is associated with the implementation of an integral assessment of the technical state of equipment of the power stations and substations, based on technical diagnostics data. Integral assessment involves the choice of ranges of the set of parameters of the technical state for groups of constituent elements of equipment, as well as the determination of their weight coefficients. Currently, the problem is solved with the help of expert assessments, arbitrarily in each specific case, which may lead to an incorrect integral assessment of the state of the equipment. The principle of decomposition makes it possible to determine the individual performance characteristics of each of them. At the same time, their subsequent aggregation ensures that the emergent properties of the system are taken into account. Such an approach was used in this work to evaluate individual types of equipment and their constituent elements. The algorithm for constructing a tree with a minimum random weight, proposed in this paper, makes it possible to increase the validity of decisions. They are made at various stages of designing complex technical systems and include tasks with an integral assessment of the technical state of equipment of power plants and substations. In the proposed algorithm, as a result of using the tree of variants, a matroid is formed, on which, using the “greedy” algorithm, the optimal solution can be determined.

1. Introduction

Currently, the issues of monitoring and analysis of the technical state of high-voltage equipment of power stations and substations are acute in the power industry. This is largely due to the fact that a significant part of the main power grid equipment has worked out the established park resource or service life, determined by regulatory documents, and is used to the limit of its capabilities [1,2,3,4,5].

To analyze the current technical state of high-voltage equipment of power stations and substations, monitoring systems are being developed [2,3,4]. They are implemented using a set of hardware and software. Such a facility is designed to record various information about the parameters of the functioning of the equipment and its constituent elements, its operating conditions, etc. Among other things, to analyze the state of equipment, based on the data obtained, and, as a result, to form recommendations for its further operation [2,4,5].

To identify optimal solutions for the further operation of power grid equipment, several things have to be determined. These include the optimal structure of the technical state of the analysis system, but also a set of criteria, on the basis of which this analysis will be performed [1,3].

An electrical substation is an installation that receives, converts and distributes electrical energy. It consists of transformer structures and other converting devices, as well as a control system, distribution devices and others. As the name suggests, for the implementation of a monitoring system for such a complex object as an electrical substation, new approaches to its formation are needed. It is due to the fact that it combines many different elements (equipment), in each of which many physical processes of a different nature take place.

The task of analyzing the technical state of an electrical substation is divided into a number of separate subtasks. This is due to the fact of analyzing the technical state of each individual type of electrical equipment of this substation [1,2,3].

An electrical substation, for example, a 110 kV one, includes the following types of equipment, such as:

▪

Power transformers;

▪

Power lines (overhead and cable lines);

▪

Auxiliary transformers;

▪

Reactors;

▪

Relay protection and emergency controls (RPEA);

▪

Circuit breakers;

▪

Disconnecting switches;

▪

Busbar sections;

▪

Measuring transformers (of current and voltage);

▪

Overvoltage limiters, etc.

In turn, the assessment of the state of each individual type of power grid equipment is divided into a number of subtasks for analyzing the state of its main elements. For example, for a 110 kV circuit breaker, this could be [4,5]:

▪

Contact system;

▪

Arc chute;

▪

Drive;

▪

Shell;

▪

Inputs;

▪

Internal insulation;

▪

Control unit, etc.

For 110 kV power transformer [6,7,8,9]:

▪

Core;

▪

Winding;

▪

Internal insulation;

▪

Tank;

▪

Bushings;

▪

Oil;

▪

Oil conservator;

▪

Explosion vent;

▪

Radiator;

▪

Control units, etc.

The depth of detail of an object in such a system is characterized by the state of the set of elements [1,3,8]. The cause of it is the purpose of the system being developed and the sufficiency of understanding the main properties of the system. The need to detail such a system should be carried out to a certain level. Then, the dependencies of its output indicators on input parameters for each element are significant from the point of view of the operability or inoperability of the equipment.

Thus, the state estimates, formed during the solving of subtasks, constitute indicators of a higher level of generalization. This, in turn, serves as the basis for the tasks of the next level of the hierarchy [10]. In other words, the task of analyzing the technical state of the power grid equipment (objects) of a substation can be characterized as a task of hierarchical decomposition. During this task, in order to solve each of the subtasks, it is necessary to ultimately form its own set of parameters, describing the current technical state of the equipment.

Forming the assessment of the technical state of the equipment is carried out on the basis of data from technical diagnostics and data from monitoring systems [1,3,4,9,10,11]. They characterize its main parameters of functioning. It is also necessary to emphasize that such data are most often interval data, which also complicates the solution to this problem.

For example, for a 110 kV power transformer, the following indicators can be attributed to the technical diagnostics and data monitoring [6,7,10,12]:

▪

Chromatographic analysis of gases (characterizes the state of the oil);

▪

No-load losses (characterizes the state of the magnetic circuit);

▪

Insulation resistance (characterizes the state of solid insulation);

▪

The year of manufacture of the transformer;

▪

The year of capital repairs (characterize the general state of the winding), etc.

Due to many interrelated physical processes of various natures occurring in the equipment, it is obvious that each of the parameters can not only characterize the process, but also might additionally describe the state of a certain set of equipment elements.

Groups of equipment are formed on the basis of functionality, technical characteristics, aging processes of equipment or its elements, types of impact on equipment and its costs. Most often, energy companies approach the tasks of choosing groups of equipment, determining their constituent elements and forming a set of parameters. These parameters can describe their technical state, based on expert assessments and formalized in the form of weighting coefficients [3,7,10]. Weighting coefficients are determined experimentally, for example, based on the cost of the impact on the equipment and its significance for the functioning of the complex facility, etc. Thus, the hierarchy, as well as the determination of their weighting coefficients, are arbitrary in each specific case. The hierarchy includes groups of equipment, their constituent elements and a set of parameters of the technical state and has only expert justification, which may be suboptimal.

Moreover, the systematic organization of the integrated power grid determines the mutual influence of adjacent objects. This includes not only the level of equipment elements, but also the level of various types of equipment. They are connected by common processes of generation, transmission, distribution and consumption of electrical energy. These features also influence the formation of a generalized assessment of the aggregate state of a group of objects (for example, an electrical substation), representing an energy production (part of the overall energy system) of a higher level of the hierarchy [2].

Thus, the main task in developing systems for analyzing the state of complex integrated power grids is the task of choosing a system variant that has one or another set of preferred characteristics. It is applicable for such objects as a power plant or substation with many different types of equipment, elements and parameters of their functioning.

The most effective approach to optimizing a complex system with deterministic or imprecise characteristics seems to be representing the system as a hierarchy, followed by optimization of that hierarchical structure.

In some cases, such hierarchical structures are the objects of standardization; for example, in relation to the development of any air, sea and land transport or equipment, the generally recognized ASD1000 guidelines apply [13]. In other cases, the hierarchical structure of the system being created is defined as part of the architecture description, as provided by the ISO/IEC/IEEE 42010 standard [14]. This approach has been used to solve a wide range of problems, including:

–

When optimizing the hierarchical structures of organizational systems [15,16,17] and as an individual case in information collection systems, in supply chain structures, and in the design and optimization of technological production [18,19,20];

–

When developing hierarchical user menus [21];

–

When analyzing the work of stock markets [22,23,24];

A significant drawback associated with the optimization of hierarchical structures in the cases considered above is that the weights of the hierarchical structure’s nodes are assumed to be deterministic values, which is virtually not the case in practice. Paper [25] considers optimization problems in hierarchies under the assumption that the weights of the hierarchy nodes are random variables. Works [26,27,28] consider cases when the weights of the hierarchy nodes are given in the form of fuzzy variables. However, as shown in the same works, optimization generally is a difficult problem to solve.

Our previous paper [29] considers the case when the weights of individual nodes are a scalar value, which is not the case in practice. Thus, a real node can be characterized by the following parameters, according to which the product should be optimized: price, weight, energy consumption, heat dissipation, dimensions, etc., which, in practice, limits the scope of the algorithm developed in [29].

A significant drawback of the algorithm [29] is optimization based on the value of the variance, which is a priori unknown. The variance can be replaced by its estimate, but the variance given in this way is not a scalar but an interval value given using a confidence interval.

In this paper, another possible approach to imprecisely specifying the weight of hierarchy nodes will be considered: representing the weight of a node as an interval value. With regard to the optimization problems of technological systems, optimization methods for hierarchies with interval-defined weights have barely been used; here, optimization remains a tricky issue to resolve. There are various approaches to determining the solution to an interval optimization problem [29,30]; however, with any approach, it becomes necessary to compare the values given in the form of intervals. Interval inequalities are often defined as rigorous, weak and central.

The rigorous definition means that on the number-scale axis, interval a is located to the left of the b interval and can have no more than one common point with it. The weak definition includes the rigorous one as a special case and allows intervals to intersect. The central definition reduces the comparison of intervals to a comparison of their centers, regardless of the width of the intervals.

A rigorous partial-order relation was proposed in [31] for pairs of non-intersecting intervals; all other intervals are considered incomparable. It is obvious that a rigorous definition of a partial order significantly limits the range of solvable interval optimization problems.

A weak partial-order relation allows the intersection of intervals, which makes it possible to increase the range of problems solved. However, special measures should be taken to consider the common parts of the intersecting intervals. Thus, in [32,33,34,35], to introduce order into a set of intervals, the Pareto efficiency concept was introduced. A disadvantage of the results, obtained in [32,33,34,35], is that they do not allow obtaining a solution with the optimal value of the upper or lower boundary of the interval solution, which is especially necessary when designing technological systems.

The contribution of this study:

–

The algorithm for searching for an object with an extreme weight of the upper (lower) limit with interval-specified weights was developed and its optimality was proved (Section 2.1);

–

The algorithm for searching for an object with an extreme weight of the upper (lower) limit with random weights (weights specified as a confidence interval) was developed and its optimality was proved (Section 2.2);

–

The generalization of the proposed algorithms for searching for an object with an extreme weight of the upper (lower) limit with interval weights and with random weights for a multidimensional case was developed and its optimality was proved (Section 2.3);

–

The quality of the algorithms considered in the work was compared, and it was shown that both for the scalar and for the multidimensional case the second option is preferable, since it allows obtaining narrower bounds for the sum of values given by the interval (Section 3.1);

–

It is proved that asymptotically for an object with the found extreme weight limit, the average weight of the object will also tend to its extreme value (minimum, maximum) for options with interval weights and with weights specified as a confidence interval (Section 3.2);

–

It is shown that the weight of the coordinates of the total extremal block weight vector will asymptotically (with increasing dimension of the interval vector) tend to its extremal value (Section 3.2);

–

It is proved that the proposed algorithms have polynomial complexity, and therefore, the optimization problem can be solved in a finite time (Section 3.3).

This paper is organized as follows. Section 2 describes the proposed algorithms for searching for an object with an extreme weight. Section 3 contains the results of the analysis of algorithms, including an estimation of their complexity. The Conclusions section (Section 4) summarizes the results.

2. Algorithms for Searching for an Object with an Extreme Weight of the Upper (Lower) Limit

2.1. Searching Algorithms in Case of Interval-Specified Weights

Further in the paper, finding an extremal solution for a hierarchical structure with weights, specified as a set of non-negative intervals, will be considered:

$$P=\left\{\mathsf{\alpha }\in \right. 𝕀ℝ \left.|(\underset{¯}{\alpha }>0)\&(\overline{\alpha }>0)\right\}.$$

(1)

Assume that the system can be represented as an assemblage of n blocks. Moreover, each block has p alternative versions (the first level of decomposition).

Let each block in the first decomposition level also have p alternative versions to create the second decomposition level, while it remains possible to divide blocks. As a result of such a decomposition, some kind of hierarchical structure will be obtained.

Additionally, assume that a rule is set in accordance with which a comparison of the interval-specified weights of individual blocks and the system as a whole will be performed.

Let us consider algorithms for constructing optimal hierarchical structures with a minimum upper bound for the minimum total weight of nodes and a maximum lower bound for the maximum total weight of nodes.

Let us first dwell on establishing an order for interval numbers.

Since in what follows we will be interested in solutions with optimal upper or lower bounds, instead of the interval $\mathrm{a}=\left[\underset{¯}{a},\overline{a}\right]$, it would be appropriate to consider the two intervals $\underset{¯}{\mathrm{a}}=\left[0,\underset{¯}{a}\right]$ and $\overline{\mathrm{a}}=\left[0,\overline{a}\right]$, where $\underset{¯}{a},\overline{a}>0$. As a value used to compare intervals ${\underset{¯}{\mathrm{a}}}_i$ or ${\overline{\mathrm{a}}}_{\mathrm{i}}$, let us take: $‖{\underset{¯}{\mathrm{a}}}_i‖={\underset{¯}{a}}_i,$ $‖{\overline{\mathrm{a}}}_i‖={\overline{a}}_i,$ or, in the case of comparing the sums of intervals

$$\underset{¯}{\mathrm{a}},\overline{\mathrm{a}}, ‖{\displaystyle \sum _{i=1}^n{\underset{¯}{\mathrm{a}}}_i}‖={\displaystyle \sum _{i=1}^n{\underset{¯}{a}}_i}, ‖{\displaystyle \sum _{i=1}^n{\overline{\mathrm{a}}}_i}‖={\displaystyle \sum _{i=1}^n{\overline{a}}_i}.$$

(2)

Let us consider the hierarchical structure, obtained by the successive decomposition of object blocks.

For each block with an interval weight, assign a non-negative value ω_i with a value equal, depending on the conditions of the problem being solved, to the norm of interval $\underset{¯}{\mathrm{a}}$ or the norm of interval $\overline{\mathrm{a}}$, and each element connecting the block $A_i,A_j$ weight $c_{i,j}$, respectively, equal to the norm of intervals ${\underset{¯}{c}}_{i,j}$ or ${\overline{c}}_{i,j}$. By the weights of blocks and connecting elements, we mean the quantities ω_i,_j, $c_{i,j}$, which are the norms of the corresponding elements.

Then, an article with an extreme weight in the upper level can be assembled, taking into account the weights of the connecting elements by choosing blocks with an extreme total weight at adjacent decomposition levels.

Assume that each block $a_{i,j}^k$ (where i—number of a group, j—number of a block in a group, k—number of decomposition levels) can be implemented in p variants. A weight for each block variant ${\omega }_{i,j}^k$ and each element of block connection $c_{i,j}^k$ is given.

In this case, p is the maximum number of options: if for some block the number of options is less than m, then the weight of this option, depending on the context of the task, will take the value either 0 or ∞, so when searching for an object with a minimum weight, the weight of the missing block variant is taken equal to ∞.

Let us consider the procedure for creating the weight of an object with a sequential block connection scheme, as shown in Figure 1.

Let us now consider the algorithm for choosing the optimal set of component parts for an article with a minimum upper weight limit (Figure 2).

Let us consider the following greedy algorithm. In each of the groups of variants that are at the lower decomposition level n, we choose the component objects with the minimum weight (the minimum norm of the interval given weight). Let us add this weight to the weights of the connecting elements of the corresponding blocks of the previous groups of n−1 of the decomposition level. We find in each of the groups of variants a block with a minimum total weight. Then, we will do the same operations at detail levels n−1, n−2 and so on, up to the first level. As a result, a tree from root to leaves will be obtained, with a minimum weight of the upper level (Figure 3).

It should be noted that the set of all variants is an acyclic graph, consisting of a set of non-crossing trees. The considered algorithm can be generalized when searching for an object with an extreme weight of the lower limit. Indeed, since the weights of article blocks are given as non-negative intervals

$${\mathrm{a}}_i=\left[{\underset{¯}{a}}_i,{\overline{a}}_i\right],{\underset{¯}{a}}_i,{\overline{a}}_i>0,i=1,2,\dots ,$$

(3)

then there are bounded non-negative intervals inverse to them:

$${\mathrm{z}}_i=\left[{\underset{¯}{z}}_i,\overline{z}{}_i\right]=\left[1/{\overline{a}}_i,1/{\underset{¯}{a}}_i\right],{\underset{¯}{z}}_i,{\overline{z}}_i>0,i=1,2,\dots .$$

(4)

Then, an article with an extreme weight on the lower level can be obtained with the algorithm, described above, by introducing a change to variables ${\mathrm{z}}_i=\left[1/{\overline{a}}_i,1/{\underset{¯}{a}}_i\right]$, whereby it should be borne in mind that the minimum upper limit for the weights after the reverse replacement will go into the maximum lower limit for weights a_i.

As an example, consider the problem of finding an article with a minimum upper limit for the minimum cost of the article. In what follows, for brevity, we will simply write ‘minimum cost’.

Statement of the problem.

Let us assume that the weight functions for each block and the sum of the blocks are defined. We will look for an article with a ‘minimum cost’. For simplicity, we assume that the cost of connecting blocks is zero or constant.

There is a certain set of elementary blocks (blocks that are indecomposable into sub-blocks) with their own weights. Blocks need to be combined at all levels of decomposition in such a way as to obtain an article with a ‘minimum cost’.

Let us assume that an article consists of two component blocks. Each component block can be made in two variants. Each variant in turn consists of two blocks, each of which has two variants and so on.

Let us consider the last level of decomposition (in our case, the third level, see Figure 4). In each of the blocks, we will sort the components by their weight. For clarity, we put them in ascending order.

When the components are connected with a ‘minimum cost’, we obtain blocks with a ‘minimum cost’ for the third level of decomposition.

Let us move on to Decomposition Level 2. Having performed the same operations at this level as at the third level, we will obtain variants of Blocks 1 and 2 with the ‘minimum cost’, variants of blocks on Decomposition Level 2.

Let us move on to Decomposition Level 1. By choosing from the variants of blocks, blocks with a ‘minimum cost’, and connecting them, we obtain an article with a minimum upper boundary for the minimum cost.

As will be shown in the work below, with a sufficiently large number of decomposition levels and number of components from the ‘minimum cost’, the upper boundary implies asymptotically the minimum cost in the average value of the interval.

The justification of the algorithm, considered above, follows using the Theorem [36]

Let J be some set of subsets of a finite set E. Then, (E, J) is a matroid if and only if J satisfies the following conditions:

(1)

∅ ∈ J;

(2)

If I ∈ J, R ⊂ I, then R ∈ J;

(3)

For an arbitrary positive weight function, the ‘greedy’ algorithm constructs a maximum weight set on J.

Let us show that the obtained result satisfies the last theorem:

(1)

The null set is acyclic, hence it is contained in J. The first condition is met;

(2)

Any subset of an acyclic graph is acyclic. The second condition of the theorem is also met;

(3)

The third condition of the theorem is met in accordance with the algorithm for constructing a tree of variants with a minimum weight of the upper boundary;

2.2. Searching Algorithm in Case of Weights Specified as a Confidence Interval

Consider further the case when the weight of some or all nodes of the tree is a random value. Let us assume that the weight of each node is distributed according to the normal law with interval values of the mathematical expectation and variance and are random independent variables. Then, the weight of each i-th node can be characterized by two parameters: ${\mathrm{m}}_i=\left[{\underset{¯}{m}}_i,{\overline{m}}_i\right]$—ensemble expectation and ${\mathsf{\sigma }}_i=\left[{\underset{¯}{\sigma }}_i,{\overline{\sigma }}_i\right]$—mean square deviation (if the weight of some node is not random, then σ_x is considered equal to zero for it), where ${\mathrm{m}}_i,{\mathsf{\sigma }}_i-$ belong to a set of non-negative real intervals.

As a weight function of the i-th node, depending on the conditions of the problem, we take the function:

$${\underset{¯}{\omega }}_{\mathrm{i}}={\underset{¯}{m}}_i+t_P{\underset{¯}{\sigma }}_i \mathrm{or} {\overline{\omega }}_{\mathrm{i}}={\overline{m}}_i+t_P{\overline{\sigma }}_i\hspace{0.17em}$$

(5)

and as the weight function of the sum of nodes, the function

$${\underset{¯}{\mathsf{\omega }}}_i+{\underset{¯}{\mathsf{\omega }}}_j={\underset{¯}{m}}_i+{\underset{¯}{m}}_j+t_P\sqrt{{\underset{¯}{\sigma }}_i^2+{\underset{¯}{\sigma }}_j^2} \mathrm{or} { \overline{\mathsf{\omega }}}_i+{\overline{\mathsf{\omega }}}_j={\overline{m}}_i+{\overline{m}}_i+t_P\sqrt{{\overline{\sigma }}_i^2+{\overline{\sigma }}_j^2}$$

(6)

where, for a given value of confidence probability, $P_{dov}$, $t_p$ is from condition [37] $P_{dov}=\frac{2}{\sqrt{2\pi }}{\displaystyle \underset{0}{\overset{t_P}{\int }}{e}^{-\frac{1}{2}{t}^2}dt}$. Assuming that $P_{dov}>0.69$, we obtain $t_P>1$.

If we accept the above expressions for the functions of the node weight and the weight of the sum of Nodes (5) and (6), then the algorithm for finding a tree with a minimum upper boundary on the weight can be constructed in the same way as for the case of a tree with a deterministic node weight.

Let us consider this case in more detail. Let us assume that the weights of the block variants are sorted in ascending order in each group of variants at all levels of decomposition $k=\overline{n,1}$.

Then, for the minimum value of the upper boundary of the confidence interval of the sum of weights at level k:

$$G_{в}^k\le {\displaystyle \sum _{j=n}^k\left({\displaystyle \sum _i^{}{\overline{m}}_{i,1}^j}+t_P\sqrt{{\displaystyle \sum _i^{}{\left({\overline{\sigma }}_{i,1}^i\right)}^2}}\right)},$$

(7)

where $i,1-$ means that in the group of i variants of blocks, the first block is selected, which, after sorting the blocks, corresponds to the block with the minimum weight. Summation by i is carried out over all selected blocks.

Let us prove the legitimacy of this algorithm.

Consider a sequence of interval-given numbers $a_i=\left({\overline{a}}_i,{\underset{¯}{a}}_i\right)$ meeting the conditions ${\overline{a}}_i>0,{\underset{¯}{a}}_i>0,{\overline{a}}_i\ge {\underset{¯}{a}}_i$. Under these conditions, the set of interval numbers satisfies the following axioms:

• a + (b + c) = (a + b) + c;
• a + b = b + a;
• a + 0 = a;
• a ∙ b = b ∙ a;
• a ∙ (b ∙ c) = (a ∙ b) ∙ c;
• a ∙ 1 = 1 ∙ a = a;
• a ∙ (b + c) = a ∙ b + a ∙ c = b ∙ a + c∙a = (b + c) ∙ a
• a ∙ 0 = 0 ∙ a = 0;

where 1 = (1, 1); 0 = (0; 0), which coincides with the axioms of semiring [36,37]. Therefore, the set of interval numbers satisfying the condition ${\overline{a}}_i>0,{\underset{¯}{a}}_i>0,{\overline{a}}_i\ge {\underset{¯}{a}}_i$ create a semicircle.

Consider the interval vector. For a vector with scalar components, if the components belong to a semicircle, it follows that the vector also belongs to the semicircle. Let us show that for the interval vector, this condition is also satisfied.

Consider the direct sum of vectors with addition and multiplication operations given in the form:

$$\begin{array}{c}\mathrm{a}+\mathrm{b}=({\underset{¯}{a}}_i+{\underset{¯}{b}}_i,{\overline{a}}_i+{\overline{b}}_i),\\ \mathrm{a}\cdot \mathrm{b}=({\underset{¯}{a}}_i\cdot {\underset{¯}{b}}_i,{\overline{a}}_i\cdot {\overline{b}}_i),\\ i=\overline{1,q},q-\mathrm{interval} \mathrm{vector} \mathrm{dimension} \mathrm{a},\mathrm{b}.\end{array}$$

(8)

Since the operation of vector addition is performed component by component and the axioms on addition are satisfied for each component, they will also be performed for the vector as a whole. Therefore, Axioms 1, 2 and 3 will hold for interval vectors.

Since the multiplication operation is also performed component by component, Axioms 4, 5, 6 and 8 will be fulfilled for the vectors.

From the fact that Axioms 1, 2, 3, 4, 5, 6 and 8 hold, Axiom 7 follows. It follows that the set of interval vectors for which the conditions are satisfied ${\overline{a}}_i>0,{\underset{¯}{a}}_i>0,{\overline{a}}_i>{\underset{¯}{a}}_i,i=\overline{1,m}$ form a semicircle.

Defining on set 𝕀ℝ the function $\mathsf{\omega }({\mathrm{a}}_i)={\mathrm{a}}_{1,i}+t\sqrt{{\mathrm{a}}_{2.i}^2}$,$\mathsf{\omega }({\mathrm{a}}_i)={\mathrm{a}}_{1,i}+t\sqrt{{\mathrm{a}}_{2.i}^2}$$t>0$, whence, due to the monotonicity of the functions ${\mathrm{x}}^a$ and $\sqrt{\mathrm{x}}$:

$$\begin{array}{l}\mathsf{\omega }({\mathrm{a}}_i)=\left({\underset{¯}{a}}_{1,i}{\overline{a}}_{1,i}\right)+t\sqrt{{\left({\underset{¯}{a}}_{2,i},{\overline{a}}_{2,i}\right)}^2}=\left({\underset{¯}{a}}_{1,i},{\overline{a}}_{1,i}\right)+t\left(\sqrt{{\underset{¯}{a}}_{2,i}^2},\sqrt{{\overline{a}}_{2,i}^2}\right)\\ =\left(\left({\underset{¯}{a}}_{1,i}+t\sqrt{{\underset{¯}{a}}_{2,i}^2}\right),\left({\overline{a}}_{1,i}+t\sqrt{{\overline{a}}_{2,i}^2}\right)\right)\end{array}$$

(9)

and consider two functions

$${\overline{\mathsf{\omega }}}_i=\left({\overline{a}}_{1,i}+t\sqrt{{\overline{a}}_{2,i}^2}\right),{\underset{¯}{\mathsf{\omega }}}_i=\left({\underset{¯}{a}}_{1,i}+t\sqrt{{\underset{¯}{a}}_{2,i}^2}\right).$$

(10)

If the function $\omega (a_i)=a_{1,i}+t\sqrt{a_{2,i}^2}$, $t\ge 1$(in fact, in our case, it is sufficient to satisfy the condition $t>0$) satisfies all axioms of the norm because $a_{1,i},a_{2,i}>0,$ then the norm is absolute. Therefore depending on the conditions of the problem being solved, we can take the value

$${\omega }_i=\left({\overline{a}}_{1,i}+t\sqrt{{\overline{a}}_{2,i}^2}\right) \mathrm{or} {\omega }_i=\left({\underset{¯}{a}}_{1,i}+t\sqrt{{\underset{¯}{a}}_{2,i}^2}\right).$$

(11)

Let us put in correspondence with the direct sum of the elements of semiring the weight function ω, which coincides with its norm,

$$\omega ({\mathrm{a}}_i+{\mathrm{a}}_j)=‖{\mathrm{a}}_i+{\mathrm{a}}_j‖=a_{1,i}+a_{1,j}+t\sqrt{a_{2,i}^2+a_{2,j}^2}$$

(12)

or, in the general case,

$$\omega \left({\displaystyle \sum _{k=1}^n{\mathrm{a}}_k}\right)={\displaystyle \sum _{k=1}^n{a}_{1,k}}+t\sqrt{{\displaystyle \sum _{k=1}^n{a}_{2,k}^2}}$$

(13)

By putting in the last expression $a_{1,j}={\overline{m}}_{i,1}^k$, $a_{2,j}={\left({\overline{\sigma }}_{i,1}^k\right)}^2$ and $t=t_P>0$, we obtain with a given probability P_dov an estimate of the upper boundary for the minimum total weight of the tree

$$G_{в}\le {\displaystyle \sum _{k=n}^1\left({\displaystyle \sum _i^{}{\overline{m}}_{i,1}^k}+t_P\sqrt{{\displaystyle \sum _i^{}{\left({\overline{\sigma }}_{i,1}^k\right)}^2}}\right)},$$

(14)

where summation by i is performed over all selected blocks and all levels of decomposition k.

Let us show that the algorithm, constructed in this way, is optimal. Indeed, since the set of all variants of hierarchy trees is a matroid (a consequence of the theorem [36,37]), and the algorithm for finding a hierarchy with a minimum weight is ‘greedy’, then, in accordance with the Rado–Edmonds theorem, an algorithm for constructing a tree with a minimum weight will be optimal.

2.3. Generalization of Proposed Algorithms for a Multidimensional Case

Let us now show how, within the framework of the approach, adopted in this paper, the results obtained can be generalized to a multidimensional case.

Let us now generalize the obtained results to a multidimensional case.

Let ${\mathrm{a}}_1,{\mathrm{a}}_2,\dots ,{\mathrm{a}}_q$ be an ordered sequence of intervals, in one way or another, reduced to dimensionless quantities. Let us divide by a unit of measurement:

$\mathrm{a}={\left(\begin{array}{cccc}{\mathrm{a}}_1& {\mathrm{a}}_2& \dots & {\mathrm{a}}_q\end{array}\right)}^T,{ \mathrm{a}}_i=\left({\underset{¯}{a}}_i,{\overline{a}}_i\right)-$ interval dimensionless vector dimension column q.

We will assume, as in the one-dimensional case, that the intervals ${\mathrm{a}}_i,i=\overline{1,q}$ belong to the set P = {${\mathsf{\alpha }}_i\in$ 𝕀ℝ $|({\underset{¯}{\alpha }}_i>0)\&({\overline{\alpha }}_i>0)$}.

In a similar way to the one-dimensional case, we will consider vectors

$$\begin{gathered} \underset{¯}{\mathrm{a}}={\left(\begin{array}{cccc}{\underset{¯}{\mathrm{a}}}_1& {\underset{¯}{\mathrm{a}}}_2& \dots & {\underset{¯}{\mathrm{a}}}_q\end{array}\right)}^T, \mathrm{where} {\underset{¯}{\mathrm{a}}}_i=\left(0,{\underset{¯}{a}}_i\right),i=\overline{1,q}, \\ \mathrm{or} \overline{\mathrm{a}}={\left(\begin{array}{cccc}{\overline{\mathrm{a}}}_1& {\overline{\mathrm{a}}}_2& \dots & {\overline{\mathrm{a}}}_q\end{array}\right)}^T, \mathrm{where} {\overline{\mathrm{a}}}_i=\left(0,{\overline{a}}_i\right),i=\overline{1,q}, \end{gathered}$$

(15)

In this case, for simplicity, we will assume that vectors having the same norm are equivalent.

We further assume that the coordinates of the vector $\underset{¯}{\mathrm{a}}$, ${\underset{¯}{a}}_i,i=\overline{1,q}$ or vector coordinates $\overline{\mathrm{a}}$, ${\overline{a}}_i,i=\overline{1,q}$ are mutually independent in magnitude, or in a more general case, each pair of coordinates does not depend in magnitude on its complement. Only then there must be an additive weight function

$$\begin{array}{c}\omega \left({\underset{¯}{\mathrm{a}}}_1,{\underset{¯}{\mathrm{a}}}_2,\dots ,{\underset{¯}{\mathrm{a}}}_q\right)={\displaystyle \sum _{i=1}^q{\omega }_i\left({\underset{¯}{а}}_{\mathrm{i}}\right)} \\ \mathrm{or}\omega \left({\overline{\mathrm{a}}}_1,{\overline{\mathrm{a}}}_2,\dots ,{\overline{\mathrm{a}}}_q\right)={\displaystyle \sum _{i=1}^q{\omega }_i({\overline{\mathrm{a}}}_i}).\end{array}$$

(16)

Let us take as an additive function of the weight $\omega$ of interval vectors $\underset{¯}{\mathrm{a}}$, $\overline{\mathrm{a}}$ their norm:

$$‖\underset{¯}{\mathrm{a}}‖={\displaystyle \sum _{i=1}^q‖{\underset{¯}{a}}_i‖}={\displaystyle \sum _{i=1}^q{\underset{¯}{a}}_i},‖\overline{\mathrm{a}}‖={\displaystyle \sum _{i=1}^q‖{\overline{a}}_i‖}={\displaystyle \sum _{i=1}^q{\overline{a}}_i}$$

(17)

or, more generally,

$${‖\underset{¯}{\mathrm{a}}‖}_{\lambda }={\displaystyle \sum _{i=1}^q‖{\underset{¯}{\lambda }}_i{\underset{¯}{a}}_i‖}={\displaystyle \sum _{i=1}^q{\underset{¯}{\lambda }}_i{\underset{¯}{a}}_i}=‖\Lambda \underset{¯}{\mathrm{a}}‖,{‖\overline{\mathrm{a}}‖}_{\lambda }={\displaystyle \sum _{i=1}^q‖{\lambda }_i{\overline{a}}_i‖}={\displaystyle \sum _{i=1}^q{\lambda }_i{\overline{a}}_i}=‖\Lambda \overline{\mathrm{a}}‖,$$

(18)

where $\Lambda -$ significance matrix (diagonal matrix of significance coefficients ${\lambda }_i,i=\overline{1,q}$), ${\lambda }_i>0-$ coefficient proportional to the significance of the i-th component of the vector. Usually, the equality ${\displaystyle \sum _{i=1}^q{\lambda }_i}=1$ is required; however, this condition is not mandatory.

Whence for the sum norm m of interval vectors $\underset{¯}{\mathrm{a}},\overline{\mathrm{a}}$ of the dimension q, we consequently obtain:

$$\begin{array}{c}‖{\displaystyle \sum _{k=1}^m{\underset{¯}{\mathrm{a}}}^k}‖={\displaystyle \sum _{k=1}^m{\displaystyle \sum _{i=1}^q{\underset{¯}{a}}_i^k}},‖{\displaystyle \sum _{k=1}^m{\overline{\mathrm{a}}}^k}‖={\displaystyle \sum _{k=1}^m{\displaystyle \sum _{i=1}^q{\overline{a}}_i^k}.}\\ \mathrm{or}\\ {‖{\displaystyle \sum _{k=1}^m{\underset{¯}{\mathrm{a}}}^k}‖}_{\lambda }={\displaystyle \sum _{k=1}^m{\displaystyle \sum _{i=1}^q{\underset{¯}{\lambda }}_i^k{\underset{¯}{a}}_i^k}}={\displaystyle \sum _{k=1}^m‖{\Lambda }^k{\underset{¯}{\mathrm{a}}}^k‖}\le {\displaystyle \sum _{k=1}^m‖{\Lambda }^k‖\cdot ‖{\underset{¯}{\mathrm{a}}}^k‖},\\ {‖{\displaystyle \sum _{k=1}^m{\overline{\mathrm{a}}}^k}‖}_{\lambda }={\displaystyle \sum _{k=1}^m{\displaystyle \sum _{i=1}^q{\overline{\lambda }}_i^k{\overline{a}}_i^k}={\displaystyle \sum _{k=1}^m‖{\Lambda }^k{\overline{\mathrm{a}}}^k‖}\le {\displaystyle \sum _{k=1}^m‖{\Lambda }^k‖\cdot ‖{\overline{\mathrm{a}}}^k‖}.}\end{array}$$

(19)

If we assume that at all decomposition levels k the significance matrix is constant, then:

$${‖{\displaystyle \sum _{k=1}^m{\underset{¯}{\mathrm{a}}}^k}‖}_{\lambda }\le ‖\Lambda ‖{\displaystyle \sum _{k=1}^m‖{\underset{¯}{\mathrm{a}}}^k‖},{‖{\displaystyle \sum _{k=1}^m{\overline{\mathrm{a}}}^k}‖}_{\lambda }\le ‖\Lambda ‖{\displaystyle \sum _{k=1}^m‖{\overline{\mathrm{a}}}^k‖}$$

(20)

As the value of the weight of an individual block ${\omega }_{i,j}^k$, we take a scalar value, which, depending on the conditions of the problem, takes the value of its norm:

$${\underset{¯}{\omega }}_{i,j}^k={\displaystyle \sum _{l=1}^q{\underset{¯}{a}}_{i,j,l}^k}, {\overline{\omega }}_{i,j}^k={\displaystyle \sum _{l=1}^q{\overline{a}}_{i,j,l}^k}$$

(21)

or

$${\underset{¯}{\omega }}_{i,j}^k={\displaystyle \sum _{l=1}^q{\underset{¯}{\lambda }}_l^k{\underset{¯}{a}}_{i,j,l}^k}=‖{\Lambda }^k{\underset{¯}{\mathrm{a}}}_{i,j}^k‖, {\overline{\omega }}_{i,j}^k={\displaystyle \sum _{l=1}^n{\overline{\lambda }}_l^k{\overline{a}}_{i,j,l}^k}=‖{\Lambda }^k{\overline{\mathrm{a}}}_{i,j}^k‖$$

(22)

Then, for the minimum value of the upper boundary of the sum of weights at the decomposition level k, it will be fair:

$$G_{в}^k\le {\displaystyle \sum _{j=n}^k{\displaystyle \sum _i^{}{\omega }_{i,1}^j}},$$

(23)

where $i,1$ indices mean that the first block is selected in the group of i variants of blocks, which after sorting the blocks corresponds to the block with the minimum weight. Summation by i is carried out over all selected blocks.

Due to the fact that the weight of the nodes is a scalar value, to find an object with an extreme upper (lower) boundary on the weight, you can use the algorithm discussed above for the scalar case.

Let us further consider the variant when the nodes of the tree are random vectors with elements, the parameters of the law, the distributions of which are given at intervals. Let us assume that the weight of each element of the vector is distributed according to the normal law with interval values of the mathematical expectation and variance and are random independent variables. Then, the weight of each component of the i-th node vector, as in the scalar case, can be characterized by two parameters, the expectation ${\mathrm{m}}_i=\left[{\underset{¯}{m}}_i,{\overline{m}}_i\right]$ and mean square deviation ${\mathsf{\sigma }}_i=\left[{\underset{¯}{\sigma }}_i,{\overline{\sigma }}_i\right]$.

The algorithm can be constructed in the same way as for the case of a tree with nodes, having a deterministic weight. However, in this case, at each k level, when comparing the weights of blocks, as the total weight, taking into account the weight of the connection blocks, we will take the value:

$${\omega }_{i,j}^k={\displaystyle \sum _{l=1}^q{\overline{m}}_{i,j,l}^k}+t\sqrt{{\displaystyle \sum _{l=1}^q{\left({\overline{\sigma }}_{i,j,l}^k\right)}^2}}={\tilde{\overline{m}}}_{i,j}^k+t\sqrt{{\left({\tilde{\overline{\sigma }}}_{i,j}^k\right)}^2}$$

(24)

$${\omega }_{i,j}^k+{\omega }_{l,v}^k=\left(({\tilde{\overline{m}}}_{i,j}^k+{\tilde{\overline{m}}}_{l,v}^k)+t_p\left(\sqrt{{({\tilde{\overline{\sigma }}}_{i,j}^k)}^2+\sqrt{{\left({\tilde{\overline{\sigma }}}_{l,v}^k\right)}^2}}\right)\right),$$

(25)

Or, more generally

$${\omega }_{i,j}^k={\displaystyle \sum _{l=1}^q{\overline{\lambda }}_l^k{\overline{m}}_{i,j,l}^k}+t\sqrt{{\displaystyle \sum _{l=1}^q{\left({\overline{\lambda }}_l^k{\overline{\sigma }}_{i,j,l}^k\right)}^2}}={\tilde{\overline{m}}}_{i,j}^k+t\sqrt{{\left({\tilde{\overline{\sigma }}}_{i,j}^k\right)}^2}$$

(26)

$${\omega }_{i,j}^k={\displaystyle \sum _{l=1}^q{\overline{\lambda }}_l^k{\overline{m}}_{i,j,l}^k}+t\sqrt{{\displaystyle \sum _{l=1}^q{\left({\overline{\lambda }}_l^k{\overline{\sigma }}_{i,j,l}^k\right)}^2}}={\tilde{\overline{m}}}_{i,j}^k+t\sqrt{{\left({\tilde{\overline{\sigma }}}_{i,j}^k\right)}^2}{\omega }_{i,j}^k+{\omega }_{l,v}^k=\left(\left({\tilde{\overline{m}}}_{i,j}^k+{\tilde{\overline{m}}}_{l,v}^k\right)+t_P\left(\sqrt{{\left({\tilde{\overline{\sigma }}}_{i,j}^k\right)}^2+\sqrt{{\left({\tilde{\overline{\sigma }}}_{l,v}^k\right)}^2}}\right)\right),$$

(27)

Then, for the minimum value of the upper boundary of the confidence interval of the sum of weights at the decomposition level k, it will be fair:

$$G_{в}^k\le {\displaystyle \sum _{j=n}^k\left({\displaystyle \sum _i^{}{\tilde{\overline{m}}}_{i,1}^j}+t_P\sqrt{{\displaystyle \sum _i^{}{\left({\tilde{\overline{\sigma }}}_{i,1}^j\right)}^2}}\right)},$$

(28)

where, as before, the indices $i,1$ mean that the first block is selected in the group of i block variants (which after sorting the blocks corresponds to the block with the minimum weight) and the summation by i is carried out over all selected blocks.

Let us prove the legitimacy of this algorithm.

Let a semicircle R₊ of non-negative real numbers be given, then the set S(a,+,*,0,1) of ordered pairs of non-negative real numbers is a semicircle [36,37]. Consider for S a direct addition operation with the actions:

$$\begin{array}{c}\mathrm{a}+\mathrm{b}=(a_{1,l}+b_{1,l},a_{2,l}+b_{2,l}),l=\overline{1,q},\\ \mathrm{a}\cdot \mathrm{b}=(a_{1,l}\cdot b_l,a_{2,l}\cdot b_{2,l}),l=\overline{1,q},\end{array}$$

(29)

where q—dimension of interval vectors.

We define for the set S the function

$$\omega (\mathrm{a})={\displaystyle \sum _{l=1}^q{a}_{1,l}}+t{\displaystyle \sum _{l=1}^q\sqrt{a_{2,l}^2}},t>0,$$

(30)

then function ω from the sum of interval vectors will be equal to

$$\omega (\mathrm{a}+\mathrm{b})={\displaystyle \sum _{l=1}^q\left(a_{1,l}+b_{1,l}\right)}+t{\displaystyle \sum _{l=1}^q\sqrt{a_{2,l}^2+b_{2,l}^2}}.$$

(31)

Let us show that function ω on S satisfies all axioms of the norm. Certainly

(1) $‖\mathrm{a}‖\ge 0,$

$$\omega \left(\mathrm{a}\right)={\displaystyle \sum _{l=1}^q{a}_{1,l}}+t{\displaystyle \sum _{l=1}^q\sqrt{a_{2,l}^2}}\ge 0,\mathrm{because} a_{1,l},a_{2,l},t>0,$$

(32)

(2) $‖\lambda \mathrm{a}‖=\left|\lambda \right|‖\mathrm{a}‖,$ where $\lambda \in R_{+}$

$$\omega (\lambda \mathrm{a})={\displaystyle \sum _{l=1}^q\lambda a_{1,l}}+t{\displaystyle \sum _{l=1}^q\sqrt{{\lambda }^2{a}_{2,l}^2}}=\left|\lambda \right|\left({\displaystyle \sum _{l=1}^q{a}_{1,l}}+t{\displaystyle \sum _{l=1}^q\sqrt{a_{2,l}^2}}\right)=\left|\lambda \right|\omega (\mathrm{a});$$

(33)

(3) $‖\mathrm{a}+\mathrm{b}‖\le ‖\mathrm{a}‖+‖\mathrm{b}‖,$

$$\omega \left(\mathrm{a}+\mathrm{b}\right)={\displaystyle \sum _{l=1}^q\left(a_{1,l}+b_{1,l}\right)}+t{\displaystyle \sum _{l=1}^q\sqrt{a_{2,l}^2+a_{2,l}^2}}$$

(34)

$$\omega \left(\mathrm{a}\right)+\omega \left(\mathrm{b}\right)={\displaystyle \sum _{l=1}^q{a}_{1,l}}+t{\displaystyle \sum _{l=1}^q\sqrt{a_{2,l}^2}}+{\displaystyle \sum _{l=1}^q{b}_{1,l}}+t{\displaystyle \sum _{l=1}^q\sqrt{b_{2,l}^2}}=\left({\displaystyle \sum _{l=1}^q\left(a_{1,l}+b_{1,l}\right)}+t{\displaystyle \sum _{l=1}^q\left(\sqrt{a_{2,l}^2}+\sqrt{b_{2,l}^2}\right)}\right),$$

(35)

Because $\sqrt{a_{2,l}^2+b_{2,l}^2}\le \left(\sqrt{a_{2,l}^2}+\sqrt{b_{2,l}^2}\right),$ then $\omega \left(\mathrm{a}+\mathrm{b}\right)\le \omega \left(\mathrm{a}\right)+\omega \left(\mathrm{b}\right)$.

Let us put into correspondence with the direct sum of the elements of the semicircle the weight function ω, which coincides with its norm:

$$\omega \left(\mathrm{a}\right)={\displaystyle \sum _{l=1}^q{a}_{1,l}}+t{\displaystyle \sum _{l=1}^q\sqrt{a_{2,l}^2}}\ge 0,$$

(36)

$$\omega \left(\mathrm{a}+\mathrm{b}\right)={\displaystyle \sum _{l=1}^q\left(a_{1,l}+b_{1,l}\right)}+t{\displaystyle \sum _{l=1}^q\sqrt{a_{2,l}^2+b_{2,l}^2}}$$

(37)

where q is the interval vector dimension.

By putting in the last expression $a_{1,j}=m_{i,j,l}^k$, $a_{2,j}^k=\left({\sigma }_{i,j,l}^k\right)$ и $t=t_P>0$, we obtain, taking into account (24) and (25) and the given probability Pdov, an upper bound estimate for the minimum total tree weight:

$$G_{в}^k\le {\displaystyle \sum _{j=n}^k\left({\displaystyle \sum _i^{}{\tilde{\overline{m}}}_{i,1}^j}+t_P\sqrt{{\displaystyle \sum _i^{}{\left({\tilde{\overline{\sigma }}}_{i,1}^j\right)}^2}}\right)},$$

(38)

where summation by i is performed over all selected blocks and all decomposition levels k.

Obviously, these algorithms will be optimal, since the same conditions are satisfied as for the algorithms in the scalar case.

3. Analysis of Proposed Algorithms

3.1. Comparison of Algorithms in Cases of Interval-Specified Weights and Weights Specified as Confidence Interval

Let us compare the quality of the algorithms considered in the paper. Consider first the scalar case. Let us assume that the interval given value can be represented as:

$$\mathrm{a}=\left[\underset{¯}{a},\overline{a}\right]=\left[m_x-t{\sigma }_x,m_x+t{\sigma }_x\right],$$

(39)

then in the first case for the sum of intervals, we obtain the expression:

$${\displaystyle \sum _i{\mathrm{a}}_{\mathrm{i}}}=\left[{\displaystyle \sum _i{m}_{xi}}-t{\displaystyle \sum _i{\sigma }_{xi}},{\displaystyle \sum _i{m}_{xi}}+t{\displaystyle \sum _i{\sigma }_{xi}}\right].$$

(40)

In the second case, respectively, for the sum of intervals, we obtain the expression:

$${\displaystyle \sum _i{\mathrm{a}}_{\mathrm{i}}}=\left[{\displaystyle \sum _i{m}_{xi}}-t\sqrt{{\displaystyle \sum _i{\sigma }^2{}_{xi}}},{\displaystyle \sum _i{m}_{xi}}+t\sqrt{{\displaystyle \sum _i{\sigma }^2{}_{xi}}}\right].$$

(41)

Since there is an inequation

$$\sqrt{{\displaystyle \sum _i{\sigma }^2{}_{xi}}}\le {\displaystyle \sum _i{\sigma }_{xi}},$$

(42)

then the second algorithm is preferable, since it allows you to obtain narrower boundaries for the sum of values given by the interval $wid({\mathrm{a}}_{\Sigma }^2)\le wid({\mathrm{a}}_{\Sigma }^1)$.

Let us show that the obtained result remains valid for the (multidimensional) vector case as well. Let the condition be satisfied for each component of the vector:

$${\mathrm{a}}_i=\left[{\underset{¯}{a}}_i,{\overline{a}}_i\right]=\left[m_{xi}-t{\sigma }_{xi},m_{xi}+t{\sigma }_{xi}\right], i=\overline{1,q}$$

(43)

Then, for the norms of the sum of vectors in the first case, we obtain:

$$‖{\displaystyle \sum _{j=1}^l{\underset{¯}{\mathrm{a}}}_j}‖={\displaystyle \sum _{i=1}^q\left({\displaystyle \sum _{j=1}^l\left({\underset{¯}{m}}_{i,j}+t{\underset{¯}{\sigma }}_{i,j}\right)}\right)},‖{\displaystyle \sum _{j=1}^l{\overline{\mathrm{a}}}_j}‖={\displaystyle \sum _{i=1}^q\left({\displaystyle \sum _{j=1}^l\left({\overline{m}}_{i,j}+t{\overline{\sigma }}_{i,j}\right)}\right)},$$

(44)

corresponding to the second case:

$$‖{\displaystyle \sum _{j=1}^l{\underset{¯}{\mathrm{a}}}_j}‖={\displaystyle \sum _{i=1}^q\left({\displaystyle \sum _{j=1}^l{\underset{¯}{m}}_{i,j}}+t\sqrt{{\displaystyle \sum _{j=1}^l{\left({\underset{¯}{\sigma }}_{i,j}\right)}^2}}\right)},‖{\displaystyle \sum _{j=1}^l{\overline{\mathrm{a}}}_j}‖={\displaystyle \sum _{i=1}^q\left({\displaystyle \sum _{j=1}^l{\overline{m}}_{i,j}}+t\sqrt{{\displaystyle \sum _{j=1}^l{\left({\overline{\sigma }}_{i,j}\right)}^2}}\right)},$$

(45)

whence, as well as for the scalar case, the preference of the second variant follows.

3.2. Analysis of Average Weight

Let us now show that for an article with the found extreme weight limit, the average weight of the article will also be close to its extreme value (minimum, maximum).

Let us first consider the first case of block weights given as interval values. Then, since the weights of the blocks are given as non-negative intervals, the midpoints of the intervals $mid\left({\mathsf{\alpha }}_{\mathrm{i}}\right)=\left({\underset{¯}{\alpha }}_i+{\overline{\alpha }}_i\right)/2$ and their radii $rad\left({\mathsf{\alpha }}_{\mathrm{i}}\right)=\left({\overline{\alpha }}_i-{\underset{¯}{\alpha }}_i\right)/2$ are non-negative quantities. Since the upper boundary on block weight is $mid\left({\mathsf{\alpha }}_{\mathrm{i}}\right)+rad\left({\mathsf{\alpha }}_{\mathrm{i}}\right)$, a sum of two positive values, then its extreme value is reached only if the middle of the interval and its radius simultaneously reach their minimum (maximum) value.

Let us now consider the second case, when the weight of tree nodes is a random value with distribution parameters given by intervals. In this case, as shown above, one of the values can be taken as the block weight:

$${\underset{¯}{\omega }}_{\mathrm{i}}={\underset{¯}{m}}_i+t_P\sqrt{{\underset{¯}{\sigma }}_i^2} \mathrm{or} {\overline{\omega }}_{\mathrm{i}}={\overline{m}}_i+t_P\sqrt{{\overline{\sigma }}_i^2},$$

(46)

since all the values included in the last expressions are not negative, then the weight will take on an extreme value, with a fixed $t_P$, only if the values ${\underset{¯}{m}}_i,{\underset{¯}{\sigma }}_i$ or ${\overline{m}}_i,{\overline{\sigma }}_i$ simultaneously reach their extreme value. Whence follows the proof of the last assertion.

Obviously, the result obtained can be easily generalized to the multidimensional case. Let us note one more important fact. From the result, obtained above, and Equations (44) and (45), it follows that the weight of the coordinates of the total extremal block weight vector will asymptotically (with increasing q) tend to its extremal value. However, it should be noted that for each finite set of article blocks, this statement will only be approximately valid.

3.3. Complexity of the Proposed Algorithm

Let us estimate the complexity of the proposed algorithm. Suppose, for simplicity, that the system can be represented as a union of blocks. In addition, each block has alternative versions (the first level of decomposition). Each block of the first level of decomposition also has m alternative variants, etc. We will also assume that the weight of the connection of blocks is equal to zero.

The algorithm for finding a tree with a minimum weight consists of two operations:

–

Finding a block with a minimum weight;

–

Summation of blocks with minimal weights.

An estimate of the complexity of the operation of finding a block with a minimum weight in each group of m alternative blocks has the form: $S_{\min }\le m^2$.

The number of block groups at decomposition level k, under the assumptions made, will be equal to $n_k=m^{k-1}.$ Then, the estimate of the complexity of the operation of finding the minimum blocks at the k level will look like:

$$S_{\min }^k\le m^2{m}^{k-1},$$

(47)

while an estimate of the complexity of the operation of finding blocks with a minimum weight over all n levels takes the form:

$$S_{\min }^{\Sigma }\le m^2{\displaystyle \sum _{i=1}^n{m}^{i-1}}=m^2\frac{m^n-1}{m-1}.$$

(48)

When the condition m >> 1 is met, we obtain:

$$S_{\min }^{\Sigma }\le m^2{m}^{n-1}=m^{n+1}.$$

(49)

This value can be taken as an estimate of the complexity of the algorithm in the scalar case. In the vector case, to estimate the complexity of the algorithm, we can take the value $S_{\min }^{\Sigma }\le (q-1)m^{n+1},$ where q is the block weight vector dimension.

The complexity of the algorithm is polynomial, and therefore, the problem of finding a system with a minimum weight can be solved in finite time.

4. Conclusions

The development of an assessment of the technical state of a complex integrated power grid, such as a substation, is based on a comprehensive study. It implies a simultaneous and coordinated study of the performance indicators of subobjects and their constituent elements from the point of view of the overall system organization. Each indicator characterizes one or another physical process that affects the state of an object, subobject and element or their combination from the standpoint of functioning within a single power system.

The system organization of the integrated power grid determines the mutual influence of adjacent objects, subobjects and elements. It is reflected both in determining their performance and in calculating the generalized assessment of the aggregate state of a group of objects. This, in the end, represents energy production (part of the overall energy system) of a higher level of hierarchy.

The algorithms for searching for an object with an extreme weight of the upper (lower) limit with interval-specified weights and with weights specified as a confidence interval have been developed. The optimality of these algorithms has been proven. For both algorithms, a generalization to the multidimensional case has been developed. The second algorithm (weights specified as a confidence interval) is preferable, since it allows obtaining narrower bounds for the sum of values given by the interval. For an object with the found extreme weight limit, the average weight of the object tends asymptotically to extreme value. The weight of the coordinates of the total extremal block weight vector will asymptotically (with increasing dimension of the interval vector) tend to its extremal value. The proposed algorithms have polynomial complexity, and therefore, the optimization problem can be solved in a finite time.

The algorithms, proposed in the paper, allows optimizing the element in terms of one parameter—the weight of the object. In this regard, when selecting options, it is necessary to set the allowable limits for changing non-optimized parameters. It should be noted that the determination of tolerances for individual blocks in the general case is a non-trivial task. However, in the first approximation, it can be solved, applied to the task, for example, of analyzing the technical state of equipment, based on the experience gained from the previously performed analysis of the state of equipment. It is important to keep in mind that, in practice, it is possible to obtain several objects with the same (or almost the same) minimum weight. Then, when choosing a single object, other non-optimizable parameters of the object should be compared with each other.

The principle of decomposition, used in this work to evaluate individual subobjects and their constituent elements, makes it possible to determine the individual performance characteristics of each of them. It is important as their subsequent aggregation ensures that the emergent properties of the system are taken into account.

The presented study is primarily focused on new mathematical apparatus, which has been addressed in detail in the present article. At the same time, due to the complexity of the industry tasks, which could be solved with the help of the suggested approach, the result of practical implementation requires a separate paper with a focus on the solution to the electrical engineering problem related to the high-voltage equipment technical state analysis with the help of the suggested approach. Thus, for the next steps, we plan to apply and verify the described approach and algorithms for analysis and evaluation of the technical state of high-voltage power equipment of a real substation.