1、第一章第一章 線性規劃線性規劃LINEAR PROGRAMMINGLINEAR PROGRAMMING本章的主要內容本章的主要內容一般線性規劃問題的數學模型一般線性規劃問題的數學模型圖解法圖解法單純形法原理單純形法原理單純形法的計算步驟單純形法的計算步驟單純形法的進一步討論單純形法的進一步討論數據包絡分析數據包絡分析 School of Management Harbin Institute of Technology 2線性規劃問題的數學模型線性規劃問題的數學模型規劃問題規劃問題生產和經營管理中經常提出如何合理安排，使人力、物力等資源得到充分利用，獲得最大的效益，這就是規劃問題線性規劃通常解

2、決以下兩類問題線性規劃通常解決以下兩類問題當任務和目標確定后，如何統籌兼顧，合理安排，用最少的資源去完成確定的任務和目標在一定的資源限制下，如何組織安排生產獲得最好的經濟效益School of Management Harbin Institute of Technology 3線性規劃問題的數學模型線性規劃問題的數學模型School of Management Harbin Institute of Technology 4線性規劃問題的數學模型線性規劃問題的數學模型 例子例子1.2 1.2 某企業計劃生產甲，乙兩種產品。這兩某企業計劃生產甲，乙兩種產品。這兩種產品需要在種產品需要在A A，

3、B B，C C三種不同的設備上進行三種不同的設備上進行加工。按工藝需求，加工各種產品所需每種設加工。按工藝需求，加工各種產品所需每種設備的單位工時如下表所示，問如何安排生產計備的單位工時如下表所示，問如何安排生產計劃，使企業的總利潤最大？劃，使企業的總利潤最大？School of Management Harbin Institute of Technology 5ABC甲甲2402乙乙2053121615線性規劃問題的數學模型線性規劃問題的數學模型School of Management Harbin Institute of Technology 6線性規劃問題的數學模型線性規劃問題的數學

4、模型線性規劃的數學模型由以下三個要素線性規劃的數學模型由以下三個要素決策變量決策變量 decision variabledecision variable目標函數目標函數 objective functionobjective function約束條件約束條件 constrainsconstrains線性規劃問題的辨別線性規劃問題的辨別目標函數是多個決策變量的線性函數，取最大值或最小值約束條件是一組多個決策變量的線性不等式或等式School of Management Harbin Institute of Technology 7線性規劃問題的數學模型線性規劃問題的數學模型School of

5、 Management Harbin Institute of Technology 8線性規劃問題的數學模型線性規劃問題的數學模型School of Management Harbin Institute of Technology 9線性規劃問題的數學模型線性規劃問題的數學模型標準形式的轉換標準形式的轉換目標函數的轉換目標函數的轉換無約束決策變量的轉換無約束決策變量的轉換約束方程的轉換約束方程的轉換 松弛變量松弛變量 剩余變量剩余變量非正決策變量的轉換非正決策變量的轉換School of Management Harbin Institute of Technology 10線性規劃問題的

6、數學模型線性規劃問題的數學模型School of Management Harbin Institute of Technology 11線性規劃問題的數學模型線性規劃問題的數學模型School of Management Harbin Institute of Technology 12School of Management Harbin Institute of Technology 13線性規劃數學模型假設線性規劃數學模型假設（1 1）比例性）比例性（2 2）可疊加性）可疊加性（3 3）可分性）可分性（4 4）確定性）確定性School of Management Harbin Ins

7、titute of Technology 14構建構建線性規劃數學模型線性規劃數學模型（1 1）分析問題：確定決策內容、要實）分析問題：確定決策內容、要實現的目標以及所受到的限制條件。現的目標以及所受到的限制條件。（2）具體構造模型：選擇合適的決策具體構造模型：選擇合適的決策變量、確定目標函數的表達式、約變量、確定目標函數的表達式、約束條件的表達式，分析各變量取值束條件的表達式，分析各變量取值的符號限制。的符號限制。School of Management Harbin Institute of Technology 15構建構建線性規劃數學模型線性規劃數學模型例例1：某工廠在生產過程中需要使

8、用濃度為：某工廠在生產過程中需要使用濃度為80%的硫酸的硫酸100 噸，而市面上只有濃度為噸，而市面上只有濃度為30%，45%，73%，85%，92%的硫酸出售，的硫酸出售， 每噸的價格每噸的價格分別為分別為400、700、1400、1900和和2500元。元。 問：問：采用怎樣的購買方案，才能使所需總費用最小？采用怎樣的購買方案，才能使所需總費用最??？School of Management Harbin Institute of Technology 16構建構建線性規劃數學模型線性規劃數學模型例例2：設有下面四個投資機會：設有下面四個投資機會： 甲：在三年內，投資人應在每年年初投資，每年

