Fuzzy parametric iterative method for multi-objective linear fractional optimization problems

1 Introduction

Optimization of ratio of linear (affine) functions under the linear constrains called the linear fractional optimization problem. It is very difficult to solve such problems due the non-convexity of linear fractional objectives. The linear fractional optimization problem mathematically can be defined as Optimize α T x + β γ T x + θ subject to(1) x ∈ S = { x ∈ ℝ : C j ( x ) ≤ 0 , x ≥ 0 , γ T x + θ > 0 , j = 1 , 2 , 3 , . . . , m , α , γ ∈ ℝ n β , θ ∈ ℝ }

The optimization of more than one ratios together under the linear constraints is known as the multi-objective linear fractional optimization problem. The research on MOLF optimization problem is increasing continuously from past four decades because it has wide variety of applications, such as financial sector, inventory management, production planning, banking sector and others. The MOLF optimization problem is used to measure the efficiency of any particular system such as optimization of debt/equity, profit/cost, inventory/sales, actual cost/standard cost, output/employees, nurses/patients ratios etc. Mathematically MOLF optimization problem can be written as: Optimize [ α 1 T x + β 1 γ 1 T x + θ 1 , α 2 T x + β 2 γ 2 T x + θ 2 , … , α k T x + β k γ k T x + θ k ] subject to(2) x ∈ S = { x ∈ ℝ n : C j ( x ) ≤ 0 , x ≥ 0 , γ i T x + θ i > 0 , j = 1 , 2 , 3 … m , α i , γ i ∈ ℝ n β i , θ i ∈ ℝ ∀ i = 1 , 2 , … k } Also, α i T x + β i, γ i T x + θ i are real valued linear (affine) functions which are defined on convex feasible space S. There are lots of computation difficulties in using the classical approaches for the solution of MOLF optimization problem. To overcome the computational difficulties of using conventional approaches to MOLF optimization problems, the theory of fuzzy sets has been introduced in the field of linear fractional optimization. Many authors proposed the techniques for the solution of MOLFP (see, [2, 26–28]). Costa [14] proposed a computational technique to find a solution using the weighted sum technique and the feasible region is divided into two parts and one of them is discarded on the basis of maximum weighted sum. This process is repeated with the remaining region. The drawback of the this algorithm is that it used several iteration to get one efficient solution and the uncertainty parameters are not considered. Also, Costa and Alves [15] presented a reference point technique to compute non-dominated solution for multi-objective linear fractional programming problem. The feasible space is partitioned into two parts by taking the middle point and analyzed for the deletion of one of them. The algorithm is terminated when difference between the iterative non-dominated solution becomes so small or less than the predefined error. The fuzzy iterative method is attempted by Lee and Tcha [4] who proposed a procedure by taking single fuzzy parameter and obtained compromise solution by maximizing the aggregate of membership functions. This method can find only some selective solutions in the feasible region. Valipaur, Yaghoobi and Mashinchi [1] suggested an iterative parametric approach for solving multi-objective linear fractional programming problems which only uses linear programming to obtain efficient solution and always converges to an efficient solution. Weakly efficient conditions for multiobjective fractional optimization problem was considered by Singh [25]. Chen and Chen [18] discussed a fuzzy approach for multi-level multi-objective decision- making problem. They used required minimum tolerence for higher - level decision maker’s decision variable to secure feasibility in the solution space. Dubey and Mehra [8] presented a Pareto optimal solution for multi-objective fuzzy linear programming. Yang, Li and Lai [16] developed a parameterized bilinear programming methodology for solving bimatix games with pay offs of triangular intuitionistic fuzzy numbers. Very recently, Bhati and Singh [9] proposed a novel approach for MOLF programming problem using branch and bound method. In this paper, we presented a fuzzy parametric extension of the method which was developed by Valipaur, Yaghoobi and Mashinchi [1].

2 Fuzzy parametric approach

The solution of multi-objective optimization problem can be obtained by many methods and there is no unique solution for any particular MOP. Most of the methods give the compromise solution to the MOP and the solution may be ranked according to the value of objective function obtained in the given feasible region. But fuzzy approaches also give the satisfaction degree for each objective in terms of membership function of each objective. It gives additional information about the solution by saying that how much contribution of each objective is presented in the compromise solution.

