網(wǎng)絡(luò)優(yōu)化模型與算法-文庫吧資料
2025-07-27 07:52本頁面
【正文】 可以變成 最大流問題 逃生成功 沒有逃 生路線 34 ? m個(gè)房間是供應(yīng)節(jié)點(diǎn)（源，供應(yīng)量為１） ? 只有邊上節(jié)點(diǎn)可以是吸收節(jié)點(diǎn)（匯，吸收量為１ ） ? 多源多匯，容易變成單源單匯 ? 每條邊容量為１ ? 每個(gè)節(jié)點(diǎn)容量為１（通過增加節(jié)點(diǎn)和邊，變成邊容量） 逃生路線問題 變成 最大流問題 逃生成功 沒有逃 生路線 其他目標(biāo)？ 35 例： 空間實(shí)驗(yàn)問題 ? 某航天公司計(jì)劃進(jìn)行一次空間載人飛行，宇航員將在飛行中進(jìn)行一系列科學(xué)實(shí)驗(yàn)。 Review Technique), 又稱網(wǎng)絡(luò)計(jì)劃技術(shù)或統(tǒng)籌法 ) 大型復(fù)雜工程項(xiàng)目 (Project)往往被分成許多子項(xiàng)目 ,子項(xiàng)目之間有一定的先后順序 (偏序 )要求 , 每一子項(xiàng)目需要一定的時(shí)間完成 . PERT網(wǎng)絡(luò)的每條弧表示一個(gè)子項(xiàng)目 ,如果以弧長表示每一子項(xiàng)目需要的時(shí)間 ,則最早完工時(shí)間對(duì)應(yīng)于網(wǎng)絡(luò)中的最長路 (關(guān)鍵路線 ). 工程上所謂的關(guān)鍵路線法 (CPM: Critical Path Method)基本上也是計(jì)劃評(píng)審技術(shù)的一部分 . 項(xiàng)目網(wǎng)絡(luò)不含圈（其最長路問題和最短路問題都是可解的） (開始 ) A F (結(jié)束 ) 5 6 6 7 4 4 5 1 3 B E D C 13 例：最大流 / 最小費(fèi)用流 從甲地到乙地的公路網(wǎng)縱橫交錯(cuò)，每天每條路上的通車量有上限 . 從甲地到乙地的每天最多能通車多少輛 ? 考慮每條路上的通行成本 ,如何確定某個(gè)車隊(duì)的具體行車路線 ,使總成本最小 ? (甲 ) A F (乙 ) 5 6 6 7 4 4 5 1 3 B E D C 14 例： 運(yùn)輸問題 (Transportation Problem) 某種原材料有 M個(gè)產(chǎn)地 ， 現(xiàn)在需要將原材料從產(chǎn)地運(yùn)往 N個(gè)使用這些原材料的工廠 . 假定 M個(gè)產(chǎn)地的產(chǎn)量和 N家工廠的需要量已知 ， 單位產(chǎn)品從任一產(chǎn)地到任一工廠的的運(yùn)費(fèi)已知 ， 那么如何安排運(yùn)輸方案可以使總運(yùn)輸成本最低 ？ 網(wǎng)絡(luò)優(yōu)化問題的例子 S T 特殊的最小費(fèi)用流問題 （二部圖 , |S|=M, |T|=N） 15 例： 指派問題 (Assignment Problem) 一家公司經(jīng)理準(zhǔn)備安排 N名員工去完成 N項(xiàng)任務(wù)，每人一項(xiàng) . 由于各員工的特點(diǎn)不同，不同的員工去完成同一項(xiàng)任務(wù)時(shí)所獲得的回報(bào)是不同的 . 如何分配工作方案可以使總回報(bào)最大？ 網(wǎng)絡(luò)優(yōu)化問題的例子 S T 特殊的最小費(fèi)用流問題 （二部圖， |S|=|T|=N） 16 最小費(fèi)用流模型的特例及擴(kuò)展 最 小 費(fèi) 用 流 問 題 指派 問題 運(yùn)輸 問題 最 大 流 問題 最 短 路 問題 帶增益的 最小費(fèi)用流問題 線性 規(guī)劃 問題 凹費(fèi)用網(wǎng)絡(luò)的最小費(fèi)用流問題 凸費(fèi)用網(wǎng)絡(luò)的最小費(fèi)用流問題 狹義模型 廣義模型 凸 規(guī) 劃 17 例：匹配 問題 (Matching Problem) 在一次有 m個(gè)大學(xué)畢業(yè)生和 n家公司參加的供需見面會(huì)上，每個(gè)畢業(yè)生愿意加入到若干家公司中的一家工作，而每個(gè)公司愿意接收若干畢業(yè)生中的一人到公司工作 . 那么，最后最多有多少人可以在這次供需見面會(huì)上找到工作（即最多有多少家公司可以在這次供需見面會(huì)上招聘到員工）？如果每個(gè)畢業(yè)生到每一家公司工作將會(huì)產(chǎn)生的效益不同，那么，為了使得最后產(chǎn)生的總效益最大，最多有多少人可以在這次供需見面會(huì)上找到工作？ 網(wǎng)絡(luò)優(yōu)化問題的例子 二部基數(shù) / 賦權(quán)匹配 18 ? 破圈法 復(fù)雜度高 ? 避圈法 貪婪算法 (Greedy Algorithm) – Kruskal 算法（ 1956 ） – Prim 算法（ 1957） ：即“邊割法” ? Dijkstra算法（ 1959） – Sollin 算法 （ 1961） 最小
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1