1、 線性規劃3.1 LP的基本概念3.2線性規劃問題的圖解法3.3 單純形表上作業法3.4 大M法和兩階段法3.5單純形法的進一步探討3.6 計算機求解3.7 習題課第3章 線性規劃線性規劃的發展1939年，前蘇聯數學家康托洛維奇用線性模型研究提高組織和生產效率問題 1947年，Dantzig提出求解線性規劃的單純形法 1950-1956年，主要研究線性規劃的對偶理論 1958年，發表整數規劃的割平面法1960年，Dantzig和Wolfe研究成功分解算法，奠定了大規模線性規劃問題理論和算法的基礎。1979年，Khachiyan，1984年，Karmarkaa研究成功線性規劃的多項式算法。 3.

2、1 LP(linear programming)的基本概念LP是在有限資源的條件下，合理分配和利用資源，以期取得最佳的經濟效益的優化方法。LP有一組有待決策的變量， 一個線性的目標函數， 一組線性的約束條件。線性規劃研究的主要問題一類是已有一定數量的資源（人力、物質、時間等），研究如何充分合理地使用它們，才能使完成的任務量為最大。另一類是當一項任務確定以后，研究如何統籌安排，才能使完成任務所耗費的資源量為最少。 實際上，上述兩類問題是一個問題的兩個不同的方面，都是求問題的最優解（ max 或 min ）。例1.1 某廠生產兩種產品，下表給出了單位產品所需資源及單位產品利潤 問：應如何安排生產計

3、劃，才能使 總利潤最大？ 例題1生產計劃問題解：1.決策變量：設產品I、II的產量分 別為 x1、x22.目標函數：設總運費為z，則有： max z = 2 x1 + 3 x23.約束條件： x1 + 2x2 8 4x1 16 4x2 12 x1， x203.1.1 LP的數學模型例題2 某廠生產三種藥物，這些藥物可以從四種不同的原料中提取。下表給出了單位原料可提取的藥物量（配方問題）要求：生產A種藥物至少160單位；B種藥物恰好200單位，C種藥物不超過180單位，且使原料總成本最小。解：1.決策變量：設四種原料的使用 量分別為： x1、x2 、x3 、x42.目標函數：設總成本為z，則有：

4、 min z = 5 x1 + 6 x2 + 7 x3 + 8 x43.約束條件： x1 + 2x2 + x3 + x4 160 2x1 +4 x3 +2 x4 200 3x1 x2 +x3 +2 x4 180 x1、x2 、x3 、x40 藥物原料ABC單位成本（元噸）甲1235乙2016丙1417丁1228例題3：人員安排問題醫院護士24小時值班，每次值班8小時。不同時段需要的護士人數不等。據統計： 序號時段最少人數安排人數1061060X12101470X23141860X34182250X45220220X56020630 x6例題3建模目標函數：min Z=x1+x2+x3+x4+x

5、5+x6約束條件： x1+x2 70 x2+x3 60 x3+x4 50 x4+x5 20 x5+x6 30 x6+x1 60非負性約束：xj 0,j=1,2,6例題4合理下料問題料長7.4米，截成2.9、2.1、1.5米各200根。如何截取余料最少？關鍵：設變量。 方案料型 1 2 3 4 5 6 7 8 2.9米 2.1米 1.5米 1 2 0 1 0 1 0 0 0 0 2 2 1 1 3 0 3 1 2 0 3 1 0 4 合計 殘料 7.4 7.3 7.2 7.1 6.6 6.5 6.3 6.0 0 0.1 0.2 0.3 0.8 0.9 1.1 1.4例題4建模設：xj為采用第 j

