Applied Mathematics, 2011, 2, 676684 doi:10.4236/am.2011.26089 Published Online June 2011 (http://www.SciRP.org/journal/am) Copyright © 2011 SciRes. AM A PrimalDual Simplex Algorithm for Solving Linear Programming Problems with Symmetric Trapezoidal Fuzzy Numbers Ali Ebrahimnejad Department of Mat hematics, Qaemshahr Branch, Islamic Azad University, Qaemshar, Iran Email: aebrahimnejad@srbiau.ac.ir, aemarzoun@gmail.com Received December 2, 2010; revised March 28, 201 1; accepted April 1, 2011 Abstract Two existing methods for solving a class of fuzzy linear programming (FLP) problems involving symmetric trapezoidal fuzzy numbers without converting them to crisp linear programming problems are the fuzzy pri mal simplex method proposed by Ganesan and Veeramani [1] and the fuzzy dual simplex method proposed by Ebrahimnejad and Nasseri [2]. The former method is not applicable when a primal basic feasible solution is not easily at hand and the later method needs to an initial dual basic feasible solution. In this paper, we develop a novel approach namely the primaldual simplex algorithm to overcome mentioned shortcomings. A numerical example is given to illustrate the proposed approach. Keywords: Fuzzy Linear Programming, Fuzzy Arithmetic, Fuzzy Orders, PrimalDual Simplex Algorithm 1. Introduction In optimizing real world systems, one usually ends up with a linear or nonlinear programming problem. For many cases, the coefficients involved in the objective and constraint functions are imprecise in nature and have to be interpreted as fuzzy numbers to reflect the real world situation. The resulting mathematical problem is therefore referred to as a fuzzy mathematical program ming problem. After the pioneering work on fuzzy linear programming by Tanaka et al. [3,4] and Zimmermann [5], several kinds of fuzzy linear programming problems have appeared in the literature and different methods have been proposed to solve such problems [612]. One important class of these methods that has been high lighted by many researches is based on comparing of fuzzy numbers using ranking functions. Based on this idea, Maleki et al. [13] proposed a simple method for solving fuzzy number linear programming (FNLP) pro blems. They also applied an special kind of FNLP pro blems, involving fuzzy numbers only in objective func tion, as an auxiliary problem for solving fuzzy variable linear programming (FVLP) problems. Ebrahimnejad et al. [14] developed their method for solving bounded linear programming with fuzzy cost coefficients. Then Mahdavi Amiri and Nasseri [15] used the certain linear ranking function to define th e dual of FNLP problem as a similar problem that lead to an efficient algorithm called the dual simplex algorithm [16] for solving FNLP problems. Based on these algorithms, Ebrahimnejad [17] inves tigated the concept of sensitivity analysis in FNLP pro blems. Of course, MahdaviAmiri and Nasseri [18] and MahdaviAmiri et al. [19] proposed two efficient algo rithms for solving FVLP problems directly without need of any auxiliary problem. Moreover, Nasseri and Ebra himnejad [20] suggested the fuzzy primal simplex me thod to solve the flexible linear programming problems directly without solving any auxiliary problem. Then, Ebrahimnejad et al. [6] gave another efficient method namely primaldual simplex method to obtain the fuzzy solution of FVLP problems. Ebrahimnejad and Nasseri [21] used the complementary slackness for solving both FNLP problem and FVLP problem. Hosseinzadeh Lotfi et al. [9] discussed full fuzzy linear programming (FFLP) problems of which all parameters and variable are triangular fuzzy numbers. They used the concept of the symmetric triangular fuzzy number and proposed an approach to defuzzify a general fuzzy quantity. After that Kumar et al. [11] proposed a new method to find the fuzzy optimal solution of same type of fuzzy linear programm i ng pr o bl e ms. Recently Ganesan and Veeramani [1] introduced a
A. EBRAHIMNEJAD677 new method based on primal simplex algorithm for solving linear programming problem with symmetric trapezoidal fuzzy numbers without converting them to crisp linear programming problems. Ebrahimnejad et al. [7] extended their method for situations in which some or all variables are restricted to lie within fuzzy lower and fuzzy upper bounds. After that, Nasseri and Mahdavi Amiri [22] and Nasseri et al. [23] developed the concept of duality of such problems that led to a new method based on dual simplex algorithm [2]. However, dual simplex algorithm begins with a basic (not necessarily feasible) dual solution and proceeds by pivoting through a series of dual basic fuzzy solution until the associated complementary primal basic solution is feasible. In this paper, we describe a new method for solving linear programming problem with symmetric trapezoidal fuzzy numbers, called the primaldual algorithm, similar to the dual simplex method, which begins with dual feasibility and proceeds to obtain primal feasibility while main taining complementary slackness. An important diffe rence between the dual simplex method and the dual simplex method is that the primaldual simplex method does not require a dual feasible solution to be basic. This paper is organized as follows: In Section 2, we give some necessary concepts of fuzzy set theory. A review of linear programming problems with symmetric trapezoidal fuzzy numbers and two methods for solving such fuzzy problems are given in Section 3. We develop and present a fuzzy primaldual algorithm to solve the fuzzy linear programming problems in Section 4 and explain it by an illustrative example. Finally, we con clude in Section 5. 2. Preliminaries In this section, we review the fundamental notions of fuzzy set theory (see [1,7,24]). Definition 2.1. A fuzzy number on (real line) is said to be a symmetric trapezoidal fuzzy number if there exist real numbers R a and , U a U aa and >0 , such that ,, 1, , = , , 0, otherwise. LLL LU UUU xa aa xaa ax xa xaa We denote a symmetric trapezoidal fuzzy number a by =,,, LU aaa , where , LU aa is the support of and its core, and the set of all ra al fuzzy a , LU aa symmetric tpezoidnumbers by R. Let =,,, LU aaa and =,bbb,, LU be two sytric trapezoidal fbers. Then thmmeuzzy nume arith metic operations on a and b are given by (taken from [1]): =,,, LLUU aba bab =,,, LUU L aba bab =, 22 22 ,, LU LULU LU UUUU aa bbaa bb ab abab , where 21 =2 tt 1=min, , , LLLUUL UU t abababab, , x, , , LLLUUL UU tabababab. 2=ma t From the above definition it can be seen tha 0, ; =,,, LU aaa <0, ; =,,,. UL aaa Note that depending upon the need, one can also use a smaller in the definition of multiplication involving symmetric trapezoidal fuzzy num bers. Definition 2. 2. Let =,,, LU aaa and =,,, LU bbb be two symmetric trapezoidal fuzzy numbers. Define t 1) he relations and as given below: ab (or ba ) if and only if < LU LU aa b 22 b , that is < 22 ULU aa bb (in this case, we my write 2) o a ab ), r =, < 22 LU LU L aa bbba and 3) or < UU ab, =, =,= 22 LU LU LU U aa bbbaab and . n cases (2) and (3), we also write Note that iab num an d say that a and b are equivalent. Remark 2.1. Two symmetric trapezoidal fuzzy bers =,,, =,, LU aaabbb LU are equivalent if and o= 22 ULU aa bb . nly if Definition 2.3. For any trapezoidal fuzzy number a , Copyright © 2011 SciRes. AM
A. EBRAHIMNEJAD 678 , if there exist we define 0a 0 and 0 such that a,, denote ,, by symm 0 . ly . We also Note that 0 is equivalent to 0,0,0= 0 . Natural, one may cr 0 =0,0,0 e zeroetric trapember. Remark 2.2. If 0x , then onside oidal fuzzy as th z nu uis said to be a zero symmetric trapezoidmber. It is to be noted that if =0x , then 0x , but the converse need not be tru al fuzzy n is e. If 0x (that is not equivalent to 0 ), then it is said to be a nonzero symmetric trapezoidal fuzzy number to be noted that if 0x , then 0x . It is , but the convneed not be true. If 0 xx e finition 2.1. w er ma 1) The relation me z rse . o following ,ab and b 2.3. If tric trapez 0 easy to form such [1]. oidal fuzzy on t on on th and 0x , then is said to be a positive (negative) symmetric trapezoidal fuzzy number and is dd by enote , , and e taken f symmetric , then numbers. 0 0xx . Now if a , bF show it is c rom trapez order relation elati that if ab , then 0ab . The following lemma immediately follows De that e set set Lemma 2.1. If c ,ab F acb . results ar c , we hav ,ab F is a partial oidal f is a linea o 0, then 1) ab ba nu h of e of 2) cab cab tThe Lemma 2.2. For any mb e: 1) ca bcacb . 2) caca cb . Lem symuzzy 2) The relation r order r symmetric trapeidal fuzzy numbers. 3) For any two symmetric trapezoidal fuzzy numbers a and b , if ab then 1aabb , for all , 01 . 3. pe h ezo Fuzzy Linear rogramm an P ani [1] ber is defined ing introduce as [1] d a tions : Gesan aVeeram idal f nd uzzy num new ty fuzzy whic of num are fuzzy arithmetic for symmetric trapezoidal ers. Here, we first review these new nob useful in our further consideration. After that we review the concept of duality for such problems proposed by Nasseri and MahdaviAmiri [22] and Nasseri et al. [23 ] . 3.1. A Fuzzy Primal Simplex Algorithm efinition 3.1. A linear programming problem with traD p min zcx .. 0 tAxb x (1) where n are given and is a feasible solution to (1) if and only if ,, mn Tm bFc FA n xF is to be deter nition 3.2. We say that a f Defi mined. uzzy vector n xF satisfies the constraf the pro blem ints and nonnegativity restrictions o . Definition 3.3. A fuzzy feasible solution * is said to be a fuzzy optimal solution to (1), if for all fuzzy feasible solution for (1), we have * cx cx . Defi pr n 3.4. Considerming ition fuzzy linear program oblem (1) in its standard form as follows: min zcx 0 .t.Ax b x (2) where the parameters of the problem are as defined in (1). Let =ijmn Aa =Am . Partition . Assume rank BN where , is nonsingular. It is , Bmm as obvious that =rankBm. Let y be the solution to = Bya . It is apparent that the basic solution 1 ,T B m xx 1 =,, 0 BB N x Bbx (3) is a solution of = xb In fact, =,T TT BN xxx . If then the fuzzy basic solution is feasibl . objecti 0 B x ,e and e is: the corresponding fuzzy ve valu B x , where zc 1 =,, B m c BB cc . Now, corresponding to every n 1,, ,on basic variable ,1,, = ji jnjBi m 1. define Bj Bj zcycBa (4) e some important results concerning to the optimalityzy feasible Below, we stat conditions improving a fuz solution and unbounded criteria (taken Theorem 3.1. If we have a fuzzy b tio from [1]). asic feasible solu n with fuzzy objective value z such that kk zc for some nonbasic variable k , and 0 k y, then it is possible to obtain a new basic feasible solution with new fuzzy objective value z , that satisfies zz . Theorem 3.2. If we have a fuzz basic feasibl tion with kk zc for some onbasic ale k ye solu nv riab , and 0 k y , then the problem (2) has an unbounded solution. Theorem 3.3. (Optiality conditionsfum) If a basic so zzy lution 1 =, 0 BN xBbx is feasible to (2) and j zc foj, 1jn r all , then the fuzzbasic is a fuzzy optimal solution to (2). y new algorithm fo we give a summary of their method in tableau format. solution Ganesan and Veeramani [1] based on these theorems proposed a r solving problem (2). Here, Copyright © 2011 SciRes. AM
A. EBRAHIMNEJAD679 Algozzy primrithm 3.1. A fual simplex method Initialization step lutions y, and , then Suppose an initial fuzzy basic feasible solution with basis B is at hand. Form the following initial Table 1. Main step 1) Calculate j zc for all nonbasic variables. Sup pose =,,, LU jjjjj zc hhhh . Let =max UL UL kk jj hh hh jT wles. , then stop solution is optim , go to (2). 2) Let here T is the index set of the current nonbasic variab If ; the current 0 UL kk hh al. Otherwise 1 = kk Ba . nd If then stop; the problem u0 k y, is unboed. Otherwise, suppose =,,, UL iiiii bbb and determine the index r as follows: 1ik im ik 3) Update the tableau by pivoting at fuzzy basic and nonbasic variables where =min UL UL i rr bb bb >0 . i rk y yy Update the rk y. k enters the basis and r leaves the basis, and go t 3.2. A Fuzzy Dual Simplex Algorithm ) is (5) is including the fuzzy variabnstraints of problem (1). In fact, the roblem as the DFLP problem. shall discuss here the re s (taken from N m 3.4. (The weak duality property.) If o (1). Definition 3.5. Dual of the FLP problem (1 defined as follows [22,23] : max s.t. uwb wA c 0w where 1 =( ,,)m m www F les corresponding to co , =1,, i wi m is defined f oblem (1). We name this p or the ith constraint of pr We lationships between the FLP problem and its corresponding dual and omit the proofasseri and MahdaviAmiri [22] and Nasseri et al. [23]). Theore 0 and 0 are fuzzy feasible solutions to FLP and DFLP problems, respectively, then 00 cxw b . Corollary 3.1. If 0 w and 0 w are fuzzy feasible so Table 1. The initial primal simplex tableau. Basis N ... HS z 0 NNBNN zccYc =1 =B zcBb I N Y 1 =bBb to FLP and DFLP problems, respectivel 00 cxw b 0 r respective and are fuzzy optimal solu i s Corollary 3.2. any one of the FLP or DFLP problem is unbounded, then the other problem has no 0 w problemtionhes to t. If fuzzy feasible solution. Theorem 3.5. (Strong duality.) If any one of the FLP or DFLP problem has an fuzzy optimal solution, then both problems have fuzzy optimal solutions and the two optimal objective fuzzy values are equal. (In fact, if * is fuzzy optimal solution of the primal problem then the fuzzy vector * =wcB 1 B , wher e B is the optimal basis, is a fuzzy optimal solution of the dual problem). Theorem 3.6. (Complementary slackness). Suppose * and * w are feasible solutions of the FLP problem and its corresponding dual, the DFLP problem, respec tively. Then * and w are respectively optimal if and only if * **** 0, 0.wAcxwbAx Ebrahimnejad and Nasseri [2] using the above results, introduced a new fuzzdual algorithm for solving pro blem (2). Algorit y hm 3.2. A fuzzy dual simplex algorithm Initialization step Suppose that basis be dual feasible for the pro blem (2). Form the Tableau 3.1 as an initial dual feasible simplex tableau. Suppose =,,, LU B jjjjj zc hh , so UL hh0 jj for all j. Main step 1) Suppose 1 =bB b . If 0b , then Stop; the current fuzzy solution is optimal. Else suppose =, LU iii bbb,, ii and let in UL ii b 1 rim =m UL r bb b. for all Stop pivot column by tng test: 2) If 0 rj y , then ; the problem (2) is infeasible. j Else select the he followik 1 =min<0 . UL UL jj kk rj jn rk rj hh hh y yy 3) Updat e the tableau by pivoting at . Update the fu rk zzy basic and nonbasic variables where k y enters the r basis and leaves the basis, and go t 4. A Fuzzy PrimalDual Algorithm W sed basis by le bases of tion of the o (1). e note that the method which is propo by Ganesan and Veeramani in [1], starts with a fuzzy basic feasible solution for FLP and moves to an optimal walking through a sequence of fuzzy feasib FLP. All the bases with the possible excep Copyright © 2011 SciRes. AM
A. EBRAHIMNEJAD 680 ptimal basis obtained in fuzzy primal simplex algorithm o don’t satisfy the optimality criteria for FLP or feasibility condition for DFLP. But their method has no efficient when a primal basic feasible solution is not at hand. So, Ebrahimnejad and Nasseri [2] developed a new dual simplex algorithm to overcome this shortcoming by using the duality results which have been proposed by Nasseri and MahdaviAmiri [22] and Nasseri et al. [23]. This algorithm starts with a dual basic feasible solution, but primal basic infeasible solution and walks to an optimal solution by moving among adjacent dual basic feasible solutions. However, the dual simplex method for solving FLP problem needs to an initial dual basic feasible solution. Here, we develop the fuzzified version of conventional primaldual method of linear programming problems that any dual feasible solution, whether basic or not, is adequate to initiate this method. Corollary 4.1. [22,23] The optimality criteria 0 jj zc , for all j, for the FLP problem is equi valent to the feasibility condition f or the DFLP pro bl e m. To explain the main strategy employed by this method, we consider the following standard FLP: min zcx s . 0 .t xb x (6) Let 12 =,,, m wwww be the row of dual vector variables. The Dual of FLP problem (6) is The complementary slackness conditions are Let be the initial fuzzy Supp lowi primal pr where and by the method which is proposed by Ganesan and Veeramani in [1] beginning the fuzzy feasible basic solution max s.t. uw b wA c (7) 0 =1,, jjj cwax jn (8) ˆ w ose dual feasible solution. Now consider the fol ˆ =: 0 jj jwa c . ng problem known as the restricted fuzzy oblem corresponding to ˆ w . min 01 s.t. 0 ja jj a xx ax Ix 0, for , , i a i j b xj x (9) 1 =,, m aama xxx F 1,0,0,,1,1,0,0F The restricted fuzzy primal probl 1= 1,m em . (9) is now solved a . In this process, once an artificial variable a drut of the basic variables, discard it from the . Let ops o problem ˆ and 0 alue be the imal solution and fuzzy obje vobtained at termination in this re fuzzy pr ectiv stricted fuzzy primal problem, respectively. If 00x , ˆ and ˆ w are optimal to (6) and (7), respectively. If 00x , let ˆ v be the optimal solution to the dual of the restrictedzzy primal problem (9). ow, we construct the new fuzzy dual solution for (6) such that all th basic imal variables in the restricted fuzzy primal problem remain in the new restricted fuzzy primal problem and in addition, at least one riables that did not belong to the set would get to resicted fuzzy primal problem. Furthermore, this variable would reduced 0 fu N d e r pr primal va passe t if intrcede odu in th basic. In order to construct such a dual fuzzy vector, consider the following fuzzy dual w , where >0 : ˆˆ =ww v Then ˆˆ ˆˆ jjjjjj wacwvacwac va (10) Now, if ˆ with j is a basic variable in the restricted fuzzy primal prom, then ompblefrom cl acknes ementary sls ˆ va 0 j ace nd hen0 jj wa c , per primal problem. If mitting jj in the new restricted fuzzy and ˆj va 0 , then0 jj c . f) we haverom (10 wa aFinlly, if j a, we show thnd ˆj va 0 ere is a >0 such that 0 for jj cwa j with at least one compone equal ty zero. First, we show in this case for each j there is an nto fuzz such that ˆˆ 0 jjjjj j wa c va wa c . Let 12 1 =,,,, 2 jjjjjj wacwwllw wj 12 12 =, 0, ˆˆ ˆˆ , < jj jjj jj cwh h ww ww ˆˆˆ ,, j w 12 0 2 jj and wa 12 12 j v1 2 ˆˆ ˆ ˆˆ ,,0, , 2 jj jjjj j vv vakkvv Now ˆˆ jv =, >0 ˆˆ 0 jjj j wawa cva jj c , if and only if 11 ˆˆ ,,, jjjjjjjjj wvhkh 11 ˆˆ jj wv 0 j k if and only if 2 ˆ 11 2 ˆˆˆ = jjjj j wvwv if and only if 121 2 ˆˆˆˆ = jjj j vv ww if and only if Copyright © 2011 SciRes. AM
A. EBRAHIMNEJAD Copyright © 2011 SciRes. AM 681 12 12 ˆˆ =. ˆˆ j j j ww vv Note that >0 j , since 12 ˆˆ >0 jj vv and f w 12 ˆˆ <0 jj ww. That is, ie choose as above, then 0 jj wa c . Now, we define as follows: 12 12 12 12 ˆˆ ˆˆ ˆ == =min0 ˆˆ ˆˆ jj kk k. j kk j ww va vv vv j j ww ion of By definit , we see 0 kk wa c . In ad e show dition, w0 jj wa c for each with ˆ0 j va . ion of j From definit , we have for all j. Thus So, we have 12 12 ˆˆ ˆˆ . jj jjj vv vv 1212 12 ˆˆˆˆ ˆˆˆˆ . 12 jjjj jjj wwvv wwvv or j 112 2 112 2 1ˆˆˆˆ 2 ˆˆˆˆ jjjj jjj jjj wvwv wvwv that is 1 2 ˆˆˆ ˆ jjjjj wa cvawa cva j But, we know . Therefore ˆˆ 0 jjj j wa cva ˆˆ 0c va . Hence, jj jjj wa cwa odifying the dual fuzzy vector leads to a new feasible dual fuzzy Also, all the variables that belonged to the ed fuzzy primal problem basis are passed to the new basis. In add ition, a n ew fuzzy variable m solution. restrict k t cane basis, is passed to th fulem. Thus, we continu present restricted fuzzy primal prob hat is a didate to enter the restricted zzy primal probe from the lem basis by entering k , which leads to a potential reduction in 0 . This process is continued until 00x in which case we have an optimal solution or else 00x and ˆ0 j va all j for . We explain this case as Theorem 4.1 as below. Theorem 4.1. If at the end of the restricte primal m, we have 00x and ˆ0 j va for all j d fuzzy proble , then the FLP (6) halution .s no so Proof. In this case consider ˆˆ =ww v . Since ˆ0 jj wa c , for all j a assumˆ0 j va jnd byption for all , then from (10), w is a dual feasible fuzzy solution for all >0 . In he dual y value is addition, t objective fuzz ˆˆ ˆˆ wbwv bwbvb Since 0 and ˆ vb are the optimal objective values for the al problem and its dual, we have restricted fuzzy prim 0 ˆ vb x . Als, so o 00x wb can be increased indefiniteby chooing ly s arbitrarily large. Therefore the DFLP is unbounded and hence from coro llary 3.2 the FLP isble. Algorithm 4.1. A fuzzprimaldual simplex algo rithm 1) {dual feasibil infeasi y ity Choose a fuzzy vector such th } w at 0 jj zc for all j. 2) =: 0 jj waQj c and solve the ed fu c ebe the optima blem. all then stop (the FLP problem is restrict zzy rimal problem. If 00x then Stop (theurrent solutional). m p is opti let ˆ v ). Els l dual fuzzy solution to the restricted fuzzy primal pro 3) If ˆ0 j va , for j infeasible Else let 12 12 12 12 ˆˆ == ww ˆˆ ˆ =min0. ˆˆ ˆˆ jj kk j j kk jj ww va vv vv and re by k place ˆ w ˆˆ wv n of the and go to (2). Foiofuzzy primaldual algorit, we cong example. ider thSee (11)) r an illu nsider the followi .1 strat hm Example 4. Conse FLP problem: ( Thus, with introducing the slack variables 6 and 7 , the above FLP problem reduces to the stanform: dard (See (12)) 3 6,8,1,1 0,2,1,1x xx 4 4 5 12 34 5 12345 ,2 5 4,8,2,2 22 1,5,1,2 ,,,,,0 x xx xx x xxxxx 12 123 min1,5,1,1 2,6,1,15,7,2 s.t. 26 zx x xxx x 5 (11) 12 34 123456 12 34 57 1234567 min1,5,1,1 2,6,1,15,7,2,26,8,1,10,2,1,1 s.t. 2654,8,2,2 2 21,5,1,2 ,,,,,,0 zx xx x xxxxxx xx xx xx xxxxxxx 5 x (12)
A. EBRAHIMNEJAD 682 The dual problem is given by the following: 1 w (13) Now we solve the FLP problem (13) by the fuzzy primaldual simplex algorithm. Initialization step: The initial fuzzy dual solution is given by 12 12 12 12 12 1 2 12 max4,8,2,2 1,5,1,1 s.t. 21,5,1,1 2,6,2,2 66,8,1, 5 20,2,1,1 0 0 , unrestricted. ww ww ww ww ww w w ww 12 25 ,7,2,2ww 12 =, =0,0www . First iteration: Substituting 12 =, =0,0www in each dual constraint, we find that the last two dual constraints hold at equality. Thus, =6,7. The rest pri es as follows: ricted fuzzy mal problem becom 9 8 68 79 6789 min1,1,0,01,1,0 s.t. 4,8,2,2 1,5,1, ,,, 0 ,0 1 x xx xx xxxx (14) where 8 and 9 are the artificial fuzzy variables. Solving this problem by Ganesan’s met optimal fuzzy solution and the optima value as follows: hod [7] gives the l objective fuzzy 678 0 8 0,4,8,2,2 , 1,5,1,1 ,5,12,3,3 . xxx xx 0, So, we have , and . Thus, Complementary slackness gives the dual solution as ˆˆˆ =,=1,1 11 ,0,0, 1,1,0,0vvv . 1 ˆ3,3,0,0 0va , 2 ˆ0va , 3 ˆ va 3,3,0 00 , 4 ˆ7,7,0,00va 5 ˆ5, 5,0,00va is determined as follows: 51 7568 , =1, =m in , 3 33 77 and we replace 3 w by 0,0,0,0,0,0,0,011,1,0,0, 1,1,0,0 =1,1,0,0, 1,1,0,0 . mputing of with new dual ves Second iteration: Reco solution , gi 1,1,0,0, 1,1,0,0w =1,4 problem: 89 14 149 1489 min 1,1,0,01,1,0,0 s.t. 26 1,5,1,1 ,,, 0 xx xx xxx xxxx 8 4,8,2,2 x (15) The optimal fuzzy solution to this problem is given by 128 2,4,1,1, 0xxx 9 x with 00x . Thus, we have an optim solution to the main probsllows: al as folem 1 234567 2,4,1,1, 0.xxxxxxx Remark 4.1. If we want to solve the problem (11) directly by use of Algorithm 3.1 proposed by and Veeramani [1], we must first solve the linear programming problem with introducing the slack variables Ganesan following and the fal ollowing new restricted fuzzy prim 6 and 7 and the fuzzy artificial fuzzy variables 8 and 9 , which minimize the sum of the artificial fu vales to obtain a initial fuzzy basic feasible solution: zzy riab 89 min1,1,0,0 1,1,0,0 s.t. 26 zx x xxx x 1234568 12 34 579 5 4,8,2,2 221,5,1 2 xxx xx xx xxx 123456789 ,,,,,,,,0xxxxxxxxx , n t ly at hand. 5. Conclusions Ganesan and Veeramani in [1] propo sed a new approach based on primal simplex algorithm to obtain the fuzzy solution of fuzzy linear programming problem sy ased on the interesting been established by Ganesan and ch can be expected to be (16) After finding a initial fuzzy basic feasible solution by solving the problem (16), we must minimize the origin al objective fuction ofhe problem (11). So, this process is time consuming and has no efficiency computationally for solving such problems in which an initial fuzzy basic solution is not easi with mmetric trapezoidal fuzzy numbers without converting them to crisp linear programming problems. In this paper, we reviewed the dual of a linear programming problem with symmetric trapezoidal fuzzy numbers. Then, we introduced a fuzzy primaldual algorithm for solving the FLP problems directly without converting them to crisp near programming problems, bli results which have eeramani [1]. This approaV efficient if an initial du al fuzzy solu tion can be co mputed readily. This algorithm is also useful specially for solving minimum cost flow problem with fuzzy para meters in which finding an initial dual feasible solution turns out to be a trivial task. However, development of Copyright © 2011 SciRes. AM
A. EBRAHIMNEJAD683 and P. Veeramani, “Fuzzy Linear Program uzzy Numbers,” Annals of Op 43, No. 1, 2006, pp. 305315. network primaldual simplex algorithm for solving such problem in fuzzy environment may also produce inter secting results. 6. Acknowledgments The author would like to thank Prof. Tian Huang, Editorial Assistant in AM Editorial Board, and anony mous referees for the various suggestions which have led to an improvement in both the quality and clarity of the paper. Finally, the author greatly appreciates to the office of vice chancellor for research of Islamic Azad Uni versityQaemshahr Branch. 7. References ] K. Ganesan[1  ming with Trapezoidal F erations Research, Vol. 1 doi:10.1007/s1047900673901 [2] A. Ebrahimnejad and S. H. Nasseri, “Linear Programs with Trapezoidal Fuzzy Numbers: A Duality Approach,” International Journal of Operations Research, in Press. [3] H. Tanaka and K. Asai, “Fuzzy Linear Programming Problems with Fuzzy Numbers,” Fuzzy Sets and Systems, Vol. 13, No. 1, 1984, pp. 110. doi:10.1016/01650114(84)900228 y, “A Dual Approach to Solve the F ming Problems,” Fuzzy Sets and Systems, Vol. 14, No. 2, 1984, pp. 131141. [4] J. L. Verdega Linear Programuzzy doi:10.1016/01650114(84)900964 [5] H. J. Zimmermann, “Optimization in Fuzzy Environ ment,” Presented at XXI International TIMES and 46 ORSA Conference, San Juan, 811th July 1974. [6] A. Ebrahimnejad, S. H. Nasseri, F. H. Lotfi and M. Sol tanifar, “A PrimalDual Method for Linear Programming Problems with Fuzzy Variables,” European Journal of Industrial Engineering, Vol. 4, No. 2, 2010, pp. 189209. doi:10.1504/EJIE.2010.031077 [7] A. Ebrahimnejad, S. H. Nasseri and F Linear Programs with Trapezoidal F . H. Lotfi, “Bounded uzzy Numbers,” In ternational Journal of Uncertainty, Fuzziness and Knowl edgeBased Systems, Vol. 18, No. 3, 2010, pp. 269286. doi:10.1142/S0218488510006532 [8] A. Ebrahimnejad and S. H. Nasseri, “A Dual Simplex 2779. Method for Bounded Linear Programmes with Fuzzy Numbers,” International Journal of Mathematics in Op erational Research, Vol. 2, No. 6, 2010, pp. 76 doi:10.1504/IJMOR.2010.035498 [9] F. H. Lotfi, T. Allahviranloo, M. A. Jondabeh and L. Alizadeh, “Solving a Full Fuzzy Linear Programming Using Lexicography Method and Fuzzy Approximate Solution,” Applied Mathematical Modelling, Vol. 33, No. 7, 2009, pp. 31513156. doi:10.1016/j.apm.2008.10.020 [10] M. Inuiguchi and M. Sakawa, “Possible and Necessary Optimality Tests in Possibilistic Linear Programming Problems,” Fuzzy Sets and Systems, Vol. 67, No. 1, 1994, pp. 2946. doi:10.1016/01650114(94)902062 [11] A. Kumar, J. Kaur and P. Singh, “A New Method for Solving Fully Fuzzy Linear Programming Problems,” Applied Mathematical Modelling, Vol. 35, No. 2, 2011, pp. 817823. doi:10.1016/j.apm.2010.07.037 [12] J. L. Verdegay, “A Dual Approach to Solve the Fuzzy Linear Programming Problems,” Fuzzy Sets and Systems, Vol. 14, No. 2, 1984, pp. 131141. doi:10.1016/01650114(84)900964 [13] H. R. Maleki, M. Tata and M. Mashinchi, “Linear Pro gramming with Fuzzy Variables,” Fuzzy Sets and Systems, Vol. 109, No. 1, 2000, pp. 2133. doi:10.1016/S01650114(98)000669 [14] A. Ebrahimnejad, S. H. Nasseri and S. M. Mansourzadeh, “Bounded Primal Simplex Algorithm for Bounded Linear Programming with Fuzzy Cost Coefficients,” Interna tional Journal of Operational Research and Information Systems, Vol. 2, No. 1, 2011, pp. 96120. doi:10.4018/IJORIS.2011010105 [15] N. MahdaviAmiri and S. H. Nasseri, “Duality in Fuzzy Number Linear Programming by Use of a Certain Linear Ranking Function,” Applied Mathe tion, Vol. 180, No. 1, 2006, pp. 2062 matics and Computa 16. doi:10.1016/j.amc.2005.11.161 [16] S. H. Nasseri and A. Ebrahimnejad, “A Fuzzy Dual Sim plex Method for Fuzzy Number Problem,” Advances in Fuzzy Sets an Linear Programming d Systems, Vol. 5, No. 2, 2010, pp. 8195. [17] A. Ebrahimnejad, “Sensitivity Analysis on Fuzzy Num ber Linear Programming Problems,” Mathematical and Computer Modelling, Vol. 53, No. 910, 2011, pp. 1878 1888. doi:10.1016/j.mcm.2011.01.013 [18] N. MahdaviAmiri and S. H. Nasseri, “Duality Results and a Dual Simplex Method for Linear Programming Problems with Trapezoidal Fuzzy Variables,” Fuzzy Sets and Systems, Vol. 158, No. 17, 2007, pp. 19611978. doi:10.1016/j.fss.2007.05.005 [19] N. MahdaviAmiri, S. H. Nasseri and A. Yazdani, “Fuzzy brahimnejad, “A Fuzzy Primal Primal Simplex Algorithms for Solving Fuzzy Linear Programming Problems,” Iranian Journal of Operational Research, Vol. 1, No. 2, 2009, pp. 6884. [20] S. H. Nasseri and A. E Simplex Algorithm and Its Application for Solving Flexi ble Linear Programming Problems,” European Journal of Industrial Engineering, Vol. 4, No. 3, 2010, pp. 372389. doi:10.1504/EJIE.2010.033336 [21] A. Ebrahimnejad and S. H. Nasseri, “Using Complemen tary Slackness Property to Solve Linear Programming with Fuzzy Parameters,” Fuzzy Information and Engi neering, Vol. 1, No. 3, 2009, pp. 233245. doi:10.1007/s1254300900269 [22] S. H. Nasseri and N. MahdaviAmiri, “Some Duality Results on Linear Programming Problems with Symmet ric Fuzzy Numbers,” Fuzzy Information and Engineering, Vol. 1, No. 1, 2009, pp. 5966. doi:10.1007/s1254300900042 Copyright © 2011 SciRes. AM
A. EBRAHIMNEJAD Copyright © 2011 SciRes. AM 684 82. 1X [23] S. H. Nasseri, A. Ebrahimnejad and S. Mizuno, “Duality in Fuzzy Linear Programming with Symmetric Trapezoi dal Numbers,” Applications and Applied Mathematics, Vol. 5, No. 10, 2010, pp.146714 [24] A. Zadeh, “Fuzzy Sets,” Information and Control, Vol. 8, No. 3, 1965, pp. 338353. doi:10.1016/S00199958(65)9024
