運籌學(xué)期末復(fù)習(xí)提綱

1、l線性規(guī)劃問題及其數(shù)學(xué)模型l圖解法l單純形法原理l單純形法計算步驟l單純形法的進一步討論l目標能表成求 MAX 或 MINl達到目標有多種方案l實現(xiàn)目標有一定條件l目標和條件都能用線性函數(shù)表示例如，對于線性規(guī)劃問題 0,6323523632max432143214214321xxxxxxxxxxxxxxxz其系數(shù)矩陣為 31125023則下面兩個矩陣都是該線性規(guī)劃問題的基。12233152和還能找出其它基嗎？基解基解：令非基變量等于0的解?；尚薪猓夯尚薪猓夯?+ 可行解 例如，對于上面的線性規(guī)劃問題，如果取x1，x2為基變量，則令非基變量x3，x4為零，約束方程組為 623232121x

2、xxx解之得 。故我們得到基解注意到這個基解還是一個可行解。 712,71521xx0, 0,712,7154321xxxx是否所有的基解都是基可行解？（選x1,x3作為基變量）0,1823122453max54321321423221xxxxxxxxxxxxxxz2.3 (1)x1x2x3x4x5z是否可行12620036y24306027y34600-642n460-612018n5094-6045n60640630y740012612y800412180y(2) 圖解法 對只包含兩個決策變量只包含兩個決策變量的線性規(guī)劃問題，可以用圖解法圖解法來求解。圖解法顧名思義就是通過作圖來求解的方法

3、，它簡單直觀、并有助于說明一般線性規(guī)劃問題求解的基本原理。 線性規(guī)劃的標準形式線性規(guī)劃的標準形式0,.,. .max2122122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz它具有如下四個特征：目標函數(shù)求max；約束方程符號取“=” ；bi非負；所有決策變量xj非負。l線性規(guī)劃問題的所有可行解構(gòu)成的集合是凸集，也可能為無限集。他們有有限個頂點，線性規(guī)劃問題的每個基可行解對應(yīng)可行域一個頂點，反之亦然。若線性規(guī)劃問題有最優(yōu)解，必在某頂點達到。l將人工變量在目標函數(shù)中反映出來得到如下形式的線性規(guī)劃：0,4222212

4、232max876543216321853217432187321xxxxxxxxxxxxxxxxxxxxxxMxMxxxxz0, 0, 0, 2, 0, 2 . 1, 4 . 1, 087654321xxxxxxxx4 . 5527*z因此最優(yōu)解為最優(yōu)目標函數(shù)值為需要說明的是，如果在用大M法求解線性規(guī)劃問題時，最終表的基變量中還含有人工變量，那么這個最終表并沒有給出原來問題的基可行解，從而沒有給出原來的線性規(guī)劃問題最優(yōu)解。這時原來線性規(guī)劃問題為無可行解無可行解。用用EXCEL執(zhí)行該計算過程執(zhí)行該計算過程0, 2, 0,56,57, 0654321xxxxxx4 . 55/27*z故原來問題的

5、最優(yōu)解為最優(yōu)目標函數(shù)值這一結(jié)果與大M法得到的結(jié)果是一致的。無可行解的判別無可行解的判別：在用大M法求解線性規(guī)劃問題時，若最終單純形表的基變量中含人工變量；或用兩階段法求解時，第一階段最終表的基變量中含非零的人工變量，也就是第一階段最優(yōu)目標函數(shù)值不等于零，則線性規(guī)劃問題無可行解。 規(guī)范形式的線性規(guī)劃與對偶規(guī)劃問題規(guī)范形式的線性規(guī)劃與對偶規(guī)劃問題0. .maxXbAXtsCXz0. .minYCYAtsYbw原問題（LP）對偶問題（DLP） 3.2.2 弱對偶性定理：弱對偶性定理： 如果X、Y分別是原問題和對偶問題的一個可行解，則其對應(yīng)的原問題的目標函數(shù)值不大于對偶問題的目標函數(shù)值，也即YbCX0

