1、第二章 線性規劃與單純形法2.1 線性規劃的基本概念2.2 單純形法2.3 單純形法的進一步探討2.4 使用計算機軟件求解線性規劃2.5 應用舉例2.6 案例2.1 線性規劃的基本概念2.1.1 線性規劃的數學模型2.1.2 線性規劃的圖解法2.1.3 線性規劃的標準型2.1.4 基可行解2.1.1 線性規劃的數學模型例 1（生產計劃問題） 某工廠在計劃期內要安排生產 A、B 兩種產品（假定產品暢銷） 。已知生產單位產品的利潤與所需的勞動力、 設備臺時及原材料的消耗， 如表2-1 所示。問應如何安排生產使該廠獲利最大？ 產品 A 產品 B 資源限額 勞動力 9 4 360 工時 設備 4 5

2、200 臺時 原材料 3 10 300 公斤 單位產品利潤（元） 70 120 例 2（營養問題） 某公司飼養實驗用的動物以供出售。已經知道這些動物的生長對飼料中的三種營養元素特別敏感，我們分別稱它們為營養元素 A、B、C。已求出這些動物每天至少需要 700 克營養元素 A，30 克營養元素 B，而營養元素 C 的每天需要量剛好是 200 毫克，不夠和過量都是有害的。現有五種飼料可供選用，各種飼料每千克所含的營養元素及單價如表 2-2 所示。為了避免過多使用某種飼料，規定混合飼料中各種飼料的最高含量分別為 50、60、50、70、40 千克。要求確定滿足動物需要而費用最低的飼料配方。 飼料 營

3、養元素 A（克） 營養元素 B（克） 營養元素 C（毫克） 價格（元/千克） 1 3 1 0.5 2 2 2 0.5 1 7 3 1 0.2 0.2 4 4 6 2 2 9 5 18 0.5 0.8 5 解： 設5 , 1jxj為每天混合飼料內包含的第 j 種飼料的千克數，則營養問題的模型為： 5 , 1, 040,70,50,60,502008 . 022 . 05 . 0305 . 022 . 05 . 070018623. .59472min5432154321543215432154321jxxxxxxxxxxxxxxxxxxxxxtsxxxxxzj 例 3（人員安排問題） 某醫院根據

4、日常工作統計，每晝夜 24 小時中至少需要下列數量的護士。 序號 時段 護士的最少人數 1 6:00-10:00 60 2 10:00-14:00 70 3 14:00-18:00 60 4 18:00-22:00 50 5 22:00-2:00 20 6 2:00-6:00 30 護士們分別在各時段開始時上班，并連續工作 8 小時，問應如何安排各個時段開始上班工作的人數， 才能使護士的總人數最少？ 解：設第 j 時段開始上班的人數為6 , 1,jxj，則 6 , 10603020506070. .min166554433221654321jxxxxxxxxxxxxxtsxxxxxxzj且為整

5、數， 線性規劃問題隱含的假設 （1）比例性假設（2）可加性假設（3）可分性假設（4）確定性假設2.1.2 線性規劃的圖解法線性規劃問題解的情況（1）唯一最優解（2）無窮多最優解（3）無界解（4）無可行解（1）唯一最優解（例 1） 0,3001032005436049. .12070max2121212121xxxxxxxxtsxxz 30010321xx2005421 xx3604921 xx40(0,30)90100(40,0) (50,0)0B(20,24)C(1000/29,360/29)DAE1x2x 在 B 點獲得最大值，z=4280 （2）無窮多最優解 0,300103200543

6、6049. .5 .8270max2121212121xxxxxxxxtsxxz 30010321xx2005421 xx3604921 xx40(0,30)90100(40,0) (50,0)0B(20,24)C(1000/29,360/29)DAE1x2x 在線段 BC 上任意一點都使 z 取得相同的最大值 （3）無界解 0,6232. .max21212121xxxxxxtsxxz 62321 xx221xx1x2x02134-1-2123 （4）無可行解 0,603001032005436049. .12070max212121212121xxxxxxxxxxtsxxz 3001032

7、1xx2005421 xx3604921 xx40(0,30)90100(40,0) (50,0)0B(20,24)C(1000/29,360/29)DAE1x2x6021 xx 二維線性規劃的兩個幾何特征（1）若可行域非空，它是一個凸集。（2）若線性規劃存在最優解，它一定可在可行域的某個頂點（極點）得到。凸集問題2.1.3線性規劃的標準型（SLP）0,. .max21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz 其中右端項0ib。 SLP的簡寫引入TnxxxX,21，ncccC,21，Tnbbbb

8、,21， nmijaA（mn 階矩陣） ，TnjjjaaaP,21（矩陣 A 的第 j 列） 則 SLP 的矩陣描述： 0. .maxXbAXtsCXz SLP 的向量描述： njxbxPtsCXzjnjjj, 2 , 1, 0. .max1 一般稱 C 為價值向量，b 為資源向量，A 為技術系數矩陣。 轉化成標準型的方法 1最小化問題的轉化（改變目標函數的符號） 。 2不等式約束的處理 （1）對小于等于約束加上松弛變量化為等式。 （2）對大于等于約束減去剩余變量化為等式。 3非正變量與符號無限制變量的處理。 （1）若0kx，令kkxx （2）若kx為符號無限制變量，則kkkxxx ，其中0,

