International Mathematical Forum, 3, 2008, no.

3, 99 - 106

Solving Interval and Fuzzy Multi Objective Linear Programming Problem by Necessarily Efficiency Points
Hassan Mishmast Nehi and Marzieh Alineghad Mathematics Department, Faculty of Science University of Sistan and Baluchestan, Zahedan, Iran hmnehi@hamoon.usb.ac.ir Abstract In this paper we focus on a kind of linear programming with fuzzy numbers and multiple objectives. First by using -cuts and fuzzy ranking ,we transform these problems to multi objective problem with fuzzy coefficients and crisp constraint then define necessarily efficiency points for new problem and for solving the problem try to find all of these necessarily efficiency points . Keywords: multi objective fuzzy programming, necessarily efficiency points, interval programming, Fuzzy ranking.

1. Introduction
In conventional mathematical programming, coefficients of problems are usually crisp values and determined by the experts. But in real world, it is an uncertain assumption that the knowledge and representation of an expert are so precise. Hence in order to develop good operation research methodology fuzzy, interval and stochastic approaches are frequently used to describe and treat imprecise and uncertain elements present in a real decision problem. In fuzzy programming problems the constraints and goals are viewed as fuzzy sets and assumed that their membership functions are known. But, in reality, to a decision maker (DM) it is not always easy to specify the membership function. At least in some of the cases, use an interval coefficients may serve the purpose better. Though by using - cuts, fuzzy numbers can be transformed into interval numbers. Moreover, most real word problems are inherently characterized by multiple, conflicting and incommensurate aspects of evaluation .these axes of evaluation are generally operationalized by objective functions to be optimized in framework of multiple objective linear programming models.

100

H. M. Nehi and M. Alineghad

In this paper, we focus on multi objective linear programming with fuzzy coefficient. By introducing -cuts and Ramik and Raminek ranking , we transforme the problem to a multiobjective linear programming with interval objective functions and crisp constraints then define necessarily efficient points and find these points for new problems with proposed algorithms.

2. Multiobjective linear programming with fuzzy coefficients

The multi objective linear programming with fuzzy coefficients can be formulated as follow:

max imaize
s .t

~ c
j =1

kj

xj

k = 1,L , p

~ a x
ij

~ bi

i = 1,L , m

(1)

xj 0

~ ~ where ~kj , aij and bi are fuzzy numbers. c

To find the necessarily efficiency points for problem (1), we transform it to a problem with interval objective function and crisp constraints. So we use -cuts to transforme coefficients of objective function to interval, as indicated follow, and Ramik and Raminek ranking to obtain crisp constraints from our fuzzy constraints.
2.1. Some definitions ~ ~ The -level set ( -cut) of a fuzzy set M is defined as an ordinary set M for which the degree of its membership function exceeds the level : ~ ~ M = { x | M }, [ 0 ,1 ] .

Observe that the -level set M can be defined by the characteristic function 1 M ( x ) ~ CM = 0 M ( x ) < Actually, an -level set is an ordinary set whose elements belong to the corresponding fuzzy set to a certain degree . A fuzzy number is a convex normalized fuzzy set of the real line R whose membership function is piecewise continuous. ~ From the definition of a fuzzy number M , it is significant to note that the -level ~ ~ set M of a fuzzy number M can be represented by the closed interval which depends on interval value of . Namely, ~ L U ~ M = { x | M }= [ M , M ]
L U Where M or M represents the left or right extreme point of the -level set M , respectively.

Linear programming problem

101

~ Especially if M = (m, , ) is a triangular fuzzy number then ~ ~ M = [ ( 1 ) + m , m ( 1 )] and if M = (m L , m R , , ) is a trapezoidal ~ fuzzy number then M = [ ( 1 ) + m L , m R ( 1 )] .
2.2. Ranking fuzzy numbers Dubios and prade proposed a method of ranking fuzzy numbers as follow: ~ ~ Definition let M and N be fuzzy numbers, then we have ~ ~ ~ ~ ~ MN M N =M By usind the definition Ramik and raminek suggested the following lemma: ~ ~ ~ ~ ~ Lemma if M and N be a fuzzy numbers, M N = M if and only if for every h [ 0 ,1 ] we have ~ ~ inf { s : M ( s ) h } inf { t : N ( t ) h }
~ ~ sup { s : M ( s ) h } sup { t : N ( t ) h } ~ ~ Especially if M = ( m L , m R , , )LR and N = (n L , n R , , ) LR be two trapezoidal fuzzy numbers, the above relation is true if and only if m L L* ( h ) L n L L * ( h ) L h [ 0 ,1 ]

m R + R* ( h ) R

n R + R * ( h ) R

h [ 0 ,1 ]

where
L* ( h ) = sup{ z : L( z ) h } L * ( h ) = sup{ z : L ( z ) h } R* ( h ) = sup{ z : T ( z ) h } R * ( h ) = sup{ z : R ( z ) h } .

