《運籌學1》復習提綱第一章線性規(guī)劃和單純形法規(guī)劃問題的三要素線性規(guī)劃問題的條件線性規(guī)劃問題的標準形式標準化方法5.作用在目標函數(shù)中的系數(shù)松弛變量化不等式約束為等式約束0人工變量使系數(shù)矩陣有單位矩陣-M（大M法）可行解、可行域、最優(yōu)解基、基向量、基變量、非基變量、基解、基可行解（至多個）、可行基、最優(yōu)基各種解之間的關(guān)系圖解法冊檢驗數(shù)

線性規(guī)劃問題解的類型用最終表判別的方法無可行解有非0人工變量有可行解有唯一最優(yōu)解無非0人工變量，非基變量的檢驗數(shù)全為負數(shù)線性規(guī)劃問題解的類型用最終表判別的方法無可行解有非0人工變量有可行解有唯一最優(yōu)解無非0人工變量，非基變量的檢驗數(shù)全為負數(shù)有無窮多最優(yōu)解有無界解 無非0人工變量，有一個非基變量的檢驗數(shù)為正數(shù)且這一列的系數(shù)全非正單純形表的結(jié)構(gòu)：前兩行，后一行，前三列，后一列，主體部分單純形法的步驟人工變量法（1）大M法（2）兩階段法單純形法的向量矩陣描述（不考）初始表中的基變量在最終表中的矩陣是 B-1最終表中的基變量在初始表中的矩陣是 B課后練習1.1,1.2(b,1.3(a,1.6(a,1.7(a,1.8,1.12,1.14第二章線性規(guī)劃的對偶理論1、 原問題的基本形式對偶問題的基本形式2、 原問題與對偶問題的互化3、 對偶問題的基本性質(zhì)1弱對偶性2最優(yōu)性3無界性4強對偶性5互補松弛性(由松得緊性)6互補的基解4、 利用對偶理論求最優(yōu)解的方法5、 影子價格6、 靈敏度分析(不考)1分析Cj，可使最優(yōu)解不變2分析bi，可使最優(yōu)基不變3增加一個變量的分析課后練習2.1（a,b,2.2,2.4,2.9（a,b,c第三章運輸問題1、 運輸問題的已知條件：產(chǎn)銷平衡表，單位運價表運輸問題有最優(yōu)解的條件：產(chǎn)銷平衡2、m產(chǎn)n銷的運輸問題有mn個決策變量，有m+n個約束條件，有m+n-1個基變量（有數(shù)字格），有mn-（m+n-1個非基變量（空格）3、 調(diào)運方案表（基可行解）：有數(shù)字格，空格4、 空格的閉回路的構(gòu)成閉回路的作用：1計算檢驗數(shù)2改進方案5、 利用檢驗數(shù)判斷調(diào)運方案的最優(yōu)性若有負檢驗數(shù)，則此方案要改進；若無負檢驗數(shù)，則此方案為最優(yōu)方案。6表上作業(yè)法的步驟1確定初始方案：最小元素法或沃格爾法2求檢驗數(shù)：閉回路法或位勢法3判斷最優(yōu)性4改進方案

7、產(chǎn)銷不平衡的運輸問題的處理-總銷量，從各產(chǎn)地至該銷地的-總產(chǎn)量，從該產(chǎn)地至剛性銷地若產(chǎn)大于銷，則增加虛擬的銷地，其銷量為總產(chǎn)量單價為0；若銷大于產(chǎn)，則增加虛擬的產(chǎn)地，其產(chǎn)量為總銷量的單價為M-總銷量，從各產(chǎn)地至該銷地的-總產(chǎn)量，從該產(chǎn)地至剛性銷地課后練習3.1,3.5(a,b,c,3.6,3.7,3.10第四章整數(shù)規(guī)劃與分配問題1、 整數(shù)規(guī)劃2、 整數(shù)規(guī)劃的分類：純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃3、 整數(shù)規(guī)劃的松弛問題4、 松弛問題的最優(yōu)解與整數(shù)規(guī)劃最優(yōu)解的關(guān)系5、 0-1變量（邏輯變量）0-1規(guī)劃&0-1變量在建模中的作用7、 分配問題已知條件：m階的效率矩陣，獨立0元素M階標準分配問題有m2個0-1變量，有2m個約束條件，是特殊的LP/IP/TP/0-1規(guī)劃，一定有最優(yōu)分配方案8、 匈牙利法1適用范圍2步驟：造0,劃直線，打破僵局3兩個說明：對于目標極大化的分配問題；當人數(shù)大于工作數(shù)時，增加虛擬的工作，每個人完成虛擬工作的時間為 0;當工作數(shù)大于人數(shù)時，增加虛擬的人，虛擬的人完成各項工作的時間為 0或M或其它。課后練習4.1，4.2，4.3，4.5，4.6，4.13，4.16第六章圖與網(wǎng)絡(luò)分析（無向圖G={V,E},點,邊，點與邊之間的關(guān)聯(lián)關(guān)系圖的階網(wǎng)絡(luò)圖（賦權(quán)圖簡單圖連通圖零圖,完全圖，完全偶圖，樹點的次,孤立點，懸掛點子圖,部分圖,部分樹樹的相關(guān)結(jié)論最小部分樹的求法：避圈法,破圈法最短路或最短距離的求法：狄克斯屈拉（dijkstra 標號算法有向圖D={V,A}，點的分類，弧的容量，弧的流量，可行流的條件，總流量，網(wǎng)絡(luò)的最大流，害割的容量，前向弧，后向弧