雙層規(guī)劃模型

1、雙層規(guī)劃法雙層規(guī)劃的一般形式 設(shè) X,Y分別為 n, m維歐式空間， X Y為 X與Y的叉積空間。雙層規(guī)劃模型的 一般形式如下：（P1） opt F x, yx（P2）opt f x, y（1）ySt. g x, y 0其中，x X,y Y分別為上層（ P1）與下層（P2）的決策變量； F x,y 與 f x,y 是 定義于凸區(qū)域 G X Y 上取值于實(shí)數(shù)集的上、下層的目標(biāo)函數(shù)，Gx, y g x, y 0 ： g x, y 為 X Y 的實(shí)函數(shù)。令 S x 存在y,使 x, y G ，稱(chēng)為允許集， x S 為允許元。當(dāng)上層給出的一決策即給出允許元 x S ，滿足下層目標(biāo)函數(shù)及約束條件 的最優(yōu)

2、解，可以表示為：x Argopt f x, y : g x, y 0（2）y此時(shí)，若 x 為單點(diǎn)集，即存在唯一的 y y x x 與之相對(duì)應(yīng)，稱(chēng)它為下層 對(duì)上層的反饋函數(shù) （這里我們假設(shè) y y x x 的唯一性，即要求對(duì)每一 x S ， 存在唯一的 y x ，但一般講這是不必要的。如果不唯一，這時(shí) y x 就成為數(shù)集， y y x 就成為的 x反饋“集”函數(shù)。本文不再討論 ）。這個(gè)問(wèn)題稱(chēng)為下層規(guī)劃問(wèn) 題（P2）?？梢钥闯?，下層的決策 y 是依賴(lài)于上層決策 x的。對(duì)每一上層決策 x S， 滿足上層目標(biāo)函數(shù)的最優(yōu)解可以表示為 :opt F x,y x : g x, y 0x（3）若存在 x S，

3、使得F x ,y xopt F x,y x ，稱(chēng) x ,y 為雙層規(guī)劃的最優(yōu)解。即：F x , y xopt F x, y x opt F x, Argopt f x, yx x y綜上所述，雙層規(guī)劃問(wèn)題是由兩個(gè)單一規(guī)劃問(wèn)題 (P1)、(P2)組成的決策變量 相互關(guān)聯(lián)的如下規(guī)劃問(wèn)題：(P1) opt F x, yx其中 y y x 如下決定(P2)opt f x, y(4)ySt. g x, y 0雙層規(guī)劃問(wèn)題可以有效地應(yīng)用于管理部門(mén)來(lái)組織生產(chǎn)， 既充分發(fā)揮生產(chǎn)部門(mén) 的潛力又能得到宏觀控制，達(dá)到持續(xù)、穩(wěn)定、健康的發(fā)展。下面就文章開(kāi)始的一 個(gè)以效益兼具公平性為雙層目標(biāo)的雙層規(guī)劃問(wèn)題建立雙層規(guī)劃模

4、型。 分配選址模型總公司下面有 N個(gè)分公司，每一個(gè)分公司記為 i i 1, ,N ，經(jīng)過(guò)多因素分 析后，在第 j j 1, ,M 個(gè)城市中，初步確定備選地址，標(biāo)號(hào)為 k k 1, , L 。 已知第 i 個(gè)公司所管轄的第 j 個(gè)城市選擇第 k 個(gè)地址后的成本與收益分別為 cijk ， wijk (可以用貨幣單位或者其他數(shù)量折算，見(jiàn)表 1)。規(guī)定每一城市至少要選建一 個(gè)超市，即在每一城市的所有備選點(diǎn)中至少要選一個(gè)。 對(duì)于下層的每一分公司來(lái) 說(shuō)就是要在選建超市的總成本不超過(guò)總公司分配額度的情況下 如何在各城市 選擇合適的備選點(diǎn) k 。使得分公司的效益最大而對(duì)于位于上層的總公司來(lái)說(shuō)，就 是要考慮如何

5、分配專(zhuān)項(xiàng)投資資金 T ，即如何決策資金分配向量NS1,S2, ,SN , Si T ，使得資金的分配最為“公平合理”詳細(xì)分析如下：i1一方面，對(duì)于每一個(gè)分公司 i i 1, , N ，根據(jù)總公司所分配的投資額度 S， 確立以效益最大為目標(biāo)的下層規(guī)劃問(wèn)題 (P2)，即：給定 i ，滿足(5)。其中，目標(biāo) 函數(shù)表示第個(gè) i分公司在所管轄城市 j 中通過(guò)選擇合適的備選點(diǎn) k而獲利最大， 反映了下層決策者對(duì)所分配資金的最佳“使用”：第一個(gè)約束條件表示第 i 個(gè)分第二個(gè)約公司為籌建各超市所投入的總成本不低于從總公司所獲得的資金分配； 束條件表示在第 j 個(gè)城市中至少要保證籌建一個(gè)超市；決策變量 xijk

