Introduction

Computer simulation of technological processes consists in optimization of the study object by a mathematical model, and further model study with the help of implemented computational algorithms on personal computers. The computer simulation process, as a single process of building and researching a model, is used for research, analysis, design and optimization of technological objects and systems [1]. Today, computer modeling approaches combines both theory and practice. Working with a model that represents a research object gives you the opportunity to explore its properties and behavior in all situations.

Computer modeling is the process of building a real study object's model and setting up computational experiments on this model in order to understand and evaluate various strategies based on the use of algorithms that ensure the functioning of this study object. Thus, the process of computer simulation includes the model design, and its application to solve the problem of optimization and design of technological processes in production. All these problems are extremely complex and include numerous elements, variables, parameters, constraints, etc. Such problems can be modeled by combinatorial optimization tasks [1][2][3][4][5][6][7][8].

The combinatorial optimization problems study comprises a fairly wide range of mathematical models associated with the need to solve various important practical problems of optimal planning, management and design [1,2,5,7,9,[10][11][12][20][21][22][23][24][25][26][27][28][29]. In this regard, many papers have recently appeared which investigate the combinatorial optimization problems and propose approaches to their solution [8,[36][37][38].

The paper presents a model of optimization problems on a combinatorial set of permutations, which is a model of many applied problems. It is proposed the algorithm for solving an optimization problem with a quadratic target function and additional restrictions on permutations.

During the method's implementation the first reference plan is located and additional restrictions are checked, which reduces the number of considered solutions at the beginning of the algorithm It is offered an example of solving a theoretical problem by the given method and demonstrating its efficiency.

2

Literature review

Computer models have become a common tool for mathematical modeling and are used in various areas of electronics, engineering, industry, and so on. Computer models are used to obtain new knowledge about the object or for an approximate assessment of the system's behavior that are too complex for analytical research.

Computer modeling is one of the effective methods for studying complex systems. The construction of a computer model is based on abstracting from the specific nature of the phenomena or the original object under study and consists of two stages -first, the creation of a qualitative, and then a quantitative model. The more significant properties will be identified and transferred to the computer model -the more approximate it will be to the real model, the greater the capabilities that the system using this model will have. Today the works of many scientists are devoted to this research area [1-5, 8-10, 21].

An important computer simulation area is analytical and simulation modeling. In analytical modeling, mathematical (abstract) models of a real object are studied in the algebraic equations form, as well as providing for the implementation of an unambiguous computational procedure leading to their exact solution. In simulation, mathematical models are studied in the algorithms form, which reproduce the functioning of the system under study by sequentially performing numerous elementary operations. Very relevant today for simulation and analytical modeling are discrete models, in particular, combinatorial optimization, their study is the subject of a great number of papers [1][2][3][4][5][6][7][8][9][10][11][12][13][14][15][16][17], [22][23][24][25][26][27][28][29][30][31].

A significant contribution to the development of modern discrete optimization theory, the development and implementation of its methods in the study and solving of important applied problems have been made over the course of more than forty years under the scientific guidance of Academician I.V. Sergienko scientists of the Institute of Cybernetics named by V.M. Glushkov National Academy of Sciences of Ukraine. They obtained important results, which became the basis for the theory development and the creation of n lines in discrete optimization.

At present, intensive studies of the stability problems of vector discrete optimization problems are carried out at the Institute of Cybernetics named by V.M. Glushkov of the National Academy of Sciences of Ukraine (I.V. Sergienko, T.T. Lebedev, N.V. Semenova, T.I. Sergienko) [16,17], Belarusian State University (V.O.Emelyichev, D.P. Podkopayev, Yu.V. Nikulin, etc.) [6,7], the Joint Institute of Computer Sciences of the National Academy of Sciences of Belarus (Yu.N.Sotskov), the Computational Center of the Russian Academy of Sciences (E.M. Gordeyev, V.K. Leontiev), Omsk Branch of the Institute of System Studies of the Polish Academy of Sciences (M. Libura), a number of universities of the Federal Republic of Germany (E. Girlich), the Netherlands (ES van der Poort, G. Sierkma, APM Wagelmans, JAA van der Veen), in the uniquely Colorado US (H.J. Greenberg).

Belarusian scientists under the scientific guidance of Professor V.O. Yemelycheva successfully develops a constructive approach to the problem of the vector discrete optimization problems correctness associated with the reception of quantitative characteristics of the stability of specified problem statements, a mathematical apparatus for studying the stability of multicriteria discrete problems with different types, vector criteria functions, principles of optimality, as well as generalized and parameterized principles of optimality are developed.

It is important to study the relation between different classes of point configurations triangulation (regular, weakly regular, deployed, symmetric, political, etc.), in particular, the study of the structure of a partially ordered set constructed on the family of triangulation classes considered in relation to the inclusion relation. Recently, algorithms for solving convex polyhedral admissibility problems are actively explored [11,18,19]. One of the interesting computational approaches is the reduction of the admissibility problem for a polyhedron to the projection problem on a normal cone generated by a dual system of inequalities [18,29,31], which is sufficiently close to the projection problem for a binary polyhedron. Today, in the research area of various classes of combinatorial models, the new methods development for their solution, great attention is paid to methods based on the use of structural properties of combinatorial sets. The properties of combinatorial sets study is closely related to the theory of polyhedral and graphs. The use of information about the structure of the convex shell of admissible multivariate solutions, which is the basis for many methods, is one of the most successful approaches to solving combinatorial optimization problems for today. But when solving such tasks there are problems related to the complexity of mathematical models, large volume of information, etc.

Applied problems simulated by extreme discrete tasks often have a high dimensionality, so they are quite complex from a computational point of view. The main task is to determine the value of an argument belonging to a certain combinatorial configuration for which the target function acquires the global optimum. So it is necessary to develop the most effective algorithm, which is based on the specific properties of the combinatorial configurations.

For the extreme problems of combinatorial optimization, polynomial algorithms for finding an optimal solution based on the properties of the input data structure have been developed, but there are few such work compared to methods based on partial overview of the options. One of the approaches to solving such problem is to carry out research and analysis of the combinatorial configurations properties, in which the target function, which reflects the combinatorial nature of the tasks, is determined. Analysis and study of combinatorial configurations as a target function argument, setting the change in the values of the target function, depending on the elements ordering of the selected combinatorial configuration and the structure of the input data specificity, does not pay sufficient attention in the literature. But it should be noted that the study of the certain tasks properties in order to identify their characteristic properties and their use for solving the problem, gives the possibility of constructing new approaches and the development of known methods.

Hence, one of the important problems in the discrete optimization area is the detection of the properties of combinatorial configurations in extreme problems, the use of which would allow to establish the regularity of the change in the values of the target functions, depending on the argument ordering and on the specificity and structure of the combinatorial configurations sets.

Today, significant results have been obtained in the area of research of combinatorial models' various classes and the development of new methods for their solution. The following foreign scientists made a fundamental contribution to the development of discrete, in particular, combinatorial optimization: M. Gary, S. Berge, D. Johnson, H. Papadimitriou, P. Pardalos, K. Staiglich, R. Stanley, F. Harari, V.A. Emelichev, V.M. Sachkov [1-8, 10, 11, 12].

In turn, the many Ukrainian scientists' works are devoted to the various classes of combinatorial optimization problems' study: L.F. Gulyanitsky, P.I. Stetsyuka, I.V. Sergienko, N.S. Shor, Yu.G. Stoyan, S.V. Yakovlev, A.O. Yemetsa, V.O. Perepelitsy and many others.

In particular, in [18][19][20][21], the authors describe the convex extensions theory and its applications in combinatorial optimization problems. Combinatorial models' applications in practical problems of geometric design are presented in the works of L.F. Gulyanitsky, I.V. Sergienko, Yu.G. Stoyan, S.V. Yakovlev, N.S. Shor [22][23][24][25][26][27]38].

Quadratic optimization on the permutation set is reflected in [28][29][30][31].

The permutation set's representation as the intersection of a permutation polyhedron and a hypersphere is interesting, as well as optimization methods on permutation configurations using the intersection described in [32].

The development of an integrated approach to the analysis of the properties of combinatorial optimization supplies covers a wide range of studies of combinatorial functions, combinatorial polyhedral, combinatorial configurations as an argument of the target function. The results give the opportunity to improve existing methods for solving such problems and develop new methods for optimal solutions searching. The problems based on the properties of combinatorial configurations are actual problems of combinatorial optimization. Of particular importance in this aspect is the consideration of extreme problems in combinatorial configurations using graph theory.

The research of tasks in graphs deals with such scientists as F. Harari, O. Ore, I.V. Sergienko, V. O. Yemelichev, A. O. Zikov, V. O. Perepelytsya, R. I. Tyshkevich and others. Despite quite large achievements in the area of discrete optimization, in the process of modeling, there are extreme problems classes for which a number of issues have not yet been investigated. Principal difficulties that arise during modeling are also related to various types of uncertainty. These include: the availability of many criteria for evaluating the quality of solutions, interval setting of task parameters, etc. In these conditions, classical methods are not sufficiently suitable for solving problems. As you know, most combinatorial optimization tasks can be reduced to integer programming tasks, but this is not always justified, since it eliminates the possibility of taking into account the combinatorial properties of task solutions.

This work is a continuation of research in the extreme discrete problem's area, in particular, combinatorial optimization, as well as optimization problems under the conditions of multicriteria, which arise in the study of many theoretical and applied problems.

Formal problem statement

We consider the permutation as an ordered sample of elements ) ,..., , (

2 1 k i i i a a a a  , where A a j i  , n j N i   , n N j   t s i i  if n N s t s    , n N t   from some multi-set } ,..., , { 2 1 q a a a A 

, which is characterized by the base } ,..., , { ) ( where

k j N j R e    , 1

and the multiplicity of the elements

j j r e k  ) ( , q r r r N j k k      ... , 2 1 k j N , 

according to [14,17]. A set of permutations with repetitions of n real numbers, among which k different, is called the general permutation set and is denoted as

) (A P nk

. This is the set of ordered n-samples from the multiset A under the condition k q n   .

If we haveq k n  

set of permutations without repetition, we denote it as n P .

Obviously, ) ( ) ( A P A P nn n



. In cases where the form of the set of permutations is not indicated, it will be possible to write down these sets as ) (A P .

It is known [14] , that is described by a well-known system of linear inequalities:

                   i j j i j j n j j n j j a x a x 1 1 1 1 , , (1)n i t j n j N i N t j t j N         , , , , ,    and ) ( vert ) ( A A P   .

Consider the optimization problem:

)} ( | ) ( max{ : )) ( , ( A P a a A P Z   (2)} ) ( | { b Gx R x D n    (3)

where

n m R G   , m R b          n i n j j i ij n j j j x x a x c a 1 1 1 2 ) ((4)

on a set of permutations ) ( A P n .

Additional linear constraints form a multifaceted set n R D  . Then, to every point

) (A P a n  will match point X x  , one that satisfies equality ) ( ) ( a x F   : } | ) ( max{ : ) , ( X x x F X F Z (5)

where,

       n i n j j i ij n j j j x x a x c x F 1 1 1 2 ) (( 6 )

and additional constraints:

} ) ( | { b Gx R x D n    (7)

where

n m R G   , m R b  X -nonempty set in n

R , which is defined as follows:

) ( vert A X   , ) ( conv A P  (8)

It is natural to assume that the maximum of a quadratic function will be one of the vertices of the permutation polyhedron, and the vertices of the graph ) ( n P G will match to all points of the set of permutations ) ( A P n . The adjacency of the vertices of a permutation polyhedron is determined by a onetime transposition of two vertex elements. The number of transpositions in the graph is determined by the formula [35]:

2 ) 1 ( 2   n n C n ( 9 )4

The algorithm for solving an optimization problem with a quadratic target function and additional constraints on the set is rearranged

The algorithm for finding the problem optimal solution consists of four steps, which in a few steps make it possible to obtain an optimal solution. STEP 1. Finding the first support solution.

Consider the first transposition of the target function: : ) ,..., 2 ( ,

2 1 n i x x   ) ... )( ( 2 2 1 1 1 2 1 12 n n x a x a x a x x f     

We form the necessary conditions for finding the first solution:

     ). (max max, , 2 1 i i a x x x (10)

Variants of transpositions:

: ) ,..., 2 ( , 2 1 n i x x   ) ... )( ( 2 2 1 1 1 2 1 12 n n x a x a x a x x f      : 3 1 x x  ) ... )( ( 3 2 23 1 13 3 1 13 n n x a x a x a x x f      … … … : 1 n x x  ) ... )( ( 2 2 1 1 1 1 n nn n n n n x a x a x a x x f     (11)

); ,..., 3 ( ,

2 n i x x i   : 3 2 x x  ) ... )( ( 2 2 22 1 12 3 2 23 n n x a x a x a x x f         … … … : 2 n x x  ) ... )( ( 2 2 1 1 2 2 n nn n n n n x a x a x a x x f         … … … : 1 n n x x   ) ... )( ( 1 2 1 2 1 1 1 1 1 n nn n n n n n n x a x a x a x x f             

The first solution will be: ) ,..., , (

2 1 n x x x

. It should be noted that there may be several first solutions. STEP 2. Check constraints: ) ,..., , ( 21 n g g g . When checking constraints, the following options are possible: All constraints are satisfied, then go to step 3. At least one of the restrictions is not satisfied, then the next solution found for the given transposition is considered. If there are none, then we consider the next point in ascending order and proceed to step 1.

In the case of consideration of all transpositions, it is necessary to consider the point in ascending order by three transpositions, four, etc. STEP 3. Formation of conditions for finding the optimal solution. Initial conditions for finding the optimal solution: , ) ,..., , (

2 1 b x x x f n                              ). ,..., ,( , ) ( )2 1 2 1 2 1 2 2 2 2 2 1 2 2 1 1 1 1 1 2 1 1 n n n n n n n n n n n x x x g b b b x x x g x x x g b b b x x x g x x x g b b b x x x g (12)

STEP 4. Improved support solution. Choose the next point from the set of permutations, which is better than the first support solution. Next, we transpose this point with respect to the first support solution and find the numerical value of the transposition of the target function:

b x x x f n tr    ) ,..., , (2 1(13) Prerequisite: b x x x f n tr    ) ,..., , (2 1

-growth. 4.1. If this condition is true, then it is necessary to check the growth of restrictions:

      1 2 i i i g g g                i g i j g j i g j j g i c x c x c x c x i i i i * * * * 1 1 2 2 (14)

All increments satisfy conditions (12), then the found point is the optimal solution. Otherwise, we return to the beginning of the step 4.

4.2. If condition ( 13) is not fulfilled, we return to the beginning of step 4.

It should be noted that conditions (12) are sufficient for finding the optimal solution, and the fulfillment of inequality ( 13) is necessary for finding the optimal solution.

Example

Find the maximum value of the target function: For formula (1), the number of possible transpositions is:

6 2 4  С .

Consider the first transposition Then the first solution may be the following points of the permutations set: (4,3,1,2), (4,2,1,3), (3,2,1,4).

Consider the first point (4,3,1,2):

       .31        x x x x x x f

Consequently, the target function increases by 6.5 units, so there is a need to check the increment of additional restrictions:

            