9、 kkxx。 例 1 0,3001032005436049. .12070max2121212121xxxxxxxxtsxxz 補充練習 1 符號無限制423143132143214321, 0, 0,x12285327. . 32 maxxxxxxx-xxxxxxxtsxxxxz 補充練習 1 符號無限制423143132143214321, 0, 0,x12285327. . 32 maxxxxxxx-xxxxxxxtsxxxxz 解：令44422,xxxxx 化為標準形式為： 0, 122285327 . . 0032 max6544321644313215443216544321 xx

10、xxxxxxxxxxxxxxxxxxxtsxxxxxxxz 解：令122 xx，333xxx ，則標準形式為 0,6133126312s.t.21max 76543321726153321433213321 xxxxxxxxxxxxxxxxxxxxxxxxxxz 化簡后得 0,73424332s.t.122 max76543321726153321433213321 xxxxxxxxxxxxxxxxxxxxxxxxxxz 2.1.4 基可行解基可行解基可行解定義結論（1）SLP的基可行解對應于其可行域的頂點（極點）。（2）若SLP有最優解，則必有最優基可行解。2.2 單純形法2.2.1 最優性

11、的檢驗2.2.2 無界解與基變換2.2.3 單純形法計算步驟2.2.1最優性的檢驗最優解判別準則2.2.2 無界解與基變換變換方程組的具體做法 2.2.3 單純形法計算步驟計算步驟（一）計算步驟（二）例 1 0, 3001032005436049. .12070max5152142132121xxxxxxxxxxxtsxxz jc 70 120 0 0 0 BC BX b 1x 2x 3x 4x 5x i 0 3x 240 7.8 0 1 0 -0.4 30.76 0 4x 50 2.5 0 0 1 -0.5 20 120 2x 30 0.3 1 0 0 0.1 100 3600 34 0 0

12、 0 -12 用 2/5（4x行） ， （-3/25）（4x行）（3x行） ， （-78/25）（4x行）（2x行） ，得到下一個表 練習： 5 , 1 , 0 41551602030. .25max5142132121jxxxxxxxxxtsxxzj jc 5 2 0 0 0 BC BX b 1x 2x 3x 4x 5x i 0 3x 70 0 14 1 -6 0 5 5 1x 3 1 1/5 0 1/5 0 15 0 5x 1 0 -1/5 0 -1/5 1 / 15 0 1 0 -1 0 用 1/14（3x行） ， （-1/70）（3x行）（1x行） ， （1/70）（3x行）（5x行）

13、 ，得到下一個表 jc 5 2 0 0 0 BC BX b 1x 2x 3x 4x 5x i 2 2x 5 0 1 1/14 -3/7 0 5 1x 2 1 0 -1/70 2/7 0 0 5x 2 0 0 1/70 -2/7 1 20 0 0 -1/14 -4/7 0 最優解為：TX2 , 0 , 0 , 5 , 2*，最優值為：z=20 2.3單純形法的進一步探討2.3.1人工變量法2.3.2 無窮多最優解的情形2.3.1人工變量法1. 大M法2. 兩階段法1. 大M法例 9 0, 12324142. .3min32131321321321xxxxxxxxxxxtsxxxz 解：標準化后有

14、： 0, 12324142. .3max543213153214321321xxxxxxxxxxxxxxxtsxxxz 引入人工變量6x、7x有： 7 , 1, 0 12324142. .3max73165321432176321jxxxxxxxxxxxxxtsMxMxxxxzj jc 3 -1 -1 0 0 -M -M BC BX b 1x 2x 3x 4x 5x 6x 7x i 0 4x 14 1 -2 1 1 0 0 0 14 -M 6x 3 -4 1 2 0 -1 1 0 1.5 -M 7x 1 -2 0 1 0 0 0 1 1 0 3-6M -1+M -1+3M 0 -M 0 0 7

15、x行不變， （4x行）-（7x行） ， （-2）（7x行）（6x行） jc 3 -1 -1 0 0 -M -M BC BX b 1x 2x 3x 4x 5x 6x 7x i 0 4x 13 3 -2 0 1 0 0 -1 / -M 6x 1 0 1 0 0 -1 1 -2 1 -1 3x 1 -2 0 1 0 0 0 1 / 1 -1+M 0 0 -M 0 -3M+1 6x行不變，3x行不變，2（6x行）（4x行）得到下一個表 jc 3 -1 -1 0 0 -M -M BC BX b 1x 2x 3x 4x 5x 6x 7x i 0 4x 15 3 0 0 1 -2 2 -5 5 -1 2x