6、XbAX0YCYAYbYAXYAXCXCX)(證明：證明：因為X、Y分別是原問題（3.1）與對偶問題（3.2）的可行解，故： 所以l推論一：推論一：原問題任一可行解的目標函數(shù)值是其對偶問題目標函數(shù)值的下界；反之對偶問題任一可行解的目標函數(shù)值是起原問題目標函數(shù)值的上界。l推論二：如果原問題存在無界解，則對偶問題一定無可行解；反之，如果對偶問題存在無界解，原問題也一定不存在可行解。l注意，該推論的逆反定理并不成立。l注意，該推論的逆反定理并不成立。l推論三：如果原問題無解，且對偶問題有可行解，則對偶問題具有無解解，；反之，如果對偶問題無解，且原問題有可行解，則對偶問題具有無界解。l 最優(yōu)性定理約束

7、 方程 也分為兩種情況： ，約束條件比較松； ，約束條件比較緊；yi=0,分為兩種情況：yi0，約束條件比較松；yi=0，約束條件比較緊；injjijbxa1injjijbxa1injjijbxa1變量同其對偶問題的約束方程之間至多只能夠有一個取松弛的情況，當其中一個取松弛的情況時，另外一個比較緊，即取嚴格等號 。l例已知下面的LP1和LP2為一組對偶規(guī)劃，且已知LP1的最優(yōu)解為X=（1.5，1）。試運用互補松弛定理求出對偶問題的最優(yōu)解Y。0,934425223max2121212121xxxxxxxxs.t.xxz生產(chǎn)計劃問題（LP1）資源定價問題（LP2）0,232342. .945min

8、321321321321yyyyyyyyytsyyyw解：由X=（1.5，1）得55 . 3221 xx01y0, 021xx232342321321yyyyyy聯(lián)立求解得：5 . 0, 5 . 0, 0321yyy 解：由X=（1.5，1）得55 . 3221 xx01y0, 021xx232342321321yyyyyy聯(lián)立求解得：5 . 0, 5 . 0, 0321yyy 解：由X=（1.5，1）得55 . 3221 xx01y0, 021xx232342321321yyyyyy聯(lián)立求解得：5 . 0, 5 . 0, 0321yyy 約束條件右端向量b的變化（1）偏差變量）偏差變量 d+

9、：正偏差變量，表示決策值超出目標值的部分：正偏差變量，表示決策值超出目標值的部分 d-：負偏差變量，表示決策值未達到目標值的部分：負偏差變量，表示決策值未達到目標值的部分 按定義有：按定義有：d+ 0， d- 0 ，d+ d- = 0（2）絕對約束和目標約束）絕對約束和目標約束 絕對約束（硬約束）：必須嚴格滿足的約束條件絕對約束（硬約束）：必須嚴格滿足的約束條件 目標約束（軟約束）：目標規(guī)劃特有目標約束（軟約束）：目標規(guī)劃特有 （3）優(yōu)先因子（）優(yōu)先因子（P）和權(quán)系數(shù)（）和權(quán)系數(shù)（W） 優(yōu)先因子用優(yōu)先因子用P1，P2， Pl表示，規(guī)定表示，規(guī)定 Pl Pl+1，表示，表示Pl比比Pl+1有更大

10、的優(yōu)先權(quán)。有更大的優(yōu)先權(quán)。（4）目標函數(shù)）目標函數(shù) 決策值決策值=目標值目標值 min f (d+ + d- ) 決策值決策值目標值目標值 min f (d- ) l例例4.1 某企業(yè)計劃生產(chǎn)甲、乙兩種產(chǎn)品。已知有關(guān)數(shù)某企業(yè)計劃生產(chǎn)甲、乙兩種產(chǎn)品。已知有關(guān)數(shù)據(jù)見表據(jù)見表4-1。問如何安排生產(chǎn)使獲得的總利潤最大？。問如何安排生產(chǎn)使獲得的總利潤最大？項項 目目甲甲 乙乙 擁有量擁有量原材料原材料（kg）2111設(shè)備設(shè)備（臺時臺時)1210利利 潤（元潤（元/件）件）810表表 4-1l設(shè)設(shè)x1、x2分別表示計劃生產(chǎn)產(chǎn)品甲、乙的產(chǎn)量，它的數(shù)學(xué)模分別表示計劃生產(chǎn)產(chǎn)品甲、乙的產(chǎn)量，它的數(shù)學(xué)模型為：型為：