6、種方案的根數（j = 1，2，8），z 為總殘料量則： min z = 0.1x2 + 0.2x3 + 0.3x4 + 0.8x5 + 0.9x6 + 1.1x7 +1.4x8 x1 +2 x2 + x4 + x6 2002x3 +2 x4 + x5 + x6 + 3x7 2003x1 + x2 + 2x3 +3 x5 + x6 +4 x8 200 xj 0 j = 1,2,8船只種類船只數拖 輪30A型駁船34B型駁船52航線號合同貨運量12002400航線號船隊類型編隊形式貨運成本（千元隊）貨運量（千噸）拖輪A型駁船B型駁船1112362521436202322472404142720問：

7、應如何編隊，才能既完成合同任務，又使總貨運成本為最小？例題5 某航運局現有船只種類、數量以及計劃期內各條航線的貨運量、貨運成本如下表所示：例題5建模設：xj為第 j 號類型船隊的隊數（j = 1，2，3，4），z 為總貨運成本則： min z = 36x1 + 36x2 + 72x3 + 27x4 x1 + x2 + 2x3 + x4 302x1 + 2x3 34 4x2 + 4x3 + 4x4 5225x1 + 20 x2 200 40 x3 + 20 x4 400 xj 0 j = 1,2,3,4用單純形法可求得： x1 = 8，x2 = 0 ，x3 = 7， x4 = 6 最優值：z =

8、 954即：四種船隊類型的隊數分別是 8、0、7、6，此時可使總貨運成本為最小，為954千元。線性規劃模型特點1 都用一組決策變量X = (x1,x2,xn)T表示某一方案； 滿足以上三個條件的數學模型稱為線性規劃2 都有一個要達到的目標，并且目標要求可以表示成決策變量的線性函數；3 都有一組約束條件，這些約束條件可以用決策變量的線性等式或線性不等 式來表示。3.2線性規劃問題的名詞和圖解法maxz=x1+3x2s.t.x1+x26-x1+2x28x1,x204 將最優解代入目標函數，求出最優值。1 在直角平面坐標系中畫出所有的約束等式，并找出所有約束條件的公共部 分，稱為可行域，可行域中的點

9、稱為可行解。2 標出目標函數值增加的方向。3 若求最大（小）值，則令目標函數等值線沿（逆）目標函數值增加的方向 平行移動，找與可行域最后相交的點，該點就是最優解。圖解法解題步驟可行域(可行解全體)基本可行解(可行域頂點、極點)基本解令非基變量 x10，x2 0則得：X (0, 0, 3, 1 )T基本解則：基變量為x2、x3，非基變量為x1、x4令非基變量 x10，x4 0則得：X (0, 1, 5, 0 )T基本解不是基本可行解基本可行解例 討論下述約束方程的解 x1 2x2 x3 3 2x1 x2 x4 1解系數矩陣為：則：基變量為x3、x4，非基變量為x1、x23）X (1/2, 1/2

10、, 3/2, 1/2)T不是基本解可行解不是基本可行解3.2.2 線性規劃的基本名詞1 可行解（ feasible solution ）：滿足線性規劃約束條件的解稱為可行解。2可行域：可行解的集合3 最優解（optimal solution）：使線性規劃目標函數達到最優的可行解。4 基本解（basic solution）：以線性規劃約束等式的系數矩陣A中任意m行m 列組成的mm滿秩子矩陣為基矩陣，與基矩陣相對應的變量稱為基變量（basic variable），其余變量稱為非基變量，令非基變量為零，可求得基變 量的值，這樣求出的解稱為基本解。 5基本可行解（basic feasible solu

11、tion）： 滿足非負約束的基本解稱為基本可行解。若約束等式中有n個變量，m個約束，則基本解的個數基礎解、基礎可行解max z=x1+3x2Ds.t. x1+ x2+x3=6 B-x1+2x2 +x4=8 x4=0 C x3=0 x1, x2,x3,x40 x1=0 E O x2=0 A1 可行解與最優解：最優解一定是可行解，但可行解不一定是最優解。線性規劃解之間的關系基本解不一定是可行解，可行解也不一定是基本解。2 可行解與基本解：3 可行解與基本可行解：基本可行解一定是可行解，但可行解不一定是基本解。基本可行解一定是基本解，但基本解不一定是基本可行解。4 基本解與基本可行解：5 最優解與基

