運(yùn)籌學(xué)——線性規(guī)劃-PPT課件

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

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

3、劃，才能使 總利潤(rùn)最大？ 例題1生產(chǎn)計(jì)劃問(wèn)題解：1.決策變量：設(shè)產(chǎn)品I、II的產(chǎn)量分 別為 x1、x22.目標(biāo)函數(shù)：設(shè)總運(yùn)費(fèi)為z，則有： max z = 2 x1 + 3 x23.約束條件： x1 + 2x2 8 4x1 16 4x2 12 x1， x203.1.1 LP的數(shù)學(xué)模型例題2 某廠生產(chǎn)三種藥物，這些藥物可以從四種不同的原料中提取。下表給出了單位原料可提取的藥物量（配方問(wèn)題）要求：生產(chǎn)A種藥物至少160單位；B種藥物恰好200單位，C種藥物不超過(guò)180單位，且使原料總成本最小。解：1.決策變量：設(shè)四種原料的使用 量分別為： x1、x2 、x3 、x42.目標(biāo)函數(shù)：設(shè)總成本為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：人員安排問(wèn)題醫(yī)院護(hù)士24小時(shí)值班，每次值班8小時(shí)。不同時(shí)段需要的護(hù)士人數(shù)不等。據(jù)統(tǒng)計(jì)： 序號(hào)時(shí)段最少人數(shù)安排人數(shù)1061060X12101470X23141860X34182250X45220220X56020630 x6例題3建模目標(biāo)函數(shù)：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非負(fù)性約束：xj 0,j=1,2,6例題4合理下料問(wèn)題料長(zhǎng)7.4米，截成2.9、2.1、1.5米各200根。如何截取余料最少？關(guān)鍵：設(shè)變量。 方案料型 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 合計(jì) 殘料 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建模設(shè)：xj為采用第 j

6、種方案的根數(shù)（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船只種類船只數(shù)拖 輪30A型駁船34B型駁船52航線號(hào)合同貨運(yùn)量12002400航線號(hào)船隊(duì)類型編隊(duì)形式貨運(yùn)成本（千元隊(duì)）貨運(yùn)量（千噸）拖輪A型駁船B型駁船1112362521436202322472404142720問(wèn)：

7、應(yīng)如何編隊(duì)，才能既完成合同任務(wù)，又使總貨運(yùn)成本為最小？例題5 某航運(yùn)局現(xiàn)有船只種類、數(shù)量以及計(jì)劃期內(nèi)各條航線的貨運(yùn)量、貨運(yùn)成本如下表所示：例題5建模設(shè)：xj為第 j 號(hào)類型船隊(duì)的隊(duì)數(shù)（j = 1，2，3，4），z 為總貨運(yùn)成本則： 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 最優(yōu)值：z =

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

