運(yùn)籌學(xué)復(fù)習(xí)筆記

1、運(yùn)籌學(xué)復(fù)習(xí)筆記Part 1 題型1. 選擇題（20分）2. 填空題（40分）3. 建模題（40分）4. 決策問(wèn)題（20分）5. 運(yùn)輸問(wèn)題（10分）計(jì)算Part 2 需要掌握的知識(shí)點(diǎn)Chapter 2 線性規(guī)劃與單純型法1、 線性規(guī)劃問(wèn)題（建模）2、 求解兩個(gè)變量的線性規(guī)劃模型圖解法 附：圖解法的啟示1) 圖解法求解結(jié)果的幾種可能情況：Ø 唯一最優(yōu)解Ø 無(wú)窮多最優(yōu)解Ø 無(wú)界解（并不是說(shuō)可行域是無(wú)界的線性規(guī)劃問(wèn)題的解就一定是無(wú)界解）Ø 無(wú)可行解2) 若線性規(guī)劃問(wèn)題的可行域非空，則可行域是一個(gè)凸集。3) 若線性規(guī)劃問(wèn)題的最優(yōu)解存在，則一定可以在可行域的凸集的某

2、個(gè)頂點(diǎn)達(dá)到。（線性規(guī)劃問(wèn)題的基可行解X對(duì)應(yīng)于可行域D的頂點(diǎn)。）3、 單純形法準(zhǔn)備知識(shí)標(biāo)準(zhǔn)型1) 標(biāo)準(zhǔn)型的四個(gè)條件Ø 目標(biāo)函數(shù)為極大（max）Ø 所有的約束條件滿足等式Ø 所有的決策變量非負(fù)Ø 右端常數(shù)均為非負(fù)數(shù)2) 化為標(biāo)準(zhǔn)型的方法Ø 若要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化，即max z=CX。這時(shí)只需將目標(biāo)函數(shù)最小化變換求目標(biāo)函數(shù)最大化，即令 z=-z，于是得到max z= CX。這就同標(biāo)準(zhǔn)型的目標(biāo)函數(shù)的形式一致了。Ø 約束方程為不等式。這里有兩種情況： 一種是約束方程為不等式，則可在不等式的左端加入非負(fù)松弛變量，把原不等式變?yōu)榈仁剑?另一種是

3、約束方程為不等式，則可在不等式的左端減去一個(gè)非負(fù)剩余變量（也可稱松弛變量），把不等式約束條件變?yōu)榈仁郊s束條件,目標(biāo)函數(shù)中加上 (松弛變量).Ø 若變量約束中：，則令，得到；若，則令 ，其中，用 、分別代替、后得到線性規(guī)劃的變量約束均為非負(fù)約束。Ø 資源限量bi 0。4、 單純型法準(zhǔn)備知識(shí)線性規(guī)劃問(wèn)題解的概念1) 可行解：滿足約束條件式（等式約束、非負(fù)約束）的解。2) 最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。3) 基：約束方程組的系數(shù)矩陣的一個(gè)滿秩的子矩陣，B稱為線性規(guī)劃問(wèn)題的一個(gè)基。附：基向量：B矩陣中每一個(gè)列向量都稱為基向量?；兞浚哼x定的向量（基向量）對(duì)應(yīng)的變量（可以不止

4、一個(gè)）稱為基變量，其他的變量稱為非基變量。4) 基解：有一個(gè)基就可以求出一個(gè)基解（運(yùn)用克萊姆法則）。5) 基可行解：滿足非負(fù)條件式的基解（基解是根據(jù)等式約束條件得到的，還沒(méi)有涉及目標(biāo)函數(shù)和變量非負(fù)的約束條件，相當(dāng)于對(duì)一個(gè)非齊次線性方程組求解。當(dāng)這樣的基解滿足變量非負(fù)的約束條件時(shí)，我們稱它為基可行解。PS：并不一定是最優(yōu)解。）6) 可行基：與基可行解相對(duì)應(yīng)的基稱為可行基。7) 可行域（可行空間）8) 幾何性質(zhì)凸集的概念 考題：求基解、判斷是否為基可行解、是否為最優(yōu)解5、 線性規(guī)劃問(wèn)題的一些性質(zhì)6、 單純形表（了解，知道如何尋找主元）口訣：最大最小找主元初行變換得新解（新的基可行解）目標(biāo)函數(shù)有改善

