圖博弈下具有未知動態(tài)的供應鏈系統(tǒng)變更設計

范佳慧，李慶奎

(北京信息科技大學 自動化學院，北京 100192)

0 引言

供應鏈系統(tǒng)是由不同節(jié)點企業(yè)如供應商、制造商、銷售商等集成，涉及資金流、物料流、信息流的復雜網絡系統(tǒng)。一般來說，不同形式的供需網絡皆可視為供應鏈系統(tǒng)[1]。供應鏈系統(tǒng)是一個復雜的動態(tài)系統(tǒng)，動態(tài)復雜性最明顯的特征是在供應鏈系統(tǒng)運行中表現(xiàn)出來的不確定性動態(tài)行為，包括子系統(tǒng)之間的切換和不確定擾動引起的需求變異放大即牛鞭效應，這種不確定性使得供應鏈管理更加困難[2]。

近些年隨著我國經濟的高速發(fā)展以及科技的日益進步，對供應鏈系統(tǒng)的穩(wěn)定性分析成為各學者研究的熱點[3]。文獻[4]提出了一種基于過程仿真的方法，為每一次供應鏈內產品設計變更選擇最經濟的路徑，以減少復雜產品開發(fā)過程中發(fā)生變更的總過程時間，并開發(fā)了基于蒙特卡羅方法的模擬算法，用于尋找可行的輸出路徑和計算輸入變化對任務的影響。文獻[5]通過考慮供應商、公司的倉庫和公司生產設施中斷的影響，分析了供應鏈系統(tǒng)中不同的變更案例，建立了Wagner-Whitin模型求解每種類型干擾的最優(yōu)排序策略，并找到使公司預期成本最小化的訂單策略。值得注意的是，目前的研究多從管理學角度，很少有學者從系統(tǒng)動力學角度兼顧切換拓撲結構研究供應鏈系統(tǒng)的變更設計。本文將供應鏈系統(tǒng)變更的一致性問題主要放在多智能體的動態(tài)圖博弈框架中考慮，主要任務是分析供應鏈系統(tǒng)在發(fā)生變更時的狀態(tài)演化機制，并保證系統(tǒng)的穩(wěn)定狀態(tài)。

博弈論為研究多智能體最優(yōu)控制問題提供了一個合適的思路。在該框架下，每個智能體都試圖優(yōu)化自己的性能，得到最優(yōu)控制策略。由于實際系統(tǒng)中外界干擾的存在，在博弈問題中，求解最優(yōu)控制策略即需要求解耦合的Hamilton-Jacobi-Isaacs(HJI)方程。針對HJI方程直接求解困難的問題，文獻[6]提出了一種基于模型的離線策略迭代算法，僅利用在線測量的狀態(tài)/輸出信息對某一控制策略進行評估，并找到更新后的控制策略。隨著強化學習和神經網絡的發(fā)展，與之結合的在線算法[7-10]逐漸受到關注。文獻[11]提出了一種多智能體強化學習算法來求解耦合HJI方程，并證明了該算法收斂于最優(yōu)解。文獻[12]利用自適應動態(tài)規(guī)劃和零和微分圖博弈理論，提出在線算法，降低計算復雜度。不同于現(xiàn)有研究結果，本文提出一種自適應最優(yōu)分布式(heuristic dynamic programming,HDP)算法，無需系統(tǒng)動力學知識即可求解耦合的HJI方程。

1 供應鏈系統(tǒng)建模

將供應鏈鏈主視為領導者，子供應鏈建模為跟隨者，子鏈需要對鏈主的庫存狀態(tài)進行追蹤并達到理想庫存水平。本文考慮系統(tǒng)出現(xiàn)變更，假設變更前供應鏈系統(tǒng)穩(wěn)定運行，且能與鏈主達到一致性，發(fā)生變更后，變更后的系統(tǒng)依然需要與原鏈主保持一致性，即達到理想庫存水平。

