约束条件为sec-max-min模糊关系不等式的Min-Max优化模型

Min-Max Optimization Model with sec-max-min Fuzzy Relation Inequality Constraints

摘要: 首先引入sec-max-min模糊关系不等式的定义，第二得到了sec-max-min模糊关系不等式解的判别条件和解的结构，最后给出了求解约束条件为sec-max-min模糊关系不等式的min-max优化模型的解法和算法。

Abstract: Firstly, the definition of the sec-max-min fuzzy relational inequality is introduced. Secondly, the discriminant conditions and solution structure of the sec-max-min fuzzy relation inequality are derived. Finally, the solution method and algorithm for the min-max optimization model with sec-max-min fuzzy relational inequalities as constraints are presented.

1. 引言

为了描述事物之间的模糊隶属关系，研究模糊不确定性的现象，1965年美国加利福尼亚大学著名的控制论专家L. A. Zadeh创造性地提出了模糊集的概念[1]。基于L. A. Zadeh的模糊集的概念，1976年法国数学家、生物学家E. Sanchez引入了含max-min合成算子的模糊关系方程[2]，并在生物医疗诊断领域得到了成功的应用[3]。随后在大量研究学者的不断努力下，模糊关系系统不但在理论上取得长足的发展，而且也在知识工程[4]、图像处理[5]、模糊逻辑[6]、工业管理[7]、网络信息传输系统[8]等方面也得到了广泛的应用。

不同于一般经典的矩阵方程，相容的max-min模糊关系方程的解集是一个非凸集，其由方程最大解和有限个极小解完全确定[3]。求解max-min模糊关系方程的最大解是一个容易的事情，但是相关的研究表明，求解所有的极小解却是一个NP困难问题[9] [10]。这给max-min模糊关系方程理论的发展和实际应用带来了不小的困扰。这给max-min模糊关系方程理论的发展和实际应用带来了不小的困扰。E. Czogala等[11]尝试引入拟极小解的概念并设计了在拟极小解集合中逐步挑选极小解的技术方法。后来有学者发现E. Czogala等人的方法存在缺陷，会产生一定量的重复计算工作，严重影响求解极小解效率。为了消除这个缺陷，我国著名模糊学专家汪培庄等[12]提出了著名的求解各类模糊关系方程的经典方法——保守路径法。

目前除了经典的max-T模糊关系系统，基于不同应用背景的含不同合成算子的模糊关系系统也迅速发展起来，例如sup-inf模糊关系系统，addition-min模糊关系系统、min-product模糊关系系统、max-average模糊关系系统等等。这些新的模糊关系系统的理论研究还不是很完善，其解集结构和性质也与经典的max-T模糊关系系统有所不同，有些只是初步探讨解集的一些简单的性质和结构，很多问题还有待进一步研究。

基于应用的需要，模糊关系系统理论的另一个研究的重点内容是模糊关系优化模型，即约束条件为模糊关系系统的数学规划。包括线性规划模型和非线性规划模型。1991年，汪培庄等[13]就提出了约束条件为max-min模糊系统的模糊关系格化线性规划，并给出了基于保守路径法求解极小解集的最优解的求解方法。1999年，方述成[13]给出了解决线性规划模型的二分子问题法。同时为了避免求解极小解集的困难点，[13]引入分支定界法求解含max-min算子的线性规划模型的最优解，大大地提高了求解的效率。近年来非线性模糊规划问题的研究也日益增多。非线性模糊规划问题的解的可行域一般是非凸集，而且目标函数是非线性的，目前没有统一的求解方法，都是根据各自的目标函数的特点，设计相应的可行的算法进行求解。

由于数据收集和处理过程中会产生误差、噪音以及随机缺失，经典的含max-min合成算子的模糊关系系统有时无法准确描述生物医疗诊断领域出现的一些新现象，为消除这个影响，我们引入一类新型的sec-max-min模糊关系不等式：

