search for




 

On New Centroid Based Techniques for Solving Fuzzy Linear Programming Problems
International Journal of Fuzzy Logic and Intelligent Systems 2019;19(4):299-306
Published online December 25, 2019
© 2019 Korean Institute of Intelligent Systems.

Sudip Bhattacharyya and Pinaki Majumdar

Department of Mathematics, M.U.C Women’s College, Burdwan, West-Bengal, India
Correspondence to: Pinaki Majumdar (pmajumdar2@rediffmail.com)
Received August 18, 2019; Revised December 10, 2019; Accepted December 12, 2019.
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract

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.

Keywords : Fuzzy linear programming problem (FLPP), Fully fuzzy linear programming problem (FFLPP), Triangular fuzzy number, Trapezoidal fuzzy numbers, Centroid
1. Introduction

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.

2. Preliminaries

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.

Definition 2.1

If X is a collection of objects, then a fuzzy setà in X is a set of ordered pairs: à = {(x, μA(x)) |xX}, where μA(x) is called the membership function or grade of membership (also degree of compatibility or degree of truth) of x in à that maps X to the membership space M i.e., μA : XM = [0, 1].

Definition 2.2

The crisp LPP is formulated as follows:

Optimize z=j=1ncjxjsubject toj=1naijxj(or=or)bi,

where xj ≥ 0, i = 1, 2, 3, …, m and j = 1, 2, 3, …, n. Here xj ’s are the decision variables, cj ’s are the price parameters, aij ’s are the activity parameters and bi’s are the requirement parameters and all of them assume real number as their values.

Definition 2.3

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.

Definition 2.4 [13]

A LPP is called FFLPP, if parameters and variables all are fuzzy numbers. General form of FFLPP is as follows:

Optimize z˜=j=1nc˜jx˜jsubject toj=1na˜ijx˜j(or=or)b˜i,

where j ≥ 0, j ∈ (F(R))n, ãj ∈ (F(R))m×n, i ∈ (F(R))m, 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.

Definition 2.5

A fuzzy number à = (b, α, β) is said to be a triangular fuzzy number with peak b, left width α = ba and right width β = cb, if its membership function is given by:

μA˜(x)={1-b-xα,if b-αxb,α>0,1-x-bβ,if bxb+β,β>0,0,otherwise.

The support of à is (bα, b + β) = (a, c)in Figure 1.

Definition 2.6

A fuzzy number à = (a, b, c, d) is said to be trapezoidal fuzzy number with tolerance interval [b, c], left width α = ba and right width β = dc, if its membership function is given by

μA˜(x)={1-b-xα,if b-αxb,α>0,1,if bxc,1-x-bβ,if bxc+β,β>0,0,otherwise.

The support of à is (bα, c + β) = (a, d) in Figure 2.

3. Solution Methods for Fuzzy LPP

In this section we shall discuss about the techniques to solve a FLPP.

Method 1

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.

Algorithm 1

Step 1: First of all, we replace the crisp numbers (cj, aij and bi) of a LPP with the triangular fuzzy numbers to obtain a FLPP, i.e.,

max z˜=c˜jx˜jsubject to a˜ijx˜jb˜i,x˜j0.

Step 2: Using the ranking function (c˜,A˜)=b+2α-β2 for a triangular fuzzy number à = (b, α, β).

Let us take a triangular fuzzy number (a, b, c), with peak as b. Now calculate α = ba and β = cb. 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.

Step 3: Solve the defuzzified LPP by simplex method. Before that, convert all the constraints into equations by adding slack variables with cost 0.

Step 4: Compute the value of jj where z˜j=i=1mCBiyij for j = 1, 2, …, n. If all those values are positive for all j, then the optimality is satisfied. Otherwise go to Step 5.

Step 5: If at least one jj < 0, then the most minimum of all jj is chosen. If min(jj) = kk then the variable xk is the entering variable and this column is called key column. Also compute min{xBiyik,yik>0}. If this minimum is unique and occurs at i = r, then the r-th variable of the basis is the departing variable and the row is called key row. The element at the intersection of the key row and key column, i.e. yrk is called the pivot element.

Step 6: Perform the pivot operation and return to Step 4. End of algorithm.

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.

Method 2

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 G(a,b,c)=a+b+c3 and then perform all the steps of the above algorithm to solve the FLPP.

Method 3

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:

C(α,β,γ,δ)=2ac+a2+bc+ab+b23(a+b),

where a = γβ; b = δα; c = βαm and α, β, γ, δ are the abscissa of the vertices of the trapezium. Then follow the similar steps to solve the FLPP.

Method 4

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:

G1=α+β+γ3,G2=β+γ+γ3and G3=γ+γ+δ3.

Now we get a triangle made by those centroids, viz G1G2G3. If G is the centroid of this triangle, then G=G1+G2+G33 and we can consider this centroid G is the centroid of the trapezium ABCD.

Now, to solve the FLPP, we have to follow the similar steps.

4. A Numerical Example to Show the Application of the Proposed Methods

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:

max z=4x1+3x2Subject to3x1+x215,3x1+4x224,x1,x20.

Here x1 and x2, 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.

Method 4.0

Solution by traditional simplex method (Table 1):

Adding slack variable to each constraint, the converted equations are,

3x1+x2+x3=15,3x1+4x2+x4=24,xi0,i=1,2,3,4.

So, optimality satisfied and the solution is: x1 = 4, x2 = 3 and max z = 25.

Method 4.1

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:

max z˜=(1.5,4,5.3)x˜1+(1.9,3,3.7)x˜2subject to(1.7,3,4.2)x˜1+(0.7,1,1.1)x˜2(5,15,20.3),(1.6,3,4.5)x˜1+(1.8,4,6.4)x˜2(11.8,24,26.2),x˜i0,   i=1,2.

Let us apply the ranking function as defined above to defuzzify the Triangular fuzzy numbers and also introduce the slack variables as follows:

max z˜=3.85x˜1+2.25x˜2+0.x˜3+0.x˜4subject to2.2x˜1+0.75x˜2+x˜3=14.85,2.15x˜1+3x˜2+x˜4=23.1,x˜i0,   i=1,2,3,4.

As shown in Table 2, optimality satisfied and the solution is: 1 = 5.42, 2 = 3.873, max = 29.581.

Method 4.2

Solution using triangular fuzzy numbers and the centroid formula:

Now we defuzzify the triangular fuzzy numbers using the centroid formula, i.e, G(a,b,c)=a+b+c3, where a, b and c are the vertices of the triangle.

So, the above FLPP is defuzzified as follows:

max z˜=3.6x˜1+2.867x˜2+0.x˜3+0.x˜4subject to2.967x˜1+0.933x˜2+x˜3=13.43,3.033x˜1+4.067x˜2+x˜4=20.66,x˜i0,   i=1,2,3,4.

As shown in Table 3, optimality satisfied and the solution is: 1 = 3.824, 2 = 2.233, max = 20.168.

Method 4.3

Solution using centroid of trapezoidal fuzzy numbers:

Now let us convert the crisp LPP into a FLPP using Trapezoidal fuzzy numbers as follows:

max z˜=(0.8,2.5,4.8,6.2)x˜1+(0.2,1.8,4.6,5.8)x˜2subject to(0.5,1.6,4.8,5.5)x˜1+(0.1,0.6,1.2,1.7)x˜2(1.5,12.2,19.6,30.8),(0.1,1.2,4.2,6.5)x˜1+(0.6,2.3,4.9,7.1)x˜2(2.6,21.3,30.8,50.8),x˜i0,   i=1,2.

Now we defuzzify the trapezoidal fuzzy numbers using the centroid formula, i.e.,

C(α,β,γ,δ)=2ac+a2+bc+ab+b23(a+b),

where a = γβ; b = δα; c = βα and α, β, γ, δ are the abscissa of the vertices of the trapezium.

So, the above FLPP is defuzzified as follows:

max z˜=3.5x˜1+2.88x˜2+0.x˜3+0.x˜4subject to2.5x˜1+0.8x˜2+x˜3=14.54,2.93x˜1+3.14x˜2+x˜4=23.78,x˜i0,   i=1,2,3,4.

As shown in Table 4, optimality satisfied and the solution is : 1 = 4.837, 2 = 3.060, max = 25.742.

Method 4.4

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:

maxz˜=4x˜1+3.622x˜2+0.x˜3+0.x˜4subject to3.689x˜1+x˜2+x˜3=17.189,3.333x˜1+4.089x˜2+x˜4=27.778,x˜i0,   i=1,2,3,4.

As shown in Table 5,

12 max z̃x̃12 max Optimality satisfied and the solution is: 1= 3.683, 2= 3.6, max = 27.771.

5. Results and Discussion

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.

6. Conclusion

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.

Conflict of Interest

No potential conflict of interest relevant to this article was reported.

Figures
Fig. 1.

Triangular fuzzy.


Fig. 2.

Trapezoidal fuzzy number.


TABLES

Table 1

Simplex table of Method 4.0

CB xB cj 4 3 0 0 Min ratio
B x1 x2 x3 x4
0 x3* 15 3* 1 1 0 153=5*
0 x4 24 3 4 0 1 243=8

zjcj 0 −4* −3 0 0

4 x1 5 1 13 13 0 15
0 x4* 9 0 3* −1 1 3*

zjcj 20 0 -53* 43 0

4 x1 4 1 0 49 -19
3 x2 3 0 1 -13 13

zjcj 25 0 0 79 59

Table 2

Simplex table of Method 4.1

CB xB cj 3.85 2.25 0 0 Min ratio
B x1 x2 x3 x4
0 x3* 14.85 2.2* 0.75 1 0 6.75*
0 x4 23.1 2.15 3 0 1 10.74

zjcj 0 −3.85* −2.25 0 0

3.85 x1 6.75 1 0.341 0.455 0 19.79
0 x4* 8.588 0 2.217* −0.978 1 4.138*

zjcj 25.987 0 −0.849* 1.752 0

3.85 x1 5.42 1 0 0.605 −0.154
2.25 x2 3.873 0 1 −0.441 0.451

zjcj 29.581 0 0 1.379 0.422

Table 3

Simplex table of Method 4.2

CB xB cj 3.6 2.867 0 0 Min ratio
B x1 x2 x3 x4
0 x3* 13.43 2.967* 0.933 1 0 4.594*
0 x4 20.66 3.033 4.067 0 1 6.812

zjcj 0 −3.6* −2.867 0 0

3.6 x1 4.526 1 0.314 0.337 0 14.414
0 x4* 6.726 0 3.012* −1.022 1 2.233*

zjcj 16.293 0 −1.736* 1.213 0

3.6 x1 3.824 1 0 0.443 −0.104
2.867 x2 2.233 0 1 −0.339 0.332

zjcj 20.168 0 0 0.666 0.577

Table 4

Simplex table of Method 4.3

CB xB cj 3.5 2.88 0 0 Min ratio
B x1 x2 x3 x4
0 x3* 14.54 2.5* 0.8 1 0 3.144*
0 x4 23.48 2.93 3.14 0 1 3.894

zjcj 0 −3.5* −2.88 0 0

3.5 x1 5.816 1 0.32 0.337 0 18.175
0 x4* 6.739 0 2.202* −1.172 1 3.060*

zjcj 20.356 0 −1.76* 1.4 0

3.5 x1 4.837 1 0 0.570 −0.145
2.88 x2 3.060 0 1 −0.532 0.454

zjcj 25.742 0 0 0.463 0.8

Table 5

Simplex table of Method 4.4

CB xB cj 4 3.622 0 0 Min ratio
B x1 x2 x3 x4
0 x3* 17.189 3.689* 1 1 0 4.659*
0 x4 27.778 3.333 4.089 0 1 8.33

zjcj 0 −4* −3.622 0 0

4 x1 4.659 1 0.271 0.271 0 17.19
0 x4 11.471 0 3.186 −0.903 1 3.6*

zjcj 18.636 0 −2.538 1.262 0

4 x1 3.683 1 0 0.348 −0.085
3.622 x2 3.6 0 1 −0.283 0.314

zjcj 27.771 0 0 0.367 0.797

Table 6

Comparison of results

Crisp Ranking function Centroid using triangular fuzzy numbers Centroid using trapezoidal fuzzy numbers Centroid of trapezoidal fuzzy numbers
1 4 5.42 3.824 4.837 3.683
2 3 3.873 2.233 3.060 3.6
max 25 29.581 20.168 25.742 27.771

References
  1. Bellman, RE, and Zadeh, LA (1970). Decision-making in a fuzzy environment. Management Science. 17, B141-B273. https://doi.org/10.1287/mnsc.17.4.B141
    CrossRef
  2. Zimmermann, HJ (1978). Fuzzy programming and linear programming with several objective functions. Fuzzy Sets and Systems. 1, 45-55. https://doi.org/10.1016/0165-0114(78)90031-3
    CrossRef
  3. Fang, SC, Hu, CF, Wang, HF, and Wu, SY (1999). Linear programming with fuzzy coefficients in constraints. Computers & Mathematics with Applications. 37, 63-76. https://doi.org/10.1016/S0898-1221(99)00126-1
    CrossRef
  4. Maleki, HR, Tata, M, and Mashinchi, M (2000). Linear programming with fuzzy variables. Fuzzy Sets and Systems. 109, 21-33. https://doi.org/10.1016/S0165-0114(98)00066-9
    CrossRef
  5. Maleki, HR (2002). Ranking functions and their applications to fuzzy linear programming. Far East Journal of Mathematical Sciences. 4, 283-301.
  6. Kolman, , and Hill, (1984). Fuzzy variable linear programming problem by use of a certain linear ranking function. Applied Mathematics. 18.
  7. Nasseri, SH, Ardil, E, Yazdani, A, and Zaefarian, R (2005). Simplex method for fuzzy variable linear programming problems. International Journal of Mathematical, Computational, Physical, Electrical and Computer Engineering. 3, 884-888.
  8. Mahdavi-Amiri, N, and Nasseri, SH 2005. Duality in fuzzy variable linear programming., Proceedings of the 4th World Enformatika Conference (WEC), Istanbul, Turkey, pp.24-26.
  9. Lotfi, FH, Allahviranloo, T, Jondabeh, MA, and Alizadeh, L (2009). Solving a full fuzzy linear programming using lexicography method and fuzzy approximate solution. Applied Mathematical Modelling. 33, 3151-3156. https://doi.org/10.1016/j.apm.2008.10.020
    CrossRef
  10. Allahviranloo, T, Lotfi, FL, Kiasary, MK, Kiani, NA, and Alizadeh, L (2008). Solving fully fuzzy linear programming problem by the ranking function. Applied Mathematical Sciences. 2, 19-32.
  11. Kumar, A, Kaur, J, and Singh, P (2010). Fuzzy optimal solution of fully fuzzy linear programming problems with inequality constraints. International Journal of Mathematical and Computer Science. 6, 37-40. 564426024
  12. Wang, YM, Yang, JB, Xu, DL, and Chin, KS (2006). On the centroids of fuzzy numbers. Fuzzy Sets and Systems. 157, 919-926. https://doi.org/10.1016/j.fss.2005.11.006
    CrossRef
  13. Karpagam, A, and Sumathi, P (2014). New approach to solve fuzzy linear programming problems by the ranking function. Bonfring International Journal of Data Mining. 4, 22-25.
    CrossRef
Biographies

Sudip Bhattacharyya is a Ph.D. scholar under Dr. Pinaki Majumdar. He has done his M.Sc. in Pure Mathematics from the University of Burdwan in 2013. His area of research includes neutrosophic sets, fuzzy operations research, fuzzy multi-sets etc. He has already published a couple of research papers in international journals.


Pinaki Majumdar is an assistant professor of Mathematics at M.U.C Women’s College, University of Burdwan, India. He has completed his M.Sc. and Ph.D. in Mathematics from Visva-Bharati University, India in 2002 and 2013, respectively. Main area of his research includes fuzzy functional analysis, soft set theory and applications, neutrosophic set theory, etc. He has published more than 40 research papers and contributed a few chapters in research monographs in reputed international journals.

E-mail: pmajumdar2@rediffmail.com