11、l它的最優(yōu)解為它的最優(yōu)解為x1=4，x2=3，最大目標函數(shù)值為，最大目標函數(shù)值為62。max z=8x1+10 x2 2x1+ x2 11st. x1+ 2x2 10 x1 , x20l但企業(yè)的經(jīng)營目標不僅是利潤，企業(yè)還考慮了以下問題：但企業(yè)的經(jīng)營目標不僅是利潤，企業(yè)還考慮了以下問題：（1）根據(jù)市場信息，產(chǎn)品甲開始出現(xiàn)滯銷現(xiàn)象，故考慮產(chǎn)品）根據(jù)市場信息，產(chǎn)品甲開始出現(xiàn)滯銷現(xiàn)象，故考慮產(chǎn)品甲的產(chǎn)量應(yīng)不超過產(chǎn)品乙；甲的產(chǎn)量應(yīng)不超過產(chǎn)品乙；（2）超過計劃供應(yīng)的原材料需高價采購，應(yīng)避免過量消耗；）超過計劃供應(yīng)的原材料需高價采購，應(yīng)避免過量消耗； （3）應(yīng)盡可能充分利用設(shè)備臺時，但不希望加班；）應(yīng)盡可能

12、充分利用設(shè)備臺時，但不希望加班；（4）應(yīng)盡可能達到并超過計劃利潤指標）應(yīng)盡可能達到并超過計劃利潤指標56元。元。 l例例4.2 例例4.1的決策者經(jīng)過綜合考慮，決策者的目標分別為：的決策者經(jīng)過綜合考慮，決策者的目標分別為：首先原材料使用限額不能突破；其次產(chǎn)品甲的產(chǎn)量不大于首先原材料使用限額不能突破；其次產(chǎn)品甲的產(chǎn)量不大于產(chǎn)品乙；再次充分利用設(shè)備臺時，不希望加班；最后利潤產(chǎn)品乙；再次充分利用設(shè)備臺時，不希望加班；最后利潤額不少于額不少于56元。問應(yīng)如何安排生產(chǎn)？元。問應(yīng)如何安排生產(chǎn)？l解：原材料使用限額的約束是絕對約束，其他三個約束是解：原材料使用限額的約束是絕對約束，其他三個約束是屬于目標約束

13、，分別賦予這三個目標的優(yōu)先因子為屬于目標約束，分別賦予這三個目標的優(yōu)先因子為P1，P2，P3。這問題的數(shù)學(xué)模型為：。這問題的數(shù)學(xué)模型為： 2x1 + x2 11 x1 - x2 + d1- - d1+ =0 x1 + 2x2 + d2- - d2+ =108x1 + 10 x2 + d3- - d3+ =56 x1,x2,di-,di+ 0 i=1,2,3min P1 d1+ , P2 ( d2- + d2+ ) , P3 d3- s.t.32目標規(guī)劃模型的一般形式：目標規(guī)劃模型的一般形式： Min Pl（ wlk-dk- + wlk+dk+ ）,l=1,2,Lk =1Kckj xj + dk

14、- - dk+ = gk ， k =1，2，Kj =1naij xj （=，） bi ，i =1，2，mj =1nxj 0 , j =1，2，ndk- ，dk+ 0 , k =1，2，KS.t.33目標規(guī)劃模型的一般形式：目標規(guī)劃模型的一般形式： Min Pl（ wlk-dk- + wlk+dk+ ）,l=1,2,Lk =1Kckj xj + dk- - dk+ = gk ， k =1，2，Kj =1naij xj （=，） bi ，i =1，2，mj =1nxj 0 , j =1，2，ndk- ，dk+ 0 , k =1，2，KS.t.當總產(chǎn)量當總產(chǎn)量 = = 總銷量，稱為產(chǎn)銷平衡問題總銷量

15、，稱為產(chǎn)銷平衡問題 當總產(chǎn)量當總產(chǎn)量總銷量，稱為產(chǎn)銷不平衡問題總銷量，稱為產(chǎn)銷不平衡問題06=+5=+6=+3=+9=+4=+7=+5+10+4+7+8+2+9+01+3+11+3=min343332312423222114131211342414332313322212312111343332312423222114131211343332312423222114131211xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxs.t.xxxxxxxxxxxxzl運輸問題含有運輸問題含有mn個變量，個變量，m+n個約束方程。其系數(shù)矩陣的結(jié)構(gòu)比個約束方程。其系數(shù)矩陣的結(jié)構(gòu)比較