~ ~ From the definition of Ramik and Raminek, if M = ( m , , )LR and N = (n, , ) LR , be triangular fuzzy numbers, then we have mn ~ ~ M N m n m + n + ~ ~ L R If M = ( m , m , , )LR and N = ( n L , n R , , )LR be two fuzzy numbers, similarly we can compare them as follow mL nL mR nR ~ ~ M N L L m n m R + n R +
By using above definition and with respect to the kind of fuzzy numbers of the problem, we can transform the fuzzy constraints to crisp ones.

102

H. M. Nehi and M. Alineghad

~ ~ In this way, if ~kj = ( c kj , kj , kj ), aij = (aij , ij , ij ) and bi = ( bi , i , i ) be c

triangular fuzzy numbers, problem (1) is equivalent to

max imaize s .t

[ kj ( 1 ) + ckj ,ckj kj ( 1 )]x j

j =1

k = 1,L , p

aij x j bi
j =1 n

i = 1,L , m

( aij ij )x j bi i
j =1

i = 1,L , m

(2)

( aij + ij )x j bi + i
j =1

i = 1,L , m

xj 0.

~ L R L R ~ Similarly if ~kj = ( c kj , c kj , kj , kj ), aij = (aij , aij , ij , ij ) and bi = ( biL ,biR , i , i ) c

be trapezoidal fuzzy numbers then, problem (1) is equivalent to

max imaize s .t
L R [ kj ( 1 ) + ckj ,ckj kj ( 1 )]x j j =1 n

k = 1,L , p

aijL x j biL
j =1 n

i = 1,L , m
i = 1,L , m

aijR x j biR
j =1

(3)

( aijL ij )x j biL i
j =1 n

i = 1,L , m i = 1,L , m

( aijR + ij )x j biR + i
j =1

xj 0.

3. Necessarily efficient points

Consider the following MOLP problem with interval objective functions:
max z( x ) = Cx
s .t

Ax b

(4)

Linear programming problem

103

x0 C . L U Where is a set of p n matrices, with elements C kj [ C kj ,C kj ] for k = 1,L , p ,

j = 1,L , n , A is a m n matrix and b is a m 1 vector. A solution is necessarily efficient to problem (4) if and only if it is efficient for any C . The necessarily efficient solution set ( N E ) is obtained by NE = I X E(C )
Where X E ( C ) is the efficient solution set for each C . Bitran (1980) proposed an implicit enumeration algorithm that uses a subproblem to test efficiency of a given basic solution and a branch and bound algorithm to solve subproblem. But his method may result in a high computational burden if the solution being analyzed is not necessarily efficient. Ida (1999) suggested an extension of the implicit enumeration algorithm.the proposed method uses two efficiency test. One of them checks necessary efficiency and the other checks non-necessary efficiency. Let R
( g ,w1 ,L,wg )
C

= CB

( g ,w1 ,L,wg )

B 1 N C U , where the columns of the interval N

matrix, , C B
C

( g ,w1 ,L,wg )

are defined as
j g, w j = U j g, w j = L g j m.

( g , w1 ,L, wg ) B

U C B. j L = C B. j [C L , C U ] B. j B. j

In this context, g is the tree level, m is the number of basic variables with interval coefficients, w j is L( U ) if the column elements of the matrix within the tree level
L R j are in the lower bounds C B . j (upper bounds C B . j ) of the intervals and j = 1,L , g .
1 g 1 g Let R and R be composed of the lower and upper bounds of ( g ,w ,L,w ) each element belonging to the interval matrix R 1 g , respectively. The operations " sc" is defined as

L( g ,w ,L,w )

U ( g ,w ,L,w )

