線性規(guī)劃和單純形法.ppt

1、教學(xué)要求：,第二章 線性規(guī)劃和單純形法,掌握線性規(guī)劃的基本建模法和單純形法基本原理,會(huì)在不同條件下運(yùn)用單純形法求解線性規(guī)劃問(wèn)題,了解線性規(guī)劃在經(jīng)濟(jì)和管理中的基本應(yīng)用方法,LP(Linear Programming),2.1 線性規(guī)劃實(shí)例與模型,一、實(shí)例與建模 例1：某公司通過(guò)市場(chǎng)調(diào)研，決定生產(chǎn)高中檔新型拉桿箱。某分銷商決定買進(jìn)該公司3個(gè)月內(nèi)的全部產(chǎn)品。拉桿箱生產(chǎn)需經(jīng)過(guò)原材料剪裁、縫合、定型、檢驗(yàn)和包裝4過(guò)程。 通過(guò)分析生產(chǎn)過(guò)程，得出：生產(chǎn)中檔拉桿箱需要用7/10小時(shí)剪裁、5/10小時(shí)縫合、1小時(shí)定型、1/10小時(shí)檢驗(yàn)包裝；生產(chǎn)高檔拉桿箱則需用1小時(shí)剪裁、5/6小時(shí)縫合、2/3小時(shí)定型、1/4小

2、時(shí)檢驗(yàn)包裝。由于公司生產(chǎn)能力有限，3月內(nèi)各部的最大生產(chǎn)時(shí)間為剪裁部630小時(shí)、縫合部600小時(shí)、定型部708小時(shí)、檢驗(yàn)包裝部135小時(shí)。 通過(guò)市場(chǎng)調(diào)研部和會(huì)計(jì)部的調(diào)查核算得出結(jié)論：生產(chǎn)中檔拉桿箱的利潤(rùn)是10元，高檔拉桿箱的利潤(rùn)是9元。公司應(yīng)各生產(chǎn)多少中檔和高檔拉桿箱才能使公司利潤(rùn)最大？,實(shí)用舉例,某公司通過(guò)市場(chǎng)調(diào)研，決定生產(chǎn)高中檔新型拉桿箱。某分銷商決定買進(jìn)該公司3個(gè)月內(nèi)的全部產(chǎn)品。拉桿箱生產(chǎn)需經(jīng)過(guò)原材料剪裁、縫合、定型、檢驗(yàn)和包裝4過(guò)程。 通過(guò)分析生產(chǎn)過(guò)程，得出：生產(chǎn)中檔拉桿箱需要用7/10小時(shí)剪裁、5/10小時(shí)縫合、1小時(shí)定型、1/10小時(shí)檢驗(yàn)包裝；生產(chǎn)高檔拉桿箱則需用1小時(shí)剪裁、5/6小

3、時(shí)縫合、2/3小時(shí)定型、1/4小時(shí)檢驗(yàn)包裝。由于公司生產(chǎn)能力有限，3月內(nèi)各部的最大生產(chǎn)時(shí)間為剪裁部630小時(shí)、縫合部600小時(shí)、定型部708小時(shí)、檢驗(yàn)包裝部135小時(shí)。 通過(guò)市場(chǎng)調(diào)研部和會(huì)計(jì)部的調(diào)查核算得出結(jié)論：生產(chǎn)中檔拉桿箱的利潤(rùn)是10元，高檔拉桿箱的利潤(rùn)是9元。公司應(yīng)各生產(chǎn)多少中檔和高檔拉桿箱才能使公司利潤(rùn)最大？,線性規(guī)劃模型的建立,建立相應(yīng)的線性規(guī)劃模型 ：其中的 稱為決策變量。,目標(biāo)函數(shù),某工廠用三種原料生產(chǎn)三種產(chǎn)品，已知的條件如表下所示，試制訂總利潤(rùn)最大的生產(chǎn)計(jì)劃。,例2：生產(chǎn)計(jì)劃問(wèn)題,問(wèn) 題 分 析,模 型,計(jì) 算 結(jié) 果,例3：運(yùn)輸問(wèn)題,問(wèn) 題 分 析,模 型,例4：家具廠生產(chǎn)計(jì)

4、劃問(wèn)題 勝利家具廠生產(chǎn)桌子和椅子兩種家具。桌子銷售利潤(rùn)為50元，椅子銷售利潤(rùn)為30元。生產(chǎn)一個(gè)桌子需要木工4小時(shí)，油漆工2小時(shí)；生產(chǎn)一個(gè)椅子需要木工3小時(shí)，油漆工1小時(shí)。該廠可用木工工時(shí)120小時(shí)，可用油漆工工時(shí)50小時(shí)，該廠如何生產(chǎn)才能使每月銷售利潤(rùn)最大？,例5：利博公司廣告組合問(wèn)題 管理層決定集中在下列三個(gè)主要產(chǎn)品上實(shí)行一個(gè)大規(guī)模的新的廣告運(yùn)動(dòng)：一種噴霧去污劑、一種新的液體洗滌劑和一種成熟的洗衣粉。這一廣告運(yùn)動(dòng)會(huì)采用電視和印刷媒體，總目標(biāo)是增加這些產(chǎn)品的銷售額，管理部門設(shè)定了如下廣告運(yùn)動(dòng)的目標(biāo)。噴霧去污劑必須至少增加3%的市場(chǎng)份額。新的液體洗滌劑必須至少增加18%的市場(chǎng)份額。洗衣粉占洗滌劑