5、 例題：1. 例2-1線性規(guī)劃問(wèn)題建模2. 用圖解法求解例2-1中建立的線性規(guī)劃模型3. 把例2-1中建立的線性規(guī)劃模型化為標(biāo)準(zhǔn)型4. 指出例2-1中建立模型的基、基變量、基解、基可行解和可行基5. 單純型表相關(guān)的題型230000812100401640010-01204001323000進(jìn)行一輪計(jì)算以后得到下表230006. 一個(gè)更為復(fù)雜的建模題某工廠明年根據(jù)合同，每個(gè)季度末向銷售公司提供產(chǎn)品，有關(guān)信息如表，若當(dāng)季生產(chǎn)的產(chǎn)品過(guò)多，季末有積余，則一個(gè)季度每積壓一噸產(chǎn)品需支付存貯費(fèi)0.2萬(wàn)元。現(xiàn)該廠考慮明年的最佳生產(chǎn)方案，使該廠在完成合同的情況下，全年的生產(chǎn)費(fèi)用最低。試建立線性規(guī)劃模型。季度生產(chǎn)

6、能力生產(chǎn)成本需求量1301520240142032015.33041014.810Chapter 3 對(duì)偶理論與靈敏度分析（4分）1、 影子價(jià)格1) 含義：代表在資源最優(yōu)利用條件下，對(duì)第i種資源一單位的估價(jià)，這種估價(jià)不是資源的市場(chǎng)價(jià)格，而是根據(jù)資源在生產(chǎn)中做出的貢獻(xiàn)而做的估價(jià)。2) 經(jīng)濟(jì)意義Ø 影子價(jià)格反映資源對(duì)目標(biāo)函數(shù)的邊際貢獻(xiàn)，即資源轉(zhuǎn)化成經(jīng)濟(jì)效益的效率。Ø 影子價(jià)格反映了資源的稀缺程度。Ø 影子價(jià)格反映了資源的邊際使用價(jià)值。Chapter 4 運(yùn)輸問(wèn)題（10分）1、 確定初始基可行解最小元素法、伏格爾法確定初始可行解的方法考試不要求，但是對(duì)于理解最優(yōu)解的判別

7、很有幫助。單位運(yùn)價(jià)表產(chǎn)地銷地B1B2B3B4A1311310A21928A374105產(chǎn)銷平衡表產(chǎn)地銷地產(chǎn)量B1B2B3B4A17A24A39銷地3656-Ø 最小元素法思想：從單價(jià)中最小的運(yùn)價(jià)開始確定供銷關(guān)系，然后次小，一直到給出初始基可行解為止。Step 1 產(chǎn)地銷地B1B2B3B4A1311310A21928A374105產(chǎn)地銷地產(chǎn)量B1B2B3B4A17A234A39銷地3656-Step 2 產(chǎn)地銷地B1B2B3B4A1311310A21928A374105產(chǎn)地銷地產(chǎn)量B1B2B3B4A17A2314A39銷地3656-Step 3 產(chǎn)地銷地B1B2B3B4A1311310

8、A21928A374105產(chǎn)地銷地產(chǎn)量B1B2B3B4A1437A2314A3639銷地3656- 口訣：最小運(yùn)價(jià)定方向，需求滿足便退出，供給耗盡線劃去；余下運(yùn)價(jià)找最小，直到運(yùn)價(jià)全劃去，所得必是可行解。Ø 伏格爾法最小元素法的缺點(diǎn)：可能開始節(jié)省一處的費(fèi)用，但隨后在其他幾處要多花幾倍的運(yùn)費(fèi)。伏格爾法的思想：對(duì)差額最大處采用最小運(yùn)費(fèi)調(diào)運(yùn)。Step 1 根據(jù)單位運(yùn)價(jià)表分別算出各行和各列的最小運(yùn)費(fèi)和次小運(yùn)費(fèi)的差額。產(chǎn)地銷地行差額B1B2B3B4A13113100A219281A3741051列差額2513-Step 2 從行和列差額中選出最大者，選擇它所在的行或列中的最小元素，確定供給方向。

