運(yùn)籌學(xué)總結(jié)課件

1、一、線性規(guī)劃一、線性規(guī)劃 線性規(guī)劃的標(biāo)準(zhǔn)形式：線性規(guī)劃的標(biāo)準(zhǔn)形式：max z=cjxj (1) s.t.aijxj=bi i=1,2,m (2) xj0 j=1,2,n (3) 后續(xù)單純形法求解中的判別針對(duì)以上標(biāo)準(zhǔn)后續(xù)單純形法求解中的判別針對(duì)以上標(biāo)準(zhǔn)形式形式 一、線性規(guī)劃一、線性規(guī)劃 單純形法單純形法 要求約束方程右端項(xiàng)要求約束方程右端項(xiàng)bi非負(fù)（存在基可行解）非負(fù)（存在基可行解） 構(gòu)造初始可行基（有時(shí)需要加入人工變量）構(gòu)造初始可行基（有時(shí)需要加入人工變量） 判斷檢驗(yàn)數(shù)判斷檢驗(yàn)數(shù) 所有非基變量檢驗(yàn)數(shù)都小于零，有唯一解；所有非基變量檢驗(yàn)數(shù)都小于零，有唯一解； 某個(gè)非基變量檢驗(yàn)數(shù)等于零，其余非基變

2、量檢驗(yàn)數(shù)小于零，某個(gè)非基變量檢驗(yàn)數(shù)等于零，其余非基變量檢驗(yàn)數(shù)小于零，無(wú)窮多最優(yōu)解；無(wú)窮多最優(yōu)解； 某個(gè)非基變量檢驗(yàn)數(shù)大于零，且其在約束方程中的系數(shù)小某個(gè)非基變量檢驗(yàn)數(shù)大于零，且其在約束方程中的系數(shù)小于等于零，無(wú)界解；于等于零，無(wú)界解； 所有非基變量檢驗(yàn)數(shù)都小于零，同時(shí)基變量中包含人工變所有非基變量檢驗(yàn)數(shù)都小于零，同時(shí)基變量中包含人工變量，無(wú)可行解。量，無(wú)可行解。 改進(jìn)的單純形法（基于矩陣的單純形法）改進(jìn)的單純形法（基于矩陣的單純形法）一、線性規(guī)劃一、線性規(guī)劃 對(duì)偶問題對(duì)偶問題原問題與對(duì)偶問題的數(shù)學(xué)模型原問題與對(duì)偶問題的數(shù)學(xué)模型 對(duì)偶問題的基本性質(zhì)和基本定理對(duì)偶問題的基本性質(zhì)和基本定理 對(duì)偶單純