5、市場(chǎng)的份額必須至少增加4%。每單位廣告增加的市場(chǎng)分額見(jiàn)下表。問(wèn)題：在最低的總成本下達(dá)到市場(chǎng)份額的目標(biāo)要在每種媒體上做多少錢的廣告？,每單位廣告增加的市場(chǎng)分額表,練習(xí)：節(jié)約下料問(wèn)題 設(shè)有一批規(guī)格為10米長(zhǎng)的圓鋼筋，將它截成分別為3米，4米長(zhǎng)的預(yù)制構(gòu)件的短鋼筋各100根，問(wèn)怎樣截取最省料。,提示：10米長(zhǎng)的鋼筋截為3米或4米長(zhǎng)，共有三種截法： 截法：3 3 3 1 米 截法：3 3 4 0 米 截法：4 4 0 2 米,二、線性規(guī)劃模型的標(biāo)準(zhǔn)形式,其中c=(c1,c2,cn)，稱為價(jià)值系數(shù)向量；,一般線性規(guī)劃模型,矩陣形式,稱為資源限制向量,X=(x1,x2,xn)T 稱為決策變量向量,稱為技術(shù)系

6、數(shù)矩陣(也稱消耗系數(shù)矩陣),2.2一般線性規(guī)劃模型,線性規(guī)劃模型的標(biāo)準(zhǔn)形式,Max Z = c1x1 + c2x2 + + cnxn Subject to (s.t.) a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 am1x1 + am2x2 + + amnxn= bm x1 0, x2 0, , xn 0,為了討論方便，把最大化、等式約束型的線性規(guī)劃稱為線性規(guī)劃的標(biāo)準(zhǔn)型，即,可以看出，線性規(guī)劃的標(biāo)準(zhǔn)形式有如下四個(gè)特點(diǎn)： 目標(biāo)最大化； 約束為等式； 決策變量均非負(fù)； 右端項(xiàng)非負(fù)。 對(duì)于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題，可以通過(guò)以

7、下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式。,如何轉(zhuǎn)化為標(biāo)準(zhǔn)形式？,1、目標(biāo)函數(shù)為求極小值，即為： 。,因?yàn)榍?min z 等價(jià)于求 max (-z)，令 z = - z， 即化為：,2、約束條件為不等式，,如何處理？,xn+1 0 松弛變量,、右端項(xiàng)bi 0時(shí)，只需將等式兩端同乘（-1）則右端項(xiàng)必大于零 （在實(shí)際問(wèn)題中，資源約束應(yīng)大于0，對(duì)于數(shù)學(xué)而言加以討論是完善理論。）,4、決策變量無(wú)非負(fù)約束,設(shè) xj 沒(méi)有非負(fù)約束，若 xj 0，可令 xj = - xj ， 則 xj 0；,又若 xj 為自由變量，即 xj 可為任意實(shí)數(shù)， 可令 xj = xj - xj，且 xj , xj 0,標(biāo)準(zhǔn)化,對(duì)某個(gè),是任意的

8、,在實(shí)際問(wèn)題中表示未使用的資源或能力，對(duì)利潤(rùn)沒(méi)有貢獻(xiàn)，在目標(biāo)函數(shù)中其系數(shù)為零，該資源可出售。,在實(shí)際問(wèn)題中表示超過(guò)某一最低需求的量。,例1:將如下線性規(guī)劃模型標(biāo)準(zhǔn)化：,min z= x1 + 5 x2 - 8 x3 - x4 s.t. 2 x1 - 3 x2 + x3 + x4 20 x1+ 2 x2 + 3 x3 - x4 30 2x2 + 2 x3 +3 x4- 50 x1 , x3 , x4 0，x2取值無(wú)約束。,max z1=-x1-5 x2+8 x3 +x4 s.t. 2 x1 - 3 x2 + x3 + x4 20 x1+ 2 x2 + 3 x3 - x4 30 2x2 + 2 x

9、3 +3 x4- 50 x1 , x3 , x4 0，x2取值無(wú)約束。,Max z2 =-x1-5y2+5y3+8x3+x4 s.t. 2 x1 - 3 y2+3y3 + x3 + x4 20 -x1- 2 y2 +2y3 - 3 x3 + x4 -30 -2y2 +2y3 - 2 x3 -3 x4 50 x1 , x3 , x4 ,y2,y3 0,max z1=-x1-5 x2+8 x3 +x4 s.t. 2 x1 - 3 x2 + x3 + x4 20 x1+ 2 x2 + 3 x3 - x4 30 2x2 + 2 x3 +3 x4- 50 x1 , x3 , x4 0，x2取值無(wú)約束,M

10、ax z2 =-x1-5y2+5y3+8x3+x4 s.t. 2 x1 - 3 y2+3y3 + x3 + x4 +x5 =20 -x1- 2 y2 +2y3 - 3 x3 + x4 +x6 = -30 -2y2 +2y3 - 2 x3 -3 x4 +x7 = 50 x1 , x3 , x4 , x5, x6, x7, y2, y3 0,Max z2 =-x1-5y2+5y3+8x3+x4 s.t. 2 x1 - 3 y2+3y3 + x3 + x4 20 -x1- 2 y2 +2y3 - 3 x3 + x4 -30 -2y2 +2y3 - 2 x3 -3 x4 50 x1 , x3 , x4

11、 ,y2,y3 0,練習(xí)1：,試將 LP 問(wèn)題,min z = -x1+2x2-3x3 s.t. x1+x2+x3 7 x1-x2+x3 2 -3x1+x2+2x3 = -5 x1,x2 0 化為標(biāo)準(zhǔn)形式。,解：,令 x3= x4 - x5 其中x4、x5 0；,對(duì)第一個(gè)約束條件加上松弛變量 x6 ；,對(duì)第二個(gè)約束條件減去松弛變量 x7 ；,對(duì)第三個(gè)約束條件兩邊乘以“-1” ；,令 z=-z 把求 min z 改為求 max z；,max z= x1-2x2+3x4- 3x5 s.t. x1+x2+x4-x5+x6=7 x1-x2+x4-x5-x7=2 3x1-x2-2x4+2x5=5 x1,

