Abstract
We investigate various types of fuzzy linear programming problems based on models and solution methods. First, we review fuzzy linear programming problems with fuzzy decision variables and fuzzy linear programming problems with fuzzy parameters (fuzzy numbers in the definition of the objective function or constraints) along with the associated duality results. Then, we review the fully fuzzy linear programming problems with all variables and parameters being allowed to be fuzzy. Most methods used for solving such problems are based on ranking functions, \(\alpha \)-cuts, using duality results or penalty functions. In these methods, authors deal with crisp formulations of the fuzzy problems. Recently, some heuristic algorithms have also been proposed. In these methods, some authors solve the fuzzy problem directly, while others solve the crisp problems approximately.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
1 Introduction
A linear programming model may represent a real-world situation involving a number of parameters whose values are assigned by experts. However, experts and decision makers frequently do not know the precise values of the parameters. Also, in most optimization problems, there are parameters with imprecise values (see Buckley and Jowers 2008; Wan and Li 2014, 2015; Wan and Dong 2015; Wan et al. 2015, 2017a, b, 2018; Xu et al. 2016). Linear programming problems with imprecise decision variables or parameters play major roles in several applications in various areas such as mathematical modeling (see Tanaka et al. 1973; Zimmermann 1983), manufacturing and production (see Hsu and Wang 2001; Kara et al. 2009), agricultural economics (Lai and Hwang 1992; Leung 1988), network location (Darzentas 1987), banking and finance (Hillier 2010; Lai and Hwang 1994; Leon et al. 2002), resource allocation (Abboud et al. 1998; Lai and Li 1999), environment management (Li et al. 2010), supply chain management (Bilgen 2010; Chen and Tzeng 2000), inventory management (Mondal and Maiti 2003; Roy and Maiti 1997, 1998), media selection (Wiedey and Zimmermann 1978), trade balance (Chanas and Kolodziejczyk 1982), management of the reservoir watershed (Chang et al. 1997), dimension design (Chen and Lin 2001), transportation management (Chanas and Kuchta 1996, 1998; Liu and Kao 2004), product mix (Karakas et al. 2010), game theory (see Bector et al. 2004; Vijay et al. 2007), engineering and economics (Buckley et al. 2002), graph theory (Cornelis et al. 2004) and manufacturing (Mahdavi et al. 2011). Also, more applications of fuzziness in different fields can be seen in Baykasoglu and Gocken (2012), Ebrahimnejad and Tavana (2014b) and Sakawa et al. (2001).
Consider a linear programming problem as follows:
where \(c \in \mathbb {R}^n\), \(A \in \mathbb {R}^{m \times n}\), \(x \in \mathbb {R}^n\) and \(b \in \mathbb {R}^{m}\). In a fuzzy linear programming problem (FLPP), variables or parameters are considered to be fuzzy numbers. Here, we investigate various types of fuzzy linear programming problems based on the models and the solutions methods. We divide fuzzy linear programming problem into three groups according to their models. In the first group, the variables of \(\text {(LP)}\) are considered to be fuzzy numbers, naming it as \(\text {FVLPP}\). In the second group, parameters of \(\text {(LP)}\) are considered as fuzzy numbers, denoted by \(\text {FNLPP}\). In the third group, variables and parameters are considered to be fuzzy numbers, named as \(\text {FFLPP}\).
We review some methods for solving different types of FLPPs. We classify various models of FLPP and their solution methods. In Sect. 2, we review the FVLPPs and its corresponding dual. In Sect. 3, we survey the FNLPPs (fuzzy numbers in the objective function or constraint definitions) and their associated duality results. In Sect. 4, we discuss the FFLPPs. In Sect. 5, we survey some heuristic methods for solving fuzzy linear programming problems.
Next, we give some basic fuzzy notations and definitions.
Definition 1
(Buckley and Jowers 2008) (Fuzzy sets) If X is a collection of objects denoted generically by x, then a fuzzy set A in X is defined to be a set of ordered pairs,
Remark 1
We assume that X is the real line \(\mathbb {R}\).
Definition 2
(Buckley and Jowers 2008) (Support) If A is a fuzzy set, then its support, denoted by suppA, is defined to be
Definition 3
(Buckley and Jowers 2008) (\(\alpha \)-cut) The \(\alpha \)-cut of fuzzy set A is denoted by \(A_{\alpha }\) and is defined to be
where \(\alpha \in (0,1]\).
Definition 4
(Buckley and Jowers 2008) (Core) The core of a fuzzy set is the set of points x in X with \(\mu _{A}(x)=1\).
Definition 5
(Nguyen and Walker 2000) A fuzzy number is a fuzzy quantity \(\tilde{A}\) satisfying the following conditions:
- 1.
\(\mu _{\tilde{A}}(x)=1\), for exactly one \(x=r\) and \(0<\mu _{\tilde{A}}(x)<1\), for \(x \ne r\).
- 2.
\(supp \tilde{A}\) is bounded.
- 3.
The \(\alpha \)-cuts of \(\tilde{A}\) are closed intervals.
Remark 2
We denote the set of all fuzzy numbers by \(F(\mathbb {R})\).
Definition 6
(Ranking function) An effective approach for ordering the elements of \(\textit{F}\)(\(\mathbb {R}\)) is to define a ranking function, which maps each fuzzy number into the real line, \(\textit{R}\): \(\textit{F}\)(\(\mathbb {R}\))\(\rightarrow \)\(\mathbb {R}\) (see Zimmermann 2001 for more details).
2 Fuzzy linear programming problems with fuzzy variables
We first discuss some applications of fuzzy variable linear programming problems. Baykasoglu and Gocken (2012) presented an algorithm based on the constrained fuzzy arithmetic concept to solve fuzzy transportation problems where the decision variables (transportation quantities) are considered as fuzzy numbers. Chanas and Kolodziejczyk (1984) studied a network problem where the flow is a real number and the fuzzy arc capacities have upper and lower bounds with a satisfaction function.
Consider the FVLPP as
where \(\tilde{b} \in F (\mathbb R^m),\,\,\,\,A \in \mathbb R^{m \times n} \) and \(c \in \mathbb R^n \) are given and \(\tilde{x} \in F (\mathbb R^n)\) is to be determined. In this model, the coefficient matrix, A, is crisp, but the decision vector \(\tilde{x}\) is composed of fuzzy numbers.
One convenient approach for solving FVLPPs is based on the concept of comparison of fuzzy numbers by use of a ranking function (see Mahdavi-Amiri and Nasseri 2006, 2007; Mahdavi-Amiri et al. 2009; Serenko and Dohan 2011; Wang and Kerre 2001). Ranking functions have been proposed to suit the requirements of the problems under consideration by Campos and Verdegay (1989).
Here, we intend to review some methods for solving FVLPPs using ranking functions on trapezoidal fuzzy numbers. Mahdavi-Amiri and Nasseri (2007) used a linear ranking function to order trapezoidal fuzzy numbers. A linear ranking function on trapezoidal fuzzy numbers is defined as
where \(\tilde{a} = (a^L ,a^U ,\alpha ,\beta )\)\(\in F(\mathbb {R})\) and \(C_L ,\,\,C_U ,\,\,C_\alpha ,\,\,C_\beta \) are constants, at least one of which is nonzero. They used a special version of the above linear ranking function proposed by Yager (see Fortemps and Roubens 1996; Yager 1981) as follows:
The above expression is easily obtained from (1) by setting \(C_U=\frac{1}{2}, C_L=\frac{1}{2}, C_\alpha =\frac{1}{4}\) and \(C_\beta =\frac{1}{4}\). The authors in Mahdavi-Amiri and Nasseri (2007) considered the linear programming problem with trapezoidal fuzzy variables as
where \(= _R\), \(\le _R\) and \(\ge _R\), receptively, mean equality and inequalities with respect to the ranking function (2).
They established the dual of (3) to be
and deduced the usual duality results. The results followed as natural extensions of duality results for linear programming problems with crisp data (such as weak duality, strong duality, fundamental theorem of duality and complementary slackness); see Bazaraa et al. (2009). Then, a dual simplex algorithm (Mahdavi-Amiri and Nasseri 2007) and a primal simplex algorithm (Mahdavi-Amiri et al. 2009) were developed for solving fuzzy linear programming problems. Mahdavi-Amiri et al. (2009) considered FVLPP as follows:
where \(\tilde{b} \in F (\mathbb R^m),\,\,\,\,A \in \mathbb R^{m \times n} ,\,\,c \in \mathbb R^n\) and \(\tilde{x} \in F (\mathbb R^n)\). They showed that a fuzzy vector \(\tilde{x} \in F (\mathbb R^n)\) is a fuzzy feasible solution for (4), if \(\tilde{x}\) satisfies the constraints \( A\tilde{x} = _R \tilde{b}\) and \(\tilde{x} \ge _R \tilde{0}\). They defined that a fuzzy feasible solution \(\tilde{x}^*\) is a fuzzy optimal solution for (4), if for every fuzzy feasible solution \({\tilde{x}}\) for (4), we have \(c^{T}\tilde{x}^* \ge _R c^{T}\tilde{x}\). Then, they described a fuzzy basic solution as follows.
Assume the coefficient matrix A is \([B,\,N]\), where B is a non-singular matrix. Let \(y_j\) be the solution to \(By = a_j\), \(\forall j=1,\ldots ,n\). Then,
is a solution of \(A\tilde{x} = _R \tilde{b}\). They called \({\tilde{x}}\), accordingly partitioned as \((\tilde{x}_B ^T ,\,\,\tilde{x}_N ^T )^T\), a fuzzy basic solution corresponding to the basis B. Next, they used a primal simplex method for solving (4). It should be noted that originally (Maleki et al. 2000) defined their model as follows:
Then, they defined an auxiliary model corresponding to (5), not realizing it being the dual of (5), as:
Next, to arrive at a solution of (5) with fuzzy variables, they made use of the solution of the auxiliary problem. The later results by Mahdavi-Amiri and Nasseri (2007) established that the auxiliary problem is indeed the dual of (5), leading to both primal and dual simplex algorithms (see Mahdavi-Amiri and Nasseri 2007; Mahdavi-Amiri et al. 2009).
Ebrahimnejad and Tavana (2014a) proposed a method for solving fuzzy linear programming problems in which the coefficients of the objective function and the values of the right-hand side were represented by symmetric trapezoidal fuzzy numbers, while the components of the coefficient matrix were represented by real numbers. They converted the fuzzy linear programming problem into an equivalent crisp linear programming problem and solved the crisp problem with the standard primal simplex method. They showed that the proposed method was simpler and computationally more efficient than two competing FLP methods commonly used in the literature.
Next, we turn to FVLP problems, with both the cost coefficient vector (c) and variables being fuzzy numbers. Ganesan and Veermani (2006) used symmetric trapezoidal fuzzy numbers in their model. They denoted a symmetric trapezoidal fuzzy number by \(\tilde{a} = [a_1 ,a_2 ,h,h]\). They defined a fuzzy linear programming problem with trapezoidal symmetric variables as follows:
where \(a_{ij} \in \mathbb R,\,\,\tilde{c}_j ,\,\tilde{x}_j \) and \( \tilde{b}_i \in F(\mathbb R)\). Then, they defined \(\tilde{x} \succeq \tilde{0}\), if there exist \(a \ge 0\) and \(h\ge 0\) such that \(\tilde{x} \succeq [-a,\, a,\, h,\, h]\). They also defined any vector \(\tilde{x} = (\tilde{x}_1 ,\ldots ,\tilde{x}_n )\), where \(\tilde{x}_i \in F(\mathbb R)\), satisfying the constraints and nonnegativity restrictions of (6) to be a feasible solution. They also obtained interesting results about improving a basic feasible solution which in turn lead to a solution of (6) without converting it to a crisp linear program, developing a concept of fuzzy basic solution, establishing some results about basic solutions and characterizing unbounded solutions. Nasseri et al. (2010) followed the work of Ganesan and Veermani and introduced the dual of a linear programming problem with symmetric trapezoidal fuzzy numbers. They defined the fuzzy linear programming problem as
where \(\tilde{b}\in F (\mathbb R^m)\), \(\tilde{c}\in F(\mathbb R^n)\) and \(A\in F(\mathbb R^{m \times n})\) are given and \(\tilde{x} \in F(\mathbb R^n)\) is to be determined. They defined the dual of problem (7) as follows:
Then, they proved some results such as weak duality, strong duality, fundamental theorem and complementary slackness, quite similar to the ones given by Mahdavi-Amiri and Nasseri (2007). Finally, they solved (7) based on the given duality results. Recently, Ebrahimnejad et al. (2010), based on the results established by Ganesan and Veermani (2006), proposed a new approach to solve a kind of bounded linear programming problems involving symmetric trapezoidal fuzzy numbers without converting them to crisp linear programming problems. This approach is useful for situations in which some or all fuzzy variables are restricted to lie within lower and upper bounds. Also, Ebrahimnejad et al. (2011) proposed a bounded fuzzy primal simplex algorithm starting with a primal feasible basis and moved toward attaining primal optimality while maintaining primal feasibility throughout. The algorithm is useful for sensitivity analysis using primal simplex tableaus.
Nasseri and Mahdavi-Amiri (2009) extended the results of Ganesan and Veermani (2006). They proved the optimality theorem and then defined the dual problem of FVLPP with symmetric fuzzy numbers. Furthermore, they gave some duality results as a natural extension of duality results for linear programming problems with crisp data.
Xiaozhong (1997) considered a particular kind of FVLPP. He denoted a triangular fuzzy number by \(\tilde{u} = (u,\,\,\underline{u},\,\,\bar{u})_{\bigtriangleup }\), where \(u-\underline{u}\) and \(u+\underline{u}\), respectively, represent the lower and upper limits of the support of \(\tilde{u}\) with mode u. He defined \(\tilde{u} \preceq \tilde{v}\) as follows:
where \(u = (u,\,\,\underline{u},\,\,\bar{u})\) and \(v = (v,\,\,\underline{v},\,\,\bar{v})\). Using this definition, he defined the problem as follows:
Assuming \(\tilde{t}_i\) as a triangular fuzzy number (fixed by the decision maker) giving allowable maximum violation in the accomplishment of the i-th constraint, (9) turns to
The above problem was then changed into the following two problems:
and
where \(A=(a_{ij})_{m \times n}\), \(|A|=(|a_{ij}|)_{m \times n}\), \(c=(c_{kj})_{l \times n}\) and \(|c|=(|c_{kj}|)_{l \times n}\), \(i=1, \ldots , m, \, j=1, \ldots , n, \, k=1, \ldots , l\). Problems (10) and (11) are then solved by a simplex method. To apply the theories and methods of linear programming, see Dantzing 1998; Katchian 1980.
Alizadeh Sigarpich et al. (2011) discussed degeneracy of fuzzy linear programming problem using the notions of strong and weak degeneracy and provided techniques for prevention of cycling in fuzzy degenerate problems. One technique was to apply “fuzzy perturbation,” and the other was a “lexicographic rule,” applied in a fuzzy environment.
In many real-life problems, one has to base decision on information which is both fuzzily imprecise and probabilistically uncertain. Modeling and problem-solving issues relate to situations where randomness and fuzziness co-occur in a linear programming framework. So, fuzzy stochastic linear programming is an attempt to fulfill this need; see other works for solving FVLP problems (Aliev et al. 2007; Buckley and Jowers 2008; Luhandjula 2006; Nasseri 2008; Pandian and Jayalakshmi 2010; Stanciulescu et al. 2003; Tanaka et al. 2000; Tsakiris and Spiliotis 2004).
3 Fuzzy linear programming problems with fuzzy parameters
We first point out some application of fuzzy linear programming problems with fuzzy parameters. Liu and Kao (2004) investigated network flow problems with arc lengths of the network being fuzzy numbers. Kumar and Kaur (2011) used fuzzy linear programming problems for maximal flow. Hernades et al. (2007) proposed an algorithm, based on the classical Ford–Fulkerson algorithm, to solve the fuzzy maximal flow problem. The algorithm used a technique of incremental graph representing all the parameters as fuzzy numbers; for more applications, see Chanas (1983), Ramik and Rimanek (1985), Rommelfanger (2004), Rommelfanger (2006), Xu et al. (2002), and Zadeh (1965).
Next, we review some fuzzy linear programming problems with fuzzy parameters and also discuss fuzzy relational equations. A fuzzy number linear programming problem (FNLPP) is
where \(\tilde{A}\in F(\mathbb {R}^{m\times n} )\), \({\tilde{c}}\in F(\mathbb {R}^{n})\), \({\tilde{b}}\in F(\mathbb {R}^{m})\) and \(x \in \mathbb R^{n}\) is to be found. Here A, b and c are composed of fuzzy numbers, but the decision variable is crisp. Maleki et al. (2000) explored the use of comparison of fuzzy trapezoidal numbers and introduced an effective method for solving these problems based on a ranking function. They worked on the FNLPP model defined as
where \(\tilde{a}_{ij}=(a_{ij}^{L}, a_{ij}^{U}, \alpha _{ij}, \beta _{ij})\), \(\tilde{b}_{i}=(b_{i}^{L}, b_{i}^{U}, \alpha _{i}, \beta _{i})\) and \(\tilde{c}_{j}=(c_{j}^{L}, c_{j}^{U}, \alpha _{j}, \beta _{j})\), \(i=1, \ldots , m, j=1, \ldots , n\), are trapezoidal fuzzy numbers. They defined x to be a feasible solution for (12), if it satisfies the constraints in (12) based on the considered ranking function. Also, \(x^{0}\) is an optimal feasible solution for (12), if \(\tilde{c}^T{x}^{0} \ge \tilde{c}^T x\) for all feasible solutions x. They also showed that problem (12) using a ranking function could be reduced to a problem in the classical form as follows:
where the \(b_{i}\) and \(a_{ij}\) are crisp values obtained by use of a ranking function on \(\tilde{b}_{i}\) and \(\tilde{a}_{ij}\), respectively. Then, they defined optimality conditions for (12) by using linear ranking function as in the usual discussion of the classical linear programming problem.
Mahdavi-Amiri and Nasseri (2006) explored some duality properties of FNLPP (weak duality, strong duality, complementary slackness; see Buckley and Feuring (2000). They established the dual of fuzzy number linear programming primal problems as
Then, they presented several duality results. Ebrahimnejad (2011) considered the FNLPPs based on Mahdavi-Amiri and Nasseri’s (2006) work. He reviewed the results obtained in Mahdavi-Amiri and Nasseri (2006) and gave some duality results of FNLPP proposed by Mahdavi-Amiri and Nasseri (2006) (weak duality property, strong duality, fundamental theorem of duality; see also Verdegay 1984). Next, the author reviewed two existing methods (fuzzy primal simplex of Mahdavi-Amiri et al. (2009) and fuzzy dual simplex algorithm of Mahdavi-Amiri and Nasseri (2007)) for solving FNLPPs proposed by Mahdavi-Amiri et al. (2009) and Nasseri and Ebrahimnejad (2010).
He also generalized the concept of sensitivity analysis in FLNP problems by applying fuzzy simplex algorithm and using general linear ranking functions on fuzzy numbers. The purpose of sensitivity analysis was to determine changes in the optimal solution of FNLPP resulting from changes in the data. If the change affected the optimality of the basis, he performed primal pivots to achieve optimality by use of the fuzzy primal simplex method. Whenever the change turned to infeasibility of the optimal basis, he performed dual pivots to achieve feasibility by use of the fuzzy dual simplex method (see also Ebrahimnejad and Tavana 2014a).
Ebrahimnejad and Nasseri (2009) considered an FNLPP as in Mahdavi-Amiri and Nasseri (2006), Mahdavi-Amiri and Nasseri (2007) and Maleki et al. (2000):
where \(\tilde{b} \in F({\mathbb {R}}^{m})\), \(\tilde{A}=(\tilde{a}_{ij})_{m \times n} \in F(\mathbb {R}^{m \times n})\), \(\tilde{c} \in F(\mathbb {R}^{n})\) with components being trapezoidal fuzzy numbers, and \(x \in \mathbb {R}^n\). They defined dual of (14) as (13) (Mahdavi-Amiri and Nasseri 2006) and used the complementary slackness result to solve (14) without the need for a simplex tableau. They explained complementary slackness for FNLPP as follows.
Let \(\tilde{x}^{*}\) and \(\tilde{w}^{*}\) be any feasible solution to an FNLPP and its corresponding dual problem. Then, \(x^{*}\) and \(w^{*}\) are, respectively, optimal if and only if
They discussed condition (15) to be equivalent to (below, \(\tilde{a}^{i}\) refers to the i-th row and \(\tilde{a}_{j}\) refers to the j-th column of \(\tilde{A}\)):
or equivalently,
Letting \(u_{i}=R(\tilde{a}^{i})x - R(\tilde{b}_i) \ge 0\), \(i=1, \ldots , m\), as the slack variables of the FNLPP and \(v_{j}= R(\tilde{c}_j)-w^T R(\tilde{a}_{j}) \ge 0\), \(j=1, 2, \ldots , n\), as the slack variables of the dual problem DFNLPP, the complementary slackness conditions are written as follows:
Mahdavi-Amiri and Nasseri (2006, 2007) developed a fuzzy dual simplex algorithm for fuzzy linear programming problems with fuzzy parameters. Ebrahimnejad and Nasseri (2009) then used the complementary slackness results to solve FNLPPs without the need for a simplex tableau.
Liu (2001) proposed a method for solving FNLPP based on the satisfaction (or fulfillment) degree of the constraints. He defined \(p(\tilde{a} \le \tilde{b})\) as follows.
If \(\tilde{a}\) and \(\tilde{b}\) were interval numbers, denoted by \(\tilde{a}=[a^{L}, a^{U}]\) and \(\tilde{b}=[b^{L}, b^{U}]\), then
Also, for two fuzzy numbers \(\tilde{a}\) and \(\tilde{b}\), Liu defined the fuzzy satisfaction degree using the \(\alpha \)-cut level as
It was shown that for two symmetric triangular fuzzy numbers \(\tilde{a}\) and \(\tilde{b}\), we have
Liu then considered the following problem with imprecise resources and technology coefficients:
where the \(\tilde{a}_{ij}\) are fuzzy numbers, the \(c_{i}\) are crisp coefficients of the objective function and the \(x_{i}\) are crisp decision variables. Now, following the idea of Bellman and Zadeh (1970), the fuzzy membership function of the objective function under fuzzy constraints can be obtained by solving the following two crisp linear programming problems at different \(\alpha \)-cut levels:
(1) Extreme linear programming problem with loose constraints:
(2) Extreme linear programming problem with strict constraints:
The optimal solutions of (20) and (21) constitute the bounds of the fuzzy objective value’s cut interval at level \(\alpha \) because of the fuzzy constraints. By using extension principle, the left-hand side of constraint i can be aggregated to a fuzzy value:
This involved the comparison of two fuzzy numbers, that is,
With the above considerations, Liu assigned to every constraint a minimal satisfaction level \(p_i=P(\tilde{a}_i \le \tilde{b}_i)\), obtaining the following problem:
With different values of \(\alpha \), the decision maker can decide on the preferred optimal solution and objective value between the two extremes of problems (20) and (21). Every possible value of the objective function corresponds to the optimal objective value at a certain satisfaction degree of the constraints. Liu discussed how to get the preferred optimal solution in the following three special cases.
Case 1. When the constraint coefficients are interval numbers, the desired solution can be obtained by solving the following parametric linear programming problem:
Case 2. When the constraint coefficients are symmetric triangular fuzzy numbers, Liu showed how to use the corresponding interval satisfaction degrees \(l_{\alpha }^{i}\) at \(\alpha \)-cut level to get the solution by solving the following fuzzy chance-constrained linear programming problem with interval numbers:
The above problem was then transformed into
Liu proved that the optimal solution at different \(\alpha \)-cut levels was the same.
Case 3. When the constraint coefficients are ordinary trapezoidal fuzzy numbers, the fuzzy chance programming problem is into
Now, letting \(\tilde{a}_{i1} x_1+ \tilde{a}_{i2} x_2+\cdots +\tilde{a}_{i2} x_2+ \cdots + \tilde{a}_{in}x_{n}=\tilde{a}_i=(a_{i1}(x), a_{i2}(x)\), \( a_{i3}(x),a_{i4}(x)), \tilde{b}_i=(b_{i1},b_{i2},b_{i3},b_{i4})\), we have \(\tilde{a}_i(x)-\tilde{b}_i=(a_{i1}(x)-b_{i4}, a_{i2}(x)-b_{i3}, a_{i3}(x)-b_{i2}, a_{i4}(x)-b_{i1})\). For given constraint satisfaction degrees, the fuzzy linear programming with trapezoidal fuzzy numbers can be solved with a group of crisp parametric mathematical programming problems. Liu (2001) only discussed solution methods for three special cases. For the ordinary fuzzy numbers, however, the fuzzy constrains with given satisfaction degrees cannot be transformed into symbolic inequalities. This type of a problem may be solved approximately by random search methods like genetic algorithm.
Ramik (2006) considered the fuzzy linear programming problem as follows:
where \(\tilde{c}_{j}\), \(\tilde{a}_{ij} \in F(\mathbb {R})\), \(i=1, \ldots , m\), \(j=1,2, \ldots , n\), and the fuzzy sets \(\tilde{c}_1 x_1 \tilde{+} \cdots , \tilde{+} \tilde{c}_n x_n\) and \(\tilde{a}_{i1} x_1 \tilde{+} \cdots \tilde{+} \tilde{a}_{in} x_n\) are defined by the extension of usual binary relation \( \le \) on \(\mathbb {R}\). In (23), the value \(\tilde{a}_{i1} \tilde{+} \cdots \tilde{+} \tilde{a}_{in} x_n \in F(\mathbb {R})\) is compared with a fuzzy quantity \(\tilde{b}_i \in F(\mathbb {R})\) by some fuzzy relation \(\tilde{P}\). Ramik considered \(\tilde{P}= \preceq ^{\text {Pos}}\) (see some properties of the relation in Inuiguchi et al. (1992)) and defined some indices as follows.
Let A and B be the fuzzy sets with the membership functions, \(\mu _{A}: \mathbb {R} \rightarrow [0,1]\) and \(\mu _{B}: \mathbb {R}\rightarrow [0,1]\), respectively. Let
He named \(Pos(A \preceq B)\) and \(Pos(A \prec B)\) as the possibility indices and \(Nec(A\preceq B)\) and \(Nec(A \prec B)\) as the necessity indices. Then, he alternatively obtained:
Next, Ramik defined the concept of \(\beta \)-solution as follows.
Let \(\mu _{\tilde{a}_{ij}}: \mathbb {R}\rightarrow [0,1]\) and \(\mu _{\tilde{b}_{i}}: \mathbb {R}\rightarrow [0,1]\), \(i=1, \ldots , m\) and \(j=1,2, \ldots , n\), be membership functions of fuzzy quantities \(\tilde{a}_{ij}\) and \(\tilde{b}_i\), respectively. Let \(\tilde{P}\) be a fuzzy extension of a binary relation P on \(\mathbb {R}\). A fuzzy set \(\tilde{X}\), whose membership function \(\mu _{\tilde{X}}\) is defined for all \(x \in \mathbb {R}^{n}\) by
is called the fuzzy set of feasible region or shortly feasible region of (23). For \(\beta \in (0,1]\), a vector \(x \in [\tilde{X}]_{\beta }\) is called \(\beta \)-feasible for (23). He then defined (\(\alpha \), \(\beta \))-maximal and (\(\alpha \), \(\beta \))-minimal solutions. His approach was different from the approaches of Inuiguchi et al. (2003) and Ramik and Vlach (2001). Particularly, in Inuiguchi et al. (2003) and Ramik and Vlach (2001), the authors investigated a different concept of an optimal solution of FNLPP, namely the satisficing solution. In contrast to the \(\alpha \)-efficient solution of FNLPP, which is a crisp vector, the satisficing solution is a fuzzy set. In Inuiguchi et al. (2003) and Ramik and Vlach (2001), the authors assumed the existence of exogenously given additional goals \(\tilde{d}\in F(\mathbb R)\) and \(\tilde{h}\in F(\mathbb R)\), and the fuzzy goal \(\tilde{d}\) was compared with the fuzzy value \(\tilde{z} = \tilde{c}_1 x_1 \tilde{+} \ldots \tilde{+} \tilde{c}_n x_n\) of the objective function of the primal FNLPP (P) by the fuzzy relation \(\preceq ^{Pos}\). On the other hand, the fuzzy goal \(\tilde{h}\) was compared to the fuzzy value \({{\tilde{\omega }}} = \tilde{b}_1 y_1 \tilde{+} \ldots \tilde{+} \tilde{b}_m y_m\) of the objective function of the dual of FNLPP (D) by the fuzzy relation \( \prec ^{Nec}\). This way, the fuzzy objectives were treated as constraints. Compared with the approach of Inuiguchi et al. (2003) and Ramik and Vlach (2001), the main advantage of the approach of Ramik (2006) is the removal of the need for the additional goals \(\tilde{d}\) and \(\tilde{h}\). Moreover, the investigated strong duality theorem was stronger than the corresponding results of Inuiguchi et al. (2003) and Ramik and Vlach (2001); see other work of Ramik on FNLPP in Ramik and Rommelfanger (1993). Nakahara and Gen (1993) proposed some ranking criteria of triangular fuzzy numbers, each being defined using two parameters. They showed that the proposed criteria included the criterion proposed by Dubois and Prade (1983). The authors of Nakahara and Gen (1993), based on the Dubois and Prade’s criteria, defined four ranking criteria for triangular fuzzy numbers. They considered FNLPP as follows:
where \(\tilde{c}_{j}=(c^{1}_{j},c^{2}_{j},c^{3}_{j})\), for \(j=1,2,\ldots , n\), \(\tilde{A}_{ij}=(a^{1}_{ij},a^{2}_{ij},a^{3}_{ij})\), \(j=1, \ldots ,n\), \(\tilde{B}_{i}=(b_{i}^{1},b_{i}^{2},b_{i}^{3})\), for \(i=1, \ldots ,m\). Then, they defined a method for solving fuzzy linear programming problems with triangular fuzzy number coefficients using the ranking obtained by the proposed ranking criteria. In their method, the decision maker can treat the constraint in more detail than the method using the ranking by indices of Dubois and Prade (1983).
Jimenez et al. (2007) proposed a method for solving linear programming problems where all the coefficients were fuzzy numbers in general. They considered the following linear programming problem with fuzzy parameters:
where \(\tilde{c}=(\tilde{c}_1, \ldots , \tilde{c}_{n})\), \(\tilde{A}=[\tilde{a}_{ij}]_{m \times n}\), \(\tilde{b}=(\tilde{b}_1, \ldots , \tilde{b}_m)^{T}\), respectively, represent the fuzzy parameters involved in the objective function and constraints. The possibility distribution of fuzzy parameters was assumed to be characterized by fuzzy numbers. The decision vector \(x=(x_1, \ldots ,x_{n})^T\) is assumed to be crisp. Some authors considered binary linear programming problems and introduced algorithm for generalized fuzzy binary linear programs.
Yu and Li (2001) discussed fuzzy binary linear programming problems (FBLPPs). In their work, they proposed a simple way to express a widely spread triangular fuzzy number by an absolute term, by giving the membership value of a triangular fuzzy value \(c_i\) with absolute value as follows:
where \(c_{i,1}\), \(c_{i,2}\) and \(c_{i,3}\) are, respectively, the possible lowest number, middle number and highest number and \(s_{i,1}\) and \(s_{i,2}\) are the slopes of line segments between \(c_{i,k}\) and \(c_{i,k+1}\), for \(k=1,2\) (Fig. 1) and
Then, they formulated an FBLPP as follows:
where the \(x_{j}\) are zero-one variables and the \(\tilde{c}_{i}\) are fuzzy coefficients in the objective function, the \(\tilde{a}_{ij}\) represent the fuzzy coefficient with respect to the \(x_{i}\) in the j-th constraint, and \(\tilde{b}_{j}\) denotes the fuzzy number in the right-hand side of the j-th constraint. Next, they changed problem (24) into
where \({\mu (c_i )}\) is the membership value corresponding to \(\tilde{c}_{i}\). Then, they proved that an optimal solution for (25) was a solution of the following maximization problem:
where \(w^ + _i = |\frac{1}{{s_{L_i } }}|\) and \(w^ - _i = |\frac{1}{{s_{R_i } }}|\) are the inverse of slopes for the triangular fuzzy numbers. They proposed an algorithm to treat a binary linear programming problem with fuzzy coefficients in the objective function, fuzzy coefficient in the constraint matrix and fuzzy numbers in the right-hand sides of the constraints; see an overview of the FBLPP techniques and a list of references in Carlsson and Fullér (1996), Castro et al. (1994), Herrera and Verdegay (1996), Mohanaty and Vijayaraghavan (1995), Rommelfanger et al. (1989) and Teng and Tzeng (1990).
Wu (2003) characterized the concept of fuzzy scalar (inner) product to be used in fuzzy objective and inequality constraints of the fuzzy primal problem. He considered the fuzzy primal (P) and dual (D) linear programming problems with fuzzy coefficients as follows:
and
where the coefficients in both the objective and the inequality constraint functions are taken to be fuzzy numbers. Wu defined \(\tilde{b} \succeq \tilde{a}\) (\(\tilde{b}\) and \(\tilde{a}\) are fuzzy numbers) if and only if \(\tilde{b}^{L}_{\alpha } \ge \tilde{a}^{L}_{\alpha }\) and \(\tilde{b}^{U}_{\alpha } \ge \tilde{a}^{U}_{\alpha }\) for an \(\alpha \in [0,1]\). In order to discuss the duality theorems more conveniently, Wu reformulated the primal problem (P) and the dual problem (D) using the fuzzy scalar (inner) product. Then, by using the fuzzy scalar concept, problem (P) was rewritten as follows:
where \( a_{i.}\) is the i-th row of the coefficient matrix. The dual of the primal problem is:
where \( a_{.j}\) is the j-th column of the coefficient matrix. Finally, he established weak and strong duality results based on the scalar product properties.
Furthermore, Wu (2008) proposed a solution concept by considering the orderings via \(\alpha \)-levels on the set of all fuzzy numbers. He derived the optimality conditions for linear programming problems with fuzzy coefficients and proposed a solution concept, similar to the non-dominated solution used in multi-objective programming.
Rommelfanger et al. (1989) presented a method for solving linear programming problems with fuzzy parameters in the objective function. To determine a compromise solution, the authors did not reduce the set of infinitely many objective functions as usually done in classical deterministic or stochastic procedures. Rommelfanger et al. (1989) introduced a problem that was reduced to a few extreme objective functions. The information in the membership function could be used to any extent by a method called \(\alpha \)-level-related pair formation.
Jamison and Lodwick (2001) used a penalty approach to propose a solution method. They considered the fuzzy linear programming problem,
with \(\tilde{c}\), \(\tilde{b}\) and \(\tilde{A}\) having fuzzy components. They replaced the constraints \(\tilde{A}_i x \le \tilde{b}_i,\, i=1,\ldots ,m,\) by subtracting the following penalty terms from the objective function:
where each \(\tilde{d}_i\) is a positive fuzzy number (i.e., \(\tilde{d}_{\alpha }^{-}>0, \,\, \forall \alpha \in [0,1]\)). The objective function then turns to
where \(\max \) was handled component-wise using the extension principle Kaufmann and Gupa (1986) and Klir and Yuan (1995). Jamison and Lodwick (1999) showed that \(\tilde{f}(x)\), the image at any vector x, was a fuzzy number, and it was completely characterized by its \(\alpha \)-cut:
This fuzzy number provides the possibility distribution for the outcome of taking action x. Thus, Jamison and Lodwich’s objective was to, in some sense, find the optimal fuzzy number. To do this, they adopted a view of possibility distribution as cumulative subjective probability distribution (see Jamison 2000) and assumed that their utility for a given interval was a positive value at its midpoint. Then, the optimization problem turned to:
This objective function requires the \(\alpha \)-cuts of the fuzzy number \(\tilde{f}(x)\) given the definition of expected average. But, this is straightforward given the alpha cuts of the fuzzy coefficients because of the linearity of the original problem and nonnegativity of x. Therefore,
These two numbers define the right and left points of the \(\alpha \)-cut of the fuzzy function evaluated at x, where \(\tilde{f}_{\alpha }^{+}(x)\) is called the optimistic value of \(\tilde{f}(x)\) at the possibility level \(\alpha \) and \(\tilde{f}_{\alpha }^{-}(x)\) is called the pessimistic value. The modified problem was posed as
Then, they proved some properties of this optimization problem. Jamison and Lodwick (2001) discussed the gradient ascent algorithm for solving this optimization problem. The first step of the algorithm determines whether the components of the terms \(\max (0, \tilde{A}_{\alpha }^{-}x-\tilde{b}_{\alpha }^{+})\) and \(\max (0, \tilde{A}_{\alpha }^{+}x-\tilde{b}_{\alpha }^{-})\) become active for some \(\alpha \in (0,1)\). The second step of the algorithm calculates the values of these \(\alpha \)s. The third step utilizes the calculated \(\alpha \)s to determine gradient of the objective function. This gradient is then used as the direction in which to search for the optimal value.
Chanasa and Zielińskib (2000) analyzed a linear programming problem with fuzzy coefficients in the objective function as follows:
where \(c_{j}\), \(j= 1, \ldots , n\), are fuzzy numbers. In the objective function of problem (26), they used the extended operations of the addition of fuzzy numbers and the multiplication of a fuzzy number by a scalar. Then, they defined the set of non-dominated solutions, with respect to an assumed fuzzy preference relation, according to Orlovsky’s concept (Orlovsky 1978). Special attention was paid to un-fuzzy non-dominated (UND) solutions (the solutions which are non-dominated to degree one). The main results obtained by Chanas and Zieli-Nskiare are the sufficient conditions on a fuzzy preference relation allowing for the reduction in the problem of determining the UND solutions to finding the optimal solutions of a classical linear programming problem. These solutions could thus be determined by classical linear programming methods.
Zhang et al. (2005) defined notions of subgradient, subdifferential and differential with respect to convex fuzzy extremum problem. They considered the problems of minimizing or maximizing a convex fuzzy mapping over a convex set and developed the necessary and sufficient optimality conditions. After that, they discussed the concept of saddle point and proved min–max theorems under fuzzy environment. They applied the obtained results to a fuzzy linear programming problem as follows:
where \(b \in \mathbb {R}^{m}\), \(\tilde{c}\) and \(\tilde{A}\) are, respectively, an n-dimensional fuzzy vector and an \(m \times n\) fuzzy matrix. Since \(x \ge 0\), \(f(x)=\tilde{c}^{T} x\) is both a convex and a concave fuzzy mapping and \(g(x)=\tilde{A}x-\tilde{b}\) is an m-dimensional fuzzy vector. Hence, the fuzzy programming problem is convex, with the Lagrangian function being given by
where \(\lambda =(\lambda _1, \ldots , \lambda _m)^{T}\) with \(\lambda _i \ge 0\), \(i=1, \ldots , m\). Then, they presented the (Lagrangian) dual problem of the fuzzy linear programming as follows:
where \(d(\lambda )=\min _{x \ge 0} L(x, \lambda )\). Since
we have \(d(\lambda )=-\lambda ^T\tilde{b}\), if \(\tilde{c}+\tilde{A}^{T} \lambda \ge 0\), and \(d(\lambda )=- \infty \), otherwise. Therefore, the dual problem is equivalent to
They finally established some results on duality and derived the KKT conditions for fuzzy linear programming problems.
Up to now, we have considered FNLP problems with non-stochastic parameters. The occurrence of randomness is inevitable owing to unexpected situations and has been considered in the context of stochastic optimization problems (Kall 1976; Luhandjula 2006; Prekopa 1995; Rommelfanger 2007; Stancu-Minasian 1984; Vajda 2010). Buckley (1988) restricted his attention to possibility linear programming problems with triangular fuzzy numbers; also see Zadeh (1975). He considered a mathematical programming problem, where all parameters could be fuzzy, specified by possibility distributions as follows:
where \(\tilde{A} = [\tilde{a}_{ij} ]_{m \times n},\tilde{x} = (x_1,\ldots ,x_n )^T,\tilde{b} = (\tilde{b}_1 ,\ldots ,\tilde{b}_m )^T\) and \( \tilde{c} = (\tilde{c}_1,\ldots ,\tilde{c}_n )^T\)
In this model, Buckley considered all parameters to be fuzzy numbers specified by their possibility distributions and also considered a possibility distribution for the objective function. He also assumed that all fuzzy numbers were non-interactive. Then, he proposed the method for solving this probabilistic linear programming problem. Zhong and Guang-Yuan (1993) studied the solution method of linear programming problems with fuzzy random coefficients and proposed some probability distribution functions, projective distribution functions and used expectation of these problems. In addition, they also used the theory of fuzzy random variables of Guang-Yuan and Zhong (1992), Kowakernaak (1978) and Puri and Ralescu (1986) to discuss two other types of linear programming problems with fuzzy random variable objective coefficients as follows:
They also considered a linear programming problem with fuzzy random number coefficients and decision vector \(\tilde{x}\) as follows:
where \(\tilde{x} \succeq \tilde{0}\) means \((\tilde{x}_{j})_{\alpha } \ge 0\), for \(j= 1, \ldots , n\), for any \(\alpha \in (0,1]\). Then, they established that (27) is equivalent to the following linear programming problem with random variable coefficients:
where \((\tilde{c}_j)_\alpha =[(c_{j})_{\alpha }^{-}, (c_{j})_{\alpha }^{+}]\), \(c_{\alpha }^{+}=((c_1)_{\alpha }^{+}, \ldots , (c_n)_{\alpha }^{+})^{T}\), \(c_{\alpha }^{-}=((c_1)_{\alpha }^{-}, \ldots , (c_n)_{\alpha }^{-})^{T}\). They then structured two programming problems using the coefficients of model (29) as follows:
and
Then, they established some results on the distribution problem of model (27). They transformed model (27) into a linear programming problem with random variable coefficients which might be solved by the simplex method of Guang-Yuan and Zhong (1993). Next, they deduced some results about distribution of model (28).
Maeda (2001) considered a fuzzy linear programming problem involving fuzzy numbers only for the coefficients of the objective function. The model is defined as
where \(\tilde{c} = (\tilde{c}_1,\ldots ,\tilde{c}_n)^T\), with the \(c_{i}\) being triangular fuzzy numbers, A being an \(m \times n\) matrix and \(b \in \mathbb {R}^{m}\). First, they gave a concept of an optimal solution for a fuzzy linear programming problem and investigated some properties. Then, in order to find all the optimal solutions, they made use of three types of bi-criteria optimization problems.
Van Hop (2007) adopted a model to measure the superiority and inferiority of fuzzy numbers/fuzzy stochastic variables. He made use of superiority between general fuzzy numbers \(\tilde{P}\) and \(\tilde{Q}\) as follows:
Analogously, Van Hop defined the inferiority of \(\tilde{P}\) and \(\tilde{Q}\) as
Then, he considered the superiority and inferiority between two triangular fuzzy numbers, \(\tilde{P}=(u,a,b)\) and \(\tilde{Q}=(v,c,d)\), as follows:
Next, he considered the following fuzzy linear program:
He then considered maximizing the objective function subject to superiority of right-hand sides over the left-hand sides of the constraints and the inferiority of the left-hand side to the right-hand sides. This requirement corresponded to maximizing the objective function along with penalty for any violation of superiority of right-hand side over left-hand side and inferiority of the left-hand side to the right-hand side. Then, problem (30) is reformulated as follows:
where \(p_i > 0\) and \(q_{i} >0\), for all i, are penalty coefficients. It is noticed that the penalty costs are basically determined without any rule. Next, they extended their consideration to the more general case of fuzzy objective function as follows:
An equivalent form of (32) is
which in turn is equivalent to
where the crisp variable \(\theta \) could be fuzzified as \((\theta , 0,0)\), posing (34) as a standard linear program. Then, they discussed the fuzzy stochastic linear programming problem,
where c, \(n \times 1\), is a crisp vector, \(\tilde{A} = [\tilde{a}_{ij} ]_{m \times n}\), and \(\tilde{b} = (\tilde{b}_1 ,\ldots ,\tilde{b}_m )^T\) is the fuzzy random variable constraint coefficient vector, with,
with E denoting the expected value, an equivalent corresponding to deterministic program for (35) was defined to be
Van Hop (2007) used a penalty function for violation of the constraints instead of using ranking function. The proposed method provides a simple deterministic linear programming model, which can be solved easily by a standard optimization package. Also, Chiang (2001) used statistical data and statistical confidence interval to derive (\(1-\alpha \))-level fuzzy numbers (\(0<\alpha <1\)) and obtained a fuzzy linear programming problem. He used two statistical confidence intervals to derive the (\(1-\beta \), \(1-\alpha \))-level of interval-valued fuzzy numbers (see Chiang 2001 for the definition of (\(1-\beta \), \(1-\alpha \))-level, when \(0<\beta<\alpha <1\)) and obtained an alternative fuzzy linear programming problem. More details about linear programming with random parameters can be found in Luhandjula (2007).
Farhadinia (2014) considered a fuzzy linear programming problem involving the level \((h^{L},h^{U})\)-interval-valued trapezoidal fuzzy numbers as parameters. The model is defined to be
where
with \(F_{IVTN}(h^{L},h^{U})\) being the family of all level \((h^{L},h^{U})\)-interval-valued trapezoidal fuzzy numbers. The author then made a sensitivity analysis of the problem.
Wan and Dong (2014) considered an FNLP problem with trapezoidal fuzzy numbers as
In their proposed method, the authors used trapezoidal fuzzy numbers to capture imprecise or uncertain information of the imprecise objective coefficients and/or the imprecise technological coefficients and/or available resources. An auxiliary multi-objective programming problem was constructed to solve the corresponding possibility linear programming problem with trapezoidal fuzzy numbers. The auxiliary multi-objective programming problem involved four objectives: minimizing the left spread, maximizing the right spread, maximizing the left endpoint of the mode and maximizing the middle point of the mode. Three approaches were proposed to solve the constructed auxiliary problem, including optimistic approach, pessimistic approach and linear sum approach based on membership function.
Dong and Wan (2018) considered the problem,
where X is a set of constraints which the variable x should satisfy according to some physical requirements. The authors showed (39) to be equivalent to a bi-objective problem, which was solved by their proposed goal programming approach. Then, the effectiveness of the proposed method was verified by a fuzzy knapsack problem and an investment problem.
Wan and Li (2014) developed a new Atanassov’s intuitionistic fuzzy (A-IF) programming method to solve heterogeneous multi-attribute group decision-making problems with A-IF truth degrees in which there were several types of attribute values such as A-IF sets (A-IFSs), trapezoidal fuzzy numbers, intervals and real numbers. In this method, the preference relations in comparison of alternatives with hesitancy degrees were expressed by A-IFSs. Hereby, A-IF group consistency and inconsistency indices were defined on the basis of preference relations between alternatives. To estimate the fuzzy ideal solution (IS) and weights, a new A-IF programming model was constructed on the concept that the AIF group inconsistency index should be minimized and should not be larger than the A-IF group consistency index by some fixed A-IFS. Also, Wan and Li (2015) developed a new fuzzy mathematical programming method for solving heterogeneous multi-attribute decision-making problems based on a linear programming technique for multi-dimensional analysis of preference. In this method, interval-valued intuitionistic fuzzy sets (IVIFSs), intuitionistic fuzzy sets (IFSs), trapezoidal fuzzy numbers, linguistic variables, intervals and real numbers were used to represent multiple types of attribute values. The preference relations between the alternatives given by the decision maker were expressed by IVIFSs of ordered pairs of alternatives. The consistency and inconsistency indices were defined as IVIFSs on the basis of comparisons of alternatives with IVIF truth degrees. The attribute weights and fuzzy ideal solution (FIS) were estimated through constructing a fuzzy mathematical programming model, which was solved by the technically developed method of IVIF mathematical programming.
Wan and Dong (2015) developed a novel interval-valued intuitionistic fuzzy (IVIF) mathematical programming method for hybrid multi-criteria group decision making (MCGDM) considering alternative comparisons with hesitancy degrees. The subjective preference relations between alternatives given by each decision maker (DM) were formulated as an IVIF set (IVIFS). The IVIFSs, intuitionistic fuzzy sets (IFSs), trapezoidal fuzzy numbers (TrFNs), linguistic variables, intervals and real numbers were used to represent the multiple types of criterion values. The information of the criterion weights was incomplete. The IVIFS-type consistency and inconsistency indices were defined by considering the fuzzy positive and negative ideal solutions simultaneously. To determine the criterion weights, they constructed a novel bi-objective IVIF mathematical programming problem of minimizing the inconsistency index and meanwhile maximizing the consistency index, which was solved by a technically developed linear goal programming approach.
Wan et al. (2015) formulated the logistics outsourcing provider selection as a kind of group decision-making (GDM) problem with intuitionistic fuzzy preference relations (IFPRs). A new intuitionistic fuzzy linear programming method was proposed for solving such problems. First, they constructed an intuitionistic fuzzy linear programming model to derive priority weights from the IFPRs. Depending on the construction of the non-membership functions, this intuitionistic fuzzy linear programming model was solved by three approaches including the optimistic, pessimistic and mixed approaches. Then, using TOPSIS (technique for order preference by similarity to ideal solution), the experts’ weights were determined objectively. Combining the experts’ weights with the derived priority weights, the authors presented a method for GDM with IFPRs.
Xu et al. (2016) investigated a kind of hybrid multiple attribute decision-making (MADM) problem with incomplete attribute weight information and developed a hesitant fuzzy programming method based on a linear programming technique for multi-dimensional analysis of preference (LINMAP).
See other works on FNLPP in Candenas and Jiménez (1996), Dubois and Prade (1978), Fang et al. (1999), Guang-Yuan and Zhong (1993), Guu and Wu (1999), Rommelfanger et al. (1989), Tanaka and Asai (1984a), Tanaka et al. (1984), Wan et al. (2017a), Wan et al. (2017b), Wan et al. (2018) and Zadeh (1975).
4 Fully fuzzy linear programming problems
Here, we review some methods for finding approximate solutions of fully fuzzy linear programming problems. First, we point out certain applications of fully fuzzy linear programming problems. Kim and Roush (1982) presented a theory for fuzzy flows on networks and found closed formulas giving necessary and sufficient conditions for existence of admissible flows and for the maximal admissible flow. Buckley and Jowers (2008) used such problems for generalizing the fuzzy min–max capacitated network and then solved this problem with a random method (see Chanas and Kolodziejczyk 1986; Taha 2010 for other applications in network).
A fully fuzzy linear programming problem (FFLPP) is
where \(\tilde{A} = (\tilde{a}_{ij} )_{m \times n} ,\,\,\,\,\tilde{c} = (\tilde{c}_1 ,\ldots ,\tilde{c}_n )^T ,\,\,\tilde{b} = (\tilde{b}_1 ,\ldots .,\tilde{b}_m )^T ,\,\,\tilde{x} = (\tilde{x}_1 ,\ldots ,\tilde{x}_n )\) and \(\tilde{a}_{ij} ,\,\,\tilde{b}_i ,\,\tilde{c}_j \in F(\mathbb R)\). In this model, all the variables and parameters are fuzzy numbers. Next, we want to review some methods on FFLPP.
Kumar et al. (2010) proposed a method for finding the fuzzy optimal solution of FFLP problems. They presented their model as (40) with all parameters and variables being triangular fuzzy numbers. Then, using some properties of fuzzy numbers (see Kaufmann and Gupa 1986; Liou and Wang 1992) and fuzzy arithmetic, they presented a method for solving the FFLP problems. In their method, they first converted all the inequalities into equality constraints and then substituting \(\tilde{c}=(c_j)_{1\times n}, \tilde{A}=(\tilde{a}_{ij})_{m\times n}, \tilde{x}= (\tilde{x}_j)_{n\times 1}\) and \( \tilde{b}= (\tilde{b}_i)_{m\times 1}\), they obtained the following problem:
All parameters and variables being fuzzy numbers, they rewrote (41) as follows:
where \(\otimes \) denotes a fuzzy multiplication. Finally, they changed (42) into a crisp problem by use of arithmetic operations and a ranking function. Then, they found the optimal solution of (42) by solving crisp problem.
Recently, Ganesan and Veermani (2006) introduced a type of fuzzy linear programming problem in which the elements of the coefficients, the constraints matrix and the right-hand side all being represented by symmetric trapezoidal fuzzy numbers. Nasseri et al. (2013) named this kind of problem as semi-fully fuzzy linear programming problem (SFFLPP). An SFFLPP is defined as follows:
where \(\tilde{b} \in F(\mathbb {R}^m)\), \(\tilde{c} \in F(\mathbb {R}^n)\) and \(\tilde{A} \in F(\mathbb {R}^{m \times n})\) are given and \(\tilde{x} \in F(\mathbb {R}^n)\) is to be determined. The authors first pointed out the shortcomings of primal basic feasible solutions and the dual simplex method. To alleviate the shortcomings, the authors proposed a method to determine fuzzy optimal solution of the problem and showed some advantages of the proposed method over other methods.
Kumar et al. (2011) also proposed a method for finding the fuzzy optimization solution of FFLP problems with equality constraints and compared it with the existing method of Kumar et al. (2010). However, Saberi Najafi and Edalatpanah (2013) showed the Kumar et al.’s model not to be correct, generally, and a new alternative version was provided. Kumar and Kaur (2011) proposed a method for solving FFLPP. Their method named as Mehar’s method was proposed for solving FFLP problems, and it was shown that the Mehar’s method was easier to apply as compared to the existing methods. Bhatia and Kumar (2012) showed the advantages of Mehar’s method over existing methods, some fuzzy sensitivity analysis problems which may not be solved by the existing methods were solved by using the Mehar’s method.
Kaur and Kumar (2014) formulated a fully fuzzy critical path as follows:
where \(\tilde{x}_{ij}\) is a nonnegative fuzzy number for each \( (i,j) \in A\), with A being a set of activities (i, j) and all the parameters being LR flat fuzzy numbers. The authors changed FFLPP to crisp problem by using ranking function and arithmetic operations.
Hashemi et al. (2006) considered the FFLP problem as follows:
where \(\tilde{a}_{ij}=(a_{ij}, \alpha _{ij})_{L}\), \(\tilde{b}_{i}=(b_{i}, \beta _{i})_{L}\), \(\tilde{c}_{j}=(c_{j}, \omega _{j})_{L}\) and the decision variables \(\tilde{x}_{j}=( x_{j}, \gamma _{j})\) are all symmetric fuzzy numbers. In order to obtain an optimal solution of (44), at first they determined the set of all feasible solutions that maximized the mean value of the fuzzy objective. Then, at the next phase, they minimized the standard deviation of the original fuzzy objective function subject to the set obtained at the first phase. Then, they generalized the concept of duality and appropriated the duality theory to the FFLP problem.
Hosseinzadeh Lotfi et al. (2009) considered symmetric fuzzy variables. In their work, the fuzzy triangular number was approximated by the nearest symmetric fuzzy triangular number. They considered an FFLP model as follows:
where \(\tilde{x}=(c_{\tilde{x}}, w_{\tilde{x}} ^{L}, w_{\tilde{x}}^{R})\), \(\tilde{b}=(c_{\tilde{b}}, w_{\tilde{b}} ^{L}, w_{\tilde{b}}^{R})\), \(\tilde{A}=(c_{\tilde{A}}, w_{\tilde{A}} ^{L}, w_{\tilde{A}}^{R})\), \(\tilde{c}=(c_{\tilde{c}}, w_{\tilde{c}} ^{L}, w_{\tilde{c}}^{R})\). Then, the authors reduced the above problem into two crisp linear problems. They found the optimal solution of FFLPP by using the solutions of these two problems.
Ezzati et al. (2015) considered a standard form of FFLP problem as follows:
where all fuzzy numbers were triangular fuzzy numbers. Then, based on a new lexicographic ordering, a novel algorithm was proposed to solve the FFLP problem by converting it to an equivalent multi-objective linear programming (MOLP) problem and solved it by the lexicographic method. It was shown that the lexicographic optimal solution of the MOLP problem could be considered as an optimal solution of the FFLP problem. Ezzati et al. (2015) also claimed that the fuzzy optimal solution of FFLP problems with inequality constraints can also be obtained by the same algorithm by transforming it into FFLP problems with equality constraints, but Bhardwaj and Kumar (2015) proved that the FFLP problems with inequality constraints cannot be transformed into FFLP problems with equality constraints, and hence, the algorithm, proposed by Ezzati et al. (2015) to find the fuzzy optimal solution of FFLP problems with equality constraints, cannot be used for finding the fuzzy optimal solution of FFLP problems with inequality constraints.
Kaur and Kumar (2013) proposed the product of unrestricted LR flat fuzzy numbers and then offered a method for solving FFLP problems. It was also shown that the FFLP problems which could be solved by the existing methods could also be solved by a method named Mehar’s method.
Kaur and Kumar (2012) pointed out the limitations of the method of Kumar et al. (2011) and proposed a new method to find the exact fuzzy optimal solution of the following types of problems:
(i) FFLP problems with equality constraints having nonnegative fuzzy coefficients and nonnegative fuzzy variables.
(ii) FFLP problems with equality constraints having unrestricted fuzzy coefficients and nonnegative fuzzy variables.
(iii) FFLP problems with equality constraints having nonnegative fuzzy coefficients where some or all the fuzzy variables were unrestricted.
Baykasoglu and Subulan (2017) presented a novel method based on the constrained fuzzy arithmetic concept to solve FFLP as follows:
where S and D denote the total number of sources and destinations, respectively. Moreover, \(\widetilde{Cap}_{i}\) and \(\widetilde{De}_{j}\) represent the unit transportation cost from source node i to destination node j, product availability of source i and demand of destination j, respectively. In their proposed method, the requisite crisp and/or fuzzy constraints between the base variables of the fuzzy components are provided from the decision maker according to his/her exact or vague judgments. Thereafter, fuzzy arithmetic operations are performed under these requisite constraints by taking into account the additional information while transforming the fuzzy transportation model into crisp equivalent form. Therefore, various fuzzy efficient solutions can be generated by making use of the proposed method according to the decision maker’s risk attitude. In order to present the efficiency/applicability of the proposed method, different types of fully fuzzy transportation problems were generated and solved as illustrative examples. A detailed comparative study was performed with other methods available. The computational analysis has shown that relatively more precise solutions were obtained from the proposed method for “risk-averse” and “partially risk-averse” decision makers. Their proposed method successfully provided fuzzy acceptable solutions for “risk seekers” with high degree of uncertainty similar to the other existing methods in the literature.
Baykasoglu and Subulan (2015) presented a detailed review and an analysis of the solution procedures developed for solving fully fuzzy linear programming problems with fuzzy decision variables. Furthermore, a new parametric method incorporating the decision maker’s attitude toward risk was proposed.
Zhong et al. (1994) proposed a fuzzy random programming problem with fuzzy random variable coefficients and fuzzy pseudo-random decision vector as follows:
where \(\tilde{A}=(\tilde{a}_{ij})_{m \times n}\), \(\tilde{B}=(\tilde{b}_{1}, \ldots , \tilde{b}_{m})^{T}\), \(\tilde{c}=(\tilde{c}_1, \ldots , \tilde{c}_{n})^{T}\), \(\tilde{x}=(\tilde{x}_{1}, \ldots , \tilde{x}_n)^T\), with \(\tilde{a}_{ij}\), \(\tilde{b}_i\), \(\tilde{c}_{j} \in F(\mathbb {R})\). By interpreting \(\tilde{x} \succeq \tilde{0}\) with \((\tilde{x}_{j})_{\alpha } \ge 0\), for any \(\alpha \in (0,1]\), \(j=1, \ldots , n\), the relation \(\le \) was then defined by
The authors showed that a fuzzy pseudo-random (respectively, fuzzy random) optimization solution of a fuzzy random linear programming problem might be resolved into a series of pseudo-random (respectively, random) optimization solutions of a related random linear program. They then presented methods to structure a fuzzy pseudo-random (respectively, fuzzy random) optimization solution of a fuzzy random linear program by a class of pseudo-random (respectively, random) optimization solutions of the related random linear program. Then, they established some results to solve the problems by finding the fuzzy probability distribution function and fuzzy mathematical expectation of optimization value for fuzzy random linear programs. The results revealed some properties of fuzzy random linear programs and provided a solution method. See other works of FFLP problems in Ghatee and Mehdi Hashemi (2007). We close this section by giving a summary in Table 3.
5 Heuristic algorithms for fuzzy linear programming problems
The need for solving real problems of ever greater dimensions, the impossibility of obtaining exact solutions in all cases and the need to provide appropriate approximate solutions for a host of practical cases (sequencing problems, design of routes, location, etc.) have all led to the growing use of heuristic-type algorithms as valuable tools to provide results which exact algorithms are not likely to provide. Here, we first discuss some heuristic algorithms developed for solving the corresponding crisp problems of the original fuzzy problems. We then conclude this section by a new approach for solving fuzzy problems directly, without converting them to crisp problems.
Lin (2008) proposed a genetic algorithm (GA) for solving a linear programming problem with fuzzy constraints as follows:
where \(\preceq \) stands for a fuzzified version of \(\le \), with the meaning that some constraints may be violated. The decision maker accepts small constraint violations but attaches different degrees of importance to violation of different constraints. Thus, the fuzzy constraints are defined by membership functions,
Each \(\mu _k\) gives the degree of lack of precision in the coefficient values expressed by the decision maker. Lin (2008), for the fuzzy linear programming problem (47), did not use membership functions to define fuzzy numbers \(\tilde{a}_{kj}\) and \(\tilde{b}_{k}\), \(j=1, \ldots , n\), \(k=1, \ldots , m\); nor did he use penalty costs for the constraint violations. Instead, he used a genetic algorithm (GA) to approximate fuzzy numbers for the fuzzy coefficients in the constraints. The proposed approach is described next. Let triangular fuzzy number \(\tilde{w}=(w-\varDelta _{1}, w, w+\varDelta _{2})\) (\(0 \le \varDelta _1 \le w\), \(0 \le \varDelta _2 \le w\)) be replaced by an arbitrary fuzzy set \(\tilde{W}\) in a given interval [a, b]. Then, Lin divided the interval [a, b] into t partitions as
naming \(p_{i}\) as the partition point. Let the membership grade of \(\tilde{W}\) at \(p_{i}\) be \(\tilde{W}(p_{i})=\mu _{i}\), \(i=0, \ldots ,t\), with \(\mu _{i} \in [0,1]\). Then, a discrete fuzzy set is obtained as follows:
For each coefficient in (47), the decision maker can provide some leeway in the constraints in order to perform flexible linear programming. Assume that \(\tilde{w}\) is a triangular fuzzy number or a triangular-shaped fuzzy number defined on the interval \([w-\varDelta , w+\varDelta ]\) (\(0<\varDelta <w\)). This interval is further equally divided into t partitions. Let
be the partition points and let \(\tilde{W}(p_{i})=\mu _{i} \in [0,1]\), \(i=0,1, \ldots ,t\), be the membership grades of the \(p_{i}\) in an arbitrary fuzzy set \(\tilde{W}\). Thus, we obtain a discrete fuzzy set \(\tilde{W}=(\mu _{0}, \mu _{1}, \ldots , \mu _{t})\), with each \(\mu _{i}\), \(i=0, 1, \ldots , t\), being a random number in [0, 1]. Lin finds an estimated value of w in \([w-\varDelta , w+\varDelta ]\) via GA. After computing the centroid of the fuzzy number \(\tilde{w}\) defined on the discrete fuzzy set \(\tilde{W}=(\mu _{0}, \mu _{1}, \ldots , \mu _{t})\), the estimated value \(w^{*}\) is defined to be
Lin (2008) also made use of a function \(N(x)=y\). Having membership values \(N(x_i)\), \(i=0,1, \ldots , t,\) the fuzzy function can then be defined by
and the centroid can be defined by (the fitness value of each chromosome)
Following this concept, (47) can be rewritten as follows:
The estimated value of each fuzzy coefficient \(\tilde{a_{kj}}\) is calculated to be
where \(p_{i}= a_{kj}-\varDelta +i\times \frac{2 \varDelta }{t}\), \(i=0,1, \ldots , t\), is defined on the interval \([a_{kj}-\varDelta , a_{kj}+\varDelta ]\). Similarly,
where \(p_{i}= b_{k}-\varDelta +i\times \frac{2 \varDelta }{t}\), \(i=0,1, \ldots , t\), which is defined on the interval \([b_{k}-\varDelta , b_{k}+\varDelta ]\). Note that z is used as the fitness of each chromosome in GA’s population. GA is a stochastic search technique based on the principles and mechanisms of natural genetics and selection (Goldberg 1989).
The proposed GA for solving the fuzzy linear programming problem is stated as follows (see Lin 2008):
- 1.
Generate an initial population: An initial population of size n is generated randomly from \([0,1]^{t+1}\) with each \(\mu \) according to the uniform distribution in the closed interval [0, 1]. Let the population be
$$\begin{aligned} \begin{array}{l} \tilde{W}_{h} = (\mu _{h_{0}}, \mu _{h_{1}}, \ldots , \mu _{h_{t}})=\frac{\mu _{h_{0}}}{p_0}+\frac{\mu _{h_{1}}}{p_1}+ \cdots +\frac{\mu _{h_{t}}}{p_t}, \end{array} \end{aligned}$$where \(h=1,2, \ldots , n\), \(\mu _{h_{i}}\) is a real number in [0, 1] and \(p_{i}\) is a regular partition point in a given interval, \(i=0,1,2, \ldots , t\). Each individual \(\tilde{W}_{h}\), \(h=1,2, \ldots , n\), in a population is a chromosome evaluated as follows:
$$\begin{aligned} \begin{array}{l} \mu _{\tilde{a}_{k}}(x) \left\{ \begin{array}{l} \frac{x-a_k+\varDelta _{k1}}{\varDelta _{k1}}, \quad a_k-\varDelta _{k1} \le x \le a_k\\ \frac{a_k +\varDelta _{k2}-x}{\varDelta _{k2}}, \quad a_k \le a_k + \varDelta _{k2}\\ 0, \quad \quad \quad \quad \quad O. W., \end{array} \right. \end{array} \end{aligned}$$where \(\tilde{a}_{k}=(a_k-\varDelta _{k1}, a_{k}, a_{k}+\varDelta _{k2})\), \(0 \le \varDelta _{k1} \le a_{k}\), \(0 \le \varDelta _{k2} \le a_{k}\), \(0 \le k \le n\). By using (50) and (51), the constraints are defined as follows:
$$\begin{aligned} \sum _{j=1}^{n} a_{kj}^{*}x_{j} \le b_{k}^{*}, \quad , k=1,2, \ldots , m. \end{aligned}$$ - 2.
Calculate the fitness value for each chromosome: The fitness value of each chromosome is then obtained from (49). The chromosomes in the population can be rated in terms of their fitness values. Let the total fitness value of the population be T. The cumulative fitness value (partial sum) for each chromosome \(S_{h}\), \(h= 1,2 \ldots , n\), is calculated. The intervals, \(I_{1}=[0,S_{1}]\), \(I_{j}=[S_{j-1}, S_{j}]\), \(j=2,3, \ldots , n-1\), and \(I_{n}=[S_{n-1},S_{n}]\) are constructed for the purpose of selection.
- 3.
Selection and reproduction: In the selection process, a random number \(r \in [0,T]\) is generated. Then, the new population is produced as follows:
$$\begin{aligned} {\tilde{Y}_{l=1,2,\ldots }} = {\left\{ \begin{array}{ll} \tilde{W}_1, \quad \text {if} \quad r \in I_1,\\ \tilde{W}_k, \quad \text {if} \quad r \in I_k, k = 2,\ldots ,n. \end{array}\right. } \end{aligned}$$This selection process is continued until the new population is created.
- 4.
Perform crossover: The crossover method used here is the one-point method, which randomly selects one cut point and exchanges the right parts of two parents to generate an offspring. Let p be the probability of a crossover, \(0\le p \le 1\). It is expected that on the average 80 percent of the chromosomes will undergo crossover.
- 5.
Perform mutation: Mutation resets a selected position in a chromosome to a randomly generated real number in [0, 1]. The number of selected positions for mutation in the population is related to the mutation rate. Let q be the probability of a mutation, \(0\le q \le 1\). Usually q is a very small value, around 0.003, so we expect that, on the average, 0.3 percent of the total population will undergo mutation.
Finally, the algorithm is terminated after k generations are produced. Let the final population be composed of \(\tilde{W}_{1}^{*}\), \(\tilde{W}_{2}^{*}\), \(\ldots \), \(\tilde{W}_{n}^{*}\). The maximum fitness value is the best chromosome in the population. The best chromosome represents the optimal solution for the problem. Let the best chromosome be
The estimated value of each fuzzy coefficient \(\tilde{a}_{kj}\) is calculated as
where \(p_{i}=a_{kj}-\varDelta +i \times \frac{2\varDelta }{t}\), \(i=0,1, \ldots ,t\), is defined on the interval \([a_{kj}-\varDelta , a_{kj}+\varDelta ]\). Similarly,
where \(p_i = b_{k} - \varDelta +i \times \frac{2\varDelta }{t}\), \(i=0,1, \ldots ,t\), which is defined on the interval \([b_k - \varDelta , b_k + \varDelta ]\).
Buckley and Feuring (2000) discussed a solution of the fully fuzzified linear programming (FFLP) problem as
where parameters and the variables being triangular fuzzy numbers. They first changed the problem of \(\max (\tilde{z}=(z_1/z_2/z_3))\), \(z_1< z_2 <z_3\), the fuzzy number value of the objective function, into a multiple objective problem. So, for \(\max \tilde{z}\) they have a multi-objective optimization problem as
where \(A_1\) is the area under the function in the interval \([z_1,z_2]\) and \(A_2\) is the area under the function in the interval \([z_2,z_3]\) (see Fig. 2). They used \(\sup \) and \(\inf \) because there is no guarantee that \(\max z_2\), \(\max A_2\) or \(\min A_1\) exist. Then, they discussed the method of fuzzy flexible programming to explore the denominated set for the FFLP problem. Let \(\mathbb {F}\) be the set of feasible \(\tilde{x}=(\tilde{x}_1, \ldots , \tilde{x}_n)\) for the FFLP problem. That is, \(\mathbb {F}\) contains all \(\tilde{x}\) such that \(\tilde{x} \succeq \tilde{0}\); and \(\sum _{j=1}^{n} \tilde{a}_{ij} \tilde{x}_j \preceq \tilde{b}_i\), for \(1\le i \le m\). Buckly and Feuring assumed that \(\tilde{c}_i \succeq \tilde{0}\), \(\tilde{a}_{ij} \succeq \tilde{0}\) and \(\tilde{b}_i \succeq \tilde{0}\), for all i, j, so that \(\tilde{x} \approx \tilde{0}\) (fuzzy number zero) is feasible, that is, \(\mathbb {F}\) is always non-empty. If \(\tilde{x} \in \mathbb {F}\), then they assumed that \(\tilde{z}=\sum _{i=1}^{n}\tilde{c}_i \tilde{x}_i\) is bounded, which means, there is \(M>0\) so that \(\tilde{z}\) is a fuzzy subtest of [0, M]. Let \(\sup z_2 = b_1\), \(\sup A_2=b_2\) and \(\sup A_1=b_3\), for \(\tilde{x} \in \mathbb {F}\). To change the objective on \(A_1\) to be supremum instead of infimum, set \(A^{'}_1 = b_3-A_1\). For \(\max \tilde{z}\), they then have the multi-objective problem:
They used Kerre’s and Chen’s inequalities for evaluating fuzzy numbers, which insured that the objective function \((\tilde{z})\) was bounded. Searching for an undominated solution of the FFLP problem was sufficiently complex that they employed a directed search technique as an evolutionary algorithm.
They applied the evolutionary algorithm to two classical fuzzified linear programs to show that it could produce good approximate solutions. A description of the algorithm is presented below. The main processes of the evolutionary algorithm are recombination, mutation and selection. Each element of the population is described by a set of triangular fuzzy number, \(\tilde{x}_i\), \(i=1,\ldots , n\), which is a feasible solution of the FFLP problem.
In order to minimize the computational expense, each fuzzy number was represented by three real numbers, \(r_{i0}, r_{i1}, r_{i2} \in [x_{i1},x_{i3}]\), where \(r_{i0}=x_{i1}\) and \(r_{i3}=x_{i3}\) were the limits of the support of \(\tilde{x}_i\) and \(r_{i1}\) is the central value of \(\tilde{x}_i\). In order to compute the sum and product of fuzzy numbers, \(\alpha -\)cuts for each fuzzy number were calculated. The \(\alpha -\)cuts were used to produce the corresponding sum or product. Because the sum and product of triangular fuzzy numbers might not be triangular, but instead triangular-shaped fuzzy numbers, Buckley and Feuring (2000) stored all the \(\alpha -\)cuts so that they could use triangular-shaped fuzzy numbers in further calculations. For each population member, additional value was added to represent the mutation rate. This value was self-adapted during the evolution process.
The proposed GA for solving the fuzzy linear programming problem is stated as follows:
- 1.
Generate an initial population:Buckley and Feuring (2000) supposed the population members as vectors \(\pi \in \mathbb {R}^{3n+1}\). Hence, an element of the population looks like
$$\begin{aligned} \pi = (p_0, p_1,p_2,p_3,\ldots ,p_n,\ldots ,p_{3n-3},p_{3n-2},p_{3n-1},\sigma ), \end{aligned}$$where \(\sigma \) stands for the mutation rate of the corresponding member. In the above equation, \(p_{3i+j}=r_{i+1,j}\), for \(1 \le i \le n\) and \(0 \le j \le 2\). Buckly and Feuring used a population size of 2000 elements. First, all elements of the population are randomly chosen according to the constraints. In order to get a suitable starting population, they randomly choose the central values of \(\tilde{x}_i\), \(p_{3i+1}\), close to the solution of corresponding crisp linear programming problem. A generated individual is only taken into population if it satisfies the constraints.
- 2.
Calculate the fitness value for each chromosome: After initializing, the evolution starts with the selection process. During selection, the fitness of the individual is computed. The fitness of an individual is given by the objective function
$$\begin{aligned} G(z_2,A_2,{A_1^{'}})=\bar{G}_1(z_2)\bar{G}_2(A_2)\bar{G}_1({A_1^{'}}), \end{aligned}$$so that if \(0\le c_1 <b_1\), then
$$\begin{aligned} \bar{G}_1(z_2)= \left\{ \begin{array}{l} 0, \quad \quad \quad \quad \quad \quad \quad \quad \quad \,\,\, z_2<c_1,\\ 0.1+0.9(\frac{z_2-c_1}{b_1-c_1}), \quad \quad c_1 \le z_2\le b_1,\\ 1, \quad \quad \quad \quad \quad \quad \quad \quad \quad \,\,\, z_2 \ge b_1, \end{array} \right. \end{aligned}$$if \(0\le c_2 <b_2\), then
$$\begin{aligned} \bar{G}_1(A_2)= \left\{ \begin{array}{l} 0, \quad \quad \quad \quad \quad \quad \quad \quad \quad \,\, A_2<c_2,\\ 0.1+0.9(\frac{A_2-c_2}{b_2-c_2}), \quad \,\, c_2 \le A_2\le b_2,\\ 1,\quad \quad \quad \quad \quad \quad \quad \quad \quad \,\, A_2 \ge b_2, \end{array} \right. \end{aligned}$$if \(0\le c_3 <b_3\), then
$$\begin{aligned} \bar{G}_1(A_2)= \left\{ \begin{array}{l} 0, \quad \quad \quad \quad \quad \quad \quad \quad \quad \,\, {A_1^{'}}<c_3,\\ 0.1+0.9(\frac{{A_1^{'}}-c_3}{b_3-c_3}),\quad c_2 \le c_3\le b_3,\\ 1,\quad \quad \quad \quad \quad \quad \quad \quad \quad \,\, {A_1^{'}} \ge b_3. \end{array} \right. \end{aligned}$$ - 3.
Selection and reproduction: Selection is deterministic. In evolution strategies, the \(\mu =300\) fittest individuals are chosen to build the offspring of the next generation by using recombination and mutation.
- 4.
Perform crossover: The recombination process builds a temporary generation by applying a crossover operator to the \(\mu \) fittest members of the previous generation. For each individual of the temporary generation, two parents \(\pi ^{old_1}\) and \(\pi ^{old_2}\) are randomly chosen from the \(\mu \) fittest elements of the previous generation (for details, see Buckley and Feuring 2000).
- 5.
Perform mutation: The mutation process generates the new generation by randomly changing the members.
The process continues until the fitness of a population member is greater than a positive value or a user-defined number of generations is reached.
Wang (1997) considered a linear programming problem with fuzzy resources and crisp objective function as follows:
where \(x \in \mathbb {R}^{n}\) is the decision vector, \(A \in \mathbb {R}^{m \times n}\), \(c \in \mathbb {R}^{n}\) are crisp constraint matrix and objective vector, and \(\tilde{b}\) is the fuzzy resource vector. The constraint matrix A can be written as
where \(A_{i}^{T}\) is the i-th row of matrix A, for \(i=1,2, \ldots , m\). Assuming the decision maker desires the objective values to be fuzzy, and the membership functions of the objective function and constraints are non-decreasing continuous linear functions, let \(p_0\) and \(p_i\) be the tolerances of the objective function and the i-th resource constraint. Then, the membership functions can be described as follows. For the objective function, they defined:
and for the i-th resource constraint, \(i=1,2, \ldots ,m\), they considered:
The problem was then rewritten as:
Generally, a unique optimal solution \((x^{*}, \alpha ^{*})\) can be found by solving the crisp linear programming problem (54) using the simplex method. Let \(x^{*}\) be the solution with the highest membership degree to the fuzzy programming problem (53). This means that the best balance of the objective and constraints has been achieved by the optimal solution \(x^{*}\). However , the membership function usually is not the preference function of the decision maker. It is possible that the unique \(x^{*}\) is not desired by the decision maker. On the other hand, a unique exact optimal solution is meaningless for a fuzzy programming problem, because the original data to be used for the calculation are imprecise or vague. Wang (1997) proposed the concept of fuzzy optimal solution of (53) instead of a unique optimal solution as follows:
where \((\mathbb {R}^{n})^{+}\) is the nonnegative n-dimensional space. Wang proved that the fuzzy optimal solution of (53) is a convex fuzzy set. This is a fundamental result for the inexact approach to linear programming problems with fuzzy objective and resources. The linear programming problem (54) is equivalent to the following optimization problem:
The optimization problem (55) can be rewritten as
This is an unconstrained \(\max --\min \) optimization problem, but its objective function is not continuously differentiable. Thus, it cannot be solved by traditional optimization methods, and a genetic algorithm (GA) may be applied. Wang (1997) took the membership function of fuzzy optimal solution, \(\mu _{\tilde{S}}(x) \in [0,1]\), to be the fitness function of the recommended GA. For a GA, the larger the fitness value, the higher the probability to produce children. Thus, the individuals with higher membership degrees have more chances to reproduce children. The remaining task is how to design the mutation operator to generate children more fit than their parents. Wang (1997) recommended the mutation operator along the weighted gradient direction. The weighted gradient of \(\mu _{\tilde{S}} (x)\) can be given as follows:
where \(w_0\), and \(w_i\), \(i=1,2, \ldots , m\), are, respectively, the weights of the objective function and the i-th constraint. Let \(\mu _{\min } = \min \{\mu _0(x), \mu _{i}(x), i=1,2, \ldots ,m\}\). Then,
where \(\sigma \) is a sufficiently small positive number.
The proposed inexact approach for fuzzy linear programming problem of the objective fuzzy type can find a family of preferred solutions which give more candidates than exact solutions. The GA used in this approach takes the mutation along the weighted gradient direction as a genetic operator. It can lead most points to the fuzzy optimal solution quickly. The points in dead area would be eliminated by the proportion selection strategy. The human–computer interaction in this approach is useful for the decision maker to find the most preferred solution.
The procedure of the approach can be described as follows:
- 1.
Generate an initial population: The basic idea is to produce a number of individuals in \((\mathbb {R}^n)^{+}\) randomly.
- 2.
Calculate the fitness value for each chromosome: For individual j, \(j=1,\ldots , N\), calculate its fitness value F(j) and selection probability P(j) by
$$\begin{aligned} F(j)=\mu _{\tilde{S}}(x(j))+\epsilon , \quad \quad P(j) = \frac{F(j)}{\sum _{i=1}^{N} F(i)}, \end{aligned}$$where \(\epsilon \) is a small positive number (usually, \(\epsilon =10^{-8}\)); it is used to guarantee a nonzero denominator.
- 3.
Selection and reproduction: The selection process begins with spinning of the roulette wheel N times.
- 4.
Perform crossover: For each individual of the temporary generation, two parents are randomly chosen from the previous generation.
- 5.
Perform mutation: The mutation process generates the new generation by
$$\begin{aligned} {x_j^{k}} = {x_j^{k-1}}+\theta G(x(i)), \end{aligned}$$where G(x(i)) is the weighted gradient direction (57), i is a selected index, \(\theta \) is the step length generated by a random number generator and k is the number of iterations.
The process continues until a user-defined number of generations is reached. Wang (1997), instead of finding an exact optimal solution, used a genetic algorithm with mutation along the weighted gradient direction to find a family of inexact solutions with acceptable membership degrees. By means of the human–computer interaction, the solution preferred by the decision maker can be achieved by a convex combination of the solutions selected from the family. Finally, Wang implemented this algorithm and tested the program on some examples.
Ribeiro and Pires (1999) considered an FNLP problem with the concept of fuzzy goal and fuzzy constraints first introduced by Bellman and Zadeh (1970) considering symmetry between the objective function and the constraints. Bellman and Zadeh stated that a fuzzy decision can be viewed as the intersection of fuzzy goal and the problem constraints since they were all defined as fuzzy sets in the space of alternatives. The optimal decision is a point at which the intersection of fuzzy goal and constraints takes the maximum membership value. The method is usually called the max–min approach. The maximum model of the fuzzy problem is:
where \(\mu _{k}(x)\) is the k-th membership value of the goals or constraint satisfactions. Note that in Bellman and Zadeh’s model (Bellman and Zadeh 1970), there is no difference between the objectives and constraints. Ribeiro and Pires (1999) used a simulated annealing (SA) algorithm for solving the max–min problem. According to Kirkpatrick et al. (1984), the four basic requirements for using an SA algorithm for combinatorial optimization problems are:
- 1.
Concise description of the problem.
- 2.
Random generation of the changes from one configuration to another.
- 3.
An objective function containing the utility function of the trade-offs.
- 4.
The initial state, the number of iterations to be performed at each temperature and its annealing scheme (for a detailed discussions of the algorithm, see Eglese 1990; Kirkpatrick et al. 1984).
Ribeiro and Pires (1999) developed two implementations of the SA algorithm, one maximizing the aggregation of the tolerance intervals (membership values of the goals and constraints), i.e., the fuzzification of both the objective and constraints, and the other only handling the fuzzification of constraints. The objective of the first implementation of the SA algorithm was to solve a maximization problem by maximizing the aggregation of the membership values of the goals and constraints (Zimmermann 1978). The membership functions of the fuzzy goal and constraints used in the two implementations were triangular. For example, for the case \(\preceq \), the membership function is defined to be
where \(R_{k}(x)= \sum _{j} a_{kj}x_{j}\) or \(\sum _{j} g_{j}x_{j}\) (the \(a_{kj}\) are coefficients of the constraints \(k=1, \ldots , m\), \(j=1,\ldots , n\), the \(g_j\) are the coefficients of the objective function and \(c_k, \,\, k=1,\ldots , m\), are the right-hand sides of the constraints), and the \(d_{k}\) are the deviations from the crisp values. Ribeiro and Pires (1999) first solved the crisp problem with both the simplex algorithm and SA. The results obtained for the objective function were the same, though with different solutions for the variables because there were multiple solutions for the crisp problem. Second, they tested the fuzzy Zimmermann’s approach (Zimmermann 2001) with the fuzzy SA approach. The fuzzy results obtained for the max–min approach with the SA algorithm were also equivalent to the ones obtained by Zimmermann’s method.
Liu (2001) presented a new concept of chance of fuzzy random events and then constructed a general framework for fuzzy random chance-constrained programming problems. He also designed a spectrum of fuzzy random simulation for computing uncertain functions arising in fuzzy random programming. To speed up the process of handling uncertain functions, Liu trained a neural network to approximate uncertain functions based on the training data generated by fuzzy random simulation. He also integrated fuzzy random simulation, neural network, and a genetic algorithm to produce a more powerful and effective hybrid intelligent algorithm for solving fuzzy random programming models.
In the reviewed methods so far, we saw fuzzy optimization problems converted to crisp problems, but at times it may be appropriate to solve the fuzzy optimization problems directly. Ghanbari et al. (2018) modified Kerre’s method for comparison of LR fuzzy numbers. They gave some new results for comparison of LR fuzzy numbers and showed how to compare two LR fuzzy numbers, without computing the fuzzy maximum of the two numbers directly. Using the modified Kerre’s method, they proposed a new variable neighborhood search (VNS) algorithm for solving fuzzy number linear programming problems. In their algorithm, a local search is made based on descent directions, which are found by four incurring mathematical programming problems.
Other approaches for solving fuzzy linear programming problems by heuristic algorithms can be seen in Buckley et al. (1999), Buckley (1995), Guu and Wu (2017), Tanaka and Asai (1984b), Wang and Liang (2004) and Zhang et al. (2018).
6 Conclusion
In the conventional linear programming problems, it is assumed that the parameters of the problem are exactly known, but there may be some situations in formulating real-life problems where variables and parameters may not be known precisely.
Here, we provided a survey of the models, methods and algorithms for fuzzy linear programming problems (FLPPs) along with promising research directions. Being a survey, our work included many references to help readers obtain more detailed information on issues of interest. First, we tried FLPPs with fuzzy decision variables. Most methods were based on different ranking functions and \(\alpha \)-cuts. One bug of ranking functions is that any two numbers \(\tilde{A}=(a,\alpha ,\beta )\) and \(\tilde{A}'=(a,\alpha +\gamma ,\beta +\gamma )\), for any \(\gamma \), will have the same rank and thus are considered to be equal, meaning that the appropriateness of the method may not generally be justified. Another bug of these methods is that authors convert fuzzy linear programming problems to crisp problems, and thus, they effectively change the underlying environment for solving the problems. Then, we explored the FLPPs with fuzzy parameters (fuzzy numbers in the objective function and in the definitions of constraints) in three parts. First, we reviewed some methods based on ranking functions. Next, we considered problems formulated by fuzzy functions using the extension principle. After that, making use of the scalar product definition to define left and right spreads in fuzzy vectors, we discussed a method based on \(\alpha \)-levels and penalty methods. In these methods, authors also change the fuzzy linear programming problems to crisp problems.
Next, we investigated the FLPPs with fuzzy variables and parameters. These types of FLPPs were solved by using approximation methods and some methods based on \(\alpha \) levels. Finally, we discussed some heuristic methods, like genetic, simulated annealing and variable neighborhood search algorithms for solving different models of fuzzy linear programming problems. The considered models by some authors were the equivalent crisp problems, while a recent approach solved the fuzzy problems directly.
As interesting areas of further research on fuzzy optimization, we point out the followings: investigating the possibility of developing duality results for direct (not crisp) fuzzy linear programming models, investigation of various heuristic methods and their possible effectiveness on various types of fuzzy optimization problems, development of various direct methods along with methods of fuzzy comparison, extensive and comprehensive comparisons of the various fuzzy optimization techniques based on acceptable benchmarks, characterization of optimal solutions of fuzzy nonlinear optimization problems and development of numerical methods (iterative algorithms).
References
Abboud N, Inuiguchi M, Sakawa M, Uemura Y (1998) Manpower allocation using genetic annealing. Eur J Oper Res 111:405–420
Aliev RA, Fazlollahi B, Guirimov BG, Aliev RR (2007) Fuzzy genetic approach to aggregate production distribution planning in supply chain management. Inf Sci 177:4241–4255
Alizadeh Sigarpich L, Allahviranloo T, Hosseinzadeh Lotfi F, Aftab Kiani N (2011) Degeneracy in fuzzy linear programming and its application. Int J Uncertain Fuzziness Knowl Based Syst 19:999–1012
Baykasoglu A, Gocken T (2012) A direct solution approach to fuzzy mathematical programs with fuzzy decision variables. Expert Syst Appl 39:1972–1978
Baykasoglu A, Subulan K (2015) An analysis of fully fuzzy linear programming with fuzzy decision variables through logistics network design problem. Knowl Based Syst 90:165–184
Baykasoglu A, Subulan K (2017) Constrained fuzzy arithmetic approach to fuzzy transportation problems with fuzzy decision variables. Expert Systh Appl 81:193–222
Bazaraa MS, Jarvis JJ, Sherali HD (2009) Linear programming and network flow, 4th edn. Wiley, New York
Bector CR, Chandra S, Vijay V (2004) Duality in linear programming with fuzzy parameters and matrix games with fuzzy pay-offs. Fuzzy Sets Syst 146:253–269
Bellman RE, Zadeh LA (1970) Decision making in a fuzzy environment. Manag Sci 17:141–164
Bhardwaj B, Kumar A (2015) A note on a new algorithm to solve fully fuzzy linear programming problems using the molp problem. Appl Math Model 39:5982–5985
Bhatia N, Kumar A (2012) Mehar’s method for solving fuzzy sensitivity analysis problems with LR flat fuzzy numbers. Appl Math Model 36:4087–4095
Bilgen B (2010) Supply chain network modeling in a golf club industry via fuzzy linear programming approach. J Intell Fuzzy Syst Appl Eng Technol 21:243–253
Buckley JJ, Jowers L (2008) Monte Carlo methods in fuzzy optimization. Stud Fuzziness Soft Comput
Buckley JJ (1988) Possibilistic linear programming with triangular fuzzy numbers. Fuzzy Sets Syst 26:135–138
Buckley JJ (1995) Joint solution to fuzzy programming problems. Fuzzy Sets Syst 72:215–220
Buckley JJ, Feuring T (2000) Evolutionary algorithm solution to fuzzy problems: fuzzy linear programming. Fuzzy Sets Syst 109:35–53
Buckley JJ, Feuring T, Hayashi Y (1999) Neural net solutions to fuzzy linear programming. Fuzzy Sets Syst 106:99–111
Buckley JJ, Eslami E, Feuring T (2002) Fuzzy mathematics in economics and engineering. Studies in fuzziness and soft computing. Physica-Velag, Berlin
Campos L, Verdegay JL (1989) Linear programming problems and ranking of fuzzy numbers. Fuzzy Sets Syst 32:1–11
Candenas JM, Jiménez F (1996) A dual approach in fuzzy linear programming. Mathw Soft Comput 3:383–394
Carlsson C, Fullér R (1996) Fuzzy multiple criteria decision making: recent development. Fuzzy Sets Syst 78:139–153
Castro JL, Herrera F, Verdegay JL (1994) Knowledge-based systems and fuzzy boolean programming. Int J Intell Syst 9:211–225
Chanas S (1983) The use of parametric programming in fuzzy linear programming. Fuzzy Sets Syst 11:243–251
Chanas S, Kolodziejczyk W (1982) Maximum flows on network with fuzzy arc capacities. Fuzzy Sets Syst 8:165–173
Chanas S, Kolodziejczyk W (1984) Real-valued flows in a network with fuzzy arc capacities. Fuzzy Sets Syst 13:139–151
Chanas S, Kolodziejczyk W (1986) Integer flows in network with fuzzy capacity constraints. Networks 16:17–31
Chanas S, Kuchta D (1996) A concept of the optimal solution of the transportation problem with fuzzy cost coefficients. Fuzzy Sets Syst 82:299–305
Chanas S, Kuchta D (1998) Fuzzy integer transportation problem. Fuzzy Sets Syst 98:291–298
Chanasa S, Zielińskib P (2000) On the equivalence of two optimization methods for fuzzy linear programming problems. Eur J Oper Res 121:56–63
Chang NB, Wen CG, Chen YL (1997) A fuzzy multi-objective programming approach for optimal management of the reservoir watershed. Eur J Oper Res 99:289–302
Chen CK, Lin JM (2001) A multi-objective fuzzy optimization for optimum dimensions design of a convective spine. Int Commun Heat Mass Transf 28:67–76
Chen YW, Tzeng GH (2000) Fuzzy multi-objective approach to the supply chain model. Int J Fuzzy Syst 2:220–228
Chiang J (2001) Fuzzy linear programming based on statistical confidence interval and interval-valued fuzzy set. Eur J Oper Res 129:65–86
Cornelis C, Dekesel P, Kerre EE (2004) Shortest paths in fuzzy weighted graphs. Int J Intell Syst 19:1051–1068
Dantzing GB (1998) Linear programming and extentions. Princeton University Press, Princeton
Darzentas J (1987) On fuzzy location models. In: Orlovski SA, Kacprzyk J (eds) Optimization models using fuzzy sets and possibility theory, vol 4. Springer, New York, pp 328–341
Dong JY, Wan SP (2018) A new trapezoidal fuzzy linear programming method considering the acceptance degree of fuzzy constraints violated. Knowl Based Syst 148:100–114
Dubois D, Prade H (1978) Operation on fuzzy numbers. Int J Syst Sci 9:613–626
Dubois D, Prade H (1983) Ranking fuzzy numbers in the setting of possibility theory. Inf Sci 30:183–224
Ebrahimnejad A (2011) Sensitivity analysis in fuzzy number linear programming problems. Math Comput Model 53:1878–1888
Ebrahimnejad A, Nasseri SH (2009) Using complementary slackness property to solve linear programming with fuzzy parameters. Fuzzy Inf Eng 1:233–245
Ebrahimnejad A, Tavana M (2014) A novel method for solving linear programming problems with symmetric trapezoidal fuzzy numbers. Appl Math Model 38:4388–4395
Ebrahimnejad A, Tavana M (2014) A simplified new approach for solving fuzzy transportation problems with generalized trapezoidal fuzzy numbers. Appl Soft Comput 19:171–176
Ebrahimnejad A, Nasseri SH, Lotfi FH (2010) Bounded linear programming with trapezoidal fuzzy numbers. Int J Uncertain Fuzziness Knowl Based Syst 18:269–286
Ebrahimnejad A, Nasseri SH, Mansourzadeh SM (2011) Bounded primal simplex algorithm for bounded linear programming with fuzzy cost coefficients. Int J Oper Res Inf Syst 2:96–120
Eglese RW (1990) Simulated annealing: a tool for operational research. Eur J Oper Res 46:271–281
Ezzati R, Khorram E, Enayati R (2015) A new algorithm to solve fully fuzzy linear programming problems using the MOLP problem. Appl Math Model 39:3183–3193
Fang SC, Hu CF, Wang H, Wu AY (1999) Linear programming with fuzzy coefficients in constraints. Comput Math Appl 37:63–76
Farhadinia B (2014) Sensitivity analysis in interval-valued trapezoidal fuzzy number linear programming problems. Appl Math Model 38:50–62
Fortemps P, Roubens M (1996) Ranking and defuzzification method based on area compensation. Fuzzy Sets Syst 82:319–330
Ganesan K, Veermani P (2006) Fuzzy linear programs with trapezoidal fuzzy numbers. Ann Oper Res 143:305–315
Ghanbari R, Ghorbani-Moghadam Kh, Mahdavi-Amiri N (2018) A variable neighborhood search algorithm for solving fuzzy number linear programming problems using modified kerre’s method. IEEE Trans Fuzzy Syst. https://doi.org/10.1109/TFUZZ.2018.2876690
Ghatee M, Mehdi Hashemi S (2007) Ranking function-based solutions of fully fuzzified minimal cost flow problem. Inf Sci 177:4271–4294
Goldberg DE (1989) Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, Boston
Guang-Yuan W, Zhong Q (1992) The theory of fuzzy stochastic processes. Fuzzy Sets Syst 51:161–178
Guang-Yuan W, Zhong Q (1993) Linear programming with fuzzy random variable coefficients. Fuzzy Sets Syst 57:295–311
Guu SM, Wu YK (1999) Two-phase approach for solving the fuzzy linear programming problems. Fuzzy Sets Syst 107:191–195
Guu SM, Wu YK (2017) A linear programming approach for minimizing a linear function subject to fuzzy relational inequalities with addition min composition. IEEE Trans Fuzzy Syst 25:985–992
Hashemi SM, Modarres M, Nasrabadi E, Nasrabadi MM (2006) Fully fuzzified linear programming solution and duality. J Intell Fuzzy Syst 17:253–261
Hernades F, Lamata MT, Takahashi MT, Verdegay JL (2007) An algorithm for the fuzzy maximum flow problem. In: IEEE international fuzzy systems conference, pp 1–6
Herrera F, Verdegay JL (1996) Fuzzy boolean programming problems with fuzzy costs: a general study. Fuzzy Sets Syst 81:57–76
Hillier FS (2010) Introduction to operations research. McGraw-Hill, New York
Hosseinzadeh Lotfi F, Allahviranloo T, Alimardani Jondabeh M, Alizadehloo L (2009) Solving a fully fuzzy linear programming using lexicography method and fuzzy approximate solution. Appl Math Model 33:3151–3156
Hsu HM, Wang WP (2001) Possibilistic programming in production planning of assemble-to-order environments. Fuzzy Sets Syst 119:59–70
Inuiguchi M, Ichihashi H, Kume Y (1992) Some properties of extended fuzzy preference relations using modalities. Inf Sci 61:187–209
Inuiguchi M, Ramik J, Tanino T, Vlach M (2003) Satisficing solutions and duality in interval and fuzzy linear programming. Fuzzy Sets Syst 135:151–177
Jamison KD (2000) Possibilities as cumulative subjective probabilities and a norm on the space of congruence classes of fuzzy numbers motivated by an expected utility functional. Fuzzy Sets Syst 111:331–339
Jamison KD, Lodwick WA (1999) Minimizing unconstrained fuzzy functions. Fuzzy Sets Syst 103:457–464
Jamison KD, Lodwick WA (2001) Fuzzy linear programming using a penalty method. Fuzzy Sets Syst 119:97–110
Jimenez M, Arenas M, Bilbao A, Rodriguez MV (2007) Linear programming with fuzzy parameters: an interactive method resolution. Eur J Oper Res 177:1599–1609
Kall P (1976) Stochastic linear programming. Springer, New York
Kara Y, Pakosy T, Chang CT (2009) Binary fuzzy goal programming approach to single model straight and u-shaped assembly line balancing. Eur J Oper Res 195:335–347
Karakas E, Koyuncu M, Erol R, Kokangul A (2010) Fuzzy programming for optimal product mix decision based on expanded ABC approach. Int J Prod Res 48:729–744
Katchian LG (1980) A polynomial algorithm in linear programming. USSR Comput Math Math Phys 20:53–72
Kaufmann A, Gupa MM (1986) Introduction to fuzzy arithmatic: theory and application. Math Comput 47:762–763
Kaur J, Kumar A (2012) Exact fuzzy optimal solution of fully fuzzy linear programming problems with unrestricted fuzzy variables. Appl Intell 37:145–154
Kaur J, Kumar A (2013) Mehar’s method for solving fully fuzzy programming problems with L-R fuzzy parameters. Appl Math Model 37:7142–7153
Kaur P, Kumar A (2014) Linear programming approach for solving fuzzy critical path problems with fuzzy parameters. Appl Soft Comput 21:309–319
Kim K, Roush F (1982) Fuzzy flow on network. Fuzzy Sets Syst 8:35–38
Kirkpatrick S, Gelatt CD, Vecchi MP (1984) Optimization by simulated annealing. Science N Ser 220:671–680
Klir GJ, Yuan B (1995) Fuzzy sets and fuzzy logic: theory and applications, 1st edn. Prentice Hall, Upper Saddle River
Kowakernaak H (1978) Fuzzy random variables-I. Definitions and theorems. Inf Sci 15:1–29
Kumar A, Kaur A (2011) A new method for solving fuzzy linear programs with trapezoidal fuzzy numbers. J Fuzzy Set Valued Anal 2011:1–12
Kumar A, Kaur M (2011) Solution of fuzzy maximal flow problems using fuzzy linear programming. World Acad Sci Eng Technol 54:15–19
Kumar A, Kaur J, Singh P (2010) Fuzzy optimal solution of fully fuzzy linear programming problems with inequality constraints. Int J Appl Math Comput Sci 6:37–41
Kumar A, Kaur J, Singh P (2011) A new method for solving fully fuzzy linear programming problems. Appl Math Model 35:817–823
Lai YJ, Hwang CL (1992) Fuzzy mathematical programming: methods and applications. Springer, New York
Lai YJ, Hwang CL (1994) Fuzzy multiple objective decision making. In: Lai YJ, Hwang CL (eds) Fuzzy multiple objective decision making, 1st edn. Springer, Berlin
Lai KK, Li L (1999) A dynamic approach to multiple-objective resource allocation problem. Eur J Oper Res 117:293–309
Leon T, Liern V, Vercher E (2002) Viability of infeasible portfolio selection problems: a fuzzy approach. Eur J Oper Res 139:178–189
Leung Y (1988) Interregional equilibrium and fuzzy linear programming. Environ Plan A 20:219–230
Li YP, Huang GH, Guo P, Nie SL (2010) Interval-fuzzy possibilistic mixed integer linear programming for environmental management under uncertainty. Int J Environ Pollut 42:93–102
Lin FT (2008) A genetic algorithm for linear programming with fuzzy constraints. J Inf Sci Eng 24:801–817
Liou TS, Wang MJ (1992) Ranking fuzzy numbers with integral value. Fuzzy Sets Syst 50:247–255
Liu B (2001) Fuzzy random chance-constrained programming. IEEE Trans Fuzzy Syst 9:713–720
Liu X (2001) Measuring the satisfaction of constraints in fuzzy linear programming. Fuzzy Sets Syst 122:263–275
Liu ST, Kao C (2004) Network flow problems with fuzzy arc lengths. IEEE Trans Syst Man Cybern 34:765–769
Luhandjula MK (2006) Fuzzy stochastic linear programming: survey and future research directions. Eur J Oper Res 174:1353–1367
Luhandjula MK (2007) Fuzzy mathematical programming: theory. Appl Ext J Uncertain Syst 1:124–136
Maeda T (2001) Fuzzy linear programming problems as bi-criteria optimization problems. Appl Math Comput 120:109–121
Mahdavi I, Mahdi-Paydar MM, Solimanpur M (2011) Solving a new mathematical model for cellular manufacturing system: a fuzzy goal programming approach. Iran J Oper Res 2:35–47
Mahdavi-Amiri N, Nasseri SH (2006) Duality in fuzzy number linear programming by use of certain linear ranking function. Appl Math Comput 180:206–216
Mahdavi-Amiri N, Nasseri SH (2007) Duality results and a dual simplex method for linear programming problems with trapezoidal fuzzy variables. Fuzzy Sets Syst 158:1961–1978
Mahdavi-Amiri N, Nasseri SH, Yazdani A (2009) Fuzzy primal simplex algorithm for solving fuzzy linear programming problems. Iran J Oper Res 1:68–84
Maleki HR (2002) Ranking function and their applications to fuzzy linear programming. Far East J Math Sci 4:283–301
Maleki HR, Tata M, Mashinchi M (2000) Linear programming with fuzzy variables. Fuzzy Sets Syst 109:21–33
Mohanaty BK, Vijayaraghavan TAS (1995) A multi-objective programming problem and its equivalent goal programming problem with appropriate priorities and aspiration levels: a fuzzy approach. Comput Oper Res 22:771–778
Mondal S, Maiti M (2003) Multi-item fuzzy EOQ models using genetic algorithm. Comput Ind Eng 44:105–117
Nakahara Y, Gen M (1993) A method for solving linear programming problems with triangular fuzzy coefficients using new ranking index. Comput Ind Eng 25:1–4
Nasseri SH (2008) A new method for solving fuzzy linear programming by solving linear programming. Appl Math Sci 2:2473–2480
Nasseri SH, Ebrahimnejad A (2010) A fuzzy dual simplex method for fuzzy number linear programming problem. Adv Fuzzy Sets Syst 5:81–95
Nasseri SH, Mahdavi-Amiri N (2009) Some duality results on linear programming problems with symmetric fuzzy numbers. Fuzzy Inf Eng 1:59–66
Nasseri SH, Ebrahimnejad A, Mizuno S (2010) Duality in fuzzy linear programming with symmetric trapezoidal numbers. Appl Appl Math Int J 5:1469–1484
Nasseri SH, Chameh R, Behmanesh E (2013) Some new results on semi fully fuzzy linear programming problems. Casp J Math Sci 2:137–146
Nguyen HT, Walker EA (2000) A first course in fuzzy logic. Chapman and Hall, London
Orlovsky SA (1978) Decision-making with a fuzzy preference relation. Fuzzy Sets Syst 1:157–167
Pandian P, Jayalakshmi M (2010) A new method for solving integer linear programming problems with fuzzy variables. Appl Math Sci 4:997–1004
Prekopa A (1995) Stochastic programming. Springer, New York
Puri ML, Ralescu DA (1986) Fuzzy random variables. J Math Anal Appl 114:409–422
Ramik J (2006) Duality in fuzzy linear programming with possibility and necessity relations. Fuzzy Sets Syst 157:1283–1302
Ramik J, Rimanek J (1985) Inequality relation between fuzzy numbers and its use in fuzzy optimization. Fuzzy Sets Syst 16:123–138
Ramik J, Rommelfanger H (1993) A single and a multi-valued order on fuzzy numbers and its use in linear programming with fuzzy coefficients. Fuzzy Sets Syst 57:203–208
Ramik J, Vlach M (2001) Generalized concavity in fuzzy optimization and decision analysis, 1st edn. Springer, New York
Ribeiro RA, Pires FM (1999) Fuzzy linear programming via simulated annealing. Kybernetika 35:57–67
Rommelfanger H (2004) The advantages of fuzzy optimization models in practical use. Fuzzy Optim Decis Mak 3:295–309
Rommelfanger H (2006) Application of fuzzy linear programming to transportation planning decision problems with multiple fuzzy goals. J Colloid Interface Sci 3:311–316
Rommelfanger H (2007) A general concept for solving linear multi-criteria programming problems with crisp, fuzzy or stochastic values. Fuzzy Sets Syst 158:1892–1904
Rommelfanger H, Hanuscheck R, Wolf J (1989) Linear programming with fuzzy objectives. Fuzzy Sets Syst 29:31–48
Rommelfanger H, Verdegay JL, Vila MA (1989) A general model for fuzzy linear programming. Fuzzy Sets Syst 29:21–29
Roy TK, Maiti M (1997) A fuzzy EOQ model with demand-dependent unit cost under limited storage capacity. Eur J Oper Res 99:425–432
Roy TK, Maiti M (1998) Multi-objective inventory models of deteriorating items with some constraints in a fuzzy environment. Comput Oper Res 25:1085–1095
Saberi Najafi H, Edalatpanah SA (2013) A note on a new method for solving fully fuzzy linear programming problems. Appl Math Model 37:7865–7867
Sakawa M, Nishizaki I, Uemeura Y (2001) Fuzzy programming and profit and cost allocation for a production and transportation problem. Eur J Oper Res 131:1–15
Serenko A, Dohan M (2011) Comparing the expert survey and citation impact journal ranking methods: example from the field of artificial intelligence. J Inf 5:629–648
Stanciulescu C, Fortemps P, Installe M, Wertz V (2003) Multiobjective fuzzy linear programming problems with fuzzy decision variables. Eur J Oper Res 149:654–675
Stancu-Minasian IM (1984) Stochastic programming with multiple objective functions. Editura Academiei, Bucharest
Taha HA (2010) Operations research: an introduction, 9th edn. Prentice Hall, Upper Saddle River
Tanaka H, Asai K (1984) Fuzzy linear programming problems with fuzzy numbers. Fuzzy Sets Syst 13:1–10
Tanaka H, Asai K (1984) Fuzzy solution in fuzzy linear programming problems. IEEE Trans Fuzzy Syst 14:325–328
Tanaka H, Okuda T, Asai K (1973) On fuzzy mathematical programming. J Cybern 3:37–46
Tanaka H, Ichihashi H, Asai K (1984) A formulation of fuzzy linear programming problem based on comparison of fuzzy numbers. Control Cybern 13:185–194
Tanaka H, Guo P, Zimmermann HJ (2000) Possibility distributions of fuzzy decision variables obtained from possibilistic linear programming problems. Fuzzy Sets Syst 113:323–332
Teng JY, Tzeng GH (1990) Transportation investment planning with uncertainty: an integrated MCDM approach. Fuzzy Sets Syst 12:199–213
Tsakiris G, Spiliotis M (2004) Fuzzy linear programming for problems of water allocation under uncertainty. Eur Water 7:25–37
Vajda S (2010) Probabilistic programming, 2nd edn. Dover Publications, New York
Van Hop N (2007) Solving fuzzy (stochastic) linear programming problems using superiority and inferiority measures. Inf Sci 177:1977–1991
Verdegay JL (1984) A dual approach to solve the fuzzy linear programming problem. Fuzzy Sets Syst 14:131–141
Vijay V, Mehra A, Chandra S, Bector CR (2007) Fuzzy matrix games via a fuzzy relation approach. Fuzzy Optim Decis Mak 6:299–314
Wan SP, Dong JY (2014) Possibility linear programming with trapezoidal fuzzy numbers. Appl Math Model 38:1660–1672
Wan SP, Dong JY (2015) Interval-valued intuitionistic fuzzy mathematical programming method for hybrid multi-criteria group decision making with interval-valued intuitionistic fuzzy truth degrees. Inf Fusion 26:49–65
Wan SP, Li DF (2014) Atanassov’s intuitionistic fuzzy programming method for heterogeneous multiattribute group decision making with Atanassov’s intuitionistic fuzzy truth degrees. IEEE Trans Fuzzy Syst 22:300–312
Wan SP, Li DF (2015) Fuzzy mathematical programming approach to heterogeneous multiattribute decision-making with interval-valued intuitionistic fuzzy truth degrees. Inf Sci 325:484–503
Wan SP, Wang F, Lin LL, Dong JY (2015) An intuitionistic fuzzy linear programming method for logistics outsourcing provider selection. Knowl Based Syst 82:80–94
Wan SP, Wang F, Xu G, Dong JY, Tang J (2017) An intuitionistic fuzzy programming method for group decision making with interval-valued fuzzy preference relations. Fuzzy Optim Dec Mak 16:269–295
Wan SP, Qin YL, Dong JY (2017) A hesitant fuzzy mathematical programming method for hybrid multi-criteria group decision making with hesitant fuzzy truth degrees. Knowl Based Syst 138:232–248
Wan SP, Jin Z, Dong JY (2018) Pythagorean fuzzy mathematical programming method for multi-attribute group decision making with Pythagorean fuzzy truth degrees. Knowl Inf Syst 55:437–466
Wang D (1997) An inexact approach for linear programming problems with fuzzy objective and resources. Fuzzy Sets Syst 89:61–68
Wang X, Kerre EE (2001) Reasonable properties for ordering of fuzzy quantities. Fuzzy Sets Syst 118:375–385
Wang RC, Liang TF (2004) Application of fuzzy multi-objective linear programming to aggregate production planning. Comput Ind Eng 46:17–41
Wiedey G, Zimmermann HJ (1978) Media selection and fuzzy linear programming. J Oper Res Soc 29:1071–1084
Wu HC (2003) Duality theory in fuzzy linear programming problems with fuzzy coefficients. Fuzzy Optim Decis Mak 2:61–73
Wu HC (2008) Optimality conditions for linear programming problems with fuzzy coefficients. Comput Math Appl 55:2807–2822
Xiaozhong L (1997) A general model for fuzzy linear programming problems with fuzzy variables. J Liaocheng 76:137–140
Xu K, Tang LC, Xie M, Ho SL, Zhu ML (2002) Fuzzy assessment of fmea for engine systems. Reliab Eng Syst Saf 75:17–29
Xu G, Wan SP, Dong JY (2016) A hesitant fuzzy programming method for hybrid MADM with incomplete attribute weight information. Informatica 27:863–892
Yager RR (1979) On solving fuzzy mathematical relationships. Inf Control 41:29–55
Yager RR (1981) A procedure for ordering fuzzy subsets unit interval. Inf Sci 24:143–161
Yu CS, Li H (2001) An algorithm for generalized fuzzy binary linear programming problems. Eur J Oper Res 133:496–511
Zadeh LA (1965) Fuzzy sets. Inf Control 8:338–353
Zadeh LA (1975) The concept of a linguistic variable and its application to approximate reasoning-I. Inf Sci 8:199–249
Zhang C, Yuan X, Lee ES (2005) Duality theory in fuzzy mathematical programming problems with fuzzy coefficients. Comput Math Appl 49:1709–1730
Zhang B, Liang H, Zhang G (2018) Reaching a consensus with minimum adjustment in magdm with hesitant fuzzy linguistic term sets. Inf Fusion 42:12–23
Zhong Q, Guang-Yuan W (1993) On solutions and distribution problems of the linear programming with fuzzy random variable coefficients. Fuzzy Sets Syst 58:155–170
Zhong Q, Yue Z, Guang-Yuan W (1994) On fuzzy random linear programming. Fuzzy Sets Syst 65:31–49
Zimmermann HJ (1978) Fuzzy programming and linear programming with several objective functions. Fuzzy Sets Syst 1:45–55
Zimmermann HJ (1983) Fuzzy mathematical programming. Comput Oper Res 10:291–298
Zimmermann HJ (2001) Fuzzy set theory and its applications, 4th edn. Kluwer Academic Publishers, Berlin
Acknowledgements
The first author thanks the Research Council of Ferdowsi University of Mashhad; the second and third authors thank the Research Council of Sharif University of Technology; and the fourth author thanks the Research Council of Ghent University for supporting this work.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
Authors declare that they have no conflict of interest.
Ethical approval
This article does not contain any studies with human participants or animals performed by any of the authors.
Additional information
Communicated by V. Loia.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Ghanbari, R., Ghorbani-Moghadam, K., Mahdavi-Amiri, N. et al. Fuzzy linear programming problems: models and solutions. Soft Comput 24, 10043–10073 (2020). https://doi.org/10.1007/s00500-019-04519-w
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00500-019-04519-w