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

一、線性規(guī)劃線性規(guī)劃的標(biāo)準(zhǔn)形式： maxz=Σcjxj(1)s.t.Σaijxj=bii=1,2,…,m(2)xj≥0j=1,2,…,n(3)后續(xù)單純形法求解中的判別針對(duì)以上標(biāo)準(zhǔn)形式

一、線性規(guī)劃線性規(guī)劃的標(biāo)準(zhǔn)形式：1一、線性規(guī)劃單純形法要求約束方程右端項(xiàng)bi非負(fù)（存在基可行解）構(gòu)造初始可行基（有時(shí)需要加入人工變量）判斷檢驗(yàn)數(shù)所有非基變量檢驗(yàn)數(shù)都小于零，有唯一解；某個(gè)非基變量檢驗(yàn)數(shù)等于零，其余非基變量檢驗(yàn)數(shù)小于零，無(wú)窮多最優(yōu)解；某個(gè)非基變量檢驗(yàn)數(shù)大于零，且其在約束方程中的系數(shù)小于等于零，無(wú)界解；所有非基變量檢驗(yàn)數(shù)都小于零，同時(shí)基變量中包含人工變量，無(wú)可行解。改進(jìn)的單純形法（基于矩陣的單純形法）一、線性規(guī)劃單純形法2一、線性規(guī)劃對(duì)偶問(wèn)題原問(wèn)題與對(duì)偶問(wèn)題的數(shù)學(xué)模型對(duì)偶問(wèn)題的基本性質(zhì)和基本定理對(duì)偶單純形法一、線性規(guī)劃對(duì)偶問(wèn)題3一、線性規(guī)劃原問(wèn)題與對(duì)偶問(wèn)題的數(shù)學(xué)模型原問(wèn)題標(biāo)準(zhǔn)形式：對(duì)偶問(wèn)題標(biāo)準(zhǔn)形式：一、線性規(guī)劃原問(wèn)題與對(duì)偶問(wèn)題的數(shù)學(xué)模型原問(wèn)題標(biāo)準(zhǔn)形式：對(duì)偶問(wèn)4一、線性規(guī)劃對(duì)偶問(wèn)題的基本性質(zhì)若原問(wèn)題（對(duì)偶問(wèn)題）為無(wú)界解，則其對(duì)偶問(wèn)題（原問(wèn)題）無(wú)可行解。原問(wèn)題的檢驗(yàn)數(shù)對(duì)應(yīng)對(duì)偶問(wèn)題的一個(gè)基本解。一、線性規(guī)劃對(duì)偶問(wèn)題的基本性質(zhì)5一、線性規(guī)劃對(duì)偶問(wèn)題的基本定理對(duì)稱性定理對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題弱對(duì)偶性定理若X(0)和Y(0)分別是原問(wèn)題和對(duì)偶問(wèn)題的可行解，則有CX(0)≤Y(0)b最優(yōu)性定理若X(0)和Y(0)分別是原問(wèn)題和對(duì)偶問(wèn)題的可行解，且有CX(0)=Y(0)b,則X(0)和Y(0)分別是原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解。一、線性規(guī)劃對(duì)偶問(wèn)題的基本定理6一、線性規(guī)劃對(duì)偶問(wèn)題的基本定理對(duì)偶定理一對(duì)對(duì)偶的線性規(guī)劃問(wèn)題，若其中有一個(gè)有最優(yōu)解，則另一個(gè)也有最優(yōu)解，且目標(biāo)函數(shù)值相等。互補(bǔ)松弛定理若X(0)和Y(0)分別是原問(wèn)題和對(duì)偶問(wèn)題的可行解，則X(0)和Y(0)都是最優(yōu)解的充要條件是Y(0)Xs=0和YsX(0)=0。

其中Xs=(xs1,xs2,…,xsm)T，xs1,xs2,…,xsm是原問(wèn)題的松弛變量，Ys=(ys1,ys2,…,ysn)T，ys1,ys2,…,ysn是對(duì)偶問(wèn)題的剩余變量。