12、x2,x4,x5,x6,x70,1、可行解:滿足所有約束條件的解x=（x1，x2，.，xn），稱為線性規(guī)劃問(wèn)題的可行解。所有可行解的集合稱為可行域。,三、線性規(guī)劃的解,2、最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最優(yōu)值的可行解稱為最優(yōu)解。,3、基： 設(shè)A是約束方程組的mn階系數(shù)矩陣，秩為m，設(shè) 是A中mm階非奇異子矩陣（即 ），則稱是線性規(guī)劃問(wèn)題的一個(gè)基矩陣，簡(jiǎn)稱基。B中的列向量稱為基向量，與基向量對(duì)應(yīng)的變量x稱為基變量，其它變量稱為非基變量。,4、基本解：令非基變量=0，則由Ax=b可求出一個(gè)解，這個(gè)解x稱為基本解。,5、基本可行解：滿足非負(fù)條件的基本解稱為基本可行解。,6、可行基：對(duì)應(yīng)于基本可行解的基稱為可

13、行基。,可行解、基本解、基本可行解的關(guān)系,可行解,基本解,基本可行解,例：說(shuō)明LP問(wèn)題中何為基、基變量、基本解、基本可行解、可行基？,練習(xí)： LP問(wèn)題,x2不滿足非負(fù)條件,例1. 某工廠在計(jì)劃期內(nèi)要安排、兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗、資源的限制，如下表：?jiǎn)栴}：工廠應(yīng)分別生產(chǎn)多少單位、產(chǎn)品才能使工廠獲利最多？,線性規(guī)劃模型： 目標(biāo)函數(shù)：Max z=50 x1 +100 x2 約束條件：s.t. x1+ x2300 2 x1 +x2400 x2250 x1 , x20,2.3線性規(guī)劃的圖解法與基本性質(zhì),一、圖 解 法,(1)分別取決策變量X1 , X2為坐

14、標(biāo)向量建立直角坐標(biāo)系。在直角坐標(biāo)系里，圖上任意一點(diǎn)的坐標(biāo)代表了決策變量的一組值，例1的每個(gè)約束條件都代表一個(gè)半平面。,（2）對(duì)每個(gè)不等式(約束條件)，先取其等式在坐標(biāo)系中作直線，然后確定不等式所決定的半平面。,（3）把五個(gè)圖合并成一個(gè)圖，取各約束條件的公共部分，如圖2-1所示。,（4）目標(biāo)函數(shù)z=50 x1+100 x2，當(dāng)z取某一固定值時(shí)得到一條直線，直線上的每一點(diǎn)都具有相同的目標(biāo)函數(shù)值，稱之為“等值線”。平行移動(dòng)等值線，當(dāng)移動(dòng)到B點(diǎn)時(shí)，z在可行域內(nèi)實(shí)現(xiàn)了最大化。A，B，C，D，E是可行域的頂點(diǎn)，對(duì)有限個(gè)約束條件則其可行域的頂點(diǎn)也是有限的。,線性規(guī)劃的標(biāo)準(zhǔn)化內(nèi)容之一：引入松馳變量（含義是資源

15、的剩余量） 例1 中引入x3，x4，x5 模型化為 目標(biāo)函數(shù)：Maxz = 50 x1+100 x2+0 x3 +0 x4 +0 x5 約束條件：s.t. x1 + x2 + x3= 300 2 x1 + x2 + x4 = 400 x2+ x5= 250 x1 , x2 , x3，x4，x5 0 對(duì)于最優(yōu)解 x1 =50 x2 = 250 ,x3 = 0 ,x4 =50 ,x5 = 0 說(shuō)明：生產(chǎn)50單位產(chǎn)品和250單位產(chǎn)品將消耗完所有 可能的設(shè)備臺(tái)時(shí)數(shù)及原料B，但對(duì)原料A則還剩余50千克。,1、如果線性規(guī)劃有最優(yōu)解，則一定有一個(gè)可行域的頂點(diǎn)對(duì)應(yīng)一個(gè)最優(yōu)解；,重要結(jié)論：,2、無(wú)窮多個(gè)最優(yōu)解。

16、若將例1中的目標(biāo)函數(shù)變?yōu)閙ax z=50 x1+50 x2，則線段BC上的所有點(diǎn)都代表了最優(yōu)解；,3、無(wú)界解。即可行域的范圍延伸到無(wú)窮遠(yuǎn)，目標(biāo)函數(shù)值可以無(wú)窮大或無(wú)窮小。一般來(lái)說(shuō)，這說(shuō)明模型有錯(cuò)，忽略了一些必要的約束條件；,4、無(wú)可行解。若在例1的數(shù)學(xué)模型中再增加一個(gè)約束條件4x1+3x21200，則可行域?yàn)榭沼?，不存在滿足約束條件的解，當(dāng)然也就不存在最優(yōu)解了。,max z = 15x1 +25x2 s.t. x1 + 3x2 60 x1 + x2 40 x1，x2 0,(40,0),(0,0),B,C,(30,10),O,L1,L2,Z=250,目標(biāo)函數(shù)變形：,x2=-3/5 x1+z/25,

17、x2,x1,最優(yōu)解： x1=30 x2 =10 最優(yōu)值：zmax=700,B點(diǎn)是使z達(dá)到最大的唯一可行點(diǎn),例2：,LP問(wèn)題圖解法的基本步驟：,1、在平面上建立直角坐標(biāo)系；,2、圖示約束條件，確定可行域和頂點(diǎn)坐標(biāo)；,3、圖示目標(biāo)函數(shù)（等值線）和移動(dòng)方向；,4、尋找最優(yōu)解。,當(dāng)只有兩個(gè)決策變量時(shí)，可用圖解法求解！,例3：用圖解法求解以下線形規(guī)劃問(wèn)題。 max z=4x1+3x2 s.t. x16 2x28 2x1+3x218 x10，x20,x1,x2,B（6，2）得z=4*4+3*2=30,二、解的特殊情況多個(gè)最優(yōu)解（無(wú)窮個(gè)）,目標(biāo)函數(shù)等值線與可行域的一個(gè)邊界所在的約束直線重合,max z =3

