線性規(guī)劃及其單純形法詳解演示文稿

線性規(guī)劃及其單純形法詳解演示文稿當前第1頁\共有57頁\編于星期二\13點6/15/20231（優(yōu)選）線性規(guī)劃及其單純形法當前第2頁\共有57頁\編于星期二\13點6/15/20232一、線性規(guī)劃問題的數(shù)學模型在現(xiàn)有各項資源條件的限制下，如何確定方案，使預期目標達到最優(yōu)，這就是規(guī)劃方法。例1美佳公司計劃制造Ⅰ、Ⅱ兩種家電產品。已知各制造一件時分別占用的設備A、B的臺時、調試時間、調試工序每天可用于這兩種家電的能力、各售出一件時的獲利情況，如表1-1所示。問該公司應制造兩種家電產品各多少件，使獲取的利潤為最大？§1-1線性規(guī)劃問題及其數(shù)學模型返回第一章目錄當前第3頁\共有57頁\編于星期二\13點6/15/20233§1-1線性規(guī)劃問題及其數(shù)學模型用數(shù)學語言來描述這個問題。假設美佳公司每天制造Ⅰ、Ⅱ兩種家電產品的數(shù)量分別是x1和x2件。max約束條件目標函數(shù)Z＝2x1＋x25x2≤156x1＋2x2≤24x1＋x2≤5x1，x2≥0這就是例1的數(shù)學模型當前第4頁\共有57頁\編于星期二\13點6/15/20234《運籌學基礎及應用》第一章例2【例2】某企業(yè)計劃生產I、Ⅱ兩種產品。這兩種產品都要分別在A、B、C、D四種不同設備上加工。按工藝資料規(guī)定，生產每件產品I需占用各設備分別為2、1、4、0小時，生產每件產品B，需占用各設備分別為2、2、0、4小時。已知設備計劃期內用于生產這兩種產品的能力分別為12、8、16、12小時，又知每生產一件產品I企業(yè)能獲得2元利潤、每生產一件產品Ⅱ企業(yè)能獲得3元利潤，問該企業(yè)應安排生產兩種產品各多少件，使總的利潤收入為最大？當前第5頁\共有57頁\編于星期二\13點6/15/20235產品資源產品Ⅰ產品Ⅱ生產能力（h）設備A（h）2212設備B（h）128設備B（h）4016設備B（h）0412利潤（元/件）23假設：計劃期內生產產品Ⅰx1件，產品Ⅱx2件。當前第6頁\共有57頁\編于星期二\13點6/15/20236例2捷運公司擬在下一年度的1～4月份的4個月內租用倉庫堆放物資。已知各月份所需倉庫面積數(shù)。倉庫租借費用隨合同期而定，期限越長，折扣越大，具體數(shù)字如表1-2所示。租借倉庫的合同每月初都可辦理，每份合同具體規(guī)定租用面積和期限。因此，該廠可根據(jù)需要，在任何一個月初辦理租借合同。每次辦理可簽一份，也可簽若干份租用面積和租借期限不同的合同，試確定該公司簽定租借合同的最優(yōu)決策，目的是使所付租借費用最小。當前第7頁\共有57頁\編于星期二\13點6/15/20237假設用xij表示捷運公司第i（i＝1，2，…，4）個月月初簽訂租借期為j（j＝1，2，…，4）個月的倉庫面積數(shù)(單位為100m2）。則minz＝2800(x11+x21+x31+x41)+4500(x12+x22+x32)+6000(x13+x23)+7300x14 x11+x12+x13+x14≥15 x12+x13+x14+x21+x22+x23≥10 x13+x14+x22+x23+x31+x32≥20 x14+x23+x32+x41≥12 xij≥0(i＝1，2，…，4；j＝1，2，…，4）租借期為一個月的倉庫面積租借期為二個月的倉庫面積租借期為三個月的倉庫面積租借期為四個月的倉庫面積一月份擁有的租借面積二月份擁有的租借面積三月份擁有的租借面積四月份擁有的租借面積一月份倉庫需求面積約束二月份倉庫需求面積約束三月份倉庫需求面積約束四月份倉庫需求面積約束非負約束當前第8頁\共有57頁\編于星期二\13點6/15/20238組成線性規(guī)劃模型的三個要素maxZ＝2x1＋x2 5x2≤15 6x1＋2x2≤24 x1＋x2≤5 x1，x2≥0目標函數(shù)：約束條件（1）變量（決策變量）:它是規(guī)劃中要確定的未知量，是用數(shù)量方式來表示的方案或措施，可由決策者決定和控制。（2）目標函數(shù)：它是決策變量的函數(shù)，是決策者在一定的限制條件下希望得到的結果。（3）約束條件：指決策變量取值時受到的各種資源條件的限制，通常用等式或不等式來表達。其中，xij≥0叫做非負約束。由于目標函數(shù)是決策變量的線性函數(shù)，約束條件是含決策變量的線性等式或不等式，所以此類模型稱為線性規(guī)劃的數(shù)學模型。實際問題中，線性的含義有二：一是嚴格的比例性，即某種產品對資源的消耗量和可獲得的利潤與其生產數(shù)量嚴格成比例。二是可迭加性。即生產多種產品對某種資源的消耗量等于各產品對該項資源的消耗量之和。當前第9頁\共有57頁\編于星期二\13點6/15/20239模型中，cj稱為價值系數(shù)。bi是資源限制量。aij稱為技術系數(shù)或工藝系數(shù)。二、線性規(guī)劃模型的一般形式假設線性規(guī)劃問題中含有n個變量，m個約束方程。則線性規(guī)劃模型的一般形式為：max(或min)z＝c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn≤（或＝，≥）b1a21x1+a22x2+…+a2nxn≤（或＝，≥）b2…………am1x1+am2x2+…+amnxn≤（或＝，≥）bmx1,x2,…,xn≥0簡寫為：向量形式：矩陣形式：當前第10頁\共有57頁\編于星期二\13點6/15/202310三、線性規(guī)劃問題的標準形式若得出的線性規(guī)劃模型不是標準形式，應通過下列方法將其化為標準形式：1.目標函數(shù)為求極小值的情況，即本教材規(guī)定，線性規(guī)劃模型的標準形式為：其特點是：(1)目標函數(shù)求極大；(2)約束條件取等式；(3)變量非負；(4)約束條件右邊常數(shù)為正值。化為標準形式的方法是，令zˊ＝－z，則當前第11頁\共有57頁\編于星期二\13點6/15/202311三、線性規(guī)劃問題的標準形式3.約束條件為不等式的情況。當約束條件為“≤”時，在約束符號的左邊加上一個松弛變量，將“≤”變?yōu)椤埃健?；?x1+2x2≤24,化為標準形式為6x1+2x2＋x3＝24，x3≥0。當約束條件為“≥”時，在約束符號的左邊減去一個剩余變量，將“≥”變?yōu)椤埃健保蝗?0x1+12x2≥18,化為標準形式為10x1+12x2－x3＝18，x3≥0。4.對變量無約束的情況。如x在（－∞，＋∞）之間變化，即x的取值可正可負時，令x＝xˊ－x〞代入線性規(guī)劃模型即可，其中xˊ≥0，x〞≥0。5.對于x≤0的情況，令xˊ＝－x，顯然xˊ≥0。2.若約束條件右邊常數(shù)項bi<0，化為標準形式的方法是：將等式或不等式兩邊同時乘以（－1）。當前第12頁\共有57頁\編于星期二\13點6/15/202312例3將下述線性規(guī)劃模型化為標準形式minz＝x1+2x2+3x3－2x1+x2+x3≤9－3x1+x2+2x3≥44x1－2x2－3x3＝－6x1≤0，x2≥0，x3取值無約束（左邊減去x8）（令z1＝－z）（左邊加上x7）（兩邊同時乘以－1）解：令x4＝－x1，x3＝x5－x6代入上式，其中x4，x5，x6≥0minz＝－x4+2x2+3（x5－x6)2x4+x2+(x5－x6)≤93x4+x2+2(x5－x6)≥4－4x4－2x2－3(x5－x6)＝－6x2,x4,x5,x6≥0maxz1＝－2x2＋x4－3x5＋3x6x2+2x4+x5－x6＋x7＝9x2+3x4+2x5－2x6－x8＝42x2＋4x4＋3x5－3x6＝6x2,x4,x5,x6,x7,x8≥0該線性規(guī)劃問題的標準形式為當前第13頁\共有57頁\編于星期二\13點6/15/202313§1-2圖解法含有兩個決策變量的線性規(guī)劃問題可用圖解法求解。圖解法的目的：一是判別線性規(guī)劃問題的求解結局；二是在存在最優(yōu)解的條件下，把問題的最優(yōu)解求出來。一、圖解法的步驟1.在坐標平面上建立直角坐標系；2.圖示約束條件，找出可行域；3.圖示目標函數(shù)，尋找最優(yōu)解。例：maxz＝2x1＋x2 5x2≤15 6x1＋2x2≤24 x1＋x2≤5 x1，x2≥0Q1Q3Q2Q4Ox1x25x2＝156x1＋2x2＝24x1＋x2＝5z＝2z＝8.5(3.5，1.5)6x1＋2x2＝24x1＋x2＝5聯(lián)立單純形法返回第一章目錄當前第14頁\共有57頁\編于星期二\13點6/15/202314二、線性規(guī)劃問題求解的幾種可能結局上例用圖解法解得線性規(guī)劃問題的最優(yōu)解為x1＝3.5，x2＝1.5，與最優(yōu)解相應的目標函數(shù)值z＝8.5。這是該線性規(guī)劃的唯一最優(yōu)解。除此之外，線性規(guī)劃問題的求解還有以下幾種情況：1.線性規(guī)劃問題有無窮多最優(yōu)解。2.線性規(guī)劃問題的最優(yōu)解無界。3.線性規(guī)劃問題無解，或無可行解。Q1Q4Q3Q2Ox1x2x1x2Ox1x2有無窮多最優(yōu)解目標函數(shù)求極大時，最優(yōu)解無界無可行域，所以無解。遺漏必要的約束條件約束條件之間存在矛盾當前第15頁\共有57頁\編于星期二\13點6/15/202315三、由圖解法得到的起示1.求解線性規(guī)劃問題時，解的情況有：有唯一最優(yōu)解；無窮多最優(yōu)解；最優(yōu)解無界（無界解）；無可行解。2.若線性規(guī)劃問題的可行域存在，則可行域是凸集。3.若線性規(guī)劃問題的最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一（如果有無窮多解的話）一定是可行域的某個頂點。4.解題思路是，先找出凸集的任一頂點，計算該處的目標函數(shù)值。比較周圍相鄰頂點的目標函數(shù)值是否比這個值大，如果不是，則該頂點就是最優(yōu)解點或最優(yōu)解的點之一，否則轉到比這個點的目標函數(shù)值更大的另一頂點，重復上述過程，直到找出使目標函數(shù)值達到最大的頂點為止。當前第16頁\共有57頁\編于星期二\13點6/15/202316§1-3單純形法原理可行解：滿足（2）、（3）式的解稱為可行解。全部可行解的集合稱為可行域。最優(yōu)解：使目標函數(shù)（1）達到最大值的可行解稱為最優(yōu)解。一、線性規(guī)劃問題的解的概念有線性規(guī)劃問題：基：設A為約束方程（2）的m×n階系數(shù)矩陣（設n>m），其秩為m，B是矩陣A中的一個m×m階的滿秩子矩陣，稱B是線性規(guī)劃問題的一個基。系數(shù)矩陣基：圖解法返回第一章目錄當前第17頁\共有57頁\編于星期二\13點6/15/202317一、線性規(guī)劃問題的解的概念基B中的每一個列向量Pj(j=1，2，…，m）稱為基向量，與基向量Pj對應的變量xj稱為基變量；除基變量以外的變量稱為非基變量。基解：在約束方程中，將非基變量移到等式右邊：P1P2Pm令非基變量xm+1＝xm+2＝…＝xn＝0，得可解得m個基變量的唯一解為：XB＝（x1，x2，…，xm）T。加上非基變量取0的值，得X＝（x1,x2,…，xm,0,…,0）T。這就是線性規(guī)劃問題的基解。當前第18頁\共有57頁\編于星期二\13點6/15/202318基可行解：滿足非負約束的解稱為基可行解?？尚谢簩诨尚薪獾幕Q為可行基。例：找出下述線性規(guī)劃問題的全部基解，指出其中的基可行解，并確定最優(yōu)解。maxz＝2x1+3x2+x3x1+x3＝5x1+2x2+x4＝10x2+x5＝4x1~5≥0一、線性規(guī)劃問題的解的概念解：用窮舉法找出該線性規(guī)劃問題的全部基解。打√者為基可行解。最優(yōu)解為：x1＝2，x2＝4，x3＝3，x4＝0，x5＝0與最優(yōu)解對應的目標函數(shù)值為z＝19當前第19頁\共有57頁\編于星期二\13點6/15/202319凸集設C為n維歐氏空間的一個點集。若對于C中任意兩點X1，X2滿足αX1+(1-α)X2∈C(0＜α＜1)則稱C為凸集。也就是說，如果X1∈C，X2∈C，則線段X1X2上的所有點X也屬于C。即：X＝αX1+(1-α)X2∈C(0＜α＜1)稱C為凸集。從直觀上看，凸集沒有凹入部分，其內部沒有孔洞。二、凸集和頂點凸集凸集凸集凸集凸集凸集當前第20頁\共有57頁\編于星期二\13點6/15/202320不是凸集不是凸集不是凸集不是凸集二、凸集和頂點頂點設K為凸集，X∈C，若X不能用C中不同的兩點X1，X2的線性組合表示為X＝αX1+(1-α)X2∈C(0＜α＜1)則稱X為C的一個頂點（或極點）。即X不能成為C中任何線段的內點。當前第21頁\共有57頁\編于星期二\13點6/15/202321三、線性規(guī)劃的基本定理定理1：若線性規(guī)劃問題存在可行解，則問題的可行域是凸集。引理線性規(guī)劃的可行解X=(x1,x2,…,xn)為基可行解的充要條件是X

的正分量所對應的系數(shù)列向量線性獨立。定理2：線性規(guī)劃的基本可行解對應于其可行域的頂點。定理3若線性規(guī)劃問題有最優(yōu)解，一定存在一個基可行解是最優(yōu)解。單純形法迭代原理當前第22頁\共有57頁\編于星期二\13點6/15/202322定理1：若線性規(guī)劃問題存在可行解，則問題的可行域是凸集。證明若滿足線性規(guī)劃約束條件線性規(guī)劃的基本定理的證明∑Pjxj＝bj=1n的所有點組成的集合C是凸集,則C內任意兩點X1，X2連線上的點也必然在C內。設X1=(x11,x12,…，x1n)T,X2=(x21,x22,…，x2n)T為C內任意兩點，即X1∈C，X2∈C，將X1，X2代入約束條件，有∑Pjx1j＝bj=1n∑Pjx2j＝bj=1n；（1-9）X1，X2連線上任意一點可表示為：

X＝aX1＋（1－a）X2

（0<a<1) (1-10)將（1-9）代入（1-10）得：所以X1∈C，X2∈C。由于集合中任意兩點連線上的點均在集合內，所以C為凸集。當前第23頁\共有57頁\編于星期二\13點6/15/202323引理線性規(guī)劃的可行解X