16、特殊，對應(yīng)變量較特殊，對應(yīng)變量xij的系數(shù)向量，其分量中除第的系數(shù)向量，其分量中除第i個和第個和第m+j個為個為1以以外，其余的都為零外，其余的都為零 l模型中只有個相互獨立的約束方程。因此，運輸問題的任一基可行解模型中只有個相互獨立的約束方程。因此，運輸問題的任一基可行解都有都有m+n-1個基變量個基變量 。2) 沃格爾法沃格爾法列罰數(shù)列罰數(shù)行罰數(shù)行罰數(shù)25130116213012 321212017635200126 31433111= c11-c13+c23-c21=3-3+2-1=1解的最優(yōu)性檢驗解的最優(yōu)性檢驗 1) 閉回路法閉回路法63 34130310-1 -529121-1101

17、2vj ui基變量：基變量：cij = ui+vj 非基變量：非基變量：ij = cij (ui + vj)l1.一般產(chǎn)銷不平衡運輸問題一般產(chǎn)銷不平衡運輸問題1)1)總產(chǎn)量總產(chǎn)量 總銷量總銷量 n1jjm1iiba 0 xn,3,2,1j,bxm,3,2,1i,ax.t .sxczminijm1ijijn1jiijm1in1jijij假想一銷地假想一銷地Bn+1，令銷量為，令銷量為 , 運價運價c = 0 n1jjm1iiba5.1 整數(shù)規(guī)劃實例及一般模整數(shù)規(guī)劃實例及一般模型型5.2 分支定界法分支定界法5.3 0-1整數(shù)規(guī)劃整數(shù)規(guī)劃5.4 指派問題指派問題l純整數(shù)規(guī)劃：純整數(shù)規(guī)劃：xj全部是

18、整數(shù)全部是整數(shù)l混合整數(shù)規(guī)劃：混合整數(shù)規(guī)劃： xj部分是整數(shù)部分是整數(shù)l0-1型整數(shù)規(guī)劃：型整數(shù)規(guī)劃：xj = 0或或1整數(shù)規(guī)劃的可行解集合是它的松弛問題可整數(shù)規(guī)劃的可行解集合是它的松弛問題可行解集合的一個子集，即整數(shù)規(guī)劃的可行解行解集合的一個子集，即整數(shù)規(guī)劃的可行解一定是其松弛問題的可行解（反之不然）一定是其松弛問題的可行解（反之不然）整數(shù)規(guī)劃問題的最優(yōu)目標函數(shù)值不會優(yōu)于整數(shù)規(guī)劃問題的最優(yōu)目標函數(shù)值不會優(yōu)于其松弛問題最優(yōu)解的目標函數(shù)值其松弛問題最優(yōu)解的目標函數(shù)值若松弛問題的可行解滿足整數(shù)約束，則它若松弛問題的可行解滿足整數(shù)約束，則它也是整數(shù)規(guī)劃的可行解也是整數(shù)規(guī)劃的可行解整數(shù)規(guī)劃問題的最優(yōu)解

19、不能由其松弛問題整數(shù)規(guī)劃問題的最優(yōu)解不能由其松弛問題最優(yōu)解經(jīng)過簡單取整得到最優(yōu)解經(jīng)過簡單取整得到如用如用“舍入取整法舍入取整法”可得可得到到4 4個點即個點即(2(2，2), (22), (2，3), (33), (3，2), (32), (3，3)3)。顯。顯然，它們都不可能是整數(shù)然，它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。規(guī)劃的最優(yōu)解。且取整數(shù)0,823324max21212121xxxxxxxxz松弛問題最優(yōu)解整數(shù)規(guī)劃最優(yōu)解不能通過舍入取整地方法，由松弛不能通過舍入取整地方法，由松弛問題的解得到整數(shù)規(guī)劃的最優(yōu)解問題的解得到整數(shù)規(guī)劃的最優(yōu)解6.1 動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念6.2 最優(yōu)化

