第五章單純形法一、問題的提出二、單純形法的基本思路和原理三、單純形法的表格形式四、人工變量法五、幾種特殊情況1編輯版pppt第五章單純形法一、問題的提出1編輯版pppt一、問題的提出圖解法只能解決二維的線性規劃問題，那更多變量的問題怎么辦？(jsj)通過代數算法搜尋最優解。單純形法，就是這樣的一種代數搜尋法。線性規劃問題的解一般有無窮多個，如果不縮小搜尋范圍，工作量太大！我們首先將最優解縮小在一個有限的范圍。2編輯版pppt一、問題的提出圖解法只能解決二維的線性規劃問題，那更多變量的一、問題的提出回顧圖解法，我們知道：最優解必定在可行域的頂點上取得，而頂點的個數總是有限的。多維線性規劃問題的可行域也存在有限個頂點。如果能夠從一個頂點開始，通過某種方式向更優頂點轉移，總會找到最優點。首先面臨的問題：如何通過代數方法找到第一個頂點？3編輯版pppt一、問題的提出回顧圖解法，我們知道：最優解必定在可行域的頂點一、問題的提出圖解法中的例1.5模型為：Maxz=50x1+100x2

s.t.1·x1+1·x2≤300

2·x1+1·x2≤400

0·x1+1·x2≤250

x1≥0，x2≥04編輯版pppt一、問題的提出圖解法中的例1.5模型為：4編輯版pppt一、問題的提出從其標準形的解向量開始研究：Maxz=50x1+100x2

s.t.1·x1+1·x2+1·x3+0·x4+0·x5＝300

2·x1+1·x2+0·x3+1·x4+0·x5＝400

0·x1+1·x2+0·x3+0·x4+1·x5＝250

