Analysis of an algorithm for solution of conditional optimization problems with linear-fractional objective functions ov
- PDF / 112,839 Bytes
- 10 Pages / 595 x 842 pts (A4) Page_size
- 37 Downloads / 222 Views
ANALYSIS OF AN ALGORITHM FOR SOLUTION OF CONDITIONAL OPTIMIZATION PROBLEMS WITH LINEAR-FRACTIONAL OBJECTIVE FUNCTIONS OVER PERMUTATIONS UDC 519.85
O. A. Yemets and O. A. Chernenko
A method is considered to solve a conditional optimization problem with a linear-fractional objective function over permutations. The performance of subalgorithms to solve this problem is evaluated. The practical efficiency of the algorithm is analyzed by conducting numerical experiments. Keywords: Euclidean optimization problem, linear-fractional function, set of permutations, method of constructing lexicographic equivalence. INTRODUCTION A choice of alternative actions usually requires optimization problems to be solved. These problems are often combinatorial [1–16]. In particular, of recent interest is Euclidean combinatory optimization [3], where the properties of and solution methods for problems with linear-fractional objective functions on Euclidean combinatory sets are analyzed. Problems on permutations have some properties that promote developing special methods and algorithms of their solution. The type of the objective function and availability of additional constraints are important. One of the aspects of such problems is to analyze their domains of definition [3–6, 10, 15], another aspect is to develop solution techniques depending on a combinatory set: transpositions, permutations, combinations, etc. [3–6, 9, 11–14, 16]. It is of importance to find efficient solution algorithms. An algorithm developed and implemented should be analyzed for efficiency. It is difficult or impossible to mathematically study many complex algorithms. It is especially important in such cases to test an algorithm in practice, to evaluate its complexity. Therefore, to obtain reliable results, both analytic and experimental analyses are necessary. Here, we analyze auxiliary algorithms for the algorithm of solving a conditional problem with a linear-fractional objective function on a set of permutations and use numerical experiments to analyze its practical efficiency. PROBLEM FORMULATION Denote by J k the set of k first natural numbers, J k = {1, 2, . . . , k}, J k0 = J k È{0}. Let k , n, h, m, and p be natural constants, g j and e i be positive real numbers "j Î J h and "i Î J n , and G = {g 1 , g 2 , . . . , g h } be a multiset with the basis S (G ) = ( e1 , e 2 , . . . , e n ) and element multiplicities kG ( e i ) = h i , i Î J n . Assume that elements of the multiset and of the basis are arranged in nondecreasing and increasing orders, respectively. Denote by E hkn (G ) the general set of k-permutations [3]. 0 Let c j , d j Î R "j Î J m , a ij , bi Î R "j Î J m , "i Î J p , and t = ( t 1 , t 2 , . . . , t k , t k + 1 , . . . , t m ) Î R
m
, where x j = t j
"j Î J k , i.e., the variables t k + 1 , . . . , t m are continuous and x1 , . . . , x k are combinatorial.
University of Consumer’s Cooperation, Poltava, Ukraine, [email protected]; [email protected]. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 133–146, July–August 200
Data Loading...