18、x1 + 5.7x2 s.t. x1 + 1.9x2 3.8 x1 - 1.9x2 3.8 x1 + 1.9x2 11.4 x1 - 1.9x2 -3.8 x1 ，x2 0,x1,x2,o,x1 - 1.9 x2 = 3.8,x1 + 1.9 x2= 3.8,x1 + 1.9 x2 = 11.4,（7.6,2）,D,0=3 x1 +5.7 x2,max Z,min Z,（3.8,4）,34.2 = 3 x1 +5.7 x2,可行域,x1 - 1.9 x2 = -3.8,(0,2),(3.8,0),綠色線段上的所有點(diǎn) 都是最優(yōu)解,即有無(wú)窮多最優(yōu)解。Zman=34.2,解的特殊情況無(wú)可行解（約束過(guò)

19、嚴(yán)）,沒(méi)有一個(gè)點(diǎn)能同時(shí)滿足所有的約束和非負(fù)條件,解的特殊情況無(wú)界解（遺漏約束）,max z = 2x1 + 2x2 s.t. 2x1 x2 2 -x1 + 4x2 4 x1，x2 0,O,x1,x2,Note: 可行域?yàn)闊o(wú)界區(qū)域， 目標(biāo)函數(shù)值可無(wú)限 增大，即解無(wú)界。 稱為無(wú)最優(yōu)解。,可行域?yàn)闊o(wú)界區(qū)域一定無(wú)最優(yōu)解嗎？,X,若線性規(guī)劃有最優(yōu)解，則最優(yōu)解必在可行域的頂點(diǎn)上達(dá)到。,討論,可行域與最優(yōu)解的關(guān)系： 可行域是空集，則無(wú)最優(yōu)解； 可行域?yàn)橛薪缂瘯r(shí)，則或有唯一最優(yōu)解或有多個(gè)最優(yōu)解；最優(yōu)解存在且唯一，則一定在頂點(diǎn)上達(dá)到；最優(yōu)解存在且不唯一，一定存在頂點(diǎn)是最優(yōu)解； 可行域?yàn)闊o(wú)界集時(shí)，則或有唯一最優(yōu)解

20、或有多個(gè)最優(yōu)解或有無(wú)界解。,三、圖解法的靈敏度分析,靈敏度分析：建立數(shù)學(xué)模型和求得最優(yōu)解后，研究線性規(guī)劃的一個(gè)或多個(gè)參數(shù)（系數(shù)）ci , aij , bj 變化時(shí)，對(duì)最優(yōu)解產(chǎn)生的影響。 1、 目標(biāo)函數(shù)中的系數(shù) ci 的靈敏度分析 考慮例1的情況，ci 的變化只影響目標(biāo)函數(shù)等值線的斜率， 目標(biāo)函數(shù) z=50 x1+100 x2 在z=x2 (x2=z斜率為0)到z=x1+x2 (x2=-x1+z斜率為-1 )之間時(shí)，原最優(yōu)解x1=50，x2=100仍是最優(yōu)解。 一般情況：z=c1x1+c2x2寫成斜截式x2=-(c1/c2)x1+z/c2 目標(biāo)函數(shù)等值線的斜率為-(c1/c2) ， 當(dāng)-1 -(

21、c1/c2)0（*）時(shí)，原最優(yōu)解仍是最優(yōu)解。,（1）假設(shè)產(chǎn)品的利潤(rùn)100元不變，即 c2=100，代到式（*）并整理得 0c1100 （2）假設(shè)產(chǎn)品的利潤(rùn) 50 元不變，即 c1=50 ，代到式（*）并整理得 50c2+ （3）假若產(chǎn)品、的利潤(rùn)均改變，則可直接用式（*）來(lái)判斷。 假設(shè)產(chǎn)品、的利潤(rùn)分別為60元、55元，則 - 2 -(60/55)-1 那么，最優(yōu)解為 z=x1+x2 和 z=2x1+x2 的交點(diǎn) x1=100，x2=200,進(jìn)一步討論,2、約束條件中右邊系數(shù) bj 的靈敏度分析 當(dāng)約束條件中右邊系數(shù) bj 變化時(shí)，線性規(guī)劃的可行域發(fā)生變化，可能引起最優(yōu)解的變化。 在例1中(1)假

22、設(shè)設(shè)備臺(tái)時(shí)增加10個(gè)臺(tái)時(shí)，即 b1變化為310,這時(shí)可行域擴(kuò)大，最優(yōu)解為： x2=250和x1+x2=310的交點(diǎn)x1=60，x2=250 。 增加的利潤(rùn)=變化后的總利潤(rùn)-變化前的總利潤(rùn) (5060+100250)-(5050+100250)=500,500/10=50元，說(shuō)明在一定范圍內(nèi)每增加（減少）1個(gè)臺(tái)時(shí)的設(shè)備能力就可增加（減少）50元利潤(rùn)，稱為該約束條件的對(duì)偶價(jià)格。,在一定范圍內(nèi)，當(dāng)約束條件右邊常數(shù)增加1個(gè)單位時(shí) （1）若約束條件的對(duì)偶價(jià)格大于0，則其最優(yōu)目標(biāo)函數(shù)值得 到改善（變好）； （2）若約束條件的對(duì)偶價(jià)格小于0，則其最優(yōu)目標(biāo)函數(shù)值受 到影響（變壞）； （3）若約束條件的對(duì)偶價(jià)格

