In this paper we have proposed some new techniques based on the centroid of triangular and trapezoidal fuzzy numbers to solve a fuzzy linear programming problem. These proposed methods are easy to implement with less number of arithmetic operations required compared to the existing methods. To illustrate the proposed method, numerical examples are given. A comparative study between the proposed methods and existing methods are given at the end. The superiority of these centroid based methods over known ranking function method has also been shown with an example.
The history of fuzzy operations research is nearly 40 years old now. It started with Beliman & Zadeh [1], although Zimmermann [2] first conceived the notion of fuzzy linear programming problem (FLPP). After that many authors have studied the notion of LPP in fuzzy settings. Fang et al. [3] introduced LPP with fuzzy constraints. Maleki and his colleagues [4, 5] considered LPP with fuzzy variables and computed the solution by considering the auxiliary problem. Fuzzy basic feasible solution for the fuzzy variable linear programming problem (FVLPP) [6, 7] and also the simplex algorithm along with the optimality conditions were studied by Mahdavi-Amiri and Nasseri [8]. Later Lotfi et al. [9] proposed a new method for finding the optimal solution of fully fuzzy linear programming problems. Allahviranloo et al. [10] proposed a new method to solve fully fuzzy linear programming problem (FFLPP) using ranking function. Kumar et al. [11] proposed FFLPP with inequality constraints by representing all the coefficients as triangular fuzzy numbers. On the other hand, Wang et al. [12] proposed new simplified formulae to find the centroids of triangular and trapezoidal fuzzy numbers. Karpagam and Sumathi [13] proposed a new technique to solve FVLPP using ranking function. Although there are several techniques available for finding the solution of a FLPP, but most of them requires a lot of rigorous calculations. Therefore our objective in this paper is to introduce some new techniques for solving FLPP which are easy to compute and gives better results. Here we have proposed a couple of centroid based methods to solve a FLPP, All these proposed methods are new and easy to implement as they require less number of arithmetic operations in comparison to other available methods. We have also shown the accuracy and compatibility of our techniques using numerical problems and established their superiority over other available methods.
The rest of the paper is organized as follows: in Section 2, some preliminary definitions related to fuzzy sets and FLPP are given. In Section 3, the brief algorithm and methods to solve a FLPP are discussed. In Section 4, a numerical example has been selected and solved by the proposed techniques discussed in the previous section. Section 5 contains results and discussions. Finally the last section concludes the article.
In this section, we recall some definitions related to fuzzy sets, fuzzy numbers, LPP, FLPP, FFLPP, triangular fuzzy number, and trapezoidal fuzzy number, etc., which will be used for the rest of the paper.
If X is a collection of objects, then a
The crisp LPP is formulated as follows:
where x_{j} ≥ 0, i = 1, 2, 3, …, m and j = 1, 2, 3, …, n. Here x_{j} ’s are the decision variables, c_{j} ’s are the price parameters, a_{ij} ’s are the activity parameters and b_{i}’s are the requirement parameters and all of them assume real number as their values.
A fuzzy number is a generalization of real numbers, i.e., fuzzy number is a quantity whose value is not fixed. It can be considered as a function from the real number set to the set of real numbers between and including 0 and 1. Each number at the domain is assigned a specific membership grade, where 0 is the smallest possible membership grade where as 1 is the largest possible membership grade.
A LPP is called FFLPP, if parameters and variables all are fuzzy numbers. General form of FFLPP is as follows:
where x̃_{j} ≥ 0, c̃_{j} ∈ (F(R))^{n}, ã_{j} ∈ (F(R))^{m}^{×}^{n}, b̃_{i} ∈ (F(R))^{m}, x̃_{j} ∈ (F(R))^{n}. F(R) is the set of all fuzzy numbers.
In case of FLPP the variables are crisp, i.e., real valued. So a FFLPP is more general in nature than FLPP.
A fuzzy number Ã = (b, α, β) is said to be a triangular fuzzy number with peak b, left width α = b − a and right width β = c − b, if its membership function is given by:
The support of Ã is (b − α, b + β) = (a, c)in Figure 1.
A fuzzy number Ã = (a, b, c, d) is said to be trapezoidal fuzzy number with tolerance interval [b, c], left width α = b − a and right width β = d − c, if its membership function is given by
The support of Ã is (b − α, c + β) = (a, d) in Figure 2.
In this section we shall discuss about the techniques to solve a FLPP.
Solution using triangular fuzzy number and a ranking function:
This method is described in [11] and is based on certain ranking function of triangular fuzzy numbers. Here all the parameters are represented by triangular fuzzy numbers which was ultimately defuzzified using ranking function to reduce the FLPP to a crisp LPP.
Let us take a triangular fuzzy number (a, b, c), with peak as b. Now calculate α = b − a and β = c − b. Then apply the ranking function to get a defuzzified form of that number. Apply this technique to all the triangular fuzzy numbers to get a defuzzified LPP.
Next we propose the following three methods which involve the centroid of triangular and trapezoidal fuzzy numbers instead of any arbitrary ranking functions. This is used because the techniques of finding the centroid of triangular or trapezoidal fuzzy numbers are well known and easy to determine. Also the centroid preserves the characteristics of the original fuzzy number.
Solution using centroid of a triangular fuzzy number:
The algorithm is almost same with Method 1 except that Step 2 of Algorithm 1, we replace the ranking function by the centroid of the triangle [9] with vertices a, b and c as
Solution using centroid of a trapezoidal fuzzy number:
The algorithm is almost same with Method 1 except that in Step 1 of Algorithm 1, we use the trapezoidal fuzzy numbers instead of triangular fuzzy numbers.
In Step 2, we defuzzify the trapezoidal fuzzy numbers using the centroid formula of Trapezoidal numbers given in [9] as follows:
where a = γ − β; b = δ − α; c = β − αm and α, β, γ, δ are the abscissa of the vertices of the trapezium. Then follow the similar steps to solve the FLPP.
Solution using trapezoidal fuzzy numbers and the centroid of centroids formula.
In Step 2, of the above algorithm, we defuzzify the trapezoidal fuzzy numbers using the centroid of centroids formula [9].
Here ABCD is the trapezoidal representation of the trapezoidal fuzzy number (α, β, γ, δ). Now, join BF. So, here we get three triangles ΔABF, ΔBCF and ΔCDF. We compute the centroids of the triangles and let G1, G2 and G3, respectively be the centroids of them.
So as discussed in Method 3, we have:
Now we get a triangle made by those centroids, viz G_{1}G_{2}G_{3}. If G is the centroid of this triangle, then
Now, to solve the FLPP, we have to follow the similar steps.
The normal or crisp LPP model the cases when there are no uncertainties associated with the parameters related to the problem. But if there are uncertainties in price, activity or requirement parameters associated to any problem then FLPP is used to model such cases. To illustrate such a case consider the following problem: Suppose a petrol pump sells two types of petrol, namely ‘normal’ and ‘speed’. But the price of each type of petrol may change slightly on day to day basis. Let the selling price of them is approximately 3 and 4 units, respectively. The storage capacities of normal and speed are approximately in the ratio of 3 : 4 with total capacity of 24 units. Again the cost price of each kind of petrol is more or less 1 and 3 units respectively. And the owner of the petrol pump can spend nearly 15 units of money each day for buying petrol. Now what are the amount of petrol of each kind should the owner buy to maximize his profit?
The above problem is modeled using a crisp LPP as follows:
Here x_{1} and x_{2}, respectively, represent the amount of ‘speed’ and ‘normal’ petrol that the owner should buy.
First of all we will apply the traditional simplex method to solve the crisp LPP. Next we model the problem using a FLPP where constants will be represented by either triangular or trapezoidal fuzzy numbers. First we use conventional ‘ranking function’ method to solve the problem. Next we use our proposed fuzzy methods to solve the problem and compare these two results. A comparative study has been provided in Section 5.
Solution by traditional simplex method (Table 1):
Adding slack variable to each constraint, the converted equations are,
So, optimality satisfied and the solution is: x_{1} = 4, x_{2} = 3 and max z = 25.
Solution using triangular fuzzy number and a ranking function [13]:
Now let us convert the crisp LPP into a FFLPP using Triangular fuzzy numbers as follows:
Let us apply the ranking function as defined above to defuzzify the Triangular fuzzy numbers and also introduce the slack variables as follows:
As shown in Table 2, optimality satisfied and the solution is: x̃_{1} = 5.42, x̃_{2} = 3.873, max z̃ = 29.581.
Solution using triangular fuzzy numbers and the centroid formula:
Now we defuzzify the triangular fuzzy numbers using the centroid formula, i.e,
So, the above FLPP is defuzzified as follows:
As shown in Table 3, optimality satisfied and the solution is: x̃_{1} = 3.824, x̃_{2} = 2.233, max z̃ = 20.168.
Solution using centroid of trapezoidal fuzzy numbers:
Now let us convert the crisp LPP into a FLPP using Trapezoidal fuzzy numbers as follows:
Now we defuzzify the trapezoidal fuzzy numbers using the centroid formula, i.e.,
where a = γ − β; b = δ − α; c = β − α and α, β, γ, δ are the abscissa of the vertices of the trapezium.
So, the above FLPP is defuzzified as follows:
As shown in Table 4, optimality satisfied and the solution is : x̃_{1} = 4.837, x̃_{2} = 3.060, max z̃ = 25.742.
Solution using trapezoidal fuzzy numbers and the centroid of centroids formula:
Using this technique, the above trapezoidal FLPP is reduced to a crisp LPP as follows:
As shown in Table 5,
x̃_{1}x̃_{2} max z̃x̃_{1}x̃_{2} max z̃ Optimality satisfied and the solution is: x̃_{1}= 3.683, x̃_{2}= 3.6, max z̃= 27.771.
In the above section we have considered a practical problem and represented it in terms of a FLPP where the constants are fuzzy numbers. Also it can be considered as a normal LPP if we neglect the uncertainty factors described there. We have first solved this FLPP by a known method using ranking function. Also for crisp case we have used well known ‘simplex method’ to solve it. Then we have applied our new centroid based methods (3 in number) to solve the FLPP. The results obtained by all these five method are represented in tabular form (Table 6).
Here we see that the results obtained by our proposed methods are different from the results obtained using the known ranking function method [13]. Also our results are comparatively closer with the results obtained by solving crisp LPP. But in all cases the results of FLPP are not equal with crisp LPP results, which is natural due to the presence of uncertainty in FLPP. On the other hand centroid of triangular and trapezoidal fuzzy numbers retains the properties of the original fuzzy number to a large extent. This shows the superiority of our proposed centroid based techniques instead of taking ranking functions. Also it can be said undoubtedly that our proposed methods involves only the calculation of centroid of triangular and trapezoidal fuzzy numbers, which is very elementary, and then the use of simplex method.
In this paper some new methods to solve a FLPP based on centroid of triangular and trapezoidal fuzzy numbers has been proposed. Also a method based on the centroid of centroids of a trapezoidal fuzzy number has been introduced. In these methods a FLPP is defuzzified into a crisp LPP using the proposed methods and solved it using normal simplex method. Since centroids are well equipped to express the features of the triangular or trapezoidal fuzzy numbers, so these methods are more realistic than the existing methods based on the ranking function. Also the calculation for finding the centroid of a triangular and a trapezoidal number is very simple. The numerical example also clearly proves the superiority of our proposed methods.
No potential conflict of interest relevant to this article was reported.
Simplex table of Method 4.0
C_{B} | 4 | 3 | 0 | 0 | Min ratio | ||
---|---|---|---|---|---|---|---|
B | |||||||
0 | 15 | 3^{*} | 1 | 1 | 0 | ||
0 | 24 | 3 | 4 | 0 | 1 | ||
0 | −4^{*} | −3 | 0 | 0 | |||
4 | 5 | 1 | 0 | 15 | |||
0 | 9 | 0 | 3^{*} | −1 | 1 | 3^{*} | |
20 | 0 | 0 | |||||
4 | 4 | 1 | 0 | ||||
3 | 3 | 0 | 1 | ||||
25 | 0 | 0 |
Simplex table of Method 4.1
C_{B} | c |
3.85 | 2.25 | 0 | 0 | Min ratio | |
---|---|---|---|---|---|---|---|
B | |||||||
0 | 14.85 | 2.2^{*} | 0.75 | 1 | 0 | 6.75^{*} | |
0 | 23.1 | 2.15 | 3 | 0 | 1 | 10.74 | |
0 | −3.85^{*} | −2.25 | 0 | 0 | |||
3.85 | 6.75 | 1 | 0.341 | 0.455 | 0 | 19.79 | |
0 | 8.588 | 0 | 2.217^{*} | −0.978 | 1 | 4.138^{*} | |
25.987 | 0 | −0.849^{*} | 1.752 | 0 | |||
3.85 | 5.42 | 1 | 0 | 0.605 | −0.154 | ||
2.25 | 3.873 | 0 | 1 | −0.441 | 0.451 | ||
29.581 | 0 | 0 | 1.379 | 0.422 |
Simplex table of Method 4.2
C_{B} | c |
3.6 | 2.867 | 0 | 0 | Min ratio | |
---|---|---|---|---|---|---|---|
B | |||||||
0 | 13.43 | 2.967^{*} | 0.933 | 1 | 0 | 4.594^{*} | |
0 | 20.66 | 3.033 | 4.067 | 0 | 1 | 6.812 | |
0 | −3.6^{*} | −2.867 | 0 | 0 | |||
3.6 | 4.526 | 1 | 0.314 | 0.337 | 0 | 14.414 | |
0 | 6.726 | 0 | 3.012^{*} | −1.022 | 1 | 2.233^{*} | |
16.293 | 0 | −1.736^{*} | 1.213 | 0 | |||
3.6 | 3.824 | 1 | 0 | 0.443 | −0.104 | ||
2.867 | 2.233 | 0 | 1 | −0.339 | 0.332 | ||
20.168 | 0 | 0 | 0.666 | 0.577 |
Simplex table of Method 4.3
C_{B} | c |
3.5 | 2.88 | 0 | 0 | Min ratio | |
---|---|---|---|---|---|---|---|
B | |||||||
0 | 14.54 | 2.5^{*} | 0.8 | 1 | 0 | 3.144^{*} | |
0 | 23.48 | 2.93 | 3.14 | 0 | 1 | 3.894 | |
0 | −3.5^{*} | −2.88 | 0 | 0 | |||
3.5 | 5.816 | 1 | 0.32 | 0.337 | 0 | 18.175 | |
0 | 6.739 | 0 | 2.202^{*} | −1.172 | 1 | 3.060^{*} | |
20.356 | 0 | −1.76^{*} | 1.4 | 0 | |||
3.5 | 4.837 | 1 | 0 | 0.570 | −0.145 | ||
2.88 | 3.060 | 0 | 1 | −0.532 | 0.454 | ||
25.742 | 0 | 0 | 0.463 | 0.8 |
Simplex table of Method 4.4
C_{B} | c |
4 | 3.622 | 0 | 0 | Min ratio | |
---|---|---|---|---|---|---|---|
B | |||||||
0 | 17.189 | 3.689^{*} | 1 | 1 | 0 | 4.659^{*} | |
0 | 27.778 | 3.333 | 4.089 | 0 | 1 | 8.33 | |
0 | −4^{*} | −3.622 | 0 | 0 | |||
4 | 4.659 | 1 | 0.271 | 0.271 | 0 | 17.19 | |
0 | 11.471 | 0 | 3.186 | −0.903 | 1 | 3.6^{*} | |
18.636 | 0 | −2.538 | 1.262 | 0 | |||
4 | 3.683 | 1 | 0 | 0.348 | −0.085 | ||
3.622 | 3.6 | 0 | 1 | −0.283 | 0.314 | ||
27.771 | 0 | 0 | 0.367 | 0.797 |
Comparison of results
Crisp | Ranking function | Centroid using triangular fuzzy numbers | Centroid using trapezoidal fuzzy numbers | Centroid of trapezoidal fuzzy numbers | |
---|---|---|---|---|---|
4 | 5.42 | 3.824 | 4.837 | 3.683 | |
3 | 3.873 | 2.233 | 3.060 | 3.6 | |
max |
25 | 29.581 | 20.168 | 25.742 | 27.771 |
E-mail: pmajumdar2@rediffmail.com