9、稱為可行解。2 標(biāo)出目標(biāo)函數(shù)值增加的方向。3 若求最大（?。┲?，則令目標(biāo)函數(shù)等值線沿（逆）目標(biāo)函數(shù)值增加的方向 平行移動(dòng)，找與可行域最后相交的點(diǎn)，該點(diǎn)就是最優(yōu)解。圖解法解題步驟可行域(可行解全體)基本可行解(可行域頂點(diǎn)、極點(diǎn))基本解令非基變量 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解系數(shù)矩陣為：則：基變量為x3、x4，非基變量為x1、x23）X (1/2, 1/2

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

11、tion）： 滿足非負(fù)約束的基本解稱為基本可行解。若約束等式中有n個(gè)變量，m個(gè)約束，則基本解的個(gè)數(shù)基礎(chǔ)解、基礎(chǔ)可行解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 可行解與最優(yōu)解：最優(yōu)解一定是可行解，但可行解不一定是最優(yōu)解。線性規(guī)劃解之間的關(guān)系基本解不一定是可行解，可行解也不一定是基本解。2 可行解與基本解：3 可行解與基本可行解：基本可行解一定是可行解，但可行解不一定是基本解?；究尚薪庖欢ㄊ腔窘?，但基本解不一定是基本可行解。4 基本解與基本可行解：5 最優(yōu)解與基

12、本解：最優(yōu)解不一定是基本解，基本解也不一定是最優(yōu)解。問(wèn)題：最優(yōu)解與基本可行解？非可行解可行解基本可行解基本解幾何概念代數(shù)概念約束直線滿足一個(gè)等式約束的解約束半平面滿足一個(gè)不等式約束的解約束半平面的交集：凸多邊形滿足一組不等式約束的解約束直線的交點(diǎn)基礎(chǔ)解可行域的極點(diǎn)基礎(chǔ)可行解目標(biāo)函數(shù)等值線：一組平行線 目標(biāo)函數(shù)值等于一個(gè)常數(shù)的解線性規(guī)劃解的性質(zhì)定理1 線性規(guī)劃的可行域 R 是一個(gè)凸集，且有有限個(gè)頂點(diǎn)。定理2 X是線性規(guī)劃可行域 R 頂點(diǎn)的充要條件是 X 線性規(guī)劃的基本可行解。定理3 若線性規(guī)劃有最優(yōu)解，則必有基本最優(yōu)解。定理4 若線性規(guī)劃在可行域的兩個(gè)頂點(diǎn)上達(dá)到最優(yōu)，則在兩個(gè)頂點(diǎn)的連線 上也達(dá)到

13、最優(yōu)。線性規(guī)劃問(wèn)題的可行域是一個(gè)凸集。線性規(guī)劃的每一個(gè)基本可行解對(duì)應(yīng)凸集的每一個(gè)頂點(diǎn)。若線性規(guī)劃有最優(yōu)解，則一定在凸集的某個(gè)（些）頂點(diǎn)上達(dá)到最優(yōu)。若線性規(guī)劃在兩個(gè)頂點(diǎn)以上達(dá)到最優(yōu),則一定有無(wú)窮多個(gè)最優(yōu)解。最優(yōu)解一定是基本可行解，但基本可行解不一定是最優(yōu)解。解的形態(tài) (d)可行域無(wú)界 (e)可行域無(wú)界 (f)可行域?yàn)榭占?多個(gè)最優(yōu)解 目標(biāo)函數(shù)無(wú)界 無(wú)可行解 (a)可行域有界 (b)可行域有界 (c)可行域無(wú)界 唯一最優(yōu)解 多個(gè)最優(yōu)解 唯一最優(yōu)解結(jié)論可行域是個(gè)凸集可行域有有限個(gè)頂點(diǎn)最優(yōu)值在可行域的頂點(diǎn)上達(dá)到唯一最優(yōu)解的情形無(wú)窮多解的情形無(wú)界解情形無(wú)解情形線性規(guī)劃的一般模式1.決策變量： X = (

14、x1,x2,.,xn)T2.目標(biāo)函數(shù)：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線性規(guī)劃的標(biāo)準(zhǔn)形式1.決策變量： X = (x1,x2,.,xn)T2.目標(biāo)函數(shù)：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線性規(guī)劃的標(biāo)準(zhǔn)形式其中：求和形式矩陣形式?jīng)Q策變量常數(shù)項(xiàng)系數(shù)矩陣價(jià)值系數(shù)其中：標(biāo)準(zhǔn)型的特征目標(biāo)函數(shù)極大化約束條件為等式?jīng)Q策變量非負(fù)約束方程右側(cè)常數(shù)全部非負(fù)正規(guī)型的特征標(biāo)準(zhǔn)型每一個(gè)約束方程均有基變量非標(biāo)準(zhǔn)型轉(zhuǎn)化為正規(guī)型目標(biāo)函數(shù)極小化轉(zhuǎn)為極大化： minZ=max(Z) ，一個(gè)數(shù)的極小化等價(jià)于其相反數(shù)的極大化。不等式約束的轉(zhuǎn)化： aijxjbi 加入松弛變量 aijxjbi 減去剩余變量非正變量：即xk 0 則令xk = xk 自由變量：即xk無(wú)約束，令xk= xkx”k非標(biāo)準(zhǔn)型轉(zhuǎn)化舉例之

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非標(biāo)準(zhǔn)型轉(zhuǎn)化舉例之二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無(wú)約束 x1 0

17、x2 0 x3 0 x”3 0 x40 x50 正規(guī)化1. 目測(cè)：松馳變量2. 構(gòu)造：人工變量（舉例）大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求解一般線性規(guī)劃問(wèn)題策略尋找初始基本可行解給出基本可行解為最優(yōu)解的判別準(zhǔn)則給出從目前基本可行解轉(zhuǎn)移到新基本 可行解的方法求解流程 確定初始

18、基本可行解最優(yōu)解？否轉(zhuǎn)移到新的基本可行解給出最優(yōu)解是3.3 單純形表上作業(yè)法單純形表的格式： 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點(diǎn)C點(diǎn)B點(diǎn)基礎(chǔ)解、基礎(chǔ)可行解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步驟用正規(guī)型表示問(wèn)題，確定初始基可行解填入初始單純形表求相對(duì)利潤(rùn)系數(shù)。如果全部非正，則停止選擇旋入變量用最小比值法確定旋出變量旋轉(zhuǎn)運(yùn)算計(jì)算

20、表格數(shù)據(jù)和相對(duì)利潤(rùn)系數(shù)。返回第三步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ìn)一步探討極小化問(wèn)題直接求解：檢驗(yàn)數(shù)的判別由所有j 0 即為最優(yōu)，變?yōu)樗衘 0則為最優(yōu)。無(wú)窮多最優(yōu)解情形：非基變量檢驗(yàn)數(shù) j= 0 (在最終單純形表中)退化解的情形：有兩個(gè)以上 值相等無(wú)界解無(wú)

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無(wú)窮多個(gè)最優(yōu)解 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無(wú)界解 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