假設非線性供應鏈系統(tǒng)由N個節(jié)點設備組成，每一個設備將自身采集的原料或生產物品提供給下一個設備。在k時刻第i個設備的庫存狀態(tài)和不確定需求分別用xi(k)∈ni和ωi(k)∈qi(i=1,2,…,N)表示。對末端設備而言，由于其與市場直接進行交互會受到不確定需求ωi(k)的影響，當末端設備不能抑制市場需求帶來的波動時，會產生牛鞭效應。根據供應鏈系統(tǒng)上各節(jié)點設備之間的物料傳輸關系，將非線性供應鏈中第i個設備的動力學方程建模為

xi(k+1)=fi(xi(k))+gi(xi(k))ui(k)+

hi(xi(k))ωi(k)

(1)

式中xi=[x1,x2,…,xi]T∈ni為庫存狀態(tài)矢量；ui(k)∈mi為系統(tǒng)的控制輸入，控制輸入不但代表了第i個設備的生產率，也包含了對上一設備產品部件產出數量的需求；fi(xi)∈ni，gi(xi)∈ni×mi和hi(xi)∈ni×qi分別是第i個子鏈未知的狀態(tài)、輸入和擾動動力學形式；從實際情況出發(fā)，本文考慮異構多智能體系統(tǒng)，即供應鏈的每個子鏈的動力學是不同的，ωi(k)∈L2[0,∞)為不確定需求，視為外界干擾。

考慮供應鏈系統(tǒng)存在一個鏈主，子供應鏈需要根據鏈主和鄰居供應鏈的庫存狀態(tài)變化調整其自身庫存狀態(tài)，假設鏈主的動力學方程為

x0(k+1)=f0(x0(k))

(2)

式中x0(k)∈n0。將式(1)和式(2)結合，得到如下基于多智能體的非線性供應鏈系統(tǒng)：

(3)

假設1非線性供應鏈系統(tǒng)中第i個設備的最大庫存水平是ci且非線性供應鏈系統(tǒng)上的每個設備的庫存狀態(tài)都滿足

0

定義每條子供應鏈的局部庫存誤差εi(k)∈ni：

(4)

ε(k)=-((L+B)?In)η(k)

(5)

式中B代表牽引矩陣，它表明鏈主與各個子供應鏈的拓撲連接情況，且有B=diag(bi)N×N。根據同步庫存誤差的定義可得供應鏈系統(tǒng)同步庫存誤差的全局動力學方程：

ε(k)=-((L+B)?In)x(k)+

(6)

引理1如果L+B是非奇異矩陣，則同步庫存誤差向量滿足：

(7)

式中σmin(·)為矩陣的最小奇異值。為了簡單起見，xi(k)從現(xiàn)在起寫成xik。

注1假設供應鏈系統(tǒng)拓撲結構中存在生成樹，并且任一子鏈的bi≠0，則L+B非奇異。

根據式(3)和式(4)，供應鏈系統(tǒng)第i個子鏈的局部鄰域跟蹤誤差的動力學方程為

(8)

2 未知非線性動力系統(tǒng)的辨識

神經網絡用于識別供應鏈子系統(tǒng)式(1)的未知動態(tài)。根據神經網絡的通用逼近特性，可以將子系統(tǒng)式(1)近似為

(9)

式中：φi(·)為激活函數；εis(k)為神經網絡估計誤差；zi(·)為神經網絡的輸入；vis和Wis分別表示輸入層和隱藏層、隱藏層和輸出層之間的理想權重矩陣。

系統(tǒng)辨識的近似誤差可定義為

(10)

平方近似誤差定義如下：

(11)

采用梯度下降規(guī)則用于最小化式(11)并更新神經網絡權重：

(12)

3 供應鏈系統(tǒng)零和動態(tài)圖博弈

3.1 零和圖博弈

存在鏈主時的供應鏈系統(tǒng)跟蹤一致問題可通過零和博弈方法進行分析求解，首先針對供應鏈同步庫存誤差系統(tǒng)式(8)定義一個性能指標函數：

Ji=({εik,uik,u-ik,ωik,ω-ik}k≥0)=

(13)

式中：Qii>0∈ni×ni；Pii>0∈qi×qi；Pij>0∈qj×qj；W(·)>0；γ>0為一個給定的常數；u-i={uj:j∈Ni}和ω-i={ωj:j∈Ni}分別是相鄰子鏈的控制輸入和干擾。為考慮控制輸入約束，每個子鏈使用如下非二次泛函如下：

(14)