9、（這一步是對(duì)伏格爾法思想的體現(xiàn)）產(chǎn)地銷地行差額B1B2B3B4A13113100A219281A3741051列差額2513-產(chǎn)地銷地行差額B1B2B3B4A13113100A219281A3741051列差額2512-產(chǎn)地銷地行差額B1B2B3B4A13113107A219281A3741051列差額25310-產(chǎn)地銷地行差額B1B2B3B4A13113103A219281A3741051列差額25310-產(chǎn)地銷地產(chǎn)量B1B2B3B4A1527A2314A3639銷地3656- 口訣：行列運(yùn)價(jià)求差額，差額最大找最?。ú铑~最大行、列處找最小的運(yùn)價(jià)），最小運(yùn)價(jià)定方向；需求滿足便退出，供給耗盡線劃

10、去；余下步驟均相同，直到運(yùn)價(jià)全劃去，所得必是可行解。2、 最優(yōu)解的判別方法閉回路法要求：求檢驗(yàn)數(shù)、調(diào)整方案、往下進(jìn)行一步（46分）（選填題）最優(yōu)解的判別方法：計(jì)算空格（非基變量）的檢驗(yàn)數(shù)。當(dāng)檢驗(yàn)數(shù)還存在負(fù)數(shù)時(shí)，說(shuō)明原方案不是最優(yōu)解，需要繼續(xù)改進(jìn)。 例題：用閉回路法檢驗(yàn)上一步中最小元素法得到的初始基可行解是否為最優(yōu)解。產(chǎn)地銷地產(chǎn)量B1B2B3B4A1437A2314A3639銷地3656-閉回路法計(jì)算檢驗(yàn)數(shù)的經(jīng)濟(jì)解釋：在已給出初始解的上表中，可以從任一空格出發(fā)，如（A1，B1），若讓A1的產(chǎn)品調(diào)勻一噸給B1。為了保持產(chǎn)銷平衡，就要依次做調(diào)整：在（A1，B3）處減少一噸，（A2，B3）處增加一噸，

11、（A2，B1）處減少一噸，即構(gòu)成（A1，B1）空格為起點(diǎn)，其他為數(shù)字格的閉回路。檢驗(yàn)數(shù)調(diào)整后運(yùn)費(fèi)的增減數(shù)本例中的檢驗(yàn)數(shù)為：，以其他空格為起點(diǎn)可以得到更多的檢驗(yàn)數(shù)。如果得到的檢驗(yàn)數(shù)全為正，則說(shuō)明初始方案無(wú)法得到進(jìn)一步改進(jìn)，即初始方案為最優(yōu)解；反之，初始基可行解不為最優(yōu)，還存在改進(jìn)的空間。3、 運(yùn)輸問(wèn)題的一些性質(zhì)Ø 基變量的個(gè)數(shù)（上一個(gè)知識(shí)點(diǎn)中，通過(guò)最小元素法得到的初始基可行解的基變量的個(gè)數(shù)為6） PS：在產(chǎn)銷平衡的運(yùn)輸問(wèn)題中，。Ø 閉回路的頂點(diǎn)數(shù)永遠(yuǎn)是偶數(shù)（只有這樣才能保證產(chǎn)銷的均衡）Chapter 5 整數(shù)線性規(guī)劃（20分）1、 整數(shù)規(guī)劃問(wèn)題（建模）：把文字描述分析轉(zhuǎn)化為數(shù)

12、學(xué)模型整數(shù)規(guī)劃問(wèn)題：是一類特殊的線性規(guī)劃問(wèn)題，是指要求部分或全部決策變量的取值為整數(shù)的規(guī)劃問(wèn)題。其中，重點(diǎn)掌握整數(shù)線性規(guī)劃問(wèn)題。2、 整數(shù)規(guī)劃問(wèn)題的決策3、 整數(shù)線性規(guī)劃問(wèn)題的類型Ø 純整數(shù)線性規(guī)劃（重點(diǎn)掌握）全部決策變量都必須取整數(shù)值Ø 混合整數(shù)線性規(guī)劃決策變量中一部分必須取整數(shù)值，另一部分可以不取整數(shù)值Ø 0-1型整數(shù)線性規(guī)劃（重點(diǎn)掌握指派問(wèn)題）決策變量只能取0或1（用于表現(xiàn)分析投資還是不投資這類問(wèn)題）4、 人力資源的分配問(wèn)題（選填題）要求：明白求解的邏輯和方法，求解的結(jié)果不要求給出Ø 標(biāo)準(zhǔn)指派問(wèn)題的數(shù)學(xué)模型 1 指派第 i 個(gè)人做第 j 件事 0