=(x1,x2,…,xn)為基可行解的充要條件是X的正分量所對應的系數(shù)列向量線性獨立。證：（1）必要性。由基可行解的定義得證。（2）充分性。若向量P1,P2,…,Pk線性獨立，則必有k≤m時；當k=m時，它們恰好構成一個基，從而X=(x1,x2,…,xm,0,…,0)T為相應的基可行解。當k<m時，則一定可以從其余列向量中找出(m-k)個與P1,P2,…,Pk構成一個基，其對應的解恰為X，所以根據(jù)定義它是基可行解。返回當前第24頁\共有57頁\編于星期二\13點6/15/202324定理2：線性規(guī)劃的基本可行解對應于其可行域的頂點。證:本定理需要證明:X是可行域頂點X是基可行解。用反證法證明：X不是可行域的頂點X不是基可行解。（1）X不是基可行解X不是可行域的頂點。假設X的前m個分量為正，有當前第25頁\共有57頁\編于星期二\13點6/15/202325由引理知P1,P2,…,Pm線性相關，即存在一組不全為零的數(shù)δi(i=1,2,…，m),使得 d1P1+d2P2+…+dmPm=0 (1.12)將（1.12）乘以一個不全為零的數(shù)μ得 md1P1+md2P2+…+mdmPm=0 (1.13)(1.13)+(1.11)得：(x1＋md1)P1+(x2＋md2)P2+…+(xm＋mdm)Pm=b(1.11)-(1.13)得：(x1－md1)P1+(x2－md2)P2+…+(xm－mdm)Pm=b令 X(1)=[(x1＋md1),(x2＋md2),…,(xm＋mdm),0,…,0] X(2)=[(x1－md1),(x2－md2),…,(xm－mdm),0,…,0]又m可以這樣來選擇，使得對所有i=1,2,…,m有xi±m(xù)di≥0即X不是可行域的頂點。引理當前第26頁\共有57頁\編于星期二\13點6/15/202326（2）X不是可行域的頂點X不是基本可行解。設X＝(x1,x2,…,0,…,0)T不是可行域的頂點，因而可以找到可行域內另外兩個不同點Y和Z，有X=aY+(1-a)Z(0<a<1),或可寫為：xj=ay+(1-a)zj;(0<a<1;j=1,2,…,n)因a>0,1-a>0,故當xj=0時，必有yi=zi=0(1.14)-(1.15)得：因(yj－zj)不全為零，故P1,P2,…,Pr線性相關，即X不是基可行解。當前第27頁\共有57頁\編于星期二\13點6/15/202327定理3若線性規(guī)劃問題有最優(yōu)解，一定存在一個基可行解是最優(yōu)解。證：設X(0)=(x10,x20,…,xn0)是線性規(guī)劃的一個最優(yōu)解，若X(0)不是基可行解，由定理2知X(0)不是頂點，一定能在可行域內找到通過X(0)的直線上的另外兩個點（X(0)+md)≥0和（X(0)－md）≥0。將這兩個點代入目標函數(shù)有C(X(0)＋md)＝CX(0)＋Cmd ; C(X(0)－md)＝CX(0)－Cmd因CX(0)為目標函數(shù)的最大值，故有CX(0)≥CX(0)＋Cmd ； CX(0)≥CX(0)－Cmd由此知Cmd＝0，即有C(X(0)＋md)＝CX(0)＝C(X(0)－md)。如果（X(0)＋md）或(X(0)－md)仍不是基可行解，按上面的方法繼續(xù)做下去，最后一定可以找到一個基可行解，使目標函數(shù)值等于CX(0)，問題得得證。當前第28頁\共有57頁\編于星期二\13點6/15/202328四、單純形法迭代原理基本思路：先找出一個基可行解，判斷它是否為最優(yōu)解，如為否，則轉換到相鄰的基可行解，并使目標函數(shù)值不斷增大，一直到求得最優(yōu)解或判斷問題無解為止。在約束條件（1.16）的系數(shù)矩陣中，總可以找到一個單位矩陣：確定初始基可行解當前第29頁\共有57頁\編于星期二\13點6/15/202329基陣P1,P2,…,Pm稱為基向量，與其對應的變量x1,x2,…xm稱為基變量，模型中的其它變量稱為非基變量。在約束條件中令所有的非基變量等于零，即可得到一個解：X＝(x1,x2,…xm,xm+1,…,xn)T＝（b1,b2,…,bm,0,…,0)T因b≥0，所以X滿足非負約束，是一個基可行解。從一個基可行解轉換為相鄰的基可行解定義：兩個基可行解稱為相鄰的，如果它們之間變換且僅變換一個基變量。當前第30頁\共有57頁\編于星期二\13點6/15/202330設初始基可行解中的前m個為基變量為：X(0)＝(x10,x20,…,xm0,0,…，0)T將其代入約束條件（1.16）有系數(shù)矩陣的增廣矩陣為：因P1,P2,…,Pm是一個基，其它向量Pj可用這個基的線性組合來表示：當前第31頁\共有57頁\編于星期二\13點6/15/202331或將（1.20）式乘上一個正數(shù)θ＞0得（1.19）+（1.21）并整理得：由（1.22）式找到滿足約束方程組的另一個點X(1),有X(1)＝(x10-qa1j,x20-qa2j,…,xm0-qamj,0,…,q,…,0)T其中q是X(1)的第j個坐標的值。要使X(1)是一個基本可行解，必須使xi0－qaij≥01.23）令這m個不等式中至少有一個等號成立。故可令當前第32頁\共有57頁\編于星期二\13點6/15/202332由式（1.24）知因alj＞0，故由矩陣元素組成的行列式不為零，P1,P2,…,Pl-1,Pl,Pl+1…,Pm是一個基。在上述增廣矩陣中作初等變換，將第l行乘上（1/alj),再分別乘以（-aij)(i=1,2,…,l-1,l+1,…,m)加到各行去，則增廣矩陣左半部分變成單位矩陣。所以，X(1)是一個可行解。與變量xl1,…,x1l-1,,x1l+1,…,xm,xj對應的向量經重新排列后得又因bl/alj＝q，所以