For the solution of fuzzy multi-objective linear fractional optimization problem (6), auxiliary variables (parameters) λ _i   ∀  i = 1, 2, …, k are introduced for each objective function in problem (6) and the well known Zimmerman’s [11] model can be as follows max { λ 1 , λ 2 , ⋯ , λ k } subject to λ i ≤ α i T x + β i γ i T x + θ i - t ˜ i g ˜ i - t ˜ i ∀ i = 1 , 2 , … , k .(7) x ∈ S = { x ∈ ℝ n : C j ( x ) ≤ 0 , x ≥ 0 , γ i T x + θ i > 0 , j = 1 , 2 , 3 … m , α i , γ i ∈ ℝ n β i , θ i ∈ ℝ i = 1 , 2 , … k } and λ i ∈ [ 0 , 1 ] ∀ i = 1 , 2 , … , k .

If we assume the auxiliary variable constraints in problem (7) as a function of x ∈ R ⁿ and λ ∈ [0, 1]  ^k such that G ( x , λ ) = α i T x + β i γ i T x + θ i - t ˜ i g ˜ i - t ˜ i - λ i ≥ 0 .(8) Then the problem (7) is transformed into the following form max G ( x , λ ) = Max [ ( α 1 T x + β 1 γ 1 T x + θ 1 - t ˜ 1 g ˜ 1 - t ˜ 1 - λ 1 ) , … , ( α k T x + β k γ k T x + θ k - t ˜ k g ˜ k - t ˜ k - λ k ) ] subject to(9) λ i ≤ α i T x + β i γ i T x + θ i - t ˜ i g ˜ i - t ˜ i x ∈ S = { x ∈ ℝ n : C j ( x ) ≤ 0 , x ≥ 0 , γ i T x + θ i > 0 , j = 1 , 2 , 3 … m , α i , γ i ∈ ℝ n β i , θ i ∈ ℝ ∀ i = 1 , 2 , … k } and λ i ∈ [ 0 , 1 ] ∀ i = 1 , 2 , … , k . After simplification and using equal weights w _i  = 1 each membership function of objectives in problem (9) max η ( x ) = max ∑ i = 1 k [ ( α i T x + β i ) - ( g i ˜ λ i + ( 1 - λ i ) t ˜ i ) ( γ i T x + θ i ) ] = max ∑ i = 1 k [ ( α i T x + β i ) - ( g i ˜ λ i + ( 1 - λ i ) t ˜ i ) ( γ i T x + θ i ) ] subject to(10) λ i ≤ α i T x + β i γ i T x + θ i - t ˜ i g ˜ i - t ˜ i x ∈ S = { x ∈ ℝ n : C j ( x ) ≤ 0 , x ≥ 0 , γ i T x + θ i > 0 , j = 1 , 2 , 3 … m , α i , γ i ∈ ℝ n β i , θ i ∈ ℝ ∀ i = 1 , 2 , … , k } and λ i ∈ [ 0 , 1 ] ∀ i = 1 , 2 , … , k .

Remark 1. In problem (10), λ ∈ [0, 1]  ^k is a fixed vector, the constraints λ i ≤ α i T x + β i γ i T x + θ i - t ˜ i g ˜ i - t ˜ i for i = 1, 2,. . . k are linear because t ˜ i and g i ˜ are the numerical values.

Theorem 3. If the feasible space S of Problem (10) is nonempty, then it has a non-negative fuzzy efficient value.

Proof. Let x be feasible solution of problem (10), then λ i ≤ α i T x + β i γ i T x + θ i - t ˜ i g ˜ i - t ˜ i , for i = 1 , . . . k ⇒ α i T x + β i γ i T x + θ i - t ˜ i g ˜ i - t ˜ i - λ i ≥ 0 , for i = 1 , . . . , k ⇒ α i T x + β i γ i T x + θ i - t ˜ i - ( g ˜ i - t ˜ i ) λ i ≥ 0 , for i = 1 , . . . , k ⇒ ( α i T x + β i ) - [ ( g i ˜ λ i + ( 1 - λ i ) t ˜ i ) ( γ i T x + θ i ) ] ≥ 0 for i = 1 , . . . , k For equal weights w _i  = 1 for all i = 1,. . . , k, we have [ ( α i T x + β i ) - ( g i ˜ λ i + ( 1 - λ i ) t ˜ i ) ( γ i T x + θ i ) ] ≥ 0 for i = 1 , . . . , k ∑ i = 1 k [ ( α i T x + β i ) - ( g i ˜ λ i + ( 1 - λ i ) t ˜ i ) ( γ i T x + θ i ) ] ≥ 0 for i = 1 , . . . , k Thus the optimal value is non-negative.

