中國(guó)科學(xué): 技術(shù)科學(xué) 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)

因?yàn)閤0∈H(見(35)式)且根據(jù)引理的條件?f1和?f2在H上一致, 從而有?f1(x)=?f2(x). 因此將(37)式中

其中“?”表示向量?jī)?nèi)積運(yùn)算. 此外, 容易驗(yàn)證:

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

兩式相加即得:

1

2

T

1

2

(45)和(46)式結(jié)合起來表明兩個(gè)一元函數(shù)φ1(y)和

??f1(x)??f2(x)??(x?x)≥0, (38) ?同, 因此這兩個(gè)函數(shù)實(shí)際上恒等, 即:

φ2(y)不僅導(dǎo)數(shù)始終相等, 而且在某一點(diǎn)上函數(shù)值相

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

以上述兩個(gè)引理為基礎(chǔ), 下面給出定理2的證明. 從而由(44)式可得: 證明: 我們僅證明Pi(?,?)是連續(xù)可導(dǎo)的凸函ifgi,k?1+gi,k=2gi+Δiτ,

數(shù), 用完全類似的方法可以證明i(?,?)是連續(xù)可導(dǎo)thenf(g,g)=f(g

1

i,k?1

i,k

2

i,k?1,gi,k),

(47)

的凹函數(shù)(證明?i(?,?)為連續(xù)可導(dǎo)凸函數(shù)即可). 令: f1(gi,k?1,gi,k)=

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

2Δi

+gi?τ, (39)

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

f2在H上光滑銜接. 又因?yàn)?

?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上的連續(xù)可導(dǎo)下凸函數(shù), 現(xiàn)在考慮R2中的下述超平面(直線):

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

所以根據(jù)引理1和引理2, i(?,?)是連續(xù)可導(dǎo)的下凸函數(shù). 定理2至此全部證完.

根據(jù)(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 求解積分約束優(yōu)化調(diào)度問題的系統(tǒng)算法

由此可得:

if

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

基于第3節(jié)的理論結(jié)果, 本節(jié)將證明最優(yōu)控制形

式的調(diào)度問題(1)~(8)可轉(zhuǎn)化為一個(gè)普通的光滑非線性規(guī)劃問題, 對(duì)某些重要應(yīng)用可進(jìn)一步轉(zhuǎn)化為凸規(guī)

(42) 劃問題. ?

考慮下列非線性規(guī)劃問題: ?

?,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) 因此, 根據(jù)鏈導(dǎo)法則及(43)和(44)式可以驗(yàn)證下式成立:

47

管曉宏等: 一類含積分約束的生產(chǎn)制造系統(tǒng)優(yōu)化調(diào)度

約束(52)~(54)中下標(biāo)的變化范圍為: i=1,2,",I,

k=1,2,",K. (53)式中產(chǎn)量上下限二元函數(shù)i(?,?)

令

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

gi?,K是給定常數(shù), 對(duì)某些系統(tǒng)該式不需要考慮, 與(8)

式對(duì)應(yīng). 我們先將問題(49)~(55)看作獨(dú)立的非線性規(guī)劃問題, 再建立問題(1)~(8)與(49)~(55)的關(guān)系.

定理3. 下述兩個(gè)結(jié)論成立.

(ⅰ) 設(shè)pi(k), gi(t), ui(t)是問題(1)~(8)的一個(gè)解, 則pi(k), gi,k是問題(49)~(55)的一個(gè)解, 且對(duì)應(yīng)的目標(biāo)函數(shù)值相同, 其中g(shù)i,k按(9)式得到.

(ⅱ) 設(shè)pi(k), gi,k是問題(49)~(55)的一個(gè)解, 則由此可以得到問題(1)~(8)的一個(gè)解pi(k), gi(t), ui(t), 且對(duì)應(yīng)的目標(biāo)函數(shù)值相同. 其中g(shù)i(t)與gi,k滿足(9)式.

定理3表明求解具有積分約束的優(yōu)化問題(1)~(8), 可以轉(zhuǎn)化為非線性規(guī)劃問題(49)~(55). 問題(49)~(55)沒有與決策變量ui(t)相直接對(duì)應(yīng)的變量, 除去約束(53)外, 其余約束均為線性約束, 因此問題結(jié)構(gòu)比較簡(jiǎn)單. 在對(duì)結(jié)論(ⅱ)證明時(shí), 可由(49)~(55)的一個(gè)解構(gòu)造(1)~(8)的一個(gè)解, 且便于實(shí)現(xiàn). 定理3的證明如下.

證明: 對(duì)于結(jié)論(ⅰ), 根據(jù)問題(1)~(8)及問題(49)~(55)的表述形式, 再結(jié)合定理1的前兩個(gè)結(jié)論可知約束(52)和(53)成立, 其他約束成立是顯然的, 兩個(gè)問題的目標(biāo)函數(shù)完全相同, 因此結(jié)論(ⅰ)成立. 下面證明結(jié)論(ⅱ).

設(shè)pi(k), gi,k是問題(49)~(55)的一個(gè)解, 則由定理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)

接下來, 對(duì)k=1,2,",K, 按如下方式依次在區(qū)間

t∈[(k?1)τ,kτ]上構(gòu)造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)

根據(jù)(57)和(60)式, (61)式可改寫為: 在區(qū)間t∈

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

max

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

按以上方式得到t∈[(k?1)τ,kτ](對(duì)應(yīng)于k=1, 2 ",K的各個(gè)區(qū)間)上ui(t)和gi(t)的表達(dá)式后, 就完

成了ui(t)和gi(t)在[0,Kτ]整個(gè)區(qū)間上的構(gòu)造.

對(duì)于生產(chǎn)率gi(t)而言, 根據(jù)(18)式和(20)式可知:

max

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

將上式代入(62)式可知, 按gi(t)在區(qū)間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)?τ?