xj≥0(j=1,2,3,4,5)5編輯版pppt一、問題的提出從其標準形的解向量開始研究：5編輯版pppt一、問題的提出頂點對應的解向量有何代數特征？O(0,0,300,400,250)A(0,250,50,150,0)B(50,250,0,50,0)C(100,200,0,0,50)D(200,0,100,0,50)答案：都有兩個變量取值為0，且非負。X1X2O(0,0)A(0,250)B(50,250)C(100,200)D(200,0)6編輯版pppt一、問題的提出頂點對應的解向量有何代數特征？X1X2O(0,一、問題的提出既然頂點解向量中有兩個變量取值為0，而標準形中又有三個約束方程，是否可以直接通過這種方式找頂點？如令x1＝0，x2＝0，則x3＝300，x4＝400，x5＝250可得到解（0，0，300，400，250）7編輯版pppt一、問題的提出既然頂點解向量中有兩個變量取值為0，而標準形中一、問題的提出又如：令x3＝0，x5＝0，由約束條件：x1+x2+x3＝3002x1+x2+x4＝400x2+x5＝250可得到解（50，250，0，50，0）8編輯版pppt一、問題的提出又如：令x3＝0，x5＝0，8編輯版pppt一、問題的提出若令x2＝0，x5＝0，會怎樣？由約束方程可知：x1+x2+x3＝300→x1+x3＝3002x1+x2+x4＝400→2x1+x4＝400x2+x5＝250→0＝250？顯然不能得到相應的解。9編輯版pppt一、問題的提出若令x2＝0，x5＝0，會怎樣？9編輯版ppp一、問題的提出為什么令x2＝0，x5＝0時不能得到解？因為其余三個變量的系數列向量為該矩陣是非可逆矩陣，即去掉x2和x5后的三個約束方程線性相關，這種情況下得不到解。10編輯版pppt一、問題的提出為什么令x2＝0，x5＝0時不能得到解？10編一、問題的提出既然如此，如果我們在技術矩陣中取出三列，組成一個可逆陣，令其余兩列對應的變量為零，則一定可以得到一個解。11編輯版pppt一、問題的提出既然如此，如果我們在技術矩陣中取出三列，組成一一、問題的提出如，取1、2、3列得到：此矩陣為可逆陣，故令x4＝0，x5＝0，一定可以得到一個解。對應的解為（75，250，-25，0，0）。12編輯版pppt一、問題的提出如，取1、2、3列得到：12編輯版pppt一、問題的提出基的概念：已知A是約束條件的m×n階系數矩陣，其秩為m。設B是A矩陣中的一個非奇異（可逆）的m×m階子矩陣，則稱B為線性規劃問題的一個基。B由A中的m個線性無關列向量組成。13編輯版pppt一、問題的提出基的概念：13編輯版pppt一、問題的提出一個基對應一組概念：非基變量基變量基向量非基向量對應基本解：（0，0，300，400，250）14編輯版pppt一、問題的提出一個基對應一組概念：非基變量基變量基向量非基向一、問題的提出(0,0,300,400,250)(0,300,0,100,-50)(0,400,-100,0,150)(0,250,50,150,0)(300,0,0,-200,-50)(200,0,100,0,50)不存在(100,200,0,0,50)(50,250,0,50,0)(75,250,-25,0,0)基本解是x3,x5p3,p5x1,x2,x4p1,p2,p4B2=(p1,p2,p4)是x3,x4p3,p4x1,x2,x5p1,p2,p5B3=(p1,p2,p5)是x1,x2p1,p2x3,x4,x5p3,p4,p5B10=(p3,p4,p5)否x1,x3p1,p3x2,x4,x5p2,p4,p5B9=(p2,p4,p5)否x1,x4p1,p4x2,x3,x5p2,p3,p5B8=(p2,p3,p5)是x1,x5p1,p5x2,x3,x4p2,p3,p4B7=(p2,p3,p4)否x2,x3p2,p3x1,x4,x5p1,p4,p5B6=(p1,p4,p5)是x2,x4p2,p4x1,x3,x5p1,p3,p5B5=(p1,p3,p5)x2,x5p2,p5x1,x3,x4p1,p3,p4B4=(p1,p3,p4)否x4,x5p4,p5x1,x2,x3p1,p2,p3B1=(p1,p2,p3)是否可行非基變量非基向量基變量基向量基15編輯版pppt一、問題的提出(0,0,300,400,250)(0,300一、問題的提出基本解可能可行，也可能不可行。滿足非負約束條件的基本解叫基本可行解，相應的基稱為可行基。否則為非可行基。16編輯版pppt一、問題的提出基本解可能可行，也可能不可行。16編輯版ppp一、問題的提出A：(0,250,50,150,0)B：(50,250,0,50,0)C：(100,200,0,0,50)D：(200,0,100,0,50)O：(0,0,300,400,250)E：(75,250,-25,0,0)F：(0,300,0,100,-50)G：(0,400,-100,0,150)H：(300,0,0,-200,-50)X1X2O(0,0)A(0,250)B(50,250)C(100,200)D(200,0)G(0,400)E(75,250)F(0,300)H(300,0)①③②17編輯版pppt一、問題的提出A：(0,250,50,150,0)X1X2O一、問題的提出線性規劃解的集合關系：基本解最優解基本可行解可行解18編輯版pppt一、問題的提出線性規劃解的集合關系：基本解最優解基本可行解可一、問題的提出顯然，將搜索范圍控制在基本可行解內，將大大減少搜索工作量。但是，即使取得一個基，得到的解還不一定可行。如何才能保證取得一個可行基呢？19編輯版pppt一、問題的提出顯然，將搜索范圍控制在基本可行解內，將大大減少一、問題的提出總結：1、可行域頂點對應的解必為基本可行解：有n-m個變量取值為0，滿足非負條件。2、一個基對應一組基本解，可能可行，也可能不可行；3、最優解必定在基本可行解中；20編輯版pppt一、問題的提出總結：20編輯版pppt二、單純形法的基本思路和原理單純形法的基本思路：首先找到一個頂點；然后判斷它是否最優；如果不是，則通過更換頂點的方式找到更優的頂點；直到找到最優頂點。21編輯版pppt二、單純形法的基本思路和原理單純形法的基本思路：21編輯版p二、單純形法的基本思路和原理第一步：找到一個頂點（初始基本可行解）22編輯版pppt二、單純形法的基本思路和原理22編輯版pppt二、單純形法的基本思路和原理思考：1、令n-m個變量為0（非基變量）是否一定可以找到？答案：不一定。如例中x2＝0，x5＝0時不能得到解。可行的辦法：找到一個基。23編輯版pppt二、單純形法的基本思路和原理思考：23編輯版pppt二、單純形法的基本思路和原理2、一個基是否一定對應可行域頂點？答案：不一定。必須是可行基。一般來說，判斷一個基是否是可行基，需要在求出其基本解后才能判斷。24編輯版pppt二、單純形法的基本思路和原理2、一個基是否一定對應可行域頂點二、單純形法的基本思路和原理3、那有沒有辦法在求出解之前保證我們取得的基為可行基？解決辦法：保證右端項非負，找到一個單位矩陣，必定是一個可行基。25編輯版pppt二、單純形法的基本思路和原理3、那有沒有辦法在求出解之前保證二、單純形法的基本思路和原理如范例系數陣：存在3階單位陣（初始可行基）右端項非負26編輯版pppt二、單純形法的基本思路和原理如范例系數陣：存在3階單位陣（初二、單純形法的基本思路和原理基本可行解為（0，0，300，400，250）此可行基稱為初始可行基。對應的解稱為初始基本可行解。初始基本可行解在上頁矩陣中一目了然。27編輯版pppt二、單純形法的基本思路和原理基本可行解為（0，0，300，4二、單純形法的基本思路和原理第二步：最優性檢驗28編輯版pppt二、單純形法的基本思路和原理28編輯版pppt二、單純形法的基本思路和原理對應于每一組基本解，目標函數都可以表示成非基變量的函數，稱為典式。如：初始基本可行解（0，0，300，400，250）其非基變量為x1，x2目標函數為Maxz=50x1+100x229編輯版pppt二、單純形法的基本思路和原理對應于每一組基本解，目標函數都可二、單純形法的基本思路和原理典式Z=50x1+100x2如果x1增加1，Z會怎樣？答案：Z增加50。如果x2的值增加1，Z會怎樣？答案：Z增加100。30編輯版pppt二、單純形法的基本思路和原理典式Z=50x1+100x2二、單純形法的基本思路和原理x1，x2的取值是否有增加的可能？分析：該解中非基變量x1，x2的取值為0，其值完全有可能增加。說明此時目標函數值還有增加的可能，沒有達到最優。31編輯版pppt二、單純形法的基本思路和原理x1，x2的取值是否有增加的可能二、單純形法的基本思路和原理再如：基本解（50，250，0，50，0）其非基變量為x3，x5由約束方程可得：x1＝50-x3+x5x2＝250-x5目標函數為Maxz=50x1+100x2＝27500-50x3-50x532編輯版pppt二、單純形法的基本思路和原理再如：基本解（50，250，0，二、單純形法的基本思路和原理典式Z=27500-50x3-50x5如果x3增加1，Z會怎樣？答案：Z減少50。如果x5的值增加1，Z會怎樣？答案：Z減少50。可見要使Z增加，只有使x3和x5減少。33編輯版pppt二、單純形法的基本思路和原理典式Z=27500-50x3-二、單純形法的基本思路和原理x3，x5的取值是否有減少的可能？分析：該解中非基變量x1，x2的取值為0，其值不可能再減少。所以Z值不可能再增加。說明此基本解對應的目標函數值已經達到最優。34編輯版pppt二、單純形法的基本思路和原理x3，x5的取值是否有減少的可能二、單純形法的基本思路和原理由以上分析，可見，完全可以由典式中的系數來判斷解是否最優。如：Z=50x1+100x2系數>0，未達到最優；Z=27500-50x3-50x5系數<0，達到最優。這些系數我們稱為檢驗數。35編輯版pppt二、單純形法的基本思路和原理由以上分析，可見，完全可以由典式二、單純形法的基本思路和原理檢驗數的概念：若只用非基變量來表示目標函數，將所有基變量從目標函數中用非基變量替換出去。此時目標函數中各非基變量的系數即為各非基變量的檢驗數，把變量xj的檢驗數記為j。顯然基變量的檢驗數為0。36編輯版pppt二、單純形法的基本思路和原理檢驗數的概念：36編輯版pppt二、單純形法的基本思路和原理最優解判別準則：對于求最大目標函數的問題中，對于某個基本可行解，若所有檢驗數j≤0，則這個基本可行解是最優解。對于求最小目標函數的情況，當所有非基變量檢驗數j≥0時，目標值最優，對應的基本可行解為最優解。37編輯版pppt二、單純形法的基本思路和原理最優解判別準則：37編輯版ppp二、單純形法的基本思路和原理第三步：基變換38編輯版pppt二、單純形法的基本思路和原理38編輯版pppt二、單純形法的基本思路和原理在保證右端常數項非負前提下，基變量與非基變量互換（換基），使檢驗數由正（非最優）變為非正（最優）。為了換基，就要合理的確定進基變量和出基變量。39編輯版pppt二、單純形法的基本思路和原理在保證右端常數項非負前提下，基變二、單純形法的基本思路和原理進基變量的確定：最大檢驗數原則，確保目標值增加最快。例中初始解1＝50，2＝100，則選x2入基。40編輯版pppt二、單純形法的基本思路和原理進基變量的確定：40編輯版ppp二、單純形法的基本思路和原理出基變量的確定：最小比值原則min{300/1，400/1，250/1}=250，x5出基以進基變量系數列中的正數為分母，以相應的方程右端常數為分子,系數為0和負不考慮。41編輯版pppt二、單純形法的基本思路和原理出基變量的確定：最小比值原則以進二、單純形法的基本思路和原理范例中，確定了x2為入基變量后，把約束方程1·x1+1·x2+1·x3+0·x4+0·x5＝300

2·x1+1·x2+0·x3+1·x4+0·x5＝400

0·x1+1·x2+0·x3+0·x4+1·x5＝250

中入基變量x2的正系數除以對應的右端常數，得b1/a12=300/1=300b2/a22=400/1=400b3/a32=250/1=250其中b3/a32的值最小，故確定原基變量中第三個約束方程中的基變量x5為出基變量。42編輯版pppt二、單純形法的基本思路和原理范例中，確定了x2為入基變量后，二、單純形法的基本思路和原理得到新的基(p2，p3，p4)，令x1＝x5＝0，得x2

+x3

=300x2+x4

=400x2

=250求得新的基本可行解（0,250,50,150,0),目標函數值z＝50x1+100x2=50×0+100×250＝25000目標函數值得到了改進。43編輯版pppt二、單純形法的基本思路和原理得到新的基(p2，p3，p4思考：若不按最小比值法確定出基變量會怎么樣？請大家計算一下：若在第一次迭代中不選x5出基，而讓x3或x4出基，會出現什么情況。44編輯版pppt思考：若不按最小比值法確定出基變量會怎么樣？請大家計算一下：二、單純形法的基本思路和原理若讓x3出基，則新的基為(p2，p4，p5)，求得解為(0,300,0,100,-50)，非可行。若讓x4出基，則新的基為(p2，p3，p5)，求得解為(0,400,-100,0,150)，非可行。結論：按最小比值原則確定出基變量，可確保解可行。45編輯版pppt二、單純形法的基本思路和原理若讓x3出基，則新的基為(p2二、單純形法的基本思路和原理事實上，若取得的基不是單位陣，也可以通過初等行變換，將其化為單位陣。如基（p1,p2,p4）：②-2×①46編輯版pppt二、單純形法的基本思路和原理事實上，若取得的基不是單位陣，也二、單純形法的基本思路和原理①-③②+③顯然，該基本解為：（50，250，0，50，0）47編輯版pppt二、單純形法的基本思路和原理①-③②+③顯然，該基本二、單純形法的基本思路和原理如此迭代直到所有檢驗數均非正，則找到了線性規劃問題的最優解。48編輯版pppt二、單純形法的基本思路和原理48編輯版pppt二、單純形法的基本思路和原理單純形法求解思路總結：第一步找到初始可行基（單位陣）；第二步檢驗解是否為最優（所有檢驗數≤0）；第三步基變換（最大檢驗數原則確定進基變量，最小比值原則確定出基變量）。重復以上步驟直到得到最優解。49編輯版pppt二、單純形法的基本思路和原理單純形法求解思路總結：49編輯版三、單純形法的表格形式0Z=000010050j=cj－zj00000zj250/10x5400/10x4300/10x3比值bi/ai225010010400010123000011100010050bx5x4x3x2x1CB基變量XB迭代次數單純形表的基本結構，以范例的初始表為例：50編輯版pppt三、單純形法的表格形式0Z=000010050j=cj－z三、單純形法的表格形式表格形式可以使求解過程更簡潔明了。但需要先從一般數學模型里推導出檢驗數的表達式和每個解對應的目標函數值。下面以例說明檢驗數和目標函數值公式的推導過程：51編輯版pppt三、單純形法的表格形式表格形式可以使求解過程更簡潔明了。51三、單純形法的表格形式將范例線性規劃模型表示為maxZ＝c1x1+c2x2+c3x3+c4x4+c5x5假設基變量為x1、x2、x3，基為單位矩陣，則約束條件可以表示為x1+a’14x4+a’15x5=b’1x2+a’24x4+a’25x5=b’2x3+a’34x4+a’35x5=b’352編輯版pppt三、單純形法的表格形式將范例線性規劃模型表示為52編輯版pp三、單純形法的表格形式則Z＝(c1b’1+c2b’2+c3b’3)+(c4-c1a’14-c2a’24-c3a’34)x4+(c5-c1a’15-c2a’25-c3a’35)x5基本解對應的目標值為(c1b’1+c2b’2+c3b’3)；檢驗數1＝2＝3＝0，4＝c4-c1a’14-c2a’24-c3a’34＝

c4-(c1a’14+c2a’24+c3a’34)5＝c5-c1a’15-c2a’25-c3a’35＝c5-(c1a’15+c2a’25+c3a’35)53編輯版pppt三、單純形法的表格形式則Z＝(c1b’1+c2b’2+c3三、單純形法的表格形式檢驗數的一般表達式為：j＝cj－zj其中zj＝（c1a’1j+c2a’2j+…+cma’mj）每個解對應的目標函數值：z＝c1b1+c2b2+…+cmbm非基變量xj的目標函數系數第一個約束方程中基變量的目標函數系數第一個約束方程中非基變量xj的技術系數54編輯版pppt三、單純形法的表格形式非基變量xj的目標函數系數第一個約束方三、單純形法的表格形式觀察系數矩陣和基變量的目標函數系數：找到規律，計算檢驗數變得更直觀。55編輯版pppt三、單純形法的表格形式觀察系數矩陣和基變量的目標函數系數：5三、單純形法的表格形式對于范例，其系數矩陣和基變量的目標函數系數：故目標函數值Z＝0×300+0×400+0×250；z1＝0×1+0×2+0×0，1＝

c1－z1＝50-0；……56編輯版pppt三、單純形法的表格形式對于范例，其系數矩陣和基變量的目標函數三、單純形法的表格形式0Z=000010050j=cj－zj00000zj250/10x5400/10x4300/10x3比值bi/ai225010010400010123000011100010050bx5x4x3x2x1CB基變量XB迭代次數主元迭代：將主列變為單位列向量。辦法：在其它行上加上主行的若干倍，使主元變為1，主列其它元素變為0。最大檢驗數最小比值57編輯版pppt三、單純形法的表格形式0Z=000010050j=cj－z三、單純形法的表格形式1-10000050j=cj－zj25000100001000zj_25010010100x2150/2150-110020x450/150-101010x300010050比值bi/ai2bx5x4x3x2x1CB基變量XB迭代次數檢驗數還有正數，故還需進一步迭代。58編輯版pppt三、單純形法的表格形式1-10000050j=cj－zj2三、單純形法的表格形式2-500-5000j=cj－zj275005005010050zj25010010100x25011-2000x450-1010150x100010050比值bi/ai2bx5x4x3x2x1CB基變量XB迭代次數所有檢驗數均非正，已求得最優解。59編輯版pppt三、單純形法的表格形式2-500-5000j=cj－zj2三、單純形法的表格形式課堂練習用單純形法求解：第五章習題，第5題（1）60編輯版pppt三、單純形法的表格形式課堂練習60編輯版pppt三、單純形法的表格形式

0005812j

0000000Zj44810014120x611110101110x520/3200011230x400005812比值bx6x5x4x3x2x1cBxB迭代次數61編輯版pppt三、單純形法的表格形式0005812j0000000三、單純形法的表格形式

-100440

j

481001412Zj1241/12001/121/3112x121/27-1/121011/122/300x588-1/4013/4100x410005812比值bx6x5x4x3x2x1cBxB迭代次數62編輯版pppt三、單純形法的表格形式-100440j481001三、單純形法的表格形式

00-4100

j

800044812Zj---4/31/60-1/3-1/60112x145/31/121-2/35/12000x532/38-1/4013/4108x220005812比值bx6x5x4x3x2x1cBxB迭代次數63編輯版pppt三、單純形法的表格形式00-4100j800044三、單純形法的表格形式

-1/5-12/5-12/5000

j

841/512/512/55812Zj21/52/5-3/500112x141/512/5-8/51005x35-2/5-9/511/50108x230005812比值bx6x5x4x3x2x1cBxB迭代次數64編輯版pppt三、單純形法的表格形式-1/5-12/5-12/5000四、人工變量法例：LP問題的標準型Maxz=5x1+2x2+3x3-x4s.t.x1+2x2+3x3=152x1+x2+5x3=20x1+2x2+4x3+x4=26x1,x2,x3,x4≥0問題：如何找到初始可行基？65編輯版pppt四、人工變量法例：LP問題的標準型65編輯版pppt四、人工變量法解決辦法：構造初始可行基引入x5、x6人工變量66編輯版pppt四、人工變量法解決辦法：構造初始可行基引入x5、x6人工變量四、人工變量法實際上，構造問題的約束條件為：s.t.x1+2x2+3x3+x5=152x1+x2+5x3+x6=20x1+2x2+4x3+x4=26x1,x2,x3,x4,x5,x6≥067編輯版pppt四、人工變量法實際上，構造問題的約束條件為：67編輯版ppp四、人工變量法構造初始基為（p4，p5，p6）；非基變量為x1，x2，x3；初始解為（0，0，0，26，15，20）出現新的問題：（0，0，0，26）是否是原問題的解？68編輯版pppt四、人工變量法構造初始基為（p4，p5，p6）；68編輯四、人工變量法顯然，原問題的約束方程和構造問題的約束方程一般情況下不同解。只有一種情況下，兩者同解：人工變量都為0時。事實上，不管中間過程如何，只要構造問題的最優解中人工變量為0，該最優解也就是原問題的最優解。69編輯版pppt四、人工變量法顯然，原問題的約束方程和構造問題的約束方程一般四、人工變量法為迫使構造問題的最優解中人工變量為0，將其目標函數表示為：Maxz=5x1+2x2+3x3-x4-Mx5-Mx6罰因子（M為足夠大的正數）70編輯版pppt四、人工變量法為迫使構造問題的最優解中人工變量為0，將其目標四、人工變量法此法稱為“大M法”。大M法求解實例：71編輯版pppt四、人工變量法71編輯版pppt四、人工變量法0008M+73M+43M+6j-35M-26-M-M-1-8M-4-3M-2-3M-1Zj6.526001421-1x4420100512-Mx6515010321-Mx50-M-M-1325比值bx6x5x4x3x2x1cBxB迭代次數72編輯版pppt四、人工變量法0008M+73M+43M+6j-35M-2四、人工變量法-8M/5-7/50007M/5+13/5-M/5+16/5j-3M+23M/5+7/5-M-13-7M/5-3/5M/5+9/5Zj25/310-4/50106/5-3/5-1x42041/50011/52/53x315/73-3/51007/5-1/5-Mx51-M-M-1325比值bx6x5x4x3x2x1cBxB迭代次數73編輯版pppt四、人工變量法-8M/5-7/50007M/5+13/5-M四、人工變量法-M-2/7-M-13/700025/7j53/72/713/7-13210/7Zj----52/7-2/7-6/7100-3/7-1x425/325/72/7-1/70103/73x3----15/7-3/75/7001-1/72x22-M-M-1325比值bx6x5x4x3x2x1cBxB迭代次數74編輯版pppt四、人工變量法-M-2/7-M-13/700025/7j5四、人工變量法-M+8/3-M-2/30-25/300j112/3-8/32/3-134/325Zj110-11100-1x425/32/3-1/307/3015x110/3-1/32/301/3102x23-M-M-1325比值bx6x5x4x3x2x1cBxB迭代次數75編輯版pppt四、人工變量法-M+8/3-M-2/30-25/300j四、人工變量法原問題最優解：(25/3，10/3，0，11)最優目標值：112/3若人工變量在罰因子的作用下最終不能出基，即構造問題的最優解中人工變量取值不為0，則原問題無可行解。76編輯版pppt四、人工變量法原問題最優解：(25/3，10/3，0，11)四、人工變量法罰因子的引入，使計算變得復雜。在構造初始基后，還有一種求解辦法——兩階段法。第一階段，使人工變量出基，找到一個原問題的可行解；第二階段，從找到的可行解繼續原問題的迭代，找到最優解。77編輯版pppt四、人工變量法罰因子的引入，使計算變得復雜。77編輯版ppp四、人工變量法如上例，構造第一階段的目標函數：Maxz=-x5-x6約束條件同樣為s.t.x1+2x2+3x3+x5=15

2x1+x2+5x3+x6=20

x1+2x2+4x3+x4=26

x1,x2,x3,x4,x5,x6≥078編輯版pppt四、人工變量法如上例，構造第一階段的目標函數：78編輯版pp四、人工變量法迭代次數xBcBx1x2x3x4x5x6b比值0000-1-10x5-1123010155x6-1215001204x40124100266.5Zj-3-3-80-1-1-35j338000解第一階段問題：79編輯版pppt四、人工變量法迭代次數xBcBx1x2x3x4x5x6b比值四、人工變量法迭代次數xBcBx1x2x3x4x5x6b比值0000-1-11x5-1-1/57/5001-3/5315/7x302/51/51001/5420x40-3/56/5010-4/51025/3Zj1/5-7/500-13/5-3j-1/57/5000-8/580編輯版pppt四、人工變量法迭代次數xBcBx1x2x3x4x5x6b比值四、人工變量法迭代次數xBcBx1x2x3x4x5x6b比值0000-1-12x20-1/71005/7-3/715/7－x303/7010-1/72/725/725/3x40-3/7001-6/7-2/752/7－Zj0000000j0000-1-1得到原問題的一個基本可行解：(0,15/7,25/7,52/7)81編輯版pppt四、人工變量法迭代次數xBcBx1x2x3x4x5x6b比值四、人工變量法迭代次數xBcBx1x2x3x4b比值523-10x22-1/710015/7－x333/701025/725/3x4-1-3/700152/7－Zj10/723-153/7j25/7000第二階段：把基本可行解填入表中82編輯版pppt四、人工變量法迭代次數xBcBx1x2x3x4b比值523-四、人工變量法迭代次數xBcBx1x2x3x4b比值523-11x22011/3010/3－x15107/3025/325/3x4-1001111－Zj5234/3-1112/3j00-25/30故最優解：(25/3，10/3，0，11)；最優值：112/3。83編輯版pppt四、人工變量法迭代次數xBcBx1x2x3x4b比值523-課堂練習：

第98頁第6題，用大M法或兩階段法求解。迭代次數基變量XBCBx1x2x3x4x5x6b比值bi/ai251300-M0x6-M142-101100.4x501-2101016－－zj=∑ciaij-M-4M-2MM0-M-10Mcj－zj5+M1+4M3+2M-M0084編輯版pppt課堂練習：

第98頁第6題，用大M法或兩階段法求解。迭代次數2x15142-10110－－x500-6-111-166zj=∑ciaij52010-505Z=50cj－zj0-19-750-M-5迭代次數基變量XBCBx1x2x3x4x5x6b比值bi/ai251300-M1x210.2510.5-0.2500.252.510x501.502-0.510.52114zj=∑ciaij0.2510.5-0.2500.25Z＝2.5cj－zj4.7502.50.250-M-0.2585編輯版pppt2x15142-10110－－x500-6-111-166z迭代次數基變量XBCBx1x2x3x4x5x6b比值bi/ai251300-M3x151-2301016x400-6-111-16zj=∑ciaij5-1015050Z=80cj－zj09-700-M找得到進基變量，卻找不到出基變量，此為無界解情況。86編輯版pppt迭代次數基變量XBCBx1x2x3x4x5x6b比值bi/a五、幾種特殊情況1、無可行解若LP問題的最終解里有人工變量大于0，則此LP問題無可行解。例如，某LP問題經兩次迭代，得到如下單純形表：87編輯版pppt五、幾種特殊情況1、無可行解87編輯版pppt五、幾種特殊情況迭代次數基變量XBCBx1x2s1s2s3a1b比值bi/ai22030000-M2x230011/10-3/100016s2010010030a1-M00-1/10-7/10-114zj20303+M/1011+7M/10M-M780-4Mcj－zj00-3-M/10-11-7M/10-M088編輯版pppt五、幾種特殊情況迭代次數基變量XBCBx1x2s1s2s3a五、幾種特殊情況表中所有檢驗數都小于或等于零，可見目標函數值不可能再增加。但此時人工變量a1沒有出基，其取值為4。故原線性規劃問題無可行解。89編輯版pppt五、幾種特殊情況89編輯版pppt五、幾種特殊情況2、無界解在某次迭代中，若存在一個大于0的檢驗數j，而該列的系數aij（i＝1，2，……m）都小于或等于0，則此線性規劃問題無界。90編輯版pppt五、幾種特殊情況2、無界解90編輯版pppt五、幾種特殊情況迭代次數基變量XBCBx1x2s1s2b比值bi/ai211001x111-1101s200-1319zj1-1101cj-

zj02-10只有x2的檢驗數大于0，但ai2均小于0，此線性規劃問題為無界解情況。91編輯版pppt五、幾種特殊情況迭代次數基變量XBCBx1x2s1s2b比值五、幾種特殊情況3、無窮多最優解一般情況下，達到最優時，基變量的檢驗數等于0，非基變量的檢驗數小于0。如果最優表中，有非基變量的檢驗數等于零，則有無窮多最優解。例如：92編輯版pppt五、幾種特殊情況3、無窮多最優解92編輯版pppt五、幾種特殊情況200-5000j=cj－zj15000005010050zj2501001050x25011-2000x450-1010150x10005050比值bi/ai2bx5x4x3x2x1CB基變量XB迭代次數已最優。但非基變量x5的檢驗數為0。可以判斷此LP問題有無窮多最優解。93編輯版pppt五、幾種特殊情況200-5000j=cj－zj150000五、幾種特殊情況將檢驗數為0的非基變量x5選為入基變量進行迭代，可得另一個最優解：迭代次數基變量XBCBx1x2x3x4x5b比值bi/ai250500003x15010-110100x5000-21150x250012-10200zj5050500015000cj-

zj00-500094編輯版pppt五、幾種特殊情況將檢驗數為0的非基變量x5選為入基變量進行迭五、幾種特殊情況第一組最優解X1＝(50，250，0，50，0)第二組最優解X2＝

(100，200，0，0，50)事實上，其余的最優解都可以表示為X1和X2的線性組合：aX1+(1－a)X2，其中0≤a≤1。最優值為15000。95編輯版pppt五、幾種特殊情況第一組最優解X1＝(50，250，0，50，五、幾種特殊情況4、進基變量的相持及其突破單純形法中進基變量的確定是以“最大檢驗數原則”。如果兩個或者多個檢驗數同時最大，應該選擇哪個變量進基？解決辦法：選擇下標最小者。96編輯版pppt五、幾種特殊情況4、進基變量的相持及其突破96編輯版pppt五、幾種特殊情況

-100440

j

481001412Zj1241/12001/121/3112x121/27-1/121011/122/300x588-1/4013/4100x410005812比值bx6x5x4x3x2x1cBxB迭代次數選擇下標小的變量x2進基。97編輯版pppt五、幾種特殊情況-100440j481001412五、幾種特殊情況5、出基變量的相持和退化問題單純形法中出基變量的確定是以“最小比值原則”。如果兩個或者多個比值同時最小，應該選擇哪個變量出基？如下表：98編輯版pppt五、幾種特殊情況5、出基變量的相持和退化問題98編輯版ppp五、幾種特殊情況迭代次數基變量XBCBx1x2x3s1s2s3b比值bi/ai2203/20000s101-1010022s2020101042s3011100133zj0000000cj-

zj203/2000若在兩者中選擇s2出基。99編輯版pppt五、幾種特殊情況迭代次數基變量XBCBx1x2x3s1s2s五、幾種特殊情況迭代次數基變量XBCBx1x2x3s1s2s3b比值bi/ai2203/20001s100-1-1/21-1/200----x12101/201/2024s30011/20-1/2112zj2010104cj-

zj001/2000基本解為（2,0,0,0,0,1），Z＝4100編輯版pppt五、幾種特殊情況迭代次數基變量XBCBx1x2x3s1s2s五、幾種特殊情況一旦出現多個最小比值，在下一步迭代求得的基本可行解中必然會有基變量的取值為0。這種解稱為退化的基本可行解，簡稱退化解。101編輯版pppt五、幾種特殊情況一旦出現多個最小比值，在下一步迭代求得的基本五、幾種特殊情況迭代次數基變量XBCBx1x2x3s1s2s3b比值bi/ai2203/20002s100001-111x121-1001-11x33/20210-122zj213/201/215cj-

zj0-100-1/2-1最優解為（1,0,2,1,0,0），Z＝5102編輯版pppt五、幾種特殊情況迭代次數基變量XBCBx1x2x3s1s2s五、幾種特殊情況迭代次數基變量XBCBx1x2x3s1s2s3b比值bi/ai2203/20000s101-1010022s2020101042s3011100133zj0000000cj-

zj203/2000比較：若選擇s1出基，迭代過程怎樣？103編輯版pppt五、幾種特殊情況迭代次數基變量XBCBx1x2x3s1s2s五、幾種特殊情況迭代次數基變量XBCBx1x2x3s1s2s3b比值bi/ai2203/20001x121-101002----s20021-21000s30021-1011?zj2-202004cj-

zj023/2-200基本解為（2,0,0,0,0,1），Z＝4104編輯版pppt五、幾種特殊情況迭代次數基變量XBCBx1x2x3s1s2s五、幾種特殊情況迭代次數基變量XBCBx1x2x3s1s2s3b比值bi/ai2203/20002x12101/201/2024x20011/2-11/2000s300001-111-----zj2010104cj-

zj001/20-10基本解為（2,0,0,0,0,1），Z＝4105編輯版pppt五、幾種特殊情況迭代次數基變量XBCBx1x2x3s1s2s五、幾種特殊情況迭代次數基變量XBCBx1x2x3s1s2s3b比值bi/ai2203/20003x121-1010022x33/2021-2100-----s300001-1111zj213/2-13/204cj-

zj0-101-3/20基本解為（2,0,0,0,0,1），Z＝4106編輯版pppt五、幾種特殊情況迭代次數基變量XBCBx1x2x3s1s2s五、幾種特殊情況迭代次數基變量XBCBx1x2x3s1s2s3b比值bi/ai2203/20004x121-1001-11x33/20210-122s100001-111zj213/201/215cj-

zj0-100-1/2-1基本解為（1,0,2,1,0,0），Z＝5107編輯版pppt五、幾種特殊情況迭代次數基變量XBCBx1x2x3s1s2s五、幾種特殊情況退化解的出現可能引起迭代次數的增加，特殊情況還會造成基的循環，不利于求解。如目標函數：minz=-3/4x4+20x5-1/2x6+6x7

約束條件：x1+1/4x4-8x5-x6+9x7=0

x2+1/2x4-12x5-1/2x6+3x7=0

x3+x6=1

x1,x2,x3,x4,x5,x6,x7≥0108編輯版pppt五、幾種特殊情況退化解的出現可能引起迭代次數的增加，特殊情況五、幾種特殊情況這個例題的確存在最優解，但用一般單純形表法，經過6次迭代后得到的單純形表與第0次單純形表一樣，而目標函數都是零，沒有任何變化，這樣迭代下去，永遠達不到最優解。為了避免這種現象，我們介紹勃蘭特法則:109編輯版pppt五、幾種特殊情況這個例題的確存在最優解，但用一般單純形表法，五、幾種特殊情況首先我們把松弛變量（剩余變量）、人工變量都用xj表示，一般松弛變量（剩余變量）的下標號列在決策變量之后，人工變量的下標號列在松弛變量（剩余變量）之后，在計算中，遵守以下兩個規則：（1）在所有檢驗數大于零的非基變量中，選一個下標最小的作為入基變量。（2）在存在兩個和兩個以上最小比值時，選一個下標最小的基變量為出基變量。這樣就一定能避免出現循環（不一定最有效率）。110編輯版pppt五、幾種特殊情況首先我們把松弛變量（剩余變量）、人工變量都用總結：單純形法計算步驟添加松弛變量、人工變量列出初始單純形表計算非基變量各列的檢驗數否是基變量中有非零的人工變量迭代運算1、用非基變量xk替換基變量xl；2、通過初等行變換，將主元變為1，主列其他元素變為0。對所有aik>0計算Qi＝bi/aik令Ql=min｛Qi｝則xl為出基變量，alk為主元否某非基變量檢驗數為零唯一最優解無界解無可行解無窮多最優解是是是否否111編輯版pppt總結：單純形法計算步驟添加松弛變量、人工變量列出初始單純形表第五章單純形法一、問題的提出二、單純形法的基本思路和原理三、單純形法的表格形式四、人工變量法五、幾種特殊情況112編輯版pppt第五章單純形法一、問題的提出1編輯版pppt一、問題的提出圖解法只能解決二維的線性規劃問題，那更多變量的問題怎么辦？(jsj)通過代數算法搜尋最優解。單純形法，就是這樣的一種代數搜尋法。線性規劃問題的解一般有無窮多個，如果不縮小搜尋范圍，工作量太大！我們首先將最優解縮小在一個有限的范圍。113編輯版pppt一、問題的提出圖解法只能解決二維的線性規劃問題，那更多變量的一、問題的提出回顧圖解法，我們知道：最優解必定在可行域的頂點上取得，而頂點的個數總是有限的。多維線性規劃問題的可行域也存在有限個頂點。如果能夠從一個頂點開始，通過某種方式向更優頂點轉移，總會找到最優點。首先面臨的問題：如何通過代數方法找到第一個頂點？114編輯版pppt一、問題的提出回顧圖解法，我們知道：最優解必定在可行域的頂點一、問題的提出圖解法中的例1.5模型為：Maxz=50x1+100x2

s.t.1·x1+1·x2≤300

2·x1+1·x2≤400

0·x1+1·x2≤250

x1≥0，x2≥0115編輯版pppt一、問題的提出圖解法中的例1.5模型為：4編輯版pppt一、問題的提出從其標準形的解向量開始研究：Maxz=50x1+100x2

s.t.1·x1+1·x2+1·x3+0·x4+0·x5＝300

2·x1+1·x2+0·x3+1·x4+0·x5＝400

0·x1+1·x2+0·x3+0·x4+1·x5＝250

xj≥0(j=1,2,3,4,5)116編輯版pppt一、問題的提出從其標準形的解向量開始研究：5編輯版pppt一、問題的提出頂點對應的解向量有何代數特征？O(0,0,300,400,250)A(0,250,50,150,0)B(50,250,0,50,0)C(100,200,0,0,50)D(200,0,100,0,50)答案：都有兩個變量取值為0，且非負。X1X2O(0,0)A(0,250)B(50,250)C(100,200)D(200,0)117編輯版pppt一、問題的提出頂點對應的解向量有何代數特征？X1X2O(0,一、問題的提出既然頂點解向量中有兩個變量取值為0，而標準形中又有三個約束方程，是否可以直接通過這種方式找頂點？如令x1＝0，x2＝0，則x3＝300，x4＝400，x5＝250可得到解（0，0，300，400，250）118編輯版pppt一、問題的提出既然頂點解向量中有兩個變量取值為0，而標準形中一、問題的提出又如：令x3＝0，x5＝0，由約束條件：x1+x2+x3＝3002x1+x2+x4＝400x2+x5＝250可得到解（50，250，0，50，0）119編輯版pppt一、問題的提出又如：令x3＝0，x5＝0，8編輯版pppt一、問題的提出若令x2＝0，x5＝0，會怎樣？由約束方程可知：x1+x2+x3＝300→x1+x3＝3002x1+x2+x4＝400→2x1+x4＝400x2+x5＝250→0＝250？顯然不能得到相應的解。120編輯版pppt一、問題的提出若令x2＝0，x5＝0，會怎樣？9編輯版ppp一、問題的提出為什么令x2＝0，x5＝0時不能得到解？因為其余三個變量的系數列向量為該矩陣是非可逆矩陣，即去掉x2和x5后的三個約束方程線性相關，這種情況下得不到解。121編輯版pppt一、問題的提出為什么令x2＝0，x5＝0時不能得到解？10編一、問題的提出既然如此，如果我們在技術矩陣中取出三列，組成一個可逆陣，令其余兩列對應的變量為零，則一定可以得到一個解。122編輯版pppt一、問題的提出既然如此，如果我們在技術矩陣中取出三列，組成一一、問題的提出如，取1、2、3列得到：此矩陣為可逆陣，故令x4＝0，x5＝0，一定可以得到一個解。對應的解為（75，250，-25，0，0）。123編輯版pppt一、問題的提出如，取1、2、3列得到：12編輯版pppt一、問題的提出基的概念：已知A是約束條件的m×n階系數矩陣，其秩為m。設B是A矩陣中的一個非奇異（可逆）的m×m階子矩陣，則稱B為線性規劃問題的一個基。B由A中的m個線性無關列向量組成。124編輯版pppt一、問題的提出基的概念：13編輯版pppt一、問題的提出一個基對應一組概念：非基變量基變量基向量非基向量對應基本解：（0，0，300，400，250）125編輯版pppt一、問題的提出一個基對應一組概念：非基變量基變量基向量非基向一、問題的提出(0,0,300,400,250)(0,300,0,100,-50)(0,400,-100,0,150)(0,250,50,150,0)(300,0,0,-200,-50)(200,0,100,0,50)不存在(100,200,0,0,50)(50,250,0,50,0)(75,250,-25,0,0)基本解是x3,x5p3,p5x1,x2,x4p1,p2,p4B2=(p1,p2,p4)是x3,x4p3,p4x1,x2,x5p1,p2,p5B3=(p1,p2,p5)是x1,x2p1,p2x3,x4,x5p3,p4,p5B10=(p3,p4,p5)否x1,x3p1,p3x2,x4,x5p2,p4,p5B9=(p2,p4,p5)否x1,x4p1,p4x2,x3,x5p2,p3,p5B8=(p2,p3,p5)是x1,x5p1,p5x2,x3,x4p2,p3,p4B7=(p2,p3,p4)否x2,x3p2,p3x1,x4,x5p1,p4,p5B6=(p1,p4,p5)是x2,x4p2,p4x1,x3,x5p1,p3,p5B5=(p1,p3,p5)x2,x5p2,p5x1,x3,x4p1,p3,p4B4=(p1,p3,p4)否x4,x5p4,p5x1,x2,x3p1,p2,p3B1=(p1,p2,p3)是否可行非基變量非基向量基變量基向量基126編輯版pppt一、問題的提出(0,0,300,400,250)(0,300一、問題的提出基本解可能可行，也可能不可行。滿足非負約束條件的基本解叫基本可行解，相應的基稱為可行基。否則為非可行基。127編輯版pppt一、問題的提出基本解可能可行，也可能不可行。16編輯版ppp一、問題的提出A：(0,250,50,150,0)B：(50,250,0,50,0)C：(100,200,0,0,50)D：(200,0,100,0,50)O：(0,0,300,400,250)E：(75,250,-25,0,0)F：(0,300,0,100,-50)G：(0,400,-100,0,150)H：(300,0,0,-200,-50)X1X2O(0,0)A(0,250)B(50,250)C(100,200)D(200,0)G(0,400)E(75,250)F(0,300)H(300,0)①③②128編輯版pppt一、問題的提出A：(0,250,50,150,0)X1X2O一、問題的提出線性規劃解的集合關系：基本解最優解基本可行解可行解129編輯版pppt一、問題的提出線性規劃解的集合關系：基本解最優解基本可行解可一、問題的提出顯然，將搜索范圍控制在基本可行解內，將大大減少搜索工作量。但是，即使取得一個基，得到的解還不一定可行。如何才能保證取得一個可行基呢？130編輯版pppt一、問題的提出顯然，將搜索范圍控制在基本可行解內，將大大減少一、問題的提出總結：1、可行域頂點對應的解必為基本可行解：有n-m個變量取值為0，滿足非負條件。2、一個基對應一組基本解，可能可行，也可能不可行；3、最優解必定在基本可行解中；131編輯版pppt一、問題的提出總結：20編輯版pppt二、單純形法的基本思路和原理單純形法的基本思路：首先找到一個頂點；然后判斷它是否最優；如果不是，則通過更換頂點的方式找到更優的頂點；直到找到最優頂點。132編輯版pppt二、單純形法的基本思路和原理單純形法的基本思路：21編輯版p二、單純形法的基本思路和原理第一步：找到一個頂點（初始基本可行解）133編輯版pppt二、單純形法的基本思路和原理22編輯版pppt二、單純形法的基本思路和原理思考：1、令n-m個變量為0（非基變量）是否一定可以找到？答案：不一定。如例中x2＝0，x5＝0時不能得到解。可行的辦法：找到一個基。134編輯版pppt二、單純形法的基本思路和原理思考：23編輯版pppt二、單純形法的基本思路和原理2、一個基是否一定對應可行域頂點？答案：不一定。必須是可行基。一般來說，判斷一個基是否是可行基，需要在求出其基本解后才能判斷。135編輯版pppt二、單純形法的基本思路和原理2、一個基是否一定對應可行域頂點二、單純形法的基本思路和原理3、那有沒有辦法在求出解之前保證我們取得的基為可行基？解決辦法：保證右端項非負，找到一個單位矩陣，必定是一個可行基。136編輯版pppt二、單純形法的基本思路和原理3、那有沒有辦法在求出解之前保證二、單純形法的基本思路和原理如范例系數陣：存在3階單位陣（初始可行基）右端項非負137編輯版pppt二、單純形法的基本思路和原理如范例系數陣：存在3階單位陣（初二、單純形法的基本思路和原理基本可行解為（0，0，300，400，250）此可行基稱為初始可行基。對應的解稱為初始基本可行解。初始基本可行解在上頁矩陣中一目了然。138編輯版pppt二、單純形法的基本思路和原理基本可行解為（0，0，300，4二、單純形法的基本思路和原理第二步：最優性檢驗139編輯版pppt二、單純形法的基本思路和原理28編輯版pppt二、單純形法的