13、不指派第 i 個(gè)人做第 j 件事PS：一項(xiàng)任務(wù)只能由一個(gè)人完成，一個(gè)人只能完成一項(xiàng)任務(wù)。Ø 指派問(wèn)題的匈牙利解法匈牙利法求最優(yōu)解的理論依據(jù)指派問(wèn)題最優(yōu)解的性質(zhì)：若從系數(shù)矩陣（）的一行（列）各元素中分別減去該行（列）的最小元素，得到新的矩陣（），那么以（）為系數(shù)矩陣求得的最優(yōu)解和用原系數(shù)矩陣求得的最優(yōu)解相同。Step 1 使指派問(wèn)題的系數(shù)矩陣經(jīng)變換，在各行各列中都出現(xiàn)0元素（只有這樣才能保證每個(gè)人都被分配到任務(wù)）。系數(shù)矩陣的每行元素減去該行的最小元素；再?gòu)南禂?shù)矩陣的每列元素中減去該列的最小元素；若某行（列）已有0元素，那就不必再減了。Step 2 進(jìn)行試指派，以尋求最優(yōu)解。目標(biāo)：尋找獨(dú)

14、立的0元素（位于不同行不同列的0元素），獨(dú)立的0元素的位置便是需要安排人的地方，這樣的安排所需要的總時(shí)間最少（總耗費(fèi)最低）。目標(biāo)的實(shí)現(xiàn)方法：當(dāng)n（任務(wù)數(shù)或者人數(shù)）較小時(shí)觀察法、試探法（重點(diǎn)掌握）；當(dāng)n較大時(shí)采用以下步驟尋找0元素：Step 2.1 從只有一個(gè)0元素的行開始，給這個(gè)0元素加圈圈。這表示對(duì)這行所代表的人，只有一種任務(wù)可指派。然后劃去圈圈所在列的其他0元素，記作。這表示這列所代表的任務(wù)已經(jīng)指派完，不需要再考慮其他人了。Step 2.2 給只有一個(gè)0元素列的0元素加圈圈。這表示這列所代表的這項(xiàng)任務(wù)，只有一個(gè)人做。然后劃去圈圈所在行的其他0元素，記作。這表示這行所代表的人已經(jīng)被只拍了任務(wù)

15、，對(duì)其他的任務(wù)不再考慮。Step 2.3 反復(fù)進(jìn)行step 2.1 和step 2.2 ，直到所有的0元素都被圈出和劃掉為止。Step 2.4 （這一步太復(fù)雜，等以后慢慢研究吧）Step 2.5 若畫圈圈元素的數(shù)目m等于矩陣（方陣）的階數(shù)，那么指派問(wèn)題的最優(yōu)解已得到。 例題1 整數(shù)線性規(guī)劃問(wèn)題的建模與求解某廠利用集裝箱托運(yùn)甲、乙兩種貨物，每箱體積重量、可獲利潤(rùn)及托運(yùn)限制如下：體積重量利潤(rùn)甲5220乙4510托運(yùn)限制2413-兩種貨物各托運(yùn)多少箱使利潤(rùn)最大？ 例題2 建模人力資源的分配問(wèn)題（指派問(wèn)題）有一份中文說(shuō)明書，需譯成英、日、德、俄四種文字，分別記做E、J、G、R?，F(xiàn)有甲、乙、丙、丁4人，

16、他們將中文說(shuō)明書翻譯成不同語(yǔ)種的說(shuō)明書所需的時(shí)間如下，問(wèn)應(yīng)指派何人去完成何種工作，使所需總時(shí)間最少？效率矩陣（系數(shù)矩陣）人員 任務(wù)EJGR甲2151314乙1041415丙9141613丁78119 例題3 指派問(wèn)題的求解匈牙利解法（有難度）人員任務(wù)ABCDE甲127979乙89666丙71712149丁15146610戊4107109Chapter 8 & 9 圖與網(wǎng)絡(luò)分析（10分）1、 了解一些圖的基本的概念結(jié)合圖形理解下列概念：Ø 邊、?。喊褍牲c(diǎn)之間不帶箭頭的連線稱為邊，帶箭頭的連線稱為弧。Ø 無(wú)向圖：如果一個(gè)圖是由點(diǎn)及邊所構(gòu)成的，則稱之為無(wú)向圖（也簡(jiǎn)稱為圖）

