| Popis: |
The tasks of multi-criteria optimization in the general formulation do not have a trivial solution, which gives rise to a multitude of approaches in determining the most “successful” solution from a certain set of solutions that satisfy the problem conditions. One of the ways of formal defining of the possible alternative solution set is to isolate the Pareto set, i.e. the set of unimprovable alternatives. The previously developed approach was applied for studying some classes of multi-criteria problems, the objective functions of which have certain properties, and its productivity was confirmed. The concept of complete problems was introduced, for which the equality of the sets of feasible solutions, the Pareto and the full set of alternatives was fulfilled. In previous works, the authors introduced the concept of quasi-completeness. In the article the class of two-criterion problems, for which the admissible solution for the first criterion has a constant number of edges, and objective function contains the criterion of weight and the criterion of the minimax edge, is distinguished. The problem on the graph of the general structure and the problem on the bichromatic graph, for which the feasible solutions have a constant number of edges, were selected as representatives of this class. A method for studying the properties and estimating the powers of an admissible set of solutions, a Pareto set and a complete set of alternatives for the problems of the selected class, has been formulated. A theorem on the quasi-completeness for the selected class problems is proved. There were obtained estimates for two representatives of this class: “about a spanning tree and a minimax edge”, “about a perfect matching on a bichromatic graph and a minimax edge”. Polynomial algorithms for solving the problems under study are proposed. Estimates of the computational complexity of these algorithms are given |