12、本解：最優解不一定是基本解，基本解也不一定是最優解。問題：最優解與基本可行解？非可行解可行解基本可行解基本解幾何概念代數概念約束直線滿足一個等式約束的解約束半平面滿足一個不等式約束的解約束半平面的交集：凸多邊形滿足一組不等式約束的解約束直線的交點基礎解可行域的極點基礎可行解目標函數等值線：一組平行線 目標函數值等于一個常數的解線性規劃解的性質定理1 線性規劃的可行域 R 是一個凸集，且有有限個頂點。定理2 X是線性規劃可行域 R 頂點的充要條件是 X 線性規劃的基本可行解。定理3 若線性規劃有最優解，則必有基本最優解。定理4 若線性規劃在可行域的兩個頂點上達到最優，則在兩個頂點的連線 上也達到

13、最優。線性規劃問題的可行域是一個凸集。線性規劃的每一個基本可行解對應凸集的每一個頂點。若線性規劃有最優解，則一定在凸集的某個（些）頂點上達到最優。若線性規劃在兩個頂點以上達到最優,則一定有無窮多個最優解。最優解一定是基本可行解，但基本可行解不一定是最優解。解的形態 (d)可行域無界 (e)可行域無界 (f)可行域為空集 多個最優解 目標函數無界 無可行解 (a)可行域有界 (b)可行域有界 (c)可行域無界 唯一最優解 多個最優解 唯一最優解結論可行域是個凸集可行域有有限個頂點最優值在可行域的頂點上達到唯一最優解的情形無窮多解的情形無界解情形無解情形線性規劃的一般模式1.決策變量： X = (

14、x1,x2,.,xn)T2.目標函數：max(min ) z = c1 x1 + c2 x2 + . + cnxn3.約束條件： a11x1 + a12 x2 +.+ a1n xn (=) b1 a21x1 + a22 x2 +.+ a2n xn (=) b2 am1x1 + am2 x2 +.+ amn xn (=) bm x1,x2,xn0線性規劃的標準形式1.決策變量： X = (x1,x2,.,xn)T2.目標函數：max z = c1 x1 + c2 x2 + . + cnxn3.約束條件： a11x1 + a12 x2 +.+ a1n xn = b1 a21x1 + a22 x2

15、+.+ a2n xn = b2 am1x1 + am2 x2 +.+ amn xn = bm x1,x2,xn0線性規劃的標準形式其中：求和形式矩陣形式決策變量常數項系數矩陣價值系數其中：標準型的特征目標函數極大化約束條件為等式決策變量非負約束方程右側常數全部非負正規型的特征標準型每一個約束方程均有基變量非標準型轉化為正規型目標函數極小化轉為極大化： minZ=max(Z) ，一個數的極小化等價于其相反數的極大化。不等式約束的轉化： aijxjbi 加入松弛變量 aijxjbi 減去剩余變量非正變量：即xk 0 則令xk = xk 自由變量：即xk無約束，令xk= xkx”k非標準型轉化舉例之

16、一maxZ=70X1+120X2 maxZ=70X1+120X2 9X1+4X2360 9X1+4X2+X3=360 4X1+5X2 200 4X1+5X2 +x4=200 3X1+10X2 300 3X1+10X2+x5 =300 X10 X20 Xj0 j=1,2,5非標準型轉化舉例之二minZ=x1+2x2-3x3 maxZ=x12x2+3(x3x”3) x1+x2+x3 9 x1+x2+x3 x”3 + x4=9 -x1-2x2+x3 2 x12x2+x3 x”3 - x5= 2 3x1+x2-3x3=5 3x1+x23(x3 x”3 )=5 x1 0 x2 0 x3無約束 x1 0

