數(shù)據(jù)模型決策05網(wǎng)絡(luò)優(yōu)化-wenkub
2023-03-28 11:33:09 本頁(yè)面
【正文】 t s m a x .][7 0 u ni t s m a x ]BMZ的一個(gè)網(wǎng)絡(luò)模型 A C B F E G [70] [80] [70] [60] [40] [50] [30] [50] [40] D 數(shù)學(xué)模型 ????????????????????????????????????????????????????????????0,700,800,300,500400,600,400,700,50000000..max)(,fxxxxxxxxxfxxxxxxxxxxxxxxxfxxxtsfzGAfGAxxxxxxxxxFGEGDFCFCEBEADACABFGEGFGDFCFEGCEBEDFADCFCEACBEABADACABFGEGDFCFCEBEADACAB的總流量）到（從運(yùn)送的貨物數(shù)量為到網(wǎng)絡(luò)中從流量為各條弧上的運(yùn)輸量設(shè)最短路問(wèn)題 最短路問(wèn)題是網(wǎng)絡(luò)理論中應(yīng)用最廣泛的問(wèn)題之一。 BMZ汽車正在加利福尼亞變得特別受歡迎，因此保證洛杉磯中心良好的供應(yīng)顯得特別的重要。 若 ，稱弧 是飽和弧。其余的點(diǎn)稱為 轉(zhuǎn)運(yùn)點(diǎn) 。 ij ij( i , j ) Eij ji i( i , j ) E ( j , i ) Eij ijm in z c xx x b , i 1 , 2 , ..., ns .t .0 x u ( ( i , j ) E )????? ? ? ???? ? ? ?????模型有可行解的必要條件是：該網(wǎng)絡(luò)是供求平衡的網(wǎng)絡(luò)。 1 0nii b? ??（１）網(wǎng)絡(luò)中求流量分配使總流量達(dá)到一定要求，而總費(fèi)用最低 如果網(wǎng)絡(luò)的一個(gè)流滿足以下條件，則這樣的流稱為 可行流 。 一個(gè)網(wǎng)絡(luò)模型 F1DCF2 W2W1$700$900[80] [ 60 ][ 90 ][70][0]$300 [50]$200 [50]$400 [50]$400 [50]凈流量 =流出 流入 數(shù)學(xué)模型 ???????????????????????????????????所有變量非負(fù)為各個(gè)節(jié)點(diǎn)間運(yùn)輸量設(shè)50x,x,x,x90xx70xx0xxxx60xx80xx.x900x400x400x200x300x700zminx,x,x,x,x,x2DCWDC2F1DCWDC1F2W2F2DCW2W2FDC2FDC2FDC1F2DCW1DCW1DCW1W1FDC1F1W1F2W2F2DCWDC2F1DCWDC1F1W1F2W2F2DCWDC2F1DCWDC1F1W1F最佳的解決辦法 F1DCF2 W2W1(30)(40)[80] [ 60 ][ 90 ][70][0](50)(30)(30)(50)最小費(fèi)用流問(wèn)題的數(shù)學(xué)建模 設(shè)一個(gè)有 n個(gè)節(jié)點(diǎn)， m條弧的網(wǎng)絡(luò)圖 Ｎ＝ {Ｖ ,Ｅ ,Ｗ } ，每一個(gè)節(jié)點(diǎn) i都對(duì)應(yīng)于一個(gè)數(shù) bi，表示該節(jié)點(diǎn)要求的凈流量。 ，通過(guò)弧的最大流量取決于該弧的容量。我們把流出接點(diǎn)的量等于流入節(jié)點(diǎn)的量稱為 流量守恒 。 網(wǎng)絡(luò)模型 F1DCF2 W2W1$700$900[80] [ 60 ][ 90 ][70][0]$300 [50]$200 [50]$400 [50]$400 [50]凈流量 =流出 流入 最小費(fèi)用流的專有名詞 節(jié)點(diǎn) 。 ? 倉(cāng)庫(kù) 1需要 60個(gè)單位；倉(cāng)庫(kù) 2需要 90個(gè)單位 。同樣數(shù)量的流量，因?yàn)樽叩穆肪€不一樣，總的費(fèi)用也不一樣。 ：在一個(gè)已經(jīng)有一條邊連接的節(jié)點(diǎn)和另一個(gè)還沒(méi)有邊連接的節(jié)點(diǎn)之間選擇成本最低的備選邊。 ? 連通并且不含圈的無(wú)向圖稱為 樹(shù) 。 有向圖 區(qū)別于 無(wú)向圖 的關(guān)鍵，在于它的邊（此時(shí)也稱?。┦怯蟹较虻?。 公園光纜通信問(wèn)題的路徑系統(tǒng) BADCFEG2 21 3 15754474圖中虛線表示可供選擇的邊 最佳的解決辦法 BADCFEG2 21 3 15 由于任意兩個(gè)節(jié)點(diǎn)之間均可以通信，這個(gè)圖必須是連通圖。第 5章 :網(wǎng)絡(luò)優(yōu)化 所謂網(wǎng)絡(luò)優(yōu)化，簡(jiǎn)單地說(shuō)，即對(duì)網(wǎng)絡(luò)進(jìn)行定性和定量分析，以便為實(shí)現(xiàn)某種優(yōu)化目標(biāo)而尋求最優(yōu)方案．這方面的典型問(wèn)題有：最小支撐樹(shù)問(wèn)題，最小費(fèi)用流問(wèn)題、最大流問(wèn)題、最短路問(wèn)題，中心問(wèn)題，重心問(wèn)題、運(yùn)輸問(wèn)題、指派問(wèn)題等等． 樹(shù)圖結(jié)構(gòu)：最小支撐樹(shù)問(wèn)題 光纜通信連接問(wèn)題 ? 某公園決定鋪設(shè)最先進(jìn)的光纖網(wǎng)絡(luò)，為它的主要景點(diǎn)之間提供高速通信 (數(shù)據(jù)，聲音和錄像 )。 并且，這個(gè)圖必須是無(wú)圈的。 ? 一個(gè)圖連同定義在其邊集上的實(shí)函數(shù)一起稱為一個(gè) 網(wǎng)絡(luò) ，我們把定義在邊集上的實(shí)函數(shù)稱為邊的權(quán)數(shù)。 ? 若樹(shù) Ｄ 中點(diǎn)的集合等于圖 Ｇ 的點(diǎn)的集合，樹(shù) Ｄ 中邊的集合是圖Ｇ 的邊的集合的子集，稱樹(shù) Ｄ 為圖 Ｇ 的 支撐樹(shù) 。 2個(gè)步驟，直到所有的節(jié)點(diǎn)都有一條邊（可能會(huì)有多于一條邊）與其相連 . 此時(shí)，就得到了最優(yōu)解 (最小支撐樹(shù) ) 其中第 2步的目的是為了保證每次生成的樹(shù)都是連接當(dāng)前子圖的所有頂點(diǎn)的成本最小的樹(shù)。從而我們希望確定 在給定網(wǎng)絡(luò)流量的基礎(chǔ)上，讓流沿著怎樣的路線走，能使總的費(fèi)用最小 。 ? 工廠 1和倉(cāng)庫(kù) 1之間以及工廠 2和倉(cāng)庫(kù) 2之間各有一條鐵路運(yùn)輸軌道。 要求的凈流量 (流出減去流入 ) 是一個(gè)確定的正數(shù)的話，這個(gè)點(diǎn)就是一個(gè) 供應(yīng)點(diǎn) 。 弧 。 ，使得所有在供應(yīng)點(diǎn)產(chǎn)生的流都能夠到達(dá)需求點(diǎn)。 如果 bi0，節(jié)點(diǎn) i為供應(yīng)節(jié)點(diǎn)，供應(yīng)量為 bi；如果 bi0，則為需求節(jié)點(diǎn)，需求量為 bi； 如果 bi=0，該節(jié)點(diǎn)為轉(zhuǎn)運(yùn)點(diǎn)。 a、 平衡條件 ： 對(duì)網(wǎng)絡(luò)中的任一節(jié)點(diǎn) i，在網(wǎng)絡(luò)中從節(jié)點(diǎn) i通過(guò)弧 (i,j)流向關(guān)聯(lián)的他節(jié)點(diǎn) j的流量 xij之和 減去與節(jié)點(diǎn) i關(guān)聯(lián)的其他節(jié)點(diǎn) j通過(guò)弧 (j,i)流入 i的流量 xji之和
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1