# Fuzzy clustering with additional information

Witold Pedrycz

► To cite this version:

Witold Pedrycz. Fuzzy clustering with additional information. Bulletin pour les sous-ensembles flous et leurs applications, 1983, 16, pp.96-106. hal-04583365

HAL Id: hal-04583365

https://hal.science/hal-04583365

Submitted on 22 May 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Fuzzy clustering with additional information

Witold Pedrycz

► To cite this version:

Witold Pedrycz. Fuzzy clustering with additional information. Bulletin pour les sous-ensembles flous et leurs applications, 1983, 16, pp.96-106. hal-04583365

HAL Id: hal-04583365

https://hal.science/hal-04583365v1

Submitted on 22 May 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
DUALITY IN FUZZY LINEAR PROGRAMMING

J.L. Verdegay

Departamento de Estadística Matemática

Facultad de Ciencias

Universidad de Granada

GRANADA (SPAIN)

INTRODUCTION.- In this work, we consider, exclusively, two types of possible Fuzzy Linear Programming (FLP) problems:

$$ \begin{array}{ll} \text{Max:} & z = cx \\ \text{s.t:} & 
\end{array} $$

(P1)

$$ \begin{array}{ll} Ax & \leq b \\ x & \geq 0 
\end{array} $$

(with only fuzziness on the constraints) and,

$$ \begin{array}{ll} \text{Max:} & z = cx \\ \text{s.t:} & 
\end{array} $$

(P2)

$$ \begin{array}{ll} Ax & \leq b \\ x & \geq 0 
\end{array} $$

(with a fuzzy objective in the sense of [10]).

Based on the fact that in Fuzzy Mathematical Programming in general, objectives and constraints plays the same role, - [1]: The dual of an FLP problem with fuzzy objective, must be an FLP problem with a fuzzy constraint set, and reciprocally. Essentially, this previous view states that the dual concept of fuzzy constraint is the fuzzy objective, and reciprocally. Nevertheless, the correspondence between FLP problems stated by the above idea of duality is too broad. The following result makes it more definite and states us the form which has the dual of an FLP problem in a more accurate way.
DUALITY IN FUZZY LINEAR PROGRAMMING

J.L. Verdegay

Departamento de Estadística Matemática

Facultad de Ciencias

Universidad de Granada

GRANADA (SPAIN)

INTRODUCTION.- In this work, we consider, exclusively, two types of possible Fuzzy Linear Programming (FLP) problems:

$$ \begin{array}{ll} \text{Max:} & z = cx \\ \text{s.t:} & 
\end{array} $$

(P1)

$$ \begin{array}{l} Ax \leq b \\ x \geq 0 \end{array} $$

(with only fuzziness on the constraints) and,

$$ \begin{array}{ll} \text{Max:} & z = cx \\ \text{s.t:} & 
\end{array} $$

(P2)

$$ \begin{array}{l} Ax \leq b \\ x \geq 0 \end{array} $$

(with a fuzzy objective in the sense of [10]).

Based on the fact that in Fuzzy Mathematical Programming in general, objectives and constraints plays the same role, - [1]: The dual of an FLP problem with fuzzy objective, must be an FLP problem with a fuzzy constraint set, and reciprocally. Essentially, this previous view states that the dual concept of fuzzy constraint is the fuzzy objective, and reciprocally. Nevertheless, the correspondence between FLP problems stated by the above idea of duality is too broad. The following result makes it more definite and states us the form which has the dual of an FLP problem in a more accurate way.
RESULT 1.- Given an FLP problem, P1 or P2, there is always such one that both are dual and, besides, they have the same fuzzy solution.

Proof: Suppose start from an FLP problem such as,

$$
\begin{array}{ll}
\text{Max:} & \mathrm{cx} \\
\text{s.t:} & \\
& A x \leq b \\
& x \geq 0
\end{array}
\qquad (1)
$$

being c∈Rⁿ, b∈Rᵐ and A(m×n) known matrices of real values.