可以看出生產(chǎn)率雖然按區(qū)間逐段定義, 但在相

鄰區(qū)間的端點(diǎn)處可以連續(xù)拼接, 上述結(jié)果同時(shí)表明gi(t)與gi,k滿足(9)式.

必須注意, 對(duì)ui(t)進(jìn)行拼接后, 在相鄰區(qū)間的端點(diǎn)處ui(t)可能不連續(xù), 但對(duì)生產(chǎn)率的變化率是允許的, 相當(dāng)于最優(yōu)控制中的“梆-梆”控制, 對(duì)最終結(jié)果并無影響. 順便指出, 定理1證明中構(gòu)造的ui(t)本身就是分段連續(xù)函數(shù), 存在不連續(xù)點(diǎn).

以上僅解釋了如何基于pi(k)和gi,k構(gòu)造gi(t) 和ui(t), 下面證明如此構(gòu)造出的gi(t)和ui(t)對(duì)應(yīng)于(1)~(8)的一組可行解, 且目標(biāo)函數(shù)值相同.

由于問題(49)~(55)的目標(biāo)函數(shù)與(1)~(8)的目標(biāo)函數(shù)完全相同, 我們僅需證明pi(k), gi(t), ui(t)滿

另外, 在定理1結(jié)論(iii)的證明中, 以gi(t)=gimin,k(t)

為例指出了如何構(gòu)造ui(t)的方法. 利用同樣的構(gòu)造方

max法, 設(shè)t∈[(k?1)τ,kτ]時(shí), 與gimin,k(t)和gi,k(t)對(duì)應(yīng)

的ui(t)

max

分別為uimin,k(t)和ui,k(t),

則有下述結(jié)論成立:

t∈[(k?1)τ,kτ]時(shí),

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)τ?

足系統(tǒng)(1)~(8)中的所有約束.

48

中國(guó)科學(xué): 技術(shù)科學(xué) 2010年 第40卷 第1期

約束(2), (3), (8)直接對(duì)應(yīng)于約束(50), (51), (55), 因此僅需證明約束(4)~(7)成立. 對(duì)于約束(4), 由(53)式和θk的定義((58)式)可知:

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

線性規(guī)劃問題(49)~(55)可以得到全局最優(yōu)解. 按照定理3結(jié)論(ii)證明中給出的構(gòu)造方法, 可以重構(gòu)出ui(t)和gi(t), 進(jìn)而得到了具有積分約束的優(yōu)化問題

將(56)式中的第二式代入(65)式, 再結(jié)合(62)式即可得(4)式.

約束(6)式可由(57)式第一行、(59)和(60)式結(jié)合得到. 約束(7)式可由(18), (20), (59), (62)式結(jié)合得到. 約束(5)式可基于(61)式對(duì)k用歸納法得到. 至此, 定理3全部證完.

定理3表明可以通過求解一個(gè)光滑的非線性規(guī)劃問題來獲得原生產(chǎn)調(diào)度問題的最優(yōu)解. 通過對(duì)問題(1)~(8)的進(jìn)一步分析, 我們發(fā)現(xiàn)如果原生產(chǎn)調(diào)度問題的目標(biāo)函數(shù)為凸函數(shù), 則等價(jià)的非線性規(guī)劃問題(49)~(55)是光滑凸規(guī)劃問題. 這是非常重要的理論結(jié)果, 因?yàn)楹芏鄬?shí)際問題的目標(biāo)函數(shù)為凸函數(shù), 其任意局部最優(yōu)解也是全局最優(yōu)解, 能夠非常有效求解. 一些經(jīng)典算法如內(nèi)點(diǎn)法、序列二次規(guī)劃、廣義簡(jiǎn)約梯度法等方法都能非常迅速地收斂到全局最優(yōu)解. 定理4解釋了問題(49)~(55)與凸規(guī)劃的聯(lián)系.

定理4. 下述兩個(gè)結(jié)論成立.

(ⅰ) 問題(49)~(55)的可行域是一個(gè)閉凸集. (ⅱ) 若Ci(?)(1≤i≤I)均為(光滑)凸函數(shù), 則

(1)~(8)的全局最優(yōu)解.

基于本節(jié)的理論結(jié)果, 本文設(shè)計(jì)了兩階段求解方法, 對(duì)問題(1)~(8)進(jìn)行數(shù)值求解. 先采用常規(guī)算法求解非線性規(guī)劃問題(49)~(55), 再依據(jù)其解按照定理3結(jié)論(ⅱ)證明中給出的方法重構(gòu)出問題(1)~(8)的解. 由定理4結(jié)論(ⅰ), 無論目標(biāo)函數(shù)性質(zhì)如何, 問題(49)~ (55)的可行域始終為閉凸集, 因此在求解非線性規(guī)劃時(shí)算法將迅速收斂于局部最優(yōu)解; 特別地, 當(dāng)生產(chǎn)成本函數(shù)為凸函數(shù)時(shí), 將收斂于全局最優(yōu)解. 圖3描述了這種兩階段框架.

在上述算法框架下, 第一階段求解的是一個(gè)一般的非線性規(guī)劃問題(可能為凸規(guī)劃), 因此任何適合于一般非線性規(guī)劃的算法都可以用于該階段問題的求解. 在本文的數(shù)值測(cè)試中采用的是序列二次規(guī)劃法[21], 其詳細(xì)步驟在一般的非線性規(guī)劃專著中均可找到. 因此這里僅給出第二階段的詳細(xì)步驟, 我們將其總結(jié)為下述算法.

第二階段算法.