Barbolina T. Theory and methods of combinatorial optimization on arrangements: deterministic and stochastic problems

The dissertation is devoted to the research of the combinatorial optimization problems on arrangements, development and substantiation of the methods for their solving. Both deterministic problems and problems under probabilistic uncertainty are considered. The properties of extremals of linear and linear-fractional function on a general set of arrangement are established, the methods for solving unconstrained linear-fractional problems on arrangements and mixed combinatorial problems of lexicographic optimization on arrangements with linear and linear-fractional objective functions and additional linear constrained are substantiated. The approach to formulation of optimization problems under probabilistic uncertainty based on ordering the random variables is proposed. The properties of linear problems of stochastic combinatorial optimization on arrangements in statements according to the offered approach are investigated and the methods for their solving are developed. The models of applied tasks are constructed as deterministic and stochastic optimization problems on arrangements.