DOI:
https://doi.org/10.14483/udistrital.jour.reving.2015.1.a08Published:
20150310Issue:
Vol. 20 No. 1 (2015): January  JuneSection:
Special Section: Best Works "VII Symposium on Optimization"On the Fuzzy Extension Principle for LP Problems with Interval Type2 Technological Coefficients
Acerca Del Principio De Extensión Para Problemas LP Con Parámetros Difusos Tipo2 De Intervalo
Keywords:
Fuzzy sets, Linear Programming, Extension Principle (en).Downloads
References
R. E. Bellman and Lofti A. Zadeh. Decisionmaking in a fuzzy environment. Management Science, 17(1):141– 164, 1970.
Juan Carlos FigueroaGarcía. An approximation method for type reduction of an interval Type2 fuzzy set based on αcuts. In IEEE, editor, Proceedings of FEDCSIS 2012, pages 1–6. IEEE, 2012.
Juan Carlos FigueroaGarcía. A general model for linear programming with interval type2 fuzzy technological coefficients. In 2012 Annual Meeting of the North American Fuzzy Information Processing Society (NAFIPS), pages 1–6. IEEE, 2012.
Juan Carlos FigueroaGarcía, Yurilev ChalcoCano, and Heriberto Roma ́nFlores. Distance measures for in terval type2 fuzzy numbers. Discrete Applied Mathematics, To appear(1), 2015.
Rafail N. Gasimov and Kursat Yenilmez. Solving fuzzy linear programming problems with linear membership functions. Turk J Math, 26(2):375–396, 2002.
George J. Klir and Tina A. Folger. Fuzzy Sets, Uncertainty and Information. Prentice Hall, 1992.
George J. Klir and Bo Yuan. Fuzzy Sets and Fuzzy Logic: Theory and Applications. Prentice Hall, 1995.
Jerry Mendel. Uncertain RuleBased Fuzzy Logic Systems: Introduction and New Directions. Prentice Hall, 1994.
Jerry M. Mendel, Robert I. John, and Feilong Liu. Interval type2 fuzzy logic systems made simple. IEEE Transactions on Fuzzy Systems, 14(6):808–821, 2006.
Jaroslav Ramík. Soft computing: overview and recent developments in fuzzy optimization. Technical report, Institute for Research and Applications of Fuzzy Modeling, 2001.
Jaroslav Ramík. Optimal solutions in optimization problem with objective function depending on fuzzy pa rameters. Fuzzy Sets and Systems, 158(17):1873–1881, 2007.
Jaroslav Ramík and Josef Rimánek. Inequality relation between fuzzy numbers and its use in fuzzy optimiza tion. Fuzzy Sets and Systems, 16:123–138, 1985.
Heinrich Rommelfanger. FULPAL  An interactive method for solving multiobjective fuzzy linear programming problems, pages 279–299. Reidel, Dordrecht, 1990.
Heinrich Rommelfanger. FULP  A PCsupported procedure for solving multicriteria linear programming problems with fuzzy data, pages 154–167. SpringerVerlag, 1991.
Heinrich Rommelfanger. Entscheiden bei UnschSrfe  Fuzzy Decision SupportSysteme 2nd ed. SpringerVerlag, Berlin/Heidelberg, 1994.
Heinrich Rommelfanger. A general concept for solving linear multicriteria programming problems with crisp, fuzzy or stochastic values. Fuzzy Sets and Systems, 158(17):1892–1904, 2007.
How to Cite
APA
ACM
ACS
ABNT
Chicago
Harvard
IEEE
MLA
Turabian
Vancouver
Download Citation
On the fuzzy extension principle for LP problems with Interval Type2 Technological Coefﬁcients
Acerca del principio de extensión para problemas LP con parámetros difusos Tipo2 de Intervalo
Juan Carlos Figueroa García, Universidad Distrital Francisco José de Caldas. jcﬁgueroag@udistrital.edu.co
Recibido: 12022015. Modiﬁcado: 08032015. Aceptado: 10032015
Abstract
A special kind of Linear Programming (LP) problems involve linguistic uncertainty that can be represented by Interval Type2 Fuzzy numbers using the extension principle for fuzzy sets. This principle has been widely used in decision making, computation of a function of fuzzy sets, fuzzy optimization, etc, so this paper focuses to clarify some aspects about its use in LPs with interval Type2 fuzzy technological parameters.
Key words: Fuzzy Sets, Linear Programming, Extension Principle.
Resumen
Una familia especial de problemas de programación lineal (LP) incluyen incertidumbre lingüística que puede ser representada a través de números difusos Tipo2 de intervalo que a su vez se operacionalizan a través del principio de extensión. Este principio ha sido ampliamente utilizado en toma de decisiones, cómputo de funciones de conjuntos difusos, optimización difusa, etc, por lo que en este artículo hacemos algunas claridades acerca de su aplicación en problemas LP con coeﬁcientes tecnológicos deﬁnidos como números difusos Tipo2 de intervalo.
Palabras claves: Conjuntos Difusos, Programación Lineal, Principio de Extensión.
1. Introduction
In some situations decision making is performed by a group of people instead of a single person, so disagreement, ambiguity, and other uncertainty sources can affect the selection of a particular parameter. The main idea of combining Linear Programming (LP) models to fuzzy sets is to include the opinion of multiple experts who deﬁne the left hand side parameters on an LP problem, namely a_{ij}.
In some practical applications, the parameters aij are just realizations of an unknown random process that can be represented through multiple experts perceptions, so the analyst has to ﬁnd a solution given those operation conditions. This way, there is a need for correlate practical issues (random realizations of a_{ij}) to experts perceptions and opinions about a_{ij}.
On the other hand, there is a need for computing the membership degree that a random selection of technological coefﬁcients of an LP problem has, to later analyze their results to what it is expected by experts.
Different approaches to Fuzzy Linear Programming (FLP) problems have been presented in bibliography. Rommelfanger [19], [20], [17], [18], Ramík [14], [15], Ramík & Rimánek [16], and Gasimov & Yenilmez [9] who treated the ﬁeld of classical fuzzy sets and its application in LP problems.
FigueroaGarcía [4] has proposed a model for FLP with uncertain technological parameters deﬁned as Interval Type2 Fuzzy Numbers (IT2FN), FigueroaGarcía & Hernández [7], [6] proposed a method for solving LP problems with Type2 fuzzy constraints, FigueroaGarcía, ChalcoCano & RománFlores [5], and FigueroaGarcía & Hernández [8] provide some deﬁ nitions on fuzzy constraints and fuzzy ordering. Building upon these results, in this paper we apply them to the particular issue of handling random values of aij in order to compute its optimal solution and it satisfaction degree.
This paper focuses on how to compute the membership degree of a random realization of aij given previous experts perceptions and/or opinions about aij which are represented using interval Type2 fuzzy sets, and applied in LP problems. The paper is divided into six sections; a ﬁrst one that introduces the main problem; a second one that shows some basic concepts on interval Type2 fuzzy sets; a third one that presents the interval Type2 fuzzy linear programming model; a fourth section introduces the extension principle for fuzzy sets; a ﬁfth section presents and application example, and ﬁnally some concluding remarks are shown in section 6.
2. Basics on Type2 fuzzy numbers
Firstly, we want to clarify some notations used throughout this paper. An Interval Type2 Fuzzy Set (IT2FS) is denoted by emphasized capital letters Ã whose membership function µ_{Ã} (x) is deﬁned over x ∈ X. A classical fuzzy set µ_{A}_{} is a measure of the afﬁnity of a particular value x ∈ X regarding a concept/word/label A, and µ_{Ã} (x) measures uncertainty of a value x ∈ X regarding A.
In this paper, we use notations and deﬁnitions provided by Jerry Mendel [12]. A Type2 fuzzy set is an ordered pair {((x,u),µ_{Ã} (x,u)) : x ∈ X, u ∈ J_{x} ⊆ [0,1]}, where A is its linguistic label, so Ã represents uncertainty around the word A; F_{1}(X) is the class of all Type1 fuzzy sets over X; F_{2}(X) is the class of all Type2 fuzzy sets over X; P(X) is the class of all crisp sets over X. A Type2 fuzzy set can be represented as follows:
Ã : X → F([0,1])
Ã = {(x,µ_{Ã} (x))  x ∈ X}
Ã = {((x,u),µ_{Ã }(x,u)  ∀x ∈ X,∀u ∈ J_{x} ⊆ [0,1]}
where J_{x} is the set of primary membership degrees of x ∈ X, 0 ≤ µ_{Ã}(x,u) ≤ 1, and u is its domain of uncertainty.
An IT2FS Ã encloses an inﬁnite amount of clasical fuzzy sets into its Footprint of Uncertainty (FOU), and A_{e} is a Type1 fuzzy set embedded in its FOU (see Mendel et al [13]):
Ã = {(x,µ_{Ã} (x))x ∈ X}
where µ_{Ã}(x) is completely characterized by J_{x} ⊆ [0,1].
A simpler Type2 fuzzy set is called Interval Type2 fuzzy set (IT2FS) in which u = 1, and is characterized by two primary membership functions: Upper Membership Function (UMF) namely µ¯_{Ã}, and Lower Membership Function (LMF) namely µ_{ Ã} . Figure 1 shows the set Ã.
As discussed by FigueroaGarcía, ChalcoCano & RománFlores [5], a Type2 fuzzy num ber (T2FN) is considered as the extension of a Type1 fuzzy number. This is, Ã is a T2FS whose UMF and LMF are fuzzy numbers e.g a normal fuzzy set, ^{α}A is closed interval for all α ∈ [0,1], and its support supp(A) ∈ P(R) is bounded which means that a fuzzy number is a convex fuzzy set as well.
The αcut of A is deﬁned as ^{α}A = {xµ_{A}(x) ≥ α}. This makes the computation of any function f(x) of fuzzy sets easier. Here, z* = c'x* comes from f( Ã_{i})(z*), so we want to compute f( Ã_{i})(z*) by using αcuts instead of mapping x_{i}. The αcut of A is simply the cut ^{α}J_{x} = {xµ_{A}(x) ≥ α} done over its primary membership function J_{x} (see Figueroa [3],and FigueroaGarcía, ChalcoCano & RománFlores [5]). A graphical representation of ^{α}Ã is provided in Figure 2.
3. The Interval Type2 fuzzy LP problem
First, the classical crisp LP problem is basically is a model that relates a set of m inequalities whose goal is to maximize the value of an objective (a.k.a goal) function, as follows:
Now, when technological parameters A cannot be well deﬁned or they are bad measured, we need to use other methods to get those parameters. A popular way to get them is by using experts opinions, so the use of fuzzy sets to quantify its perceptions about A become an im portant information source. Commonly in the industry, there are more than one expert who can provide valuable information about A, so we need to comprise all their perceptions and opinions into a single measure: an IT2FN.
This leads us to redeﬁne the crisp LP model as an IT2FLP, as follows:
This model cannot be solved in a closed form, so the idea in this paper is to show how to compute the membership degree of any crisp solution and how to understand its sense. Based on the results of FigueroaGarcía [4] we do a complement of his results by clarifying some concepts about random solutions instead of αcuts (which is also a reasonable method).
The αcuts approach proposed by FigueroaGarcía [4] is way to go from Ã to ˜z (which is the IT2FS of optimal solutions), but it does not include random choices of A. A random choice of A is a selection of different aij that depends on the current conditions of the system, and mostly are just available conditions under the system has to operate, so the analyst has no any guarantee that their results are the best possible or even good, they are just solutions of the IT2FLP.
Next section is dedicated on explain how to compute the membership degree that any random solution has, and how to understand its meaning.
4. Extension principle for IT2FS
A ﬁrst approach to ﬁnd an appropriate way for modeling fuzzy functions is given by the Zadeh’s Extension principle (see Bellman & Zadeh [1], Klir & Yuan [10], and Mendel [12]). Let f be a function such as f : X_{1},X_{2},··· ,X_{n} → z, and A_{i} is a fuzzy set in X_{i}, i = 1,2,··· ,n with x_{i} ∈ X_{i}, then we have
The fuzzy extension principle projects any function e.g z = f(x_{1},x_{2},··· ,x_{n}) to a fuzzy set by using their memberships A_{1}(x_{1}),A_{2}(x_{2}),··· ,A_{n}(x_{n}). Its extended version is as follows.
Deﬁnition 1 Let A_{x} ∈ supp ( Ã) be a matrix of crisp technological coefﬁcients, A_{x} ∈ R^{m,n}, and z*_{x} = c'x* be the optimal solution of the LP for A_{x}. Then we have
where i' ∈ k is the set of all binding constraints of the optimal program.
This Deﬁnition computes the membership degree of any random solution z*_{x} regarding the set ˜z. Basically it is computed using the membership degree that A_{x} has regarding the sets Ã_{ij}, that is µ¯_{Ãij} and µ_{Ãij} which ﬁnally lead to f(A_{x})(z*_{x}).
5. Application example
To illustrate how an IT2FLP works, we present the following example. Suppose that a company has to plan the production quantity (in thousands) of two products x_{1} and x_{2}, where every sold product returns c_{1} = 2 and c_{2} = 3 thousand US dollars (proﬁts) per unit, and its production requires two materials which are available by b_{1} = 12 and b_{2} = 15 tons, respectively. The material consumption a_{ij} per product x_{1},x_{2} is uncertain since historical data is absent, so the analyst is encouraged to ﬁnd a way to plan the best production quantities that maximize proﬁts.
Given hypothetical normal operation conditions, it is supposed that the material consumption per product should be a_{11} = 1,a_{12} = 4,a_{21} = 3 and a_{22} = 2, but it is a hard supposition since we do not have historical information about the material consumption in order to verify the performance of the company. To have a better idea about the system, we have to ask the people involved into production planning, so we enquire to ﬁve experts (people on manufacturing, engineering, mechanical processes, etc) about their perception around material consumption of every product.
Now, both uncertain parameters and information that comes from multiple experts (perceptions and opinions) leads us to deal with Type2 fuzzy uncertainty, so a_{ij} turns into Ã_{ij}. This way, the experts are encouraged to provide its opinions about “Normal material consumption” of every Ã_{ij} using two boundaries: pessimistic and optimistic. The description of the IT2FLP is given next:
The analyst has to use the information provided by the experts, which usually is described using sentences such as “I think that the parameter (i,j) should be between a and c”, or “I think that the most possible value of the parameter (i,j) should be b”. Now, the ﬁve experts namely E1,··· ,E5 were asked for the parameters a_{ij} using the above sentences having the same idea about its most possible value (provided as starting information in the model, but they are not agree about their perceptions around its boundaries.
In this paper, the UMF and LMF of every aij are triangular membership functions. A triangular membership function T(a,b,c) is deﬁned by an optimistic boundary a, an expected value b, and a pessimistic boundary c, as follows:
The complete description of a_{ij} is shown next:
First, we solve the IT2FLP using the method proposed by FigueroaGarcía [4] which computes a predetermined amount of αcuts (in this case 10), and then solve the 4α crisp problems using 1. This leads to solve a crisp LP for ^{α}Ã^{L(+)},^{α}Ã^{L(−)},^{α}Ã^{R(−)} and ^{α}Ã^{R(+)} (see Figure 2). Finally the set of optimal solutions ˜ z is done by using the representation theorem and the extension principle for fuzzy sets (see Klir & Yuan [11]), this is f( Ã)(z*). The set of optimal solutions ˜z is shown in Figure 3
Figure 3 show the whole set of optimal solutions of the IT2FLP as a function of α. In practice there is no any certainty that the values of A corresponding to ^{α}Ã occur. Nay, what we can see in practical applications are random realizations of Ã namely A_{x}, which indeed lead to an optimal solution z*_{x} having a membership degree that can be computed by using Deﬁnition 1.
FigueroaGarcía [4] did not consider random realizations A_{x} of Ã since that method maps uncertainty using αcuts while this paper is focused to compute the membership of A_{x} regarding the set ˜ z of optimal solutions proposed by FigueroaGarcía [4]. The current proposal complements the results of FigueroaGarcía [4] in the sense that he maps all uncertainty of Ã while in this paper the membership of a random value A_{x} is computed and enclosed into ˜ z.
Now, suppose that the following values A_{x} → a_{11} = 0.7,a_{12} = 6.2,a_{21} = 3.1 and a_{22} = 1.4 are observed, leading to z*_{x} = 12.7467. The question is, how satisfactory is this solution to the experts?. This can be computed using Deﬁnition 1 as follows:
Now, the membership value of f(A_{x})(z*_{x} = 12.7467) is computed as follows
This means that the optimal z*_{x} = 12.7467 is satisfactory to all experts in the range [0,0.2667]. On the other hand, this interval of satisfaction degrees is not as large as the corresponding α cut is, which means that arbitrary choices of A_{x} ∈ Ã are not always the most satisfactory solutions of the problem.
A fully satisfactory crisp solution of this example is z* = 13.5 coming from x*_{1} = 3.6,x_{2} = 2.1. It can be compared to the solution provided by A_{x} which is z*_{x} = 12.7467 coming from x*_{1} = 4.18,x*_{2} = 1.46 in the sense that A_{x} is a random realization of Ã while the crisp solution needs more materials than the random problem except from ﬁrst material for second product. Other issue is that the crisp problem is the expected value of the problem which is a less possible combination of parameters. The random problem prefers to produce more units of x_{1} than the crisp one and reduces the quantities of x_{2} to have a better usage of materials.
Both examples provide different solutions for different operation points of the system, so every optimal solution provides a different way to operate the system.
6. Concluding remarks
We have clariﬁed the meaning of the extension principle applied to IT2FLPs when using random choices of a_{ij} which are enclosed into Ã_{ij}. This kind of solutions are enclosed into the set of optimal solutions ˜ z, but their membership degrees are smaller than the αcuts solutions which in practice means that random selections of a_{ij} are less satisfactory to the experts of the system even when they are feasible and optimal.
A practical example that shows the applicability of our results is presented to illustrate how a random choice can be optimal in a crisp sense, but less satisfactory to experts expectations about the system’s performance.
Based on the IT2FLP model proposed by FigueroaGarcía [4], [2], and some deﬁnitions about fuzzy constraints provided by FigueroaGarcía, ChalcoCano & RománFlores [5] we have extended the applicability of IT2FLPs in presence of random parameters a_{ij} which is a common issue seen on practical applications. Now, the analyst can see how satisfactory an optimal solution is, given any combination of parameters a_{ij}.
Next steps lead to general modeling for FLPs with fuzzy costs, technological coefﬁcients, and constraints which are more complex problems. Also the use of generalized Type2 fuzzy sets comes as a new way to represent uncertainty, so its potential use in optimization arises as a new ﬁeld to explore.
References

R. E. Bellman and Lofti A. Zadeh. Decisionmaking in a fuzzy environment. Management Science, 17(1):141– 164, 1970.

Juan Carlos FigueroaGarcíıa. Linear programming with interval type2 fuzzy right hand side parameters. In 2008 Annual Meeting of the IEEE North American Fuzzy Information Processing Society (NAFIPS), 2008.

Juan Carlos FigueroaGarcía. An approximation method for type reduction of an interval Type2 fuzzy set based on αcuts. In IEEE, editor, In Proceedings of FEDCSIS 2012, pages 1–6. IEEE, 2012.

Juan Carlos FigueroaGarcía. A general model for linear programming with interval type2 fuzzy technological coefﬁcients. In 2012 Annual Meeting of the North American Fuzzy Information Processing Society (NAFIPS), pages 1–6. IEEE, 2012.

Juan Carlos FigueroaGarcía, Yurilev ChalcoCano, and Heriberto RománFlores. Distance measures for in terval type2 fuzzy numbers. Discrete Applied Mathematics, To appear(1), 2015.

Juan Carlos FigueroaGarcía and German Hernández. Constraint Programming and Decision Making  Studies in Computational Intelligence, volume 539, chapter Linear Programming with Interval Type2 fuzzy cons traints, pages 19–34. Springer Verlag, 2014.

Juan Carlos FigueroaGarcía and Germán Hernández. A method for solving Linear Programming models with Interval Type2 fuzzy constraints. Pesquisa Operacional, 34(1):1–17, 2014.

Juan Carlos FigueroaGarcía and Germán Jairo HernándezPérez. On the computation of the distance between interval type2 fuzzy numbers using acuts. In Annual Meeting of the North American Fuzzy Information Processing Society (NAFIPS), volume 1, pages 1–6. IEEE, 2014.

Rafail N. Gasimov and Kürs¸at Yenilmez. Solving fuzzy linear programming problems with linear membership functions. Turk J Math, 26(2):375–396, 2002.

George J. Klir and Tina A. Folger. Fuzzy Sets, Uncertainty and Information. Prentice Hall, 1992.

George J. Klir and Bo Yuan. Fuzzy Sets and Fuzzy Logic: Theory and Applications. Prentice Hall, 1995.

Jerry Mendel. Uncertain RuleBased Fuzzy Logic Systems: Introduction and New Directions. Prentice Hall, 1994.

Jerry M. Mendel, Robert I. John, and Feilong Liu. Interval type2 fuzzy logic systems made simple. IEEE Transactions on Fuzzy Systems, 14(6):808–821, 2006.

J. Ramík. Soft computing: overview and recent developments in fuzzy optimization. Technical report, Institute for Research and Applications of Fuzzy Modeling, 2001.

Jaroslav Ramík. Optimal solutions in optimization problem with objective function depending on fuzzy para meters. Fuzzy Sets and Systems, 158(17):1873–1881, 2007.

Jaroslav Ramík and Josef Rimánek. Inequality relation between fuzzy numbers and its use in fuzzy optimization. Fuzzy Sets and Systems, 16:123–138, 1985.

H Rommelfanger. FULPAL  An interactive method for solving multiobjective fuzzy linear programming problems, pages 279–299. Reidel, Dordrecht, 1990.

H Rommelfanger. FULP  A PCsupported procedure for solving multicriteria linear programming problems with fuzzy data, pages 154–167. SpringerVerlag, 1991.

H Rommelfanger. Entscheiden bei UnschSrfe  Fuzzy Decision SupportSysteme 2nd ed. SpringerVerlag, Berlin/Heidelberg, 1994.

Heinrich Rommelfanger. A general concept for solving linear multicriteria programming problems with crisp, fuzzy or stochastic values. Fuzzy Sets and Systems, 158(17):1892–1904, 2007.
Juan Carlos FigueroaGarcía
He is an Assistant Professor at the Engineering Faculty of the Universidad Distrital Francisco José de Caldas  Bogotá, Colombia. He obtained his bachelor degree on Industrial Engineering at the same university in 2002, a Master degree on Industrial Engineering at the same university in 2010, and a Ph.D. degree on Industry and Organizations at the Universidad Nacional de Colombia in 2014. His main interests are: fuzzy sets, fuzzy optimization, time series analysis and evolutionary optimization.
email: jcﬁgueroag@udistrital.edu.co
This work is authorized by an AttributionNonCommercialNoDerivs CC BYNCND license.
License
From the edition of the V23N3 of year 2018 forward, the Creative Commons License "AttributionNonCommercial  No Derivative Works " is changed to the following:
Attribution  NonCommercial  Share the same: this license allows others to distribute, remix, retouch, and create from your work in a noncommercial way, as long as they give you credit and license their new creations under the same conditions.