通信網(wǎng)理論基礎(chǔ)：07-網(wǎng)絡(luò)優(yōu)化問(wèn)題的線(xiàn)性規(guī)劃建模

1、通信網(wǎng)理論基礎(chǔ)Part 07: 網(wǎng)絡(luò)優(yōu)化問(wèn)題的線(xiàn)性規(guī)劃建模 線(xiàn)性規(guī)劃建模12線(xiàn)性規(guī)劃模型的基本概念 最大流問(wèn)題建模 3最小費(fèi)用流問(wèn)題建模 4多商品流問(wèn)題建模線(xiàn)性規(guī)劃模型的基本概念線(xiàn)性規(guī)劃模型的基本組成部分123建模：從一個(gè)簡(jiǎn)單的例子開(kāi)始如何描述網(wǎng)絡(luò)中的一個(gè)流線(xiàn)性規(guī)劃模型的組成部分決策變量?jī)?yōu)化目標(biāo)約束線(xiàn)性規(guī)劃模型一般形式的線(xiàn)性規(guī)劃模型決策變量約束優(yōu)化目標(biāo)一個(gè)簡(jiǎn)單的LP建模例子一個(gè)公司使用m種原料生產(chǎn)n種不同的產(chǎn)品。假設(shè)bi（i = 1, , m） 是第 i 種原料的可用數(shù)量。第 j ( j = 1, , n) 種產(chǎn)品需要第i種原料的數(shù)量為aij 單位，并且銷(xiāo)售一個(gè)單位的第 j 種產(chǎn)品可以獲利 c

2、j 元。公司生產(chǎn)管理部門(mén)需要決策每種產(chǎn)品的生產(chǎn)量以獲得最大的利潤(rùn)。生產(chǎn)問(wèn)題決策變量？ xj : 每種變量產(chǎn)品的生產(chǎn)量?jī)?yōu)化目標(biāo)？ 總利潤(rùn)最大約束？ 課堂練習(xí)一個(gè)醫(yī)院新成立了一個(gè)科室，該科室需要招收一批護(hù)士，這些新招收的護(hù)士實(shí)行輪班制度，每個(gè)護(hù)士每周連續(xù)上5天班，休息兩天。該科室在一周的第i天需要護(hù)士di個(gè)，醫(yī)院領(lǐng)導(dǎo)希望該科室降低成本，所以要求在滿(mǎn)足科室護(hù)理要求的情況下，盡量減少招收護(hù)士的數(shù)量。問(wèn)題描述該問(wèn)題的難點(diǎn)在于如何確定決策變量如何對(duì)“流”進(jìn)行建模？一個(gè)流用什么決策變量表示？xij: 這個(gè)流在鏈路(i, j) 上的流量一個(gè)流必須滿(mǎn)足什么約束？流量守恒約束，容量約束SEFBHGCDA怎么用數(shù)學(xué)

3、模型表達(dá)流的約束簡(jiǎn)單例子用約束標(biāo)示出從節(jié)點(diǎn)1到節(jié)點(diǎn)2的一個(gè)流，該流的大小為 d1x12x21x13x31d3x32x13x312x32x23x23x21x12dx13 + x12 x31 x21 = dx31 + x32 x13 x23 = 0 x23 + x21 x32 x12 = -d矩陣形式2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)10 / 50假定：m維矢量x = xijn維矢量b = b(i)矩陣N是什么東西？維度？nm。取值？1或1或0。何時(shí)Nij =1？頂點(diǎn)i是邊j的起點(diǎn)。何時(shí)Nij = 1？頂點(diǎn)i是邊j的終點(diǎn)。N : node-arc incidence matrix。流量守恒約束可寫(xiě)為：