3、形法對(duì)偶單純形法一、線性規(guī)劃一、線性規(guī)劃 原問題與對(duì)偶問題的數(shù)學(xué)模型原問題與對(duì)偶問題的數(shù)學(xué)模型原問題標(biāo)準(zhǔn)形式：原問題標(biāo)準(zhǔn)形式：對(duì)偶問題標(biāo)準(zhǔn)形式對(duì)偶問題標(biāo)準(zhǔn)形式：nmijTnaAxxxXXbAXtsCXz)(,),(0. .max21),(0.min21nyyyYYCYAtsYb一、線性規(guī)劃一、線性規(guī)劃 對(duì)偶問題的基本性質(zhì)對(duì)偶問題的基本性質(zhì) 若原問題（對(duì)偶問題）為無(wú)界解，則其對(duì)偶問題若原問題（對(duì)偶問題）為無(wú)界解，則其對(duì)偶問題（原問題）無(wú)可行解。（原問題）無(wú)可行解。 原問題的檢驗(yàn)數(shù)對(duì)應(yīng)對(duì)偶問題的一個(gè)基本解。原問題的檢驗(yàn)數(shù)對(duì)應(yīng)對(duì)偶問題的一個(gè)基本解。一、線性規(guī)劃一、線性規(guī)劃 對(duì)偶問題的基本定理對(duì)偶問題

4、的基本定理 對(duì)稱性定理對(duì)稱性定理 對(duì)偶問題的對(duì)偶是原問題對(duì)偶問題的對(duì)偶是原問題 弱對(duì)偶性定理弱對(duì)偶性定理 若若X(0)和和Y(0)分別是原問題和對(duì)偶問題的可行解，則有分別是原問題和對(duì)偶問題的可行解，則有CX(0)Y(0)b 最優(yōu)性定理最優(yōu)性定理 若若 X(0)和和Y(0)分別是原問題和對(duì)偶問題的可行解，且有分別是原問題和對(duì)偶問題的可行解，且有CX(0) =Y(0)b , 則則X(0) 和和Y(0)分別是原問題和對(duì)偶問題的最優(yōu)解。分別是原問題和對(duì)偶問題的最優(yōu)解。一、線性規(guī)劃一、線性規(guī)劃 對(duì)偶問題的基本定理對(duì)偶問題的基本定理 對(duì)偶定理對(duì)偶定理 一對(duì)對(duì)偶的線性規(guī)劃問題，若其中有一個(gè)有最優(yōu)解，則另一對(duì)

5、對(duì)偶的線性規(guī)劃問題，若其中有一個(gè)有最優(yōu)解，則另一個(gè)也有最優(yōu)解，且目標(biāo)函數(shù)值相等。一個(gè)也有最優(yōu)解，且目標(biāo)函數(shù)值相等。 互補(bǔ)松弛定理互補(bǔ)松弛定理 若若X(0) 和和Y(0)分別是原問題和對(duì)偶問題的可行解，則分別是原問題和對(duì)偶問題的可行解，則X(0)和和Y(0)都是最優(yōu)解的充要條件是都是最優(yōu)解的充要條件是Y(0)Xs=0和和YsX(0)=0。其中其中Xs=(xs1,xs2,xsm)T，xs1,xs2,xsm 是原問題的松弛是原問題的松弛變量，變量，Ys=(ys1,ys2,ysn)T ，ys1,ys2,ysn是對(duì)偶問題的剩是對(duì)偶問題的剩余變量。余變量。 一、線性規(guī)劃一、線性規(guī)劃 對(duì)偶單純形法對(duì)偶單純形

6、法 初始單純型表中所有檢驗(yàn)數(shù)小于等于零，且約初始單純型表中所有檢驗(yàn)數(shù)小于等于零，且約束方程右端項(xiàng)束方程右端項(xiàng)bi小于零的條件下，可應(yīng)用對(duì)偶小于零的條件下，可應(yīng)用對(duì)偶單純形法；單純形法； 通常用于靈敏度分析。通常用于靈敏度分析。練習(xí)練習(xí)(表上作業(yè)法, 10月14日上課時(shí)交)：甲乙兩煤礦供應(yīng)A、B、C三個(gè)城市用煤，各煤礦產(chǎn)量及各城市用煤量見表，各煤礦到各城市之間的運(yùn)輸價(jià)格也見表。 問：甲、乙兩地分別向A、B、C三地運(yùn)輸多少煤礦， 使得煤礦運(yùn)輸?shù)目傮w運(yùn)費(fèi)最低。 (1)應(yīng)用伏格爾法求出初始方案; (2)應(yīng)用閉回路法和閉回路調(diào)整法進(jìn)行最優(yōu)解判別， 給出最優(yōu)方案。 單位運(yùn)價(jià)表 二、整數(shù)規(guī)劃二、整數(shù)規(guī)劃 純

7、整數(shù)規(guī)劃純整數(shù)規(guī)劃 分枝定界法分枝定界法 割平面法割平面法 0-1整數(shù)規(guī)劃整數(shù)規(guī)劃練習(xí)2: 用割平面法求解下列整數(shù)規(guī)劃問題取整數(shù),0,32/12054.34max2121212121xxxxxxxxtsxxZ用隱枚舉法求解0-1規(guī)劃問題12312312323123min z = 4x +3x +2x2x -5x +3x44x +x +3x3 x +x1x ,x ,x0 1或 三、動(dòng)態(tài)規(guī)劃三、動(dòng)態(tài)規(guī)劃 動(dòng)態(tài)規(guī)劃基本方程動(dòng)態(tài)規(guī)劃基本方程 動(dòng)態(tài)規(guī)劃逆序解法動(dòng)態(tài)規(guī)劃逆序解法 動(dòng)態(tài)規(guī)劃順序解法動(dòng)態(tài)規(guī)劃順序解法三、動(dòng)態(tài)規(guī)劃三、動(dòng)態(tài)規(guī)劃 動(dòng)態(tài)規(guī)劃建模方法動(dòng)態(tài)規(guī)劃建模方法 劃分階段，通常按照時(shí)間或空間特征劃分

