運(yùn)籌學(xué)胡運(yùn)權(quán)第五版復(fù)習(xí)提綱匯總

1、運(yùn)籌學(xué)1復(fù)習(xí)提綱第一章線性規(guī)劃和單純形法1 .規(guī)劃問(wèn)題的三要素2 .線性規(guī)劃問(wèn)題的條件3 .線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式4 .標(biāo)準(zhǔn)化方法5 .作用在目標(biāo)函數(shù)中的系數(shù)松弛變量化不等式約束為等式約束 0人工變量 使系數(shù)矩陣有單位矩陣-M （大M法）6 .可行解、可行域、最優(yōu)解7 .基、基向量、基變量、非基變量、基解、基可行解（至多 q個(gè)）、可行基、最優(yōu)基8 .各種解之間的關(guān)系9 .圖解法10 .檢驗(yàn)數(shù)對(duì)11.線性規(guī)劃問(wèn)題 解的類型用最終表判別的方法無(wú)可行解有非0人工變量有可行解有唯一最優(yōu)解無(wú)非0人工變量，非基 變量的檢驗(yàn)數(shù)全為負(fù)數(shù)有無(wú)窮多最優(yōu)無(wú)非0人工變量，非基變解量的檢驗(yàn)數(shù)全非正，且有一個(gè)非基變量的檢

2、驗(yàn)數(shù)為0有無(wú)界解無(wú)非0人工變量，有一個(gè) 非基變量的檢驗(yàn)數(shù)為正 數(shù)且這一列的系數(shù)全非 正12 .單純形表的結(jié)構(gòu)：前兩行，后一行，前三列，后一列，主 體部分13 .單純形法的步驟14 .人工變量法（1）大M法（2）兩階段法15.單純形法的向量矩陣描述（不考）初始表中的基變量在最終表中的矩陣是B-1最終表中的基變量在初始表中的矩陣是課后練習(xí)1.1,1.2(b,1.3(a,1.6(a,1.7(a,1.8,1.12,1.14第二章線性規(guī)劃的對(duì)偶理論1、原問(wèn)題的基本形式對(duì)偶問(wèn)題的基本形式2、原問(wèn)題與對(duì)偶問(wèn)題的互化3、對(duì)偶問(wèn)題的基本性質(zhì)1弱對(duì)偶性2最優(yōu)性3無(wú)界性4強(qiáng)對(duì)偶性5互補(bǔ)松弛性(由松得緊性)6互補(bǔ)的基

3、解4、利用對(duì)偶理論求最優(yōu)解的方法5、影子價(jià)格6、靈敏度分析(不考)1分析Cj,可使最優(yōu)解不變2分析bi ,可使最優(yōu)基不變3增加一個(gè)變量的分析課后練習(xí)2.1（a,b,2.2,2.4,2.9（a,b,c第三章運(yùn)輸問(wèn)題1、運(yùn)輸問(wèn)題的已知條件：產(chǎn)銷平衡表，單位運(yùn)價(jià)表運(yùn)輸問(wèn)題有最優(yōu)解的條件：產(chǎn)銷平衡2、m產(chǎn)n銷的運(yùn)輸問(wèn)題有mn個(gè)決策變量，有m+n個(gè)約束條件，有 m+n-1個(gè)基變量（有數(shù)字格），有mn-（m+n-1個(gè)非基變量（空格）3、調(diào)運(yùn)方案表（基可行解）：有數(shù)字格，空格4、空格的閉回路的構(gòu)成閉回路的作用：1計(jì)算檢驗(yàn)數(shù)2改進(jìn)方案5、利用檢驗(yàn)數(shù)判斷調(diào)運(yùn)方案的最優(yōu)性若有負(fù)檢驗(yàn)數(shù)，則此方案要改進(jìn)；若無(wú)負(fù)檢驗(yàn)數(shù)

4、，則此方案為最優(yōu)方案。6、表上作業(yè)法的步驟1確定初始方案：最小元素法或沃格爾法2求檢驗(yàn)數(shù)：閉回路法或位勢(shì)法3判斷最優(yōu)性4改進(jìn)方案7、產(chǎn)銷不平衡的運(yùn)輸問(wèn)題的處理若產(chǎn)大于銷，則增加虛擬的銷地，其銷量為總產(chǎn)量-總銷量，從各產(chǎn)地至該銷地的單價(jià)為0;若銷大于產(chǎn)，則增加虛擬的產(chǎn)地，其產(chǎn)量為總銷量-總產(chǎn)量，從該產(chǎn)地至剛性銷地的單價(jià)為M至彈性銷地的單價(jià)為0.課后練習(xí)3.1,3.5（a,b,c,3.6,3.7,3.10第四章 整數(shù)規(guī)劃與分配問(wèn)題1、整數(shù)規(guī)劃2、整數(shù)規(guī)劃的分類：純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃3、整數(shù)規(guī)劃的松弛問(wèn)題4、松弛問(wèn)題的最優(yōu)解與整數(shù)規(guī)劃最優(yōu)解的關(guān)系5、0-1變量（邏輯變量）0-1規(guī)劃6、0-1變量

5、在建模中的作用7、分配問(wèn)題已知條件：m階的效率矩陣，獨(dú)立0元素M階標(biāo)準(zhǔn)分配問(wèn)題有 m2個(gè)0-1變量，有2m個(gè)約束條件，是特殊的LP/IP/TP/0-1 規(guī)劃，一定有最優(yōu)分配方案8、匈牙利法1適用范圍2步驟：造0,劃直線，打破僵局對(duì)于目標(biāo)極大化的分配問(wèn)題；當(dāng)人數(shù)大于工作數(shù)時(shí)，增加虛擬的工作，每個(gè)人完成虛擬工作的時(shí)間為0;當(dāng)工作數(shù)大于人數(shù)時(shí)，增加虛擬的人，虛擬的人完成各項(xiàng)工作的時(shí)間為0或M或其它。課后練習(xí)4.1 , 4.2 , 4.3 , 4.5 , 4.6 , 4.13 , 4.16第六章圖與網(wǎng)絡(luò)分析1 .（無(wú)向圖G=V,E,點(diǎn)，邊，點(diǎn)與邊之間的關(guān)聯(lián)關(guān)系2 .圖的階3 .網(wǎng)絡(luò)圖（賦權(quán)圖4 .簡(jiǎn)單圖5 .連通圖6 .零圖，完全圖，完全偶圖，樹(shù)7 .點(diǎn)的次，孤立點(diǎn)，懸掛點(diǎn)8 .子圖，部分圖，部分樹(shù)9 .樹(shù)的相關(guān)結(jié)論10 .最小部分樹(shù)的求法：避圈法，破圈法11 .最短路或最短距離的求法：狄克斯屈拉（dijkstra標(biāo)號(hào)算法12 .有向圖D= V,A,點(diǎn)的分類，弧的容量,弧的流量，可行流的條件，總流 量，網(wǎng)絡(luò)的最大流，割，割的容量，前向弧，后向弧，增廣鏈的條件，重要結(jié)論：最小割的容量=最大流的流量