運(yùn)籌學(xué)復(fù)習(xí)提綱

1、運(yùn)籌學(xué) 1復(fù)習(xí)提綱第一章規(guī)劃問(wèn)題的三要素 線性規(guī)劃問(wèn)題的條件線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)化方法線性規(guī)劃和單純形法1.2.3.4.5.6.可行解、可行域、最優(yōu)解7.向量、基變量、非基變量、基解、基可行解（至多作用在目標(biāo)函數(shù)中的系數(shù)松弛變量化不等式約束為等式約束0人工變量使系數(shù)矩陣有矩陣-M（大 M 法）第二章 線性規(guī)劃的對(duì)偶理論1、原問(wèn)題的基本形式對(duì)偶問(wèn)題的基本形式2、原問(wèn)題與對(duì)偶問(wèn)題的互化3、對(duì)偶問(wèn)題的基本性質(zhì)1)2)3)4)5)6)弱對(duì)偶性最優(yōu)性性 強(qiáng)對(duì)偶性互補(bǔ)松弛性（由松得緊性）互補(bǔ)的基解4、利用對(duì)偶理論求最優(yōu)解的方法5、價(jià)格6、靈敏度分析（不考）1)2)3)分析 Cj，可使最優(yōu)解不變分析

2、bi，可使最優(yōu)基不變?cè)黾右粋€(gè)變量的分析2.1(a,b),2.2,2.4,2.9(a,b,c)第三章1、問(wèn)題的已知條件：產(chǎn)銷(xiāo)平衡表，問(wèn)題有最優(yōu)解的條件：產(chǎn)銷(xiāo)平衡問(wèn)題運(yùn)價(jià)表2、m 產(chǎn) n 銷(xiāo)的問(wèn)題有 mn 個(gè)決策變量，有 m+n 個(gè)約束條件，有 m+n-1 個(gè)基變量（有數(shù)字格），有 mn-(m+n-1)個(gè)非基變量（空格） 3、調(diào)運(yùn)方案表（基可行解）：有數(shù)字格，空格4、空格的閉回路的閉回路的作用：計(jì)算檢驗(yàn)數(shù)改進(jìn)方案5、利用檢驗(yàn)數(shù)判斷調(diào)運(yùn)方案的最優(yōu)性若有負(fù)檢驗(yàn)數(shù)，則此方案要改進(jìn)；若無(wú)負(fù)檢驗(yàn)數(shù)，則此方案為最優(yōu)方案。6、表上作業(yè)法的步驟1)2)3)4)確定初始方案：最小元素法或求檢驗(yàn)數(shù)：閉回路法或位勢(shì)法判

3、斷最優(yōu)性改進(jìn)方案法7、產(chǎn)銷(xiāo)不平衡的問(wèn)題的處理若產(chǎn)大于銷(xiāo)，則增加虛擬的銷(xiāo)地，其銷(xiāo)量為總產(chǎn)量-總銷(xiāo)量，從各產(chǎn)地至該銷(xiāo)地的單價(jià)為 0；若銷(xiāo)大于產(chǎn)，則增加虛擬的產(chǎn)地，其產(chǎn)量為總銷(xiāo)量-總產(chǎn)量，從該產(chǎn)地至剛性銷(xiāo)地的單價(jià)為 M，至彈性銷(xiāo)地的單價(jià)為 0.3.1,3.5(a,b,c),3.6,3.7,3.10第四章 整數(shù)規(guī)劃與分配問(wèn)題1、整數(shù)規(guī)劃2、整數(shù)規(guī)劃的分類(lèi)：純整數(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 變量在建模中的作用7、分配問(wèn)題已知條件：m 階的效率矩陣，獨(dú)立 0 元素M 階標(biāo)準(zhǔn)分配問(wèn)題有個(gè) 0-1 變量，

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