23、等于0，則最優(yōu)目標(biāo)函數(shù)值不變。,(2)假設(shè)原料 A 增加10 千克時(shí)，即 b2變化為410，這時(shí)可行域擴(kuò)大，但最優(yōu)解仍為 x2=250和x1+x2=300的交點(diǎn) x1=50，x2=250。 此變化對(duì)總利潤(rùn)無(wú)影響，該約束條件的對(duì)偶價(jià)格為 0 。,解釋：原最優(yōu)解沒(méi)有把原料 A 用盡，有50千克的剩余，因此增加10千克值增加了庫(kù)存，而不會(huì)增加利潤(rùn)。,圖解法優(yōu)點(diǎn)：,直觀、易掌握。有助于了解解的結(jié)構(gòu)。,圖解法缺點(diǎn)：,只能解決低維問(wèn)題，對(duì)高維無(wú)能為力。,習(xí)題,P35 2.1(2)(4) 2.2 2.3(1),四、凸集的概念,凸集是線性規(guī)劃中一個(gè)很重要的概念，凸集的一般定義為：如果在集合C中任意取兩個(gè)點(diǎn)x1

24、，x2，其連線上的所有點(diǎn)也都在集合C中，則稱集合C為凸集合。用數(shù)學(xué)解析式表達(dá)為：對(duì)任意 ，均有 ，則稱C是凸集合。,非凸集,非凸集,凸集,頂點(diǎn)的概念,頂點(diǎn):凸集C中滿足下述條件的點(diǎn)X稱為頂點(diǎn)，如果在集合C中不存在任意取兩個(gè)不同點(diǎn)x1，x2，使得X成為這兩個(gè)點(diǎn)連線上的一個(gè)點(diǎn)。 用數(shù)學(xué)解析式表達(dá)為： 對(duì)任意 ，如果X不能表示為 ，則稱X是凸集C的頂點(diǎn)。,五、線性規(guī)劃的基本性質(zhì),定理2.1：線性規(guī)劃的可行域： 是凸集（凸多面體）。,引理2.1：線性規(guī)劃的可行解 為基本可行解的充分必要條件是x的正分量所對(duì)應(yīng)的系數(shù)列向量是線性無(wú)關(guān)的，即每個(gè)正分量都是一個(gè)基變量。,定理2.2：線性規(guī)劃問(wèn)題的基本可行解x對(duì)

25、應(yīng)于可行域的頂點(diǎn),定理2.3：若線性規(guī)劃有最優(yōu)解，則最優(yōu)解必在可行域的頂點(diǎn)上達(dá)到。,max z= x1-2x2+3x4- 3x5 s.t. x1+x2+x4-x5+x6=7 x1-x2+x4-x5-x7=2 3x1-x2-2x4+2x5=5 x1,x2,x4,x5,x6,x70,令 x1=x2=x4=0,基本解唯一嗎？ 最多有多少？,20,Note:,1、圖解法無(wú)法解決；,2、計(jì)算復(fù)雜性問(wèn)題。,設(shè)有一個(gè)50個(gè)變量、20個(gè)約束等式的 LP 問(wèn)題，則 最多可能有 個(gè)基。,即約150萬(wàn)年,單純形法（Simplex Method）是1947年由 G.B.Dantzig 提出，是解 LP 問(wèn)題最有效的算

26、法之一，且已成為整數(shù)規(guī)劃和非線性規(guī)劃某些算法的基礎(chǔ)。,基本思路： 基于 LP 問(wèn)題的標(biāo)準(zhǔn)形式，先設(shè)法找到一個(gè)基可 行解，判斷它是否是最優(yōu)解，如果是則停止計(jì)算；否 則，則轉(zhuǎn)換到相鄰的目標(biāo)函數(shù)值不減的一個(gè)基可行解 （兩個(gè)基可行解相鄰是指它們之間僅有一個(gè)基變量不 相同）。,2.4單純形法原理,對(duì)于線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式：,max z = c1x1 + c2x2 + + cnxn s.t. a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 am1x1 + am2x2 + + amnxn = bm xj 0 （j = 1,2,n） bi

27、0 （i = 1,2,m）,特點(diǎn)：,1、目標(biāo)函數(shù)為極 大化；,2、除決策變量的 非負(fù)約束外，所有 的約束條件都是等 式，且右端常數(shù)均 為非負(fù)；,3、所有決策變量 均非負(fù)。,LP的幾種表示形式：,在上述 LP 問(wèn)題中，約束方程組（2）的系數(shù) 矩陣 A 的任意一個(gè) mm 階的非奇異的子方陣 B （即 |B|0），稱為 LP 問(wèn)題的一個(gè)基陣或基。,稱 pi (i=1,2,m) 為基向量;,xi (i=1,2,m) 為基變量；,xj (j= m+1,n) 為非基變量,pj (j= m+1,n) 為非基向量;,記：,則 A = ( B, N ),A = ( B, N ),xB= (x1,xm)T , x

28、N =(xm+1,xn)T,代入約束方程(2)，Ax=b，得,松弛變量 （人工變量）,令,稱（4）為相應(yīng)于基 B 的基本解,是可行解嗎？,如果 B-1b 0，則稱（4）為相應(yīng)于基 B 的基可行解，此時(shí)的基 B 稱為可行基。,稱它是非退化的解；反之，如果有一個(gè)基變量也取 零值，則稱它是退化的解。一個(gè)LP問(wèn)題，如果它的 所有基可行解都是非退化的就稱該是非退化的，否 則就稱它是退化的。,一、初始基本可行解的確定,考慮如下形式的線性規(guī)劃問(wèn)題 max z=c1x1+c2x2+.+cnxn s.t. a11x1+a12x2+a1nxnb1 a21x1+a22x2+a2nxnb2 (1) . am1x1+a

