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

1、 線性規(guī)劃n3.1 lp的基本概念n3.2線性規(guī)劃問題的圖解法n3.3 單純形表上作業(yè)法n3.4 大m法和兩階段法n3.5單純形法的進(jìn)一步探討n3.6 計(jì)算機(jī)求解n3.7 習(xí)題課第3章 線性規(guī)劃n線性規(guī)劃的發(fā)展線性規(guī)劃的發(fā)展n1939年，前蘇聯(lián)數(shù)學(xué)家康托洛維奇用線性模型研究提高組織和生產(chǎn)效率問題 1947年，dantzig提出求解線性規(guī)劃的單純形法 1950-1956年，主要研究線性規(guī)劃的對偶理論 1958年，發(fā)表整數(shù)規(guī)劃的割平面法n1960年，dantzig和wolfe研究成功分解算法，奠定了大規(guī)模線性規(guī)劃問題理論和算法的基礎(chǔ)。n1979年，khachiyan，1984年，karmarkaa

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

3、，下表給出了單位產(chǎn)品所需資源及單位產(chǎn)品利潤 問：應(yīng)如何安排生產(chǎn)計(jì)劃，才能使 總利潤最大？ 例題1生產(chǎn)計(jì)劃問題解：解：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)三種藥物，這些藥物可以從四種不同的原料中提取。下表給出了單位原料可提取的藥物量（配方問題）要求：生產(chǎn)a種藥物至少160單位；b種藥物恰好200單位，c種藥物不超過180單位，且使原料總成本最小。解：解：1.決策變量：設(shè)四種原料的使用

4、量分別為： x1、x2 、x3 、x42.目標(biāo)函數(shù)：設(shè)總成本為z，則有： 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：人員安排問題n醫(yī)院護(hù)士24小時(shí)值班，每次值班8小時(shí)。不同時(shí)段需要的護(hù)士人數(shù)不等。據(jù)統(tǒng)計(jì)： 序號時(shí)段最少人數(shù)安排人數(shù)1061060x12101470x23141860x34182250x45220220x560

5、20630 x6例題3建模n目標(biāo)函數(shù)：min z=x1+x2+x3+x4+x5+x6n約束條件： 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合理下料問題n料長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.

