Fuzzy Linear Programming problem

I. INTRODUCTION

The need to find the optimal solution, or the best solution among those available, in well-defined problems is why we study and propose theories and methodologies to the scientific field in which there is the question to be resolved. From a concrete viewpoint, an important class of problems are those known under the name of optimization problems usually associated with having to find the maximum or the minimum value that can achieve a particular function in an certain pre-specified set. Optimization problems are common to a large variety of research and development fields, to such an extent that it could be stated that in any theoretical or applied process, whatever its nature, at a given time an optimization problem will have to be faced, and thus the developments related to both optimization methods and models are very frequent and numerous in the literature. In particular, this is also true in the concrete, but also general, mathematical programming area. In this last context, it is convenient to distinguish two key aspects relating to their methods and models. Given whatever problem, and in particular, without loss of generality, a linear one, we can consider different approaches according to how we deal with it from a theoretical or practical perspective.
Among all models included in Mathematical Programming, the most and best studied, and which has proven to have a major practical impact, is the corresponding uni-objective linear case, the subject of concern to the Linear Programming (LP). The methods and linear programming models have important applications in different areas of Engineering, Economics, Mathematics, Artificial Intelligence, and other subjects more or less related to the optimization, and provide a theoretical more than adequate to address an elegant and efficient way very complex situations.
Although as stated above, models and LP techniques are the most and best studied, it is precisely for that reason, along with that efficiency and elegance that characterizes them, so they are easily adaptable to new technological context. They are the protagonists on the latest scientific developments, such as in incorporation and implementation of the pattern generating systems of Decision Support Systems (DSS). Thus the LP appears united in one of the most promising lines of development in the field of Artificial Intelligence, and consequently, despite its more than fifty years, at the forefront of scientific advancement.
From the first point of view, a LP problem is established as

where c and x are n vectors, b is an m vector, and A is an m×n matrix, i.e., if ℜ denotes the real line, c, x in ℜⁿ, b ∈ ℜ^m and A ∈ ℜ^m × ℜⁿ. As it is well known from this simple model, multiple results and theoretical extensions, which afterwards have an undoubted practical reflection, can be obtained.
However, from the practical point of view, when we approach a problem of this type, and we ask the corresponding expert or decision maker the specific details that have to be introduced in the model, in many circumstances the answers that he gives us are of a vague nature, and thus it is usual that when we ask, for example, for the costs included in the objective function, we are told that the first cost is "about 18", the second one is "not much more than 29", etc. And the same can happen with the rest of the parameters that define the problem (right hand side b and coefficients in the technological matrix A). Usually, this frequent lack of precision is avoided by simplifying the problem forcing these vague values to be exact (by rounding off, by approximation, etc.), so obliging us to formulate and solve a problem with a (precise) nature different from the (vague) original one. But this "simplification" of the problem has two immediate effects. In the first place, the nature of the model is effectively changed, since, from one, that is imprecise owing to the vagueness of its information, it goes to another of a conventional type, and therefore, of an exact numerical formulation, that can cause an excessive and counterproductive simplification (think of what would occur if we do the same, when the initial information has a probabilistic nature, instead of the imprecise nature that we assume here). Secondly, this simplification of the model can produce very serious errors relating to the obtaining of the solution. In effect, let us suppose that one of the details that the decision maker gives us is that the cost "c" has a value "around 500", and that we take the true value of "c" to be exactly 500. If in reality the actual value of "c" was 510 (only 2% more than 500), the true optimal solution could be very different from the optimal solution that would have been obtained for the simplified model.
Therefore, it seems evident from a theoretical point of view, as well as from a practical point of view, that for problems that have imprecise formulations in the sense considered here, this vague nature should be maintained as in its formulation as in its solution. A theoretical tool that has been proved to be very useful for the modelization of these situations is that which the fuzzy numbers provides [7], since they permit numerical treatment of these types of qualitative details to which we are referring, and that are a natural expression of the habitual form of communication between human beings.
In this context, we considers LP problems in which the data that define them (c, b, and A), have a vague (fuzzy) nature, and not exact as is habitual, so that it permits the decision maker to express his knowledge over these data, for which he has a certain lack of precision, in a qualitative way, [1,2]. These fuzzy LP problems (FLP) can be solved in a direct and easy way, obtaining solutions that are coherent with their former fuzzy nature, [1,2].

II. THE MODEL

To introduce the problem, only the essential ideas on basic concepts are summarized in the following. Any case [8] presents an extensive and comprehensive survey on fuzzy mathematical programming (FMP). Besides this, current interesting issues on fuzzy optimization can be found in [5]. Let us consider, as we have commented, that when an expert is asked for the values of the different coefficients that are used in the formulation of a problem such as (1), he gives us imprecise information about them, and that this information has not a probabilistic nature, but a vague one. A vague quantity can be modeled by making use of the concept of fuzzy number. Fuzzy numbers were introduced in [10] with the main goal of analyzing and manipulating approximate numeric values, and they are based on the former concept of fuzzy set [9].

