運(yùn)籌優(yōu)化問題及算法

1、網(wǎng)絡(luò)優(yōu)化問題及算法簡介. 1數(shù)學(xué)建模題目類型： B. 運(yùn)籌學(xué)1994 B 鎖具裝箱 1998 B 災(zāi)情巡視路線2000 B 鋼管訂購和運(yùn)輸 2001 B 公交車調(diào)度2003 B 露天礦生產(chǎn)的車輛安排2007 B 乘公交，看奧運(yùn)2008 ? 汶川地震2圖論的起源： Konigsberg 七橋問題七橋問題：能否從某塊陸地出發(fā)，經(jīng)過每座橋一次且僅一次，最后回到原出發(fā)地？Euler：陸地點(diǎn) ，兩點(diǎn)間的橋梁線 七橋問題圖中Euler圈問題。3圖與網(wǎng)絡(luò)圖：有序?qū)Γ╒，E），V：頂點(diǎn)集，E：邊集。賦權(quán)圖G=（V，E，w), w: ER+點(diǎn)人，邊兩個(gè)人相互認(rèn)識(shí)點(diǎn)球隊(duì)，有向邊(x,y)x勝y點(diǎn)城市，邊城市間的道

2、路，w(e)道路e的長度，修建道路e的費(fèi)用等。4圖與網(wǎng)絡(luò)中的傳統(tǒng)優(yōu)化問題1. 最短路問題實(shí) 例: 邊賦權(quán)圖G=(V,E,w),點(diǎn)s,tV可行解: G中所有s-t路目 標(biāo)：極小化路上所有邊的權(quán)和.算 法： Dijkstra 19595圖與網(wǎng)絡(luò)中的傳統(tǒng)優(yōu)化問題1.最短路問題：Dijkstra算法6圖與網(wǎng)絡(luò)中的傳統(tǒng)優(yōu)化問題2.最小支撐樹問題72.最小支撐樹問題-破圈法(Rosenstiehl 1967) 82.最小支撐樹問題-避圈法(Rosenstiehl 1967) 9圖與網(wǎng)絡(luò)中的傳統(tǒng)優(yōu)化問題 3. 最大匹配問題實(shí) 例: 邊賦權(quán)圖G=(V,E,w)可行解: G中的邊獨(dú)立集M目 標(biāo)：極小化M上所有邊

3、的權(quán)和.算 法： Edmonds 196510圖與網(wǎng)絡(luò)中的傳統(tǒng)優(yōu)化問題 4.中國郵路問題中國郵路問題：管梅谷 1960 一個(gè)郵遞員送信時(shí)，要走遍他所負(fù)責(zé)的 每條街道，完成送信任務(wù)后回到郵局. 他 應(yīng)按什么樣的路線走，使走的總里程最短?實(shí) 例: 邊賦權(quán)圖G=（V，E，w)可行解: 通過G中所有邊的圈 （未必是簡單的）目 標(biāo)：極小化圈上所有邊的權(quán)和.11 4.中國郵路問題算 法： Edmonds, Johnson 197312圖與網(wǎng)絡(luò)中的傳統(tǒng)優(yōu)化問題5.貨郎問題貨郎問題：一個(gè)推銷員要到若干個(gè)城市推銷貨物，然后回到出發(fā)點(diǎn). 他應(yīng)該如何選擇旅行路線，使每個(gè)城市通過一次且僅一次，并且總的里程最短?實(shí) 例

4、: 邊賦權(quán)圖G=(V,E,w)可行解: 通過G中所有頂點(diǎn)一次且僅一次的圈目 標(biāo)：極小化圈上所有邊的權(quán)和.近似算法：兩邊交換算法、三邊交換算法、 (歐氏距離下) 1.5 近似算法135.貨郎問題：(歐氏距離下) 1.5 近似算法 Find a MST of G. Say T .Find a minimum cost perfect Matching M, on the set of odd-degree vertices of G. Add M to T and obtain an Eulerian graph MT. Let be its Euler-tourOutput the tour t

5、hat visit the vertices of G in the order of their first pearance in . 例：14通訊網(wǎng)絡(luò)中的優(yōu)化問題1.經(jīng)典最小Steiner樹問題問題：給定平面上若干個(gè)點(diǎn)，如何將它 們連接起來使得連線長度最短？解的結(jié)構(gòu)： 該問題的解一定有樹的結(jié)構(gòu) (Steiner樹)，而且可能會(huì)引入一 些新的點(diǎn)( Steiner 點(diǎn))例：15經(jīng)典最小Steiner樹問題定理（M. R. Garey et al, 1979）最小Steiner樹 問題是NP-難解的.定理（J. B. Kruskal, 1956; R. C. Prim, 1967） 最小生成樹

