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

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

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

X＝aX1＋（1－a）X2

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

=(x1,x2,…,xn)為基可行解的充要條件是X的正分量所對應(yīng)的系數(shù)列向量線性獨(dú)立。證：（1）必要性。由基可行解的定義得證。（2）充分性。若向量P1,P2,…,Pk線性獨(dú)立，則必有k≤m時；當(dāng)k=m時，它們恰好構(gòu)成一個基，從而X=(x1,x2,…,xm,0,…,0)T為相應(yīng)的基可行解。當(dāng)k<m時，則一定可以從其余列向量中找出(m-k)個與P1,P2,…,Pk構(gòu)成一個基，其對應(yīng)的解恰為X，所以根據(jù)定義它是基可行解。返回當(dāng)前第24頁\共有57頁\編于星期二\13點(diǎn)6/15/202324定理2：線性規(guī)劃的基本可行解對應(yīng)于其可行域的頂點(diǎn)。證:本定理需要證明:X是可行域頂點(diǎn)X是基可行解。用反證法證明：X不是可行域的頂點(diǎn)X不是基可行解。（1）X不是基可行解X不是可行域的頂點(diǎn)。假設(shè)X的前m個分量為正，有當(dāng)前第25頁\共有57頁\編于星期二\13點(diǎn)6/15/202325由引理知P1,P2,…,Pm線性相關(guān)，即存在一組不全為零的數(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不是可行域的頂點(diǎn)。引理當(dāng)前第26頁\共有57頁\編于星期二\13點(diǎn)6/15/202326（2）X不是可行域的頂點(diǎn)X不是基本可行解。設(shè)X＝(x1,x2,…,0,…,0)T不是可行域的頂點(diǎn)，因而可以找到可行域內(nèi)另外兩個不同點(diǎn)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,故當(dāng)xj=0時，必有yi=zi=0(1.14)-(1.15)得：因(yj－zj)不全為零，故P1,P2,…,Pr線性相關(guān)，即X不是基可行解。當(dāng)前第27頁\共有57頁\編于星期二\13點(diǎn)6/15/202327定理3若線性規(guī)劃問題有最優(yōu)解，一定存在一個基可行解是最優(yōu)解。證：設(shè)X(0)=(x10,x20,…,xn0)是線性規(guī)劃的一個最優(yōu)解，若X(0)不是基可行解，由定理2知X(0)不是頂點(diǎn)，一定能在可行域內(nèi)找到通過X(0)的直線上的另外兩個點(diǎn)（X(0)+md)≥0和（X(0)－md）≥0。將這兩個點(diǎn)代入目標(biāo)函數(shù)有C(X(0)＋md)＝CX(0)＋Cmd ; C(X(0)－md)＝CX(0)－Cmd因CX(0)為目標(biāo)函數(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ù)做下去，最后一定可以找到一個基可行解，使目標(biāo)函數(shù)值等于CX(0)，問題得得證。當(dāng)前第28頁\共有57頁\編于星期二\13點(diǎn)6/15/202328四、單純形法迭代原理基本思路：先找出一個基可行解，判斷它是否為最優(yōu)解，如為否，則轉(zhuǎn)換到相鄰的基可行解，并使目標(biāo)函數(shù)值不斷增大，一直到求得最優(yōu)解或判斷問題無解為止。在約束條件（1.16）的系數(shù)矩陣中，總可以找到一個單位矩陣：確定初始基可行解當(dāng)前第29頁\共有57頁\編于星期二\13點(diǎn)6/15/202329基陣P1,P2,…,Pm稱為基向量，與其對應(yīng)的變量x1,x2,…xm稱為基變量，模型中的其它變量稱為非基變量。在約束條件中令所有的非基變量等于零，即可得到一個解：X＝(x1,x2,…xm,xm+1,…,xn)T＝（b1,b2,…,bm,0,…,0)T因b≥0，所以X滿足非負(fù)約束，是一個基可行解。從一個基可行解轉(zhuǎn)換為相鄰的基可行解定義：兩個基可行解稱為相鄰的，如果它們之間變換且僅變換一個基變量。當(dāng)前第30頁\共有57頁\編于星期二\13點(diǎn)6/15/202330設(shè)初始基可行解中的前m個為基變量為：X(0)＝(x10,x20,…,xm0,0,…，0)T將其代入約束條件（1.16）有系數(shù)矩陣的增廣矩陣為：因P1,P2,…,Pm是一個基，其它向量Pj可用這個基的線性組合來表示：當(dāng)前第31頁\共有57頁\編于星期二\13點(diǎn)6/15/202331或?qū)ⅲ?.20）式乘上一個正數(shù)θ＞0得（1.19）+（1.21）并整理得：由（1.22）式找到滿足約束方程組的另一個點(diǎn)X(1),有X(1)＝(x10-qa1j,x20-qa2j,…,xm0-qamj,0,…,q,…,0)T其中q是X(1)的第j個坐標(biāo)的值。要使X(1)是一個基本可行解，必須使xi0－qaij≥01.23）令這m個不等式中至少有一個等號成立。故可令當(dāng)前第32頁\共有57頁\編于星期二\13點(diǎn)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對應(yīng)的向量經(jīng)重新排列后得又因bl/alj＝q，所以

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