b=(b1-qa1j,…,bl-1-qal-1,j,bl+1-qal+1,j,…,bm-qamj)T

由此X(1)是同X(0)相鄰的基可行解，且由基向量組成的矩陣仍為單位矩陣。當前第33頁\共有57頁\編于星期二\13點6/15/2023333.最優(yōu)性檢驗和解的判別將基本可行解X(0)和X(1)分別代入目標函數(shù)得式中，因為q＞0,所以只要就有z(1)＞z(0)。當前第34頁\共有57頁\編于星期二\13點6/15/202334最優(yōu)性檢驗和解的判別準則（1）當所有sj≤0時，當前基可行解是線性規(guī)劃問題的最優(yōu)解；（2）當所有sj≤0，若對某個非基變量xj有cj－zj＝0,則該線性規(guī)劃問題有無窮多個最優(yōu)解；若對所有非基變量有sj＜0，線性規(guī)劃問題有唯一最優(yōu)解。（3）若存在sj＞0，又Pj≤0，則表明線性規(guī)劃問題有無界解。當前第35頁\共有57頁\編于星期二\13點6/15/202335§1-4單純形法計算步驟第一步：求初始基可行解，列出初始單純形表。cj→c1…cm…cj…cnCB基bx1…xm…xj…xnc1x1b11…0…a1j…a1nc2x2b20…0…a2j…a2n┆┆┆┆┆┆…┆┆┆cmxmbm0…1…amj…amncj－zj0…0……基變量及其值問題中所有變量單位矩陣非基變量系數(shù)向量Pj表示為基向量線性組合時的系數(shù)，因基向量是單位向量，故有Pj=a1jP1+a2jP2+…+amj。各變量在目標函數(shù)中的系數(shù)值各基變量在目標函數(shù)中對應的系數(shù)檢驗數(shù)sj=cj-zj=cj-(c1a1j+c2a2j+…+cmamj)返回第一章目錄當前第36頁\共有57頁\編于星期二\13點6/15/202336第二步：最優(yōu)性檢驗若單純形表中所有檢驗數(shù)cj－zj≤0，且基變量中不含有人工變量，則得到線性規(guī)劃問題的最優(yōu)解，計算結束；若存在cj－zj＞0，而Pj≤0，則問題為無界解，計算結束；否則轉下一步。第三步：從一個基可行解轉換到相鄰的目標函數(shù)值更大的基可行解，列出新的單純形表。1.確定換入基的變量。只要有檢驗數(shù)sj＞0，其對應的xj就可以作為換入基的變量，當有一個以上檢驗數(shù)大于零時，從中找出最大的一個sk，其對應的變量xk為換入基的變量（簡稱換入變量）。2.確定換出基的變量。用Pk列的系數(shù)分別去除常數(shù)項，找出最小比值確定xl為換出基的變量，元素alk