sc( R

L( g ,w1 ,L,wg )

)={R

L( g +1,w1 ,L,wg ,L )

,R

L( g +1,w1 ,L,wg ,U )

and
sc ( R
U ( g , w1 ,L, wg )

) = {R

U ( g +1, w1 ,L, wg , L )

,R

U ( g +1, w1 ,L, wg ,U )

}.

3.1. Necessary efficiency algorithms The necessary efficiency test is obtained in the following way: Algorithm 1 Step1. Let S L = R L( 0 ) .

Step2. Select one element R

L( g ,w1 ,L,wg )

from S L and check whether it is efficient.

( g ,w1K,wg )

(a) If it is efficient then remove the element from S L .

1 g ) to S L .If ( R (b) Otherwise, add sc( R then R is not necessarily efficient.

L( g ,w ,L,w )

) = ( R ( m ,w1K,wm ) ) ,

104

H. M. Nehi and M. Alineghad

Step3. If the set S L is empty, then R is necessarily efficient. Step4. Return to step 2.

This algorithm is based on the following theorem:

Theorem If all of the elements of S L are efficient, then R is necessarily efficient.(Ida, 1999) If the solution being analyzed is not necessarily efficient, his implicit enumeration algorithm may be out of acceptable computational limits due to the branching required. Therefore, Ida proposed another algorithm in the following way. Algorithm 2 Step1. Let S U = R U ( 0 ) .

1 g from S U and check whether it is efficient. Step2. Select one element R (a) If it is not efficient, then R is not necessarily efficient.

U ( g ,w ,L,w )

(b) Otherwise, add sc( R

U ( g ,w1 ,L,wg )

) to S U .If ( R

( g ,w1K,wg )

) = ( R ( m ,w1K,wm ) ) ,

Do not add any thing to S U . Step3. If the set S U is empty, then R is necessarily efficient. Step4. Return to step 2.

This algorithm is based on the following theorem (Ida, 1999): Theorem If there is an element of S U that it is not efficient, then R is not efficient. The efficiency is based on chernikova's algorithm (chernikova, 1999) and proceeds as follows:
Algorithm 3
Step1. Compute R . Step2. Analyze column and rows of R and proceed as follow:. (a) If there are any columns in R such that R. j 0 , then eliminate these columns. (b) If there are any rows in R such that Ri. 0, then eliminate these rows.. Step3. Analyze columns and rows of R and proceed as follow: (a) If there is a column in R such that R. j 0 , then R is not efficient. (b) If there is arrow in R such that Ri. > 0 , then R is efficient. (c) If there is a row in R such that Ri . 0 ( Rij = 0 ),then R is efficient. Step4. Calculate the summation of the columns( R. ) and rows( R. ) of R . (a) If R.0 , then R is not efficient. (b) If R. > 0 , then R is efficient. Step5. Let D = R and process the rows by using the extreme ray generation method (chernikova,1965). Let. simultaneously, D = R T and process the row in parallel by using extreme ray generation method ( D is defined in chernikova(1965) and Ida (2000b)). Step6. Return to step 2. and a row i i such that Rij > 0

Linear programming problem

105

4. Numerical Example
Consider the following MOLP with fuzzy coefficients: ~ max C x
s .t

~ ~ Ax b x0 where ~ ( 5 ,1 ) ( 10 ,0.7 ) , C= ( 4 ,1 ) ( 2 ,0.4 ) ~ ( 2 ,1 ) b = ( 3.0.5 )

~ A = [( 2 ,0.7 )( 3,0.5 )] ,

Let = 0.7 , Then we have the following interval for objective coefficients. ( 5 ,1 )0.7 = [ 4.7 ,5.3 ] ( 7 ,0.7 )0.7 = [ 6.79 ,7.21 ] ( 2 ,0.4 )0.7 = [ 1.88 ,2.12 ] ( 3,1 )0.7 = [ 2.7 ,3.3 ] If we want to test the necessary efficiency of the extreme point ( we obtain
B
1

10 6 12 ,0, ,0, ) , then 13 13 13

CU N Thus,

0 0.7692 0 = 1 1.5358 0 , 0 2.0769 1 10.21 0 = 4.3 0

3 0 N = 2.5 1 and 3 .5 0

[ 4.7 ,5.3 ] 0 0 1 ( U R ( 0 ) = C B0 ) B 1 N C U = N B N CN [ 1.88 ,2.12 ] 0 0 [ 3.61524 ,4.07676 ] [ 1.1719 ,0.0181 ] = [ 0.68476 ,0.22324 ] [ 1.446096 ,1.630704 ] Hence, 0.0181 4.07676 1.1719. 3.61524 L( 0 ) RU ( 0 ) = = and R . 0.22324 1.630704 0.68476 1.446096 Since R.U (0) 0 , then R is not efficient (there is an element of S U which is not 1 efficient)

106

H. M. Nehi and M. Alineghad

Conclusion
A new solution to a linear multiobjective programming problems with fuzzy coefficients proposed based on the necessary efficiency. The method to find the necessarily efficiency points is indicated. Although we use Ramik and Raminek definition to compare fuzzy numbers, we can uses the others linear ranking methods, like loius and wang index, and compare the results. An example is given to demonstrate the proposed solution.

References
Bitran G.R., linear multiple objective problems with interval coefficients, Management Science 26, pp. 694-706, 1980.
[1]

[2] Chernicova N.V., Algorithm for finding a general formula for nonnegative solutions of a system of linear inequalities, USSR. Computational Mathematics and Mathematical Physics 5, pp 228-233, 1965. [3] Ida M., Necessary efficient test in interval multi objective linear programming, In: proceedings of 8th international fuzzy systems association world congress, pp.500- 504, 2000. [4] Ida M., Efficient solution generation for multiple objective linear programming and uncertain coefficients, In: proceedings of 8th Bellman continuum, pp.132-136, 2000. [5] Ida M., Interval multiobjective programming and mobile robot path planning, In: Mohammadian M. (Eds.), New Frontiers in computational Intelligence and its applications. ISO press, pp 313-322, 2000. [6] Ishibuchi H., Tanaka H., Multiobjective programming in optimization of the interval objective Systems, Prentic Hall,Englewood Cliffs, NJ, 1982. [7] Oliveira C., Antunes C.H., ultiple objective linear programming modeles with interval coefficients an illustrated overview, European journal of operational Research, pp.1-30, 2006. [8] Sakawa M., Fuzzy sets and interactive multiobjective optimization, Plenum press, New York,1993. [9] Steuer P.E., Multiple criteria optimization:theory,computation and application, John wiley & Sons, New york, 1986.
Received: September 12, 2007