9、每元投甲：在三年內，投資人應在每年年初投資，每年每元投資可獲利資可獲利0.2元，每年取息后可重新將本息用于投資。元，每年取息后可重新將本息用于投資。 乙：在三年內，投資人應在第一年年初投資，每兩年每乙：在三年內，投資人應在第一年年初投資，每兩年每元投資可獲利元投資可獲利0.5元，兩年后取息，取息后可重新將本息用元，兩年后取息，取息后可重新將本息用于投資。這種投資最多不得超過于投資。這種投資最多不得超過20,000元。元。 丙：在三年內，投資人應在第二年年初投資，兩年后每丙：在三年內，投資人應在第二年年初投資，兩年后每元投資可獲利元投資可獲利0.6元。這種投資最多不得超過元。這種投資最多不得超過

10、15,000元。元。 ?。涸谌陜龋顿Y人應在第三年年初投資，一年后每丁：在三年內，投資人應在第三年年初投資，一年后每元投資可獲利元投資可獲利0.4元。這種投資最多不得超過元。這種投資最多不得超過10,000元。元。 假定在這三年為一期的投資中，每期的開始有假定在這三年為一期的投資中，每期的開始有30,000元元資金可供使用，問：采取怎樣的投資計劃，才能在第三年資金可供使用，問：采取怎樣的投資計劃，才能在第三年年底獲得最大收益？年底獲得最大收益？School of Management Harbin Institute of Technology 17構建構建線性規劃數學模型線性規劃數學模型例

11、例3：合理下料：合理下料問題問題： ： 要制作要制作100套套鋼鋼筋架子，每套含筋架子，每套含2.9米、米、2.1米、米、1.5米的米的鋼鋼筋各一根。已知原料筋各一根。已知原料長長7.4米，米，問問：如何下料，使用料最：如何下料，使用料最??？省？方案方案下料數下料數長長度度2.9米米2.1米米1.5米米121221 3123合合計計(米米)7.47.37.27.16.6料料頭頭(米米)00.10.20.30.8School of Management Harbin Institute of Technology 18思考思考題題： ：目目標標函數是否可以函數是否可以選選取取為為 min z=x

12、1+x2+x3+x4+x5 ， ，為為什么？什么？構建構建線性規劃數學模型線性規劃數學模型School of Management Harbin Institute of Technology 19構建構建線性規劃數學模型線性規劃數學模型例例4 4：有：有A A、 、B B兩種兩種產產品，都需要品，都需要經過經過前、后兩到化學反前、后兩到化學反應過應過程。每種程。每種產產品需品需要的反要的反應時間應時間及其可供使用的及其可供使用的總時間總時間如表示。如表示。 每生每生產產一個一個單單位位產產品品B B的同的同時時，會，會產產生生2 2個個單單位的副位的副產產品品C C，且不需，且不需外加任何外

13、加任何費費用。副用。副產產品品C C的一部分可以出售盈利，其余的只能加以的一部分可以出售盈利，其余的只能加以銷毀銷毀。 。 副副產產品品C C每每賣賣出一個出一個單單位可位可獲獲利利3 3元，但是如果元，但是如果賣賣不出去，不出去，則則每每單單位需位需銷毀費銷毀費用用2 2元。元。預測預測表明，最多可售出表明，最多可售出5 5個個單單位的副位的副產產品品C C。 。 要求確定使利要求確定使利潤潤最大的最大的生生產計產計劃。劃。線性規劃問題的數學模型線性規劃問題的數學模型線性規劃問題的解線性規劃問題的解求解線性規劃問題，就是從滿足約束條件（2）（3）的解中找出一個解，使目標函數（1）達到最大值S

14、chool of Management Harbin Institute of Technology 20線性規劃問題的數學模型線性規劃問題的數學模型School of Management Harbin Institute of Technology 21線性規劃問題的數學模型線性規劃問題的數學模型 基解：某一確定的基基解：某一確定的基B B，零非基變量等于零，由約束條，零非基變量等于零，由約束條件方程（件方程（2 2）解出基變量，稱這組解為基解。在基解中）解出基變量，稱這組解為基解。在基解中，變量取非零的個數不大于方程數，變量取非零的個數不大于方程數m m。 基可行解：滿足變量非負約束的基

