The tolerance approach in multiobjective linear fractional programming

Sociedad de Estadistica e Investigacidn Operativa Top (1997) Vol. 5, No. 2, pp. 241-252 The Tolerance Approach in Multiobjective Linear Fractional Programming Ar~valo, M.T., Mfirmol,A.M. and Zapata,A. Departamento de Economla Aplicada I Universidad de Seviila. Avda. Ramdn y Cajal 1, 41018 Seviila, Spain Abstract When solving a multiobjective programming problem by the weighted sum approach, weights represent the relative importance associated to the objectives. As these values are usually imprecise, it is important to analyze the sensitivity of the solution under possible deviations on the estimated values. In this sense, the tolerance approach provides a direct measure of how weights may vary simultaneously and independently from their estimated values while still retaining the same efficient solution. This paper provides an explicit expression to the maximum tolerance on weights in a multiobjective linear fractional programming problem when all the denominators are equal. An application is also presented to illustrate how the results may help the decision maker to choose a most satisfactory solution in a production problem. Key Words: managerial decision making; multiobjective; sensitivity; fractional programming. AMS subject classification: 90C29, 90C31, 90C32. 1 Introduction Fractional programming is an important tool widely used in the complex field of managerial decision making. It arises in a variety of practical areas such as agricultural planning (Bereanu,1953), models for minimizing wastage (Gilmore and Gomory,1961), optimal policy for a Markov chain (Derman,1962; Fox,1966), information theory (Meister and Oetlli,1967), shipping schedule (Bitran and Novaes,1974), investment portfolios (Ziemba, Parkan and Brooks-Hill,1974), econometric models (Bradley and Frey,1974), inventory models (Stancu-Minasian, 1980), etc. Sensitivity analysis is a fundamental issue when dealing with these problems because it allows to control the permanence of the solution when the data involved in the model are imprecise. Received: January 1997; Accepted: August 1997 242 M.T. Ardvalo, A.M. Mdrmol and A. Zapata. Recent work on this field has presented a new perspective on sensitivity analysis in mathematical programming called the tolerance approach. It permits to deal with simultaneous and independent perturbations of the coefficients in a variety of problems, that arise in management science and business administration. It provides a direct but simple sensitivity measure of the variable values that the decision maker controls with respect to simultaneous and independent changes in the problem parameters. This approach avoids the difficulty of the classic multiparametric analysis, that yields to a region difficult for the decision maker to understand. Besides it does not require the specification of increase or decrease directions that is needed in other methods such as the 100 percent rule. Wendell (1985,1984) and Ravi and Wendell (1989) presented the tolerance approach for dealing with variations in a standard linear programming problem. The approach incorporates the possibility of using a priori information about the variability of the coefficients in order to obtain larger tolerance percentages. Hansen, Labb6 and Wendell (1989) proposed the tolerance approach to address sensitivity analysis of the multiobjective linear problem. They showed how to calculate the maximum tolerance with respect to the weights that generate an efficient solution. Recently, Ms and Puerto (1997) have studied how specially structured information on the importance of the objectives can be exploited to yield a larger maximum tolerance percentage in a multiobjective linear problem. The sensitivity in the scalar fractional case has also been approached from this perspective. Dutta, Rao and Tiwari (1992) considered the tolerance approach in a linear fractional programming problem, obtaining expressions of the tolerance that depend on the equivalent linear problem. The purpose of this paper is to study the sensitivity of the solution in multiobjective linear fractional programming problems provided that all denominators are equal. Specifically, we apply the tolerance approach with respect to the weights used to generate efficient solutions. The paper proceeds as follows. In section 2 the mathematical statement of the problem is provided and the expression of the maximum tolerance is obtained. An application of a production problem illustrating the results of section 2 is presented in section 3. Finally, section 4 is devoted to the conclusions and to outline possible extensions. Tolerance Approach in LFP. 243 2 Tolerance on weights in a multiobjective linear fractional programming problem. Consider the multiobjective linear fractional programming problem (MOLFP): [ citx"~-Oll 1 max ql(x)-- dt x_q_/3 ''"'qp(X)-- dt xq_t3 J s.t. x E X = {x E ll:ln/Ax <<_ b,x >_ O,A E Mm.n,b E 11~ m} where X is a nonempty bounded set, and such that dtx +/3 7s O, Vx E X; c~,d E /R n and c~,3 E/R, r = 1, ...,p, and assume that A has full rank. As optimal solution in the traditional sense is impossible if multiple criteria are involved, we adopt the usual concept of efficient or Pareto optimal solution. Definition 2.1. x* E X is an efficient solution of the MOLFP if x E X/q~(x) > q~(x*), r = 1, ...,p; 3i/qi(x) > qi(x*) Since MOLFP has identic denominators, efficient solutions are solutions of weighted sum prob}ems. Therefore, for each w ~ E W = {w E IRP/w~ > 0, r = 1, ...,p}, we get an efficient solution of the MOLFP as the optimal solution of the weighted problem (WFP) P max w ~ + dtx + 13 r----1 s.t. Ax <_ b, x>O When solving this problem by the weighted sum approach, each objective 0 and all are (crtx -4- (~r)/(dtx -4-/3) is associated with a positive weight w~ combined into a composite criterion function. Each component of this vector w ~ represents the relative importance that the decision maker gives to the objective. A great difficulty with weighting problems is that, in many situations, the decision maker may be unable to specify a weighting vector. Thus, as the efficient solution obtained depends on the values assigned to the weights, it is important to analyze the effect that possible variations in the estimated values of weights produce on the efficient solution obtained. 244 M.T. Ardvalo, A.M. Mdrmol and A. Zapata. In order to deal with simultaneous and independent perturbations from their estimated values w ~ we focus on the following perturbed fractional problem (PFP): P I ~ crtx JrO~r max (w~ + 7x7 r=l s.t. Ax <_ b, x>0 ' (r = 1, p) are given values and 7~ are real parameters. This The w~ ..., general perturbation scheme allows to handle a wide range of cases. If t 0 w r = w~, r = 1,...,p, */r represents the percentage deviation from the 0 If ~ = 1, 7~ represents an additive perturbation from estimated value wr. w r w~. Moreover, if the value w ~ is precisely known, we can suppress variation in the value of this weight setting w~ = 0. In particular, when all the weights are expressed in terms of the first one, they can be normalized ! ~ 0* setting w ~ = 1, w 1 To address the problem, let x* be the basic efficient solution of MOLFP, obtained from the vector of weights w ~ Let B denote the optimal basis to WFP, and we use the notation A.j to denote the jth column of matrix A. Definition 2.2. A finite nonnegative number is called an allowable tolerance r for PFP if and only if the same basis B is optimal in PFP as long as the absolute value of each perturbation 7~ does not exceed r, r = 1, ...,p. We define v* as a maximum tolerance for PFP if v* is the least upper bound of the set {v : v is a tolerance for PFP }. Hansen, Labb~ and Wendell (1989) developed the expression for the maximum tolerance to simultaneous and independent variations of weights, for the multiobjective linear weighted problem P 0 rt max Ire x r----1 s.t. Ax <_ b, x>0 0 i If weights are perturbed as w r + ~'rw~, the maximum tolerance r* is com- Tolerance Approach in LFP. 245 puted as / p } Z 0 r rt --1 -- Wr(C j -- CBB A.j) r----1 r" = min rj = --~------ .... t r rt --1 jeJ wrlQ _ cuB A.Jl r=l where J is the index set of the nonbasic variables. Based on this result, the following theorem establishes the expression of the maximum tolerance within which weights associated to the objectives may deviate simultaneously and independently from their estimated values w ~ in the weighted fractional problem WFP. Theorem 2.1. Let x* be an efficient basic solution of the MOLFP obtained from a vector of weights w ~ B the basis associated to x*, cs, dB the basic parts of c, d and J the index set of the nonbasic variables. The maximum tolerance r* is given by: r* -- min vj jeJ whe~ o _, (x.)-d~) - ~-~ w,(cj -q,. r=l rj= v r=l = c~ - c~ B1A.j ~s = dj - di~B -lnj Proof." As a consequence of the one to one transformation of Charnes and Cooper (1962), that consists of t = 1/(dtx -t- ~), y -= tx, WFP is equivalent to the following linear weighted problem (PLP) P maxE w~ + ~,t) r=l s.t. Ay-bt < O dry + fit = 1 y_>0, t>0 Given an optimal basic solution for this problem (y*, t*), we can obtain the expression of the maximum tolerance from the corresponding rj computed 246 M.T. Ardvalo, A.M. Mdrmol and A. Zapata. as 0 r -- Wr(C j -- cr~___B___-IA.j) r----1 ~= p WtrIC; -- cr~B-1A.jl r=l where matrix A = dt , B is the optimal basis of PLP. As t* ~k O, we can assume that the basic variables of the optimal solution (y*, t*) of PLP are Y~, 9 9 9 Ym, t*. It follows that xi--* - y~/t*, i = 1, ..., m are the basic variables of the optimal solution of WFP. Hence matrix B__ can be written as (~ r) B__ = d~ , where B is the basis associated to x*. In order to compute B -1, we partition matrix B and we obtain B__ -1 _-- ( B -1(I also, we can write 1 t --1 B-lb d*BB=lb+3bds B ) dtBB-lb+fl ) -d~ B-l , 1 Then we have: c~B-lb + ~ (dj - dtBB-1A j) cj - c~B -1 A_j -~ (c; - c~B -1Aj) - dtBB_l b + t3 =~-q~(**)aj and the result follows. Notice that the value of r* can even be infinite, meaning that any vector of perturbations will lead to the same basic efficient solution. Particularly, when w' = w ~ if ~j - qr(x*)-dj = O, Vj E J, Vr = 1,... ,p, then r* -- q-oo and any percentage deviation from w ~ will preserve the basis. It is important to point out that the expression of the tolerance established in Theorem 2.1 is easy to calculate. All the elements needed to calculate the maximum tolerance can be determined from the simplex Tolerance Approach in LFP. 247 tableau associated to the basic efficient solution. Vectors _c, d can be interpreted as the reduced costs of vector c and d associated to the given basis, and can be easily computed in a simplex tableau. The value -5j - q(x*)-dj is the reduced cost that appears in some of the algorithms that look for optimal solutions of linear fractional programming problems (see e.g. Martos, 1964). In addition, this approach permits to detect those weights that will lead to a different efficient solution. For instance, when determining the maximum tolerance percentage it is possible to obtain the 'nearest' adjacent solution in the sense of minimum percentual variation on the estimated weights. In this case, the solution is obtained solving the weighted problem with the following perturbations: for the index j such that T* ---- rj if ~j qr(x*)-dj > 0, then 7r ---- v* if ~ - q~(x*)-dj < 0, then 7, = -r* if ~ - q~(x*)-aj = 0, then 7~ arbitrary This solution could be of interest to the decision maker in the procedure to solve the multiobjective problem. 3 An application: a production problem. Capacity available Machines (hours) 800 1 3 Owned capital 1000 4 2 Profit per unit 1 2 Employment 5 3 Pollution 3 2,5 Demand per unit of product P1 P2 Table 1 Let us consider a company that manufactures two products P1 and P2. Assume that the costs arising and the capital demands required are both proportional to individual activities. Regardless of the production program 248 M.T. Ardvalo, A.M. Mdrmol and A. Zapata. to be determined, there are fixed charges amounting to 200 dollars, a fixed capital demand amounting to 400 dollars and a fixed employment demand amounting to 100 hours. Furthermore, the production of P2 is more than the production of/~ at most in 200 units. Further production data appear in Table 1. Due to the fixed capital demand, there are 1000 dollars left for the variable capital demand. One of the objectives of the company is the maximization of owned capital profitability. In order to receive state aids to business development, the company also wishes to maximize the employment in relation to the owned capital. In addition, as pollution generated by the production process is penalized depending on the relative size of the company, pollution by owned capital employed must be minimized. From these data, we establish the following linear fractional problem with three objectives: profitability, employment by owned capital and pollution by owned capital: [ X 1 q2X 2 -- 200 5Zl + 3X2 + 100 --3Xl -- 2.5X2 ] max [~-xl ~--~--x2 ~- ~-0' 4xl + 2x~ + 400' 4~11~ 2~2 7~0J s.t. -xl+x2_<200 xl + 3x2 _< 800 4xl + 2x2 ~ 1000 Xl, X 2 ~ 0 where xi are the units of the products P,. (i = 1, 2) that the company may produce. In order to find a solution to the problem, the company provides an estimation of the importance associated to each of the objectives: the first objective is three times more important than the third one, and the second objective is twice as important as the first one. It follows that the vector of weights is w ~ =(3,6,1) and the associated efficient solution is to produce 140 units of product P1 and 220 units of product P2. In this case, the profitability is 19/70, the employment by owned capital is 73/70, and the pollution generated by owned capital is 97/140. Suposse the company wants to analyze the sensitivity of the solution obtained with respect to the importance associated to the objectives. The maximum tolerance percentage will give a measure of how the weights may deviate from their estimated values while retaining the same solution. The efficient tableau associated to the solution is given in Table 2. Tolerance Approach in LFP. 249 4 -3 5 1 2 -2.5 3 2 0 0 0 0 d C ~ C z B\c 1 t"1 P2 P3 1 cl c~ - zj C z -- Z~ z c} - z; d i - z~ 4 2 0 0 0 -3 -2.5 0 0 0 5 3 0 0 0 1 2 0 0 0 b 1 0 0 -1/5 3/10 0 1 0 2/5 -1/10 0 0 1 -3/5 2/5 0 0 0 -3/5 -1/10 0 0 0 -1/5 -12/10 0 0 0 2/5 la/20 0 0 0 0 -1 140 220 120 q:-- q =~670 Table 2: Efficient tableau. ! As we consider multiplicative perturbations, then w r = wr, j = 1, 2, 3. It follows from Theorem 2.1 that 7-4 = 13/17, r5 = 11/35 and r* = 11/35 which means that weights can vary simultaneously and independently within 31.42% of their estimated values yielding to the same solution. In this production problem an optimal policy would consist of the same quantity of products P1 and /)2 as long as the weights remain within a 31.42% of their estimated values (3,6,1). The tolerance region is: {w E n:~3/w, e [72/35,138/35], w2 E [144/35,276/35], w3 e [24/35, 46/35]} as shown in Figure 1. If the company believes that the weights may vary beyond the maximum tolerance limit, another solution must be explored. One of the vertices of the tolerance region is a vector of weights that leads to obtain an adjacent efficient solution. As r* =rb, this vector is given by w* = (138/35,144/35, 24/35). A nearby solution is obtained by substituting in the basis the slack variable associated to the third constraint by the one associated to the first constraint. Notice that vector w* is proportional to (23,24,4), thus if the relative importances of the objectives are specified by this vector, the best solution consists of producing 50 units of product P1 and 250 units of product P2. This is the nearest solution in the indicated sense.