17、x2 0 x3 0 x”3 0 x40 x50 正規化1. 目測：松馳變量2. 構造：人工變量（舉例）大M法例解Min Z=-3X1+X2+X3 Max Z= 3X1-X2-X3 MX6-MX7 s.t. X1-2X2 +X3 11 s.t. X1-2X2 +X3 +X4 =11 -4X1+X2 +2X3 3 -4X1+X2 +2X3 -X5 +X6 = 3 2X1-X3 =-1 -2X1+X3 +X7 =1 X10,X20,X30 Xj 0 j=1,2,7求解一般線性規劃問題策略尋找初始基本可行解給出基本可行解為最優解的判別準則給出從目前基本可行解轉移到新基本 可行解的方法求解流程 確定初始

18、基本可行解最優解？否轉移到新的基本可行解給出最優解是3.3 單純形表上作業法單純形表的格式： CjC1 C2 Cn i CBXBbx1 x2 . xn C1 C2 Cmx1x2xmb1b2bma11 a12 a1na21 a22 a2n am1 am2 amn 1 2 m -z * 1 2 n 例解：（表圖）max z=x1+3x2Ds.t. x1+ x2+x3=6 B-x1+2x2 +x4=8 x4=0 C x3=0 x1, x2,x3,x40 x1=0 E O x2=0 A Cj1 3 0 0CBXBbX1 X2 X3 X4j 0 0 X3X468 1 1 1 0 -1 2 0 1 6/1

19、8/2-z0 1 3 0 0 0 3X3X224 3/2 0 1 -1/2 -1/2 1 0 1/24/3-z-12 5/2 0 0 -3/213X1X24/314/3 1 0 2/3 -1/3 0 1 1/3 1/3-z-46/3 0 0 -5/3 -2/3O點C點B點基礎解、基礎可行解max z=x1+3x2Ds.t. x1+ x2+x3=6 B-x1+2x2 +x4=8 x4=0 C x3=0 x1, x2,x3,x40 x1=0 E O x2=0 A步驟用正規型表示問題，確定初始基可行解填入初始單純形表求相對利潤系數。如果全部非正，則停止選擇旋入變量用最小比值法確定旋出變量旋轉運算計算

20、表格數據和相對利潤系數。返回第三步3.4 大M法和兩階段法例解Min Z=-3X1+X2+X3 Max Z= 3X1-X2-X3 MX6-MX7 s.t. X1-2X2 +X3 11 s.t. X1-2X2 +X3 +X4 =11 -4X1+X2 +2X3 3 -4X1+X2 +2X3 -X5 +X6 = 3 2X1-X3 =-1 -2X1+X3 +X7 =1 X10,X20,X30 Xj 0 j=1,2,7 Cj3 -1 -1 0 0 -M -MCBXBbX1 X2 X3 X4 X5 X6 X7j 0 -M -MX4X6X71131 1 -2 1 1 0 0 0-4 1 2 0 -1 1 0

21、 -2 0 1 0 0 0 1-z0 3 -1 -1 0 0 -M -M 0 -M -MX4X6X7113 1 1 -2 1 1 0 0 0 -4 1 2 0 -1 1 0 -2 0 1 0 0 0 1113/21-z4M3-6M M-1 3M-1 0 -M 0 00-M-1X4X6X31011 3 -2 0 1 0 0 -1 0 1 0 0 -1 1 -2 -2 0 1 0 0 0 1-1-zM+1 1 M-1 0 0 -M 0 3M初始單純形表大M法 Cj3 -1 -1 0 0 -M -MCBXBbX1 X2 X3 X4 X5 X6 X7j 0 0 0X4X2X312113 0 0 1 -

