通信網(wǎng)規(guī)劃理論(更新版)
【正文】 高速公路直接或間接到達(dá)另一個(gè)城市 . 假定已經(jīng)知道了任意兩個(gè)城市之間修建信息高速公路的成本，那么應(yīng)如何決定在哪些城市間修建信息高速公路，使得總成本最小？ 網(wǎng)絡(luò)優(yōu)化問題的例子 例 路由方案 (Transportation Problem) 有 M個(gè)信息源 ， 現(xiàn)在需要將信息從 M個(gè)信息源發(fā)送到 N個(gè)節(jié)點(diǎn) . 假定 M個(gè)信息源的信息量和N節(jié)點(diǎn)接收的信息量 已知 ， 單位信息從任一節(jié)點(diǎn)到任一節(jié)點(diǎn)的信息傳輸費(fèi)用已知 ， 那么如何安排路由方案可以使總傳輸成本最低 ？ 網(wǎng)絡(luò)優(yōu)化問題的例子 例 中國 郵 遞 員 問 題 (CPPChinese Postman Problem) 一條信息將走遍網(wǎng)絡(luò)中的所有結(jié)點(diǎn) ,最后返回起始點(diǎn) 。 請(qǐng)?jiān)O(shè)計(jì)一條最短的信息回路 (從起點(diǎn)出發(fā) ， 經(jīng)過網(wǎng)絡(luò)中的每一節(jié)點(diǎn)恰好一次 ，最后返回起點(diǎn) )？ 這一問題的研究歷史十分悠久 ， 通常稱之為旅行商問題 . 電信網(wǎng)規(guī)劃問題的例子 ?《 網(wǎng)絡(luò)優(yōu)化 》 ： 《 網(wǎng)絡(luò)流 》 （ Network Flows) ?特點(diǎn) ： （ 1） 與圖形有關(guān)，或易于用圖形方式表示 （ 2）優(yōu)化問題：從若干可能的安排或方案中尋求某種意義下的最優(yōu)安排或方案 網(wǎng)絡(luò)規(guī)劃簡(jiǎn)介 ——圖與網(wǎng)路分析 26 圖與網(wǎng)絡(luò) – 定義 ?從圖論的觀點(diǎn)看，網(wǎng)是由節(jié)點(diǎn)集V={v1,v2,… ,vn}和邊鏈路的集L={l1,l2,… ,lm}組成，圖表述網(wǎng)的模型稱為圖（ Graph），記為 G(V,L) 27 圖與網(wǎng)路的基本概念 圖與網(wǎng)路 ? 節(jié)點(diǎn) (Vertex) – 物理實(shí)體、事物、概念 – 一般 用 vi 表示 ? 邊 (Edge) – 節(jié)點(diǎn)間的連線，表示有關(guān)系 – 一般 用 eij 表示 ? 圖 (Graph) – 節(jié)點(diǎn)和邊的集合 – 一般用 G(V,E) 表示 – 點(diǎn)集 V={v1,v2,… , vn} – 邊集 E={eij } v1v5v4v3v2e12e34e13e24e22e39。為進(jìn)一步的進(jìn)行實(shí)際的規(guī)劃工作奠定基礎(chǔ)。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1