4、其中何時(shí)Nij = 0？頂點(diǎn)i非邊j的終點(diǎn)或起點(diǎn)。流模型的矩陣形式11 / 55圖的關(guān)聯(lián)矩陣N，關(guān)聯(lián)矩陣的元素aij=1表示節(jié)點(diǎn)i是鏈路j的tail，元素aij=-1表示節(jié)點(diǎn)i是鏈路j的head，otherwise aij = 0 所以，流量守恒約束可以寫(xiě)為：關(guān)聯(lián)矩陣的第i行乘以流向量x代表什么呢？節(jié)點(diǎn)i的出流量減去入流量矩陣N表述的是什么關(guān)系？節(jié)點(diǎn)和鏈路的關(guān)系所以這種建模方法也稱(chēng)作Node-Link的建模方法其中Node-Link model2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)12 / 50Node-Link模型網(wǎng)絡(luò)優(yōu)化問(wèn)題的一種建模方法。特點(diǎn)：約束定義在每個(gè)頂點(diǎn)(Node)上：流守恒約束變量定義

5、在每條邊(Link)上：流變量xij約束的系數(shù)矩陣描述的是Node與Link之間的關(guān)系：關(guān)聯(lián)矩陣N13 / 70線(xiàn)性規(guī)劃建模12線(xiàn)性規(guī)劃模型的基本概念 最大流問(wèn)題建模 3最小費(fèi)用流問(wèn)題建模 4多商品流問(wèn)題建模14 / 32最大流問(wèn)題2013年春季給定流網(wǎng)絡(luò)G，給定節(jié)點(diǎn)對(duì)(s, t)，求從s到t 的一個(gè)流，使得流量值最大(或者只要求得到最大流量值)。決策變量：鏈路(i, j)上流過(guò)的流量?jī)?yōu)化目標(biāo)：流的大小最大約束：流守恒約束和容量約束最大流問(wèn)題2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)15 / 50變量是什么？xij和v：m+1個(gè)。目標(biāo)函數(shù)是線(xiàn)性的嗎？約束是線(xiàn)性的嗎？是是有多少個(gè)約束？每個(gè)頂點(diǎn)有一個(gè)流守恒約

6、束（等式約束）。每條邊有兩個(gè)約束（不等式約束）。n+2mMF-1線(xiàn)性規(guī)劃建模12線(xiàn)性規(guī)劃模型的基本概念 最大流問(wèn)題建模 3最小費(fèi)用流問(wèn)題建模 4多商品流問(wèn)題建模最小費(fèi)用流問(wèn)題建模最小費(fèi)用流問(wèn)題建模12最小費(fèi)用流問(wèn)題的特例建模這是個(gè)什么問(wèn)題？2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)18 / 50三個(gè)變化：1)maxmin；2)v是給定值；3)目標(biāo)函數(shù)符號(hào)說(shuō)明: cij表示(i, j)上的單位流代價(jià)。這是什么問(wèn)題？最小費(fèi)用流問(wèn)題：在節(jié)點(diǎn)s和t之間“搬運(yùn)”v個(gè)單位的流，要求費(fèi)用最小。MCF更一般的最小費(fèi)用流問(wèn)題2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)19 / 50符號(hào)說(shuō)明: b(i)表示頂點(diǎn)i的“需求量”或者“供應(yīng)量”

7、。需求量為負(fù)整數(shù)；供應(yīng)量為正整數(shù)。b(i)0，則頂點(diǎn)i為供應(yīng)節(jié)點(diǎn)； b(i)0，則頂點(diǎn)i為需求節(jié)點(diǎn)；b(i)=0，則頂點(diǎn)i為轉(zhuǎn)運(yùn)節(jié)點(diǎn)。MCF矩陣形式2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)20 / 50假定：m維矢量c = cijm維矢量x = xijn維矢量b = b(i)m維矢量u = uijMCFN : node-arc incidence matrix。最小費(fèi)用流的特例建模最短鏈路分離路徑對(duì)問(wèn)題建模最小費(fèi)用流的特例建模單源最短路問(wèn)題建模最大流問(wèn)題建模單源最短路徑問(wèn)題建模 單源單宿最短路問(wèn)題給定有向加權(quán)圖G(V, E)，給定源點(diǎn)/起始點(diǎn)s和宿點(diǎn)/終止點(diǎn)t，求從s出發(fā)到t的權(quán)重最小的路徑。MCF：令

