Applied Mathematics, 2011, 2, 676-684
doi:10.4236/am.2011.26089 Published Online June 2011 (http://www.SciRP.org/journal/am)
A Primal-Dual 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
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 primal-dual simplex algorithm to overcome mentioned shortcomings.
A numerical example is given to illustrate the proposed approach.
Keywords: Fuzzy Linear Programming, Fuzzy Arithmetic, Fuzzy Orders, Primal-Dual 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 [6-12]. 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, Mahdavi-Amiri and Nasseri [18] and
Mahdavi-Amiri 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 primal-dual 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 primal-dual 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 primal-dual 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 primal-dual 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
L
a and ,
U
a
L
U
aa and >0

,
such that

,,
1, ,
=
, ,
0, otherwise.
LLL
LU
UUU
xa
x
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

F
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
L
ULU
aa bb
(in this case, we my write
2) o
a
ab

),
r =, <
22
LU LU
L
L
aa bbba  and
3) or
<
UU
ab,
=, =,=
22
LU LU
L
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
L
ULU
aa bb
.
nly if
Definition 2.3. For any trapezoidal fuzzy number a
,

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
x

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
x
 is not equivalent to 0
), then
it is said to be a non-zero 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 Mahdavi-Amiri [22] and Nasseri et al. [23 ] .
3.1. A Fuzzy Primal Simplex Algorithm
efinition 3.1. A linear programming problem with tra-D
p
min zcx
..
0
s
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

x
satisfies the
constraf the pro-
blem ints and non-negativity restrictions o .
Definition 3.3. A fuzzy feasible solution *
x
 is said to
be a fuzzy optimal solution to (1), if for all fuzzy feasible
solution
x
 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
s
.t.Ax b
x




(2)



where the parameters of the problem are as defined in (1).
Let =ijmn
Aa






=Am . Partition
A
. Assume rank


BN where , is nonsingular. It is , Bmm as
obvious that


=rankBm. Let
j
y be the solution to
=
j
Bya . It is apparent that the basic solution


1
,T
B
m
xx


1
=,, 0
BB N
x Bbx

 (3)
is a solution of =
A
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
B
x
, where zc 


1
=,,
B
m
c


BB
cc
 . Now, corresponding to every n
1,, ,on-
basic variable ,1,, =
ji
x
jnjBi m


1.
 define
j
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
x
, 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
x
, 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
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,

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
j
zc  for all nonbasic variables. Sup-
pose

=,,,

LU
j
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
y
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
x
 enters the
basis and
B
r
x
 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 Mahdavi-Amiri [22] and
Nasseri et al. [23]).
Theore 0
x
 and
0 are fuzzy feasible solutions to FLP and DFLP
problems, respectively, then 00 cxw b

  .
Corollary 3.1. If 0
w

x
 and 0
w
 are fuzzy feasible so-
Table 1. The initial primal simplex tableau.
Basis
B
x
 N
x
 ...
R
HS
z
 0
 NNBNN
zccYc

 =1 =B zcBb


B
x
 I N
Y 1 =bBb
 
to FLP and DFLP problems, respectivel
00
cxw b
 0
x

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 *
x

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
*
x
 and * w  are feasible solutions of the FLP problem
and its corresponding dual, the DFLP problem, respec-
tively. Then *
x
 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