15、解稱為基可行解?；尚薪猓簼M足變量非負約束的基解稱為基可行解。 可行基：對應于基可行解的基稱為可行基?？尚谢簩诨尚薪獾幕Q為可行基。School of Management Harbin Institute of Technology 22線性規劃問題的數學模型線性規劃問題的數學模型有解，或無解有解，或無解解就在那里解就在那里可行才是關鍵可行才是關鍵最優，或不優最優，或不優答案就在那里答案就在那里頂點才能發現頂點才能發現School of Management Harbin Institute of Technology 23線性規劃問題的數學模型線性規劃問題的數學模型School o

16、f Management Harbin Institute of Technology 24線性規劃問題的數學模型線性規劃問題的數學模型基基基解基解是基可行解？是基可行解？ 目目標標函數函數x1x2x3x4x5P1P2P343-200否17P1P2P433040是15*P1P2P542005是14P1P3P5404015是8P1P4P5600-815否12P2P3P4036160是9P2P4P506016-15否18P3P4P500121615是0School of Management Harbin Institute of Technology 25圖解法圖解法線性規劃求解方法線性規劃求解

17、方法圖解法單純形法對于只有兩個決策變量的線性規劃問對于只有兩個決策變量的線性規劃問題，可以通過圖解的方法求解。圖解題，可以通過圖解的方法求解。圖解法簡單直觀，有助于我們理解線性規法簡單直觀，有助于我們理解線性規劃求解的基本原理和幾何意義。劃求解的基本原理和幾何意義。School of Management Harbin Institute of Technology 26圖解法圖解法School of Management Harbin Institute of Technology 27圖解法圖解法School of Management Harbin Institute of Techno

18、logy 28圖解法圖解法 線性規劃問題的解：唯一最優解、無窮多最線性規劃問題的解：唯一最優解、無窮多最優解、無界解、無可行解優解、無界解、無可行解 若線性規劃問題的可行域存在，則該可行域若線性規劃問題的可行域存在，則該可行域是一個凸集是一個凸集 若若LPLP的最優解存在，則最優解或最優解之一的最優解存在，則最優解或最優解之一一定能夠在可行域（凸集）的某個頂點找到一定能夠在可行域（凸集）的某個頂點找到 解題思路是先找到凸集中的任意一點，計算解題思路是先找到凸集中的任意一點，計算目標函數值，與周邊相鄰頂點目標函數進行目標函數值，與周邊相鄰頂點目標函數進行比較比較School of Managem

19、ent Harbin Institute of Technology 29單純形法原理單純形法原理School of Management Harbin Institute of Technology 30單純形法原理單純形法原理School of Management Harbin Institute of Technology 31單純形法原理單純形法原理School of Management Harbin Institute of Technology 32單純形法原理單純形法原理School of Management Harbin Institute of Technology 3

20、3單純形法原理單純形法原理可行解聚成凸集可行解聚成凸集向量獨立方為基向量獨立方為基頂點對應基可行頂點對應基可行最優需到基中尋最優需到基中尋School of Management Harbin Institute of Technology 34單純形法原理單純形法原理School of Management Harbin Institute of Technology 35單純形法原理單純形法原理 從初始基可行解轉換為另一基可行解從初始基可行解轉換為另一基可行解 最優解檢驗和解的判斷最優解檢驗和解的判斷 所有檢驗數不大于零，對應的基可行解為最優解 所有檢驗數不大于零，并且某個非基變量的檢驗數

21、等于零，則該問題有無窮多最優解； 如果某個檢驗數大于零，并且其對應的約束條件系數向量的所有分量均不大于零，則該問題存在無界解。School of Management Harbin Institute of Technology 36單純形法原理單純形法原理檢驗主要看貢獻檢驗主要看貢獻系數比較成關鍵系數比較成關鍵目系減去基系權目系減去基系權收益不增方清閑收益不增方清閑另一非基無增減另一非基無增減只要可行無窮錢只要可行無窮錢就怕有個冒頭鳥就怕有個冒頭鳥處處作對解無邊處處作對解無邊School of Management Harbin Institute of Technology 37單純形法計

