供應鏈管理中的兩層規劃算法

摘要：文章概述兩層規劃問題在交通領域、資源分配、委托代理以及供應鏈管理中的應用并討論了線性和非線性兩種兩層規劃問題，總結了極點算法、下降迭代、懲罰函數和分支定界算法，并進行了評價，最后進一步探討了兩層規劃問題的應用前景和算法的發展方向。

關鍵詞：兩層規劃；啟發式算法；博弈決策

中圖分類號：F224 文獻標識碼：A 文章編號：1002-3100(2007)11-0055-04

Abstract: This paper describes bilevel programming and its application in transportation， resource allocation， principal-agent problem and supply chain management. Both Linear and nonlinear programmings are discussed. Pole algorithm， descending iteration algorithm， penalty function algorithm and branch and bound algorithm are presented and evaluated. At the end of the paper， we also discuss the development direction of bilevel programming and its algorithms.

Key words: bilevel programming; heuristic algorithm; game theory

供應鏈管理指的是對各個設施點之間的物流及信息流進行管理，如供貨商、制造商、加工商、分銷中心等。在早期的供應鏈管理中，一般是指局限于對供應鏈中的每個節點單獨優化，而很少考慮供應鏈節點之間的互動。但隨著研究的深入，人們認識到如果對供應鏈的各個階段加以集成和協調，將會明顯地降低整個供應鏈的運營費用，提高客戶服務水平，從而增強企業的競爭力。尤其是在引入博弈論之后，對供應鏈之間的博弈決策，并在此基礎之上協調整個供應鏈利益的研究也越來越多。而兩層規劃算法正是求解博弈問題的一種非常有效的方法。

兩層規劃是兩層決策問題的數學模型，它是一種具有兩層遞階結構的系統優化問題，上層問題和下層問題都有各自的目標函數和約束條件。上層問題的目標函數和約束條件不僅與上層決策變量有關，而且還依賴于下層的問題的最優解，而下層問題的最優解又受上層決策變量的影響。下層根據上層的決策結果調整策略使自己的利益最優化，上層根據下層的反應重新做出決策。整個系統在雙方博弈中，達到各自滿意狀態。兩層規劃的研究起源于經濟問題，如有限資源在各自部門中的分配，價格控制問題的研究等。但是兩層規劃求解是非常復雜的，即使當系統的上、下層的目標函數和約束條件都是線性的，整個系統也可能是非凸問題，并且是處處可微的，所以兩層規劃雖然在現實世界中有廣泛的應用，但是由于其計算的困難性，包括它的非凸性，NP困難性以及它的一些算法的無效性，使得兩層規劃的理論研究仍有待進一步發展。本文將從兩層規劃的實際應用和啟發式算法發展兩個方面對兩層規劃進行綜述。

1兩層規劃的實際應用

1.1交通領域的應用

兩層規劃在交通控制中有著很廣泛的應用，如O-D旅行需求估計問題，上層決策者需求整個交通網絡的交通擁塞和O-D需求估計偏差最小化，而下層決策則需求網絡平衡狀態。相關文獻如[1]、[2]探討了O-D旅行需求模型的求解方法。另外，如何進行信號控制，使車輛使用者做出合理反應，減少交通堵塞和延遲，也可以作為兩層規劃問題進行優化，如文獻[3]中的描述。

1.2資源分配中的應用

資源分配是一類比較復雜的管理問題。上層部門將資源分配給多個下層部門，下層部門根據分配的資源和自己已有的資源組織生產，使自己的效益最大化，而上層如何使有限的資源產生最大的效益是上層面臨的最大問題。Cassidy等人[4]1971年首先提出了政府部門的資源分配問題，文章描述了一個使中央政府能有效為其他層次的政府部門分配資源的模型，模型指出下層政府部門在擁有獨立資源的情況下能獨立做出決策。另外，公共設施的建設問題也屬于資源分配的一類，如污水處理站的建設，上層決策者制定一些政策使得廢物生產公司能盡量少排放廢物，最大化社會福利，下層公司最大化自己的利潤，減小成本（包括納稅成本）。Mahyar、Amouzegar和Moshirvaziri在這方面做了大量的研究，如文獻[5]、[6]。