17、，記為G（V，E）。Ø 有向圖：如果一個(gè)圖是由點(diǎn)及弧所構(gòu)成，則稱為有向圖，記為D（V，A）。Ø 無(wú)向圖的一些名詞和記號(hào)： （邊的）端點(diǎn)、（點(diǎn)與點(diǎn)）相鄰、（邊是點(diǎn)的）關(guān)聯(lián)邊、環(huán)（兩個(gè)端點(diǎn)相同的邊）、多重邊（兩個(gè)點(diǎn)之間有多余一條的邊）、簡(jiǎn)單圖（無(wú)環(huán)無(wú)多重邊的圖）、多重圖（一個(gè)無(wú)環(huán)，但允許有多重邊的圖）、次：以點(diǎn)v為端點(diǎn)的邊的個(gè)數(shù)稱為點(diǎn)v的次，記為d(v)。要求：會(huì)計(jì)算（數(shù)）端點(diǎn)的次、特別注意有環(huán)存在時(shí)的次（記兩次）。懸掛點(diǎn)、懸掛邊：次為1的點(diǎn)稱為懸掛點(diǎn)、懸掛點(diǎn)的關(guān)聯(lián)邊稱為懸掛邊。孤立點(diǎn)：次為零的點(diǎn)稱為孤立點(diǎn)。 奇點(diǎn)、偶點(diǎn)：次數(shù)為奇的點(diǎn)稱為奇點(diǎn)，次數(shù)為偶的點(diǎn)稱為偶點(diǎn)。 鏈、中間點(diǎn)

18、、圈 初等鏈：中間點(diǎn)均為不同點(diǎn)的鏈稱為初等鏈（一個(gè)點(diǎn)不經(jīng)過(guò)兩次）； 初等圈：中間點(diǎn)均為不同點(diǎn)的圈稱為初等圈。 簡(jiǎn)單鏈（圈）：鏈（圈）中含有的邊均不相同（同一個(gè)邊不經(jīng)過(guò)兩次）。 連通圖、不聯(lián)通圖：任何兩個(gè)點(diǎn)之間至少有一條鏈的圖，否則稱為不連通圖。 連通分圖：若G是不連通圖，它的每個(gè)連通的部分稱為G的一個(gè)連通分圖（簡(jiǎn)稱分圖）。 支撐子圖：給一個(gè)圖，如果圖，使及，則稱為的一個(gè)支撐子圖。Ø 有向圖的一些名詞和記號(hào)基礎(chǔ)圖：設(shè)給了一個(gè)有向圖，從D中去掉所有弧上的箭頭就得到一個(gè)無(wú)向圖，稱之為D的基礎(chǔ)圖，記為?！坝邢驁D無(wú)向化以后得到有向圖的基礎(chǔ)圖”。始點(diǎn)、終點(diǎn)：給D中的一條弧a=(u,v)，稱u為a

19、的始點(diǎn)，v為a的終點(diǎn)。路回路Ø 鏈（P標(biāo)號(hào)、T標(biāo)號(hào)）2、 樹Ø 樹的定義：一個(gè)無(wú)圈的連通圖稱為樹Ø 樹的性質(zhì)1 設(shè)圖是一個(gè)樹，則G中至少有兩個(gè)懸掛點(diǎn)。 PS：圖G或圖D的點(diǎn)數(shù)記為或，邊（?。?shù)記為或2 圖是一個(gè)樹的充分必要條件是G不含圈，且恰有條邊3 圖是一個(gè)樹的充分必要條件是任意兩個(gè)頂點(diǎn)之間恰有一條鏈（無(wú)論去掉哪一條邊，都會(huì)變成一個(gè)不連通圖）3、 圖的支撐樹Ø 支撐樹的定義：設(shè)圖是圖的支撐子圖，如果是一個(gè)樹，則稱T是G的一個(gè)支撐樹。Ø 尋求連通圖的支撐樹的方法破圈法、閉圈法這兩種方法的理論支持：圖G有支撐樹的充分必要條件是圖G是連通的。破圈法

