中国科学: 技术科学 2010年 第40卷 第1期

?????

1210???f1(x)??f1(x)??(x?x)≥0,1202???f2(x)??f2(x)??(x?x)≥0,

T

T

(37)

φ1′(y)=(1?1)??f1(y,2g+Δiτ?y)

′(y),=(1?1)??f2(y,2g+Δiτ?y)=φ2

(45)

因为x0∈H(见(35)式)且根据引理的条件?f1和?f2在H上一致, 从而有?f1(x)=?f2(x). 因此将(37)式中

其中“?”表示向量内积运算. 此外, 容易验证:

φ1(gi+Δiτ/2)=φ2(g+Δiτ/2), (46)

两式相加即得:

1

2

T

1

2

(45)和(46)式结合起来表明两个一元函数φ1(y)和

??f1(x)??f2(x)??(x?x)≥0, (38) ?同, 因此这两个函数实际上恒等, 即:

φ2(y)不仅导数始终相等, 而且在某一点上函数值相

此即(29)式. 引理2至此证完. φ1(y)≡φ2(y),

以上述两个引理为基础, 下面给出定理2的证明. 从而由(44)式可得: 证明: 我们仅证明Pi(?,?)是连续可导的凸函ifgi,k?1+gi,k=2gi+Δiτ,

数, 用完全类似的方法可以证明i(?,?)是连续可导thenf(g,g)=f(g

1

i,k?1

i,k

2

i,k?1,gi,k),

(47)

的凹函数(证明?i(?,?)为连续可导凸函数即可). 令: f1(gi,k?1,gi,k)=

(gi,k?1?g)2+(gi,k?gi)2

2Δi

+gi?τ, (39)

上式表明f1, f2在H上保持一致, 再结合(43)式可知f1,

f2在H上光滑衔接. 又因为:

?f1(gi,k?1,gi,k),

?

ifgi,k?1+gi,k<2g+Δiτ,?

Pi(gi,k?1,gi,k)=?

f(g,g),?2i,k?1i,k?ifgi,k?1+gi,k≥2g+Δiτ,(48)?

(gi,k?1?gi,k)2τΔ

f2(gi,k?1,gi,k)=+?(gi,k?1+gi,k)?i?τ2,

4Δi24

(40)

显然f1, f2均为R2上的连续可导下凸函数, 现在考虑R2中的下述超平面(直线):

H={(gi,k?1,gi,k)|gi,k?1+gi,k=2gi+Δiτ}, (41)

所以根据引理1和引理2, i(?,?)是连续可导的下凸函数. 定理2至此全部证完.

根据(39)和(40)式可得:

??gi,k?1?g????

Δi???

??f1(gi,k?1,gi,k)=?g?g?,

???i,k

????Δi? ?

?gi,k?1?gi,k+Δiτ?

??2Δi

??f2(gi,k?1,gi,k)=?

?gi,k?gi,k?1+Δiτ?

???2Δi??

4 求解积分约束优化调度问题的系统算法

由此可得:

if

gi,k?1+gi,k=2g+Δiτ,

基于第3节的理论结果, 本节将证明最优控制形

式的调度问题(1)~(8)可转化为一个普通的光滑非线性规划问题, 对某些重要应用可进一步转化为凸规

(42) 划问题. ?

考虑下列非线性规划问题: ?

?,IK? minJ=∑∑Ci(pi(k)), (49)

gi,k,pi(k)?i=1k=1?

?I

s.t.∑pi(k)=D(k); k=1,2,",K, (50)

i=1

then?f1(gi,k?1,gi,k)=?f2(gi,k?1,gi,k),

(43)

k=2,",K, (51) ∑aj,ipi(k)≤Rj,k;j=1,2,",J, 1,

i=1

I

即?f1,?f2在超平面H上保持一致. 再令:

gi,k?gi,k?1≤Δiτ, (52)

P(gi,k?1,gi,k)≤pi(k)≤i(gi,k?1,gi,k), (53) ??φ1(y)=f1(y,2gi+Δiτ?y),

(44) ? g≤gi,k≤i, (54) =+Δ?(y)f(y,2gy),φτ2i?i?2

