字典序方法

2024-05-21

字典序方法（精选三篇）

字典序方法篇1

图的自同态幺半群是图的自同构群的推广, 其目的是建立图论和半群的代数理论间的关系。近年来, 图的自同态幺半群的研究受到了广泛的关注并且取得了许多有趣的结果。纯正性是半群理论中的一个重要概念, 本文讨论了纯正图和它的字典序积纯正的关系, 明确给出了具有纯整自同态幺半群的两个二部图的字典序积。

定义[1]X[Y]表示图X与Y的字典序积, 即顶点集为v (X[Y]) =v (X) ×v (Y) , 边集E (X[Y]) ={ (x1, y1) , (x2, y2) =) | (x1, x2) ∈E (x) orx1=x2and{y1, y2}∈E (Y) }.

关于图及半群的术语, 可参考文献[1]。本文所考虑的图均为有限、无向、无环、无重边的简单图。

2几个引理

引理1[2]如果X[Y]是End-正则, 那么X和Y是End-正则。

引理2[2]设X是图, f∈End X, 则下列条件等价: (1) f是正则元 (2) R (f) 是X的收缩核, 并且存在X的收缩核, 使得f│v (A) 是从A到R (f) 的同构。

引理3[2]X是二部图, 则X是End-纯整的当且仅当X是以下的图:K1, K2, P2, P3, C4, 2K1和K1∪K2。

3主要结论

定理1如果X[Y]是End-纯整的, 那么X和Y是End-纯整的。

证明:假设X不是End-纯整的, 则存在f1, f2∈Idpt (X) , 使得f1, f2埸Idpt (X) , 定义:F1:X[Y]→X[Y] (x, yi) → (f1 (x) , yi) F2:X[Y]→X[Y] (x, yi) → (f2 (x) , yi) 易证F1, F2是X[Y]幂等元自同态, 又因为X[Y]是自同态纯整的, 所以F1F2是X[Y]的幂等元自同态, F1F2:X[Y]→X[Y] (x, yi) → (f1f2 (x) , yi) , 易证f1f2 (x) 是幂等的, 与假设矛盾。因此X是End-纯整的。

同理可得Y是End-纯整的.证完

注:该定理的逆不真, 即X和Y是End-纯整, X[Y]不一定是End-纯整。

这里不存在X[Y]的收缩核, 使得f│v (A) 是从A到R (f) 的同构, 所以f不正则, X[Y]不正则, X[Y]不纯整。

定理2 X和Y是End-纯整的二部图, 则X[Y]是End-纯整当且仅当 (1) 或 (2) 或 (3) 成立

(1) X是K1, Y是End-纯整的二部图;

(2) X[Y]=X, 其中X≠K1;

(3) K2[K2], K2[2K1]。

证明:充分性: (1) X[Y]=Y, 由引理3, X[Y]End-纯整的。 (2) K2[K1]=K2, P2[K1]=P2, P3[K1]=P3, 2K1[K1]=2K1, (K1∪K2) [2K1]=K1∪K2, (K1∪K2) [K1]=K1∪K2, 显然, 它们是End-纯整的。 (3) K2[K2]=K4, 因为Knn叟1是不可收缩的, 所以它是纯整的, K2[2K1]=C4, 显然, X[Y]纯整

必要性:我们仅需要说明以下六种情况下不是纯整的, 对每种情形, 证明的主要思想是, 找到f∈End X[Y], 使得A到R (f) 的映射f│v (A) 不同构。 (0, 1, 2, 3分别代表图X和Y的端点)

2k1[2K1]=4k1由引理3[2], X[Y]不纯整

K2[C4]=C4+C4由[3]知, 不纯整

因为两个幂等元的乘积不是幂等元, 所以, 2k1[K2]不纯整

2k1[C4]2K1[K1∪K2], 都为二部图, 由引理3, 2k1[C4], 2K1[K1∪K2]不纯整

(K1∪K2) [P2]在举例中已说明

