# Some Duality Results on Linear Programming Problems with Symmetric Fuzzy Numbers

Some Duality Results on Linear Programming Problems with Symmetric Fuzzy Numbers Fuzzy Inf. Eng. (2009)1: 59-66 DOI 10.1007/s12543-009-0004-2 ORIGINAL ARTICLE Some Duality Results on Linear Programming Problems with Symmetric Fuzzy Numbers S.H. Nasseri · N.Mahdavi-Amiri Received: 18 May 2008/ Revised: 20 August 2008/ Accepted: 19 December 2008/ © Springer and Fuzzy Information and Engineering Branch of the Operations Research Society of China Abstract Recently, linear programming problems with symmetric fuzzy numbers (LPSFN) have considered by some authors and have proposed a new method for solv- ing these problems without converting to the classical linear programming problem, where the cost coeﬃcients are symmetric fuzzy numbers (see in [4]). Here we extend their results and ﬁrst prove the optimality theorem and then deﬁne the dual problem of LPSFN problem. Furthermore, we give some duality results as a natural extensions of duality results for linear programming problems with crisp data. Keywords Duality results · Fuzzy basic feasible solution · Fuzzy linear program- ming · Symmetric fuzzy numbers 1. Introduction Fuzzy set theory has been applied to many disciplines such as control theory and op- erations research, mathematical modeling and industrial applications. The concept of fuzzy mathematical programming on general level was ﬁrst proposed by Tanaka et al. [11]. The ﬁrst formulation of fuzzy linear programming is proposed by Zimmer- mann [15]. Afterwards, many authors considered various types of the fuzzy linear programming problems and proposed several approaches for solving these problems [1-7], [12]. Chanas [2] showed an application of parametric programming techniques in fuzzy linear programming and obtained the set of solutions maximizing the objec- tive function, being analytically dependent on a parameter. Delgado et al. [3] studied a general model for fuzzy linear programming problems which includes fuzziness S.H. Nasseri () Department of Mathematics, Mazandaran University, Babolsar, Iran and National Elite Foundation, Tehran, Iran e-mail: nasseri@umz.ac.ir N. Mahdavi-Amiri Department of Mathematics, Sharif University of Technology, Tehran, Iran e-mail: nezamm@sharif.edu 60 S.H. Nasseri · N.Mahdavi-Amiri (2009) both in the coeﬃcients and in the accomplishment of the constraints. Some authors used the concept of comparison of fuzzy numbers for solving fuzzy linear program- ming problems [1], [5-7]. Nevertheless, usually in such methods authors deﬁne a crisp model which is equivalent to the fuzzy linear programming problem and then use optimal solution of the model as the optimal solution of the fuzzy linear program- ming problem. Some authors considered types of linear programming problems in which the variables and the right-hand-sides of the constraints are fuzzy parameters [4], [5-7]. The study of duality theory for fuzzy parameter linear programming problems has attracted researchers in fuzzy decision theory. The duality of fuzzy parameter linear programming was ﬁrst studied by Rodder and Zimmermann [10]. Verdegay [12] deﬁned the fuzzy dual problem with the help of parametric linear programming and showed that the fuzzy primal and dual problems both have the same fuzzy solu- tion under some suitable conditions. The fuzzy primal and dual linear programming problems with fuzzy coeﬃcients were formulated by using the fuzzy scalar product proposed in [13]. Ramik [8,9] discussed a class of fuzzy linear programming prob- lems based on fuzzy relations and a new concept of duality and deduced the weak and strong duality theorems. Wu [14] oﬀered a concept of fuzzy scalar product and proved the weak and strong duality theorems using a dual fuzzy mathematical programming problem. Recently, a new method for solving linear programming with symmetric fuzzy numbers (LPSFN) proposed by Ganesan et al. [4]. Their method can solve these problems without converting to the classical linear programming problem. In this paper, we deﬁne the dual of LPSFN problems and state some duality results. This paper is organized in 6 sections. In the next section, we ﬁrst give some nec- essary notations and deﬁnitions of fuzzy set theory. Then we provide a discussion of fuzzy arithmetic. The deﬁnition of the fuzzy linear programming problem is given in Section 3. Section 4 explains the notion of fuzzy basic feasible solution. We deﬁne the dual of LPSFN problems in Section 5 and deduce some duality results. We ﬁnally conclude in Section 6. 2. Preliminaries We review the main concept of fuzzy set theory (taken from [4] and [6]). Deﬁnition 1 A fuzzy number a ˜ on R is said to be a symmetric trapezoidal fuzzy L U L U number if there exist real numbers a and a ,a  a andα  0 such that x α− a L L + , x ∈ [a −α, a ], α α ⎪ L U 1, x ∈ [a , a ], a ˜ (x) = ⎪ −x a +α U U ⎪ + , x ∈ [a , a +α], ⎪ α α 0, otherwise. Fuzzy Inf. Eng. (2009) 1: 59-66 61 L U L We denote symmetric trapezoidal fuzzy number a ˜ by a ˜ = (a , a ,α), where (a − U L U α, a + α) is the support of a ˜ and [a , a ] its core, and the set of all symmetric trapezoidal fuzzy numbers by F(R). L U L U Let a ˜ = (a , a ,α) and b = (b , b ,β) be two symmetric trapezoidal fuzzy num- bers. Then the arithmetic operations on a ˜ and b are given as follows: L L U U Addition: a ˜ + b = (a + b , a + b ,α+β). L U U L Subtraction: a ˜ − b = (a − b , a − b ,α+β). L U L U L U L U a + a b + b a + a b + b U U Multiplication: a ˜ b = (( )( )−ω, ( )( )+ω,|a β+b α|), 2 2 2 2 t − t 2 1 L L L U U L U U L L L U U L where ω = , t = min{a b , a b , a b , a b }, t = max{a b , a b , a b , 1 2 U U a b }. From the above deﬁnition it is clear that L U λ  0,λ ∈ R; λ a ˜ = (λa ,λa ,λα), U L λ< 0,λ ∈ R; λ a ˜ = (λa ,λa ,−λα). Note that depending upon the need, one can also use a smaller ω in the deﬁnition of multiplication involving symmetric trapezoidal fuzzy numbers. L U L U Deﬁnition 2 Let a ˜ = (a , a ,α) and b = (b , b ,β) be two symmetric trapezoidal ˜ ˜ fuzzy numbers. Deﬁne the relation  as a ˜  b (or b  a ˜ ) if and only if either L U L U L U L U (a −α)+ (a +α) (b −β)+ (b +β) a + a b + b < , that is < (in this 2 2 2 2 L U L U a + a b + b L L U U case, we may write a ˜ ≺ b), or = , b < a and a < b ,or 2 2 L U L U a + a b + b L L U U = , b = a , a = b andα  β. 2 2 ˜ ˜ Note that in the two above cases, we also write a ˜ ≈ b and say that a ˜ and b are equivalent. L U L U Remark 1. Two symmetric trapezoidal fuzzy numbers a ˜ = (a , a ,α), b = (b , b ,β) L U L U a + a b + b are equivalent if and only if = . 2 2 Deﬁnition 3 For any trapezoidal fuzzy number a, ˜ we deﬁne a ˜ 0, if there exist ε  0 and α  0 such that a ˜ (−ε,ε,α). We also denote (−ε,ε,α) by 0. Note that ˜ ˜ 0 is equivalent to (0, 0, 0) = 0. Naturally, one may consider 0 = (0, 0, 0) as zero symmetric triangular fuzzy number. Remark 2. If x ˜ ≈ 0, then x ˜ is said to be a zero symmetric trapezoidal fuzzy ˜ ˜ number. It is to be noted that if x ˜ = 0, then x ˜ ≈ 0, but the converse need not be true. ˜ ˜ If x ˜  0 (that is x ˜ is not equivalent to 0), then is said to be a non-zero symmetric ˜ ˜ trapezoidal fuzzy number. It is to be noted that if x ˜  0, then x ˜  0, but the converse ˜ ˜ ˜ need not be true. If x ˜  0(x˜  0) and x ˜  0, then is said to be a positive (negative) ˜ ˜ symmetric trapezoidal fuzzy number and is denoted by x ˜  0(x˜ ≺ 0). ˜ ˜ ˜ ˜ Now if a ˜ , b ∈ F(R), it is easy to show that if a ˜  b, then a ˜ − b  0. The following lemma immediately follows form Deﬁnition 1. Lemma 1 If a ˜, b ∈ F(R), and c ∈ R such that c  0, then ˜ ˜ (i) a ˜ b ≈ b a ˜, 62 S.H. Nasseri · N.Mahdavi-Amiri (2009) ˜ ˜ ˜ (ii) c(˜ a b) ≈ (ca ˜ ) b ≈ a ˜ (cb). Two following results taken from [4] and we omit the details and proofs. Lemma 2 For any symmetric trapezoidal fuzzy number a ˜, b and c, ˜ we have ˜ ˜ (i) c ˜(˜ a+ b) ≈ (˜ ca ˜ + c ˜b), ˜ ˜ (ii) c ˜(˜ a− b) ≈ (˜ ca ˜ − c ˜b). Here we also give some new results on arithmetic of the fuzzy numbers. Lemma 3 If a ˜, b ∈ F(R), then ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜ (i) a ˜ b  0, if and only if a ˜  0 and b  0 or a ˜  0 and b  0, ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜ (ii) a ˜ b  0, if and only if a ˜  0 and b  0,or a ˜  0 and b  0, ˜ ˜ (iii) a ˜  b, if and only if λa ˜  λb, for anyλ< 0,λ ∈ R. Proof It is straightforward. ˜ ˜ Lemma 4 Suppose that a ˜, b, c ˜ ∈ F(R) such that a ˜  b. Then ˜ ˜ (i) c ˜a ˜  c ˜b, if c ˜  0. ˜ ˜ (ii) c ˜a ˜  c ˜b, if c ˜  0. ˜ ˜ ˜ ˜ ˜ Proof From a ˜  b,wehave b− a ˜  0. Hence from Lemma 3, we have c ˜(b− a ˜ )  0, ˜ ˜ ˜ ˜ if c ˜  0, and also c ˜(b− a ˜ )  0, if c ˜  0. Now the results are clear by Lemma 2. ˜ ˜ ˜ ˜ Lemma 5 Suppose that a ˜, b, c ˜ ∈ F(R) such that a ˜ ≈ b, c ˜  0. Then, c ˜a ˜ ≈ c ˜b. Proof It is straightforward. 3. Fuzzy Linear Programming A linear programming with symmetric fuzzy numbers (LPSFN) problem is deﬁned as ([4]): max z ˜≈c ˜x ˜ (1) s.t. Ax ˜b, x ˜0, m n m×n n where b ∈ (F(R)) , c ˜ ∈ (F(R)) , A ∈ R are given and x ˜ ∈ (F(R)) is to be determined. Deﬁnition 4 We say that fuzzy vector x ˜ ∈ (F(R)) is a fuzzy feasible solution to (1) if x ˜ satisﬁes the constraints of the problem. Deﬁnition 5 A fuzzy feasible solution x ˜ is a fuzzy optimal solution for (1), if for all fuzzy feasible solution x ˜ for (1), we have c ˜ x ˜ c ˜ x. ˜ A method for solving the LPSFN problem has been given by Ganesan et al. [4]. They stated some results and proposed a new method for solving the LPSFN prob- lem without converting to crisp linear programming problem. Here we extend their results to deﬁne the dual of the linear programming problems with symmetric fuzzy numbers. Fuzzy Inf. Eng. (2009) 1: 59-66 63 4. Fuzzy basic feasible solution Here, we explore the concept of fuzzy basic feasible solution for LPSFN problems, similar to our deﬁnition of fuzzy basic feasible solution in [6]. Consider the LPSFN problem, max z ˜≈ c ˜ x ˜ s.t. Ax ˜≈ b, (2) x ˜ 0, where the parameters of the problem are as deﬁned in (1). Let A = [a ] . Assume ij m×n rank(A)=m. Partition A as [BN] where B, m× m, is nonsingular. It is obvious that rank(B)=m. Let y be the solution to By = a , where a is the jth column of the j j j coeﬃcient matrix A. It is apparent that the basic solution T −1 x ˜ = (˜ x ,··· , x ˜ ) ≈ B b, x ˜ ≈ 0 (3) B B B N 1 m T T T is a solution of Ax ˜ ≈ b. We call x ˜, accordingly partitioned as (x ˜ x ˜ ) , a fuzzy basic B N solution corresponding to basis B.If x˜  0, then the fuzzy basic solution is feasible and the corresponding fuzzy objective value is z ˜ ≈ c ˜ x ˜ , where c ˜ = (˜ c ,··· , c ˜ ). B B B B B 1 m Now, corresponding to every index j,1  j  n, deﬁne −1 z ˜ ≈ c ˜ y ≈ c ˜ B a . (4) j B j B j −1 Observe that for any basic index j = B, 1  i  m, we have B a = e where e = i j i i (0,··· , 0, 1, 0,··· , 0) is the i− th unit vector, since Be = [a ,··· , a ,··· , a ]e = i B B B i 1 i m a = a , and so we have: B j −1 z ˜ − c ˜ ≈ c ˜ B a − c ˜ ≈ c ˜ e − c ˜ ≈ c ˜ − c ˜ ≈ c ˜ − c ˜ ≈ 0. (5) j j B j j B i j B j j j The following theorem characterizes optimal solutions. The converse part of the result needs the nondegeneracy assumption of the problem, where all fuzzy basic variables corresponding to every basis B are nonzero (and hence positive). Theorem 1 (Optimality conditions.) Assume the fuzzy linear programming problem (2) is nondegenerate and B is a feasible basis. A fuzzy basic feasible solution x ˜ = −1 −1 ˜ ˜ ˜ B b  0, x ˜ ≈ 0 is optimal to (2) if and only if z ˜ ≈ c ˜ B a  c ˜ for all j, 1  j N j B j j n. T T T Proof Suppose x ˜ ≈ (˜ x x ˜ ) is a fuzzy basic feasible solution to (2), where B N −1 ˜ ˜ x ˜ ≈ B b, x ˜ ≈ 0. Then the corresponding fuzzy objective value is: B N −1 ≈ c ˜x ˜ ≈ c ˜ x ˜ ≈ c ˜ B b. (6) z ˜ ∗ ∗ B B B On the other hand, for any fuzzy basic feasible solution x ˜ to (2), we have b ≈ Ax ˜ ≈ Bx ˜ + N x ˜ . (7) B N Hence, we can rewrite (7) as follows: −1 −1 x ˜ ≈ B b− B N x ˜ . (8) B N 64 S.H. Nasseri · N.Mahdavi-Amiri (2009) Then, for any fuzzy basic feasible solution to (2), we have −1 −1 z ˜ ≈ c ˜x ˜ ≈ c ˜ x ˜ + c ˜ x ˜ ≈ c ˜ B b− (˜ c B N − c ˜ )˜ x B B N N B B N N n n −1 −1 −1 ˜ ˜ ≈ c ˜ B b− (˜ c B a − c ˜ )˜ x ≈ c ˜ B b− (˜ z − c ˜ )˜ x . B B j j j B j j j j=1 j=1 Hence, using (5) and (6), we have: z ˜ ≈ z ˜ − (˜ z − c ˜ )˜ x . (9) ∗ j j j jB Now, if for all j,1  j  n we have z ˜  c ˜ , then from feasibility of x ˜ we have j j ˜ ˜ (˜ z − c ˜ )˜ x  0, and then we obtain (˜ z − c ˜ )˜ x  0. Therefore, it follows from (9) j j j j j j jB that z ˜  z ˜ , and so x ˜ is optimal. For “ only if ” part, let x ˜ be a fuzzy optimal basic ∗ ∗ ∗ feasible solution to (2). For j = B, 1  i  m, from (5) we know that z ˜ − c ˜ ≈ 0. i j j From (9) it is obvious that if for any nonbasic variable x ˜ we have z ˜ ≺ c ˜ , then we j j j can enter x ˜ into the basis and obtain z ˜ ≺ z ˜ (because the problem is nondegenerate j ∗ and x ˜  0 in the new basis). This is a contradiction to z ˜ being optimal. Hence we j ∗ must have z ˜  c ˜ , 1  j  n. j j Now we state some results given in [4] and omit the proofs. −1 Theorem 2 Let x ˜ ≈ B b is a fuzzy basic feasible solution of (2). If for any column a in A which is not in B, the condition (˜ z − c ˜ ) ≺ 0 hold and y > 0 for some j j j ij i, 1  i  m, then it is possible to obtain a new fuzzy basic feasible solution by one of the columns in B by a . −1 Theorem 3 If x ˜ ≈ B b is a fuzzy basic feasible solution of (2) with z ˜ ≈ c ˜ x ˜ as the B 0 B B fuzzy value of the objective function and if x ¯ is another fuzzy basic feasible solution with z ¯ ≈ c ¯ x ¯ obtained by admitting a nonbasic column vector a in the basic for B B j which (˜ z − c ˜ ) ≺ 0 and y > 0 for some i, 1  i  m, then z ¯  z ˜ . j j ij 0 −1 Theorem 4 Let x ˜ ≈ B b is a fuzzy basic feasible solution of (2). If there exist an a B j in A which is not in B such that (˜ z − c ˜ ) ≺ 0 and y  0, for all i, 1  i  m, then the j j ij fuzzy linear programming problem (2) has an unbounded solution. 5. Duality 5.1 Formulation of the dual problem For the following LPSFN problem max z ˜≈ c ˜x ˜ (10) s.t. Ax ˜ b, x ˜ 0, deﬁne the dual of LPSFN problem (DLPSFN) as: min u ˜ ≈ w ˜ b (11) s.t. wA ˜ c ˜, w ˜  0. Fuzzy Inf. Eng. (2009) 1: 59-66 65 5.2 Relations between LPSFN and DLPSFN problems Here we shall discuss some relationships between the LPSFN problem and its corre- sponding dual. Theorem 5 Dual of DLPSFN is LPSFN. Proof Since the DLPSFN problem is a fuzzy linear programming problem, we may consider the dual deﬁnition on DLPSFN problem. Hence, write DLPSFN problem as follows: max (−b)˜ w (12) s.t. w ˜ (−A) (−c ˜), w ˜  0. Now the DLPSFN is in form (10). So the dual of the current LPSFN problem is as follows: min (−c ˜)˜ x (13) s.t. (−A)˜ x (−b), x ˜ 0, where x ˜ play the role of the fuzzy vector of dual variables and this problem is the same as max c ˜ x ˜ (14) s.t. Ax ˜ b, x ˜ 0, which is precisely the original fuzzy primal problem. Remark 3. Theorem 5 indicates that the duality results can be applied to any of the primal or dual problems posed as the primal problem. Theorem 6 (The weak duality property.) If x ˜ and w ˜ are feasible solutions to LPSFN 0 0 and DLPSFN problems, respectively, then c ˜x ˜  w ˜ b. 0 0 ˜ ˜ Proof Multiplying Ax ˜  b on the left by w ˜  0 and w ˜ A  c ˜ on the right by 0 0 0 ˜ ˜ x ˜  0 and using Lemma 4, we get c ˜x ˜  w ˜ Ax ˜  w ˜ b. 0 0 0 0 0 Corollary 1 If x ˜ and w ˜ are feasible solutions to LPSFN and DLPSFN problems, 0 0 respectively, and c ˜x ˜ ≈ w ˜ b, then x ˜ and w ˜ are optimal solutions to their respective 0 0 0 0 problems. Proof It is straightforward, using Theorem 6. The following corollary relates unboundeness of one problem to infeasibility of the other. We use the deﬁnition below. Deﬁnition 6 We say LPSFN problem (or DLPSFN problem) is unbounded if feasible solutions exist with arbitrary large (or small) fuzzy objective value. Corollary 2 If any one of the LPSFN or DLPSFN problem is unbounded, then the other problem has no feasible solution. Proof It is straightforward, using Theorem 6. 66 S.H. Nasseri · N.Mahdavi-Amiri (2009) 6. Conclusions In this paper we used the new deﬁnition of fuzzy arithmetic which was proposed by Ganesan et.al to obtain the optimality condition for LPSFN problems and then deﬁned the dual of a linear programming problems with symmetric fuzzy numbers. In particular we stated some duality results as a natural extensions of the duality results in crisp environments. Acknowledgments The ﬁrst and second authors respectively thanks to the Research Center of Algebraic Hyperstructurs and Fuzzy Mathematics and the Research Council of Sharif Univer- sity of Technology for their partly supports. References 1. L. Campos, J.L. Verdegay (1989) Linear programming problems and ranking of fuzzy numbers. Fuzzy Sets and Systems 32: 1-11 2. S. Chanas (1983) The use of parametric programming in fuzzy linear programming. Fuzzy Sets and Systems 11: 243-251 3. M. Delgado, J.L. Verdegay and M.A. Vila (1989) A general model for fuzzy linear programming. Fuzzy Sets and Systems 29: 21-29 4. K. Ganesan, P. Veeramani (2006) Fuzzy linear programming with trapezoidal fuzzy numbers. Ann. Oper. Res. 143: 305-315 5. N. Mahdavi-Amiri, S.H. Nasseri (2006) Duality in fuzzy number linear programming by use of a certain linear ranking function. Applied Mathematics and Computation 180: 206-216 6. N. Mahdavi-Amiri, S.H. Nasseri (2007) Duality results and a dual simplex method for linear pro- gramming with trapezoidal fuzzy variables. Fuzzy Sets and Systems 158: 1961-1978 7. H.R. Maleki, M. Tata and M. Mashinchi, (2000) Linear programming with fuzzy variables. Fuzzy Sets and Systems 109: 21-33 8. J. Ramik (2005) Dualiy in fuzzy linear programming: some new concepts and results. Fuzzy Opti- mization and Decisin Making 4: 25-39 9. J. Ramik (2003) Dualiy in fuzzy linear programming based on fuzzy relations. Proceedings of the 10th IFSA World Congress, June 29- July 2, Istanbul, Turkey 10. W. Rodder, H.J. Zimmermann (1977) Dualiy in fuzzy linear programming. In Internat. Symp. On Extremal Methods and Systems Analysis, University of Texas at Austin 415-427. (Proceedings, A.V. Fiacco and K.O. Kortanek (eds.), Berlin, Heidelberg, New York, 1980) 11. H. Tanaka, T. Okuda and K. Asai (1974) On fuzzy mathematical programming. The Journal of Cybernetics 3: 37-46 12. J.L. Verdegay (1984) A dual approach to solve the fuzzy linear programming problems. Fuzzy Sets and Systems 14: 131-141 13. Wu, H.C. (2003) Duality theory in fuzzy linear programming problems with fuzzy coeﬃcients. Fuzzy Optimization and Decision Making 2: 61-73 14. Wu, H.C. (2003) Duality theorems in fuzzy mathematical programming problems based on the con- cept of necessity. Fuzzy Sets and Systems 139: 363-377 15. H. J. Zimmermann (1978) Fuzzy programming and linear programming with several objective func- tions. Fuzzy Sets and Systems 1: 45-55 http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Fuzzy Information and Engineering Taylor & Francis

