Fuzzy Sets and Systems 157 (2006) 1328 – 1332

[Link]/locate/fss

Computing efficient solutions to fuzzy multiple objective linear

programming problems
Xue-quan Li∗ , Bo Zhang, Hui Li
School of Mathematical Science and Computing Technology, Central South University, Changsha, China, 410083

Received 1 November 2003; received in revised form 2 November 2005; accepted 2 December 2005
Available online 20 December 2005

Abstract
In this paper, we improve the fuzzy compromise approach of Guu and Wu by automatically computing proper membership
thresholds instead of choosing them. Indeed, in practice, choosing membership thresholds arbitrarily may result in an infeasible
optimization problem. Although we can adjust minimum satisfaction degree to get fuzzy efficient solution, it sometimes makes the
process of interaction more complicated. In order to overcome this drawback, a theoretically and practically more efficient two-phase
max–min fuzzy compromise approach is proposed in this paper. Moreover, the efficiency of the two-phase approach is verified by
an example.
© 2005 Elsevier B.V. All rights reserved.

Keywords: Fuzzy multiple objective linear programming; Max–min operator approach; Fuzzy compromise approach; Two-phase approach

1. Introduction

Multiple Objective Linear Programming (MOLP) problems can be formulated as:

max Z = [c1 x, . . . , cN x]T = [Z1 (x), . . . , ZN (x)]T

(1)
s.t. x ∈ X, X = {x ∈ R n : Ax
b, x 0}

where A = (aij )m×n , ci ∈ R n (0
i
N ), b ∈ R m . In problem (1), all objective functions can hardly reach
their optima at the same time subject to the given constraints. Therefore, in practice the decision-maker chooses some
efficient solutions as final decision according to the satisfaction degree (or preference) of each objective value. The fuzzy
approach for solving MOLP proposed by Zimmermann [10] has given an effective way of measuring the satisfaction
degree of MOLP.

Definition 1.1. The vector, whose components are composed by maximum value of each objective function under the
given constraints, i.e.

Z ∗ = [Z1∗ , . . . , ZN
∗
] = [max(Z1 (x)), . . . , max(ZN (x))] (2)

∗ Corresponding author. Tel./fax: +8607318716560.

E-mail address: lixuequan2@[Link] (X.-q. Li).

0165-0114/$ - see front matter © 2005 Elsevier B.V. All rights reserved.
doi:10.1016/[Link].2005.12.003
 X.-q. Li et al. / Fuzzy Sets and Systems 157 (2006) 1328 – 1332 1329

is called the ideal solution [1]. Similarly, the negative ideal solution is defined by
Z − = [Z1− , . . . , ZN
−
] = [min(Z1 (x)), . . . , min(ZN (X))]. (3)

Let the initial solution of objective vector given by decision-maker be

O = [O1 , . . . , ON ]. (4)
To make a proper decision on the choice of initial solution, a decision-maker can use the negative ideal solution as
a reference point, namely, chooses the initial solution not less than negative ideal solution. Furthermore, membership
function [5] of each objective function value’s satisfaction degrees can be defined as the following:
⎧
⎪
⎪ 1, Zk (x) > Zk∗ ,
⎨ ∗
Z − Zk (x)
uk (x) = 1 − k ∗ Ok < Zk (x)
Zk∗ , k = 1, . . . , N. (5)
⎪
⎪ Zk − O k
⎩
0, Zk (x)
Ok ,
If the initial solution is chosen to be negative ideal solution, then membership function of each objective value’s
satisfaction degrees is given by
⎧
⎪
⎪ 1, Zk (x) > Zk∗ ,
⎨ Z ∗ − Zk (x)
u−k (x) = ⎪
1− k∗ , Zk− < Zk (x)
Zk∗ , k = 1, . . . , N. (6)
⎪ Zk − Zk−
⎩
0, Zk (x)
Zk− ,
To solve problem (1), following the concept of membership function, Zimmermann proposed max–min operator
approach [9]:
max

s.t.

uk (x), k = 1, . . . , N, (7)

∈ [0, 1], x ∈ X.
It has been proved that max–min operator approach possesses some good properties. However, the efficiency of the
solution yielded by max–min operator is not guaranteed. In order to overcome inefficiency, in this paper, the compromise
approach and two-phase approach are proposed (see [4,7,2]).

2. Fuzzy compromise method for MOLP

Based on the above analysis, problem (1) can be transformed into the following linear programming problem (fuzzy
compromise approach [8]):

N
max
=  k
k
k=1
s.t.
lk

k
uk (x), k = 1, . . . , N, (8)

N
x ∈ X, k = 1, k > 0,
k=1

where
lk (0

lk
1) is the minimum satisfaction degree of the kth objective function chosen by decision-maker. To
increase the minimum satisfaction degree of one objective function means that the value of this objective function is
closer to the optimal value; on the other hand, it may make other objective function values far from their optimal values.
As a result, when the minimum satisfaction degree chosen by decision-maker is too great, (8) may have no solution.
So, to ensure the existence of a feasible solution,
lk needs to be adjusted properly.

