數(shù)據(jù)模型決策05網(wǎng)絡(luò)優(yōu)化-免費(fèi)閱讀
【正文】 前例輸入后，得到的最優(yōu)運(yùn)輸方案為： 銷地產(chǎn)地 B1 B2 B3 產(chǎn)量 A1 50 150 0 200 A2 100 0 200 300 銷量 150 150 200 指派問題 有 4個工人 ,要指派他們分別 完成 4項(xiàng)工作 ,每人做各項(xiàng)工作所消耗的時間如下表。 這樣該問題就變?yōu)椋呵髲墓?jié)點(diǎn)０到節(jié)點(diǎn)４的最短路問題 . 數(shù)學(xué)模型 ???????????????????????????????????????????????變量為 10x,x,x,x,x,x,x,x,x,x1xxxx0xxxx0xxxx0xxxx1xxxx.34242314131204030201342414043423130324231202141312010403020134242314131204030201最短路問題也可看成最小費(fèi)用流問題的特例 當(dāng)確定從任一節(jié)點(diǎn) i至另一節(jié)點(diǎn) j的最短路時，只要作以下假定： (1)當(dāng)網(wǎng)絡(luò)中任意兩個節(jié)點(diǎn)之間存在連接的弧時，弧上的費(fèi)用系數(shù)等于該弧的長度； (2)作為起點(diǎn)的節(jié)點(diǎn) i為供應(yīng)節(jié)點(diǎn)且其凈流出量為 1，作為終點(diǎn)的節(jié)點(diǎn) j為需求節(jié)點(diǎn)且其凈流出量為 1，所有其他節(jié)點(diǎn)的凈流出量為零； (3) 總費(fèi)用等于從節(jié)點(diǎn) i（起點(diǎn)）到節(jié)點(diǎn) j（終點(diǎn)）所經(jīng)過的各條弧的長度之和，目標(biāo)函數(shù)是總費(fèi)用最小，也就是從節(jié)點(diǎn) i到節(jié)點(diǎn) j的路徑最短。 ? 問題 :首先考慮從公園入口到公園出口的最短線路 . BADCFEG2 21 3 15754474景點(diǎn)號 A B C D E F G A 0 2 4 5 8 7 13 13 B 2 0 2 3 6 5 11 11 C 4 2 0 1 4 3 9 9 D 5 3 1 0 5 4 10 10 E 8 6 4 5 0 1 5 8 F 7 5 3 4 1 0 6 7 G 13 11 9 10 5 6 0 13 )( ivD由于 最小，所以醫(yī)院應(yīng)建在 F ，此時離醫(yī)院最遠(yuǎn)的景點(diǎn) A 距離為 7。 最短路問題的一般提法是：設(shè) 為連通圖，圖中 各邊或弧 有權(quán) ( 表示 ， 間沒有邊或?。?, 為圖中任意兩點(diǎn)，求一條道路 ，使它是從 到 的所有路中總權(quán)最小的路。 如果網(wǎng)絡(luò)的一個流滿足以下條件，則這樣的流稱為 可行流 : 最大流問題的數(shù)學(xué)建模 用決策變量 表示通過弧 (i,j)的流量， 表示弧 (i,j)的容量，則數(shù)學(xué)模型為： ijx ijusij ji s t( i , j ) E ( j , i ) Etij ijm ax z ff , ( i v )x x 0 , ( i v , v )s .t .f , ( i v )0 x u ( ( i , j ) E )???? ????? ? ???? ?????? ? ? ????1v3v2v4v5vsv tv6v2333554BMZ公司的最大流問題 ? BMZ公司是歐洲一家生產(chǎn)豪華汽車的制造商。為什么？ 1 0nii b? ??最小費(fèi)用流問題的數(shù)學(xué)建模 （ 2）另一類最小費(fèi)用流問題是在預(yù)算費(fèi)用 C給定的情況下，求流量分配，使得從 能夠輸送的總流量達(dá)到最大。 對于一個網(wǎng)絡(luò)，如果有 ，稱為 供求平衡的網(wǎng)絡(luò) 。 容量 。 ? 卡車司機(jī)總共可以從每家工廠運(yùn)輸 50個單位到配送中心，然后可以從配送中心運(yùn)輸 50個單位到每個倉庫 （任何運(yùn)輸?shù)脚渌椭行牡漠a(chǎn)品必須隨后運(yùn)送到倉庫）。 算法的應(yīng)用： 首次連接 BADCFEG2 21 3 15745744V={C， D} W={A， B， E， F， G} 從 V中的節(jié)點(diǎn)連向 W中節(jié)點(diǎn)的備選邊中選擇成本最小的一條邊 算法的應(yīng)用： 第二次連接 BADCFEG2 21 3 15745744V={B， C， D} W={A， E， F， G} 算法的應(yīng)用： 第三次連接 BADCFEG2 21 3 15745744V={A， B， C， D} W={E， F， G} 算法的應(yīng)用： 第四次連接 BADCFEG2 21315745744V={A， B， C， D， F} W={E， G} 算法的應(yīng)用： 第五次連接 BADCFEG2 21315745744V={A， B， C， D， E， F} W={G} 算法的應(yīng)用： 最后的連接 BADCFEG2 21315745744V={A， B， C， D， E， F， G} 最小費(fèi)用流問題 這里的 流 是一個廣泛的概念，例如在交通運(yùn)輸網(wǎng)絡(luò)中有人流、車流、貨物流、供水系統(tǒng)中有水流，金融系統(tǒng)中有現(xiàn)金流，通信系統(tǒng)中有信息流，等等。該 網(wǎng)絡(luò)記為 Ｎ＝ {V， E， W}。 ? 為了利用光纖技術(shù)在景點(diǎn)之間高速通信的優(yōu)勢，不需要在每兩個景點(diǎn)之間都用一條光纜把他們直接聯(lián)系起來。 樹、圖的專有名詞 ? 圖 G定義為點(diǎn)和邊的集合 ,記為 G={V， E},其中， Ｖ 是點(diǎn)的集合，Ｅ 是邊的集合。 最小支撐樹問題 的算法 ：選擇成本最低的 備選邊（圖中虛線） 。 ? 工廠 1生產(chǎn) 80個單位；工廠 2生產(chǎn) 70個單位。 要求的凈流量 恒為 0，這個點(diǎn)稱為 轉(zhuǎn)運(yùn)點(diǎn) 。 ，使通過網(wǎng)絡(luò)供應(yīng)的總成本最小。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1