STOCHASTIC OPTIMIZATION ON ARRANGEMENTS: PROPERTIES OF LINEAR UNCONSTRAINED PROBLEMS - Iemets, O. O.; Barbolina, T. M. (Computer Science and Applied Mathematics, 2017)
Actual trend of the modern theory of optimization is to study the problems of combinatorial nature. Important results have been obtained as a result of immersion of combinatorial sets in Euclidean space and study the properties of such problems. This paper is a continuation and development of a research within the Euclidean combinatorial optimization, it considers such an important class of Euclidean combinatorial optimization problems as arrangement problems. We also should note that the problems with uncertainty, including probabilistic, attract the attention of researchers recently. Such problems arise and in combinatorial optimization. Stochastic combinatorial models can be used to describe and solve many other important practical problems. Earlier the authors proposed an approach for stochastic optimization problems formalization through the introduction of the order relation on the set of random variables. This order on a set of discrete random variables is defined through the comparison of the mathematical expectations, dispersions, possible values and associated probabilities. Using introduced linear order, let us order the elements of the set of discrete random variables. The first random variable in this ordered list is the minimum value and the last one is the maximum value. The definition of the minimum and maximum allows setting the optimization problem for finding the extreme elements under existing conditions. In this article we discuss linear unconstrained problem of stochastic combinatorial optimization on the common set of arrangements when elements of multiset Γ are discrete random variables. Some properties of such problems are obtained. The interrelation of problems with stochastic uncertainty with the determined problems is shown. Determined problems are specially constructed: coefficients of objective function are powers of coefficients of objective function of initial stochastic problem, feasible region is the general set of arrangements when multiset elements are equal to mathematical expectation (or dispersion) of discrete random variables from given multiset Γ. We prove that minimal in solution of determined problem can be received using numerical characteristics of components of minimal in the solution of stochastic problem. On the other hand if x is the minimal in the solution of determined problem then there is a minimal in solution of the stochastic problem such that mathematical expectations (dispersions) of components are equal to corresponding components of x. Further research of properties of stochastic optimization problems based on criterion of minimal in (determined) linear unconstrained optimization problem on arrangements. A minimal in solution of linear unconstrained stochastic optimization problem on arrangements can be constrained using minimals in the problems of less dimension. The feasible sets of these problems are sets of arrangements from the elements of submultisets of given multiset Γ. The obtained result is used to prove properties of minimal in solution of linear unconstrained stochastic optimization problem on arrangements. There exists a minimal such that mathematical expectations and dispersions of its components are equal to corresponding mathematical expectations and dispersions of specific elements of multiset Γ. In particular if coefficients of objective function are positive and ordered by the lack of increase then there exists a minimal such that mathematical expectations and dispersions of its components are equal to corresponding numerical characteristics of leading elements of multiset which are located according to introduced order. If in addition there are no elements of multiset with equal mathematical expectation and dispersion then the arrangement which components are equal to corresponding elements of multiset is the minimal in solution of linear unconstrained stochastic optimization problem on arrangements . Subsequent studies suggest further study of the properties of the considered problems that will allow developing methods and algorithms to solve them.