1.3價格控制問題中的應用

在價格控制問題中，有兩個決策者，上層是價格控制者，下層是生產者、顧客等。在不同的價格下，生產者企圖找到對它“最好”的生產規模，或者下層顧客最小化自己費用支出。價格控制問題在航空領域的收益管理方面有較多的應用，如Cote和Jean-Philippe等人[7]提出的航空公司訂價模型中，上層決策者（leader）航空公司為了最大化其整個航線網絡的最大收益，而制定出最有策略；下層顧客則綜合考慮航班的費用、舒適度等等一系列因素使得自己的支出最小化，下層的決策變量影響上層的策略制定。這就構成了兩層主從對策問題。價格控制在稅收模型中也有很廣泛的應用，如Brotcorne和Luce等人在文獻[8]中探討了輪船承運商如何制定航線價格及托運人如何選擇承運商及托運路線使其費用最小化的兩層規劃模型，并給出了一種求解算法。

1.4委托代理中的應用

委托人希望代理人按照前者的利益選擇行動，但委托人不能直接觀測到代理人選擇了什么行動，能觀測到的只是另外一些變量，這些變量由代理人的行動和其他外生的隨機因素（稱為自然狀態）共同決定，委托人充其量只能得到代理人行動的不完全信息。問題委托人的問題是如何根據這些觀測到的信息來獎懲代理人，以激勵其選擇對委托人最有利的行動。代理人如何做出能使自己的利益最大化的決策。這樣委托人和代理人就形成了主從對策博弈的情況。其模型如下所示：

上層為委托人的效用函數，a為代理人的行動決策，下層是代理人的效用最大化函數，代理人選擇能使其效用V達到最大的行為a。

1.5其他供應鏈管理中的應用

兩層規劃模型在其他供應鏈管理中也有一些應用，比如供應鏈集成問題，廠商與其供應商是敵對態度，都希望自己的利益最大化，導致整個供應鏈績效低下，如何使廠商與供應商協作達成共識，是目前研究的熱點，因此建立兩層規劃模型，以各成員利潤最大化為下層目標，以供應鏈的綜合效益為上層目標。這方面的文獻目前比較少，已有的研究如文獻[9]、[10]。另外，在供應鏈局部問題領域也有兩層規劃的應用，如文獻[11]中提出了供應鏈分銷系統雙層規劃優化的模型，上層決策者在允許的固定投資范圍內確定最佳的分銷中心地點以使總成本最小；而下層規劃則描述了在多個分銷中心存在的條件下，客戶需求量在不同分銷中心之間的分配模式，它的目標是使每個客戶的費用最低。

2兩層規劃問題的分類

2.1線性的兩層規劃問題

兩層線性規劃問題BLP可以描述為下面的形式：

模型中，即使下層規劃i有不同的最優解但其最優值是相同的，因此上層規劃問題總是確定的。

關于兩層非線規劃的最優性條件參見文獻[13]。

3兩層規劃問題求解算法綜述

3.1極點算法

極點算法主要用于解決兩層線性規劃問題，Candler和Townsley[14]在研究上層無約束和下層有唯一解的兩層規劃時得到一個性質：如果兩層線性規劃最優解個數有限，那么，在約束集的極點處，至少有一個最優解。后來Bialas等人[15]證明了在約束集有界的情況下，這是兩層線性規劃的共性，并給出了通過枚舉約束集的極點來計算兩層線形規劃的全局最優解。比較常用的極點算法是Wen[16]提出的K次最好法，其算法思想如下：先在容許集合S上求出上層目標函數的最好解（1次最好解），然后檢驗這個解的可行性，若可行，即為最優解；否則放棄這個解；再在S上求出上層的次好解（2次最好解），然后檢驗這個解的可行性。如此下去，在有界集S上，無論是線性函數還是二次函數，必然經過優先次迭代可達到價格控制問題的全局最優。這種方法主要用于兩層線性規劃問題的求解。

3.2下降迭代算法

3.3分支定界算法