j
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
x
enters the
B
r
x
basis and leaves the basis, and go t
4. A Fuzzy Primal-Dual 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

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 Mahdavi-Amiri [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 primal-dual 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
A
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
x
. In this process, once an artificial variable
j
a
x
 drut of the basic variables, discard it from the
. Let
ops o
problem ˆ
x
 and 0
x

alue be the imal solution and fuzzy obje vobtained at termination in this
re
fuzzy pr
ectiv
stricted fuzzy primal problem, respectively. If 00x


,
ˆ
x
 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
x
 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




ˆˆ ˆˆ
j
jjjjjj
wacwvacwac va  
 

 (10)
Now, if ˆ
j
x
 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
cwa
 j

with at least
one compone equal ty zero.
First, we show in this case for each j there is an
nto fuzz
j

such that


ˆˆ 0
jjjjj j
wa c

va

 wa c




. Let
 



12 1
=,,,, 2
j
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
ˆˆˆ
=
j
jjjj j
wvwv




if and only if


121 2
ˆˆˆˆ
=

j
jjj j
vv ww 
if and only if

A. EBRAHIMNEJAD 681
12
12
ˆˆ
=.
ˆˆ
j
j
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
j

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
j

  for all j.
Thus
So, we have

12 12
ˆˆ ˆˆ .
jj jjj
vv vv  
 
1212 12
ˆˆˆˆ ˆˆˆˆ
.

12
j
jjjj jjj
wwvv wwvv  
or
j

 

 

112 2
112 2
1ˆˆˆˆ
2
ˆˆˆˆ
jjjj
jjj jjj
wvwv
wvwv




that is

1
2




ˆˆˆ

ˆ
j
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
x
 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
x
, which leads to a potential reduction in 0
x
. 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
x
 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 fuzzprimal-dual 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 primal-dual 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
x
and
7
x
, 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
primal-dual 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
x
xx
xx
xxxx









(14)

where 8
x
 and 9
x
 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
x
and 7
x
and the fuzzy artificial fuzzy
variables 8
x
and 9
x
, 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 primal-dual 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

A. EBRAHIMNEJAD683
and P. Veeramani, “Fuzzy Linear Program
uzzy Numbers,” Annals of Op-
43, No. 1, 2006, pp. 305-315.
network primal-dual 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-
versity-Qaemshahr Branch.
7. References
] K. Ganesan[1 -
ming with Trapezoidal F
erations Research, Vol. 1
doi:10.1007/s10479-006-7390-1
[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. 1-10.
doi:10.1016/0165-0114(84)90022-8
y, “A Dual Approach to Solve the F
ming Problems,” Fuzzy Sets and Systems,
Vol. 14, No. 2, 1984, pp. 131-141.
[4] J. L. Verdega
Linear Programuzzy
doi:10.1016/0165-0114(84)90096-4
[5] H. J. Zimmermann, “Optimization in Fuzzy Environ-
ment,” Presented at XXI International TIMES and 46
ORSA Conference, San Juan, 8-11th July 1974.
[6] A. Ebrahimnejad, S. H. Nasseri, F. H. Lotfi and M. Sol-
tanifar, “A Primal-Dual Method for Linear Programming
Problems with Fuzzy Variables,” European Journal of
Industrial Engineering, Vol. 4, No. 2, 2010, pp. 189-209.
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-
edge-Based Systems, Vol. 18, No. 3, 2010, pp. 269-286.
doi:10.1142/S0218488510006532
[8] A. Ebrahimnejad and S. H. Nasseri, “A Dual Simplex
2-779.
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. 3151-3156. 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. 29-46. doi:10.1016/0165-0114(94)90206-2
[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. 817-823. 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. 131-141.
doi:10.1016/0165-0114(84)90096-4
[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. 21-33.
doi:10.1016/S0165-0114(98)00066-9
[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. 96-120.
doi:10.4018/IJORIS.2011010105
[15] N. Mahdavi-Amiri 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. 206-2
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. 81-95.
[17] A. Ebrahimnejad, “Sensitivity Analysis on Fuzzy Num-
ber Linear Programming Problems,” Mathematical and
Computer Modelling, Vol. 53, No. 9-10, 2011, pp. 1878-
1888. doi:10.1016/j.mcm.2011.01.013
[18] N. Mahdavi-Amiri 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. 1961-1978.
doi:10.1016/j.fss.2007.05.005
[19] N. Mahdavi-Amiri, 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. 68-84.
[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. 372-389.
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. 233-245.
doi:10.1007/s12543-009-0026-9
[22] S. H. Nasseri and N. Mahdavi-Amiri, “Some Duality
Results on Linear Programming Problems with Symmet-
ric Fuzzy Numbers,” Fuzzy Information and Engineering,
Vol. 1, No. 1, 2009, pp. 59-66.
doi:10.1007/s12543-009-0004-2

A. EBRAHIMNEJAD 684
82. 1-X
[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.1467-14
[24] A. Zadeh, “Fuzzy Sets,” Information and Control, Vol. 8,
No. 3, 1965, pp. 338-353.
doi:10.1016/S0019-9958(65)9024