決定了從一個基可行解到相鄰基可行解的轉移去向，所以，稱alk為主元。當前第37頁\共有57頁\編于星期二\13點6/15/2023373.用換入變量xk替換換出變量xl，作初等變換，得到一個新的單純形表。初等變換的方法是：將主元化為1，主元所在列的其它元素化為0。第四步：重復第二、三兩步，直到得出計算結果。例5

用單純形法求解線性規(guī)劃問題解：在約束方程中加松弛變量，將該線性規(guī)劃問題化為標準形式其約束條件系數(shù)矩陣的增廣矩陣為：P1P2P3P4bP5基變量為x3、x4、x5；非基變量為x1、x2。單位矩陣構成一個基當前第38頁\共有57頁\編于星期二\13點6/15/202338令非基變量x1、x2等于零，的初始基本可行解為：

X(0)＝(0,0,15,24,5)T初始單純形表cj→21000CB基bx1x2x3x4x50x315051000x424620100x5511001cj－zj21000因為存在s1＝2＞0，s2＝1＞0。所以初始基可行解不是最優(yōu)解。選擇最大檢驗數(shù)對應的非基變量作為換入變量。求最小比值，確定換入變量。主元列主元行將主元化為1，主元所在列的其它元素化為0。當前第39頁\共有57頁\編于星期二\13點6/15/202339迭代運算初始單純形表cj→21000CB基bx1x2x3x4x50x315051000x424[6]20100x5511001cj－zj21000第一次迭代的單純形表cj→21000CB基bx1x2x3x4x5cj－zjx3x1x5020141/301/600155100012/30-1/6101/30-1/30當前第40頁\共有57頁\編于星期二\13點6/15/202340迭代運算第一次迭代的單純形表cj→21000CB基bx1x2x3x4x50x315051002x1411/301/600x510[2/3]0-1/61cj－zj01/30-1/30第二次迭代的單純形表cj→21000CB基bx1x2x3x4x5cj－zjx3x1x2021103/20-1/43/2017/201/4-1/20015/215/4-15/2000-1/4-1/2當前第41頁\共有57頁\編于星期二\13點6/15/202341迭代運算結果最終單純性表（第二次的結果）cj→21000CB基bx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2cj－zj000-1/4-1/2因為所有檢驗數(shù)sj≤0，且基變量中不含人工變量，所以得到線性規(guī)劃問題的最優(yōu)解為：代入目標函數(shù)得：當前第42頁\共有57頁\編于星期二\13點6/15/202342§1-5單純形法的進一步討論一、人工變量法線性規(guī)劃模型化為標準形式后，若其約束條件的系數(shù)矩陣中不含有單位矩陣，需加人工變量，以便求解。例6

