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

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

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

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

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

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

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

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

9、（這一步是對伏格爾法思想的體現(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)價求差額，差額最大找最?。ú铑~最大行、列處找最小的運(yùn)價），最小運(yùn)價定方向；需求滿足便退出，供給耗盡線劃

10、去；余下步驟均相同，直到運(yùn)價全劃去，所得必是可行解。2、 最優(yōu)解的判別方法閉回路法要求：求檢驗數(shù)、調(diào)整方案、往下進(jìn)行一步（46分）（選填題）最優(yōu)解的判別方法：計算空格（非基變量）的檢驗數(shù)。當(dāng)檢驗數(shù)還存在負(fù)數(shù)時，說明原方案不是最優(yōu)解，需要繼續(xù)改進(jìn)。 例題：用閉回路法檢驗上一步中最小元素法得到的初始基可行解是否為最優(yōu)解。產(chǎn)地銷地產(chǎn)量B1B2B3B4A1437A2314A3639銷地3656-閉回路法計算檢驗數(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）空格為起點，其他為數(shù)字格的閉回路。檢驗數(shù)調(diào)整后運(yùn)費(fèi)的增減數(shù)本例中的檢驗數(shù)為：，以其他空格為起點可以得到更多的檢驗數(shù)。如果得到的檢驗數(shù)全為正，則說明初始方案無法得到進(jìn)一步改進(jìn)，即初始方案為最優(yōu)解；反之，初始基可行解不為最優(yōu)，還存在改進(jìn)的空間。3、 運(yùn)輸問題的一些性質(zhì)Ø 基變量的個數(shù)（上一個知識點中，通過最小元素法得到的初始基可行解的基變量的個數(shù)為6） PS：在產(chǎn)銷平衡的運(yùn)輸問題中，。Ø 閉回路的頂點數(shù)永遠(yuǎn)是偶數(shù)（只有這樣才能保證產(chǎn)銷的均衡）Chapter 5 整數(shù)線性規(guī)劃（20分）1、 整數(shù)規(guī)劃問題（建模）：把文字描述分析轉(zhuǎn)化為數(shù)

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

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

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

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

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

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

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

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

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

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

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