8、b(s) = 1, b(t) = -1b(i) = 0 (i s t)SPM：Shortest Path Model對(duì)邊上的容量有沒(méi)有要求？必須大于1。邊上容量有意義嗎？上述約束只限制了流入流出的差值為1，會(huì)不會(huì)出現(xiàn)環(huán)路？使得目標(biāo)函數(shù)最小的解一定不會(huì)出現(xiàn)環(huán)路。最短路問(wèn)題模型分析該模型的最優(yōu)解會(huì)出現(xiàn)多條等價(jià)路的情況嗎？是的，從理論上講，該模型的最優(yōu)解可能是多條等價(jià)最短路SPM 1cij, uijx=x12, x23, x14, x42, x43, x13 用MCF模型求解頂點(diǎn)1和3之間的最短路，下面3個(gè)解都是最佳的：x1=1,1,0,0,0,0，x2=0,1,1,1,0,0 x3=0.4, 0.

9、7, 0.6, 0.3, 0.3, 012342, 11, 11, 12, 11, 18, 1好意思把x3稱(chēng)作“路”嗎？怎么辦?2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)24 / 50解決方法：引入整數(shù)約束在單源單宿最短路問(wèn)題的MCF模型中，加入以下約束：或者整數(shù)線(xiàn)性規(guī)劃問(wèn)題，或者簡(jiǎn)稱(chēng)整數(shù)規(guī)劃。0-1規(guī)劃是整數(shù)規(guī)劃的特例。SPM 2建模技巧1：引入整數(shù)變量整數(shù)規(guī)劃問(wèn)題Project No. 4-12013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)25 / 50Project No.4-1分別用線(xiàn)性規(guī)劃模型SPM1和整數(shù)規(guī)劃模型SPM2建模單源單宿最短路問(wèn)題。用Lingo軟件求解這兩個(gè)模型，比較求解時(shí)間和求解的結(jié)果。用Dijk

10、stra算法求解同樣的問(wèn)題，比較求解時(shí)間和結(jié)果。主要目的：熟悉基于流變量的建模方法；學(xué)習(xí)并掌握Lingo軟件的使用方法；驗(yàn)證整數(shù)約束的效果。這是啥問(wèn)題？2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)26 / 50單源多宿最短路問(wèn)題。一個(gè)重要的結(jié)論：?jiǎn)卧醋疃搪穯?wèn)題是MCF問(wèn)題的特例。邊上的容量u該如何設(shè)置？SPM-SSMD必須大于n 1。難道all-pair最短路問(wèn)題不是？邊上容量也有意義嗎？SSMD：Single Source Multiple Destination課堂練習(xí)2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)27 / 50帶寬約束下的最短路問(wèn)題給定加權(quán)圖G，每條邊上既有代價(jià)cij，也有帶寬bij。給定源點(diǎn)s，宿點(diǎn)

11、t，以及帶寬需求B。求從s出發(fā)到t的帶寬大于B的最小權(quán)重路徑。注意：要求選定的路徑帶寬大于B，等價(jià)于要求具有非零流變量xij的邊上帶寬大于B。流變量為0的邊上呢？沒(méi)有任何約束。怎樣建模？最短鏈路分離路徑對(duì)問(wèn)題建模最短分離路徑對(duì)問(wèn)題給定加權(quán)圖G。給定源點(diǎn)s和宿點(diǎn)d。求從s出發(fā)到d的一對(duì)路徑（兩條），要求這兩條路徑“鏈路分離”，且路徑權(quán)重之和最小。MCF:令b(s) = 2, b(t) = -2b(i) = 0 (i s t)邊上的容量u該如何設(shè)置？必須等于 1。邊上容量有意義嗎？SDPP-1 & 22013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)29 / 50SDPP：Shortest Disjoint Path

