Theory and Methodology
On the equivalence of two optimization methods for fuzzy linear programming problems

https://doi.org/10.1016/S0377-2217(99)00011-9Get rights and content

Abstract

The paper analyses the linear programming problem with fuzzy coefficients in the objective function. The set of nondominated (ND) solutions with respect to an assumed fuzzy preference relation, according to Orlovsky's concept, is supposed to be the solution of the problem. Special attention is paid to unfuzzy nondominated (UND) solutions (the solutions which are nondominated to the degree one). The main results of the paper are sufficient conditions on a fuzzy preference relation allowing to reduce the problem of determining UND solutions to that of determining the optimal solutions of a classical linear programming problem. These solutions can thus be determined by means of classical linear programming methods.

Introduction

In the paper the linear programming problem is considered in which the objective function coefficients are given in an imprecise way, by means of fuzzy numbers. The other coefficients are known precisely. In this case, for each feasible solution the corresponding objective function value, constituting an estimate of its utility, is also a fuzzy number. There are many concepts of the solution of this problem (see e.g., Refs. 3, 13). One of them was presented by Orlovsky [12], in which he makes use of the approach to the decision making (the choice of the “best” solution) which he had earlier proposed in Ref. [11] and which bases itself on a fuzzy preference relation defined on the set of feasible solutions. In this paper this concept is assumed to be the valid definition of the solution of the problem. Let a fuzzy preference relation be defined on the set of fuzzy numbers, a relation which determines a fuzzy order on this set. According to Orlovsky's concept, the solution of the problem is a fuzzy set of those feasible solutions which are nondominated with respect to this fuzzy preference relation. The value of the membership function of this set for a given feasible solution determines the degree to which we can be sure that the fuzzy objective function value corresponding to this solution is not dominated by the objective function values corresponding to other feasible solutions of the problem. It can be then recommended to the decision maker to choose as the definitive decision this feasible solution for which the membership function in the set of nondominated (ND) solutions attains a maximal value. From the practical point of view those solutions are interesting, which are nondominated to the degree one – if such solutions exist, of course. The set of the solutions which are nondominated to the degree one has been called by Orlovsky the set of unfuzzy nondominated (UND) solutions.

In the general case the determination of an UND solution with respect to a given fuzzy preference relation can be reduced to the determination, in the set of feasible solutions, of the saddle point of the membership function of a fuzzy relation of strict preference, linked to the original relation. For the problem reduced in this way, the existing algorithms determining the saddle point are very labour-consuming, which sometimes ruins their practical usefulness.

In the paper we give some conditions whose fulfilment makes it possible to reduce a linear programming problem with fuzzy coefficients in the objective function to a classical (usual) linear programming problem. The fuzzy coefficients in the objective function of the original problem are replaced with their real equivalents, being the values of a ranking function, which considerably simplifies the problem and allows to use classical algorithms of linear programming. The optimal solutions of the linear programming problem defined in this way are UND solutions of the original problem. In Ref. [4] we have obtained equally effective ways of determining UND solutions but only for specific six fuzzy preference relations known from the literature. In this paper, however, we answer a more general question: which conditions should be fulfilled by any fuzzy preference relation so that a ranking function exists and the problem of determining UND solutions with respect to this relation can be reduced to that of determining the optimal solutions of a classical linear programming problem? We cover a broader class of fuzzy preference relations. The conditions proved in this paper are a generalization, for the continuous case, of the result obtained by Kołodziejczyk [10] for the case of the discrete linear problem with fuzzy coefficients in the objective function with a finite set of feasible solutions.

Section snippets

Selected notions from the fuzzy numbers arithmetic

We will remind here only those notions linked to the fuzzy numbers arithmetic which we will use further on in the paper.

Definition 1. Fuzzy number A is a fuzzy set defined on the set of real numbers R characterized by means of a membership function μA(x), μA:R→[0,1], which is upper semicontinuous and which fulfils the following conditions:

  • 1.

    normality, i.e. supx∈RμA(x)=1;

  • 2.

    convexity, i.e. for any x,y∈R, λ∈[0,1] it holds μA(λx+(1−λ)y)⩾min{μA(x),μA(y)}.


In the paper we will use extended operations of

Formulation of the problem

The linear programming problem with fuzzy coefficients in the objective function, abbreviated as LPPFCO, can be formulated in the following way:F(x)=j=1nCjxjmax,x∈X:j=1naijxj⩽bi,i=1,…,m,xj⩾0,j=1,…,n,where Cj, j=1,…,n, are fuzzy numbers.

In the objective function of problem (2) we use of course the extended operations of the addition of fuzzy numbers and of the multiplication of a fuzzy number with a scalar, which are defined in Definition 2. From the properties of these operations it follows

Orlovsky's concept

We will present now a definition of the solution of problem (2) based on the concept of the choice of the best solution with respect to a fuzzy preference relation (defined on the set of feasible solutions), presented by Orlovsky [11].

Let us denote with FN(R) the set of all fuzzy numbers. Let us assume that on this set there is defined a fuzzy preference (order) relation R with the membership function μR:FN(RFN(R)→[0,1]. The value μR(A,B), A,B∈FN(R) denotes the degree to which the fuzzy

Reduction of the LPPFCO problem to the classical linear programming problem

Let us present a sufficient condition assuring that the problem of determining an UND solution of the LPPFCO problem, according to Definition 6, can be reduced to that of determining the optimal solutions of a classical linear programming problem. But first of all let us remind the theorem on the separating hyperplane (see Ref. [8]).

Theorem 2. If two convex sets 1 and 2 have in common at the most some boundary points, then there exists a hyperplanef(x)=a1x1+a2x2+⋯+anxn=b,a0which separates 1

Computational example

Before we give an example illustrating the usefulness of Theorem 3, we will present several proposals of fuzzy preference relations and the ranking functions for those relations. These are of course not the only definitions of fuzzy preference relations which have been proposed so far. A systematic survey and classification of various methods of comparing fuzzy numbers can be found in the paper of Chen and Hwang [5].

Baas and Kwakernaak [1] have suggested fuzzy preference relation R1 with the

Conclusions

The main result of the paper are the conditions which should be fulfilled by the strict fuzzy preference relation assumed in the definition of the solution, which ensure that the problem of determining UND solutions of problem LPPFCO can be reduced to that of determining the optimal solutions of a linear programming problem, with the coefficients in the objective function being the values of a ranking function which exists for this relation. These conditions are a consequence of the theorem we

References (15)

There are more references available in the full text version of this article.

Cited by (66)

  • An approach to interval programming problems with left-hand-side stochastic coefficients: An application to environmental decisions analysis

    2011, Expert Systems with Applications
    Citation Excerpt :

    Optimization techniques were widely used in the field of environmental management and pollution control (Huang & Chang, 2003). Many innovated optimization techniques were developed to tackle uncertainties existing in environmental systems (Chanas & Zielinski, 2000; Chang & Kashani, 2009; Chang & Wang, 1997; He & Huang, 2008; Huang, Baetz, & Patry, 1992, 1994, 1995; Huang, Cohen, & Yin, 1996; Huang, Li, Xiao, & Qin, 2007; Liu, Huang, Liao, & He, 2009; Luo, Maqood, Huang, Yin, & Han, 2005; Qin & Huang, 2009; Yeomans, 2008; Yeomans & Huang, 2003). Among them, Huang et al. (1992) developed an interval linear programming (ILP) approach for municipal solid waste management system.

View all citing articles on Scopus
View full text