16、1 0 1 0 0 -1 1 -2 / -1 3x 1 -2 0 1 0 0 0 1 / 1 0 0 0 -1 -M+1 -M-1 1/34x行，2x行不變，2/3（4x行）（3x行）得到下一個表 jc 3 -1 -1 0 0 -M -M BC BX b 1x 2x 3x 4x 5x 6x 7x i 3 1x 5 1 0 0 1/3 -2/3 2/3 -5/3 -1 2x 1 0 1 0 0 -1 1 -2 -1 3x 11 0 0 1 2/3 -4/3 4/3 -7/3 3 0 0 0 -1/3 -1/3 -M+1/3 -M+2/3 最優解為：TX0 , 0 ,11, 1 , 5*，最優值為

17、：z=3 2. 兩階段法第一階段：求出原問題的初始基可行解。構造一個輔助線性規劃，其目標函數是人工變量之和并要求實施最小化（由于人工變量非負，故等價于要求所有人工變量取零值） ，而約束方程組是已加入人工變量的典式。用單純形法求解該輔助問題，若得到0min，標明所有人工變量都已取零值，第一階段的最優解便是原問題的一個基可行解，可以進行第二階段的計算。若0min，則原問題無可行解，應停止計算。 第二階段：將第一階段的最終表，刪去人工變量，并將目標函數行的系數，換成原問題的目標函數系數，這就得到了第二階段的初始單純形表。 例 10 0, 12324142. .3min32131321321321xx

18、xxxxxxxxxtsxxxz 解：標準化后有： 0, 12324142. .3max543213153214321321xxxxxxxxxxxxxxxtsxxxz 第一階段的輔助問題為： 7 , 1, 0 12324142. .max73165321432176jxxxxxxxxxxxxxtsxxj jc 0 0 0 0 0 -1 -1 BC BX b 1x 2x 3x 4x 5x 6x 7x i 0 4x 14 1 -2 1 1 0 0 0 14 -1 6x 3 -4 1 2 0 -1 1 0 1.5 -1 7x 1 -2 0 1 0 0 0 1 1 -6 1 3 0 -1 0 0 7x行

19、不變，用（4x行）-（7x行） ， （-2）（7x行）（6x行）得到下一個表 jc 0 0 0 0 0 -1 -1 BC BX b 1x 2x 3x 4x 5x 6x 7x i 0 4x 13 3 -2 0 1 0 0 -1 / -1 6x 1 0 1 0 0 -1 1 -2 1 0 3x 1 -2 0 1 0 0 0 1 / 0 1 0 0 -1 0 -3 6x行不變，3x行不變，用 2（6x行）（4x行）得到下一個表 jc 0 0 0 0 0 -1 -1 BC BX b 1x 2x 3x 4x 5x 6x 7x i 0 4x 15 3 0 0 1 -2 2 -5 0 2x 1 0 1 0

20、0 -1 1 -2 0 3x 1 -2 0 1 0 0 0 1 0 0 0 0 0 0 -1 -1 最優解：TX0 , 0 , 0 ,15, 1 , 1 , 0*，最優值：0。去掉人工變量6x、7x，換回原問題的目標函數得到下一個表 jc 3 -1 -1 0 0 BC BX b 1x 2x 3x 4x 5x i 3 1x 5 1 0 0 1/3 -2/3 -1 2x 1 0 1 0 0 -1 -1 3x 11 0 0 1 2/3 -4/3 3 0 0 0 -1/3 -1/3 最優解：TX0 , 0 ,11, 1 , 5*，最優值：z=-3 補充作業題用大 M 法和兩階段法求解下面 LP 問題：

21、 0, 3232s.t.42min21212121xxxxxxxxz 2.3.2 無窮多最優解的情形 當存在某非基變量kx的檢驗數0k，這時，并不能肯定線性規劃一定有多個最優解，而要作進一步運算。令kx入基，用規則（最小比值規則）確定出基變量。若0，則旋轉變換后可得到新最優基可行解，因此，問題有多個最優解；若0，則進行旋轉變換后，最優基可行解不變。 例 11 某 LP 問 題 的 最 優 單 純 形 表 如 下 所 示 ， 最 優 基 可 行 解 為TX4 , 0 , 0 , 2 , 4*，最優值為24*z jc 3 6 0 0 0 BC BX b 1x 2x 3x 4x 5x i 3 1x 4 1 0 0 1/4 0 16 0 5x 4 0 0 -2 1/2 1 8 6 2x 2 0 1 1/2 -1/8 0 / 24 0 0 -3 0 0 非基變量的檢驗數為零，令4x入基，5x出基，旋轉變換有下表 jc 3 6 0 0 0 BC BX b 1x 2x 3x 4x 5x i 3 1x 2 1 0 1 0 -1/2 0 4x 8 0 0 -4 1 2 6 2x 3 0 1 0 0 1/4 24 0 0 -3 0 0 最優基可行解為TX0 , 8 , 0 , 3 , 2*，最優值為24*z。最優基可行解變化，目標函數最優值不變。因為兩個最優基可行解的凸組合仍是