22、算步驟單純形法計算步驟 求出線性規劃的初始基可行解，列出初求出線性規劃的初始基可行解，列出初始單純形表始單純形表 進行最優性檢驗進行最優性檢驗 從一個基可行解轉換到另一個目標函數從一個基可行解轉換到另一個目標函數值更大的基可行解，列出新的單純形表值更大的基可行解，列出新的單純形表 重復第二、三步一直到計算終止重復第二、三步一直到計算終止School of Management Harbin Institute of Technology 38單純形法計算步驟單純形法計算步驟 確定換入基的變量確定換入基的變量 確定換出基的變量確定換出基的變量 用換入變量替換基變量中的換出變量用換入變量替換基變量

23、中的換出變量將主元素所在行數字除以主元素其它行變換檢驗數變換School of Management Harbin Institute of Technology 39單純形法計算步驟單純形法計算步驟School of Management Harbin Institute of Technology 40老虎里面打蒼蠅老虎里面打蒼蠅被抓全因臺不硬被抓全因臺不硬串通一窩全被免串通一窩全被免重新洗牌新聯姻重新洗牌新聯姻豎除橫乘負后加豎除橫乘負后加新主登基換新人新主登基換新人政權是否穩如山政權是否穩如山照鏡檢驗萬里行照鏡檢驗萬里行單純形法計算步驟單純形法計算步驟School of Manageme

24、nt Harbin Institute of Technology 41單純形法計算步驟單純形法計算步驟School of Management Harbin Institute of Technology 42 人工變量法人工變量法前面討論了在標準型中系數矩陣有單位矩陣，很容易確定一組初始基可行解。但實際問題中有一些模型并不含有單位矩陣，為得到一組基向量和初始基可行解，在約束條件的等式左端（標準化后的模型）加一組虛擬變量，從而得到一組基變量。這種人為加的變量稱為人工變量，對應的可行基稱為人工基，用大M法或兩階段法求解。School of Management Harbin Institute

25、 of Technology 43單純形法的進一步討論單純形法的進一步討論單純形法的進一步討論單純形法的進一步討論School of Management Harbin Institute of Technology 44單純形法的進一步討論單純形法的進一步討論School of Management Harbin Institute of Technology 45Cj-30100-M-MCB基bx1x2x3x4x5x6x70 x441111000-Mx61-21-10-110-Mx790310001cj-zj-2M-34M10-M000 x4330211-100 x21-21-10-110

26、-Mx7660403-31cj-zj6M-304M+103M-4M00 x400011-1/21/2-1/20 x23011/30001/3-3x11102/301/2-1/21/6cj-zj00303/2-M-3/2-M+1/20 x400001-1/21/2-1/20 x25/2-1/2100-1/41/41/41x33/23/20103/4-3/41/4cj-zj-9/2000-3/4-M+3/4-M-1/4 兩階段法兩階段法第一階段：求解一個目標函數中只包含人工變量的線性規劃問題。令目標函數中其他變量的系數取零，人工變量的系數取某個正的常數（一般取1），在保持原問題約束條件不變的情況下

27、求這個目標函數極小化時的解（目標函數為零）第二階段：當第一階段有可行解時，從第一階段的最終單純形表出發，去掉人工變量，并按原問題的目標函數繼續尋求最優解。School of Management Harbin Institute of Technology 46單純形法的進一步討論單純形法的進一步討論單純形法的進一步討論單純形法的進一步討論- -兩階段法兩階段法School of Management Harbin Institute of Technology 47單純形法的進一步討論單純形法的進一步討論- -兩階段法兩階段法School of Management Harbin Insti

28、tute of Technology 48Cj00000-1-1CB基bx1x2x3x4x5x6x70 x441111000-1x61-21-10-110-1x790310001cj-zj-2400-1000 x4330211-100 x21-21-10-110-1x7660403-31cj-zj60403-400 x400011-1/21/2-1/20 x23011/30001/3-3x11102/301/2-1/21/6cj-zj00000-1-1單純形法的進一步討論單純形法的進一步討論- -兩階段法兩階段法School of Management Harbin Institute of

29、Technology 49Cj-30100CB基bx1x2x3x4x50 x400011-1/20 x23011/300-3x11102/301/2cj-zj00303/20 x400001-1/20 x25/2-1/2100-1/41x33/23/20103/4cj-zj-9/2000-3/4單純形法的進一步討論單純形法的進一步討論School of Management Harbin Institute of Technology 50CB基基bx1x2x3x4x53x13101/20-1/50 x4400-214/53x2301001/500-3/200CB基基bx1x2x3x4x53x141001/400 x5500-5/25/413x22011/2-1/4000-3/