運籌學(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ù)單純形法求解中的判別針對以上標(biāo)準(zhǔn)形式

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

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

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