12、 PairSDPP-1SDPP-21SDPP-32013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)30 / 50SDPP-3符號(hào)說(shuō)明：每條邊上增加了一個(gè)yij變量；bx(s)=by(s)=1；bx(t)=by(t)= 1第三個(gè)約束中，不等式右邊是m維的全1矢量。第三個(gè)約束是什么意思？非零的x和y變量各自構(gòu)成一條路，并且不重疊。增加整數(shù)約束Project No. 4-22013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)31 / 50Project No.4-2用Lingo軟件求解SDPP-1 3這3個(gè)模型。比較求解時(shí)間和求解的結(jié)果。最大流：MCF建模2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)32 / 50最短路問(wèn)題可以MCF來(lái)建模，最大流問(wèn)題也可

13、以。怎么可能？首先，MF問(wèn)題中supply和demand沒(méi)有給定；其次，MF問(wèn)題中根本沒(méi)有cost的概念。建模思路：令b(i)=0, for all i V；st增加一條邊ts：cts = 1, uts = 1, 令cij=0, for all (i, j) A；求最小費(fèi)用流意味著什么？為了盡量減小費(fèi)用，必須在(t, s)上安排盡可能多的流。為了維持流守恒，必須在原網(wǎng)絡(luò)的s和t之間安排盡可能多的流。MF-2最小生成樹(shù)：整數(shù)約束2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)33 / 50MST：Minimum Spanning TreeMST-1xij表示邊(i,j)是否在生成樹(shù)上；E(S)表示一個(gè)邊的子集，這

14、些邊的端點(diǎn)均在集合S中。這些約束都是什么意思？xij還是流變量嗎？MST-2：輔助變量2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)34 / 50能不能想辦法描述該生成樹(shù)的權(quán)重？直接用流變量乘以邊上權(quán)重，再求和：不對(duì)，流的代價(jià)不等于樹(shù)的代價(jià)。流變量非零的邊必在生成樹(shù)上：引入0-1變量yij。要求yij在xij =0時(shí)取0，在xij取非零值時(shí)取1。M是個(gè)足夠大的整數(shù)。MST-2：模型2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)35 / 50MST-2請(qǐng)用心體會(huì)整數(shù)變量的作用。課堂練習(xí)2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)36 / 50施泰納(Steiner)樹(shù)問(wèn)題給定加權(quán)圖G，以及一個(gè)V的子集X，求一棵包含了X中所有頂點(diǎn)的，最小權(quán)重

15、的樹(shù)。怎樣建模？線(xiàn)性規(guī)劃建模12線(xiàn)性規(guī)劃模型的基本概念 最大流問(wèn)題建模 3最小費(fèi)用流問(wèn)題建模 4多商品流問(wèn)題建模All-pair最短路：多商品流2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)38 / 50為什么不能用最小費(fèi)用流來(lái)建模？每個(gè)節(jié)點(diǎn)需要發(fā)出的流為n1，需要收到的流也是n1 。若按照MCF建模，則b(i)=0，無(wú)法保證得到n1條路。怎么辦？每個(gè)節(jié)點(diǎn)發(fā)出的流不相同：不同的商品。對(duì)于第k種商品有，bk(k) = n1, bk(i)= 1(ik)。第k種商品在邊(i,j)上的流變量為xkij。APSP-1APSP：All-Pair Shortest PathAPSP-12013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)39 /

