On Complete and Quasi-Complete Two-Criteria Optimization Problems on Graphs
- PDF / 123,372 Bytes
- 6 Pages / 594 x 792 pts Page_size
- 103 Downloads / 198 Views
ON COMPLETE AND QUASI-COMPLETE TWO-CRITERIA OPTIMIZATION PROBLEMS ON GRAPHS V. A. Perepelitsa1 and E. V. Tereschenko2
UDC 519.176
Abstract. Sufficient conditions are studied for the presence of the completeness or quasicompleteness property in two-criteria discrete optimization problems with the same and different weight-type criteria. Estimates are computed for the cardinalities of sets of feasible solutions, the Pareto set, and a complete set of alternatives for a number of two-criteria problems. Keywords: multicriteria optimization, vector optimization, Pareto set, complete set of alternatives, complete problem, quasi-complete problem.
In various fields of human activity, a made decision has to be evaluated by many quality criteria, which makes it necessary to consider a set of alternatives. In the general case, this leads to the situation when, for each solution, there are alternatives, i.e., other solutions each of which is better than the solution in question by at least one criterion [1–3]. A distinction of a multicriterion problem from a one-criterion one is that, in the first case, we obtain not one solution but a solution set (a set of alternatives) [2, 4]. The final choice of the most expedient solution is made by man. The question of decision-making is beyond the formal definition of the concept of an “optimum” or an “optimal solution” since this concept can pertain to no less than two different elements (in the general case). This implies the mathematical ambiguity of the problem of definition of an “optimal solution” in the case when the number of criteria is no less than two. Denote by the symbol Z g , g = 1, 7 , a one-criterion problem of determining the corresponding minimum of the sum of weights of edges, which is formulated on an n-vertex graph G = (V , E ) . We now consider the following problems: Z1 on perfect matchings, Z 2 on spanning trees, Z 3 on distributions, Z 4 on perfect matchings on a bipartite graph with equal parts, Z 5 on Hamiltonian cycles, Z 6 on Hamiltonian chains, and Z 7 on assignments. Denote the set of all feasible solutions (SFS) to a problem Z g with an individual criterion Fg ( x ) by X g = { x g } , where x g is a subgraph (V , E g ) of the graph G , E g Í E , and g is the individual number of the criterion. For example, if, in the problem on Hamiltonian cycles Z 5 , the constraint “moving from city to city must not exceed l units” is added, then we obtain a new problem Z g 0 , where g 0 > 7. Denote by the symbol Z g 1 , g 2 a two-criteria problem on a two-weighted n-vertex m-edge graph with minimized criteria Fg ( x ) ® min , i = 1, 2 , of a vector objective function Fg 1 , g 2 ( x g 1 , g 2 ) . Indices g i , i = 1, 2 , denote individual i
numbers of the criteria, and the order of criteria Fg i ( x ) determines the order of solving problems Z g i . In particular, in the case of Z1, 2 the solution begins with the consideration of the problem on perfect matchings and, in the case of Z 6 ,1 , it begins with finding Hamiltonian chains. The set of feasible solutions of a
Data Loading...