gi,0=gi?,0,gi,K=gi?,K, (55) 因此, 根据链导法则及(43)和(44)式可以验证下式成立:

47

管晓宏等: 一类含积分约束的生产制造系统优化调度

约束(52)~(54)中下标的变化范围为: i=1,2,",I,

k=1,2,",K. (53)式中产量上下限二元函数i(?,?)

令

和Pi(?,?)由(12)和(13)式确定; (55)式中的gi?,0和

gi?,K是给定常数, 对某些系统该式不需要考虑, 与(8)

式对应. 我们先将问题(49)~(55)看作独立的非线性规划问题, 再建立问题(1)~(8)与(49)~(55)的关系.

定理3. 下述两个结论成立.

(ⅰ) 设pi(k), gi(t), ui(t)是问题(1)~(8)的一个解, 则pi(k), gi,k是问题(49)~(55)的一个解, 且对应的目标函数值相同, 其中gi,k按(9)式得到.

(ⅱ) 设pi(k), gi,k是问题(49)~(55)的一个解, 则由此可以得到问题(1)~(8)的一个解pi(k), gi(t), ui(t), 且对应的目标函数值相同. 其中gi(t)与gi,k满足(9)式.

定理3表明求解具有积分约束的优化问题(1)~(8), 可以转化为非线性规划问题(49)~(55). 问题(49)~(55)没有与决策变量ui(t)相直接对应的变量, 除去约束(53)外, 其余约束均为线性约束, 因此问题结构比较简单. 在对结论(ⅱ)证明时, 可由(49)~(55)的一个解构造(1)~(8)的一个解, 且便于实现. 定理3的证明如下.

证明: 对于结论(ⅰ), 根据问题(1)~(8)及问题(49)~(55)的表述形式, 再结合定理1的前两个结论可知约束(52)和(53)成立, 其他约束成立是显然的, 两个问题的目标函数完全相同, 因此结论(ⅰ)成立. 下面证明结论(ⅱ).

设pi(k), gi,k是问题(49)~(55)的一个解, 则由定理1的证明过程(参考(18)和(20)式)及(53)式可知:

?0, if(gi,k?1,gi,k)=i(gi,k?1,gi,k)??pi(k)?i(gi,k?1,gi,k)?

,θk=?

?(,)(,)ggPggi,k?1i,ki?ii,k?1i,k

??ifPi(gi,k?1,gi,k)<i(gi,k?1,gi,k),(58)?

由(53)及(58)式可知

0≤θk≤1, (59)

接下来, 对k=1,2,",K, 按如下方式依次在区间

t∈[(k?1)τ,kτ]上构造ui(t)和gi(t):

max

ui(t)=(1?θk)uimin,k(t)+θkui,k(t), (60)

gi(t)=gi,k?1+∫

t(k?1)τ

ui(ξ)dξ, (61)

根据(57)和(60)式, (61)式可改写为: 在区间t∈

[(k?1)τ,kτ]上

max

gi(t)=(1?θk)gimin,k(t)+θkgi,k(t). (62)

