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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

20、：任取一個圈，從圈中去掉一邊，對余下的圖重復這個步驟，直到不含圈時為止，即得到一個支撐樹。閉圈法：4、 最小支撐樹問題Ø 知識準備賦權圖Ø 最小支撐樹：在所有的支撐樹中權最小的樹Ø 最小支撐樹的求法避圈法破圈法5、 最短路問題Ø 知識準備最短路Ø 最短路的算法雙標號（T標號、P標號）算法，也叫狄克斯拉算法理論基礎：假定(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、計算最佳經濟訂購批量、模型的運用條件（假設條件）Ø 模型的假設條件1. 缺貨費用無窮大；2. 當存儲降至零時，可以立即得到補充（模型中不考慮缺貨費用）；3. 需求是連續的、均勻的，設需求速度R（單位時間的需求量）為常數，則時間段t內的需求量為Rt；4. 每次訂貨量不變，訂購費不變；5. 單位存儲費不變。Ø 存儲量變化圖Ø 衡量存儲策略優劣的指標總平均費用Ø 最佳的訂購時間間隔、經濟訂購批量、最佳費用1. 最佳的訂購時間間隔2. 經濟訂購批量3. 最佳費用其中，是單位時間內單位物品的存儲費用，是訂購費（除了商品價款外的其它費用），是單位時間的需求量。推導過

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