(K1∪K2) [C4]是K2[C4]的子图, 因为K2[C4]不纯整, 所以 (K1∪K2) [C4]不纯整.证完

参考文献

[1]Chris Godsil, .Algebraic Graph Theory., New York, Springer, 2001.103～125[1]Chris Godsil, .Algebraic Graph Theory., New York, Springer, 2001.103～125

字典序方法篇2

具体如下：

这段代码可以把字典的所有key输出为一个数组

d2 = {‘spam‘: 2, ‘ham‘: 1, ‘eggs‘: 3} # make a dictionaryprint d2 # order is scrambledprint d2.keys # create a new list of my keys

字典序方法篇3

关键词：模型预测控制,约束线性系统,多目标控制,优化级,区间运算

模型预测控制(MPC)简称预测控制,由于能显式处理系统约束及多变量等优点,在工业过程控制中得到了广泛的应用[1,2,3]。考虑到工业过程中的各种控制目标,如设定值目标、约束目标、能耗目标及效益目标等,传统MPC设计方法是构造一个由被控量和控制量综合表达的目标函数,通过加权系数将各控制目标函数进行叠加[3,4,5,6,7]。这种设计方法的主要缺点是缺乏直观的物理意义,无法直接从加权系数了解控制目标的相对重要性即优先级,特别是在控制目标及其优先级发生改变时,这种方法不能自动调整权系数以适应控制的要求。

为有效处理工业过程中的多目标优化控制问题,国内外相关学者提出了一些多目标MPC策略。例如,文献[6]将多目标MPC问题转换为一离线计算目标函数加权系数问题,从而将多目标问题转换为单目标问题,这也是目前广泛使用的多目标控制方法。文献[7]采用Lyapunov方法和多参数规划方法提出了一种稳定的多目标线性MPC算法;文献[8,9,10]利用混合逻辑表示各控制目标的优先级,进而通过整数规划算法在线计算多目标预测控制量;文献[11,12]通过在线切换优化的目标函数设计多目标MPC策略;文献[13]在模块多变量控制[14]的基础上提出了字典序多目标MPC策略,并成功应用于实际过程的控制[15,16];文献[17]总结现有多性能指标、约束及其不可行问题,给出了更一般性的字典序优化问题描述;而文献[18]据此设计城市污水处理系统的多目标MPC;文献[19]在文献[17]的基础上给出了字典序多目标MPC闭环稳定的一个充分条件。但据笔者所知,目前还未见到有关字典序多目标MPC优化计算相关成果的报道。近年来,区间运算[20]在动态不确定系统估计和分析中得到了广泛应用[21,22,23,24],并且已用于MPC的鲁棒性研究[25,26]。区间运算是对实数运算的扩展,其一个显著优点是可以使用区间数据来表示系统变量的取值范围,在构造上包含了未知变量的真实取值,从而可以显式处理不确定性等因素对系统响应的影响。

笔者在现有字典序多目标MPC策略[13,14,15,16,17,18,19]的基础上,考虑区间约束的离散时间线性系统优先级多目标MPC问题。采用字典序方法描述各控制目标的优先级关系,将多目标MPC问题分解为多层单目标MPC优化模块。再利用区间运算法则在线计算各优化子模块的容许控制集。在此基础上,通过对容许集求交集得到作用于系统的最终控制量。

1 系统描述与预备

1.1 系统描述考虑多变量离散时间线性定常系统:

x(t+1)=Ax(t)+Bu(t),t=0,1,2,… (1)

其中x∈Rn为状态变量,u∈Rm为控制变量,A∈Rn×n和B∈Rn×m为常数矩阵。系统状态变量和控制变量满足区间约束,即xLb≤x(t)≤xUb, uLb≤u(t)≤xUb,t=0,1,2,…,其中实数sLb和sUb分别表示变量s的下限和上限。假设系统(1)的状态是完全能控、能观的。

1.2 字典序多目标MPC

对于系统(1),给定L个不同优先级的控制