Edmunds和Bard[18]結合隱枚舉法給出了一種混合分支定界方法。現將下層的目標規劃用KKT條件代替。然后將其中的互補松弛條件除去，求解相應的簡化問題。如果所得的解與互補松弛條件矛盾，則使用分支定界方法進行求解。

3.4懲罰函數法

懲罰函數法是通過構造某種懲罰函數，并將它加到非線性規劃的目標函數上，從而將原來的約束極值問題轉化為無約束問題求解。在兩層規劃中，早期的懲罰函數只是將下層的問題用懲罰函數法轉化成無約束的問題處理。后期也出現了雙懲罰的懲罰函數法，即將上下層都進行懲罰使得整個問題變成無約束問題。在求解過程中根據初試點的選取及搜索方向，又可以將懲罰函數分為內點法和外點法。

4總結

兩層規劃的研究剛處于起步階段，尤其是在供應鏈中的應用還比較少，還有很大的研究前景；另外在公共政策的制定方面，兩層規劃也具有重要的應用。兩層規劃由于其復雜性，目前為止，并沒有非常好的求解算法，現有的算法在處理大規模問題中，還有很多局限性。目前，有少量文章探討了智能算法在求解兩層規劃中的應用，而且取得了較好的效果，因此智能算法在求解兩層規劃算法中有著很大的前景。

參考文獻：

[1]Yang. Heuristic algorithms for the bi-level origin destination matrix estimation problem[J]. Trans. Res， 1995，29B:231-242.

[2]Tobin， Friesz. Sensitivity Analysis for Equilibrium Network Flow[J]. Trans. Science， 1988(4):242-250.

[3]Migdalas， Athanasios. Bilevel programming in traffic planning: Models， methods and challenge[J]. Journal of Global Optimization， 1995，7(4):381-405.

[4]Cassidy， Kirby， Raike. Efficient distribution of resource through three levels of government[J]. Management Science， 1971，17(8):462-473.

[5]Mahyar， Amouzegar， Khosrow， Moshirvaziri. Strategic management decision support system: An analysis of the environmental policy issues[J]. Environmental Modeling and Assessment， 2001(6):297-306.

[6]Mahyar， Amouzegar， Khosrow， Moshirvaziri. Determining optimal pollution control policies: An application of bilevel programming[J]. European Journal of Operational Research， 1999，119:100-120.

[7]Cote， Jean-Philippe， Marcotte， Patrice， Savard， Gilles. A bilevel modeling approach to pricing and fare optimization in the airline industry[J]. Journal of Revenue Pricing Management， 2003，2(1):23-37.

[8]Brotcorne， Luce， Labbé， Martine， Marcotte， Patrice， Savard， Gilles. A Bilevel Model and Solution Algorithm for a Freight Tariff-Setting Problem[J]. Transportation Science， 2000，34(3):289-303.

[9] 陳安，劉魯，李剛，等. 虛擬企業協調博弈中的雙優策略[J]. 系統工程理論與實踐，2000，8:12-17.

[10] 黃小原，盧震. 一種交互式進化規劃及其在供應鏈問題中的應用[J]. 東北大學學報：自然科學版，2000，21(5):556-572.

[11] 孫會君，高自友. 供應鏈分銷系統雙層優化模型[J]. 管理科學學報，2003，8:66-70.

[12] Bard. Optimality conditions for the bilevel programming problem[J]. Naval Research Logistics Quarterly， 1984，31:13-26.

[13] 王先甲，馮尚友. 二層系統最優化理論[M]. 北京：北京科學出版社，1995.

[14]Candler， Townsley. A linear two-level programming problem[J]. Computers and Operation Research， 1982，9(9):59-76.

[15]Bialas， Karwan. Two-level linear programming[J]. Management Science， 1984，30:1004-1020.

[16]Wen. The“Kth-Best”algorithm for multi-level programming[R]. Technical Report， Department of Operation Research， State University of New York at Buffalo， 1981.

[17]Savard， Gauvin. The steepest descent direction for the nonlinear bilevel programming problem[J]. Operation Research Letters， 1994，15:275-282.

[18]Edmunds， Bard. Algorithm for nonlinear bilevel mathematical programs[J]. IEEE transactions on Systems， Man and Cybernetics， 1991，21(1):83-89.

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文