Definition 2.1. x ∗ is a fuzzy-efficient solution to (8) if there does not exist any x ∈ X such that uk (x ∗ )
uk (x) for all
k (k = 1, . . . , N ) and us (x ∗ ) < uk (x) for at least one s.
1330 X.-q. Li et al. / Fuzzy Sets and Systems 157 (2006) 1328 – 1332

Theorem 2.1 (Sakawa [5]). The optimal solution x ∗ of (8) is a fuzzy efficient solution.

3. The two-phase approach for MOLP

The optimal solution obtained by max–min operator approach may not be efficient solution, on the other hand, if

lk in compromise approach (8) is improperly given, it will make the process of interaction more complicated. So
some improvements are needed. In fact, if we take the minimum satisfaction degree in compromise approach (8) equal
to the solution of the max–min operator approach, then the calculation amounts of compromise approach (8) will be
decreased. Moreover, the disadvantage of max–min operator (7) can be overcome. Consequently, a two-phase approach
for solving MOLP is put forward, whose steps are as follows:
(1) Take the negative ideal solution as the initial solution of max–min operator (7), i.e. O = Z − , solve model (7) to
get an optimal solution x 0 , then calculate the relative membership uk (x 0 ) (1
k
N ) of each objective value’s
satisfaction degrees.
(2) Set
lk = uk (x 0 ), solve model (8) to get an optimal solution x ∗ of two-phase approach for solving MOLP. Namely,
solve the following model to get x ∗ :


N
max
= k
k
k=1
s.t. uk (x 0 )

k
uk (x), k = 1, . . . , N, (9)
N
x ∈ X, k = 1, k > 0.
k=1

(3) Substitute x ∗ in the objective function in model (1).

Theorem 3.1. A solution to the fuzzy MOLP (9) exists, and is an efficient solution to problem (1).

Proof. First, it is obvious that x 0 , which is an optimal solution of model (7), is a feasible solution of (9), namely the
solution set of (9) is not empty. So (9) must have an optimal solution.
Second, suppose that x ∗ is an optimal solution of (9) and it is not an efficient solution for problem (1), then (1)
must have an efficient solution x ∗∗ , i.e. ∃i ∈ [1, N], Zi (x ∗∗ ) > Zi (x ∗ ), then ∀k, uk (x 0 )

∗k
uk (x ∗ )
uk (x ∗∗ ), and
∃i ∈ [1, N], ui (x 0 )

∗k
ui (x ∗ ) < ui (x ∗∗ ). The objective value
  
k
∗k = k
∗k + i
∗i < k
∗k + i
∗∗
i .
k k,k=i k,k=i

Thus, x ∗ is not the optimal solution of (9), a contradiction. 

4. Numerical example

To check the efficiency of the two-phase approach proposed in this paper, we consider the same example as given
by Lee [3]:

max Z1 = 2x1 + 5x2 + 7x3 + x4 ,

max Z2 = 4x1 + x2 + 3x3 + 11x4 ,
max Z3 = 9x1 + 3x2 + x3 + 2x4 ,
min W1 = 1.5x1 + 2x2 + 0.3x3 + 3x4 ,
min W2 = 0.5x1 + x2 + 0.7x3 + 2x4 ,
s.t. 3x1 + 4.5x2 + 1.5x3 + 7.5x4 = 150,
x1 , x2 , x3 , x4 0.
 X.-q. Li et al. / Fuzzy Sets and Systems 157 (2006) 1328 – 1332 1331

Transfer the multiple objective linear programming problem into the standard form:
max Z1 = 2x1 + 5x2 + 7x3 + x4 ,
max Z2 = 4x1 + x2 + 3x3 + 11x4 ,
max Z3 = 9x1 + 3x2 + x3 + 2x4 ,
max Z4 = −1.5x1 − 2x2 − 0.3x3 − 3x4 ,
max Z5 = −0.5x1 − x2 − 0.7x3 − 2x4 ,
s.t. 3x1 + 4.5x2 + 1.5x3 + 7.5x4 = 150,
x1 , x2 , x3 , x4 0.
The ideal solution Z ∗ = (700, 300, 450, −30, −25) and the negative ideal solution Z − = (20, 33.33, 40, −75, −70).
The programming corresponding to (7) is
max

s.t.

(1/680)(2x1 + 5x2 + 7x3 + x4 − 20),


(1/266.67)(4x1 + x2 + 3x3 + 11x4 − 33.33),


(1/410)(9x1 + 3x2 + x3 + 2x4 − 40),


(1/45)(75 − 1.5x1 − 2x2 − 0.3x3 − 3x4 ),


