數(shù)據(jù)模型決策05網(wǎng)絡(luò)優(yōu)化-文庫吧資料
2025-03-13 11:33本頁面
【正文】 最遠(yuǎn)的景點(diǎn)游客就診時(shí)所走的路程最近？ 重心問題： 已知各景點(diǎn)的員工人數(shù)分別為 40,25,45,30,20, 35,，可使所有員工在參加會(huì)議 時(shí)間所走的總路程最短？ BADCFEG2 21 3 15754474 )(jvh由于 最小，所以會(huì)議中心應(yīng)建在 C 875)( ?h公園的重心 (各個(gè)景點(diǎn)員工人數(shù) 40,25,45,30,20,35,50.) 景點(diǎn)號(hào) A B C D E F G A 0 80 160 20 320 280 520 B 50 0 50 75 150 125 275 C 180 90 0 45 180 135 405 D 150 90 30 0 150 120 300 E 160 120 80 100 0 20 100 F 245 175 105 140 35 0 210 G 650 550 450 500 250 300 0 1435 1105 875 1060 1085 980 1810 有向網(wǎng)絡(luò) 最短路問題的數(shù)學(xué)建模 設(shè)始點(diǎn)為 1，終點(diǎn)為 n，引入 0－ 1決策變量 ，如果弧 (i,j)在從始點(diǎn)到終點(diǎn)的某條路徑上，則 ，否則 。 ? 在該小冊子中要告訴旅客從公園入口 ,各個(gè)景點(diǎn)之間以及入口之間的最短線路。 (注意，邊和弧也可能代表其他類型的活動(dòng) ) (總長度最小的路 ) 。 (允許任一方向的行進(jìn)） ,也允許存在弧 (只允許朝一個(gè)方向行進(jìn) )。即： ),( EVG ?),( ji vvijl ??ijl iv,sv jvt ?svt ? ?? ?? )v,v( ijjil)(L最小。許多優(yōu) 化問題都可以使用這個(gè)模型，如設(shè)備更新、管道的鋪設(shè)、 線路的安排、廠區(qū)的布局等。 ? 問題：通過每條運(yùn)輸路線可以運(yùn)送多少貨物，使得從總廠運(yùn)送到洛杉磯配送中心的配件流最大。 ? 大部分汽車配件以及新車是在該公司位于德國的斯圖加特的總廠生產(chǎn)的， BMZ公司需要制定一個(gè)計(jì)劃，使得下個(gè)月從總廠運(yùn)送到洛杉磯配送中心的配件流盡可能大。雖然它生產(chǎn)的汽車在所有發(fā)達(dá)國家銷量都不錯(cuò)，對它來講，出口到美國尤其重要。 ij ijxu? )v,v( ji使網(wǎng)絡(luò)總流量達(dá)到最大的可行流稱為 最大流 。 發(fā)收點(diǎn)：發(fā)點(diǎn)流出量 =收點(diǎn)流入量 =網(wǎng)絡(luò)總流量。 ,svt② 每一個(gè)弧上都給定一個(gè)容量的網(wǎng)絡(luò)稱為 容量網(wǎng)絡(luò) ，記 )W,E,V(G ?③ 的每一個(gè)弧上都給定一個(gè)實(shí)際流量 的網(wǎng)絡(luò)稱為給 定了 網(wǎng)絡(luò)一個(gè)流 。 仍用決策變量 表示通過弧 (i,j)的流量， 表示弧 (i,j)的費(fèi)用系數(shù)， 表示弧 (i,j)上的容量，則數(shù)學(xué)模型為： ts vv ?ijx ijcijuij ij( i , j ) Esij ji s t( i , j ) E ( j , i ) Etij ijm ax z fc x Cf , ( i v )s .t . x x 0 , ( i v , v )f , ( i v )0 x u ( ( i , j ) E )????? ????????? ? ?????????? ? ? ??????最大流問題 一、 有關(guān)概念： 例：下圖是輸油管道網(wǎng)， 為起點(diǎn)， 為終點(diǎn)， ， ， ， 為中轉(zhuǎn)站，弧上的數(shù)字表示該管道的最大輸油能 力（也稱容量），記為 ，問應(yīng)如何安排各管道輸油量， 才能使從 到 的總輸油量最大？ 1v3v2,4v5 sv tv6v iju1v3v2v4v5vsv tv6v2333554svt1v3v2v4v5vsv tv6v2333554① 分別稱 為 發(fā)點(diǎn)、收點(diǎn) 。即： 。 網(wǎng)絡(luò)最小費(fèi)用流問題就是找到使總費(fèi)用最小的可行流。 a、 平衡條件 ： 對網(wǎng)絡(luò)中的任一節(jié)點(diǎn) i，在網(wǎng)絡(luò)中從節(jié)點(diǎn) i通過弧 (i,j)流向關(guān)聯(lián)的他節(jié)點(diǎn) j的流量 xij之和 減去與節(jié)點(diǎn) i關(guān)聯(lián)的其他節(jié)點(diǎn) j通過弧 (j,i)流入 i的流量 xji之和 與該節(jié)點(diǎn)要求的凈流量平衡。 網(wǎng)絡(luò)所有弧 （ i,j） ∈ G上的流量 xij（一共 n個(gè)分量）組成的向量 X=[xij]稱為 網(wǎng)絡(luò)的一個(gè)流 。 如果 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)。 ，使通過網(wǎng)絡(luò)供應(yīng)的總成本最小。 ，使得所有在供應(yīng)點(diǎn)產(chǎn)生的流都能夠到達(dá)需求點(diǎn)。 最小費(fèi)用流問題的假定 ；至少有一個(gè)節(jié)點(diǎn)是需求點(diǎn)；所有剩下的節(jié)點(diǎn)都是轉(zhuǎn)運(yùn)點(diǎn)。 弧 。 要求的凈流量 恒為 0，這個(gè)點(diǎn)稱為 轉(zhuǎn)運(yùn)點(diǎn) 。 要求的凈流量 (流出減去流入 ) 是一個(gè)確定的正數(shù)的話，這個(gè)點(diǎn)就是一個(gè) 供應(yīng)點(diǎn) 。 ? 問題：確定一個(gè)運(yùn)輸方案（即每條路線運(yùn)送多少單位的產(chǎn)品），使得運(yùn)輸成本達(dá)到最小。 ? 工廠 1和倉庫 1之間以及工廠 2和倉庫 2之間各有一條鐵路運(yùn)輸軌道。 ? 工廠 1生產(chǎn) 80個(gè)單位；工廠 2生產(chǎn) 70個(gè)單位。從而我們希望確定 在給定網(wǎng)絡(luò)流量的基礎(chǔ)上，讓流沿著怎樣的路線走，能使總的費(fèi)用最小 。 問題的提出： 在一個(gè)關(guān)于流的網(wǎng)絡(luò)中，每一個(gè)流量都有一定的費(fèi)用，流所走的路線不一樣，單位費(fèi)用不一樣。 2個(gè)步驟，直到所有的節(jié)點(diǎn)都有一條邊（可能會(huì)有多于一條邊）與其相連 . 此時(shí)，就得到了最優(yōu)解 (最小支撐樹 ) 其中第 2步的目的是為了保證每次生成的樹都是連接當(dāng)前子圖的所有頂點(diǎn)的成本最小的樹。 最小支撐樹問題 的算法 ：選擇成本最低的 備選邊（圖中虛線） 。 ? 若樹 Ｄ 中點(diǎn)的集合等于圖 Ｇ 的點(diǎn)的集合，樹 Ｄ 中邊的集合是圖Ｇ 的邊的集合的子集，稱樹 Ｄ 為圖 Ｇ 的 支撐樹 。 ? 對于圖 G={V， E},如果任意兩個(gè)節(jié)點(diǎn)間都可以由一條或幾條邊連起來，則稱該圖為 連通圖 。 ? 一個(gè)圖連同定義在其邊集上的實(shí)函數(shù)一起稱為一個(gè) 網(wǎng)絡(luò) ，我們把定義在邊集上的實(shí)函數(shù)稱為邊的權(quán)數(shù)。 樹、圖的專有名詞 ? 圖 G定義為點(diǎn)和邊的集合 ,記為 G={V， E},其中， Ｖ 是點(diǎn)的集合，Ｅ 是邊的集合。 并且，這個(gè)圖必須是無圈的。 ? 問題：確定需要鋪設(shè)那些光
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1