一、線性規(guī)劃對(duì)偶問(wèn)題的基本定理7一、線性規(guī)劃對(duì)偶單純形法初始單純型表中所有檢驗(yàn)數(shù)小于等于零，且約束方程右端項(xiàng)bi小于零的條件下，可應(yīng)用對(duì)偶單純形法；通常用于靈敏度分析。一、線性規(guī)劃對(duì)偶單純形法8練習(xí)(表上作業(yè)法,10月14日上課時(shí)交)：甲乙兩煤礦供應(yīng)A、B、C三個(gè)城市用煤，各煤礦產(chǎn)量及各城市用煤量見(jiàn)表，各煤礦到各城市之間的運(yùn)輸價(jià)格也見(jiàn)表。問(wèn)：甲、乙兩地分別向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à)表

練習(xí)(表上作業(yè)法,10月14日上課時(shí)交)：9二、整數(shù)規(guī)劃純整數(shù)規(guī)劃分枝定界法割平面法0-1整數(shù)規(guī)劃二、整數(shù)規(guī)劃純整數(shù)規(guī)劃10練習(xí)2:用割平面法求解下列整數(shù)規(guī)劃問(wèn)題練習(xí)2:用割平面法求解下列整數(shù)規(guī)劃問(wèn)題11用隱枚舉法求解0-1規(guī)劃問(wèn)題用隱枚舉法求解0-1規(guī)劃問(wèn)題12運(yùn)籌學(xué)總結(jié)課件13三、動(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ī)劃基本方程14三、動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃建模方法劃分階段，通常按照時(shí)間或空間特征劃分階段。確定決策變量，可以取問(wèn)題中的變量為決策變量。確定狀態(tài)變量：一般為累計(jì)量或隨遞推過(guò)程變化的量。列出狀態(tài)轉(zhuǎn)移方程定義指標(biāo)函數(shù)列出邊界條件動(dòng)態(tài)規(guī)劃基本方程三、動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃建模方法15累加形式指標(biāo)函數(shù)的動(dòng)態(tài)規(guī)劃基本方程邊界條件：乘積形式指標(biāo)函數(shù)的動(dòng)態(tài)規(guī)劃基本方程邊界條件：累加形式指標(biāo)函數(shù)的動(dòng)態(tài)規(guī)劃基本方程邊界條件：乘積形式指標(biāo)函數(shù)16運(yùn)籌學(xué)總結(jié)課件17四、排隊(duì)論不同類型排隊(duì)系統(tǒng)數(shù)量指標(biāo)的推導(dǎo)基于狀態(tài)轉(zhuǎn)移圖列出狀態(tài)轉(zhuǎn)移方程求解狀態(tài)轉(zhuǎn)移方程得到狀態(tài)概率基于狀態(tài)概率推導(dǎo)排隊(duì)系統(tǒng)的隊(duì)長(zhǎng)、隊(duì)列長(zhǎng)、等待時(shí)間、逗留時(shí)間不同類型排隊(duì)系統(tǒng)數(shù)量指標(biāo)的計(jì)算四、排隊(duì)論不同類型排隊(duì)系統(tǒng)數(shù)量指標(biāo)的推導(dǎo)18五、對(duì)策論二人有限零和對(duì)策的求解五、對(duì)策論二人有限零和對(duì)策的求解19六、決策論不確定型決策根據(jù)收益矩陣按照不同準(zhǔn)則選擇方案風(fēng)險(xiǎn)型決策決策樹(shù)法貝葉斯法六、決策論不確定型決策20六、決策論方案分枝概率分枝決策點(diǎn)方案點(diǎn)結(jié)果點(diǎn)方案點(diǎn)結(jié)果點(diǎn)結(jié)果點(diǎn)結(jié)果點(diǎn)決策樹(shù)六、決策論方案分枝概率分枝決策點(diǎn)方案點(diǎn)結(jié)果方案點(diǎn)結(jié)果結(jié)果結(jié)果21按原工藝方案生產(chǎn)價(jià)低0.1-100-200-300-200-300中0.5050500-250價(jià)高0.4100150250200600買(mǎi)專利(0