29、m2x2+ +amnxnbm x1，x2，.，xn0 (2) 對(duì)每個(gè)不等式約束引入一個(gè)非負(fù)松弛變量，得標(biāo)準(zhǔn)形式： max z=c1x1+c2x2+.+cn xn s.t. a11x1+a1nxn+xn+1 =b1 a21x1+a2nxn +xn+2 =b2 (3) . am1x1+amn xn +xn+m =bm x1，x2，.，xn，xn+1，xn+m0,是線性規(guī)劃(2)的一個(gè)可行基。令非基變量為零,得,由此得到一個(gè)初始基本可行解為,而基變量為,單純形法引例,首先，化原問(wèn) 題為標(biāo)準(zhǔn)形式：,x3, x4 是基變量。,基變量用非基變量表示：,x3 = 60 -x1 - 3x2 x4 = 40 -

30、x1 - x2,代入目標(biāo)函數(shù)：,z =15 x1+25 x2,令非基變量 x1= x2=0,z=0 基可行解 x(0)=(0,0,60,40)T,是最優(yōu)解？,max z = 15x1 +25x2 s.t. x1 + 3x2 60 x1 + x2 40 x1，x2 0,max z = 15x1 + 25x2 + 0 x3 + 0 x4 s.t. x1 + 3x2 + x3 = 60 x1 + x2 + x4=40 x1，x2 , x3, x4 0,z =15 x1+25 x2 x3 = 60 -x1 - 3x2 x4 = 40 -x1 - x2,因?yàn)閤2 的系數(shù)大，所以x2 換入基變量。,x3

31、= 60 - 3x2 0 x4 = 40 - x2 0,誰(shuí)換出？,如果 x4 換出，則x2 = 40， x3 = -60，不可行。,如果是“+”會(huì)怎樣？,如果 x3 換出，則x2 = 20， x4 = 20。,最小比值法則,所以 x3 換出。,基變量用非基變量表示：,代入目標(biāo)函數(shù)：,z =500+20/3 x1- 25/3 x3,令非基變量 x1= x3=0,z=500 基可行解 x(1)=(0,20,0,20)T,大于零！,因?yàn)閤1 的系數(shù)大，所以x1 換入基變量。,所以 x4 換出。,基變量用非基變量表示：,代入目標(biāo)函數(shù)：,z =700 5 x3 10 x4,令非基變量 x3= x4=0,

32、z=700 基可行解 x(2)=(30,10,0,0)T,因?yàn)榉腔兞康南禂?shù)都小于零， 所以 x(2)=(30,10,0,0)T 是最優(yōu)解 zmax=700,目標(biāo)函數(shù)用非基變量表示時(shí)，非基變量的系數(shù)稱為檢驗(yàn)數(shù),(40,0),(0,0),(0,20),A,B,C,(30,10),O,L1,L2,Z=250,x2,x1,x(0)=(0,0,60,40)T z=0,x(1)=(0,20,0,20)T z=500,x(2)=(30,10,0,0)T z=700,二、單純形法的基本原理,稱(1a)(2a)(3a)為L(zhǎng)P問(wèn)題對(duì)應(yīng)于 基 B 的典則形式（典式）.,Ax = b,基變量用非基變量表示：,代入目

33、標(biāo)函數(shù)：,如果記,則典式(1a)(2a)(3a) 可寫成,定理 7 在 LP 問(wèn)題 的典式 (1b) (3b)中， 如果有,則對(duì)應(yīng)于基 B 的基可行解,是 LP 問(wèn)題的最優(yōu)解，記為,相應(yīng)的目標(biāo)函數(shù)最優(yōu)值 z*=z(0),此時(shí)，基B稱 為最優(yōu)基,定理 8 在 LP 問(wèn)題 的典式 (1b) (3b)中，,是對(duì)應(yīng)于基 B 的一個(gè)基可行解，如果滿足下列條件：,(1)有某個(gè)非基變量 xk 的檢驗(yàn)數(shù) k 0 (m+1 k n);,(2)aik(i=1,2,m) 不全小于或等于零，即至少有一個(gè) aik0 (i=1,2,m) ;,(3) 0 (i=1,2,m) ,即x(0) 為非退化的基可行解。,則從 x(0

34、)出發(fā)，一定能找到一個(gè)新的基可行解,三、最優(yōu)性檢驗(yàn),定理2.4： 在最大化問(wèn)題中，對(duì)于某個(gè)基本可行解，如果所有 的 ，則這個(gè)基本可行解是最優(yōu)解。 在最小化問(wèn)題中，對(duì)于某個(gè)基本可行解，如果所有 的 ，則這個(gè)基本可行解是最優(yōu)解。,例：某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗見(jiàn)下表。該工廠生產(chǎn)一件甲產(chǎn)品獲利2元，乙產(chǎn)品獲利3元，問(wèn)應(yīng)如何安排生產(chǎn)計(jì)劃可使該企業(yè)獲利最多？,四、單純形法求解步驟,將所給問(wèn)題化為標(biāo)準(zhǔn)形 找出一個(gè)初始可行基，建立初始單純形表 檢查所有檢驗(yàn)數(shù)(若全為非負(fù),則已得到最優(yōu)解,計(jì)算停止，否則繼續(xù)下一步) 考察是否無(wú)解(若是，計(jì)算停止，否則繼續(xù)下

35、一步) 確定入基變量,出基變量 對(duì)初始單純形表進(jìn)行單純形變換,單純形方法的一般步驟,確定一個(gè)初始可行解點(diǎn),根據(jù)某種法則進(jìn)行頂點(diǎn)的最優(yōu)性判斷,不是最優(yōu)頂點(diǎn),是最優(yōu)頂點(diǎn),考察與當(dāng)前頂點(diǎn)相鄰的 “更好”的一個(gè)頂點(diǎn)，并置為當(dāng)前頂點(diǎn)。,根據(jù)某種法則進(jìn)行LP的無(wú)界或不可行判斷,無(wú)界或不可行,還不能做出判斷,求解結(jié)束,五、單純形表法,解：引進(jìn)松馳變量x3, x4，化為標(biāo)準(zhǔn)形得：,4=4（03+02）；3=3（02+03）,檢驗(yàn)數(shù),表中最后一行的所有檢驗(yàn)數(shù)均為非正數(shù)，表明目標(biāo)函數(shù)已達(dá)到最大值，上述表為最優(yōu)表。從表中可得到最優(yōu)解為X=（x1,x2,x3,x4）=（6，4，0，0），最優(yōu)值為Z=36,課堂練習(xí)：用