6、問題是多項(xiàng)式時(shí)間內(nèi)可解的.定理（D.-Z. Du et al, 1979）最小生成樹與 最小Steiner樹權(quán)重之比不超過 16 通訊網(wǎng)絡(luò)中的優(yōu)化問題；2.網(wǎng)絡(luò)上的Steiner樹問題實(shí) 例: 邊賦權(quán)圖G=(V,E,w)和頂點(diǎn)集合的一個(gè)子集S.可行解: 連接集合S上所有頂點(diǎn)的樹T (Steiner樹).目 標(biāo)：極小化樹T上所有邊的權(quán)和.應(yīng)用背景：在通訊服務(wù)中經(jīng)常需要把信息從一個(gè)源點(diǎn)傳到多個(gè)收點(diǎn)，即多播傳輸(multicast), 如有線電視服務(wù)（vido-on-demand）, 或者要把一組點(diǎn)聯(lián)接起來 （group communication）, 如電視/電話會(huì)議（tele-conferenc

7、e）. 這里的核心問題就是如何把這些點(diǎn)連接起來.定理（M. R. Garey et al, 1979） 網(wǎng)絡(luò)上的最小Steiner樹問題是NP-難解的.17 通訊網(wǎng)絡(luò)中的優(yōu)化問題；3.最少Steiner 點(diǎn)的Steiner樹問題 問題: 給定平面上若干個(gè)點(diǎn)和一個(gè)正實(shí)數(shù)R，如何將它們連接起使每段長度不超過R且所引入的Steiner 點(diǎn)最少.應(yīng)用背景：1) 在通訊網(wǎng)絡(luò)的具體設(shè)計(jì)中，我們通常還要考慮其它實(shí)際因素. 例如：如果連接兩點(diǎn)的通訊線路太長，那么信號在傳輸過程中會(huì)有所衰竭. 一個(gè)解決方法就是在長線路中放置信號放大器(amplifier). 很自然地產(chǎn)生了一個(gè)組合優(yōu)化問題: 就是如何設(shè)計(jì)網(wǎng)絡(luò)使得

8、所需要的信號放大器最少？2) 消防車、戰(zhàn)備倉庫的選址18動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 (Dynamic Programming)是解決多階段決策過程最優(yōu)化問題的一種方法. 1951年，美國數(shù)學(xué)家Bellman等人根據(jù)一類多階段決策問題的特征，提出了解決這類問題的“最優(yōu)化原理”，并研究解決了許多實(shí)際問題，從而創(chuàng)建了動(dòng)態(tài)規(guī)劃.有許多實(shí)際問題，特別是對離散性問題, 利用動(dòng)態(tài)規(guī)劃的方法去處理常常比用線性規(guī)劃或非線性規(guī)劃更為有效. 動(dòng)態(tài)規(guī)劃方法是處理離散性問題的一種得力的工具.19動(dòng)態(tài)規(guī)劃的最優(yōu)化原理最優(yōu)化原理: 作為整個(gè)過程的最優(yōu)策略具有這樣的性質(zhì): 對于最優(yōu)策略過程中的任一狀態(tài)而言，無論其過去的狀態(tài)和決策如何，

9、其余下的諸決策必然構(gòu)成一個(gè)最優(yōu)的子策略例：最短路問題：如果為中從到v的長度為的w-最短路, u 為 P 上的任意一點(diǎn)，則s,u為中從到u的w-最短路. s u v 20動(dòng)態(tài)規(guī)劃的若干基本概念狀態(tài)變量xk: 第k階段所面臨的出發(fā)位置決策變量uk：第k階段的狀態(tài)給定以后，從該狀態(tài)演變到下一階段的某個(gè)狀態(tài)的選擇允許決策集合Uk(xk):狀態(tài)轉(zhuǎn)移方程： xk+1=Tk (xk, uk(xk)階段效益vk (xk, uk) ：衡量所考察階段的決策效果的數(shù)量指標(biāo)，表示在第k階段由狀態(tài)xk和決策, uk(xk) 所得的效益.最優(yōu)指標(biāo)函數(shù)fk(xk):它表示從第k個(gè)階段狀態(tài)xk出發(fā)到過程結(jié)束時(shí)能獲得的所有指標(biāo)函數(shù)值中的最優(yōu)值21動(dòng)態(tài)規(guī)劃的基本方程動(dòng)態(tài)規(guī)劃的基本方程: fk(xk)=o