6、 1表示第 i 個(gè)分公司在第 j 個(gè)城市選擇第 k 個(gè)備選點(diǎn)。 xijk 0 表示第 i 個(gè)分公司在第 j 個(gè)城 市中第 k 個(gè)備選點(diǎn)未被選中。MLmaxxijk wijkj 1k 1MLx ijk c ijk Si , j1k1L（P2）St.xijk 1, （5）k1xijk 0, xijk 0or1,j 1,2, ,M ,k 1,2, ,L 那么總公司應(yīng)該如何構(gòu)建目標(biāo)函數(shù) 才能使一個(gè)資金分配向量 S1, S2, ,SN 反映出上層對(duì)下層分公司資金分配的公平性 （即如何以“公平合理”為目標(biāo) ）。利 用遺憾值函數(shù)，作為上層決策者的目標(biāo)函數(shù)。 這里我們雖也用 min maxri min rii

7、i 作為目標(biāo)函數(shù)， 但給予了新的解釋?zhuān)?即目標(biāo)函數(shù)表示公司間的差異最小化， 稱(chēng)為 公平指數(shù)。原因如下：任何資金 T 的一個(gè)分配方案，都會(huì)給各分公司帶來(lái)或多或 少的遺憾。 即分公司本能達(dá)到而因資金不充分未能實(shí)現(xiàn)的效益。 如果一個(gè)資金分 N配方案 S1,S2, ,SN , Si T，能使 N個(gè)分公司留下的遺憾值。即不滿意程度 i1差距最小就能顯示此項(xiàng)資金分配的公平性?？梢杂萌缦乱?guī)劃問(wèn)題表示：min maxri min ri iiNS T ,（P1）St. i 1 Si T,（6）Si 0其中：M L M L M Lriwijkxijk wijk /wijkj 1 k1 j 1k 1 j 1k 1i

8、 1,2, , N7)目標(biāo)函數(shù)是分公司中具有最大遺憾值與最小遺憾值的差。 稱(chēng)為差異化， 總公 司的目標(biāo)就是尋求合理的資金分配方案 S1, S2, ,SN ，使差異化最小。下面給出 此雙層規(guī)劃模型的算法。分配選址模型的求解步驟 按上述雙層規(guī)劃的定義，分配一選址模型的求解可以按以下幾步進(jìn)行。(1) 給出分公司及所管轄城市擬建超市的各備選點(diǎn)的成本與收益 (見(jiàn)表 1)。(2) 對(duì)于總公司的每一投資分配決策 S S1,S2, ,SN ，分公司 i i 1, ,N 根 據(jù)投資 Si 來(lái)尋找回報(bào)最大的備選點(diǎn) (xijk Si 1)，并計(jì)算出該分公司在投資分配Si 下的遺憾值 ri Si ，見(jiàn)表2。(3) 根

9、據(jù)分公司的遺憾程度，調(diào)整上層決策，從而經(jīng)過(guò)若干輪上、下層的互 動(dòng)與協(xié)調(diào)，最終確定一資金分配向量NS S1 , S2 , , SNS1 , S2 , , SNSi T ，使差異化i1maxri Si min ri Si 最小，即iimin min ri Si max ri SiS1, , SN i i i i i i上述步驟可以用逐次逼近法來(lái)實(shí)現(xiàn)。 逐次逼近法的思想是先在可行域中取一 個(gè)初值。然后逐步調(diào)整至遺憾值較小的解直到最優(yōu)解的獲得。 分配選址問(wèn)題算例設(shè)總公司現(xiàn)有總數(shù)為 T 19 的資金。要分配給下屬的三個(gè)分公司， 每個(gè)分公 司管轄二個(gè)城市， 每一城市有二個(gè)備選點(diǎn)可供選擇來(lái)籌建超市 預(yù)計(jì)各備

10、選點(diǎn)投 資后的收益與成本見(jiàn)表 4。依上述計(jì)算步驟及表 3，可得如下結(jié)果，見(jiàn)表 5-8。表 4 分公司擬在所管轄城市籌建超市的成本與收益注：每一分公司根據(jù)不同數(shù)目的投資，尋求回報(bào)最大的決策變量和收益值， 見(jiàn)表 5。如投資在范圍 3，4中，實(shí)際作用為 3，小數(shù)部分投資不可能產(chǎn)生新的備 選點(diǎn)建設(shè)，自然也不產(chǎn)生效益。表7 第3個(gè)分公司投資S、后最大收益及遺憾值S3X311312X321X)22最大收 益廠(SJ0,4)無(wú)可行解(4,5)101040.625,6)0110 15.50.48©7)101170337.8)0111&50.198.9)0111&50.199,10)0

11、111&501910111110.50表8上層投資分配向量、總投資額及各公司差異化值T=Sj + §2 +&SiSzS3nr103340.670.530.62044Lt4340600.530.620.09為最小 *3440.670.20 j0.620473350.670.5310.44ai9r 124350.600.530.480.12為最小4440.600.200620.425340400.530.620.22135350.400.530.4«0.13堀小4360600.530330.27145450.400.200.4«0.285360.40Q530330.20為最小155460.400.200.33020牌小6450270.20OM085370.400