If we state the fuzziness of the constraint set by means
of an m-vector of membership functions µ = (µ₁, ..., µm) given-
by,

$$
\forall v \in \mathbb{R}, \mu_j(v) := \begin{cases} [(b_j+d_j)-v]/d_j & : b_j+d_j \ge v \ge b_j, j=1, \dots, m \\ 1 & : v < b_j \\ 0 & : b_j+d_j < v \end{cases} \quad (2)
$$

where, as usual, the values d_j∈R (j=1,...,m) express the violations which the decision-maker allows in the accomplishment of the linear constraints of (1); we know that the fuzzy solution of (1) is found by obtaining the optimal solution of the linear parametric problem,

$$
\begin{array}{ll}
\text{Max:} & \mathrm{cx} \\
\text{s.t:} & \\
& \mu(\mathbf{Ax}, \mathbf{b}) \ge \alpha \\
& x \ge 0, \quad \alpha \in [0, 1]
\end{array}
$$

But, according to (2),

$$
\mu(\mathbf{Ax}, \mathbf{b}) \ge \alpha \leftrightarrow \mathbf{Ax} \le \mathbf{b} + \mathbf{d}(1-\alpha)
$$

the whole expressed in a matrix form.

Therefore, we have

$$
\begin{array}{ll}
\text{Max:} & \mathrm{cx} \\
\text{s.t:} & \\
& Ax \leq b + d(1-\alpha) \\
& x \geq 0, \quad \alpha \in [0, 1]
\end{array}
\qquad (3)
$$

As this problem is a classical parametric linear programming
RESULT 1.- Given an FLP problem, P1 or P2, there is always -
such one that both are dual and, besides, they ha-
ve the same fuzzy solution.

Proof: Suppose start from an FLP problem such as,

$$
\begin{array}{ll}
\text{Max:} & \mathrm{cx} \\
\text{s.t:} & \\
\quad & A_x \le b \\
\quad & x \ge 0
\end{array}
\qquad (1)
$$

being c∈Rⁿ, b∈Rᵐ and A(m×n) known matrices of real values.

If we state the fuzziness of the constraint set by means
of an m-vector of membership functions µ = (µ₁, ..., µm) given-
by,

$$
\forall v \in \mathbb{R}, \mu_j(v) := \begin{cases} \frac{[(b_j+d_j)-v]}{d_j} & : b_j+d_j \ge v \ge b_j, j=1, \dots, m \\ 1 & : v < b_j \\ 0 & : b_j+d_j < v \end{cases} \quad (2)
$$

where, as usual, the values d_j∈R (j=1,...,m) express the violations which the decision-maker allows in the accomplishment of the linear constraints of (1); we know that the fuzzy solution of (1) is found by obtaining the optimal solution of the linear parametric problem,

$$
\begin{array}{ll}
\text{Max:} & \mathrm{cx} \\
\text{s.t:} & \\
\mu(\mathrm{Ax}, \mathrm{b}) & \geq \alpha \\
\mathrm{x} & \geq 0, \alpha \in [0, 1]
\end{array}
$$

But, according to (2),

$$
\mu(\mathbf{Ax}, \mathbf{b}) \ge \alpha \leftrightarrow \mathbf{Ax} \le \mathbf{b} + \mathbf{d}(1-\alpha)
$$

the whole expressed in a matrix form.

Therefore, we have

$$
\begin{array}{ll}
\text{Max:} & \mathrm{cx} \\
\text{s.t:} & \\
\quad & Ax \leq b + d(1-\alpha) \\
\quad & x \geq 0, \quad \alpha \in [0, 1]
\end{array}
\qquad (3)
$$

As this problem is a classical parametric linear programming
problem, its dual is given by,

$$
\begin{array}{ll}
\text{Min:} & [b + d(1-\alpha)] \cdot u \\
\text{s.t:} & uA' \geq c \\
& u \geq 0, \alpha \in [0,1]
\end{array}
\qquad (4)
$$