式中：R>0為正定對角陣;π∈mi;φ(·)∈mi；φ-1(ui)=[φ-1(ui(1))φ-1(ui(2))…φ-1(ui(m)]T；φ(·)為單調奇有界函數，滿足|φ(·)|≤1，且其一階導數是有界的；是執(zhí)行器的界。

生產率的目標是最小化性能指標函數，而不確定市場需求的目標是最大化性能指標函數。

當ωi(k)=0時，解決零和動態(tài)圖博弈的同步問題即要找到一個約束控制輸入ui(k)，當ωi(k)≠0時，對于給定的γ>γ*，應滿足如下有界L2增益條件：

(15)

式中：β為有界函數，且β(0)=0；γ*為滿足上述有界L2增益條件的最小γ值。

定義1對于系統(tǒng)輸入uik，?i可以穩(wěn)定系統(tǒng)式(8)，并保證相應的值函數是有限的，則i被定義為可容許的。

給定供應鏈系統(tǒng)的容許控制策略，每個子系統(tǒng)i的值函數定義為

(16)

由式(16)，每個子鏈的Bellman方程為

Vi(εik)=Ui(εik,uik,u-ik,ωik,ω-ik)+

Vi(εi(k+1))

(17)

式中初始條件Vi(0)=0。

(18)

式中:u-i={uj:j∈Ni};ω-i={ωj:j∈Ni}。

因此，每個子鏈的有界最優(yōu)控制策略和最壞擾動如下：

(19)

(20)

(21)

基于誤差動力學式(8)和性能指標式(13)，每個子鏈i的哈密頓函數定義為：

bi(f0(x0)-fi(xik))-(dj+bj)(gi(xik)uik+

(22)

ω-ik))=

(23)

(24)

將式(23)和式(24)代入式(22)，得到以下的耦合DTHJI方程：

(25)

式中，初始條件Vi(0)=0。耦合Bellman最優(yōu)方程式(21)和DTHJI方程式(25)是等價的[14]。求解耦合的DTHJI方程很困難。因此，采用值迭代算法來近似求解。

3.2 納什均衡

為了求解供應鏈系統(tǒng)的離散時間圖博弈，需要找到耦合離散時間HJI方程的納什均衡解。定義納什均衡條件為：

定義2對于供應鏈的所有子鏈，N人博弈都有一個全局納什均衡解：

(26)

定理1給出了局部鄰域跟蹤誤差漸近穩(wěn)定以及供應鏈所有子鏈與鏈主保持一致性的條件。

定理2說明耦合HJI方程的解為博弈問題提供了納什均衡解，并可以求解零和動態(tài)圖博弈。相關證明可以參考文獻[13]，此處不贅述。

3.3 值迭代算法

在這一部分中，提出了一種基于Bellman方程式(17)的在線值迭代HDP算法來求解零和動態(tài)圖博弈。該算法求解耦合的Bellman最優(yōu)方程式(21)，得到控制策略和干擾策略的最優(yōu)值。與策略迭代不同，值迭代不需要初始容許控制。具體算法步驟如下：

算法步驟:初始化:給定所有子鏈的任意初始控制、干擾策略和相應值。for l=0,1,…,迭代l次:1.策略評估:用以下公式求解Vl+1i:Vl+1i(εik)=Ui(εik,ulik,ul-ik,ωlik,ωl-ik)+Vli(εi(k+1))(27)2.策略改進:通過以下方程式更新控制和干擾策略:ul+1ik= Uφ( UR)-1(di+bi)gTiΔVi(εi(k+1))l+1(28)ωl+1ik=-1γ2(di+bi)P-1iihTiΔVi(εi(k+1))l+1(29)until滿足Vl+1i(εik)-Vli(εik)≤εEnd

3.4 求解未知動態(tài)圖博弈對策值迭代HDP算法

(30)

(31)

(32)

執(zhí)行神經網絡對控制輸入的逼近誤差可以定義為

(33)

控制輸入uik為

(34)

由式(32)，式(34)可以寫成

(35)

式中，Oi=2×[0…[i]ii…0]∈ni×niNij。

控制輸入的執(zhí)行神經網絡的平方逼近誤差定義如下：

(36)

