中國科學: 技術科學 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)式)且根據(jù)引理的條件?f1和?f2在H上一致, 從而有?f1(x)=?f2(x). 因此將(37)式中

其中“?”表示向量內積運算. 此外, 容易驗證:

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

兩式相加即得:

1

2

T

1

2

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

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

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

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

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

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

1

i,k?1

i,k

2

i,k?1,gi,k),

(47)

的凹函數(shù)(證明?i(?,?)為連續(xù)可導凸函數(shù)即可). 令: 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上的連續(xù)可導下凸函數(shù), 現(xiàn)在考慮R2中的下述超平面(直線):

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

所以根據(jù)引理1和引理2, i(?,?)是連續(xù)可導的下凸函數(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)化調度問題的系統(tǒng)算法

由此可得:

if

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

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

式的調度問題(1)~(8)可轉化為一個普通的光滑非線性規(guī)劃問題, 對某些重要應用可進一步轉化為凸規(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ù)鏈導法則及(43)和(44)式可以驗證下式成立:

47

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

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

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

令

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

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

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

定理3. 下述兩個結論成立.

(ⅰ) 設pi(k), gi(t), ui(t)是問題(1)~(8)的一個解, 則pi(k), gi,k是問題(49)~(55)的一個解, 且對應的目標函數(shù)值相同, 其中gi,k按(9)式得到.

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

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

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

設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, 按如下方式依次在區(qū)間

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)

根據(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τ](對應于k=1, 2 ",K的各個區(qū)間)上ui(t)和gi(t)的表達式后, 就完

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

對于生產率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)?τ?

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

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

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

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

由于問題(49)~(55)的目標函數(shù)與(1)~(8)的目標函數(shù)完全相同, 我們僅需證明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)τ?

足系統(tǒng)(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)

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

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

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

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

定理4. 下述兩個結論成立.

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

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

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

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

第二階段算法.