Theory and MethodologyOn the equivalence of two optimization methods for fuzzy linear programming problems
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 characterized by means of a membership function μA(x), , which is upper semicontinuous and which fulfils the following conditions:
- 1.
normality, i.e. ;
- 2.
convexity, i.e. for any , λ∈[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: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 the set of all fuzzy numbers. Let us assume that on this set there is defined a fuzzy preference (order) relation with the membership function . The value , 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 and have in common at the most some boundary points, then there exists a hyperplanewhich separates
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 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)
- et al.
Rating and ranking of multiple-aspect alternatives using fuzzy sets
Automatica
(1977) - et al.
A procedure for ranking fuzzy numbers using fuzzy relations
Fuzzy Sets and Systems
(1988) On equivalence of two optimization methods for fuzzy discrete programming problems
European Journal of Operational Research
(1988)- et al.
Linear programming with fuzzy objectives
Fuzzy Sets and Systems
(1989) A procedure for ordering fuzzy subsets of the unit interval
Information Science
(1981)- S. Chanas, Fuzzy optimization in networks, in: J. Kacprzyk, S. Orlovsky (Eds.), Optimization Models Using Fuzzy Sets...
- S. Chanas, D. Kuchta, Linear programming with fuzzy coefficients in the objective function, in: M. Delgado, J....
Cited by (66)
Soft robust solutions to possibilistic optimization problems
2021, Fuzzy Sets and SystemsHesitant fuzzy numbers with (α, k)-cuts in compact intervals and applications
2020, Expert Systems with ApplicationsAn inexact programming approach for urban electric power systems management under random-interval-parameter uncertainty
2015, Applied Mathematical ModellingAn approach to interval programming problems with left-hand-side stochastic coefficients: An application to environmental decisions analysis
2011, Expert Systems with ApplicationsCitation 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.
ICQSWM: An inexact chance-constrained quadratic solid waste management model
2010, Resources, Conservation and Recycling