Theorem 4. Let x ^e  ∈ S and λ e = [ ( α 1 T x e + β 1 γ 1 T x e + θ 1 - t ˜ 1 g ˜ 1 - t ˜ 1 ), ( α 2 T x e + β 2 γ 2 T x e + θ 2 - t ˜ 2 g ˜ 2 - t ˜ 2 ) , … , ( α k T x e + β k γ k T x e + θ k - t ˜ k g ˜ k - t ˜ k ) ] Then x ^e is a fuzzy efficient solution of FMOLF optimization problem (6) if and only if the optimal value of problem (10) is zero.

Proof. Let x ^e be a fuzzy efficient solution of FMOLF optimization problem (6) and assume that the fuzzy efficient value of problem (10) is nonzero. Therefore, by theorem (3) there exists a feasible point y ∈ S such that λ i e ≤ α i T y + β i γ i T y + θ i - t ˜ i g ˜ i - t ˜ i,   for   i = 1, 2,. . . , k ⇒ ( α i T y + β i γ i T y + θ i - t ˜ i g ˜ i - t ˜ i - λ i e ) ≥ 0,  for   i = 1, 2,. . . , k ⇒ ( α i T y + β i γ i T y + θ i - t ˜ i g ˜ i - t ˜ i - λ i e ) ≥ 0,   then there exists index j  such that ( α j T y + β j γ j T y + θ j - t ˜ j g ˜ j - t ˜ j - λ j e ) > 0 ⇒ ( α j T y + β j γ j T y + θ j - t ˜ j g ˜ j - t ˜ j - λ j e ) > 0 ⇒ α j T y + β j γ j T y + θ j - t ˜ j g ˜ j - t ˜ j > λ j e = α j T x e + β j γ j T x e + θ j - t ˜ j g ˜ j - t ˜ j. Also, λ i e = α i T x e + β i γ i T x e + θ i - t ˜ i g ˜ i - t ˜ i for i = 1, 2,. . . , k . Hence, α i T y + β i γ i T y + θ i - t ˜ i g ˜ i - t ˜ i ≥ α i T x e + β i γ i T x e + θ i - t ˜ i g ˜ i - t ˜ i for i = 1, 2,. . . , k and there exists j such that α j T y + β j γ j T y + θ j - t ˜ j g ˜ j - t ˜ j > α j T x e + β j γ j T x e + θ j - t ˜ j g ˜ j - t ˜ j . Which is contradiction with the fuzzy efficiency of x ^e .

Conversely. Let a fuzzy efficient value of problem (10) is zero and suppose that x ^e is not a fuzzy efficient solution of FMOLF optimization problem (6). Then, there exists another feasible point y ∈ S such that α i T y + β i γ i T y + θ i - t ˜ i g ˜ i - t ˜ i ≥ α i T x e + β i γ i T x e + θ i - t ˜ i g ˜ i - t ˜ i for i = 1 , 2 , . . . , k and α j T y + β j γ j T y + θ j - t ˜ j g ˜ j - t ˜ j > α j T x e + β j γ j T x e + θ j - t ˜ j g ˜ j - t ˜ j for some j .

Thus y is a feasible solution of problem (6). Further α i T y + β i γ i T y + θ i - t ˜ i g ˜ i - t ˜ i - λ i e ≥ α i T x e + β i γ i T x e + θ i - t ˜ i g ˜ i - t ˜ i - λ i e for i = 1 , 2 , . . . , k . ⇒ ∑ i = 1 k [ ( α i T y + β i ) - ( g i ˜ λ i e + ( 1 - λ i e ) t ˜ i ) ( γ i T y + θ i ) ] ≥ ∑ i = 1 k [ ( α i T x e + β i ) - ( g i ˜ λ i e + ( 1 - λ i e ) t ˜ i ) ( γ i T x e + θ i ) ] which contradicts the fuzzy efficiency of x ^e .

In this section, the proposed method is outlined in a systematic way

Input: For the solution of FMOLF optimization Problem (6)  ∀ i = 1,. . . , k and assume that acceptable error in the obtained solution is ε > 0, and make partition feasible space using the same technique as defined by Valipour, Yaghoobi and Mashinchi [1].