目标J(t)={J1(t),J2(t),…,JL(t)},其中下标小的目标优先级高,即对下标i<j,目标Ji优先级高于目标Jj,简记为Ji>Jj,则字典序多目标MPC问题定义如下[13,14,15,16,17,18,19]:

$J_{1}^{*} (t) = \min_{u (Ν; t)} {J_{1} (t) | \begin{array}{l} (1) ‚ (2) ‚ x (0 | t) = x (t) \\ k = 1, \dots, Ν - 1 \end{array}}, \dots, J_{i}^{*} (t) = \min_{u (Ν; t)} {J_{i} (t) | \begin{array}{l} (1), (2), x (0 | t) = x (t), \\ J_{j} (t) \leq J_{j}^{*} (t), j = 1, \dots, i - 1, \\ k = 1, \dots, Ν - 1 \end{array}}$

(2)

uMPC(t)=u(0|t)*,t=0,1,2,… (3)

对于字典序多目标MPC问题(2),字典序最优解总是存在且唯一[17,19]。

1.3 区间运算法则

区间运算是对实数运算的扩展,最初主要用于计算机浮点数运算产生的误差研究,后来广泛应用于决策、优化及控制等方面[21,26]。一个实数域R的封闭区间称为区间数,即 $[d] = [\underline{d}, \bar{d}] = {d \in R | \underline{d} \leq d \leq \bar{d}}$ ,其中实数 $\underline{d}$ 和 $\bar{d}$ 分别为区间数[d]的下界和上界。当下界为正时,[d]称为正区间数;当下界和上界相等时,[d]退化为普通的实数。同理,区间数概念可以推广到区间向量[D],此时,[D]的每个元素都是区间数[d]。进一步,区间运算是定义在区间数上的运算操作,其基本的四项区间运算如下:

$\begin{array}{l} [d_{1}] + [d_{2}] = [\underline{d}_{1}, \bar{d}_{1}] + [\underline{d}_{2}, \bar{d}_{2}] = [\underline{d}_{1} + \underline{d}_{2} ‚ \\ \bar{d}_{1} + \bar{d}_{2}] (4) \\ [d_{1}] - [d_{2}] = [\underline{d}_{1}, \bar{d}_{1}] - [\underline{d}_{2}, \bar{d}_{2}] = [\underline{d}_{1} - \bar{d}_{2} ‚ \bar{d}_{1} - \underline{d}_{2}] (5) \\ [d_{1}] \times [d_{2}] = [\min (\underline{d}_{1} \cdot \underline{d}_{2}, \underline{d}_{1} \cdot \bar{d_{2}}, \bar{d_{1}} \cdot \underline{d_{2}}, \bar{d_{1}} \cdot \\ \bar{d_{2}}), \max (\underline{d}_{1} \cdot \underline{d}_{2}, \underline{d}_{1} \cdot \bar{d_{2}} ‚ \bar{d_{1}} \cdot \underline{d}_{2}, \bar{d_{1}} \cdot \bar{d_{2}})] (6) \\ [d_{1}] \div [d_{2}] = [\underline{d}_{1}, \bar{d_{1}}] / [\underline{d}_{2}, \bar{d_{2}}] \\ = [\underline{d}_{1}, \bar{d_{1}}] \times [\frac{1}{\bar{d_{2}}}, \frac{1}{\underline{d}_{2}}], i f 0 \in [\underline{d}_{2}, \bar{d_{2}}] (7) \end{array}$

2 字典序多目标MPC的区间运算

字典序多目标MPC的核心思想是按照控制目标优先级高低顺序,依次求解各控制目标的最优解。据此,一种字典序多目标MPC求解方法是:按控制目标优先级依次求解各MPC模块的容许控制集Ui,直到最低优先级目标求解实现。如果各模块优化可行,最终的解集退化为一个点(即整体MPC问题的最优控制量);否则,控制解将在最终解集的边界上取值;如果最终解集为空集(通常由系统局部故障状态产生),则按照控制目标的相对重要性,逐个去掉优先级较低的控制目标,重新求解控制解集,直到最终解集非空为止。字典序多目标MPC求解原理如图1所示。