按以上方式得到t∈[(k?1)τ,kτ](对应于k=1, 2 ",K的各个区间)上ui(t)和gi(t)的表达式后, 就完

成了ui(t)和gi(t)在[0,Kτ]整个区间上的构造.

对于生产率gi(t)而言, 根据(18)式和(20)式可知:

max

gimin,k(kτ)=gi,k(kτ)=gi,k, (63)

将上式代入(62)式可知, 按gi(t)在区间t∈[(k?1)τ, kτ]上的定义, 有:

max

gi(kτ)=θkgimin,k(kτ)+(1?θk)gi,k(kτ)=gi,k. (64)

max?g≤gimin≤(t)g,,k(t)≤i,ki

?ik?τ

min?Pi(gi,k?1,gi,k)=(56) ∫(k?1)?τgi,k(t)dt≤pi(k) ?

?kτ ?

≤∫gimax(t)dt(g,g),=?,kii,k?1i,k

(k?1)?τ?

可以看出生产率虽然按区间逐段定义, 但在相

邻区间的端点处可以连续拼接, 上述结果同时表明gi(t)与gi,k满足(9)式.

必须注意, 对ui(t)进行拼接后, 在相邻区间的端点处ui(t)可能不连续, 但对生产率的变化率是允许的, 相当于最优控制中的“梆-梆”控制, 对最终结果并无影响. 顺便指出, 定理1证明中构造的ui(t)本身就是分段连续函数, 存在不连续点.

以上仅解释了如何基于pi(k)和gi,k构造gi(t) 和ui(t), 下面证明如此构造出的gi(t)和ui(t)对应于(1)~(8)的一组可行解, 且目标函数值相同.

由于问题(49)~(55)的目标函数与(1)~(8)的目标函数完全相同, 我们仅需证明pi(k), gi(t), ui(t)满

另外, 在定理1结论(iii)的证明中, 以gi(t)=gimin,k(t)

为例指出了如何构造ui(t)的方法. 利用同样的构造方

max法, 设t∈[(k?1)τ,kτ]时, 与gimin,k(t)和gi,k(t)对应

的ui(t)

max

分别为uimin,k(t)和ui,k(t),

则有下述结论成立:

t∈[(k?1)τ,kτ]时,

max??Δi≤uimin

,k(t)≤Δi,?Δi≤ui,k(t)≤Δi,

?t?gimin(t)guimin=+i,k?1∫,k(ξ)dξ, (57) ?,k(k?1)τ

t?max

g(t)guimax=+?i,ki,k?1∫,k(ξ)dξ,?k(1)τ?

足系统(1)~(8)中的所有约束.

48

中国科学: 技术科学 2010年 第40卷 第1期

约束(2), (3), (8)直接对应于约束(50), (51), (55), 因此仅需证明约束(4)~(7)成立. 对于约束(4), 由(53)式和θk的定义((58)式)可知:

pi(k)=(1?θk)Pi(gi,k?1,gi,k)+θki(gi,k?1,gi,k). (65)

线性规划问题(49)~(55)可以得到全局最优解. 按照定理3结论(ii)证明中给出的构造方法, 可以重构出ui(t)和gi(t), 进而得到了具有积分约束的优化问题

将(56)式中的第二式代入(65)式, 再结合(62)式即可得(4)式.

约束(6)式可由(57)式第一行、(59)和(60)式结合得到. 约束(7)式可由(18), (20), (59), (62)式结合得到. 约束(5)式可基于(61)式对k用归纳法得到. 至此, 定理3全部证完.

定理3表明可以通过求解一个光滑的非线性规划问题来获得原生产调度问题的最优解. 通过对问题(1)~(8)的进一步分析, 我们发现如果原生产调度问题的目标函数为凸函数, 则等价的非线性规划问题(49)~(55)是光滑凸规划问题. 这是非常重要的理论结果, 因为很多实际问题的目标函数为凸函数, 其任意局部最优解也是全局最优解, 能够非常有效求解. 一些经典算法如内点法、序列二次规划、广义简约梯度法等方法都能非常迅速地收敛到全局最优解. 定理4解释了问题(49)~(55)与凸规划的联系.

定理4. 下述两个结论成立.

(ⅰ) 问题(49)~(55)的可行域是一个闭凸集. (ⅱ) 若Ci(?)(1≤i≤I)均为(光滑)凸函数, 则

(1)~(8)的全局最优解.

基于本节的理论结果, 本文设计了两阶段求解方法, 对问题(1)~(8)进行数值求解. 先采用常规算法求解非线性规划问题(49)~(55), 再依据其解按照定理3结论(ⅱ)证明中给出的方法重构出问题(1)~(8)的解. 由定理4结论(ⅰ), 无论目标函数性质如何, 问题(49)~ (55)的可行域始终为闭凸集, 因此在求解非线性规划时算法将迅速收敛于局部最优解; 特别地, 当生产成本函数为凸函数时, 将收敛于全局最优解. 图3描述了这种两阶段框架.

在上述算法框架下, 第一阶段求解的是一个一般的非线性规划问题(可能为凸规划), 因此任何适合于一般非线性规划的算法都可以用于该阶段问题的求解. 在本文的数值测试中采用的是序列二次规划法[21], 其详细步骤在一般的非线性规划专著中均可找到. 因此这里仅给出第二阶段的详细步骤, 我们将其总结为下述算法.

第二阶段算法.