20、：任取一個(gè)圈，從圈中去掉一邊，對(duì)余下的圖重復(fù)這個(gè)步驟，直到不含圈時(shí)為止，即得到一個(gè)支撐樹。閉圈法：4、 最小支撐樹問(wèn)題Ø 知識(shí)準(zhǔn)備賦權(quán)圖Ø 最小支撐樹：在所有的支撐樹中權(quán)最小的樹Ø 最小支撐樹的求法避圈法破圈法5、 最短路問(wèn)題Ø 知識(shí)準(zhǔn)備最短路Ø 最短路的算法雙標(biāo)號(hào)（T標(biāo)號(hào)、P標(biāo)號(hào)）算法，也叫狄克斯拉算法理論基礎(chǔ)：假定(1，2)，(2，3)，(3，4)是點(diǎn)1到4的最短路，則(1，2)，(2，3)是點(diǎn)1到3的最短路；(2，3)，(3，4)是點(diǎn)2到4的最短路。Chapter 10 存儲(chǔ)論（4分）（選填題）1、 模型一：不允許缺貨、備貨時(shí)間很短要求：

21、計(jì)算最佳經(jīng)濟(jì)訂購(gòu)批量、模型的運(yùn)用條件（假設(shè)條件）Ø 模型的假設(shè)條件1. 缺貨費(fèi)用無(wú)窮大；2. 當(dāng)存儲(chǔ)降至零時(shí)，可以立即得到補(bǔ)充（模型中不考慮缺貨費(fèi)用）；3. 需求是連續(xù)的、均勻的，設(shè)需求速度R（單位時(shí)間的需求量）為常數(shù)，則時(shí)間段t內(nèi)的需求量為Rt；4. 每次訂貨量不變，訂購(gòu)費(fèi)不變；5. 單位存儲(chǔ)費(fèi)不變。Ø 存儲(chǔ)量變化圖Ø 衡量存儲(chǔ)策略優(yōu)劣的指標(biāo)總平均費(fèi)用Ø 最佳的訂購(gòu)時(shí)間間隔、經(jīng)濟(jì)訂購(gòu)批量、最佳費(fèi)用1. 最佳的訂購(gòu)時(shí)間間隔2. 經(jīng)濟(jì)訂購(gòu)批量3. 最佳費(fèi)用其中，是單位時(shí)間內(nèi)單位物品的存儲(chǔ)費(fèi)用，是訂購(gòu)費(fèi)（除了商品價(jià)款外的其它費(fèi)用），是單位時(shí)間的需求量。推導(dǎo)過(guò)

22、程如下：PS：由于時(shí)間t是相同的，所以上式的表達(dá)是正確的。PS：其中K是貨物的單價(jià)對(duì)總平均費(fèi)用關(guān)于t求一階導(dǎo)，令其為0，得，即為最佳訂購(gòu)時(shí)間間隔。其他變量的推導(dǎo)相同。PS：由于經(jīng)濟(jì)訂購(gòu)批量和最佳訂購(gòu)時(shí)間間隔均和貨物的單價(jià)K無(wú)關(guān)，所以我們?cè)诳傎M(fèi)平均用函數(shù)中不考慮含有K的項(xiàng)。即，代入最佳訂購(gòu)時(shí)間間隔均可得最佳費(fèi)用。Ø 例題1 某廠按合同每年需提供D個(gè)產(chǎn)品，不許缺貨。假設(shè)每一周期工廠需裝配費(fèi)元，存儲(chǔ)費(fèi)每年每單位產(chǎn)品為元，為全年應(yīng)分幾批供貨才能使裝配費(fèi)，存儲(chǔ)費(fèi)兩者之和最少？Ø 例題2某軋鋼廠每月按計(jì)劃需產(chǎn)角鋼30000噸，每噸每月存儲(chǔ)費(fèi)53元，每次生產(chǎn)需調(diào)整及其設(shè)備等，共需裝配費(fèi)250000元?，F(xiàn)在該廠每月生產(chǎn)角鋼一次，生產(chǎn)批量為30000