20、原理最優(yōu)化原理6.3 經(jīng)濟管理問題舉例經(jīng)濟管理問題舉例動態(tài)規(guī)劃的分類：動態(tài)規(guī)劃的分類：離散確定型離散確定型 離散隨機型離散隨機型 連續(xù)確定型連續(xù)確定型 連續(xù)隨機型連續(xù)隨機型決策決策1 1狀態(tài)狀態(tài)1決策決策2 2狀態(tài)狀態(tài)2決策決策n n狀態(tài)狀態(tài)3狀態(tài)狀態(tài)n1、階段、階段 ，階段數(shù)，階段數(shù)階段變量：階段變量：k; 階段數(shù)記作階段數(shù)記作n。無后效性：如果某階段的狀態(tài)給定，這階段以后過程的無后效性：如果某階段的狀態(tài)給定，這階段以后過程的發(fā)展不受這階段以前各階段狀態(tài)的影響發(fā)展不受這階段以前各階段狀態(tài)的影響 3、決策、決策 某階段狀態(tài)確定后，為確定下一階段的狀態(tài)，所作出某階段狀態(tài)確定后，為確定下一階段的狀

21、態(tài)，所作出的決定（選擇）。的決定（選擇）。 決策變量：決策變量：u k(s k) 表示第表示第k階段狀態(tài)為階段狀態(tài)為s k時的決策時的決策 允許決策集合：允許決策集合：D k ( s k )2、狀態(tài)、狀態(tài)每個階段開始時所處的自然狀態(tài)或客觀條件每個階段開始時所處的自然狀態(tài)或客觀條件狀態(tài)變量：狀態(tài)變量：s k狀態(tài)集合：狀態(tài)集合：S k4、策略：、策略： 由決策組成的序列稱為策略。由決策組成的序列稱為策略。 p 1 , n u 1(s 1) , u 2(s 2) , , u n(s n) 允許策略集合：允許策略集合：P1 , n最優(yōu)策略：最優(yōu)策略： p* 1 , n 子策略：子策略：5、狀態(tài)轉(zhuǎn)移方程

22、、狀態(tài)轉(zhuǎn)移方程 s k+1 = T k ( s k , u k )6、效益、效益(指標指標)函數(shù)函數(shù): Vkn(sk,pkn(sk) 階段效益函數(shù)：階段效益函數(shù)：wk(sk,uk (sk) 最優(yōu)效益函數(shù)：最優(yōu)效益函數(shù)：fk(sk) 最優(yōu)策略最優(yōu)策略:pkn*()knkpx)*,()(,11,111nnpsVsf全過程的最優(yōu)效益函數(shù)全過程的最優(yōu)效益函數(shù)07681614141621202226所以最短路為AB1C2D2E，最短路長為26。0)()(),(min)(f5511ksfsfuswskkkkkk動態(tài)規(guī)劃的基本方程（逆序法）：動態(tài)規(guī)劃的基本方程（逆序法）：f k ( sk)表示從第表示從第k

23、階段狀態(tài)階段狀態(tài)sk到終點到終點F的最短距離的最短距離如果一個策略是最優(yōu)策略，則其子策略也一定是最優(yōu)策略；如果一個策略是最優(yōu)策略，則其子策略也一定是最優(yōu)策略；如果兩段子策略都是最優(yōu)策略，則連起來是否是最優(yōu)策略呢？如果兩段子策略都是最優(yōu)策略，則連起來是否是最優(yōu)策略呢？動態(tài)規(guī)劃的基本方程（動態(tài)規(guī)劃的基本方程（順序法順序法）：）：0)()(),(),(min)(f11111ksfssusfuswskkkkkkkkk圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念 最短路徑問題最短路徑問題 最大流問題最大流問題 最小費用最大流問題最小費用最大流問題5 5、連通圖：、連通圖：圈：圈：無向無向圖G =（V, E）中起點和終點重合的）中起點和終點重合的鏈稱為鏈稱為圈圈初等、簡單圈：初等、簡單圈：沒有重復(fù)點沒有重復(fù)點的的圈稱為圈稱為初等圈初等圈，沒有重復(fù)邊，沒有重復(fù)邊的圈稱為的圈稱為簡單圈簡單圈。( v( v1 1 , e , e1 1 , v , v2 2 , e , e6 6 , v , v4 4 , e , e3 3 , v , v3 3 , e , e5 5 , v , v1 1 ) )6 6、子圖與生成子圖：、子圖與生成子圖：子圖：子圖：圖圖G=( V, E )，E是是E的子集，的子集，V是是V的子的子集，且集，且E 的邊與的邊與V的頂點想關(guān)聯(lián)，的頂點想關(guān)聯(lián)， G=( V, E)是圖是