36、單純形方法求解線性規(guī)劃問(wèn)題 解：本題的目標(biāo)函數(shù)是求極小化的線性函數(shù)， 可以令 則 這兩個(gè)線性規(guī)劃問(wèn)題具有相同的可行域和最優(yōu)解， 只是目標(biāo)函數(shù)相差一個(gè)符號(hào)而已。,0 1 0 1 0,3,x2,2,0 0 1 2 -1,2,x3,0,-,0 1 0 1 0,3,x2,2,4/1,1 0 1 0 0,4,x3,0,3/1,0 1 0 1 0,3,x4,0,_,1 0 1 0 0,4,x3,0,0 0 0 0 -1,8,1 0 0 -2 1,2,x1,1,1 0 0 -2 0,6,2/1,1 0 0 -2 1,2,x5,0,1 2 0 0 0,0,8/2,1 2 0 0 1,8,x5,0,x1 x2

37、x3 x4 x5,b,XB,CB,1 2 0 0 0,C,最優(yōu)解最優(yōu)值,2/2,3/1,-,因?yàn)榉腔兞縳4的檢驗(yàn)數(shù)4=0，由無(wú)窮多最優(yōu)解判別定理，本例的線性規(guī)劃問(wèn)題存在無(wú)窮多最優(yōu)解。事實(shí)上若以x4為換入變量，以x3為換出變量，再進(jìn)行一次迭代，可得一下單純形表：,最優(yōu)解 最優(yōu)值 最優(yōu)解的一般表示式,對(duì)于極小化的線性規(guī)劃問(wèn)題的處理： 先化為標(biāo)準(zhǔn)型，即將極小化問(wèn)題變換為極大化問(wèn)題，然后利用單 純形方法求解。 直接利用單純形方法求解，但是檢驗(yàn)是否最優(yōu)的準(zhǔn)則有所不同， 即： 若某個(gè)基本可行解的所有非基變量對(duì)應(yīng)的檢驗(yàn)數(shù) （而不是）， 則基本可行解為最優(yōu)解 否則采用最大減少原則（而非最大增加原則）來(lái)確定換

38、入變量， 即： 若 則選取對(duì)應(yīng)的非基變量xm+k為換入變量 確定了換入變量以后，換出變量仍采用最小比值原則來(lái)確定。,2.5 大M法,基本思想：在約束條件中增加人工變量，同時(shí)修改目標(biāo)函數(shù)，對(duì)目標(biāo)函數(shù)加上具有很大正系數(shù)M的懲罰項(xiàng)，為使人工變量不影響目標(biāo)函數(shù)取值，在迭代過(guò)程中，應(yīng)把人工變量從基變量中退出，使其成為非基變量。,其中，M是很大的正數(shù)，同時(shí)增加兩個(gè)人工變量。,不容易找到初始可行解,大M法,大M法首先將線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型。如果約束方程組中包含有一個(gè)單位矩陣I，那么已經(jīng)得到了一個(gè)初始可行基。否則在約束方程組的左邊加上若干個(gè)非負(fù)的人工變量，使人工變量對(duì)應(yīng)的系數(shù)列向量與其它變量的系數(shù)列向量共同

39、構(gòu)成一個(gè)單位矩陣。以單位矩陣為初始基，即可求得一個(gè)初始的基本可行解。 為了求得原問(wèn)題的初始基本可行解，必須盡快通過(guò)迭代過(guò)程把人工變量從基變量中替換出來(lái)成為非基變量。為此可以在目標(biāo)函數(shù)中賦予人工變量一個(gè)絕對(duì)值很大的負(fù)系數(shù)-。這樣只要基變量中還存在人工變量，目標(biāo)函數(shù)就不可能實(shí)現(xiàn)極大化。 以后的計(jì)算與單純形表解法相同，只需認(rèn)定是一個(gè)很大的正數(shù)即可。假如在單純形最優(yōu)表的基變量中還包含人工變量，則說(shuō)明原問(wèn)題無(wú)可行解。否則最優(yōu)解中剔除人工變量的剩余部分即為原問(wèn)題的初始基本可行解。,例：用大M法求解下面的線性規(guī)劃問(wèn)題: 解： 首先將原問(wèn)題化為標(biāo)準(zhǔn)型 添加人工變量，并在目標(biāo)函數(shù)中分別賦予-,-,0 1 -1/

40、2 -1/2 0 1/2 1/2,3/2,X2,2,1 0 -1/2 1/2 0 1/2 -1/2,1/2,X1,-1,-,-1 1 0 -1 0 0 1,1,X2,2,1/2,2 0 -1 1 0 1 -1,1,X6,-M,1/1,-1 1 0 -1 0 0 1,1,X7,-M,2/1,1 1 -1 0 0 1 0,2,X6,-M,0 0 1/2 3/2 0 -1/2-M -3/2-M,5/2,0 0 1/2 1/2 1 -1/2 -1/2,3/2,X5,0,1+2M 0 -M 2+M 0 0 -2-2M,2-M,2/1,1 0 0 1 1 0 -1,2,X5,0,-1 2+2M -M -M