$\{\begin{array}{c}\sec -\max \{a_{11}\wedge x_1,a_{12}\wedge x_2,\cdots ,a_{1n}\wedge x_n\}\ge b_1\\ \sec -\max \{a_{21}\wedge x_1,a_{22}\wedge x_2,\cdots ,a_{2n}\wedge x_n\}\ge b_2\\ \cdots \cdots \\ \sec -\max \{a_{m1}\wedge x_1,a_{m2}\wedge x_2,\cdots ,a_{mn}\wedge x_n\}\ge b_m\end{array}$ (1)

其中，$a_{ij},\begin{array}{c}{b}_i,x_j\end{array}\in \left[0,1\right],a_{ij}\wedge x_j=\min \left\{a_{ij},x_j\right\},\forall 1\le i\le m,1\le j\le n.$

函数$\sec -\max \left(x\right)$ 的定义如下[14]：对任意向量$x=\left(x_1,x_2,\cdots ,x_n\right)$ ，将分量序列$x_1,x_2,\cdots ,x_n$ ，按非严格递减的大小顺序重新排列为$x_{j1}\ge x_{j2}\ge \cdots \ge x_{jn}$ ，其中序列$j_1,j_2,\cdots ,j_n$ 是序列$1,2,\cdots ,n$ 的一个排列。定义

$\begin{array}{l}\sec -\max \left(x\right)=\sec -\max \left\{x_1,x_2,\cdots ,x_n\right\}=x_{j2}\\ \sec -\min \left(x\right)=\sec -\max \left\{x_1,x_2,\cdots ,x_n\right\}=x_{j2}\end{array}$ .

称矩阵

$A=\left[\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{m1}& a_{m2}& \cdots & a_{mn}\end{array}\right],$

为系统(1.1)的系数矩阵，而向量$b={[b_1,b_2,\cdots ,b_n]}^T$ 为系统(1.1)的常数列。

类似于一般的模糊关系系统，为了增强系统(1.1)的解的稳定性，我们考虑如下的min-max优化问题：

$\begin{array}{l}\min \begin{array}{c}\end{array}z\left(x\right)=x_1\vee x_2\vee \cdots \vee x_n\\ s.t.\begin{array}{c}\end{array}\{\begin{array}{c}\sec -\max \left\{a_{11}\wedge x_1,a_{12}\wedge x_2,\cdots ,a_{1n}\wedge x_n\right\}\ge b_1\\ \sec -\max \left\{a_{21}\wedge x_1,a_{22}\wedge x_2,\cdots ,a_{2n}\wedge x_n\right\}\ge b_2\\ \cdots \cdots \\ \sec -\max \left\{a_{m1}\wedge x_1,a_{m2}\wedge x_2,\cdots ,a_{mn}\wedge x_n\right\}\ge b_m\end{array}\end{array}$ (2)

2. 系统(1.1)的解的判断与结构

这一节，主要给出系统(1.1)的解的判断条件和解的结构。为了方便记号，记$I=\left\{1,2,\cdots ,n\right\},J=\left\{1,2,\cdots ,m\right\}$ .

定义2.1 若向量$y=\left(y_1,y_2,\cdots ,y_n\right)\in {\left[0,1\right]}^n$ 满足系统(1.1)，即

$\{\begin{array}{l}\text{sec-max}\left\{a_{11}\wedge y_1,a_{12}\wedge y_2,\cdots ,a_{1n}\wedge y_n\right\}\ge b_1\\ \text{sec-max}\left\{a_{21}\wedge y_1,a_{22}\wedge y_2,\cdots ,a_{2n}\wedge y_n\right\}\ge b_2\\ ⋮\\ \text{sec-max}\left\{a_{m1}\wedge y_1,a_{m2}\wedge y_2,\cdots ,a_{mn}\wedge y_n\right\}\ge b_m\end{array}$

则称$y=\left(y_1,y_2,\cdots ,y_n\right)$ 是系统(1.1)的一个解。记$S\left(A,b\right)$ 为系统(1.1)的所有解组成的集合。

设$i\in I$ ，若$b_i=0$ ，则不等式$\text{sec-max}\left\{a_{i1}\wedge x_1,a_{i2}\wedge x_2,\cdots ,a_{in}\wedge x_n\right\}\ge b_i$ 的解集为${\left[0,1\right]}^n$ 。因此，我们可以去掉系统(1.1)中的第$i$ 个不等式而不影响整个系统的解集。故而在下文中我们总是假设对任意的$1\le i\le m$ ，有$b_i>0$ 。

引理2.2 系统(1.1)有解当且仅当对任意的$i\in I$ ，有$\left|I_i\right|=\left|\left\{j|j\in J,a_{ij}\ge b_i\right\}\right|\ge 2$ 。

证明：根据系统(1.1)解的定义，容易验证该引理成立。

定义2.3 设$x=\left(x_1,x_2,\cdots ,x_n\right),y=\left(y_1,y_2,\cdots ,y_n\right)\in {\left[0,1\right]}^n$ ，若$x_j\ge y_j,\forall 1\le j\le n$ ，则称$x\ge y$ 。如果$x\ge y$ 且$x\ne y$ ，则记$x>y$ 。类似的我们可以定义$x\le y$ 和$x<y$ 。

定义2.4 系统(1.1)的解$x\in S\left(A,b\right)$ 称为系统(1.1)的一个最大解，如果对所有的$y\in S\left(A,b\right)$ ，都有$x\ge y$ 。如果若$y\le x,y\in S\left(A,b\right)$ ，都有$y=x$ ，则称$x$ 是系统(1.1)的一个极小解。

引理2.5 系统(1.1)有解当且仅当$\widehat{x}=\left(1,1,\cdots ,1\right)$ 是系统(1.1)的解。故而，若系统(1.1)有解，则$\widehat{x}=\left(1,1,\cdots ,1\right)$ 是系统(1.1)的最大解。

证明：(必要性)若系统(1.1)有解$y=\left(y_1,y_2,\cdots ,y_n\right)\in {\left[0,1\right]}^n$ ，则对任意的$1\le i\le m$ ，

$\text{sec-max}\left\{a_{i1}\wedge y_1,a_{i2}\wedge y_2,\cdots ,a_{in}\wedge y_n\right\}\ge b_i.$

由于$\left(y_1,y_2,\cdots ,y_n\right)\le \left(1,1,\cdots ,1\right)$ ，有$a_{ij}\wedge 1\ge a_{ij}\wedge y_j$ ，$1\le j\le n$ ，因此，

$\text{sec-max}\left\{a_{i1}\wedge 1,a_{i2}\wedge 1,\cdots ,a_{in}\wedge 1\right\}\ge \text{sec-max}\left\{a_{i1}\wedge ,a_{i2}\wedge y_2,\cdots ,a_{in}\wedge y_n\right\}\ge b_i,$

因此$\widehat{x}=\left(1,1,\cdots ,1\right)$ 是系统(1.1)的一个解。

(充分性)结论是显然的。

引理2.6 如果$x^{\left(1\right)}\le x^{\left(2\right)}$ 都是系统(1.1)的解，若$y\in {\left[0,1\right]}^n,x^{\left(1\right)}\le y\le x^{\left(2\right)}$ ，则$y$ 也是系统(1.1)的一个解。

证明：容易验证该结论成立。

定理2.7 (系统(1.1)解的结构)设$\stackrel{\vee }{S}$ 是系统(1.1)所有极小解组成的集合，若系统(1.1)有解，则系统(1.1)的解集为

$S\left(A,b\right)=\underset{\stackrel{\vee }{x}\in \stackrel{\vee }{S}}{\cup }\left[\stackrel{\vee }{x},\stackrel{\wedge }{x}\right].$

证明：由引理2.5和引理2.6可得结论成立。

由定理2.7，要求出系统(1.1)的所有解，只要求出它的所有极小解。类似于max-min模糊关系系统，要求出系统(1.1)的所有极小解并不容易。

下面我们给出系统(1.1)的一种特殊的解，称为系统(1.1)的矩阵解。

定义2.8 (判别矩阵)称矩阵$D={\left(d_{ij}\right)}_{m\times n}$ ，其中对任意的$1\le i\le m,1\le j\le n$ ，

$d_{ij}=\{\begin{array}{l}{a}_{ij},如果a_{ij}\ge b_i\\ 0,如果a_{ij}<b_i\end{array}$

为系统(1.1)的判别矩阵。

定理2.9 系统(1.1)有解当且仅当对任意的$1\le i\le n$ ，集合$D_i=\left\{d_{ij}|d_{ij}\ne 0,1\le j\le n\right\}$ 至少有两个元素。

证明：由引理2.2和引理2.5，可得结论成立。

定义2.10 称矩阵$K={\left(k_{ij}\right)}_{m\times n}$ 为矩阵$L={\left(l_{ij}\right)}_{m\times n}$ 的子矩阵，如果对任意的$1\le i\le m,1\le j\le n$ ，有$k_{ij}\in \left\{l_{ij}\right\}\cup \left\{0\right\}$ 。

定义2.11 设矩阵$\tilde{D}={\left({\tilde{d}}_{ij}\right)}_{m\times n}$ 是判别矩阵$D={\left(d_{ij}\right)}_{m\times n}$ 的一个子矩阵。如果对任意的$1\le i\le m$ ，矩阵$\tilde{D}$ 的第$i$ 行${\tilde{D}}_i$ 中的非零元素个数都是2，则称$\tilde{D}={\left({\tilde{d}}_{ij}\right)}_{m\times n}$ 是系统(1.1)的一个解矩阵。

定理2.12 设矩阵$\tilde{D}={\left({\tilde{d}}_{ij}\right)}_{m\times n}$ 是系统(1.1)的一个解矩阵。则向量

$x^{\tilde{D}}=\left(x_1^{\tilde{D}},x_2^{\tilde{D}},\cdots ,x_n^{\tilde{D}}\right)=\left(\underset{1\le i\le m}{\max }\left({\tilde{d}}_{i1}\right),\underset{1\le i\le m}{\max }\left({\tilde{d}}_{i2},\right)\cdots ,\underset{1\le i\le m}{\max }\left({\tilde{d}}_{in}\right)\right)$

是系统(1.1)的一个解。

证明：由已知条件可知，对任意的$1\le i\le m$ ，存在$1\le j_{i1}<j_{i2}\le n$ 使得

${\tilde{d}}_{i{j}_{i1}}=a_{i{j}_{i1}}\ge b_i,{\tilde{d}}_{i{j}_{i2}}=a_{i{j}_{i2}}\ge b_i,{\tilde{d}}_{ij}=0,1\le j\le n,j\notin \left\{j_{i1},j_{i2}\right\}.$

故而

$\begin{array}{l}\text{sec-max}\left\{a_{i1}\wedge x_1^{\tilde{D}},a_{i2}\wedge x_2^{\tilde{D}},\cdots ,a_{in}\wedge x_n^{\tilde{D}}\right\}\\ \ge \sec -\max \left\{a_{i{j}_{i1}}\wedge x_{j_{i1}}^{\tilde{D}},a_{i{j}_{i2}}\wedge x_{j_{i2}}^{\tilde{D}}\right\}\\ =\text{sec-max}\left\{a_{i{j}_{i1}}\wedge \underset{1\le t\le m}{\max }\left({\tilde{d}}_{t{j}_{i1}}\right),a_{i{j}_{i2}}\wedge \underset{1\le t\le m}{\max }\left({\tilde{d}}_{t{j}_{i2}}\right)\right\}\\ \ge \text{sec-max}\left\{a_{i{j}_{i1}}\wedge {\tilde{d}}_{i{j}_{i1}},a_{i{j}_{i2}}\wedge {\tilde{d}}_{i{j}_{i2}}\right\}\\ \ge \text{sec-max}\left\{a_{i{j}_{i1}}\wedge a_{i{j}_{i1}},a_{i{j}_{i2}}\wedge a_{i{j}_{i2}}\right\}\\ =\text{sec-max}\left\{a_{i{j}_{i1}},a_{i{j}_{i2}}\right\}\ge b_i.\end{array}$

因此，向量

$x^{\tilde{D}}=\left(x_1^{\tilde{D}},x_2^{\tilde{D}},\cdots ,x_n^{\tilde{D}}\right)=\left(\underset{1\le i\le m}{\max }\left({\tilde{d}}_{i1}\right),\underset{1\le i\le m}{\max }\left({\tilde{d}}_{i2},\right)\cdots ,\underset{1\le i\le m}{\max }\left({\tilde{d}}_{in}\right)\right)$

是系统(1.1)的一个解。

如果系统(1.1)可解，我们称

$x^{\tilde{D}}=\left(x_1^{\tilde{D}},x_2^{\tilde{D}},\cdots ,x_n^{\tilde{D}}\right)=\left(\underset{1\le i\le m}{\max }\left({\tilde{d}}_{i1}\right),\underset{1\le i\le m}{\max }\left({\tilde{d}}_{i2},\right)\cdots ,\underset{1\le i\le m}{\max }\left({\tilde{d}}_{in}\right)\right)$

是系统(1.1)的一个矩阵解。

3. 优化模型(1.2)的最优解

这一节，主要给出优化模型(1.2)的解法和求解算法。

定义3.1 称矩阵$Q={\left(q_{ij}\right)}_{m\times n}$ ，其中对任意的$1\le i\le m,1\le j\le n$ ，

$q_{ij}=\{\begin{array}{l}{b}_i,如果a_{ij}\ge b_i\\ 0,如果a_{ij}<b_i\end{array}$

为系统(1.1)的标记判别矩阵。

由定理2.10可得到系统(1.1)有解当且仅当对任意的$1\le i\le n$ ，集合$Q_i=\left\{q_{ij}|q_{ij}\ne 0,1\le j\le n\right\}$ 至少有两个元素。

定义3.2 设矩阵$\tilde{Q}={\left({\tilde{q}}_{ij}\right)}_{m\times n}$ 是判别矩阵$Q={\left(q_{ij}\right)}_{m\times n}$ 的一个子矩阵。如果对任意的$1\le i\le m$ ，矩阵$\tilde{Q}$ 的第$i$ 行${\tilde{Q}}_i$ 中的非零元素个数都是2，则称$\tilde{Q}={\left({\tilde{q}}_{ij}\right)}_{m\times n}$ 是系统(1.1)的一个标记解矩阵。

定理3.3 假设系统(1.1)有解。设矩阵$\tilde{Q}={\left({\tilde{q}}_{ij}\right)}_{m\times n}$ 是系统(1.1)的一个标记解矩阵。则向量

$x^{\tilde{Q}}=\left(x_1^{\tilde{Q}},x_2^{\tilde{Q}},\cdots ,x_n^{\tilde{Q}}\right)=\left(\underset{1\le i\le m}{\max }\left({\tilde{q}}_{i1}\right),\underset{1\le i\le m}{\max }\left({\tilde{q}}_{i2}\right),\cdots ,\underset{1\le i\le m}{\max }\left({\tilde{q}}_{in}\right)\right)$

是系统(1.1)的一个解。

证明：类似定理2.12可证。

定理3.4 设$y={\left(y_j\right)}_n$ 是系统(1.1)的一个解，则存在标记解矩阵$\tilde{Q}$ 使得$x^{\tilde{Q}}\le y$ 。

证明：因为$y={\left(y_j\right)}_n$ 是系统(1.1)的一个解，所以由引理2.2，可得对任意的$1\le i\le m$ ，存在$1\le j_{i1}<j_{i2}\le n$ 使得$a_{i{j}_{i1}}\wedge y_{j_{i1}},a_{i{j}_{i2}}\wedge y_{j_{i2}}\ge b_i$ 。故而$a_{i{j}_{i1}},a_{i{j}_{i2}},y_{j_{i1}},y_{j_{i2}}\ge b_i>0$ 。令$\tilde{Q}={\left({\tilde{q}}_{ij}\right)}_{m\times n}$ ，其中对任意的$1\le i\le m,1\le j\le n$ ，

${\tilde{q}}_{ij}=\{\begin{array}{ll}{b}_i,\hfill & 如果j=j_{i1},j_{i2}\hfill \\ 0,\hfill & 其他情况\hfill \end{array}$

令

$y^{\tilde{Q}}=\left(y_1^{\tilde{Q}},y_2^{\tilde{Q}},\cdots ,y_n^{\tilde{Q}}\right)=\left(\underset{1\le i\le m}{\max }\left({\tilde{q}}_{i1}\right),\underset{1\le i\le m}{\max }\left({\tilde{q}}_{i2}\right),\cdots ,\underset{1\le i\le m}{\max }\left({\tilde{q}}_{in}\right)\right)$

下证$y^{\tilde{Q}}\le y$ 。这是因为对任意的$j\in J$ ，由定义有

${\tilde{q}}_{ij}\le x_j,j=j_{i1},j_{i2},{\tilde{q}}_{ij}=0,j\ne j_{i1},j_{i2},$

故而，

$\begin{array}{c}{y}_j^{\tilde{Q}}=\underset{1\le i\le m}{\max }\left\{{\tilde{q}}_{ij}\right\}=\underset{i\in I,j=j_{i1}}{\max }\left\{{\tilde{q}}_{ij}\right\}\vee \underset{i\in I,j=j_{i2}}{\max }\left\{{\tilde{q}}_{ij}\right\}\vee \underset{i\in I,j\notin \left\{j_{i1},j_{i2}\right\}}{\max }\left\{{\tilde{q}}_{ij}\right\}\\ =\underset{i\in I,j=j_{i1}}{\max }\left\{{\tilde{q}}_{ij}\right\}\vee \underset{i\in I,j=j_{i2}}{\max }\left\{{\tilde{q}}_{ij}\right\}\le x_j.\end{array}$

定义3.5 设$x$ 是系统(1.1)的一个解，如果对系统(1.1)的任一个解$y$ ，有$z\left(x\right)\le z\left(y\right)$ ，则称$x$ 是优化模型(1.2)的一个最优解。

定理3.6 假设系统(1.1)有解。设$C^{\vee }={\left(c_{ij}^{\vee }\right)}_{m\times n}$ 是系统(1.1)的一个标记解矩阵，则向量

$x^{{}_{C^{\vee }}}={\left(x_j^{C^{\vee }}\right)}_n=\left(\underset{1\le i\le m}{\max }\left(c_{i1}^{\vee }\right),\underset{1\le i\le m}{\max }\left(c_{i2}^{\vee }\right),\cdots ,\underset{1\le i\le m}{\max }\left(c_{in}^{\vee }\right)\right)$

是优化模型(1.2)的一个的一个最优解。

证明：由定理3.4可知，$x^{C^{\vee }}$ 是系统(1.1)的一个解。下证$x^{C^{\vee }}$ 是系统(1.2)的一个最优解，即证对任意的$y\in S\left(A,b\right)$ 有$z\left(y\right)\le z\left(x^{C^{\vee }}\right)$ 。由定理3.4，对任意的$y\in S\left(A,b\right)$ ，存在标记解矩阵$\tilde{Q}$ 使得$x^{\tilde{Q}}\le y$ 。故而$z\left(y\right)\le z\left(x^{\tilde{Q}}\right)$ 。因此，我们只需要验证对任意的标记解矩阵$\tilde{Q}$ ，有$z\left(x^{C^{\vee }}\right)\le z\left(x^{\tilde{Q}}\right)$ 。

设$\tilde{Q}={\left({\tilde{q}}_{ij}\right)}_{m\times n}$ 是一个标记解矩阵，由标记解矩阵的定义直接计算可得

$z\left(x^{\tilde{Q}}\right)=\underset{1\le j\le m}{\max }\underset{1\le i\le m}{\max }\left\{{\tilde{q}}_{ij}\right\}=\underset{1\le i\le m}{\max }\left\{b_i\right\}=z\left(x^{C^{\vee }}\right).$

因此$x^{C^{\vee }}$ 是优化模型(1.2)的一个最优解，最优值为$v_{opt}=\underset{1\le i\le m}{\max }\left\{b_i\right\}$ 。

根据上面的定理证明可知，任意一个标记解矩阵对应的解都是优化模型(1.2)的一个最优解。由定理3.6，可以给出一个求解优化模型(1.2)的一个最优解的一个算法。

算法3.7 步骤一：求出系统(1.1)的标记判别矩阵$Q={\left(q_{ij}\right)}_{m\times n}$ 。

步骤二：判断系统(1.1)的可解性。若系统不可解，则程序终止，否则转入下一步。

步骤三：取系统(1.1)的一个标记解矩阵$C^{\vee }={\left(c_{ij}^{\vee }\right)}_{m\times n}$ 。

步骤四：计算最优解向量

$x^{{}_{C^{\vee }}}={\left(x_j^{C^{\vee }}\right)}_n=\left(\underset{1\le i\le m}{\max }\left(c_{i1}^{\vee }\right),\underset{1\le i\le m}{\max }\left(c_{i2}^{\vee }\right),\cdots ,\underset{1\le i\le m}{\max }\left(c_{in}^{\vee }\right)\right).$

步骤五：计算最优值$v_{opt}=\underset{1\le i\le m}{\max }\left\{b_i\right\}$ 。

算法的复杂度分析：步骤一需要$n^2$ 个计算大小，步骤二$n^2$ 个计算，步骤三需要$n^2$ 个计算，步骤四需要$n^2$ 个计算，步骤五需要$n$ 个计算，总共需要$4n^2+n$ 个计算，故计算的复杂度为$4n^2+n$ 。

例子3.8 求解优化模型

$\begin{array}{l}\min z\left(x\right)=x_1\vee x_2\vee x_3\vee x_4\vee x_5\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}\text{sec-max}\left\{0.21\wedge x_1,0.38\wedge x_2,0.42\wedge x_3,0.16\wedge x_4,0.51\wedge x_5\right\}\ge 0.41\\ \text{sec-max}\left\{0.53\wedge x_1,0.45\wedge x_2,0.34\wedge x_3,0.58\wedge x_4,0.65\wedge x_5\right\}\ge 0.50\\ \text{sec-max}\left\{0.14\wedge x_1,0.28\wedge x_2,0.51\wedge x_3,0.45\wedge x_4,0.36\wedge x_5\right\}\ge 0.31\\ \text{sec-max}\left\{0.75\wedge x_1,0.61\wedge x_2,0.35\wedge x_3,0.46\wedge x_4,0.38\wedge x_5\right\}\ge 0.52\end{array}\end{array}$

解：步骤一：直接计算可得优化模型的的约束系统的标记判别矩阵为

$Q=\left(\begin{array}{ccccc}0& 0& 0.41& 0& 0.41\\ 0.50& 0& 0& 0.50& 0.50\\ 0& 0& 0.31& 0.31& 0.31\\ 0.75& 0.61& 0& 0& 0\end{array}\right)$

步骤二：因为标记判别矩阵$Q$ 的每一行的非零元素个数都大于2，故该优化模型的约束系统有解。

步骤三：取优化模型的约束系统的一个标记解矩阵

$C^{\vee }=\left(\begin{array}{ccccc}0& 0& 0.41& 0& 0.41\\ 0.50& 0& 0& 0.50& 0\\ 0& 0& 0.31& 0.31& 0\\ 0.75& 0.61& 0& 0& 0\end{array}\right)$

步骤四：计算出优化模型的一个最优解向量

$x^{C^{\vee }}=\left(0.75,0.61,0.41,0.50,0.41\right).$

步骤五：计算优化模型的最优值$v_{opt}=\underset{1\le i\le m}{\max }\left\{b_i\right\}=0.75$ 。

4. 结论

引入一类新型的sec-max-min模糊关系不等式，接着讨论了sec-max-min模糊关系不等式解的判别条件和解的结构，最后给出了求解约束条件为sec-max-min模糊关系不等式的min-max优化模型的解法和算法。