8、階段。劃分階段，通常按照時(shí)間或空間特征劃分階段。 確定決策變量，可以取問題中的變量為決策變量。確定決策變量，可以取問題中的變量為決策變量。 確定狀態(tài)變量：一般為累計(jì)量或隨遞推過程變化的量。確定狀態(tài)變量：一般為累計(jì)量或隨遞推過程變化的量。 列出狀態(tài)轉(zhuǎn)移方程列出狀態(tài)轉(zhuǎn)移方程 定義指標(biāo)函數(shù)定義指標(biāo)函數(shù) 列出邊界條件列出邊界條件 動(dòng)態(tài)規(guī)劃基本方程動(dòng)態(tài)規(guī)劃基本方程 kk1kkkkkoptsDukksufsusvsfkkk,累加形式指標(biāo)函數(shù)的動(dòng)態(tài)規(guī)劃基本方程累加形式指標(biāo)函數(shù)的動(dòng)態(tài)規(guī)劃基本方程0sf1n1n邊界條件：邊界條件： kk1kkkkkoptsDukksufsusvsfkkk,乘積形式指標(biāo)函數(shù)的動(dòng)態(tài)

9、規(guī)劃基本方程乘積形式指標(biāo)函數(shù)的動(dòng)態(tài)規(guī)劃基本方程邊界條件：邊界條件：1sf1n1n四、排隊(duì)論四、排隊(duì)論 不同類型排隊(duì)系統(tǒng)數(shù)量指標(biāo)的推導(dǎo)不同類型排隊(duì)系統(tǒng)數(shù)量指標(biāo)的推導(dǎo) 基于狀態(tài)轉(zhuǎn)移圖列出狀態(tài)轉(zhuǎn)移方程基于狀態(tài)轉(zhuǎn)移圖列出狀態(tài)轉(zhuǎn)移方程 求解狀態(tài)轉(zhuǎn)移方程得到狀態(tài)概率求解狀態(tài)轉(zhuǎn)移方程得到狀態(tài)概率 基于狀態(tài)概率推導(dǎo)排隊(duì)系統(tǒng)的隊(duì)長(zhǎng)、隊(duì)列長(zhǎng)、基于狀態(tài)概率推導(dǎo)排隊(duì)系統(tǒng)的隊(duì)長(zhǎng)、隊(duì)列長(zhǎng)、等待時(shí)間、逗留時(shí)間等待時(shí)間、逗留時(shí)間 不同類型排隊(duì)系統(tǒng)數(shù)量指標(biāo)的計(jì)算不同類型排隊(duì)系統(tǒng)數(shù)量指標(biāo)的計(jì)算五、對(duì)策論五、對(duì)策論 二人有限零和對(duì)策的求解二人有限零和對(duì)策的求解六、決策論六、決策論 不確定型決策不確定型決策 根據(jù)收益矩陣按照不同準(zhǔn)則

10、選擇方案根據(jù)收益矩陣按照不同準(zhǔn)則選擇方案 風(fēng)險(xiǎn)型決策風(fēng)險(xiǎn)型決策 決策樹法決策樹法 貝葉斯法貝葉斯法六、決策論六、決策論方案分枝方案分枝概率分枝概率分枝決策點(diǎn)方案點(diǎn)結(jié)果點(diǎn)方案點(diǎn)結(jié)果點(diǎn)結(jié)果點(diǎn)結(jié)果點(diǎn)決策樹決策樹按原工按原工藝方案藝方案生產(chǎn)生產(chǎn)價(jià)低價(jià)低 0.1 -100 -200 -300 -200 -300 中中 0.5 0 50 50 0 -250價(jià)高價(jià)高 0.4 100 150 250 200 600買專利買專利(0.8)自研自研(0.6)產(chǎn)量產(chǎn)量不變不變?cè)霎a(chǎn)增產(chǎn)產(chǎn)量產(chǎn)量不變不變?cè)霎a(chǎn)增產(chǎn)(萬(wàn)元萬(wàn)元)84219561073 買 專 利 自 研 制 成 功 0 .8 失 敗 0.2 失 敗 0.4 成 功 0 .6 原 產(chǎn) 增 產(chǎn)0.50.40.10.50.4 原 產(chǎn) 量 增 產(chǎn) 價(jià) 低 0 .1 中 0 . 5 高 0 . 4 價(jià) 低 0 .1 中 0 . 5 高 0 . 40.10.50.40.10.50.4-20050150-30050250-1000100-1000100-2000200-300-250600110.1精品課件精品課件！精品課件精品課件！解：解：8421956107382 買 專 利 自 研 制8263 成 功 0 .8 失 敗 0.2 失 敗 0.4 成 功 0 .69530