16、 50APSP-1由于是求路徑，所有的容量約束都沒(méi)有必要存在。APSP-2：進(jìn)一步擴(kuò)展2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)40 / 50每個(gè)節(jié)點(diǎn)對(duì)之間的流都當(dāng)作一種“商品”。sk，dk分別表示第k種商品的源點(diǎn)和宿點(diǎn)。APSP-2sk加入容量約束2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)41 / 50APSP模型中沒(méi)有容量約束，完全可以劃分為多個(gè)子問(wèn)題。加入容量約束呢？最佳路由問(wèn)題：Optimal Routing最佳路由問(wèn)題2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)42 / 50所有節(jié)點(diǎn)對(duì)之間都有需求，且需求hk都等于1。最佳路由問(wèn)題給定部分或全部節(jié)點(diǎn)對(duì)之間的流量需求：給定網(wǎng)絡(luò)拓?fù)銰(V,E)，邊上代價(jià)cij，容量uij。共

17、計(jì)K個(gè)這樣的需求，編號(hào)k=1, 2, , K第k個(gè)需求的大小為hk，源和宿為sk和dk為所有需求尋路，要求目標(biāo)函數(shù)達(dá)到最優(yōu)。顯然，上頁(yè)的模型是最佳路由問(wèn)題的特例：優(yōu)化目標(biāo)是最小化流量代價(jià)之和。最佳路由問(wèn)題的一般模型2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)43 / 50OR-Generic最佳路由：負(fù)載均衡2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)44 / 50OR-1容量設(shè)計(jì)問(wèn)題2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)45 / 50容量設(shè)計(jì)問(wèn)題給定部分或全部節(jié)點(diǎn)對(duì)之間的流量需求：給定網(wǎng)絡(luò)拓?fù)銰(V,E)，鏈路容量的單位成本為cij。共計(jì)K個(gè)這樣的需求，編號(hào)k=1, 2, , K第k個(gè)需求的大小為hk，源和宿為sk和dk為所有

18、鏈路設(shè)定容量yij，要求總成本最小。注意：為了設(shè)計(jì)鏈路容量，必須確定流量安排方式。容量設(shè)計(jì)問(wèn)題仍然是流量規(guī)劃問(wèn)題，與OR一樣；只不過(guò)目標(biāo)函數(shù)不同了。容量設(shè)計(jì)：Node-Link模型2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)46 / 50CD-1CD：Capacity Dimensioning拓?fù)湓O(shè)計(jì)問(wèn)題2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)47 / 50拓?fù)湓O(shè)計(jì)問(wèn)題給定部分或全部節(jié)點(diǎn)對(duì)之間的流量需求：給定節(jié)點(diǎn)集合V，不給定鏈路。共計(jì)K個(gè)這樣的需求，編號(hào)k=1, 2, , K第k個(gè)需求的大小為hk，源和宿為sk和dk確定應(yīng)該鋪設(shè)哪些鏈路，并設(shè)定鏈路容量，要求總成本最小。假定為全連通圖拓?fù)湓O(shè)計(jì)：Node-Link模型

19、2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)48 / 50TD-1TD：TopologyDesign第一種多商品流模型分析在前面的多商品流問(wèn)題的LP模型中，一個(gè)流的路由是通過(guò)流量守恒約束來(lái)描述的。在前面的模型中，如果流的個(gè)數(shù)為K個(gè)，網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)目為N，那么流量守恒約束有多少個(gè)呢？K*N個(gè)在前面的模型中，如果流的個(gè)數(shù)為K個(gè)，網(wǎng)絡(luò)的鏈路數(shù)目為M，那么變量的個(gè)數(shù)為多少呢？M*K個(gè)如果每個(gè)節(jié)點(diǎn)對(duì)間都有一個(gè)流，那么前面的LP模型中的約束的個(gè)數(shù)最多為N3 +N4，變量的個(gè)數(shù)將最多為N4可見(jiàn)隨著網(wǎng)絡(luò)規(guī)模的增加，問(wèn)題的規(guī)模成指數(shù)的增長(zhǎng)，問(wèn)題的求解難度也隨著急劇的增加解決的辦法是什么？ 給定每個(gè)流的備選路徑集合第二種建模方法