考虑区间约束线性系统(1),下面采用区间运算法则求解字典序多目标MPC容许控制集Ui,i=0, 1,…,L,进而确定最终控制量。

令x(t)=xt为当前时刻t的状态量,则时刻t对未来时刻t+k的预测状态变量为:

$x (k | t) = A^{k} x_{t} + \sum_{j = 0}^{k - 1} A^{j} B u (k - 1 - j | t)$ (8)

其中第i个状态分量xi的预测变量为:

$x_{i} (k | t) = (A^{k})_{i} x_{t} + \sum_{j = 0}^{k - 1} (A^{j} B)_{i} u (k - 1 - j | t)$ (9)

其等价式为:

$\begin{array}{l} B_{i} u (k - 1 | t) = x_{i} (k | t) - (A^{k})_{i} x_{i} - \sum_{j = 1}^{k - 1} (A^{j} B)_{i} \cdot \\ u (k - 1 - j | t), i = 1, \dots, n (10) \end{array}$

考虑第l(l=1,…,L)层子优化模块问题,当k=1,2,…时,由式(7)可得:

Biu(0|t)=xi(1|t)-Aixt (11)

Biu(1|t)=xi(2|t)-(A2)ixt-(AB)iu(0|t) (12)

$\begin{array}{l} U_{l} = [\cap_{i = 1}^{n} [u (0 | t)]_{i}^{Τ} \cap_{i = 1}^{n} [u (1 | t)]_{i}^{Τ} \dots \cap_{i = 1}^{n} [u (k - 1 | t)]_{i}^{Τ}]^{Τ} ‚ \\ l = 1, \dots, L (13) \end{array}$

对于设定值控制目标,若对式(10)直接进行区间运算,可能会出现空集。因此,一种可行的方法是采用松弛变量法,把设定值xsp松弛为区间[xsp-ε,xsp+ε],其中ε>0为松弛变量;另一种方法是直接采用跟踪设定值设计,通过极小化跟踪误差计算最优控制量,其中跟踪设定值可通过期望轨迹生成器实现。

下面给出基于区间运算的字典序多目标MPC设计步骤:

a. 输入MPC设计参数——预测步长N和相关控制目标函数;

b. 根据实际控制要求,定义各控制目标函数Ji的优先级序列;

c. 在t时刻,以x(0|t)=x(t)为边界条件,在线求解字典序多目标优化问题(2);

d. 将u(t)MPC作用于系统(1),并在下一个控制周期令t=t+1,返回步骤c。

步骤c还包括以下具体步骤:

a. 令l=1, i=1,构造初始容许集U1=[u]。

b. 模块l=L?是,转入步骤h;否,读入第l模块中涉及的状态分量的个数nl,转入步骤c。

c. 变量i=nl?是,转入步骤f;否,转入步骤d。

d. 根据式(11)、(12)和区间运算(4)～(7)计算控制量区间[u(k|t)]i,k=0,1,…,N-1。

e. 令i=i+1,转入步骤c。

f. 根据式(13)计算第l层模块容许控制集Ul。

g. 令l=l+1,转入步骤b。

h. 控制集UL=空集?是,L=L-1,转入步骤a;否,转入步骤i。

i. 控制集UL退化为点?是,则由滚动优化原理得预测控制量u(t)MPC=u(0|t)*;否,则u(t)MPC取区间数[u(0|t)]的最小值,或任意u(0|t)∈[u(0|t)],转入MPC的设计步骤d。

