Boolean problem of sequential minimization of moduli of linear functions and stability theorems
- PDF / 106,437 Bytes
- 8 Pages / 595 x 842 pts (A4) Page_size
- 43 Downloads / 150 Views
BOOLEAN PROBLEM OF SEQUENTIAL MINIMIZATION OF MODULI OF LINEAR FUNCTIONS AND STABILITY THEOREMS UDC 519.8
V. A. Emelichev and E. E. Gurevsky
A multicriterion Boolean problem of lexicographic optimization with partial criteria represented by moduli (absolute values) of linear functions is considered. Five types of stability of a set of lexicographic optima under “small” variations in the parameters of a vector criterion are investigated. Keywords: multicriteria Boolean problem, absolute values (moduli) of linear functions, lexicographic optima, stability of a problem with respect to a vector criterion. INTRODUCTION In many publications of works performed by a collective of mathematicians under the direction of academician I. V. Sergienko and published in the journal “Cybernetics and Systems Analysis” [1–8], the questions of correctness, decidability, stability, regularization, and parametric analysis of discrete optimization problems are investigated. In particular, based on the use of properties of point-set mappings, a comparative analysis of five types of stability with respect to functionals and constraints of vector integer problems with linear and quadratic partial criterions is made in [6–8] (see also [9, 10] in which these and many other results are systematized). The mentioned works, as well as other achievements of the collective, substantially stimulated investigations of similar problems in Russia (for example, [11–14]*), Belarus (for example, [15–27]*), Poland [28, 29], and other countries [30]. As is mentioned in [10], the complexity of investigating the problem of stability of discrete optimization problems is basically conditioned by the considerable complexity of discrete models that often become unpredictable even after minor variations in initial data. It is this circumstance that excites modern interest in the investigation of discrete optimization models under uncertainty and risk conditions. The objective of this article is the obtaining of qualitative characteristics of stability of the discrete problem considered here. Namely, for a vector Boolean problem of minimization of moduli of linear functions with the lexicographic optimality principle, an investigation of five most known types of problem stability (T1 - T5 -stability in terms of [6–8, 10]) is pursued. The necessary and sufficient conditions are obtained under which the existence of a vicinity of initial data in the parameter space of the problem is guaranteed and this vicinity is such that any “perturbed” problem with parameters from this vicinity possesses some preassigned invariant property that corresponds to the mentioned types of stability with respect to the initial problem. 1. BASIC DEFINITIONS AND PROPERTIES We assume that m is the number of criteria, n is the number of Boolean variables, x = ( x1 , x 2 , . . . , x n )T
Î X Í En = {0, 1}n , | X | ³ 2 , C i is the ith row of the matrix C = [ c ij ] m ´ n Î R m ´ n , m ³ 1, n ³ 2 , i Î N m = {1, 2, . . . , m}. Let a vector function consisting of moduli of linear functions f
Data Loading...