# Some Duality Results on Linear Programming Problems with Symmetric Fuzzy Numbers

, Volume 1 (1): 8 – Mar 1, 2009
8 pages

/lp/taylor-francis/some-duality-results-on-linear-programming-problems-with-symmetric-8waOOzTo6j

# References (16)

Publisher
Taylor & Francis
© 2009 Taylor and Francis Group, LLC
ISSN
1616-8666
eISSN
1616-8658
DOI
10.1007/s12543-009-0004-2
Publisher site
See Article on Publisher Site

### Abstract

Fuzzy Inf. Eng. (2009)1: 59-66 DOI 10.1007/s12543-009-0004-2 ORIGINAL ARTICLE Some Duality Results on Linear Programming Problems with Symmetric Fuzzy Numbers S.H. Nasseri · N.Mahdavi-Amiri Received: 18 May 2008/ Revised: 20 August 2008/ Accepted: 19 December 2008/ © Springer and Fuzzy Information and Engineering Branch of the Operations Research Society of China Abstract Recently, linear programming problems with symmetric fuzzy numbers (LPSFN) have considered by some authors and have proposed a new method for solv- ing these problems without converting to the classical linear programming problem, where the cost coeﬃcients are symmetric fuzzy numbers (see in [4]). Here we extend their results and ﬁrst prove the optimality theorem and then deﬁne the dual problem of LPSFN problem. Furthermore, we give some duality results as a natural extensions of duality results for linear programming problems with crisp data. Keywords Duality results · Fuzzy basic feasible solution · Fuzzy linear program- ming · Symmetric fuzzy numbers 1. Introduction Fuzzy set theory has been applied to many disciplines such as control theory and op- erations research, mathematical modeling and industrial applications. The concept of fuzzy mathematical programming on general level was ﬁrst proposed by Tanaka et al. [11]. The ﬁrst formulation of fuzzy linear programming is proposed by Zimmer- mann [15]. Afterwards, many authors considered various types of the fuzzy linear programming problems and proposed several approaches for solving these problems [1-7], [12]. Chanas [2] showed an application of parametric programming techniques in fuzzy linear programming and obtained the set of solutions maximizing the objec- tive function, being analytically dependent on a parameter. Delgado et al. [3] studied a general model for fuzzy linear programming problems which includes fuzziness S.H. Nasseri () Department of Mathematics, Mazandaran University, Babolsar, Iran and National Elite Foundation, Tehran, Iran e-mail: nasseri@umz.ac.ir N. Mahdavi-Amiri Department of Mathematics, Sharif University of Technology, Tehran, Iran e-mail: nezamm@sharif.edu 60 S.H. Nasseri · N.Mahdavi-Amiri (2009) both in the coeﬃcients and in the accomplishment of the constraints. Some authors used the concept of comparison of fuzzy numbers for solving fuzzy linear program- ming problems [1], [5-7]. Nevertheless, usually in such methods authors deﬁne a crisp model which is equivalent to the fuzzy linear programming problem and then use optimal solution of the model as the optimal solution of the fuzzy linear program- ming problem. Some authors considered types of linear programming problems in which the variables and the right-hand-sides of the constraints are fuzzy parameters [4], [5-7]. The study of duality theory for fuzzy parameter linear programming problems has attracted researchers in fuzzy decision theory. The duality of fuzzy parameter linear programming was ﬁrst studied by Rodder and Zimmermann [10]. Verdegay [12] deﬁned the fuzzy dual problem with the help of parametric linear programming and showed that the fuzzy primal and dual problems both have the same fuzzy solu- tion under some suitable conditions. The fuzzy primal and dual linear programming problems with fuzzy coeﬃcients were formulated by using the fuzzy scalar product proposed in [13]. Ramik [8,9] discussed a class of fuzzy linear programming prob- lems based on fuzzy relations and a new concept of duality and deduced the weak and strong duality theorems. Wu [14] oﬀered a concept of fuzzy scalar product and proved the weak and strong duality theorems using a dual fuzzy mathematical programming problem. Recently, a new method for solving linear programming with symmetric fuzzy numbers (LPSFN) proposed by Ganesan et al. [4]. Their method can solve these problems without converting to the classical linear programming problem. In this paper, we deﬁne the dual of LPSFN problems and state some duality results. This paper is organized in 6 sections. In the next section, we ﬁrst give some nec- essary notations and deﬁnitions of fuzzy set theory. Then we provide a discussion of fuzzy arithmetic. The deﬁnition of the fuzzy linear programming problem is given in Section 3. Section 4 explains the notion of fuzzy basic feasible solution. We deﬁne the dual of LPSFN problems in Section 5 and deduce some duality results. We ﬁnally conclude in Section 6. 2. Preliminaries We review the main concept of fuzzy set theory (taken from [4] and [6]). Deﬁnition 1 A fuzzy number a ˜ on R is said to be a symmetric trapezoidal fuzzy L U L U number if there exist real numbers a and a ,a  a andα  0 such that x α− a L L + , x ∈ [a −α, a ], α α ⎪ L U 1, x ∈ [a , a ], a ˜ (x) = ⎪ −x a +α U U ⎪ + , x ∈ [a , a +α], ⎪ α α 0, otherwise. Fuzzy Inf. Eng. (2009) 1: 59-66 61 L U L We denote symmetric trapezoidal fuzzy number a ˜ by a ˜ = (a , a ,α), where (a − U L U α, a + α) is the support of a ˜ and [a , a ] its core, and the set of all symmetric trapezoidal fuzzy numbers by F(R). L U L U Let a ˜ = (a , a ,α) and b = (b , b ,β) be two symmetric trapezoidal fuzzy num- bers. Then the arithmetic operations on a ˜ and b are given as follows: L L U U Addition: a ˜ + b = (a + b , a + b ,α+β). L U U L Subtraction: a ˜ − b = (a − b , a − b ,α+β). L U L U L U L U a + a b + b a + a b + b U U Multiplication: a ˜ b = (( )( )−ω, ( )( )+ω,|a β+b α|), 2 2 2 2 t − t 2 1 L L L U U L U U L L L U U L where ω = , t = min{a b , a b , a b , a b }, t = max{a b , a b , a b , 1 2 U U a b }. From the above deﬁnition it is clear that L U λ  0,λ ∈ R; λ a ˜ = (λa ,λa ,λα), U L λ< 0,λ ∈ R; λ a ˜ = (λa ,λa ,−λα). Note that depending upon the need, one can also use a smaller ω in the deﬁnition of multiplication involving symmetric trapezoidal fuzzy numbers. L U L U Deﬁnition 2 Let a ˜ = (a , a ,α) and b = (b , b ,β) be two symmetric trapezoidal ˜ ˜ fuzzy numbers. Deﬁne the relation  as a ˜  b (or b  a ˜ ) if and only if either L U L U L U L U (a −α)+ (a +α) (b −β)+ (b +β) a + a b + b < , that is < (in this 2 2 2 2 L U L U a + a b + b L L U U case, we may write a ˜ ≺ b), or = , b < a and a < b ,or 2 2 L U L U a + a b + b L L U U = , b = a , a = b andα  β. 2 2 ˜ ˜ Note that in the two above cases, we also write a ˜ ≈ b and say that a ˜ and b are equivalent. L U L U Remark 1. Two symmetric trapezoidal fuzzy numbers a ˜ = (a , a ,α), b = (b , b ,β) L U L U a + a b + b are equivalent if and only if = . 2 2 Deﬁnition 3 For any trapezoidal fuzzy number a, ˜ we deﬁne a ˜ 0, if there exist ε  0 and α  0 such that a ˜ (−ε,ε,α). We also denote (−ε,ε,α) by 0. Note that ˜ ˜ 0 is equivalent to (0, 0, 0) = 0. Naturally, one may consider 0 = (0, 0, 0) as zero symmetric triangular fuzzy number. Remark 2. If x ˜ ≈ 0, then x ˜ is said to be a zero symmetric trapezoidal fuzzy ˜ ˜ number. It is to be noted that if x ˜ = 0, then x ˜ ≈ 0, but the converse need not be true. ˜ ˜ If x ˜  0 (that is x ˜ is not equivalent to 0), then is said to be a non-zero symmetric ˜ ˜ trapezoidal fuzzy number. It is to be noted that if x ˜  0, then x ˜  0, but the converse ˜ ˜ ˜ need not be true. If x ˜  0(x˜  0) and x ˜  0, then is said to be a positive (negative) ˜ ˜ symmetric trapezoidal fuzzy number and is denoted by x ˜  0(x˜ ≺ 0). ˜ ˜ ˜ ˜ Now if a ˜ , b ∈ F(R), it is easy to show that if a ˜  b, then a ˜ − b  0. The following lemma immediately follows form Deﬁnition 1. Lemma 1 If a ˜, b ∈ F(R), and c ∈ R such that c  0, then ˜ ˜ (i) a ˜ b ≈ b a ˜, 62 S.H. Nasseri · N.Mahdavi-Amiri (2009) ˜ ˜ ˜ (ii) c(˜ a b) ≈ (ca ˜ ) b ≈ a ˜ (cb). Two following results taken from [4] and we omit the details and proofs. Lemma 2 For any symmetric trapezoidal fuzzy number a ˜, b and c, ˜ we have ˜ ˜ (i) c ˜(˜ a+ b) ≈ (˜ ca ˜ + c ˜b), ˜ ˜ (ii) c ˜(˜ a− b) ≈ (˜ ca ˜ − c ˜b). Here we also give some new results on arithmetic of the fuzzy numbers. Lemma 3 If a ˜, b ∈ F(R), then ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜ (i) a ˜ b  0, if and only if a ˜  0 and b  0 or a ˜  0 and b  0, ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜ (ii) a ˜ b  0, if and only if a ˜  0 and b  0,or a ˜  0 and b  0, ˜ ˜ (iii) a ˜  b, if and only if λa ˜  λb, for anyλ< 0,λ ∈ R. Proof It is straightforward. ˜ ˜ Lemma 4 Suppose that a ˜, b, c ˜ ∈ F(R) such that a ˜  b. Then ˜ ˜ (i) c ˜a ˜  c ˜b, if c ˜  0. ˜ ˜ (ii) c ˜a ˜  c ˜b, if c ˜  0. ˜ ˜ ˜ ˜ ˜ Proof From a ˜  b,wehave b− a ˜  0. Hence from Lemma 3, we have c ˜(b− a ˜ )  0, ˜ ˜ ˜ ˜ if c ˜  0, and also c ˜(b− a ˜ )  0, if c ˜  0. Now the results are clear by Lemma 2. ˜ ˜ ˜ ˜ Lemma 5 Suppose that a ˜, b, c ˜ ∈ F(R) such that a ˜ ≈ b, c ˜  0. Then, c ˜a ˜ ≈ c ˜b. Proof It is straightforward. 3. Fuzzy Linear Programming A linear programming with symmetric fuzzy numbers (LPSFN) problem is deﬁned as ([4]): max z ˜≈c ˜x ˜ (1) s.t. Ax ˜b, x ˜0, m n m×n n where b ∈ (F(R)) , c ˜ ∈ (F(R)) , A ∈ R are given and x ˜ ∈ (F(R)) is to be determined. Deﬁnition 4 We say that fuzzy vector x ˜ ∈ (F(R)) is a fuzzy feasible solution to (1) if x ˜ satisﬁes the constraints of the problem. Deﬁnition 5 A fuzzy feasible solution x ˜ is a fuzzy optimal solution for (1), if for all fuzzy feasible solution x ˜ for (1), we have c ˜ x ˜ c ˜ x. ˜ A method for solving the LPSFN problem has been given by Ganesan et al. [4]. They stated some results and proposed a new method for solving the LPSFN prob- lem without converting to crisp linear programming problem. Here we extend their results to deﬁne the dual of the linear programming problems with symmetric fuzzy numbers. Fuzzy Inf. Eng. (2009) 1: 59-66 63 4. Fuzzy basic feasible solution Here, we explore the concept of fuzzy basic feasible solution for LPSFN problems, similar to our deﬁnition of fuzzy basic feasible solution in [6]. Consider the LPSFN problem, max z ˜≈ c ˜ x ˜ s.t. Ax ˜≈ b, (2) x ˜ 0, where the parameters of the problem are as deﬁned in (1). Let A = [a ] . Assume ij m×n rank(A)=m. Partition A as [BN] where B, m× m, is nonsingular. It is obvious that rank(B)=m. Let y be the solution to By = a , where a is the jth column of the j j j coeﬃcient matrix A. It is apparent that the basic solution T −1 x ˜ = (˜ x ,··· , x ˜ ) ≈ B b, x ˜ ≈ 0 (3) B B B N 1 m T T T is a solution of Ax ˜ ≈ b. We call x ˜, accordingly partitioned as (x ˜ x ˜ ) , a fuzzy basic B N solution corresponding to basis B.If x˜  0, then the fuzzy basic solution is feasible and the corresponding fuzzy objective value is z ˜ ≈ c ˜ x ˜ , where c ˜ = (˜ c ,··· , c ˜ ). B B B B B 1 m Now, corresponding to every index j,1  j  n, deﬁne −1 z ˜ ≈ c ˜ y ≈ c ˜ B a . (4) j B j B j −1 Observe that for any basic index j = B, 1  i  m, we have B a = e where e = i j i i (0,··· , 0, 1, 0,··· , 0) is the i− th unit vector, since Be = [a ,··· , a ,··· , a ]e = i B B B i 1 i m a = a , and so we have: B j −1 z ˜ − c ˜ ≈ c ˜ B a − c ˜ ≈ c ˜ e − c ˜ ≈ c ˜ − c ˜ ≈ c ˜ − c ˜ ≈ 0. (5) j j B j j B i j B j j j The following theorem characterizes optimal solutions. The converse part of the result needs the nondegeneracy assumption of the problem, where all fuzzy basic variables corresponding to every basis B are nonzero (and hence positive). Theorem 1 (Optimality conditions.) Assume the fuzzy linear programming problem (2) is nondegenerate and B is a feasible basis. A fuzzy basic feasible solution x ˜ = −1 −1 ˜ ˜ ˜ B b  0, x ˜ ≈ 0 is optimal to (2) if and only if z ˜ ≈ c ˜ B a  c ˜ for all j, 1  j N j B j j n. T T T Proof Suppose x ˜ ≈ (˜ x x ˜ ) is a fuzzy basic feasible solution to (2), where B N −1 ˜ ˜ x ˜ ≈ B b, x ˜ ≈ 0. Then the corresponding fuzzy objective value is: B N −1 ≈ c ˜x ˜ ≈ c ˜ x ˜ ≈ c ˜ B b. (6) z ˜ ∗ ∗ B B B On the other hand, for any fuzzy basic feasible solution x ˜ to (2), we have b ≈ Ax ˜ ≈ Bx ˜ + N x ˜ . (7) B N Hence, we can rewrite (7) as follows: −1 −1 x ˜ ≈ B b− B N x ˜ . (8) B N 64 S.H. Nasseri · N.Mahdavi-Amiri (2009) Then, for any fuzzy basic feasible solution to (2), we have −1 −1 z ˜ ≈ c ˜x ˜ ≈ c ˜ x ˜ + c ˜ x ˜ ≈ c ˜ B b− (˜ c B N − c ˜ )˜ x B B N N B B N N n n −1 −1 −1 ˜ ˜ ≈ c ˜ B b− (˜ c B a − c ˜ )˜ x ≈ c ˜ B b− (˜ z − c ˜ )˜ x . B B j j j B j j j j=1 j=1 Hence, using (5) and (6), we have: z ˜ ≈ z ˜ − (˜ z − c ˜ )˜ x . (9) ∗ j j j jB Now, if for all j,1  j  n we have z ˜  c ˜ , then from feasibility of x ˜ we have j j ˜ ˜ (˜ z − c ˜ )˜ x  0, and then we obtain (˜ z − c ˜ )˜ x  0. Therefore, it follows from (9) j j j j j j jB that z ˜  z ˜ , and so x ˜ is optimal. For “ only if ” part, let x ˜ be a fuzzy optimal basic ∗ ∗ ∗ feasible solution to (2). For j = B, 1  i  m, from (5) we know that z ˜ − c ˜ ≈ 0. i j j From (9) it is obvious that if for any nonbasic variable x ˜ we have z ˜ ≺ c ˜ , then we j j j can enter x ˜ into the basis and obtain z ˜ ≺ z ˜ (because the problem is nondegenerate j ∗ and x ˜  0 in the new basis). This is a contradiction to z ˜ being optimal. Hence we j ∗ must have z ˜  c ˜ , 1  j  n. j j Now we state some results given in [4] and omit the proofs. −1 Theorem 2 Let x ˜ ≈ B b is a fuzzy basic feasible solution of (2). If for any column a in A which is not in B, the condition (˜ z − c ˜ ) ≺ 0 hold and y > 0 for some j j j ij i, 1  i  m, then it is possible to obtain a new fuzzy basic feasible solution by one of the columns in B by a . −1 Theorem 3 If x ˜ ≈ B b is a fuzzy basic feasible solution of (2) with z ˜ ≈ c ˜ x ˜ as the B 0 B B fuzzy value of the objective function and if x ¯ is another fuzzy basic feasible solution with z ¯ ≈ c ¯ x ¯ obtained by admitting a nonbasic column vector a in the basic for B B j which (˜ z − c ˜ ) ≺ 0 and y > 0 for some i, 1  i  m, then z ¯  z ˜ . j j ij 0 −1 Theorem 4 Let x ˜ ≈ B b is a fuzzy basic feasible solution of (2). If there exist an a B j in A which is not in B such that (˜ z − c ˜ ) ≺ 0 and y  0, for all i, 1  i  m, then the j j ij fuzzy linear programming problem (2) has an unbounded solution. 5. Duality 5.1 Formulation of the dual problem For the following LPSFN problem max z ˜≈ c ˜x ˜ (10) s.t. Ax ˜ b, x ˜ 0, deﬁne the dual of LPSFN problem (DLPSFN) as: min u ˜ ≈ w ˜ b (11) s.t. wA ˜ c ˜, w ˜  0. Fuzzy Inf. Eng. (2009) 1: 59-66 65 5.2 Relations between LPSFN and DLPSFN problems Here we shall discuss some relationships between the LPSFN problem and its corre- sponding dual. Theorem 5 Dual of DLPSFN is LPSFN. Proof Since the DLPSFN problem is a fuzzy linear programming problem, we may consider the dual deﬁnition on DLPSFN problem. Hence, write DLPSFN problem as follows: max (−b)˜ w (12) s.t. w ˜ (−A) (−c ˜), w ˜  0. Now the DLPSFN is in form (10). So the dual of the current LPSFN problem is as follows: min (−c ˜)˜ x (13) s.t. (−A)˜ x (−b), x ˜ 0, where x ˜ play the role of the fuzzy vector of dual variables and this problem is the same as max c ˜ x ˜ (14) s.t. Ax ˜ b, x ˜ 0, which is precisely the original fuzzy primal problem. Remark 3. Theorem 5 indicates that the duality results can be applied to any of the primal or dual problems posed as the primal problem. Theorem 6 (The weak duality property.) If x ˜ and w ˜ are feasible solutions to LPSFN 0 0 and DLPSFN problems, respectively, then c ˜x ˜  w ˜ b. 0 0 ˜ ˜ Proof Multiplying Ax ˜  b on the left by w ˜  0 and w ˜ A  c ˜ on the right by 0 0 0 ˜ ˜ x ˜  0 and using Lemma 4, we get c ˜x ˜  w ˜ Ax ˜  w ˜ b. 0 0 0 0 0 Corollary 1 If x ˜ and w ˜ are feasible solutions to LPSFN and DLPSFN problems, 0 0 respectively, and c ˜x ˜ ≈ w ˜ b, then x ˜ and w ˜ are optimal solutions to their respective 0 0 0 0 problems. Proof It is straightforward, using Theorem 6. The following corollary relates unboundeness of one problem to infeasibility of the other. We use the deﬁnition below. Deﬁnition 6 We say LPSFN problem (or DLPSFN problem) is unbounded if feasible solutions exist with arbitrary large (or small) fuzzy objective value. Corollary 2 If any one of the LPSFN or DLPSFN problem is unbounded, then the other problem has no feasible solution. Proof It is straightforward, using Theorem 6. 66 S.H. Nasseri · N.Mahdavi-Amiri (2009) 6. Conclusions In this paper we used the new deﬁnition of fuzzy arithmetic which was proposed by Ganesan et.al to obtain the optimality condition for LPSFN problems and then deﬁned the dual of a linear programming problems with symmetric fuzzy numbers. In particular we stated some duality results as a natural extensions of the duality results in crisp environments. Acknowledgments The ﬁrst and second authors respectively thanks to the Research Center of Algebraic Hyperstructurs and Fuzzy Mathematics and the Research Council of Sharif Univer- sity of Technology for their partly supports. References 1. L. Campos, J.L. Verdegay (1989) Linear programming problems and ranking of fuzzy numbers. Fuzzy Sets and Systems 32: 1-11 2. S. Chanas (1983) The use of parametric programming in fuzzy linear programming. Fuzzy Sets and Systems 11: 243-251 3. M. Delgado, J.L. Verdegay and M.A. Vila (1989) A general model for fuzzy linear programming. Fuzzy Sets and Systems 29: 21-29 4. K. Ganesan, P. Veeramani (2006) Fuzzy linear programming with trapezoidal fuzzy numbers. Ann. Oper. Res. 143: 305-315 5. N. Mahdavi-Amiri, S.H. Nasseri (2006) Duality in fuzzy number linear programming by use of a certain linear ranking function. Applied Mathematics and Computation 180: 206-216 6. N. Mahdavi-Amiri, S.H. Nasseri (2007) Duality results and a dual simplex method for linear pro- gramming with trapezoidal fuzzy variables. Fuzzy Sets and Systems 158: 1961-1978 7. H.R. Maleki, M. Tata and M. Mashinchi, (2000) Linear programming with fuzzy variables. Fuzzy Sets and Systems 109: 21-33 8. J. Ramik (2005) Dualiy in fuzzy linear programming: some new concepts and results. Fuzzy Opti- mization and Decisin Making 4: 25-39 9. J. Ramik (2003) Dualiy in fuzzy linear programming based on fuzzy relations. Proceedings of the 10th IFSA World Congress, June 29- July 2, Istanbul, Turkey 10. W. Rodder, H.J. Zimmermann (1977) Dualiy in fuzzy linear programming. In Internat. Symp. On Extremal Methods and Systems Analysis, University of Texas at Austin 415-427. (Proceedings, A.V. Fiacco and K.O. Kortanek (eds.), Berlin, Heidelberg, New York, 1980) 11. H. Tanaka, T. Okuda and K. Asai (1974) On fuzzy mathematical programming. The Journal of Cybernetics 3: 37-46 12. J.L. Verdegay (1984) A dual approach to solve the fuzzy linear programming problems. Fuzzy Sets and Systems 14: 131-141 13. Wu, H.C. (2003) Duality theory in fuzzy linear programming problems with fuzzy coeﬃcients. Fuzzy Optimization and Decision Making 2: 61-73 14. Wu, H.C. (2003) Duality theorems in fuzzy mathematical programming problems based on the con- cept of necessity. Fuzzy Sets and Systems 139: 363-377 15. H. J. Zimmermann (1978) Fuzzy programming and linear programming with several objective func- tions. Fuzzy Sets and Systems 1: 45-55

### Journal

Fuzzy Information and EngineeringTaylor & Francis

Published: Mar 1, 2009

Keywords: Duality results; Fuzzy basic feasible solution; Fuzzy linear programming; Symmetric fuzzy numbers