Спросить
Войти
CO <D </)
o" CM O CM
CD >Q
PARTIAL STABILITY OF MULTI ATTRIBUTE DECISION-MAKING SOLUTIONS FOR INTERVAL DETERMINED CRITERIA WEIGHTS -THE PROBLEM OF NONLINEAR PROGRAMMING
Radomir R. Bukic
independent researcher, Krusevac, Republic of Serbia,
e-mail: raddjukic@gmail.com,
ORCID iD: https://orcid.org/0000-0002-3799-8009
DOI: 10.5937/vojtehg68-27014; https://doi.org/10.5937/vojtehg68-27014
FIELD: Mathematics, Nonlinear programming ARTICLE TYPE: Original scientific paper
Abstract:
Introduction/purpose: The paper presents a designed procedure for solving a class of nonlinear programming (NLP) tasks with the nonlinear and differentiate objective function, linear natural constraints (intervals of possible arguments values - variables) and the normalization condition for arguments. The procedure was applied to determine the partial stability of the solution of the problem of multi attibute decision-making (MADM). Methods: The basis of the procedure is to define the nodes of argument pairs and their parameters for the allowable multidimensional points. The parameters are implemented in the gradient method, the favorable directions method and the line search method. In the development of the procedure, the basics of the TOPSIS method for MADM with interval-given criteria weights were used, primarily due to the nonlinearity of the reference function.
Results: The paper elaborates the procedure of determining extreme and other admissible solutions of the reference function (boundary and basic solutions) and all vertices of the convex set of the function definition. This forms a complete graph of the function, i.e. the required solutions from the allowable set can be determined. A procedure for determining a set of solutions for defining a separating hyperplane of a set of function values has been developed; in this way, as a specific case, a set of solutions of partial stability of the variant is defined as MADM solutions. Adequate procedures have been proposed to eliminate the degeneration of the procedure (wedging and oscillation of the solution).
Conclusions: The most significant contribution of the paper is the definition of the nodes of argument pairs and their parameters which ensure the
normalization condition in each node and for each allowable point, non-negativity of variables and independence of argument changes in nodes, within active constraints. An original procedure for determining function graphs has been developed. An appropriate real numerical example is given.
Introduction
Problems of nonlinear programming (NLP) with the nonlinear objective function, linear natural constraints of arguments (intervals of possible values of arguments) and the normalization condition for arguments cannot be solved by applying classical NLP methods. The normalization condition implies a constant sum and positive values of arguments in each multidimensional point from the admissible convex set of the function definitions. Relying on the knowledge and procedures from the classical NLP methods (Petric, 1979), (Hadley, 1964), (Zangville, 1969), (Bazaraa et al, 2006), (Luenberger Ye, 2016), developed for problems with or without limitations, the procedure developed in this paper can be applied for the development of the procedure for solving this class of NLP tasks. At the same time, the necessary procedures based on the introduced concept of nodes of arguments (or nodes of criterion) for the problem of multi attribute decision-making (MADM) have been developed, thus transforming the criterion function and constraints and creating a new NLP model based on node parameters. The new model does not contain a singled out normalization condition, because it is built into each feasible point through the node parameters.
As the aim of the paper is conceived on two bases - to show a possible procedure for solving this class of NLP tasks while including consideration of partial stability of MADM solutions - a complex method TOPSIS (Technique for Order Preference by Similarity to Ideal Solution) was chosen as an example (Hwang Yoon, 1981), (Yoon, 1987). The chosen method is based on multiple distances of quantitative indicators of quality of variants (values according to the established criteria - criteria values from the best and most unfavorable existing ("perceived") criteria values. The method was chosen solely because of the nonlinearity of the reference function, since in most other methods this function is linear (VIKOR, MABAC, COPRAS, AHP), and not because of preference over some other methods. The above procedure can also be applied to these,
</) tj>
o" CM o CM
>OH <
CD >Q
as well as other methods with a continuous reference function. The function of partial stability of one variant in relation to the another one represents a set of weight points for which the difference of the reference TOPSIS values of these variants is positive. Feasible weight points are given to components whose values are within a certain interval, which can be the result of determining the value of weights using group methods, combining multiple methods, incomplete or unreliable information, uncertainty of decision makers and the like.
By applying the TOPSIS method, a reference nonlinear objective function is obtained, the constraints of the variables are linear, and their values must meet the normalization condition, which limits the application of standard NLP methods for conditional optimization. Based on the constraints and possible changes in the values of the weight components (variables), the nodes of the pairs of criteria (arguments) are formed. They ensure the normalization condition, non-negativity of variables and independence of weight changes in one node from changes in other nodes, under active constraints. The Cauchy gradient method of the fastest fall (growth) (Vujicic et al, 1980, pp.89-92) and the line search method, adapted to the conditional optimization and characteristics of the nodes of the pairs of criteria, were applied as a basis for the proposed procedure for solving the NLP problem. The first part of the paper defines the function of similarity of a variant to an ideal solution, the nodes of criteria pairs and their characteristics for one variant, and also presents the procedure for determining the extremum of a function (exact and approximate solutions). The way of solving a possible occurrence of degeneration of the procedure (wedging or oscillation of the solution in the "vicinity" of the boundary of the set of feasible solutions) is also shown. In the second part of the paper, the partial stability of one variant in relation to the other ones is defined and the already performed parameter relations for one variant are applied to the partial stability function. Based on the introduced system of basic solutions for the required value of the reference TOPSIS function (separating the hyperplane of the values set of the function), a set of solutions was determined for which one variant is better in relation to the other selected variant. The paper does not explicitly deal with the analysis of the influence of criteria weights on the values of quantitative indicators of variant quality, but with the procedure of determining weight points from the set of admissible points, for which the stability of one variant in relation to the other one from the set of available variants can be determined. As an illustration of the procedure, a corresponding real numerical example is given.
The objective function (the similarity function of the variant to the ideal solution)
An MADM problem: There are m variants yi;i = 1,m e I available ._ and each of them is described with n attributes that are used as criteria I Kj-;j = 1,n e J in the decision-making process: the MADM problem is defined as a requirement to determine the variant yp;peI that is best according to all criteria Kj, as well as a ranking list of all variants. In the decision matrix C = (cij;i = 1,m;j = 1,n} (Cij e R are criteria values), the criteria are associated with numerical values of weights wj e (0,1) with the normalization condition £j=nWj = 1 and the operators - min/max criteria: Lj = -1 (min) or Lj = +1 (max).
The TOPSIS method: It is based on compromise decision making and Lp metrics (Hwang Yoon, 1981), (Zeleny, 1982), (Yoon, 1987) and can be displayed in several steps, when determining:
- Normalized criteria values:
a) Qij = j^cj, for Lj = +1 (maximumX
b) ajj = jJzumcj2, cj = Cj + Cj - Cij,), for Lj = -1 (minimum), (1) where Cj are the best and c,■ are the most unfavorable criteria ("perceived" ideal and anti-ideal)1, when all criteria become maximizing (Lj = +1).
- Distances of Lp metrics for p = 1,j,c» according to the normalized values of the "perceived" ideal y* = (aj = maxj(aij}) and the anti-ideal
y- = (a- = minj {aj}) :
a) tjpi = Lp(yj;yj = [£ j=nwP(aj - ap)p]1 p ,
b) tp., = Lp(V- ;Vi) = [£ j=nwP(aj - aj)p ]1p , P = U» . (2)
- Unified distances of variants from ideals and anti-ideals:
absolute best (desirable) and the worst (undesirable or critical) values of the criteria functions that are outside the perceived best and worst criterion values, thus forming a secondary ideal and anti-ideal.
t* = V pXp,rt*p,,; u=VpxP.rtp/0; p = 1,2,x; (3)
where v i Vp v = 1 are the coefficients of the linear combination in
/v p,r p /1 p,r
the system of three metrics (t1, 12 , t»), which represent the relative reliability of the function tp for the dimension y (e.g. y is the number of
criteria, variants, class, rankings, etc.) (Yoon, 1987, pp.283-284) or are chosen depending on the nature of the problem i.e. on what is required: a greater overall benefit (p = 1), geometric proximity to the ideal (p = 2) or smaller individual maximum deviations of the criteria values (p = <x>) (Opricovic, 1986, pp.45-48).
- Ideal similarity vector S = {si} - similarity (closeness) of the variant Vi to the ideal solution V* with elements (ideal similarity coefficients):
s, = til(t* + u ); 0 < si < 1 ■ (4)
- Rank of variants according to the criterion:
R(i) = maxi(si). (5)
The coefficient of similarity of ideal (4) is a quantitative indicator of the quality of the variant V i at the same time according to all criteria and in relation to the ideal and the anti-ideal (or the degree of "goodness" of the variant). For s, > 0, 5 (when i ti > ti) the variant v, has a greater influence on the variant and the variant is considered to be under the "control" of the ideal (the opposite is also true for fi<t* the anti-ideal).
The similarity function of the variant to the ideal (similarity function) (4), for the constant criterion values Cij e R (1) and one variant v,
(hereinafter the index "i" is implied), can be represented as a real function of n variables - weight Wj e (0;1) for each j e J:
s(w) = Sl (w); w = (Wj e (0;1)}; V j^Wj = 1; for i e Ii j e J , (6) where Vj ==1Wj = 1 is the normalization condition. For the solved MADM problem, the weight components w are given in the intervals w = (Wj) e [Wj,WBj], where wj are the lower limits and WBj the upper
limits of the interval of the values of the weight components (some components can be specified as discrete values). Interval weight estimates can be obtained in the process of group decision making on weights, when applying several objective methods of determining weights, as a consequence of incomplete information or uncertainty of decision-makers and the like. A set of initial weights is formed for each
criterion wp and the lower wf and upper limit values wBP are separated. The starting point of the weight w0P = (wf) has components wf < w]P < wB/ that can be the arithmetic means of several obtained weights (either modal or medial values) or at will chosen weight and for which it is generally £j~Jnw]p * 1. By normalizing these values, the basic
point of weights w0 = (wj) e [wAj,wBj] and £j=JV0 = 1 is obtained, with the limit weights wj and wB whose sums are £ j=nwj < 1 and £j-=1w j > 1. According to the basic point of weights w = (w0j) and expressions (1-5), a basic TOPSIS solution of the MADM problem (w0;s0p = sp(w0)) is obts
Sp(w°) = max {Si(w°);i =1,m}.
The function definition set s(w) is a compact (closed and bounded) and convex set of points we Ec<Rn, such that EcF. A set F is an n-dimensional set bounded by 2n hyperplanes, wj and , and
w = (wj) e [wj.wB] is an n-dimensional point. The point w e F, with the components wj > 0 for each j e J, not connected by the normalization
condition £ j= 1nw0j =1 , is the vertex of the set F only if each component has a value of wj = wj or wj = wB . The vertex of the set F must contain n components: p components wj > 0 for jA e ja c J and q components
(w0;sP = sv(w>)) is obtained or a variant yp,p e I for
> 0 for jB e JB c J , so that 0 < p < n , 0 < q < n , p + q = n , JA JB = J,
and janjb = 0; the total number of vertices is jn (variations with repetition). Since it is wAA +£jBwBjB * 1 in the general case and due to the normalization condition £ j =Jnwj = 1, the set E c F does not contain vertices, and thus not all points of boundaries (edges) and sides of the set F.
A point w e E\\E is a boundary point of a set E c <Rn only if there is wj = wA or wj = wB for at least one j e J , and an inner point w e E -only if there is wA < w. < wB for every j e J, where E is the interior of
the set E. Each vertex of the set E contains n components: p components wAh , q components wbJb (where in 0 < p < n -1, 0 < q < n -1
and p + q = n -1) and a Wr component:
-&ja wja +1jbwb
Wr = 1-(Zw1r + Z,B WB,„) , WAr <Wr < WB ; (7)
which is a condition for some combinations of the values WA and WB to
form the vertex of the set E . As it is wA < (1-ZJawAa -ZJbwBb) < wB , condition (7) in the general case cannot be fulfilled for all 2(n1) possible combinations of the values WA and WB .
A set of function values s( w ) is a set S = {s e [sm;sM]} limited
with the values of the function for extreme solutions: minimum
(w^;sm = s(wm)) and maximum (wM_;sM = s(w^)) . Mapping
s: E ^ S (<Rn ^^) is a surjection: there is at least one point w e E for which there is s(w) = C e S and for each point w e E there is only one
value s(w) = C e S : (Vs(w) e S) (Bw e E); (Vw eE) (3!s(w) = C eS). The set of all solutions forms the graph of the function Ts = {(w; s) e ^n+1 \\w e E,s = s(w) e S} .
The extremes of the function s(w) are obtained as solutions of the NLP problem with a nonlinear objective function, 2n linear constraints, the normalization condition and positive values of the variables:
(min/ max) s(w) ;
Wj ^ WA ; Wj < WBJ ; ZJ=1wj = 1 ; Wj > 0 ; j = 1,n . (8)
The function s(w) on a convex set E is continuous and twice differentiate, but it is not possible to unambiguously determine the convexity or concavity of the function on the whole set E. For a special case and for a constant value s(w) = C, function (4) can be written as C = t /(t* +1-) or Ct* - (1 - C)t = 0. Hence the assertion (Yoon, 1987, p.280) that a function s(w) is convex for the subsets of points w e E\\ c E in which it is s(w) > 0.5, and concave for subsets of points w e e2 = E\\E\\ in which it is s(w) < 0.5. Therefore, each local extremum is also a global extremum, that is, a function has extreme solutions at the boundary of the set E, which are unique in terms of the values of the
function and arguments. The convex function ( s(w) ^ 0.5 ) has a maximum, and the concave (s(w) < 0.5) has a minimum at the vertex of
the set E (Martic, 1978, pp.144-145) and these are exact extreme solutions that meet the optimality criterion. The minimum convex and maximum concave functions are at the boundary of the set (they can also be the vertices of the set E ), and if they are not the vertices of the set E, then they are determined as approximate extreme solutions (incorrect, acceptable) according to the predefined criteria for function values and/or arguments according to real (exact) extreme solutions.
Nodes of the pairs of arguments (criteria)
Defining the nodes of the pairs of arguments (criteria) and their basic parameters is the most important phase of the presented method of solving the NLP problem. Nodes are formed for one variant v and each
pair of criteria r,t e J;r * t and one point Wk. In a narrower sense, the node of the pair (two) of criteria (r,t) is the node of two different components wkj for j = r,t of one point of weight wk : it represents a qualitatively new set of parameters arising from the mutual relations of characteristics (parameters) of current components wkr and wk.
The transition from the initial to a new solution is done by changing the starting point wk to a new point of weights wk+1, where k = 0,1,2,..., is
the mark of the iterative solution. The basic parameters of the point wk are:
Active constraints of the criteria df and df (possible changes in weight components) at the point wk for the intervals [wAj,wBj] :
jAk k A ^ n . jBk B k ^ n. jAB iAk . Bk B A ■ _ j /Q\\
dj = Wj - Wj ^ 0; dj = Wj - Wj ^ 0; dj = dj + dj = Wj - Wj, j e J, (9)
where dAk ^ 0 is the largest possible decrease, dBjk ^ 0 is the largest possible increase in weight Wk, and dAB ^ 0 is the size of the interval [wLjWL.] • The values df and df ^ 0 and their sums £&r^df and £ijj=idBjk can be related by any sign (<, =,>).
The vector of change (increment) is the weight vk : when changing the point Wk to the point Wk+1, the new point Wk+1 = Wk + vk, where the
vk = (vj) vector of change (increment) is the weight. The values vk can
be * 0 or = 0, which is why non-negative values are introduced vf,vf > 0 (vf > 0 reduction and vf > 0 increase weight wkj ):
a) vf = - vk > 0, vAk g [0,dAk] ; za v) < 0;
b) vBk = v) > 0, vf g [0,dBk], za v) > 0. (10) The values of the weight components at the new point wk+1 are2:
k+1 k . k k . Bk Ak
= w,- + v,- = Wj + v,- -v,- . (ll)
where for each component Wkj (11) at least one of the values vAk or vBk is equal to 0.
The gradient of function: from the development of function (6) into Taylor&s polynomial of the first degree:
s(wk+1) = sW) + vs(W_Xwkl - W.) + R1 = s( wk) + a(WL) + R1 (12)
and for the value of the remainder r1 «0, the auxiliary function
ak = cr(Wk) is equal to:
a(wk) = Vs(wk;(wk+1 - wk) = Vs(wk)(vBk - vAL) ; (13)
where Vs(W^) = {ds(wk_)/d
wj} ■=m the gradient of the function s(w) is at the point Wk. Approximate values of the gradient components gk = gj(Wk)«ds(Wk)j8Wkj can be calculated by the method of double increment of variables (Milovanovic Stanimirovic, 2002, p.114):
gk = [s(wjk+) - s(wJ,k -)]/25; S> 0; j e J, (14)
where points J = (w1 ,■■■ ,wk + 5,••• ,wkn) and wJk_ = (w1 ,••• ,wk-5,••• ,wkn), and 5> 0 the increment is small (e.g. 5 = 10~6 or less).
Node parameters
For the transition from the point Wk to the point Wk+: and with the
normalization condition ZJIw = 1, it is necessary to change the weights of at least two criteria r,t e J that form a node (r,t) with a unique value
The index k = 0,1,2,..., indicates the quantities in the point wk (eg: sk, ck, df, d(rt), gk, gk(r ) and the quantities that "come out" of it (eg: vk, vAk, zk(r,t>, rk(r,t)).
of weight changes VAkt) = vB(kr) > 0 and the direction of changes: VAk0 is the reduction of the weight Wkr, and vB(kr) is the increase of the weight Wk. The components r,t e J of the point Wk+1 are equal to:
k+1 k Ak . k+1 k | Bk . Ak Bk n. „ t — t / ^ o
Wr = Wr - Vr(t)& Wt = Wt + Vt(r)& Vr(t) = Vr(t) > 0; r,t e J > (15)
while the other components are unchanged Wkj+1 = Wk, j e J\\{r,t}. A set of nodes is formed for a known solution
© = {(r,t)\\r,t e J,r ± t} (16)
with n(n -1 ) elements in total. The basic characteristics of the nodes are:
Active constraints of nodes d^^t) = d(rt)(Wk) depend on a possible
decrease in the r-component and on an increase of the t-component weight in nodes (9) (available resources):
= min(dAk;dBk) > 0; (r,t) e©
(r,t) = i 0; r = t, [(r,t) <£©]
dkrt) H & \\ , (17)
where the matrix Dk =(d(rt))nxn for r,t e J.
Variables z(rtt): variables z(rtt) > 0 are introduced, whose values show the change of the weight components in the nodes, whereby a square matrix zk = (z(r,t))nxn is formed, with the following elements:
k N dkr,t) > 0, (r, t) e©
a Z(r,tf
j )-U(r, t)= 0; r = t, [(r,t) g© ] &
b) zk(r,t) = vA() = vfr) > 0 • (18)
Since vAkt) = vBkr), the values of the variables z(rtt) > 0 are conditional and compensatory values of the weight changes in the node (r,t), and their summation in the nodes (r,t) e© gives the total increase vAk or decrease vtB( of each weight component:
n\\ V ,Ak Ak , . Ak S^t=n Ak s^t=n k ^ ,Ak
a) j = r ^ vr = Vr( 1) + + Vr(n) = £t=1 Vr(t) = £t=1 Z(r,t) < dr ,
[i ; > v Bk Bk . . Bk ^r=n Bk ^r=n k ^ yBk
b) j =t ^ vt = vt(1) + • + vt(n) = £r=1Vt(r) = £r=1 z(r,t) < dt ,
c) £ j =nvBk -£ j =nvAk = 0. (19)
The normalization condition is provided in each node and does not need to be considered further. The condition from the starting point of weights Zj=„W0 = 1 (11) is also contained in the point W1 because of
(19c): ZJ=nw) = ZJ=nw0 + ZJ=M0 - Z J=nvA0 = 1. The normalization condition
is transformed into ZJ ==nvf - ZfJtvf = 0 or ZJ ==„v_j = 0 and is contained in
each node (r,t) and for each point WkeE in any iteration k = 0,1, 2,...,.
Gradient function in the node gk f,: the increment of the value of the
- £>(r,t)
auxiliary function (13) for the node (r,t) is:
ckr,t) = (8s(W)/8w_)-vBl)-(8s(w_)j8w_)-vA_0. (20)
By changing gk*8s(m_)/8w_ for gl and gk (14) and ^0
(19a, b) expression (20) becomes:
c(zkr t)) « zkr,t)(gk -gk) = Z(r,t) ■ glt), g&kr,t) = g(z(r,t)) , (21)
where gkrt) = g t)(Wk) is the approximate value of the gradient function
component s(w) in the node (r , t) e0k. The values gkr t) for all nodes
(r,t) form a square antisymmetric matrix Gk = (gkrt))„x„ with the elements:
/ =1 gk - gk; (r,t) e0k (22)
(r,t) 10; r = t, [(r,t)£0k]& where gk(rt) = - gk(tr). The approximate total change in the value of the function s(Wk) for all nodes (r,t) e@k, according to (21), is equal to:
c(Zk) = Z(r,o g(zkrt)) zkrt), (r,t) e 0k . (23)
Possible changes in the function values by the nodes Tk(rt) are derived values based on the values of the elements of the matrix d_ (18) and g_ (22). A matrix t_ = (xk(r,t))nxn is formed, with the elements:
^ jf&^0;& °;dk-j) >0, (r,»^ (24)
I 0 za g(r,t)=0 ih d(r,t)=0
The active nodes in the point wk are the nodes (r , t) e©- <u©++, and
of which there may be at most n (n-1) elements Tkrt) * 0. This defines the basic characteristics of the nodes (r , t): dkr,t), gkr t) and Tkrtt) and the variables zkrt), shown in Table 1.
Active nodes
The characteristic Tkrt) * 0, as a derived quantity, is the most significant indicator of the possibility of changing the value of the function in the node (r, t) for the current point wk. Based on the values Tkrt) * 0,
the matrix t- with the elements that are 0 or Tkr t) < 0 and the matrix t+ with the elements that are 0 or Tkr t) > 0; this determines the subsets of active nodes ©- and ©+ at the point wk:
a) ©- = {(r, t)\\Tk(, t) < 0} ^©k ;
b) ©++ = {(r , t)\\Tkr _ t) > 0} ^©k . (25)
the active gradient components are only the components gK(r t) * 0 in the
active nodes (the nodes in which there are gkr t) * 0 and dkr,t) = 0 are not
active nodes). According to the influence on the value of the function (increase or decrease), i.e. for determining the extreme of the function (minimum, maximum), active nodes are the nodes (r,t) e©- for decreasing the value or determining the minimum of the function and the nodes (r , t) e ©+ for increasing the value or determining the maximum of the function. Active gradient components are only the components gkr t) < 0 (min) or gkr t) > 0 (max) in the active nodes (Tkr,t) * 0). The sum
£(r,t)Wkr,t)\\=£(r,t)\\gkr.t)\\dkr,t)> 0 for the node (r,t)e©- is the largest possible decrease, and for the node (r,t) e©++ the largest possible increase of the value of the function s(w) is at the point wk. The value £.(r,t)\\Tkrt)\\ can also be a criterion for accepting the achieved solution as an approximate extreme solution and for interrupting the iterative procedure if £(r,t)\\rkr,t)\\^sT for (r,t)e©- (min) or (r,t)e©+ (max),
</) tj>
o" CM o CM
>OH <
CD >Q
because the improvement of the function value in the next iteration cannot be greater than the defined value St (e g- 5• 1° 5)■
The formation of the nodes (r,t) e0k ensures that the normalization condition Z= 1 (or Z%"vkj = 0 ) is contained in each point wk e E the non-negativity of the variables zk(rtt) > 0 and the independence of weight
changes in a particular node (r,t) e0k from changes in the other nodes, with active limitations of criteria (18, 19).
Extreme solutions of the objective function (similarity functions)
The extremes of the function s = s(w) (8) are determined by an iterative procedure starting from some feasible solution (wk;sk) which, in general, is not extreme. Improving the initial solution is possible only if there is at least one node (r,t) e0k_ (25a) (decrease in the value sk ) or only if there is at least one node (r,t) e0kk (25b) (increase in the value sk)■ According to expression (13), the current solution (wk:sk) is improved by increasing (decreasing) the value of the auxiliary function a(Zk) (13, 23), when the nodes taken into account are only the nodes (r,t) e 0k in which weight changes contribute to the improvement of the value of the auxiliary function o(zk ) ■
The iterative procedure determines the boundary solutions (wkk1 e E\\E ;sk ) with the improved function s(w) values, i.e. the
boundary points (wkk1 = wk*)eE\\E that will give an improved TOPSIS
solution (2-4), while active constraints allow it. At the end of the procedure, a solution will be obtained at the point at the vertex of the set E , which will be the exact extreme solution wk* = (wm vwM)eE\\E or
the initial solution for a further procedure and determination of the approximate extreme solution. In both cases, there is a single iterative procedure by which an admissible solution is obtained at the vertex of the set E , from which no better solution can be obtained at any vertex of the set E.
Exact extreme solutions
For the initial solution (wk;sk), usually k=0, it is convenient to form a
table similar to Table 1 which contains the values of the active constraints dAk and dBk (9), the node characteristics (r ,t) - the elements
of the matrices Dk (17), Gk (22) and Tk (24) at the point w, the partial
sums gkr t) and Tkrtt) dependent on the active nodes ©- or ©-, the
space for writing variables z(kr t ) and their sums as the components of the
vector / = (vk.).
The extremes of the function s(w) (8) are determined as the solutions of the NLP problem with restrictions on the weight changes in the nodes z(, ,,t) < dkr,t) > 0 (18) and according to the criteria
£t=nzkr.t) < dAk > 0 and £rmzkrt) < dBk > 0 (19), that is, from the condition that the points of extremes are admissible, and, at the same time, the boundary points wk+1 eE\\E.
The mathematical model NLP (8) was transformed according to the node parameters and a new model was formed containing the nonlinear objective function (due to the multiple differentiability of the function s(w)
and the nonlinearity of the function g( zkrtt))), n(n +1) linear constraints (the normalization condition £j =Jnwj = 1 is contained in the nodes parameters) and for n(n -1) variables zkr 11) > 0, with indices as in Table 1:
(min/ max) a(Zk) = £r„ t) g(zkr 11)) z(, ,t), zkr,t) < dkr,t), n(n-1) constraints,
£TJzkr,t) < dAk, n constraints, (26)
£r;= Izkrt) < dBk, n constraints,
zkr,t) > 0; (r, t) e©k- (min) or (r, t) e ©+ (max).
The NLP task (8,26) is solved by applying an iterative procedure based on the first-order gradient method or the Cauchy method of the
</) tj>
o" CM o CM
>OH <
CD >Q
fastest drop (growth) of the value of the function s(w)3 adapted for the application of node parameters. The direction of the antigradient - Vs(wk) is also the direction of the fastest decrease in the value of the
function s(w) at the point wk, that is, it is the most favorable direction from the point wk for determining the minimum (Vujicic et al, 1980, p.89); the direction of the gradient Vs(wk) is the most favorable direction for determining the maximum.
Through the starting point wk, in addition to the most favorable
direction, countless other favorable directions can be drawn that will contain the characteristics of one or more active nodes4. The aim is to determine the point wk+1 e E at which the TOPSIS value of the function
skk1 is better than the value sk in the chosen favorable direction and in accordance with the limitations in model (26).
Solving problem (26) requires at least one known feasible solution (wk;sk) (basic TOPSIS solution (w0;s°) or any other feasible solution),
for which there is at least one node (r , t) e0- (minimum) or at least one node (r , t) e0k+ (maximum) (25). Based on the values of all active components of the gradient at the point wk, the most favorable direction
or the direction of the fastest fall (growth) of the objective function is set through it. Active nodes are determined depending on the required extreme: (r, t) e0- (min) or (r, t) e©\\ (max). The most n(n -1 )/2 active nodes are possible for each required extremum, that is, it is the largest number of elements of the sets q- and @k+ for the inner point w e E. In the intersection of the most favorable direction and some, unknown in advance, hyperplane of the set E - wj or wB, there is the boundary
point (wk* = wkk1 ) e E\\E :
k* k , k / k , k 1 / k , Bk Ak i. • ^ j
w -w k ^-(Wj k Vj) -fWj k Vj - Vj J e J .
Table 1 - Parameters of the point w and the nodes (r, t) for the NLP model Таблица 1 - Параметры точки wk и узлов (r, t) для модели НЛП Табела 1 - Параметри тачке wk и чворова (r,t) за модел НЛП
j =1 1 n
j =r jAk \\ jBk dr \\dt ,Bk d i -¡Bk dn sums*
k k gr \\gt k gi k g n
d i 0 Лk d( i, n)
k T(r,t) 0 k T( i, n) 2t_iT(i,t) l
k z(r,t) 0 k Z( i,n) •\\r.t_n k Ak L,t_i Z(i,t)~ Vi
-¡Ak dn ik U(n, 1) 0
n k g n k g(n, 1) 0 Tt=nl£k l ¿->t_ ilS (n,t)
k T(r, t) k T(n, 1) 0 Yt_nTk l
k z(r,t) k Z(n, 1) 0 x~^t_n k Ak L,t_i Z(n,t)~ Vn
yr=m gk | r=1 1 О (r ,i ) vr=ni k ^r=i lg(r,n) 1
sums* 2r=iT(r, i )l y=nlTk l ^r =i \\ l(r,n) r,t )lT(r,t )l
^r_n k Bk L,r=1 Z(r, 1) - Vi x-^r-n k _ Bk Z^r_i Z(r,n) Vn
О) (N Ю
*sums g(rt) and Tkr,t) are determined in relation to (r,t) e©k or (r,t) e©^
Minimum problem: The direction of the fastest fall is the direction of the antigradient -Vs(wk), that is, the direction of the antigradient vector
in the active nodes for the point wk (the gradient vector is the sum of the gradient vectors gk(r t) < 0;(r, t) e@- of the active components); the values of the variables zkr,t) > 0, (r, t) e@- (18,19) have the same
■c ra CL
o" CM o CM
OH z>
interrelationship (proportionality) as the values of the active components of the gradient5:
zkr,t)-ju\\gk(r,t)\\;(r,t)e Q- , (28)
where rf > 0, the unique coefficient (proportionality) of weight increment for all active nodes, depends on the active constraints in the nodes (dkr.t) > 0 ) and the criteria (dAk > 0 and dBk > 0 ); it is necessary to
ensure, when passing the point wk e E to the boundary point wk* e E\\E :
o a) that the point wk* (27) is a feasible point; b) that wk* is in the most
< favorable direction; and, c) that the active constraints of the nodes and the criteria are met to the maximum (to achieve the maximum possible
> are obtained on the basis of the following considerations:
< 1) Active constraints in the nodes zkr,t) ^ dkr,t) > 0,(r , t) eQ- (18): for
the boundary case z^-d^> 0 and zU)-4U^Ui-dU);^,t)eQ-, where £k t, > 0 is the node coefficient. The lowest value <Ek t, > 0 in all
Wr, t) ^s(r, t)
nodes allows at least one resource dkr - active constraint to be fully
CD (r ,t)
g utilized and that dk**,t) - 0, based on which the coefficient of active nodes i is determined £k > 0 :
° a) M--, o/\\gkr ,, t)\\> 0 ;(r t) e Q- .
o (r,tt} 1^0; (r, t) £0-_
b) t = nmi(r.t){t(r,t)>^(r.t)^0ki}. (29)
In the following text, for a simpler presentation, the components of the gradient
gft) < 0;(r,t) e ©-- and g^ > 0;(r,t) e ©k+ are rep^ced by | |> 0 for(r , t) e ©(min) or (r, t) e©k (max).
utilized and there should be df =0 or df =0 at least for one j = J. The weight components for one criterion (27) are v) = vf - vf, where in the final outcome vf = 0 or vf = 0. The change of the component vk depends on partial changes in the row and column of the same index | j = r = t in the matrix Gk: changes in the row j = r are
tt=nzkr,t) = vf = wkZt=1\\gk(r ,t) > 0, and in the column j = t they are
TZnzkr,t) = vf = jZ7=1\\gk(r,t)\\>0, where ¥k >0 is the coefficient of proportionality for the _/&th-criterion. It follows that vk = vkjrz=n\\gk(r.j)\\-ZT^gkjtoU, where the sums in the parentheses [.] can be connected by any sign (<, =,>), when three cases are possible: a)
vk < 0vAk, followed by vj = -vAk and vBk = 0; b) vk > 0, followed by vk = vf
and vf = 0; and, c) vk = vf = vf = 0. For boundary cases, when j = df > 0 or vf = dAjk > 0, the coefficients of the criteria () and the coefficient of all criteria (yk) are obtained:
df/(Zt=n\\gk(J,t)\\-Zr=n\\gk(r,n\\)>0; for Zt=1\\gk(U)\\>Z% 1\\gt df&l(Zr=1\\g^(r,])\\-Zt=n\\g(w\\)>0; for zr=n\\gk(rj)\\>Zt=1\\gk
( \\; ( r,j) \\;
a) W]=b) y/k = minj{tykj > 0; j e J} . (30)
(r,j)\\ ¿-t= HÔ (j,t)f"< J- ^r=VS (r,j)^ ^t=V (j,t)\\>
for zt=n\\gk(ht)\\= Zr=n\\gk(r,])\\; (r,j),(j,t)e©-;
The transition from the point wk e E, which can be a boundary or an inner point, to the boundary point wk*eE\\E in the direction of the fastest fall, is realized for the value of the unique coefficient:
ff = min{f > 0;yk > 0}, for ©- , (31)
where the values Ef and can be associated with any sign
(<,=,>). Expressions (27-31) are key to determining exact extreme solutions using active node parameters.
In the further procedure, the values of the variables zk(r,t) ^ 0 are calculated (28) as well as the values of the weight increments vf = Zt=nZk(j,t) ^ 0 (the sum zk(jt) in the rows of the matrix zk ) and
vf = Zri&zkr.j) > 0 (the sum zk(r,t) in the columns of the matrix zk ) (19),
>Q! <
together with the components of the point weight w (27), and then the TOPSIS solution (wk*;sk*) (2-4) is determined.
<3 Maximum problem: Expressions (27-31) and (2-4) are used to
> determine the solution (wk*;sk*), so that the nodes (r,t) e ©k_ (25a) are
replaced by the nodes (r, t) e ©kk (25b), and the matrices jk - by the
of matrices jk
^ Optimality solution: In the continuation of the examination procedure,
o the obtained solution (wk*;sk*) is obtained according to two criteria:
< - basic criterion:
° a) sk* < sk (min); b) sk* > sk (max); (32)
- optimality criterion:
a) Tk*rt)-gk*r,t)dk*r.t) ^ 0; for every (r, t) e0k* (min), or
b) Tk:,t)-gC,t)dk:,0 ^ 0; for every (r, t) eQk* (max), (33)
when three cases can occur:
for the (k+1) iteration, when the node parameters in Table 1 are calculated and the procedure is repeated (27-33); the procedure is v repeated until solutions are obtained according to cases 2 or 3; x 2) criteria (32) and (33) are met: the exact extreme solution was
¡5 reached at the vertex of the set E ;
(wk*;sk*) are the initial solutions for the procedure of determining the
approximate extreme solution (the case when (32) is not fulfilled, and when it is fulfilled, (33) is impossible).
For the starting inner point of the weights wk=0 e E, the number of active nodes (r, t) e©k and (r , t) e©k is equal to n(n k i)/ 2. If there is an exact extreme solution (wm;sm) or (wM;sM) (33) and, during the
procedure, in each iteration, %k >^k > 0 and /u = \\yk (31), and there is
no degeneration - oscillation, then the solution is achieved after the iteration k = n k i. After each k = 1,2, — iteration, the number of active nodes decreases and is equal to (n k k)(n k k k i)/ 2. At the end of the procedure and after iterations, there is only one active node, and at the
point wk after k = n -1 iterations, there are no active nodes: 0k_ = 0
(min) or 0+ = 0 (max). From the beginning of the procedure in each subsequent iteration, the value of the possible total weight change £(r,t)\\Tk(r,t) \\ in the active nodes decreases; for the exact extreme solution |
is £(r, t)\\Tk(*r, t)\\= 0 and there is no possibility of further improvement of the function value. The number of iterations increases if oscillation or wedging (discussed below) appear "near" the hyperplane W or wB.
Approximate extreme solutions
Determining approximate extreme solutions is necessary in the case when the extreme solution is not at the vertex of the set E and when criteria (32) and (33) are not met. One of possible solutions is the line search procedure6, adjusted to node parameters, where the number of iterations should be as small as possible. The absence of an exact extreme solution is manifested in the iteration by which it would be obtained, when there is only one active node and when the value of the function sk* is not better than the value sk. Instead of £(r^)\\rk(*r,t)\\= 0, new active nodes appear that did not exist previously7; this means that on the direction [wk, w(r] there is a value of the function that is better
than sk and sk* (it does not have to be an extreme value, because it can be located at the point w which is not on the current direction). First, the known segment of the direction [wk,wk*] is examined, and if a solution
described procedure is continued by choosing the most favorable direction (27-31), due to the change of the gradient sign in previously active nodes, they will become inactive, and new active nodes will appear that did not exist at the beginning of the procedure - for the initial solution (wk;sk). For the obtained new solution, the value of the function may be
even better than the value s(r, but criterion (33) will not be met; then, a new solution is obtained from this solution, etc., until after several iterations, the solution ( wkr;skr ) is
obtained again, when the procedure begins to "circle" over the already obtained solutions. There does not have to be a solution (wk;sk) among these solutions.
that meets the set criteria is not found on it, then, by applying the procedure based on the direction of the fastest fall (growth), a new search segment is determined. s The segment of the direction fwk,wk*] is divided into several equal
° mark of the points on the segment of the direction, and nk ^ 4 is both the
ft number of equal search steps and the number of equal subsegments
S (integer) which provides search for a sufficient number of points for
o smaller subsegments. The following points are generated on a segment
^ of the direction fwkS0,wk-"k] :
w where ck e (0; 1/4) is the constant size of the weight change step in each £ of nk > 4 equal steps in total; expression (34) is a linear combination of
wkl = wkl+ lavf; fori = 1,2,...,nk -1; (34)
the points wk 0 and wk&"k : wk,l = (1 - la)wkfi + lakwk
The criteria for accepting the approximate solution (wk:l;sk&l) as an
extreme solution and for stopping the iterative procedure are defined < here in relation to the values of the function and the values of the « arguments (criteria weights) for three consecutive iterative solutions: - basic criterion:
a) sk&1 1 > sk&1 < sk&l+1 ; (min),
O f\\ k,l k,l-1 I . I k,l+1 k,l I ) ^ .
,----- {\\wj - wj \\,\\wj - wj \\j ^Sw ; (36)
^ b) skl< skl > skJ+1; (max); (35)
- argument value criterion:
f\\ k, l k, l-1 | . maxj{\\wj -Wj \\AWj -w
- function value criterion: max{\\ skJ - s"-11 .• I su+l ~ skJ I}<e,\\ (37)
where l = 1, 2,..., nk -1, and Sw,ss > 0 are the parameters of small values.
The number of steps nk and the size of the steps ak are determined depending on the selected parameter Sw (36):
nk >(maxj {\\w]jnk - wk/0 \\}/sw) + 3 (n - the first major integer); (38)
cck = 1/nk , ak e (0;1/4 j. (39)
whereby criterion (36) is met. The increments of the weight components (akvki) are constant, and, with nk > 4, it is ensured that at least three
points wkJ are determined on each segment [wks>, wk,n ] and the value of the limit parameter is achieved:
skw=maxj {\\w(jnk - wk/0 \\}/nk) < sw • (40)
The choice of parameter values Sw and Ss can be based on the £ sensitivity of the value of the function to changes in the value of arguments in the extremum environment. Although the criteria for stopping the optimization process can be based on the norms of the arguments \\\\wk+1 - wk \\\\/\\\\wk \\\\< sw and the function values
\\ s(wk+l) - s(_w_) \\/s(wk) <
ss in two consecutive iterations, for the current
NLP problem, the parallel application of criteria (36,37) in three iterations is favorable. Criterion (36) limits the largest individual weight changes via the parameter Sw (40), so that the largest weight increment is
maxjavk = skw <Sw The sensitivity of the value of a function (ok) , as a criterion for the selection of parameters sw and ss , can be defined as the ratio of changes in the value of the function and the maximum change of individual weights, i.e. as the ratio of the realized parameters sw<Sw and sk for a certain subsegment: ok = sk/skw. Numerical results for TOPSIS solutions show greater sensitivity of argument values (weight) than function values, because it is ok = skJskw < 1 or sks <skw, which should focus on the choice of the parametersw . The parameters sw and ss can also be determined depending on the required accuracy of the values of arguments and functions: in order to round the values of weights and the function of the target to four exact decimal digits, it is
enough to set sw = 5 ■ 10 5, which ensures sks < 5 • 10 5.
In the set of solutions (wk,l,sk&l;l = 1,2,...,nk -1 ), there does not have
to be a solution for which sk,l < sk 0 (min) or sk,l > sk 0 (max), because
such a solution can also be in the first subsegment [wk,0;wk,l 1 ]. Therefore, for the sake of generality of the procedure, a point wk,a is
determined on the segment [wk0,wk,nk] in which the function has the value:
a) sk,a = minl{sk; l = 1,2,....,a- 1,a,a + l,...,nk-1} (min),
b) sk,a = maxl{sk; l = 1,2,....,a- 1,a,a + \\,...,nk-1} (max). (41)
</) tj>
o" CM o CM
>OH <
CD >Q
There is an improved solution on the subsegment fwk,a 1;wk,a+1 ] :
according to the selected Sw and for nk ^ 4 which provides at least four new intervals, determine the required parameters (38-40), search the subsegment and determine the TOPSIS solution according to the criteria (35,37).
The disadvantage of the procedure based on fulfilling criterion (36) is a large number of generated wkJ points on the segment fwk 0,wk,nk],
especially for larger interval widths, when the values of the sk,l function and other required quantities need to be calculated for several hundred generated wkJ points.
For the solved MADM problem procedure will satisfy criteria (35-37), knowing that due to the nonlinearity of the function gradient in the nodes g(zk(rt)) and the appearance of new active nodes, the exact solution will
be outside the direction fwk;wk*]. For the sake of generality of the
procedure and reduction of error according to criteria (36,37), a two-phase procedure can be applied: a) linear search and determination of the best solution in the segment fwk;wk*], it can also be the solution
fwk+l = wk&a;sk■a] ; and, b) determining a new segment between the
obtained solution and the solution on the hyperplanes wor w. If the
point wk+l is where the best solution is achieved on the segment
fwk;wk*], a new direction of the fastest fall (growth) is set through it and
a point w(k+l)* is determined. On the new segment fwk+1;w(k+1 )*], the
value of the function is calculated at the newly generated points, etc. The two-phase procedure is repeated until criteria (35,37) are met. In general, an approximately extreme solution was obtained in two steps with a smaller error, but the procedure is much longer.
Procedure degenerations: wedging and oscillation The presented procedure for determining a point on one hyperplane requires that in each iteration at least one component of weight w( ,
which is different from the limit values wj < wkj < wBj, have a value wk* = wA or wk** = wB at the new point wk* and is in the direction of the fastest fall (growth). These requirements cannot be met if wedging
occurs: starting from some k-th iteration and a point wk that can be an inner or boundary point, through all subsequent iterations, the points "accumulate" "near" the hyperplane wj or wBj and some expected
boundary point w(r which cannot be reached in a finite number of § iterations. The expected point w(r cannot be an extreme point, because
wedging does not appear in the iteration in which the extreme solution is obtained; this iteration is preceded by only one active node, and for the occurrence of wedging there must be two or more active nodes, which facilitates the elimination of the problem. The possibility of wedging cannot be established at the initial stage of the proceedings.
Wedging occurs (but not necessarily) when the coefficient of active
nodes %k (29) is smaller than the coefficient of all criteria ^ (30): / = % <^k (31). As a consequence, none of the active constraints under criteria (19a, b) that had a positive value df > 0 or dBf > 0 in the point wk, will be fully utilized to achieve that df = 0 or dBk* = 0 for at least one j = J. Through several iterations, the unique coefficient
/ = % <^k (31) decreases and / ^ 0, due to successive reduction
% = %f(rt) > 0. In each subsequent iteration, the values of the weight
changes per node zkr,t) = /i\\gk(rt)\\ decrease as well as the increment of
the value of the objective function. When the process enters wedging, the number and indices of active nodes do not change, so that all the components of the direction vector that were active at the starting point wk exist.
The / = % < y/k disorder can disappear by the algorithm: if in some subsequent iteration in the second node (p, q) % = q) <%f(r t) and
£k . >wk. are achieved, then the most favorable direction towards £k .
p, q) Yj& p, q)
will be chosen, and the active node (r t ) will have no effect or will become an inactive node.
Unlike some possible ways to solve the problem of wedging, e.g. s -approximation (Zangville, 1969) for the current problem of NLP and based on relative independence of active nodes, a procedure based on
changing the direction can be applied: a new direction is chosen from a set of favorable directions which exclude individual active nodes. In any iteration after the occurrence of wedging, at the obtained point wk close
to the expected boundary point wk*, a new and less favorable direction is
o~ selected based on the characteristics of all active nodes except the node
cm (r, t) which is the cause of wedging and is found to be ¡1 =£(rt). By
^ setting gk(rt) = 0 for that node (current iteration only), the node (r,t) is
o excluded from the set of active nodes (25) and the new direction is selected in accordance with the characteristics of the remaining active o nodes using expression (29-31). This does not disturb the procedure, x because a favorable direction is chosen, but after obtaining a new
CJ ir* k+1
uu boundary point wk , the current value g(rt) * 0 must be returned to the
£ procedure for the node (r,t), so that the node (r,t) can become an
active node again if it satisfies conditions (25), when again the most favorable direction is chosen (29-31). There is a possibility that in several consecutive iterations the selected favorable directions must be changed and the number of active nodes successively reduced, until at some step
it is obtained that it is ¡U = yk <%k > 0 , when the procedure continues by
procedure.
w As the extreme solution does not depend on the initial solution or on
o the secondary solutions that are a consequence of choosing one of the g favorable directions (based on the characteristics of all or only some active nodes), it gives the possibility to simplify the problem of wedging
by: always when ¡u =%k = £ t) <^k, set the gkr t) = 0 for the node (r, t)
and select another favorable direction, and in the (k+1) iteration, include
the calculated value of gk+1i) * 0 in the procedure of selecting the most
favorable direction. This prevents the occurrence of wedging, that is, automates its removal, and the whole procedure is extended by several iterations at the most.
A special form of degeneration can be described as an oscillation of the value of the wk component in the vicinity of a hyperplane. For example: in the k-th iteration for the r-th component of the point wk , the value wkr = wf is reached. In the normal course of the procedure, the
already reached values on the hyperplane wj or W do not change until the end of the procedure, which is not the case with oscillations: instead of wkr = wkr+1 = wA, the wkr+1 > WA value close to wA is obtained in the (k+1)
k+1 A
iteration, while for some other component the boundary value w(+1 = wf &|j or w(+1 = wBt is reached. In one of the following iterations, the value of wj is reached again for the r-th component, but wedging can also occur. The oscillation can also be repeated on the same hyperplane, when the w(+1 - wA differences also decrease. Apart from increasing the number of iterations, the oscillations do not affect the final solution, and the wedging is removed in the described way.
Partial stability of solutions
The stability of the MADM solution - the variant Vp \\ (w, Sp (w)); P e I is defined in relation to all other variants Vq\\(w.; sq(w);qeI\\{p} and represents the set of points w e Ep ç E for which it is
Sp(w) > Sq(w); p e I;q e I\\{p} .
The partial stability of the solution VP\\(w.;sP(w)) is determined in relation to one of the other variants Vq;qeI\\{p} : The solution Vp\\(w;sp(w)) is stable in relation to the solution Vq\\(w.;sq(w.)) for all points w e Epq ç E for which the function of partial stability is:
hpq(w) = Sp(w) - Sq(w) > 0; p,q e I,p * q, (42)
that is, if it is sp(w)/sq(w) > 1. For smp > sf , the solution (w;Sp(w)) is stable in relation to the solution (w;Sq(w)) at each point w e E (Figure 1a) and therefore the determination of partial stability makes sense only if Sp n Sq , ie, if sMP > sm a sp < sMq (Figure 1: b,c,d,e). The function hpq(w) is concave or convex, continuous and differentiable on the
convex set E, and the local extreme is also the global extreme.
The set of values of the function is Jfq = {hpq e [hmvq;hMvq]} for
p,q e I and p * q or the line segment hmpq;htMq ■
о" СМ О СМ
УУ 0£ ZD О
>он <
со <
О >о
X ш I—
The extremes of the function hpq(w) follow from the function development kpq(wk+1 ) = ht™ into the Taylor&s polynomial of the first
degree (12): h%1 = (sp - skq) + о
sk = C. The auxiliary
function of о pq , according to (13,21), is equal to:
Z(r,t)( S p(r,t) gq(r,t)) z(r,t) Z(r,t)S
> pq(r,t)Z( r,t)
—о •
; (r,t)se. (43)
Figure 1 - Possible relations of the set of function values si(w) of two variants Рис. 1 - Возможные отношения множеств значений функций Si(w) двух
вариантов
Слика 1 - МогуПи односи скупова вредности функци^а Si(w) две варианте
The values of the function gradient components hpq(w) ¡n the nodes (r,t) e are:
Sk = I Sp(r,t)
^pq(rt) 1 0; r = t, [(r, t) £0k]
- gq(r,ty (r,t) S0k
and the elements are antisymmetric matrices Gpq(wk) = Gkpq = (gkpq(r,t))nXn ■ To determine the extremes, it is sufficient to
determine the points of weight w in which the nonlinear auxiliary function <7pq(w) (43) has extreme values, and then the corresponding TOPSIS solutions. Starting from an admissible solution (let that be the solution at the starting point (w0;h0pq) ), by applying the presented procedure for
determining the extremum of the function s, (w) (27-41) and by
calculating the values g
(22, 44), dA, d? and dk(r,t) (9, 17) in
each iteration, the extreme solutions of (wm;hmpq < 0) and (wM;kqpPq > 0) are obtained.
The separating hyperplane of the value set of the function hpq = CR is defined by any value8 of the h = CR\\hm <CR <hM function and divides | the value set of the function S = {h e [hm;hM]} ç^ into two subsets:
S- = {h\\hp<h<CR}çS and S + = {h\\hM>h>CR}çS, where S^^S+ = S
and s- n S+ = 0 . An acceptable approximate value of the function in the vicinity of the separating hyperplane of h = CR is:
hC=Ce[CR ±sc]; k = 0,1,2..., (45)
where sc is a low value parameter (e.g. sc = 5 • 10 5 or less). The procedure for determining the set of solutions on the separating hyperplane of (w;hC = C) has several phases, where it is determined: the set of 2n boundary solutions and their extremes; basic boundary solutions for hC = C (if any) or basic solutions that are closest to the current hyperplane wj or wBj ; and, a set of solutions for hC = C on the
set ec ç E. Accordingly, the partial stability of the variant vp with
respect to Vq is achieved for all points of w e E with the corresponding
(w;(h > 0)eS+)) solutions.
Boundary solutions
Boundary solutions are a set of solutions on one hyperplane of the set E ( wi or wB ). On the hyperplane wi , these are (waX;haX) solutions
for the points waÀ = (waz,--,wf = wAj,••• ,wanx) (due to unambiguous
indexing, additional A = 1,n e J marks are introduced). If condition (7) is met, then there is at least one boundary point with the component
wx = wâ .
Based on the relative independence of the variables z°(Â>j) > 0 (18)
and the built-in normalization condition (19) in each node, the
о" СМ О СМ
он УУ 0£ ZD О
он <
со <
О >о
component is determined on the basis of any starting point w e E - let that be the point w0: the choice of variables Z0A,j) < d0A,j) > 0 eliminates the active constraint of the A -criterion df > 0 ^ df = 0 and achieves the required condition: £j^¿¡f n = df;(f j) e@°. Nodes (A, j) and the corresponding variables j) < d0A, j) > 0 (the A row of the matrix t0 ) can be chosen at will until the specified condition is met, or preference can be given to a node in which z0A,j) = d%,j) = maxj{d0A,j)} ; if it is
fulfilled that
z( i, j)
= df, then also Wa/ = wi, otherwise the procedure
should be continued by selecting a next node from the A row of the matrix t0 and by adding the necessary difference, until it is fulfilled that
£j=n 0 = dA0 £ j=1 Z( A,j)-U A ■
■■ h ................. ai,kM
A ai, k Wf Wi
Figure 2 - Overview of the procedure for determining the basic solutions on hyperplanes Рис. 2 - Обзор процедуры определения базовых решений на гиперплоскостях Слика 2 - Приказ поступка одре^иваша основних решена на хиперравнима
Practically, in all rows of the matrix G0 except in the A row, g0 j) = 0;jeJ;jleJ\\{A} should be set and in the active nodes (A,j) the values of Z0A, j) < d0A, j) > 0 should be determined until the condition
Zj=nz0z,j) = dio is fulfilled. By applying expression (2-4) for the point waT = waT, the TOPSIS solution (waT1;hT1 ) is obtained. In the same way, the solution of (wbX&1;hbX&1 ) on the hyperplane wBj was obtained by eliminating the active constraint dT > 0 ^ dT = 0 based on the choice of the variable z°( j,t, — d°( j t) > 0 from which the Zj="z0( j t) = dT (the T column of the matrix t0 ) was obtained.
Extreme solutions on the hyperplanes wj and wBj (extreme
boundary solutions) are the exact solutions at the vertex of the set E and are determined by applying the presented method for the extremes of the function s(w). The starting point is the obtained solutions on the
hyperplanes: e.g. for the hyperplane wj, the initial solution is (waTl;haT) ; the component waf1 =wAx retains its value, which requires that the nodes that affect its value must become inactive.
From the starting point waT, the most favorable direction is chosen
in accordance with the characteristics of the active nodes (the set for the minimum or the set 0\\ for the maximum) that are not in the T row and the T column of the matrix t1 : set gjT j) = gl(jT) = 0 for all nodes (r,t)
in the row of T and the column of T, and the further procedure for determining the extremes (waTm;haTm) (min) and (waTM;haTM) (max) is
identical to the procedure shown for determining the exact extreme solutions of the function s(w) (27-31). The interval of the value of the
function [haTm;haTM] on the hyperplane wT cannot be greater than the interval of the extremum of the function h(w) : haTM - haTm — hM - hm, Figure 2. In the same way, the extreme solutions on the hyperplane wBx are determined. Extreme boundary solutions (maximum 4n solutions), among which are the extreme solutions h(w) of the function, are unique in terms of the corresponding points w and the values of the function h(w). Not all extreme points ( waTm and waTM ) are linearly independent; by eliminating the linearly dependent points, a set of points wv is obtained which are the vertices of the set E .
™ System of basic solutions for the separating hyperplane
ë A system ofbasic solutions (SBSC) is established for the value of the
c5 function h = C, which contains 2n basic solutions: n solutions (waA,c;haA,c = c) and n solutions (wbic;hbiC = C). These are the basic
boundary solutions for the point waic if wfc = wt (or wbic for
OH --^ wtic = wBt ) or the basic non-boundary solutions that are closest to the o current hyperplane wt or wl with wf&c > wt or wf&c < wl :
a) On the hyperplane wl (or wt ), there is an edge solution (wbt;hbt = cR) (Figure 2, hyperplane wBt ) because it is hbim < cR < hbtM ° and it is determined by repeatedly halving the segment [wbi m;wbtM ]
yj and it is ueieimmeu by lepeaiedly halving the segment [w ;w
I— -£ until it is achieved that it is hbt&c = c. The segment [wbim;wbtM] is
* halved for the point wi = 0.5wbim+ 0.5wbiM as well. The TOPSIS
solution, in general, has the value hbi2 ^ c ; in the next iteration, the
segment of the interval in which h = cR ([wbt&m;wbt&2] or [wbi2;wbtM] )
w ---is halved and the TOPSIS value is calculated, etc. The procedure is
^ interrupted when hbik = ck e [cR ±ec] is obtained in the k-th iteration and that solution is accepted as the basic boundary solution
lu [wbt&c;h,ic] ; for a larger number of iterations, a smaller absolute error
i0 ec =1 cR - hbt&c |< ec was obtained.
o b) On the hyperplane wt (or wt ), there is no solution
(waA: haA = CR) because CR £ Hi&" "& : halM] ■ To achieve the h = C value,
These solutions are not boundary based on wf = wt, but are closest to the hyperplane wt (basic non-boundary solutions). The position of cR can be cR < haim (as in Figure 2) or cR > haiM. For the situation in Figure 2, in order to determine the wf> wt component, the point wf&2 > wt is first determined by iterative halving of the segment between two known points at which there is a solution with h = cR until the value haik = c is reached: for hai&m > cR + ec value hat&2 = cR it is on the
the point wat cannot have a value of wf = wt, but a value of wf> wt.
segment [wm;waTm], and for haTM < CR - Sc, on the segment [waÀM;wM]. From the point w., for the constant value wf2 (in the row of T and the column of T the matrix G2, set g2. ., = g2 T,= 0 ) and determine the minimum (waT2m;haT2m) . If the obtained solution does not satisfy condition (45) and if it is haX,2m < CR - Sc , by repeatedly halving the new segment [waÀ,2m;waÀ,m], a new point waT3 and a minimum (waT,3m; haT,3m < cs - Sc) are obtained, etc. The procedure ends when the solution (waTkm;haTkm = c) = (waTC;haTC = C) is obtained in the k-th
iteration, from which it is not possible to further move the point
towards the hyperplane w\\ provided that h = C, which determines the basic non-boundary solution (waTkm;haTkm = C) = (waTC;haTC) (based on other weight components wj;je J\\{T}, these solutions can also be boundary) 9.
On the hyperplane , if haT,M < CR - Sc , the procedure for determining the solution is similar: the segment [waZ,M;wM] is considered; the relevant points are wM and waT,kM ; the non-boundary solution is (waTkM;haTkM = C) = (waTC;haTC) .
The presented procedure yields n solutions (waTC;haTC) and n solutions (wbTC;hbTC) that make up the SBSC for the value of the function h = cR ±Sc . Due to the components T of the points waTC and
, the points of solution w in SBSC are mutually linearly independent.
A set of solutions for the separating hyperplane h = cR : From SBSC linear combinations of the weight points waTC and wbTC , countless new
In the numerical example, the solution (wb4;fob40 = 0) is the basic non-boundary solution because (wb4 = 0-1681 ) < (wBA= 0.(830) although wb4eE\\E is a boundary point due to wb4 = wf = 0-0990 e
o" CM O CM
satisfactory solution (wab,C; hab,C ) can be determined by the line search in
weight points can be obtained based both on them and on the solutions with h C :
wb = Z j="pa-wj + Z j=ww Z j=wa + Z j^W, = 1; j e J , (46)
where all coefficients PjWp > 0 are not equal to 0, and can be selected according to different criteria. Due to the nonlinearity of the h(wab) of function, by using the points wm and wM and/or other known points, a
coticfactory colution (,..ab,C ■ l„ab,C
° the vicinity of the point wab
o The procedure completely defines the set of all solutions of the
x function h(w) (graph of the function): based on the most 4n extreme
w boundary solutions (whose points w are not linearly independent), a set
£ of linearly independent points wv is singled out, which are also all
vertices of the set E . Other TOPSIS solutions can be determined on the basis of linear combinations of points on the vertices of the set E. For each criterion j e J and any value wj e [w1,wB], weight points can be
< determined for which the function hva(w) has a maximum and minimum
¡3 the parameters of the remaining active nodes. By combining multiple
SBSC solutions for different cme [hmpq;hMq] values, solutions with a range of hpq e [Cf ;C2] values and stricter criteria for weight component values can be determined.
Numerical example
By applying the TOPSIS method to the MADM problem given by the initial matrix C = {Cij; i = 1,5, j = 1,6}, for the weight point w 0 and the
coefficients of the linear combination Zp,6 = (0 5717; 0 2647; 0-1636) for p = 1,2, œ, the basic solution was obtained: the variant v 2
(w0;s2 = 0.6209) and the rank v2-V3-V5-V1 -V4 (1-5) (Table 2).
Table 2 - Criteria Matrix, basic solution and extreme solutions Таблица 2 - Матрица критериальных значений, базовые решение и экстремальные решения Табела 2 - Матрица критериумских вредности, основно решете и екстремна
решена
О) (N Ю
criteria st(w° ) (rank) Sj (wm) Sj( wM)
Ki(+; K 2 ( - ) K з(+) K 4 ( - ) K 5 ( + ) K 6 ( - )
variants V1 415 85 1112 60 1.42 11.9 0.4348 (4) 0.4107 0.4645
V 2 432 94 970 35 1.71 15.2 0.6209 (1) 0.5846 0.6518
V 3 405 77 1015 55 1.88 14.6 0.6058 (2) 0.5812 0.6366
V 4 352 62 1055 54 1.06 13.8 0.3522 (5) 0.3248 0.3838
V 5 328 78 1045 38 1.43 17.5 0.4997 (3) 0.4717 0.5214
A W 0.099 0.132 0.237 0.147 0.208 0.088 Set of function values Sj(w)
B W 0.134 0.161 0.273 0.183 0.241 0.105
, A 0 d j 0.013 0.012 0.021 0.020 0.015 0.008
,B 0 d j 0.022 0.017 0.015 0.016 0.018 0.009
, AB d j 0.035 0.029 0.036 0.036 0.033 0.017 3 0.4 0.5 0.6 0 7
Table 2 provides data for the weight range limits W and
initial active limits dj0 and dB0 (9) for k = 0, and the extreme values of
Sj(wm) and si(wM). Based on the characteristics of the formed nodes (Table 1), exact extreme solutions were obtained at the vertices of the set E (27-31, 2-4) when the optimality criterion (33) was met, regardless of the convexity or concavity of the function. The variant V2 is slightly better than the variant V 3, but in the conditions of interval given weights, the ratio of their extreme values is (sM = 0.6518) > (s&m = 0.5812) and (sm = 0.5846) < (sM = 0.6366), which shows that the sets of values of functions partially overlap and require testing the stability of solution V2 \\(w;s2 (w)) in relation to the solution V3 \\(w;s3 (w)).
The solution
stable with respect to
h2,3 (w) = S2(w) ~ S3(w) > 0 ■ For the function h(w) (42), extreme solutions are determined (which are on the vertices of the set E, in
■c ra CL
>он <
accordance with (7)), where, except for the component W3, all other components Wj have values of one of the limits of the weight interval,
Tab|e 3. The set of values of the function is SZ = {h2.3 e [-0.0298; 0.0557]} , in the point wM the largest difference of TOPSIS values of the variants V2 and V3 ( h2,3 (WM) = 0.0557 ) is achieved, while in the point wZ. the variant Vз is "better" than the variant
V2 (h2,3 (wm) = -0.0298) .
Table 3 - Extreme solutions of the function h2 3 (w) Таблица 3 - Экстремальные решения функции h2 3 (w) Табела 3 - Екстремна решена функци]е h2 3 (w)
m w 0.0990 0.1610 0.2640 0.1470 0.2410 0.0880 0.6009 0.6307 -0.0298
M w_ 0.1340 0.1320 0.2550 0.1830 0.2080 0.0880 0.6425 0.5868 0.0557
<л <
О ■О
X ш I—
For each hyperplane w-j = wa;i/L and w^w/, boundary solutions
and extreme boundary solutions (4n = 24 solutions) are determined, whereby the individual extreme boundary solutions are identical to each other or identical to the extreme solutions of the function h(w). On the
segments [w;/m;w;/M] and [wb/m;wb/M], the basic boundary
solutions for the separating hyperplane hC=C[CR +sCJ (45) and for
the reference value of the function cr = 0 (if any) are determined, or the basic non-boundary solutions are determined. In order to determine only solutions with positive values of the function h > 0, due to partial stability
and s + = {h\\hM ^ h > CR = 0} ç S, a modified expression (45) was
applied: hC=C^[CR + scJ.
The obtained basic solutions are also boundary solutions based on the
current hyperplane because wa/&0 = or wbÄÄ■ 0 = , except for the solution for the point wM-0 which is not a boundary solution based on the hyperplane
ьл,C , B
Wx ф Wл
(non-boundary basic solution) and ■ ° = 0.1681 < W = 0.1830. In general, according to the definition of the
boundary solution, the solution wb 40 is a boundary solution based on other
hyperplanes, because w14,0 = wf = 0990 and wf&0 = wB2 = °.161° (Tab|e 4)10.
Table 4 - System of basic solutions for the separating hyperplane h(w) = 0 Таблица 4 - Система базовых решений для разделения гиперплоскостей h(w) = 0 Табела 4 - Систем основних решена за хиперраван раздва]а^а h(w) = 0
\\w j \\ a1 0 w b1& 0 w a 2& 0 w b 2& 0 w a3, 0 w b3& 0 w a 4& 0 w b4, 0 w a 5& 0 w b5 0 w a 6& 0 w b6& 0 w
h(w ) 0.00002 0.00001 0.00004 0.00000 0.00003 0.00001 0.00003 0.00003 0.00004 0.00004 0.00000 0.00004
s2=s3 0.6091 0.6188 0.6238 0.6089 0.6174 0.6092 0.6139 0.6122 0.6007 0.6222 0.6150 0.6153
О) (N Ю
It is shown that the function h(w) between the points of the weight
of the basic solutions is concave or convex: between the points
wb1,0 the function is convex, and between the points wa2 0 and wb2 0 the
function is concave. Due to the values of the A weight components ( and
), all points of the basic solutions waA0 and w 0 are linearly
independent and their linear combinations give innumerable new weight points in the environment of the separating hyperplane. By applying
expression (46) for fia = fib = 1 / 2n = 1 /12, the solution is obtained:
= (0.1123; 0.1497; 0.2572; 0.1591; 0.2266; 0.0951) ;
h2,3 (wab) = 0.0003 <£c = 0.00005 and s2 (w_) = s3 (w_) = 0.6139 ■ The solution does not need to be corrected in accordance with other known
For Sc = 5 • 10 5 and the calculation of one basic boundary solution for which
or = wb* about twenty iterations were required, and for the non-edge solution
about forty iterations.
■E ra CL
УУ 0£ ZD
>ОН <
со <
О >о
X ш I—
points, for example in accordance with the extremes of the function or the boundary extreme solutions, because h2, 3 (wab) <sC and the solution
(wab;h f3) can be accepted in accordance with condition (45). The
fulfilled condition (45) can also be a consequence of the concavity or convexity of the function on the segments between the points of the basic solutions.
Table 5 - Vertices of the set E Таблица 5 - Вершины множества E Табела 5 - Врхови скупа E
v w wi w2 w3 w4 w5 w6 h( wl_)
wl 0.0990 0.1610 0.2470 0.1470 0.2410 0.1050 -0.0294
wl 0.0990 0.1610 0.2730 0.1470 0.2320 0.0880 -0.0283
wl 0.1090 0.1610 0.2370 0.1470 0.2410 0.1050 -0.0269
wl 0.1060 0.1610 0.2730 0.1470 0.2080 0.1050 -0.0216
wl 0.1340 0.1610 0.2370 0.1470 0.2330 0.0880 -0.0194
wl 0.1020 0.1320 0.2730 0.1470 0.2410 0.1050 -0.0111
wl 0.1340 0.1320 0.2730 0.1470 0.2090 0.1050 0.0040
wl 0.0990 0.1610 0.2370 0.1830 0.2303 0.0897 0.0207
wll 0.1230 0.1610 0.2370 0.1830 0.2080 0.0880 0.0337
wll 0.1190 0.1320 0.2370 0.1830 0.2410 0.0880 0.0416
wll 0.0990 0.1320 0.2730 0.1830 0.2080 0.1050 0.0467
wll 0.1160 0.1320 0.2730 0.1830 0.2080 0.0880 0.0512
wll 0.1340 0.1320 0.2370 0.1830 0.2090 0.1050 0.0550
w15 0.1340 0.1320 0.2380 0.1830 0.2080 0.1050 0.0554
wi 0.1340 0.1320 0.2550 0.1830 0.2080 0.0880 0.0557
Some of the weight components do not have to be given intervally but as discrete values (maximum n-2 components), which also enables the determination of a set of solutions for a certain value of the function and the definition of the separating hyperplane. For example, if the weight point is w = (wj) with the components wj = w0 for j = 1, 2, 3 and
the components wj e [w,wBj] for j = 4,5,6 (according to Table 2), and
From the set of points w for the extreme boundary solutions (
w , w and w
bx,m _aXM and wbAM), which are not all linearly independent, linearly
independent points wv are singled out and all vertices of the set E are
determined by them (16 vertices of the set wv e E are obtained, Table 5).
This completely describes the set of definitions of the function E , which with TOPSIS values of the function, represents a complete graph of the function rh = l(w;h2,3) e^7 \\w e E, h2, 3 (w) e S2, 3} ■ Knowledge of function
graphs enables determination of sets of solutions complying with specific requirements in accordance with the stated limitations, which exceeds the goal and scope of this work.
Conclusion
The initial idea of developing a concept for testing the stability of the solution of the MADM problem (best variant and the corresponding quantitative indicator of the quality of the variant according to the chosen MADM method) in relation to other solutions (variants) and variable criteria weights was operationalized only through the examination of partial stability in relation to some other solution - one variant. The problem of determining the set of solutions of partial stability is set as a problem of NLP with the aim of finding feasible solutions that meet the conditions from the definition of partial stability. The TOPSIS method with parameters and interval-given criteria weights was considered as a basis, which defined the reference function as nonlinear and differentiable, in the presence of a normalization condition for arguments (weight components).
the required value is h2, 3 (w) = 0.0500 (to ensure a significant "advantage" of the variant v2 over v3 ), althhough h2,3 (w) < hMS = 0 0557 , such a solution does not exit because the maximum possible value of the function for these conditions is equal to h2 3 (w) = 0.0421. For a smaller |
value, for example for h2, 3 (w) = 0.0400, there is a set of basic boundary
solutions, and linear combinations of points of difficulty of these solutions determine other solutions that meet condition (45). One of these solutions is: wfL = (01120; 0.1440; 0.2580; 0.1828; 0.2132; 0.0900) ;
h2, 3(wab) = 0.0400 ; S2(wab) = 0.6278 and S3(wab) = 0.5878 .
CO <D </)
o" CM O CM
CD >Q
The created NLP model contains a nonlinear objective function, linear constraints based on the nature of the arguments (values: from -to) and the normalization condition for the arguments. An appropriate method was not known for solving the set NLP task, and therefore an attempt was made to solve the problem by introducing the nodes of argument (criteria) pairs and by defining their parameters. This ensures the normalization condition in each node and for each feasible point, non-negativity of variables and independence of variables in nodes, within the limits of active constraints. Node parameters were applied to determine the extremes of the function, the extremes on the hyperplanes of the set of arguments and other feasible solutions needed to determine the partial stability of the MADM solution, as well as to eliminate the consequences of accompanying degeneration (wedging and oscillation of the solution).
The presented procedure for determining the extremes of a given NLP problem differs from the basic gradient method in applying nodes parameters, choosing favorable directions, determining improved solutions, as well as in the procedure of linear search for the point of difficulty for an improved TOPSIS solution. The well-known and applied line search procedure can be replaced by another, for example, the "golden ratio" procedure, if this would contribute to the reduction of the procedure.
The procedure can be applied to other MADM methods with a nonlinear reference function, as well as to the class of NLP problems with conditional optimization, in which the mathematical model contains a nonlinear and on the whole set of arguments differentiable objective function, natural linear constraints and the normalization condition for variables. The procedure is robust and requires a larger number of calculations, so adequate software support would increase the possibilities of application.
References
Bazaraa, M.S., Sherali, H.D., Shetty, C.M. 2006. Nonlinear Programming: Theory and Algorithms, 3rd Edition. New Jersey: John Wiley Sons, Inc. ISBN: 978-0-471-48600-8.
Hadley, G. 1964, Nonlinear and dynamic programming. Boston: Addison-Wesley Publishing Company Inc. ISBN 10: 0201026643, ISBN 13: 9780201026641.
Hwang, C.L., Yoon, K. 1981. Multiple Attribute Decision Making, New York: Springer-Verlag. ISBN: 978-3-642-48318-9.
Luenberger, D.G., Ye, Y. 2016. Linear and nonlinear programming. Basel: Springer International Publishing. ISBN: 978-0-387-74503-9.
Martic, Lj. 1978. Visekriterijumsko programiranje. Zagreb: Informator (in Serbian).
Milovanovic, G.V. Stanimirovic, P.S. 2002. Simbolicka implementacija nelinearne optimizacije. Nis: Elektronski fakultet (in Serbian).
Opricovic, S. 1986. Visekriterijumska optimizacija. Belgrade: Naucna knjiga (in Serbian).
Petric, J. 1979. Nelinearno programiranje. Belgrade: ISRO „Privredni pregled" (in Serbian).
Vujicic, V., Asic, M., Milicic, N. 1980. Matematicko programiranje. Belgrade: Matematicki institut (in Serbian).
Yoon, K. 1987. A Reconciliation Among Discrete Compromise Solutions. Journal of the Operational Research Society, 38(3), pp.277-286. Available at: https://doi.org/10.1057/jors.1987.44.
Zangwill, W.I. 1969. Nonlinear programming. Englewood Cliffs, N.J: Prentice-Hall. ISBN 10: 0136235794, ISBN 13: 9780136235798.
Zeleny, M. 1982. Multiple Criteria Decision Making. New York: McGraw-Hill.
ЧАСТИЧНАЯ УСТОЙЧИВОСТЬ МНОГОАТРИБУТИВНОГО ПРИНЯТИЯ РЕШЕНИЙ ПО ИНТЕРВАЛЬНО ЗАДАННОМУ ВЕСУ КРИТЕРИЯ - ПРОБЛЕМА НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Радомир Р. Джукич
независимый исследователь, г. Крушевац, Республика Сербия
РУБРИКА ГРНТИ: 27.00.00 МАТЕМАТИКА;
Резюме:
Введение/цель: В статье представлена разработанная процедура для решения класса задач нелинейного программирования (НЛП) с нелинейной и дифференцируемой целевой функцией, линейными естественными ограничениями и условием нормализации переменных (аргументов). Процедура была применена для определения частичной устойчивости решения задач многоатрибутивного принятия решений.
Методы: Основой процедуры является определение узлов пар аргументов и их параметров для допустимых многомерных точек. Параметры внедрены в примененном градиентном методе, методе возможных направлений и методе линейного поиска. При разработке процедуры были использованы основы метода TOPSIS как метода для многоатрибутивного принятия решений с интервально заданными критериями веса, в первую очередь из-за нелинейности в вызове функций.
Результаты: Также разработана процедура определения экстремальных и других допустимых решений при вызове функций (маргинальные и базовые решения) и всех вершин выпуклого °° множества определения функции. Таким образом сформирован
> допустимого множества. Разработана процедура установления
° множества решений для определения разделяющей
° гиперплоскости множества значений функции; благодаря чему в
ос отдельных случаях множество решений частичной устойчивости
¡2 варианта определяется как решение многоатрибутивного
принятия решений. Были предложены соответствующие о процедуры для устранения отклонений в процедуре (заклинивание
< и колебание решений). Выводы: Данное исследование является значительным вкладом в
^ определение узлов аргументов и их параметров, которые
ш обеспечивают условия нормализации в каждом узле и для каждой
>_ допустимой точки, неотрицательность переменных и
независимость изменений аргументов в узлах в рамках активных ограничений. Разработана оригинальная процедура определения графов функций. Приведены соответствующие реальные числовые примеры.
< градиентный метод, метод возможных направлений, система о базовых решений, метод многоатрибутивного принятия ^ решений, частичная устойчивость решений.
ПАРЦШАЛНА СТАБИЛНОСТ РЕШЕНА ВИШЕАТРИБУТНОГ £ ОДЛУЧИВА^А ЗА ИНТЕРВАЛНО ЗАДАТЕ ТЕЖИНЕ
КРИТЕРШУМА - ПРОБЛЕМ НЕЛИНЕАРНОГ ПРОГРАМИРА^А
° Радомир Р. Ъукип
fgf самостални истаживач, Крушевац, Република Cp6nja
ОБЛАСТ: математика, нелинеарно програмира^е ВРСТА ЧЛАНКА: оригинални научни рад
Сажетак:
Увод/цил>: У раду je приказан npojeKmoeaHu поступак за решаваъе класе задатака нелинеарног програмираъа (НЛП) са нелинеарном и диференц^абилном функц^ом циъа, линеарним природним ограничеъима и ноpмиpаjуfíим условом за променъиве (аргументе). Поступак je применен за одреГ/иваъе парц^алне стабилности решена проблема вишеатрибутног одлучиваъа (ВАО).
Методи: Основ поступка представка дефинисане чворова парова аргумената и нихових параметара за допустиве вишедимензионалне тачке. Параметри се имлементираjу у гради/ентни метод, метод повоъних праваца и метод лин^ског тражена. У развоjу поступка коришЯени су основи метода § ТОПСИС за ВАО са интервално задатим тежинама критер^ума, првенствено због нелинеарности референтне фунще. Резултати: Разращен jе поступак одре^ивана екстремних и других допустивих решена референтне функц^е (рубна и основна решена) и свих врхова конвексног скупа дефинисаности функц^е. Тиме jе формиран потпуни график функц^е, на основу щег се могу одредити захтевана решена из допустивог скупа. Разв^ен jе поступак одре^ивана скупа решена за дефинисане хиперравани раздва]ана скупа вредности функц^е. На таj начин се, као специфичан случаj, дефинише и скуп решена парц^алне стабилности варианте као решена ВАО. За откланане дегенераци&е поступка (заклинаване и осциловане решена) предложене су адекватне процедуре.
Закъучак: Наjзначаjниjи допринос овог рада jесте дефинисане чворова аргумената и нихових параметара щима се осигурава нормираjуhи услов у сваком чвору и за сваку допустиву тачку, ненегативност променъивих и независност промена аргумената у чворовима, у границама активних ограничена. Тако^е, развц&ен jе оригиналан поступак за одре^иване графика функц^е и представлен одговараjуhи реалан нумерички пример. Къучне речи: тежине критер^ума, чворови парова аргумената, град^ентни метод, метод повоъних праваца, систем основних решена, вишеатрибутно одлучиване, парц^ална стабилност
_решена._
Paper received on / Дата получения работы / Датум приема чланка: 10.06.2020. Manuscript corrections submitted on / Дата получения исправленной версии работы / Датум достав^а^а исправки рукописа: 06.07.2020.
Paper accepted for publishing on / Дата окончательного согласования работы / Датум коначног прихвата^а чланка за об]ав^ива^е: 08.07.2020. © 2020 The Author. Published by Vojnotehnicki glasnik / Military Technical Courier (www.vtg.mod.gov.rs, втг.мо.упр.срб). This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution license (http://creativecommons.org/licenses/by/3.0/rs/).
© 2020 Автор. Опубликовано в «Военно-технический вестник / Vojnotehnicki glasnik / Military Technical Courier» (www.vtg.mod.gov.rs, втг.мо.упр.срб). Данная статья в открытом доступе и распространяется в соответствии с лицензией «Creative Commons» (http://creativecommons.org/licenses/by/3.0/rs/).
© 2020 Аутор. Обjавио Воjнотехнички гласник / Vojnotehnicki glasnik / Military Technical Courier (www.vtg.mod.gov.rs, втг.мо.упр.срб). Ово jе чланак отвореног приступа и дистрибуира се у складу са Creative Commons licencom (http://creativecommons.org/licenses/by/3.0/rs/).
[(£) ® I