在上述字典序多目标MPC设计步骤中,预测控制量区间[u(k|t)]i(k=0,1,…,N-1)的保守性随步长N的增加而增大。一种改善保守性的方法是采用预镇定控制策略,即令u=Kx+v,其中K为预先设计的控制器增益,而优化问题(2)求解的变量为v。其次,在MPC的设计步骤c的具体步骤b中,读入第l模块中涉及的状态分量的个数nl,主要是因为如设定值控制目标中可能就只对一个状态分量xj有要求。最后,在L个控制目标{Jl, l=1,…,L}中,一些子目标具有相似的性质和要求,此时可以将这些子目标加权合并作为一层优化模块,从而减少分层模块数量,提高多目标MPC在线计算效率。

3 双容水箱液位控制

考虑双容水箱液位控制系统,取采样周期为1s,得离散时间状态空间模型为:

$x (t + 1) = [\begin{array}{l} 0.9246 0.0860 \\ 0 0.9246 \end{array}] x (t) + [\begin{array}{l} 0 \\ 0.0860 \end{array}] u (t)$

(14)

其中状态变量x1和x2分别为1#和2#水箱液位(m),控制变量u为2#水箱的流入水流量(0.1kg/s),则系统(14)满足平衡方程x1=1.141x2和x2=1.141u。

在本文多目标控制问题中,取状态变量和控制变量的约束分别为0.5<x1<1.5、0.5<x2<1.5和0.5<u<1.5。进一步,令仿真时间为50s,预测步长N=4s,初始条件x(0)=(1.0,1.0)及控制目标分别为G1:0.5< x1<1.5、0.5<x2<1.5和G2:x1=1.2及G3:x2=0.8。显然,由平衡方程可知,目标G2和G3不可能同时成立。为此分别采用优先级顺序A:G1>G2>G3和B:G1>G3>G2实现水箱液位控制,则在相同仿真环境下,闭环系统状态响应曲线和控制输入曲线分别如图2～4所示,其中实线为A组仿真结果,虚线为B组仿真结果。

分析多目标MPC优先级顺序A,最重要的是两个水箱液位满足区间约束,其次优先保证1#水箱的液位,最后考虑2#水箱的液位。由于目标G2和G3相互矛盾,故优先满足更高优先级的控制目标G2。在此基础上,多目标MPC控制器尽可能将2#水箱液位维持在目标G3的附近。对照图2～4中实线仿真结果,本文算法很好地体现了多目标优先级顺序A的要求,即在两个水箱液位满足目标G1条件下,优先使1#水箱液位维持在控制目标G2处,再使2#水箱液位尽可能地接近目标G3处。同理,对于多目标MPC优先级顺序A,图2～4中虚线仿真结果也很好地反映了优先级顺序B的控制要求。

进一步,对于优先级顺序A控制,1#水箱液位的初始状态为1,而控制目标为1.2。显然需要提高流入该水箱的流量,故需要先增加2#水箱的液位,即将阀门开度增至最大范围1.5。之后,根据1#水箱液位的实际情况,实时调整2#水箱流入水流量。分析图中实线结果,本文算法很好地符合上述控制过程。而对于优先级顺序B控制,2#水箱液位的初始状态(1)超过了控制目标0.8,因此首先将流入水流量降低到容许范围的最小值,即阀门开度减至最小。之后,根据2#水箱液位的实际值,在线实时调整阀门开度。分析图中虚线结果,本文算法同样符合上述控制过程,从而验证了结果的有效性和灵活性。

4 结束语

对线性多目标优化控制问题,笔者提了一种基于区间运算的字典序多目标MPC控制器设计方法。这种方法充分利用了区间运算的优点,对具有区间约束的多变量线性系统,结合字典序多目标规划法设计字典序多目标MPC控制器。仿真结果分析表明:该设计方法能按照控制目标给定的相对重要性即优先级顺序,依次实现不同目标的优化控制,得到多目标MPC优化问题的字典序最优解(集),从而建立多目标MPC控制器。

本文来自 360文秘网(www.360wenmi.com)，转载请保留网址和出处

【字典序方法】相关文章：

字典翻译05-01

《字典大楼》05-11

英语字典简介04-23

查字典教案04-24

字典公公作文04-30