采用梯度下降規(guī)則來更新控制輸入的執(zhí)行神經網絡權重：

(37)

類似地，執(zhí)行神經網絡對擾動的逼近誤差可以定義為

(38)

擾動ωik可以由評價神經網絡定義為

(39)

由式(44)，式(51)可以寫為

(40)

為了更新擾動的執(zhí)行神經網絡權重，采用如下梯度下降規(guī)則：

(41)

目標值函數Vik由下式給出：

(42)

采用梯度下降法來更新評價神經網絡的權重：

(43)

針對未知動態(tài)圖博弈中的執(zhí)行—評價神經網絡權重在線調整問題，提出了算法2，該算法僅使用系統(tǒng)軌跡的可測量數據。具體算法步驟如下：

算法步驟:初始化:隨機初始化執(zhí)行神經網絡辨識器權重,并將評價神經網絡權重設為零。for l=0,1,…,迭代l次: 1.計算系統(tǒng)軌跡上的局部跟蹤誤差εi0。 2.通過式(30)和式(31)計算控制策略u^lik和擾動策略ω^lik。 3.通過式(10)計算估計狀態(tài)x^li(k+1)。 4.使用估計的狀態(tài)計算局部跟蹤誤差εli(k+1)。 5.通過式(32)計算值函數V^li(k+1)。 6.更新評價神經網絡權重 W^(1+l)Tic=W^lTic-μ^ic(Vik-ZTikW^lTicZik)ZikZTik式中Vik由式(42)給出。 7.更新執(zhí)行神經網絡權重 W^(1+l)Tia=W^lTia-μ^ia(W^lTiaZik-ulik)ZTik、 W^(1+l)Tid=W^lTid-μ^id(W^lTidZik-ulik)ZTik。 8.更新辨識器權重 W^(1+l)Tis=W^lTis-μ^isφi(W^lTisφi-xik)T。 until滿足Vl+1i(εik)-Vli(εik)≤εEnd

4 仿真分析

為了驗證所提方法有效性，考慮一個包含4條子供應鏈、一個鏈主的供應鏈系統(tǒng)，其中每條子供應鏈包含2個設備，分別負責產品的生產環(huán)節(jié)和銷售環(huán)節(jié)，4條子鏈和鏈主分別通過圖1所示的通信拓撲進行信息交互。圖中0表示鏈主，1、2、3、4表示4條子鏈。

圖1 供應鏈系統(tǒng)的拓撲結構

每個子供應鏈的狀態(tài)、輸入和干擾矩陣如下[14]：

鏈主的狀態(tài)為：

供應鏈系統(tǒng)變更后庫存變化曲線如圖2～5所示。

圖2 供應鏈系統(tǒng)庫存狀態(tài)xi1變化曲線

圖2和圖3展示了變更后子供應鏈和供應鏈鏈主的庫存狀態(tài)變化，變更后供應鏈系統(tǒng)中的4條子供應鏈在第25天左右實現(xiàn)與供應鏈鏈主的庫存狀態(tài)一致。圖4和圖5展示了變更后各個子供應鏈與供應鏈鏈主之間的庫存誤差變化，庫存誤差值在第25天左右趨于0，這也表示子鏈與鏈主之間的庫存狀態(tài)趨于一致，即變更后的系統(tǒng)仍能穩(wěn)定運行。

圖3 供應鏈系統(tǒng)庫存狀態(tài)xi2變化曲線

圖4 供應鏈系統(tǒng)庫存誤差ηi1變化曲線

圖5 供應鏈系統(tǒng)庫存誤差ηi2變化曲線

5 結束語

本文研究了零和圖博弈下具有未知動態(tài)的供應鏈系統(tǒng)變更一致性問題，針對存在外部擾動的供應鏈變更系統(tǒng)，提出了一種新的自適應分布式優(yōu)化算法，求解存在未知動力學的系統(tǒng)耦合HJI方程。神經網絡用于辨識供應鏈系統(tǒng)每個子鏈的未知動態(tài)，并采用執(zhí)行—評價神經網絡逼近最優(yōu)值函數、最優(yōu)控制和最壞情況下的干擾策略。仿真結果表明，所提方法可以保證供應鏈變更系統(tǒng)的穩(wěn)定性與一致性。