Definition 1: A fuzzy set of a referential set X is characterized by a membership function μ_A which is valued in [0,1], that is

with μ_A(x) representing the membership degree of x ∈ X in A.          □

The concept of fuzzy number is defined differently by different authors [6], but the most frequently used definition [7] is as follows.

Definition 2: A fuzzy number is a fuzzy set in the real line which

1. is normal, that is, Sup_r∈ℜ μ_A(r) = 1, and
2. is bounded convex, i.e., the sets {r ∈ ℜ: μ_A(r) ≥ α}, ∀ α ∈[0,1], are convex and bounded.          □

Using this definition, information such as "the cost c is about 23", can be expressed by means of the membership function

We will denote these numbers in bold print and with the help of a triple value. So the former number will be denoted such as c = (23, 21, 25), with a clear significance. We will therefore note F(ℜ) the set of membership functions on R and when we speak about the fuzzy numbers we can refer to the element c ∈ F(ℜ) as well as μ_c ∈ F(ℜ).

Remark 1: The definition of a fuzzy number can be made much more general than the former to include the case, for example, of trapezoidal membership functions (μ(x) = 1 along an interval), or nonlinears (the said LR numbers). But it could be demonstrated [4] that under very gentle hypothesis, all these cases can be easily solved if previously, the solution of the problem is obtained using membership functions like those presented here (triangular). That is the reason why in this article, we concentrate exclusively on this type of triangular functions.

Remark 2: Associated with the concept of fuzzy numbers is the problem of ranking them. A single method to solve this problem does not exist. In view of this, there is a long list of methods for ranking fuzzy numbers (of relations of comparisons between fuzzy numbers, generally noted as ≤_g), that in many cases provide different rankings [12]. This can be understood because, being imprecise quantities, the appreciation that each specific decision maker has for these can be different.

In FLP the models from a singular point of view are the following:

• Problems with fuzzy constraints, in which a decision maker permits a flexible satisfaction of constraints, that is, he allows small violations in the accomplishment of the constraints.
• Problems with a fuzzy objective, in which the information on tbe coefficients of tbe objective function is vague. They may be defined by fuzzy numbers. The set of real fuzzy numbers will be denoted F(R).
• Problems with fuuy coefficients, in which we can use fuzzy numbers in both the coefficients of the technological matrix and the coefficients of the right-hand side, with a similar origin to that of the previous case.

Obviously, every combination of the three situations is allowed, [1]. The most general problem, [1], including the three models, may be written as

where now c^f and b^f are vectors of fuzzy numbers and A^f is a matrix of fuzzy coefficients, all of them with appropriated dimensions. Then, in order to maintain the coherence in this fuzzy context, and to formulate the problem in a correct way, two points should be noted, [1].

1. The meaning of (2) is identical to the classic (1), except that now we have introduced imprecise coefficients in the sense already mentioned.
2. As occurs in other FLP problems [11], in (2) the verification of constraints can also be flexible, that is to say, owing to the fuzzy nature of the data of the problem, the decision maker can be prepared to permit certain violations in the accomplishment of these constraints. From this point of view the symbol ≤, noted before, will have to be replaced by ≤^f, which has specific reference to these possible violations. More concretely, we allow the constraints to be violated up to some extent (denoted d^f_i below). Then the degree of accomplishment of the ith fuzzy constraint would be

   μi(x) =

   ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩

   1      if    (Afx)i ≤g bfi mi [(Afx)i]      if    bfi ≤g (Afx)i ≤g bfi+dfi 0      if    (Afx)i ≥g bfi+dfi

where the symbol ≤_g makes explicit reference to the fact that we are comparing fuzzy numbers, and hence we need to do it by using some relation of comparison for fuzzy numbers ≤_g, that has to be in agreement with the decision maker's interests, when it comes to finding the solution to our problem. Usually it is assumed that m_i() ∈ [0,1] is such that the higher the violation of the constraints, the lower the value of m_i.

Therefore, (2) is rewritten more explicitly as, [1,2]

From a formal theoretical point of view, in (3) there are the following membership functions, [1,2]:

1. for each row, constraint, ∃ μ_i ∈ F(ℜ) such that μ_i: ℜ → [0,1], i ∈ M, which defines the fuzzy number in the right hand side;
2. for each i = 1, ..., m and j ∈ N, ∃ μ_ij ∈ F(ℜ) such that μ_ij: ℜ → [0,1], defining the fuzzy numbers in the technological matrix;
3. for each j = 1, ..., n; ∃ μ_j ∈ F(ℜ) such that μ_j: ℜ → [0,1], defining the fuzzy numbers in the objectives function; and
4. for each row, ∃ μⁱ ∈ F(F(ℜ)) such that μⁱ: F(ℜ) → [0,1], which gives, ∀ x in ℜⁿ, the accomplishment degree of the fuzzy number a_i1 x₁ + a_i2 x₂ + ... + a_in x_n, i∈ M with respect to the ith constraint, that is, the adequacy between this fuzzy number and the one b_i with respect to the ith constraint.