(1/45)(70 − 0.5x1 − x2 − 0.7x3 − 2x4 ),
3x1 + 4.5x2 + 1.5x3 + 7.5x4 = 150,

∈ [0, 1], x1 , x2 , x3 , x4 0.

Then we get an optimal solution
opt = 0.5, optimal objective function value vector Z 0 = (371.36, 248.64, 245, −52.5,
−48.9), x 0 = (21.59, 0, 46.59, 2.05), the membership function value of objective value’s satisfaction degree is u(x 0 ) =
(0.52, 0.81, 0.5, 0.5, 0.47).
The programming corresponding to (9) is
max 0.2
1 + 0.2
2 + 0.2
3 + 0.2
4 + 0.2
5 ,
s.t. 0.55

1
(1/680)(2x1 + 5x2 + 7x3 + x4 − 20),
0.74

2
(1/266.67)(4x1 + x2 + 3x3 + 11x4 − 33.33),
0.5

3
(1/410)(9x1 + 3x2 + x3 + 2x4 − 40),
0.5

4
(1/45)(75 − 1.5x1 − 2x2 − 0.3x3 − 3x4 ),
0.5

5
(1/45)(70 − 0.5x1 − x2 − 0.7x3 − 2x4 ),
3x1 + 4.5x2 + 1.5x3 + 7.5x4 = 150,
x1 , x2 , x3 , x4 0.
Then, we get an optimal solution uopt = (
1 ,
2 ,
3 ,
4 ,
5 ) = (0.56, 0.81, 0.54, 0.5, 0.5), x ∗ = (25, 0, 50, 0), an
optimal objective function value vector Z 1 = (400, 250, 275, −52.5, −47.5), thus Z 1 Z 0 , so the optimal solution
x 0 of max–min operator approach is not efficient. Obviously, the result of two-phase approach is better than that of
max–min operator approach.
Note that in Table 1, in fuzzy compromise method, if we take
lk = 0 (k = 1, . . . , N ) (i.e. average operator
method for multiple objective linear programming problems, see [1]), then we get the results
opt = (1, 1, 0.15, 1, 0),

Table 1
The results of different approaches
 

5
Approach k=1
k /5 x Z

1 0.5 — (20.71, 3.51, 48.05, 0) (395.32, 230.52, 245, −52.5, −47.5)

2 — 0.629 (0, 0, 100, 0) (700, 300, 100, −30.00, −70.00)
3 — 0.589 (25.00 0.00 50.00 0.00) (400.00 250.00 275.00 − 52.50 − 47.50)

1—Max–min operator, 2—Average operator, 3—Two-phase.

1332 X.-q. Li et al. / Fuzzy Sets and Systems 157 (2006) 1328 – 1332


Z = (700, 300, 100, −30.00, −70.00). The sum 5k=1
k of membership values of average operator approach is
greater than that of the two-phase approach. This is because when Z1 , Z2 and Z4 reach their ideal values, it is at the
cost of driving the values of Z3 and Z5 close to the negative ideal solution. When the two-phase method is compared
to max–min operator method, it is obvious that the latter method did not get an effective solution.

5. Conclusion

The proposed approach can get an efficient solution to the MOLP problem, also avoiding the potential infeasibility
in the fuzzy compromise approach of Guu and Wu. The proposed example demonstrates the actual improvement made
by our two-phase approach.

References

[1] H.-K. Chen, H.-W. Chou, Solving multiobjective linear programming problems—a generic approach, Fuzzy Sets and Systems 82 (1996)
35–38.
[2] S.-m. Guu, Y.-k. Wu, Two-phase approach for solving the fuzzy linear programming problems, Fuzzy Sets and Systems 107 (1999) 191–195.
[3] R.-j. Li, E.S. Lee, Fuzzy approaches to multicriteria de novo programs, J. Math. Anal. Appl. 153 (1990) 97–111.
[4] M.K. Luhandjula, Multiple objective programming problems with possibilistic coefficients, Fuzzy Sets and Systems 21 (1987) 135–145.
[5] O.M. Saad, Stability on multiobjective linear programming problems with fuzzy parameters, Fuzzy Sets and Systems 74 (1995) 207–215.
[6] M. Sakawa, Fuzzy Sets and Interactive Multiobjective Optimization, Plenum Press, New York, 1993.
[7] R. Slowinski, A muliticriteria fuzzy linear programming method for water supply system development planning, Fuzzy Sets and Systems 19
(1986) 217–237.
[8] Y.-k. Wu, S.-m. Guu, A compromise model for solving fuzzy multiple objective linear programming problems, J. Chinese Inst. Ind. Eng. 18 (5)
(2001) 87–93.
[9] H.J. Zimmermann, Fuzzy programming and linear programming with several objective functions, Fuzzy Sets and Systems 1 (1978) 45–55.
[10] H.J. Zimmermann, Fuzzy Set Theory and Its Applications, Kluwer Academic Publishers, Hingham, 1985.