22、2 2 -50 1 0 0 -1 1 -2 -2 0 1 0 0 0 14-z2 1 0 0 0 -1 1-M -1-M -3 1 1X1X2X341 91 0 0 1/3 -2/3 2/3 -5/30 1 0 0 -1 1 -2 0 0 1 2/3 -4/3 4/3 -7/3-z-20 0 0 -1/3 -1/3 1/3-M 2/3-M 大M法 Cj0 0 0 0 0 -1 -1CBXBbX1 X2 X3 X4 X5 X6 X7j 0 -1 -1X4X6X71131 1 -2 1 1 0 0 0-4 1 2 0 -1 1 0 -2 0 1 0 0 0 1-W0 0 0 0 0 0 -1 -1

23、 0 -1 -1X4X6X7113 1 1 -2 1 1 0 0 0 -4 1 2 0 -1 1 0 -2 0 1 0 0 0 1113/21-W4-6 1 3 0 -1 0 00-10X4X6X31011 3 -2 0 1 0 0 -1 0 1 0 0 -1 1 -2 -2 0 1 0 0 0 0-1-W1 0 1 0 0 -1 0 3初始單純形表兩階段法第一階段 Cj0 0 0 0 0 -M -MCBXBbX1 X2 X3 X4 X5 X6 X7j 0 0 0X4X2X312113 0 0 1 -2 2 -50 1 0 0 -1 1 -2 -2 0 1 0 0 0 1-W0 0 0 0 0

24、 0 -1 -1兩階段法第一階段 Cj3 -1 -1 0 0CBXBbX1 X2 X3 X4 X5j 0 -1 -1X4X2X312113 0 0 1 -20 1 0 0 -1-2 0 1 0 04-z21 0 0 0 -1 3 -1 -1X1X2X341 91 0 0 1/3 -2/30 1 0 0 -10 0 1 2/3 -4/3-z-20 0 0 -1/3 -1/3兩階段法第二階段3.5單純形法的進一步探討極小化問題直接求解：檢驗數的判別由所有j 0 即為最優，變為所有j 0則為最優。無窮多最優解情形：非基變量檢驗數 j= 0 (在最終單純形表中)退化解的情形：有兩個以上 值相等無界解無

25、解 Cj3 2 0 0 0CBXBbX1 X2 X3 X4 X5j 0 0 3X3X4X1753 0 1 1 0 1 0 5 0 1 3 1 1 0 0 171-z-9 0 5 0 0 3 0 2 3X3X2X161 4 0 0 1 1/5 8/5 0 1 0 1/5 -3/5 1 0 0 1/5 2/515/4-10-z-14 0 0 0 -1 0023X5X2X115/413/45/2 0 0 5/8 -1/8 1 0 1 3/8 1/8 0 1 0 -1/4 1/4 0 626/3-z-14 0 0 0 -1 0無窮多個最優解 Cj0 0 0 2 0 1.5CBXBbX1 X2 X3 X

26、4 X5 X6j 0 0 0X1X2X3243 1 0 0 1 -1 0 0 1 0 2 0 1 0 0 1 1 1 1 223-z0 0 0 0 2 0 1.5 2 0 0X4X2X320 1 1 0 0 1 -1 0 -2 1 0 0 2 1 -1 0 1 0 2 1 -01.5-z-4 -2 0 0 0 2 1.5200X4X5X2201 0 0.5 0 1 0 0.5 -1 0.5 0 0 1 0.5 0 -1 1 0 0 040-z-4 0 -1 0 0 0 0.5退化解 Cj2 3 0 0CBXBbX1 X2 X3 X4j 0 0 X3X424 1 1 1 0 -3 1 0 1-4-z0 2 3 0 0 0 3X3X264 -2 0 1 1 -3 1 0 1-z-12 11 0 0 -3無界解 Cj2 1 0 0 -MCBXBbX1 X2 X3 X4 X5j 0 -M X3X526 1 1 1 0 0 2 2 0 -1 1 23-z6M 2+2M 1+2M 0 -M 0 2 -MX1X522 1 1 1