運(yùn)籌學(xué)期末復(fù)習(xí)提綱-資料下載頁(yè)
2025-04-30 12:10本頁(yè)面
【正文】 xxxxxxxxz松弛問(wèn)題最優(yōu)解 整數(shù)規(guī)劃最優(yōu)解 例 不能通過(guò)舍入取整地方法，由松弛問(wèn)題的解得到整數(shù)規(guī)劃的最優(yōu)解 6 動(dòng)態(tài)規(guī)劃 動(dòng)態(tài)規(guī)劃的基本概念 最優(yōu)化原理 經(jīng)濟(jì)管理問(wèn)題舉例 多階段決策過(guò)程 動(dòng)態(tài)規(guī)劃的分類： 離散確定型 離散隨機(jī)型 連續(xù)確定型 連續(xù)隨機(jī)型 決策 1 狀態(tài) 1 決策 2 狀態(tài) 2 決策 n 狀態(tài) 3 …… 狀態(tài) n 階段 ，階段數(shù) 階段變量： k。 階段數(shù)記作 n。 無(wú)后效性：如果某階段的狀態(tài)給定，這階段以后過(guò)程的發(fā)展不受這階段以前各階段狀態(tài)的影響 決策 某階段狀態(tài)確定后，為確定下一階段的狀態(tài)，所作出的決定（選擇）。 決策變量： u k(s k) 表示第 k階段狀態(tài)為 s k時(shí)的決策 允許決策集合： D k ( s k ) 動(dòng)態(tài)規(guī)劃的基本概念 狀態(tài) 每個(gè)階段開(kāi)始時(shí)所處的自然狀態(tài)或客觀條件 狀態(tài)變量： s k 狀態(tài)集合： S k 策略： 由決策組成的序列稱為策略。 p 1 , n { u 1(s 1) , u 2(s 2) , … , u n(s n) } 允許策略集合： P1 , n 最優(yōu)策略： p* 1 , n 子策略： 狀態(tài)轉(zhuǎn)移方程 s k+1 = T k ( s k , u k ) 效益 (指標(biāo) )函數(shù) : Vkn(sk,pkn(sk)) 階段效益函數(shù)： wk(sk,uk (sk)) 最優(yōu)效益函數(shù)： fk(sk) 最優(yōu)策略 :pkn* ()kn kpx)*,()( ,11,111 nn psVsf ? 全過(guò)程的最優(yōu)效益函數(shù) 標(biāo)號(hào)法求解最短路問(wèn)題 0 7 6 8 16 14 14 16 21 20 22 26 所以最短路為 A— B1— C2— D2— E，最短路長(zhǎng)為 26。 最優(yōu)化原理 ?????? ??0)()}(),(m i n {)(f5511ksfsfusws kkkkkk動(dòng)態(tài)規(guī)劃的基本方程（逆序法）： f k ( sk)表示從第 k階段狀態(tài) sk到終點(diǎn) F的最短距離 如果一個(gè)策略是最優(yōu)策略，則其子策略也一定是最優(yōu)策略； 如果兩段子策略都是最優(yōu)策略，則連起來(lái)是否是最優(yōu)策略呢？ 動(dòng)態(tài)規(guī)劃的基本方程（ 順序法 ）： ??????? ???0)()() } ,(),(m i n {)(f11111ksfssusfusws kkkkkkkkk 7 網(wǎng)絡(luò)優(yōu)化模型 圖與網(wǎng)絡(luò)的基本概念 最短路徑問(wèn)題 最大流問(wèn)題 最小費(fèi)用最大流問(wèn)題 圖與網(wǎng)絡(luò)的基本概念 連通圖： 圈： 無(wú)向 圖 G =（ V, E）中起點(diǎn)和終點(diǎn)重合的鏈稱為 圈 初等、簡(jiǎn)單圈： 沒(méi)有重復(fù)點(diǎn) 的 圈稱為 初等圈 ，沒(méi)有重復(fù)邊的圈稱為 簡(jiǎn)單圈 。 ( v1 , e1 , v2 , e6 , v4 , e3 , v3 , e5 , v1 ) 圖與網(wǎng)絡(luò)的基本概念 子圖與生成子圖： 子圖： 圖 G=( V, E )， E’是 E的子集， V’是 V的子集，且 E’ 的邊與 V’的頂點(diǎn)想關(guān)聯(lián)， G’=( V’, E’)是圖 G的一個(gè) 子圖 。 生成子圖 ：若 V’=V，則 G’是 G的 生成子圖 圖與網(wǎng)絡(luò)的基本概念 樹(shù)的概念及性質(zhì) 樹(shù)（ T）： 無(wú)圈的連通圖稱為 樹(shù) 樹(shù)葉 分枝點(diǎn) 圖與網(wǎng)絡(luò)的基本概念 樹(shù)的概念及性質(zhì) 樹(shù)的性質(zhì) 性質(zhì) 樹(shù)中任意兩點(diǎn)之間有且只有一條鏈。 性質(zhì) 如圖 G中任意兩點(diǎn)之間，有且只有一條鏈，則該圖 G是一個(gè)樹(shù)。 性質(zhì) 一個(gè)樹(shù)，則 m=n1。 性質(zhì) 樹(shù)中任意兩個(gè)不相鄰的點(diǎn)之間增加一條邊，則形成唯一的圈。 性質(zhì) 一個(gè)樹(shù)如果去掉任何一條邊，該圖就不再連通。 圖與網(wǎng)絡(luò)的基本概念 樹(shù)的概念及性質(zhì) 圖的生成樹(shù) 生成樹(shù)（支撐樹(shù)）： 圖 G的生成子圖是一棵樹(shù)，則稱該樹(shù)為 G的 生成樹(shù) 圖 G中屬于生成樹(shù)的邊稱為 樹(shù)枝 ，不屬于生成樹(shù)的邊稱為 弦 定理 ： 圖 G=（ V,E） ,有生成樹(shù)的充分必要條件為 G是連通圖 最小生成樹(shù) ：圖 G = ( V， E )的生成樹(shù)所有樹(shù)枝上的權(quán)數(shù)的總和 ,稱為 生成樹(shù)的權(quán) 。權(quán)數(shù)最小的生成樹(shù)稱為最小生成樹(shù) 。 尋找最小生成樹(shù)的方法：避圈法、破圈法 最小生成樹(shù) 權(quán) =1
語(yǔ)文相關(guān)推薦
鄂ICP備17016276號(hào)-1