As it is evident, the main inconvenience is the presence of fuzziness both in the accomplishment of the constraints, and in the coefficients included in them. In order to avoid this, the constraints in (3) will be changed into more tractable ones, [3]. For this, the fuzzy set (3.2) will be changed into another more conventional fuzzy constraint set, [3].

Let b, d be fuzzy numbers fixed by the decision maker and let g be a fuzzy numbers linear ranking¹ function. We define the following function, m, [1]:

Definition 3: Let m : F(ℜ) × F(ℜ) → F(ℜ) be a function such that

with d^f_i, a fuzzy number in a way that its support is included in ℜ⁺ and ⊕, ⊖ the usual operations between fuzzy numbers [7].          □
Then we can define the membership function of the fuzzy constraints, measuring the user's satisfaction degree of the fuzzy numbers ∑ⁿ_j=1 a^f_ij x_j with respect to fuzzy number b^f_i, as follows, [1].

Definition 4: The membership function associated with the fuzzy constraint a^f_ix ≤^f b^f_i, with d^f_i a fuzzy number giving the maximum violation in the verification of the ith constraint, is

where g is a linear ranking function.          □
If we consider problem (3), ≤^f with membership functions like those in definition 4 and using the decomposition theorem for fuzzy sets [1], we obtain

where ≤_g is the relationship associated to a linear ranking function g.

Also, nonlinear ranking functions g could be used, but then nonlinear constraint sets can be obtained. Because of this we concentrate on the use of the linear ranking functions in the constraint set, [1]. Then, the fuzzy constraint set in (3) may be substituted by a convex fuzzy set, [1]. Thus we can propose as auxiliary problem to solve (3)

Therefore, this problem will be used in the remainder as an intermediate to obtain the optimal fuzzy solution to (3).

This model here presented permits us to deal with problems in which all of its elements, because of some expert's lack of information on the former exact values, are defined as fuzzy sets. The solution methods reported show us that it is possible to solve these problems, for which the experts provide qualitative statements on the parameters involved instead of unknown exact numerical ones. From this perspective the model can be viewed as a first step to build an intelligent decision support system helping to solve optimization problems (even nonlinear ones) addressed in a human consistent linguistic and qualitative way, [1,2].

¹ A simple method for ranking fuzzy numbers consists of the definition of a ranking function mapping each fuzzy number into the real line, g: F(ℜ) → ℜ. If function g() is known, then

Usually, g is called linear ranking function if

1. g(A^f +B^f) = g(A^f) + g(B^f), ∀ A^f,B^f ∈ F(ℜ)
2. g(rA^f) = rg(A^f), r ∈ ℜ, r>0, A^f ∈ F(ℜ)

REFERENCES

[1] J.M. Cadenas, J.L. Verdegay, Probo: an interactive system in fuzzy linear prograrnming. Fuzzy Sets and Systems 76 (1995) 319-332.
[2] J.M. Cadenas, J.L. Verdegay, Using fuzzy numbers in linear programming. IEEE transactions on Systems, Man and Cybernetics, part B., 27 (6) (1997) 1-6.
[3] M. Delgado. JL. Verdegay, M.A. Vila. lmprecise costs in mathematical programming problems. Control Cybernet. 16 (2) (1987) 113-121.
[4] M. Delgado, F. Herrera, J.L. Verdegay, M.A. Vila, Post-optimality analysis on the membership function of a fuzzy linear programming problems, Fuzzy Sets and Systems 53 (1993) 289-297.
[5] M. Delgado, J.L. Verdegay, M.A. Vila (eds), Fuzzy Optimization: Recent advances (Physica Verlag, Germany, 1994).
[6] M. Delgado, J.L. Verdegay, M.A. Vila, Fuzzy numbers: Definitions and properties. Mathware and SoftComputing 1(1) (1994) 31-43.
[7] D. Dubois, H. Prade, Fuzzy Sets and Systems. Theory and Applications (Academic, New York, 1980).
[8] M. Fedrizzi, J. Kacprzyk and J.L. Verdegay, A survey of fuzzy optimization and fuzzy mathematical programming, in: M. Fedrizz, J. Kacprzyk aod M. Roubens, Eds., Interactive Fuzzy Optimization and Mathematical Programming (Springer, Berlin, 1991).
[9] L.A. Zadeh, Fuzzy Sets. Inf. Contr. 8 (1965) 338-353.
[10] L.A. Zadeh, The concept of a linguistic variable and its aplication to approximate reasoning. Parts I and II, Inf. Sci. 8 (1975) 199-249, 301-357; Part III, Inf. Sci. 9 (1975) 43-80.
[11] H.J. Zirnmermann, Fuzzy Sets, Decision Making, and Expert Systems (Kluwer Academic, Boston, 1987).
[12] Q. Zhu, E.S. Lee, Comparison and ranking of fuzzy number, in: J. Kacprzyk and M. Fedrizzi, Eds., Fuzzy Regression Analysis (Omnitech, Germany, 1992).