20、假設(shè)每個(gè)流可能走的路徑集合給定每個(gè)流從給定的路徑集合中挑選一條或者多條路徑來(lái)承載該流的流量不需要 ，因?yàn)槭褂脧脑吹剿薜穆窂匠休d流，天然保證了流量守恒約束（與基于增廣路徑的最大流算法類(lèi)似）那么，還需要什么約束呢？基于上述假設(shè)，模型中還需要流量守恒約束嗎？基于上述假設(shè)，模型中的決策變量是什么呢？Xdp：流d的第p條被選路上承載的流d的流量流需求約束 容量約束 單個(gè)流的流量限制示例(1)51 / 55節(jié)點(diǎn)用v表示，鏈路用e表示，業(yè)務(wù)需求/流用d 表示 每個(gè)業(yè)務(wù)需求的備選路徑集合為：需求d在路徑p上的數(shù)據(jù)流表示為：ce表示鏈路e的容量v = 2v = 3v = 1d = 1d = 3d = 2v =

21、2v = 4v = 1v = 3e = 4e = 1e = 3e = 2e = 5DemandNetwork示例(2)52 / 55備選路徑集v = 2v = 3v = 1h1 = 15v = 2v = 4v = 1v = 3e = 4e = 1e = 3e = 2e = 5DemandNetworkh3 = 10h2 = 20業(yè)務(wù)需求d=1只有一條路徑P11=2，4，2，4的意思是這條路徑包含了標(biāo)號(hào)為2和4的兩條鏈路P1=P11業(yè)務(wù)需求d=2有兩條路徑，P21=5，P22=3，4業(yè)務(wù)需求d=3也有兩條路徑，P31=1，P32=2，3示例(3)53 / 55流需求約束鏈路容量約束單個(gè)流的流量限

22、制鏈路和路徑的關(guān)系表達(dá)在第二種建模方法中，要得到鏈路上的使用容量，必須清楚鏈路和路徑之間的關(guān)系。他們之間的關(guān)系可以用鏈路-路徑（link-path）的關(guān)聯(lián)系數(shù) 表示 在給定路徑列表和每條路徑所包含鏈路的情況下， 是一個(gè)定值。因?yàn)檫@個(gè)系數(shù)的引進(jìn)，我們可以將鏈路e上的流量用下面的式子表示：從而容量約束可以寫(xiě)成：第二種建模方法叫做Link-Path的建模方式第二種建模方法分析55 / 55決策變量的個(gè)數(shù)是多少D*Pd約束的個(gè)數(shù)是多少？D+2M如果任意兩點(diǎn)間都有一個(gè)流，并且網(wǎng)絡(luò)是Full-Mesh的情況下，變量的個(gè)數(shù)為N2*Pd，約束的個(gè)數(shù)為3N2第二種建模方法的優(yōu)點(diǎn)是什么？問(wèn)題的規(guī)?？梢钥刂频诙N建

23、模方法的缺點(diǎn)是什么？求得的解不一定最優(yōu)容量設(shè)計(jì)：Link-Path模型2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)56 / 50CD-2CD：Capacity Dimensioning拓?fù)湓O(shè)計(jì)：Link-Path模型2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)57 / 50TD-2TD：Topology DesignNode-Link vs. Link-Path(1/2)2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)58 / 50以容量規(guī)劃問(wèn)題為例。CD-2: Link-PathCD-1: Node-Link變量數(shù)目？約束數(shù)目？變量數(shù)目？約束數(shù)目？符號(hào)說(shuō)明：Node-Link vs. Link-Path(2/2)2013年春季通信網(wǎng)絡(luò)理論基礎(chǔ)59 / 50以容量規(guī)劃問(wèn)題為例。CD-2: Link-PathCD-1: Node-Link變量數(shù)目？約束數(shù)目？變量數(shù)目？約束數(shù)目？結(jié)論：Link-Path模型求得的解不是最佳解，除非備選路徑集合中包含了原圖中所有的路徑。Projec