If,

$$
Y = \{ u \in \mathbb{R}^m / \ uA' \geq c, u \geq 0 \}
$$

we have,

$$
\begin{array}{ll}
\text{Min:} & au \\
\text{s.t:} & a = b + d(1-\alpha) \\
& u \in Y, \alpha \in [0,1]
\end{array}
\qquad (5)
$$

taking $\beta=1-\alpha$, this problem is equivalent to

$$
\begin{array}{ll}
\text{Min:} & \text{au} \\
\text{s.t:} & a \le b + d(1-\alpha) \\
& u \in Y, \alpha \in [0,1]
\end{array}
\qquad (6)
$$

understanding the equivalence in the sense that every optimal
solution of (5) is also an optimal solution of (6).

But as,

$$
a_j \le b_j + d_j \beta \leftrightarrow (b_j + d_j - a_j) / d_j \ge 1 - \beta, \quad j=1, \dots, m
$$

(6) may be rewritten as,

$$
\begin{array}{ll}
\text{Min:} & \text{au} \\
\text{s.t:} & \mu_j (a_j) \geq 1-\beta, \quad j=1, \dots, m \\
& u \in Y, \quad \alpha \in [0,1]
\end{array}
\qquad (7)
$$

being $\mu_j(\cdot)$ given by (2). Thus, (7) is an FLP problem with fuzzy objective,

$$
\begin{array}{ll}
\text{Min:} & \text{au} \\
\text{u} & \in Y
\end{array}
\qquad (8)
$$

with membership functions in the objective coefficients given
by (2). Furthermore, this FLP problem has the same fuzzy solu-
tion as (1), only by means of taking $\beta=1-\alpha$.
problem, its dual is given by,

$$
\begin{array}{ll}
\text{Min:} & [b + d(1-\alpha)] \cdot u \\
\text{s.t:} & uA' \geq c \\
& u \geq 0, \alpha \in [0,1]
\end{array}
\qquad (4)
$$

If,

$$
Y = \{ u \in \mathbb{R}^m / \ uA' \geq c, u \geq 0 \}
$$

we have,

$$
\begin{array}{ll}
\text{Min:} & au \\
\text{s.t:} & a = b + d(1-\alpha) \\
& u \in Y, \alpha \in [0,1]
\end{array}
\qquad (5)
$$

taking $\beta=1-\alpha$, this problem is equivalent to

$$
\begin{array}{ll}
\text{Min:} & \text{au} \\
\text{s.t:} & a \le b + d(1-\alpha) \\
& u \in Y, \alpha \in [0,1]
\end{array}
\qquad (6)
$$

understanding the equivalence in the sense that every optimal
solution of (5) is also an optimal solution of (6).

But as,

$$
a_j \le b_j + d_j \beta \leftrightarrow (b_j + d_j - a_j) / d_j \ge 1 - \beta, \quad j=1, \dots, m
$$

(6) may be rewritten as,

$$
\begin{array}{ll}
\text{Min:} & \text{au} \\
\text{s.t:} & \mu_j(a_j) \ge 1-\beta, \quad j=1, \dots, m \\
& u \in Y, \quad \alpha \in [0,1]
\end{array}
\qquad (7)
$$

being $\mu_j(\cdot)$ given by (2). Thus, (7) is an FLP problem with fuzzy objective,

$$
\begin{array}{ll}
\text{Min:} & \text{au} \\
\text{u} & \in Y
\end{array}
\qquad (8)
$$

with membership functions in the objective coefficients given
by (2). Furthermore, this FLP problem has the same fuzzy solu-
tion as (1), only by means of taking $\beta=1-\alpha$.
If we had initially started from a P2 FLP problem, developing it, in relation to the previous one, in a parallel -- way, we should have come to a P1 FLP problem with the same fuzzy solution as the one taken from the very start.

REMARK. - Taking into account this result, whenever the membership functions which take part in the statement of - the problem be like (2), we may define the dual of an FLP problem given by (1), as (7), or reciprocally, the dual of (8) - as problem (3).

However, it seems that a good definition of the dual problem may only be stated in similar cases to the previous one, i.e., with linear membership functions. Now we shall see that under little restrictive hypotheses, the above result is easily applied in general.

RESULT 2. - Given an P1 (P2) FLP problem with membership functions $\mu(\cdot) = [\mu_i(\cdot), \dots, \mu_m(\cdot)]$ for the restrictions (costs), if these are continuous and strictly monotones, - either increasing or decreasing following the sense of the inequalities (depending on whether it maximizes or minimizes), there exists always another P2 (P1) FLP problem, dual of the former, and of such a kind that both possess the same fuzzy - solution.

Proof: Let,

$$ \mu_j: R \rightarrow [0,1], \quad j = 1, \dots, m $$

be continuous and strictly increasing functions for the FLP - problem,

$$ \begin{array}{ll} \text{Max:} & \text{cx} \\ \text{s.t:} & \end{array} $$

$$ \begin{array}{l} Ax < b \\ x \ge 0 \end{array} $$

we shall find their fuzzy solution from every α-cut of the fuzzy constraint set,

$$ \mu(Ax, b) \ge \alpha, \quad \alpha \in [0, 1] $$

But according to the hypotheses,
If we had initially started from a P2 FLP problem, developing it, in relation to the previous one, in a parallel -- way, we should have come to a P1 FLP problem with the same fuzzy solution as the one taken from the very start.

REMARK. - Taking into account this result, whenever the membership functions which take part in the statement of - the problem be like (2), we may define the dual of an FLP problem given by (1), as (7), or reciprocally, the dual of (8) - as problem (3).

However, it seems that a good definition of the dual problem may only be stated in similar cases to the previous one, i.e., with linear membership functions. Now we shall see that under little restrictive hypotheses, the above result is easily applied in general.

RESULT 2. - Given an P1 (P2) FLP problem with membership functions $\mu(\cdot) = [\mu_i(\cdot), \dots, \mu_m(\cdot)]$ for the restrictions (costs), if these are continuous and strictly monotones, - either increasing or decreasing following the sense of the inequalities (depending on whether it maximizes or minimizes), there exists always another P2 (P1) FLP problem, dual of the former, and of such a kind that both possess the same fuzzy - solution.

Proof: Let,

$$ \mu_j: R \rightarrow [0,1], \quad j = 1, \dots, m $$

be continuous and strictly increasing functions for the FLP - problem,

$$ \begin{array}{ll} \text{Max:} & \text{cx} \\ \text{s.t:} & \end{array} $$

$$ \begin{array}{l} Ax < b \\ x \ge 0 \end{array} $$

we shall find their fuzzy solution from every α-cut of the fuzzy constraint set,

$$ \mu(Ax, b) \ge \alpha, \quad \alpha \in [0, 1] $$

But according to the hypotheses,
$$ \mu(Ax,b) \geq \alpha \iff Ax \leq \psi(\alpha) = \mu^{-1}(\alpha) $$

and the proof it follows as in the Result 1.

**CONCLUDING REMARKS.** The linearity of FLP problems which have been considered, is never lost by the -- special form which the membership functions may have, even if these are non linear. This fact is only related to the pa- rameter used, therefore the linearity of the problem is not a ffected.

The most important uselfuness derived from the dual rela- tionship which has been shown in this work, lies in the abili- ty of solving problems with fuzzy constraint set without le- tting this fuzziness affect said set. This can be obtained by mean of the dual, which make easy the problem.

**REFERENCES.**

[1]. R. BELLMAN and L.A. ZADEH: Decision Making in a Fuzzy En- vironment. Man. Sci., 17 (1970), 141-164.

[2]. D. DUBOIS and H. PRADE: Fuzzy Sets and Systems: Theory - and Applications (Academic Press, 1980)

[3]. T. GAL: Postoptimal Analyses, Parametric Programming and Related Topics (McGraw Hill, 1979)

[4]. J.A. GOGUEN: L-Fuzzy Sets. J. Math. Anal. and Appl., 18- (1967) 145-174.

[5]. H. HAMACHER, H. LEBERLING and H.J. ZIMMERMANN: Sensitivi- ty Analysis in Fuzzy Linear Programming, Fuzzy Sets and- Systems, 1 (1978), 269-281.

[6]. G. KABBARA: New Utilization of Fuzzy Optimization Method in M.M Gupta and E. Sanchez (Eds) Fuzzy Information and- decision Processes (North-Holland, 1982) 239-246.

[7]. C.V. NEGOITA and D.A. RALESCU: Applications of Fuzzy Set to Systems Analysis (Birkhauser Verlag, 1975)

[8]. W. RODDER and H.J. ZIMMERMANN: Duality in Fuzzy Progra- mining. Int. Symp. on Extremal Methods and Systems Analy- sis. University of Texas, Austin, Sept (1977).

[9]. J.L. VERDEGAY: Fuzzy Mathematical Programming, in M.M. - Gupta and E. Sanchez (Eds) Fuzzy Information and Decisi- on Processes (North-Holland 1982) 231-237.

[10]. J.L. VERDEGAY: Solving the Mathematical Programming Pro- blem with a New Formulation of Fuzzy Objective. To appe- ar in BUSEFAL.
$$ \mu(Ax,b) \geq \alpha \iff Ax \leq \psi(\alpha) = \mu^{-1}(\alpha) $$

and the proof it follows as in the Result 1.

**CONCLUDING REMARKS.** The linearity of FLP problems which have been considered, is never lost by the -- special form which the membership functions may have, even if these are non linear. This fact is only related to the pa- rameter used, therefore the linearity of the problem is not a ffected.

The most important uselfuness derived from the dual rela- tionship which has been shown in this work, lies in the abili- ty of solving problems with fuzzy constraint set without le- tting this fuzziness affect said set. This can be obtained by mean of the dual, which make easy the problem.

**REFERENCES.**

[1]. R. BELLMAN and L.A. ZADEH: Decision Making in a Fuzzy En- vironment. Man. Sci., 17 (1970), 141-164.

[2]. D. DUBOIS and H. PRADE: Fuzzy Sets and Systems: Theory - and Applications (Academic Press, 1980)

[3]. T. GAL: Postoptimal Analyses, Parametric Programming and Related Topics (McGraw Hill, 1979)

[4]. J.A. GOGUEN: L-Fuzzy Sets. J. Math. Anal. and Appl., 18- (1967) 145-174.

[5]. H. HAMACHER, H. LEBERLING and H.J. ZIMMERMANN: Sensitivi- ty Analysis in Fuzzy Linear Programming, Fuzzy Sets and- Systems, 1 (1978), 269-281.

[6]. G. KABBARA: New Utilization of Fuzzy Optimization Method in M.M Gupta and E. Sanchez (Eds) Fuzzy Information and- decision Processes (North-Holland, 1982) 239-246.

[7]. C.V. NEGOITA and D.A. RALESCU: Applications of Fuzzy Set to Systems Analysis (Birkhauser Verlag, 1975)

[8]. W. RODDER and H.J. ZIMMERMANN: Duality in Fuzzy Progra- mining. Int. Symp. on Extremal Methods and Systems Analy- sis. University of Texas, Austin, Sept (1977).

[9]. J.L. VERDEGAY: Fuzzy Mathematical Programming, in M.M. - Gupta and E. Sanchez (Eds) Fuzzy Information and Decisi- on Processes (North-Holland 1982) 231-237.

[10]. J.L. VERDEGAY: Solving the Mathematical Programming Pro- blem with a New Formulation of Fuzzy Objective. To appe- ar in BUSEFAL.