6、1 0.2 0.3 0.8 0.9 1.1 1.4例題4建模設(shè)：xj為采用第 j種方案的根數(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航線號合同貨運(yùn)量12002400航線號船隊(duì)類型編隊(duì)形式貨運(yùn)成本（千元隊(duì)）貨運(yùn)量（千噸）拖輪a

7、型駁船b型駁船1112362521436202322472404142720問：應(yīng)如何編隊(duì)，才能既完成合同任務(wù)，又使總貨運(yùn)成本為最?。坷}5 某航運(yùn)局現(xiàn)有船只種類、數(shù)量以及計(jì)劃期內(nèi)各條航線的貨運(yùn)量、貨運(yùn)成本如下表所示：例題5建模設(shè)：xj為第 j 號類型船隊(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用單純形法可求

8、得： x1 = 8，x2 = 0 ，x3 = 7， x4 = 6 最優(yōu)值：z = 954即：四種船隊(duì)類型的隊(duì)數(shù)分別是 8、0、7、6，此時(shí)可使總貨運(yùn)成本為最小，為954千元。線性規(guī)劃模型特點(diǎn)線性規(guī)劃模型特點(diǎn)1 都用一組決策變量x = (x1,x2,xn)t表示某一方案； 滿足以上三個(gè)條件的數(shù)學(xué)模型稱為線性規(guī)劃滿足以上三個(gè)條件的數(shù)學(xué)模型稱為線性規(guī)劃2 都有一個(gè)要達(dá)到的目標(biāo)，并且目標(biāo)要求可以表示成決策變量的線性函數(shù)；3 都有一組約束條件，這些約束條件可以用決策變量的線性等式或線性不等 式來表示。3.23.2線性規(guī)劃問題的名詞和圖解法線性規(guī)劃問題的名詞和圖解法max z= x1+3x2 s.t. x

9、1+x26 -x1+2x28 x1,x20123456xz=0z=3z=6z=9z=12z=15.3013456約 束 條 件 （ 1）約 束 條 件 （ 2）c-1-8-2-3-4-5-6-7x214 將最優(yōu)解代入目標(biāo)函數(shù)，求出最優(yōu)值。1 在直角平面坐標(biāo)系中畫出所有的約束等式，并找出所有約束條件的公共部 分，稱為可行域，可行域中的點(diǎn)稱為可行解。2 標(biāo)出目標(biāo)函數(shù)值增加的方向。3 若求最大（小）值，則令目標(biāo)函數(shù)等值線沿（逆）目標(biāo)函數(shù)值增加的方向 平行移動(dòng)，找與可行域最后相交的點(diǎn)，該點(diǎn)就是最優(yōu)解。圖解法解題步驟圖解法解題步驟o123123xx21abcdx3=0 x4=0 x2=0 x1=0可行域

10、可行域(可行解全體可行解全體)基本可行解基本可行解(可行域頂點(diǎn)、極點(diǎn)可行域頂點(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ù)矩陣為：10120121a則：基變量為x3、x4，非基變量為x1、x23）x (1/2, 1/2, 3/2, 1/2)t不是基本解可行解不是基本可行解3.2.2 3.2.2 線性規(guī)劃的基本名詞線性規(guī)劃的基本

11、名詞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滿秩子矩陣為基矩陣，與基矩陣相對應(yīng)的變量稱為基變量（basic variable），其余變量稱為非基變量，令非基變量為零，可求得基變 量的值，這樣求出的解稱為基本解。 5基本可行解（basic feasible solution）： 滿足非負(fù)約束的基本解稱為基本可行解。若約束等式中有n個(gè)變量，m個(gè)約

12、束，則基本解的個(gè)數(shù)mnc基礎(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 aoabcde基變量x3 x4x1 x4x1 x2x2 x3x2 x4x1 x3非基變量x1 x2x2 x3x3 x4x1 x4x1 x3x2 x4xj0-x4x1基礎(chǔ)可行解是是是是否否1 可行解與最優(yōu)解：最優(yōu)解一定是可行解，但可行解不一定是最優(yōu)解。線性規(guī)劃解之間的關(guān)系線性規(guī)劃解之間的關(guān)系基本解不一定是可行解，可行解也不一定是基本解。2 可行解與基本解：3 可行解與基本可行解：基本可行

13、解一定是可行解，但可行解不一定是基本解?；究尚薪庖欢ㄊ腔窘?，但基本解不一定是基本可行解。4 基本解與基本可行解：5 最優(yōu)解與基本解：最優(yōu)解不一定是基本解，基本解也不一定是最優(yōu)解。問題：最優(yōu)解與基本可行解？非可行解可行解基本可行解基本解幾何概念代數(shù)概念約束直線滿足一個(gè)等式約束的解約束半平面滿足一個(gè)不等式約束的解約束半平面的交集：凸多邊形滿足一組不等式約束的解約束直線的交點(diǎn)基礎(chǔ)解可行域的極點(diǎn)基礎(chǔ)可行解目標(biāo)函數(shù)等值線：一組平行線 目標(biāo)函數(shù)值等于一個(gè)常數(shù)的解線性規(guī)劃解的性質(zhì)線性規(guī)劃解的性質(zhì)定理定理1 線性規(guī)劃的可行域 r 是一個(gè)凸集，且有有限個(gè)頂點(diǎn)。定理定理2 x是線性規(guī)劃可行域 r 頂點(diǎn)的充要條

14、件是 x 線性規(guī)劃的基本可行解。定理定理3 若線性規(guī)劃有最優(yōu)解，則必有基本最優(yōu)解。定理定理4 若線性規(guī)劃在可行域的兩個(gè)頂點(diǎn)上達(dá)到最優(yōu)，則在兩個(gè)頂點(diǎn)的連線 上也達(dá)到最優(yōu)。線性規(guī)劃問題的可行域是一個(gè)凸集。線性規(guī)劃的每一個(gè)基本可行解對應(yīng)凸集的每一個(gè)頂點(diǎn)。若線性規(guī)劃有最優(yōu)解，則一定在凸集的某個(gè)（些）頂點(diǎn)上達(dá)到最優(yōu)。若線性規(guī)劃在兩個(gè)頂點(diǎn)以上達(dá)到最優(yōu),則一定有無窮多個(gè)最優(yōu)解。最優(yōu)解一定是基本可行解，但基本可行解不一定是最優(yōu)解。解的形態(tài) (d)可行域無界可行域無界 (e)可行域無界可行域無界 (f)可行域?yàn)榭占尚杏驗(yàn)榭占?多個(gè)最優(yōu)解多個(gè)最優(yōu)解 目標(biāo)函數(shù)無界目標(biāo)函數(shù)無界 無可行解無可行解 (a)可行域有界可

15、行域有界 (b)可行域有界可行域有界 (c)可行域無界可行域無界 唯一最優(yōu)解唯一最優(yōu)解 多個(gè)最優(yōu)解多個(gè)最優(yōu)解 唯一最優(yōu)解唯一最優(yōu)解結(jié)論n可行域是個(gè)凸集n可行域有有限個(gè)頂點(diǎn)n最優(yōu)值在可行域的頂點(diǎn)上達(dá)到n唯一最優(yōu)解的情形n無窮多解的情形n無界解情形n無解情形線性規(guī)劃的一般模式1.決策變量： x = (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 +.+ a

16、mn 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 +.+ a2n xn = b2 am1x1 + am2 x2 +.+ amn xn = bm x1,x2,xn0線性規(guī)劃的標(biāo)準(zhǔn)形式線性規(guī)劃的標(biāo)準(zhǔn)形式其中：), 2 , 1( 0), 2 , 1(max(min)11njxmibxaxczjnjijijnjjj求和形式求和形式矩陣形式矩陣形式0 max(

17、min)xbaxcxznxxxx21決策變量決策變量常數(shù)項(xiàng)常數(shù)項(xiàng)nbbbb21系數(shù)矩陣系數(shù)矩陣nmijmnmmnnaaaaaaaaaaa212222111211價(jià)值系數(shù)價(jià)值系數(shù)ncccc21其中：標(biāo)準(zhǔn)型的特征n目標(biāo)函數(shù)極大化n約束條件為等式n決策變量非負(fù)n約束方程右側(cè)常數(shù)全部非負(fù)正規(guī)型的特征n標(biāo)準(zhǔn)型n每一個(gè)約束方程均有基變量非標(biāo)準(zhǔn)型轉(zhuǎn)化為正規(guī)型n目標(biāo)函數(shù)極小化轉(zhuǎn)為極大化： minz=max(z) ，一個(gè)數(shù)的極小化等價(jià)于其相反數(shù)的極大化。n不等式約束的轉(zhuǎn)化： aijxjbi 加入松弛變量 aijxjbi 減去剩余變量n非正變量：即xk 0 則令xk = xk 自由變量：即xk無約束，令xk= x

18、kx”k非標(biāo)準(zhǔn)型轉(zhuǎn)化舉例之一之一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

19、 x2 0 x3無約束 x1 0 x2 0 x3 0 x”3 0 x40 x50 正規(guī)化1. 目測：松馳變量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ī)劃問題策略求解一般線性規(guī)劃問題策略尋找初始基本可行解尋找初始基本可行解給出基本可行解為最優(yōu)

20、解的判別準(zhǔn)則給出基本可行解為最優(yōu)解的判別準(zhǔn)則給出從目前基本可行解轉(zhuǎn)移到新基本給出從目前基本可行解轉(zhuǎn)移到新基本 可行解的方法可行解的方法求解流程求解流程 確定初始確定初始基本可行解基本可行解最優(yōu)解？最優(yōu)解？否否轉(zhuǎn)移到新轉(zhuǎn)移到新的基本可行解的基本可行解給出最優(yōu)解給出最優(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例解：（表圖）max z=x1+3x2ds.t. x1+ x2+x3=6 b-x1+2x2 +x4=8 x

21、4=0 c x3=0 x1, x2,x3,x40 x1=0 e o x2=0 aoabcde基變量x3 x4x1 x4x1 x2x2 x3x2 x4x1 x3非基變量x1 x2x2 x3x3 x4x1 x4x1 x3x2 x4xj0-x4x1基礎(chǔ)可行解是是是是否否 cj1 3 0 0cbxbbx1 x2 x3 x4j 0 0 x3x468 1 1 1 0 -1 2 0 1 6/18/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

22、-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 aoabcde基變量x3 x4x1 x4x1 x2x2 x3x2 x4x1 x3非基變量x1 x2x2 x3x3 x4x1 x4x1 x3x2 x4xj0-x4x1基礎(chǔ)可行解是是是是否否步驟n用正規(guī)型表示問題，確定初始基可行解n填入初始單純形表n求相對利潤系數(shù)。如果全部非正，則停止n選擇旋入變量n用最小比值法確定旋出變量n旋轉(zhuǎn)運(yùn)算計(jì)算表格數(shù)據(jù)和相對利潤系數(shù)

23、。返回第三步3.4 大m法和兩階段法n例解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 -2 0 1 0

24、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 0初始單純形表大m法miijijjacc1b cj3 -1 -1 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 14-z2 1 0 0 0 -1 1-m -1-m -3 1 1x1x2x341 91 0 0 1/

25、3 -2/3 2/3 -5/30 1 0 0 -1 1 -2 0 0 1 2/3 -4/3 4/3 -7/3大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 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 0初始單純形表兩階段法第一階段 cj0 0 0 0 0 -

26、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 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兩階段法第二階段mii

27、jijjacc1b3.5單純形法的進(jìn)一步探討n極小化問題直接求解：檢驗(yàn)數(shù)的判別由所有j 0 即為最優(yōu)，變?yōu)樗衘 0則為最優(yōu)。n無窮多最優(yōu)解情形：非基變量檢驗(yàn)數(shù) j= 0 (在最終單純形表中)n退化解的情形：有兩個(gè)以上 值相等n無界解n無解 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 0023x5

28、x2x115/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-無窮多個(gè)最優(yōu)解 cj0 0 0 2 0 1.5cbxbbx1 x2 x3 x4 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.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