Step 1: Let x⁰ ∈ S be any feasible starting point and assume that λ 0 = ( α 1 T x 0 + β 1 γ 1 T x 0 + θ 1 - t ˜ 1 g ˜ 1 - t ˜ 1 , . . . , α k T x 0 + β k γ k T x 0 + θ k - t ˜ k g ˜ k - t ˜ k ) and set p = 0 for x ^p  = x⁰. The feasibleregion can be defined as S p = S ∩ ( x ∈ R n : λ i p ≤ α i T x + β i γ i T x + θ i - t ˜ i g ˜ i - t ˜ i , i = 1 , . . . , k ) where pand S ^p are the iteration stage and the feasible region in the p ^th iteration, respectively.

If, any λ _i ’s equal to 0 for the initial point, then discard that i ^th constraints and solve the programming to find new λ _i ’s.

Step 2: Find the fuzzy efficient solution x^p+1 for the problem (6) and η^p+1 as fuzzy efficient value for the problem (6). max η p + 1 = max ∑ i = 1 k [ ( α i T x + β i ) - ( g i ˜ λ i p + ( 1 - λ i p ) t ˜ i ) ( γ i T x + θ i ) ] subject to(11) λ i p ≤ α i T x + β i γ i T x + θ i - t ˜ i g ˜ i - t ˜ i x ∈ S = { x ∈ ℝ n : C j ( x ) ≤ 0 , x ≥ 0 , γ i T x + θ i > 0 , j = 1 , 2 , 3 … m , α i , γ i ∈ ℝ n , β i , θ i ∈ ℝ ∀ i = 1 , 2 , … k } and λ i ∈ [ 0 , 1 ] ∀ i = 1 , 2 , … , k . By setting ξ^p+1 = η^p+1.

Step 3: If ξ^p+1 < ε, then go to Step 4, else, p = p + 1 , λ p = ( α 1 T x p + β 1 γ 1 T x p + θ 1 - t ˜ 1 g ˜ 1 - t ˜ 1 , . . . , α k T x p + β k γ k T x p + θ k - t ˜ k g ˜ k - t ˜ k ) , S p = S ∩ [ x ∈ R p : λ i p = α i T x p + β i γ i T x p + θ i - t ˜ i g ˜ i - t ˜ i ≤ α i T x + β i γ i T x + θ i - t ˜ i g ˜ i - t ˜ i , i = 1 , . . . , k ] and return to step 2, end of it.

Step 4: If ξ^p+1 = 0, then stop the method and the solution obtained x^p+1 in a fuzzy efficient solution and stop the iteration.

else

if ξ^p+1 < ε, then x^p+1 is an ε-fuzzy efficient solution, where, ε = (ε₁,. . . , ε _k ). Also, every x ∈ S ^p is an ε- fuzzy efficient solution which approximates the fuzzy efficient solution. end of it.

Output: A fuzzy efficient or an approximate fuzzy efficient solution is obtained.

Theorem 5. The following statements hold for the proposed method

∅ ≠ S^p+1 ⊂ S ^p for p = 1, 2, 3 . . .

Proof.

x^p+1 is the fuzzy efficient solution of problem (11) in step 2 of the method. Thus, x p + 1 ∈ S p ⇒ λ i p + 1 ≤ α i T x p + 1 + β i γ i T x p + 1 + θ i - t ˜ i g ˜ i - t ˜ i for i = 1,. . . , k⇒ ( x ∈ S : λ i p + 1 ≤ α i T x p + 1 + β i γ i T x p + 1 + θ i - t ˜ i g ˜ i - t ˜ i , for i = 1 , . . . , k ) ⊂ ( x ∈ S : λ i p ≤ α i T x p + β i γ i T x p + θ i - t ˜ i g ˜ i - t ˜ i , for i = 1 , . . . , k ) ⇒S^p+1 ⊂ S ^p  .

Theorem 6. The sequence {ξ ^p } converge to zero.

Proof. lim p → ∞ ξ p = lim p → ∞ ∑ i = 1 k [ ( α i T x p + β i ) - ( g i ˜ λ i p - 1 + ( 1 - λ i p - 1 ) t ˜ i ) ( γ i T x p + θ i ) ] lim p → ∞ ∑ i = 1 k [ ( α i T x p + β i γ i T x p + θ i - t ˜ i g ˜ i - t ˜ i - λ i p - 1 ) ( γ i T x p + θ i g ˜ i - t ˜ i ) ] = lim p → ∞ ∑ i = 1 k [ ( λ i p - λ i p - 1 ) ( γ i T x p + θ i g ˜ i - t ˜ i ) ]