41、 0 0 0,-3M,3/1,0 1 0 0 1 0 0,3,X5,0,X1 x2 x3 x4 x5 x6 x7,b,XB,CB,-1 2 0 0 0 -M -M,C,0 1 0 0 1 0 0,3,X2,2,1 0 0 1 1 0 -1,2,X4,0,1 1 -1 0 0 1 0,2,X2,2,2 0 -1 1 0 1 -1,1,X4,0,-,0 1 -1/2 -1/2 0 1/2 1/2,3/2,X2,2,1/2/1/2,1 0 -1/2 1/2 0 1/2 -1/2,1/2,X1,-1,-1 0 0 0 -2 -M -M,6,Z,-1 0 1 0 1 -1 0,1,X3,0,-3 0 2

42、 0 0 -2-M -M,4,Z,-1 0 1 0 1 -1 0,1,X5,0,0 0 1/2 3/2 0 -1/2-M -3/2-M,5/2,Z,3/2 /1/2,0 0 1/2 1/2 1 -1/2 -1/2,3/2,X5,0,X1 x2 x3 x4 x5 x6 x7,b,XB,CB,-1 2 0 0 0 -M -M,C,最優(yōu)解 最優(yōu)值,2.6 兩階段法,兩階段法引入人工變量的目的和原則與大M法相同，所不同的是處理人工變量的方法。 兩階段法的步驟： 求解一個(gè)輔助線性規(guī)劃。目標(biāo)函數(shù)取所有人工變量之和，并取極小化；約束條件為原問(wèn)題中引入人工變量后包含一個(gè)單位矩陣的標(biāo)準(zhǔn)型的約束條件。 如果輔助線

43、性規(guī)劃存在一個(gè)基本可行解，使目標(biāo)函數(shù)的最小值等于零，則所有人工變量都已經(jīng)“離基”。表明原問(wèn)題已經(jīng)得了一個(gè)初始的基本可行解，可轉(zhuǎn)入第二階段繼續(xù)計(jì)算；否則說(shuō)明原問(wèn)題沒(méi)有可行解，可停止計(jì)算。 求原問(wèn)題的最優(yōu)解。在第一階段已求得原問(wèn)題的一個(gè)初始基本可行解的基礎(chǔ)上，繼續(xù)用單純形法求原問(wèn)題的最優(yōu)解,例：用兩階段法求上例中的線性規(guī)劃問(wèn)題。 解：首先將問(wèn)題化為標(biāo)準(zhǔn)型 添加人工變量x6,x7,并建立輔助線性規(guī)劃如下：,由于輔助線性規(guī)劃的目標(biāo)函數(shù)是極小化，因此最優(yōu)解的判別準(zhǔn)則應(yīng)為：,0 1 -1/2 -1/2 0 1/2 1/2,3/2,X2,0,1 0 -1/2 1/2 0 1/2 -1/2,1/2,X1,0,

44、-,-1 1 0 -1 0 0 1,1,X2,0,1/2,2 0 -1 1 0 1 -1,1,X6,1,1/1,-1 1 0 -1 0 0 1,1,X7,1,2/1,1 1 -1 0 0 1 0,2,X6,1,0 0 0 0 0 1 1,0,0 0 1/2 1/2 1 -1/2 -1/2,3/2,X5,0,-2 0 1 -1 0 0 2,1,2/1,1 0 0 1 1 0 -1,2,X5,0,0 -2 1 1 0 0 0,3,3/1,0 1 0 0 1 0 0,3,X5,0,x1 x2 x3 x4 x5 x6 x7,b,XB,CB,0 0 0 0 0 1 1,C,輔助規(guī)劃所有檢驗(yàn)數(shù)：,原問(wèn)題已

45、得一個(gè)初始基本可行解，,由上表可知，通過(guò)若干次旋轉(zhuǎn)變換，原問(wèn)題的約束方程組已變換成包含一個(gè)單位矩陣的約束方程組 該約束方程組可作為第二階段初始約束方程組，將目標(biāo)函數(shù)則還原成原問(wèn)題的目標(biāo)函數(shù)，可繼續(xù)利用單純形表求解。,-1 0 0 0 -2,6,1 0 0 1 1 0 1 0 0 1 -1 0 1 0 1,2 3 1,X4 X2 X3,0 2 0,-3 0 2 0 0,4,2 0 -1 1 0 1 1 -1 0 0 -1 0 1 0 1,1 2 1,X4 X2 X5,0 2 0,0 0 1/2 3/2 0,5/2,1/2/1/2 - 3/2/1/2,1 0 -1/2 1/2 0 0 1 -1/2

46、 -1/2 0 0 0 1/2 1/2 1,1/2 3/2 3/2,X1 X2 X5,-1 2 0,x1 x2 x3 x4 x5,b,XB,CB,-1 2 0 0 0,C,可得最優(yōu)解 ，目標(biāo)函數(shù)值maxZ=6， 與用大M法的結(jié)果完全相同。,2.7單純形表與線性規(guī)劃問(wèn)題的討論,一、無(wú)可行解,通過(guò)大法或兩階段法求初始的基本可行解。但是如果在大法的最優(yōu)單純形表的基變量中仍含有人工變量，或者兩階段法的輔助線性規(guī)劃的目標(biāo)函數(shù)的極小值大于零，那么該線性規(guī)劃就不存在可行解。 人工變量的值不能取零，說(shuō)明了原線性規(guī)劃的數(shù)學(xué)模型的約束條件出現(xiàn)了相互矛盾的約束方程。此時(shí)線性規(guī)劃問(wèn)題的可行域?yàn)榭占?例：求解下列線性規(guī)劃問(wèn)題 解： 首先將問(wèn)題化為標(biāo)準(zhǔn)型 令，則,故引入人工變量， 并利用大M法求解,C,-3 -2 -1 0 0 0 -M -M,CB,XB,b,x1 x2 x3 x4 x5 x6 x7 x8,0 -M -M,x4 x7 x8,6 4 3,1 1 1 1 0 0 0 0 1 0 -1 0 -1