用單純形法求解線性規(guī)劃問題P4P6P7罰因子，任意大負值人工變量返回第一章目錄當前第43頁\共有57頁\編于星期二\13點6/15/202343單純形法求解過程cj→-30100-M-MCB基bx1x2x3x4x5x6x70x441111000-Mx61-21-10-110-Mx790310001cj－zj-2M-34M10-M000x40x2-Mx7cj－zj1-21-10-110033211-10066403-31s1＝－3－[0×3＋0×(－2)+(－M)×6]＝6M－36M－3s2＝0－[0×0＋0×1+(－M)×0]＝00s3＝1－[0×2＋0×(－1)+(－M)×4] ＝4M＋14M＋1s4＝0－[0×1＋0×0+(－M)×0] ＝00s5＝0－[0×1＋0×(－1)+(－M)×3] ＝3M3Ms6＝－M－[0×(－1)＋0×1+(－M)×(－3)]＝－4M－4Ms7＝－M－[0×0＋0×0+(－M)×1]＝00當前第44頁\共有57頁\編于星期二\13點6/15/202344單純形法求解過程cj→-30100-M-MCB基bx1x2x3x4x5x6x70x4330211-100x21-21-10-110-Mx76[6]0403-31cj－zj6M-304M+103M-4M00x40x2-3x1cj－zj1102/301/2-1/21/60311/30001/300001-1/21/2-1/200303/2-M-3/2-M+1/2當前第45頁\共有57頁\編于星期二\13點6/15/202345單純形法求解過程cj→-30100-M-MCB基bx1x2x3x4x5x6x70x400001-1/21/2-1/20x23011/30001/3-3x1110[2/3]01/2-1/21/6cj－zj00303/2-M-3/2-M+1/20x40x21x3cj－zj103/23/203/4-3/41/401-1/25/20-1/41/41/400001-1/21/2-1/200-9/20-3/4-M+3/4-M-1/4∵所有檢驗數(shù)均≤0，且人工變量為零，∴得到問題的最優(yōu)解。X＝(0,5/2,3/2,0,0)T;z＝－3x1＋x3＝3/2兩階段法當前第46頁\共有57頁\編于星期二\13點6/15/202346檢驗數(shù)計算cj→-30100-M-MCB基bx1x2x3x4x5x6x70x441111000-Mx61-21-10-110-Mx790310001cj－zj-2M-34M10-M00單純形法求解過程當前第47頁\共有57頁\編于星期二\13點6/15/202347二、兩階段法對添加人工變量后的線性規(guī)劃問題分兩個階段來計算，稱兩階段法。第一階段：構造只包括人工變量的目標函數(shù)，保持原問題約束條件不變，求第一階段目標函數(shù)極小化的解。判斷：當所有sj≤0時，若人工變量為0，第一階段的目標函數(shù)值也為0，則得到第一階段最優(yōu)解，轉入第二階段計算。否則，原問題無解。第二階段：去掉人工變量，將目標函數(shù)該為原問題的目標函數(shù)，繼續(xù)迭代，尋找線性規(guī)劃問題的最優(yōu)解。當前第48頁\共有57頁\編于星期二\13點6/15/202348用兩階段法求解線性規(guī)劃問題x6、x7是人工變量。解：1)構造第一階段的目標函數(shù)。2）將第一階段的目標函數(shù)化為標準形式：3）列單純形表計算求解。當前第49頁\共有57頁\編于星期二\13點6/15/202349cj→00000-1-1CB基bx1x2x3x4x5x6x70x441111000-1x61-21-10-110-1x790310001cj-zj-2400-1000x4330211-100x21-21-10-110-1x7660403-31cj-zj60403-400x400001-1/21/2-1/20x23011/30001/30x11102/301/2-1/21/6cj-zj00000-1-1表1-11表1-12當前第50頁\共有57頁\編于星期二\13點6/15/202350表1-12cjCB基bx1x2x3x4x50x400001-1/20x23011/300-3x11102/301/2cj-zjcj-zj-3010000303/2x4x2x3001103/403/23/201-1/25/200001-1/20-1/4-9/2000-3