由此X(1)是同X(0)相鄰的基可行解，且由基向量組成的矩陣仍為單位矩陣。當(dāng)前第33頁\共有57頁\編于星期二\13點(diǎn)6/15/2023333.最優(yōu)性檢驗(yàn)和解的判別將基本可行解X(0)和X(1)分別代入目標(biāo)函數(shù)得式中，因?yàn)閝＞0,所以只要就有z(1)＞z(0)。當(dāng)前第34頁\共有57頁\編于星期二\13點(diǎn)6/15/202334最優(yōu)性檢驗(yàn)和解的判別準(zhǔn)則（1）當(dāng)所有sj≤0時，當(dāng)前基可行解是線性規(guī)劃問題的最優(yōu)解；（2）當(dāng)所有sj≤0，若對某個非基變量xj有cj－zj＝0,則該線性規(guī)劃問題有無窮多個最優(yōu)解；若對所有非基變量有sj＜0，線性規(guī)劃問題有唯一最優(yōu)解。（3）若存在sj＞0，又Pj≤0，則表明線性規(guī)劃問題有無界解。當(dāng)前第35頁\共有57頁\編于星期二\13點(diǎn)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。各變量在目標(biāo)函數(shù)中的系數(shù)值各基變量在目標(biāo)函數(shù)中對應(yīng)的系數(shù)檢驗(yàn)數(shù)sj=cj-zj=cj-(c1a1j+c2a2j+…+cmamj)返回第一章目錄當(dāng)前第36頁\共有57頁\編于星期二\13點(diǎn)6/15/202336第二步：最優(yōu)性檢驗(yàn)若單純形表中所有檢驗(yàn)數(shù)cj－zj≤0，且基變量中不含有人工變量，則得到線性規(guī)劃問題的最優(yōu)解，計算結(jié)束；若存在cj－zj＞0，而Pj≤0，則問題為無界解，計算結(jié)束；否則轉(zhuǎn)下一步。第三步：從一個基可行解轉(zhuǎn)換到相鄰的目標(biāo)函數(shù)值更大的基可行解，列出新的單純形表。1.確定換入基的變量。只要有檢驗(yàn)數(shù)sj＞0，其對應(yīng)的xj就可以作為換入基的變量，當(dāng)有一個以上檢驗(yàn)數(shù)大于零時，從中找出最大的一個sk，其對應(yīng)的變量xk為換入基的變量（簡稱換入變量）。2.確定換出基的變量。用Pk列的系數(shù)分別去除常數(shù)項(xiàng)，找出最小比值確定xl為換出基的變量，元素alk

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

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

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

用單純形法求解線性規(guī)劃問題P4P6P7罰因子，任意大負(fù)值人工變量返回第一章目錄當(dāng)前第43頁\共有57頁\編于星期二\13點(diǎn)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當(dāng)前第44頁\共有57頁\編于星期二\13點(diǎn)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當(dāng)前第45頁\共有57頁\編于星期二\13點(diǎn)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∵所有檢驗(yàn)數(shù)均≤0，且人工變量為零，∴得到問題的最優(yōu)解。X＝(0,5/2,3/2,0,0)T;z＝－3x1＋x3＝3/2兩階段法當(dāng)前第46頁\共有57頁\編于星期二\13點(diǎn)6/15/202346檢驗(yàn)數(shù)計算cj→-30100-M-MCB基bx1x2x3x4x5x6x70x441111000-Mx61-21-10-110-Mx790310001cj－zj-2M-34M10-M00單純形法求解過程當(dāng)前第47頁\共有57頁\編于星期二\13點(diǎn)6/15/202347二、兩階段法對添加人工變量后的線性規(guī)劃問題分兩個階段來計算，稱兩階段法。第一階段：構(gòu)造只包括人工變量的目標(biāo)函數(shù)，保持原問題約束條件不變，求第一階段目標(biāo)函數(shù)極小化的解。判斷：當(dāng)所有sj≤0時，若人工變量為0，第一階段的目標(biāo)函數(shù)值也為0，則得到第一階段最優(yōu)解，轉(zhuǎn)入第二階段計算。否則，原問題無解。第二階段：去掉人工變量，將目標(biāo)函數(shù)該為原問題的目標(biāo)函數(shù)，繼續(xù)迭代，尋找線性規(guī)劃問題的最優(yōu)解。當(dāng)前第48頁\共有57頁\編于星期二\13點(diǎn)6/15/202348用兩階段法求解線性規(guī)劃問題x6、x7是人工變量。解：1)構(gòu)造第一階段的目標(biāo)函數(shù)。2）將第一階段的目標(biāo)函數(shù)化為標(biāo)準(zhǔn)形式：3）列單純形表計算求解。當(dāng)前第49頁\共有57頁\編于星期二\13點(diǎn)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當(dāng)前第50頁\共有57頁\編于星期二\13點(diǎn)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