運籌學課件單純形法的迭代原理

四、單純形法的迭代原理

1、確定初始基可行解

(1)初始可行基的確定

觀察法——觀察系數(shù)矩陣中是否含有現(xiàn)成的單位陣？LP限制條件中全部是“≤”類型的約束——將新增的松弛變量作為初始基變量，對應的系數(shù)列向量構成單位陣；四、單純形法的迭代原理1

先將約束條件標準化，再引入非負的人工變量，以人工變量作為初始基變量，其對應的系數(shù)列向量構成單位陣，稱為“人造基”；然后用大M法或兩階段法求解；

線性規(guī)劃限制條件都是“≥”或“=”類型的約束——先將約束條件標準化，再引入非負的人工變量，2

等式約束左端引入人工變量的目的

使約束方程的系數(shù)矩陣中出現(xiàn)一個單位陣，用單位陣的每一個列向量對應的決策變量作為“基變量”，這樣，出現(xiàn)在單純形表格中的B(i)列（即約束方程的右邊常數(shù)）值正好就是基變量的取值。

等式約束左端引入人工變量的目的3①如果限制條件中既有“≤”類型的約束，又有“≥”或“=”類型的約束，怎么辦？構造單位陣

問題②初始可行基一定要選單位陣？b列正好就是基變量的取值，因此稱b列為解答列①如果限制條件中既有“≤”類型的約束，又有“≥”或“=”類型4（2）寫出初始基可行解——

令非基變量取0，基變量對應b(i)，一起構成初始基可行解（2）寫出初始基可行解——5此時LP的標準型為

運籌學課件單純形法的迭代原理6在約束條件中的變量系數(shù)矩陣中總會有一個單位矩陣初始可行基：當線性規(guī)劃的約束條件均為≤，其松弛變量的系數(shù)矩陣為單位矩陣；當線性規(guī)劃的約束條件均為≥或=，為便于找到初始基可行解，構造人工變量，人為產(chǎn)生一個單位矩陣。在約束條件中的變量系數(shù)矩陣中總會有一個單位矩陣當線性規(guī)劃的約7初始基本可行解：

式中p1,…,pm為基變量,同其所對應的x1,x2,…..,xm為基變量；其它變量xm+1,xm+2，……,xn為非基變量。令所有的非基變量等于零。初始基本可行解：式中p1,…,pm為基變量,同其所對應的8定義：兩個基可行解稱為相鄰的，如果它們之間變換且僅變換一個基變量。初始基可行解的前m個為基變量，2、基變換代入約束條件有定義：兩個基可行解稱為相鄰的，如果它們之間變換2、基變換代入9系數(shù)矩陣的增廣矩陣因為p1,…,pm,是一個基，其他向量pj可以這個基的線性組合表示：系數(shù)矩陣的增廣矩陣因為p1,…,pm,是一個基，其他向量pj10相減，然后乘上一個正數(shù)θ,加上經(jīng)過整理得到：找到滿足約束方程組的另一點：第j個大于0只變換1個變量；前m個變量必須換出1個相減，然后乘上一個正數(shù)θ,加上經(jīng)過整理得到：找到滿足約束方程11其中θ是X（1）的第j個坐標的值，要使X（1）是一個基可行解，對所有的i=1,…,m,存在令這m個不等式至少有一個等號成立，當其中θ是X（1）的第j個坐標的值，要使X（1）是一個基可行解12

是一個可行解。因為變量x11,x21,xl-11,xl+11,…………xm1,xj1所對應的向量，經(jīng)過重新排列后加行b列形成的增廣矩陣為：Lalj×(1/alj)=1rL×(-al-1j)+rL-10-(bL/aLj)+bL-1

13所以，P1,P2,…,Pl-1,Pj,Pl+1,…,Pm,是一個基。進行初等行變換，將第L行乘上1/alj,再分別乘以-aij,(i=1,…,l-1,l+1,…,m)加到各行，增廣矩陣的左邊變成一個單位矩陣，所以，P1,P2,…,Pl-1,Pj,Pl+1,…,Pm,是14３、最優(yōu)性檢驗和解的判別將代入目標函數(shù)計算：３、最優(yōu)性檢驗和解的判別將代入目標函數(shù)計算：15最優(yōu)性判別１、如果所有的檢驗數(shù)，表明現(xiàn)有的頂點對應的基可行解為最優(yōu)解。２、當所有的檢驗數(shù)，又對某個非基變量xj的檢驗數(shù)等于０，并且可以找到>0,這表明可以找到一個頂點目標函數(shù)達到最大，說明LP有無窮多個最優(yōu)解。３、如果存在某個檢驗數(shù)>0,又≤0,表明目標函數(shù)達到無限，說明LP有無界解。最優(yōu)性判別１、如果所有的檢驗數(shù)，表明現(xiàn)有的頂點對應的基16

第四節(jié)單純形法計算步驟第一步：求初始基可行解，列出初始單純形表。

將LP化為標準型，并加以整理。引入適當?shù)乃神Y變量、剩余變量和人工變量，使約束條件化為等式，并且約束方程組的系數(shù)陣中有一個單位陣。第四節(jié)單純形法計算步驟第一步：求初始基可行解，列出初始17cjc1…cm…cj…cnCB基bx1…xm…xj…xnc1c2.cmx1x2.xmb1b2.bm10.000.1a1ja2j.amja1na2n.amn

cj-zj0…0…cjc1…cm…cj…cnCB基bx1…xm…xj18第二步：最優(yōu)性檢驗計算檢驗數(shù)，檢查：所有檢驗數(shù)是否≤0？

是——結(jié)束，寫出最優(yōu)解和目標函數(shù)最優(yōu)值；還有正檢驗數(shù)——檢查相應系數(shù)列≤0？是——結(jié)束，該LP無界解。不屬于上述兩種情況，轉(zhuǎn)入下一步—基變換。確定是停止迭代還是轉(zhuǎn)入基變換？第二步：最優(yōu)性檢驗19

選擇（最大）正檢驗數(shù)對應的系數(shù)列為主元列，主元列對應的非基變量xk為換入變量；最小比值對應的行為主元行，主元行對應的基變量xl為換出變量。主元行和主元列的交叉元素alk稱為主元素。第三步：基變換選擇（最大）正檢驗數(shù)第三步：基變換20

利用矩陣的初等行變換把主元列變成單位向量，主元素變?yōu)?，進基變量對應的檢驗數(shù)變成0，從而得到一張新的單純形表，返回第二步。完成一次迭代，得到新的基可行解和相應的目標函數(shù)值利用矩陣的初等行變換把主元列變成單位向量，主元素變?yōu)?1該迭代過程直至下列情況之一發(fā)生時停止檢驗數(shù)行全部變?yōu)榉钦?；（得到最?yōu)解）或主元列≤0（無界）

該迭代過程直至下列情況之一發(fā)生時停止22例題：使用單純形法求解線性規(guī)劃問題解：化成標準形式例題：使用單純形法求解線性規(guī)劃問題解：化成標準形式23其約束條件系數(shù)矩陣的增廣矩陣為p3,p4,p5構成單位矩陣，對應的基變量x3,x4,x5,令非基變量x1,x2=0,找到一個初始基可行解X=(0,0,15,24,5)T,以此列出初始單純形表其約束條件系數(shù)矩陣的增廣矩陣為p3,p4,p5構成單位矩陣24Cj21000CB基bX1X2X3X4X50X315051000X424620100X5511001σj=Cj-Zj=Cj-(C1a1j+C2a2j+…+Cmamj)21000σ1=2-(0×0+0×6+0×1)=2;σ2=1-(0×5+0×2+0×1)=1σ3=0-(0×1+0×0+0×1)=0;σ4=0-(0×0+0×1+0×1)=0σ5=0-(0×0+0×0+0×1)=0

Cj21000CB基bX1X2X3X4X50X315051025檢驗數(shù)σ1和σ2均大于0，所以表中的基可行解不是最優(yōu)解。σ1>σ2，選擇最大正檢驗數(shù)對應的系數(shù)列為主元列，主元列對應的非基變量X1為換入變量；，檢驗數(shù)σ1和σ2均大于0，所以表中的基可行解不是最優(yōu)解。σ126Cj21000CB基bX1X2X3X4X50X315051000X424[6]20100X5511001σj=Cj-Zj=Cj-(C1a1j+C2a2j+…+Cmamj)21000θ最小比值對應的行為主元行，主元行對應的基變量X4為換出變量。得到一個新的基P3,P1,P5，列出新的單純形表，繼續(xù)計算。

x12142/601/60014/601-1/601/30-1/30Cj21000CB基bX1X2X3X4X50X315051027Cj21000CB基bX1X2X3X4X50X315051002X1412/601/600X510[4/6]0-1/61σj=Cj-Zj=Cj-(C1a1j+C2a2j+…+Cmamj)01/30-1/30σ2最大，X2為進基變量；x21106/40-1/43/2017/201/4-1/20015/215/4-15/2000-1/4-1/2Cj21000CB基bX1X2X3X4X50X315051028X5為出基變量。P2,P3,P1一個新的基,列出新的單純形表，繼續(xù)計算。Cj21000CB基bX1X2X3X4X50X315/20015/4-15/22X17/21001/4-1/21X23/2010-1/43/2σj=Cj-Zj=Cj-(C1a1j+C2a2j+…+Cmamj)000-1/4-1/2X5為出基變量。P2,P3,P1一個新的基,列出新的單純形29σ1=0σ2=0σ3=0σ4=0-(0×5/4+2×1/4-1×1/4)=-1/4σ5=0-(-0×15/2-2×1/2+1×3/2)=-1/2所有的σ≤0，基變量不含有人工變量，所以可行解X=(7/2,3/2,15/2,0,0)T為最優(yōu)解，代入目標函數(shù)得到Z=8.5σ1=0所有的σ≤0，基變量不含有人工變量，30小結(jié)1、線性規(guī)劃單純形法基本原理。2、單純形法計算步驟。作業(yè)1.3(1)1.4(1)小結(jié)1、線性規(guī)劃單純形法基本原理。作業(yè)31四、單純形法的迭代原理

1、確定初始基可行解

(1)初始可行基的確定

觀察法——觀察系數(shù)矩陣中是否含有現(xiàn)成的單位陣？LP限制條件中全部是“≤”類型的約束——將新增的松弛變量作為初始基變量，對應的系數(shù)列向量構成單位陣；四、單純形法的迭代原理32

先將約束條件標準化，再引入非負的人工變量，以人工變量作為初始基變量，其對應的系數(shù)列向量構成單位陣，稱為“人造基”；然后用大M法或兩階段法求解；

線性規(guī)劃限制條件都是“≥”或“=”類型的約束——先將約束條件標準化，再引入非負的人工變量，33

等式約束左端引入人工變量的目的

使約束方程的系數(shù)矩陣中出現(xiàn)一個單位陣，用單位陣的每一個列向量對應的決策變量作為“基變量”，這樣，出現(xiàn)在單純形表格中的B(i)列（即約束方程的右邊常數(shù)）值正好就是基變量的取值。

等式約束左端引入人工變量的目的34①如果限制條件中既有“≤”類型的約束，又有“≥”或“=”類型的約束，怎么辦？構造單位陣

問題②初始可行基一定要選單位陣？b列正好就是基變量的取值，因此稱b列為解答列①如果限制條件中既有“≤”類型的約束，又有“≥”或“=”類型35（2）寫出初始基可行解——

令非基變量取0，基變量對應b(i)，一起構成初始基可行解（2）寫出初始基可行解——36此時LP的標準型為

運籌學課件單純形法的迭代原理37在約束條件中的變量系數(shù)矩陣中總會有一個單位矩陣初始可行基：當線性規(guī)劃的約束條件均為≤，其松弛變量的系數(shù)矩陣為單位矩陣；當線性規(guī)劃的約束條件均為≥或=，為便于找到初始基可行解，構造人工變量，人為產(chǎn)生一個單位矩陣。在約束條件中的變量系數(shù)矩陣中總會有一個單位矩陣當線性規(guī)劃的約38初始基本可行解：

式中p1,…,pm為基變量,同其所對應的x1,x2,…..,xm為基變量；其它變量xm+1,xm+2，……,xn為非基變量。令所有的非基變量等于零。初始基本可行解：式中p1,…,pm為基變量,同其所對應的39定義：兩個基可行解稱為相鄰的，如果它們之間變換且僅變換一個基變量。初始基可行解的前m個為基變量，2、基變換代入約束條件有定義：兩個基可行解稱為相鄰的，如果它們之間變換2、基變換代入40系數(shù)矩陣的增廣矩陣因為p1,…,pm,是一個基，其他向量pj可以這個基的線性組合表示：系數(shù)矩陣的增廣矩陣因為p1,…,pm,是一個基，其他向量pj41相減，然后乘上一個正數(shù)θ,加上經(jīng)過整理得到：找到滿足約束方程組的另一點：第j個大于0只變換1個變量；前m個變量必須換出1個相減，然后乘上一個正數(shù)θ,加上經(jīng)過整理得到：找到滿足約束方程42其中θ是X（1）的第j個坐標的值，要使X（1）是一個基可行解，對所有的i=1,…,m,存在令這m個不等式至少有一個等號成立，當其中θ是X（1）的第j個坐標的值，要使X（1）是一個基可行解43

是一個可行解。因為變量x11,x21,xl-11,xl+11,…………xm1,xj1所對應的向量，經(jīng)過重新排列后加行b列形成的增廣矩陣為：Lalj×(1/alj)=1rL×(-al-1j)+rL-10-(bL/aLj)+bL-1

44所以，P1,P2,…,Pl-1,Pj,Pl+1,…,Pm,是一個基。進行初等行變換，將第L行乘上1/alj,再分別乘以-aij,(i=1,…,l-1,l+1,…,m)加到各行，增廣矩陣的左邊變成一個單位矩陣，所以，P1,P2,…,Pl-1,Pj,Pl+1,…,Pm,是45３、最優(yōu)性檢驗和解的判別將代入目標函數(shù)計算：３、最優(yōu)性檢驗和解的判別將代入目標函數(shù)計算：46最優(yōu)性判別１、如果所有的檢驗數(shù)，表明現(xiàn)有的頂點對應的基可行解為最優(yōu)解。２、當所有的檢驗數(shù)，又對某個非基變量xj的檢驗數(shù)等于０，并且可以找到>0,這表明可以找到一個頂點目標函數(shù)達到最大，說明LP有無窮多個最優(yōu)解。３、如果存在某個檢驗數(shù)>0,又≤0,表明目標函數(shù)達到無限，說明LP有無界解。最優(yōu)性判別１、如果所有的檢驗數(shù)，表明現(xiàn)有的頂點對應的基47

第四節(jié)單純形法計算步驟第一步：求初始基可行解，列出初始單純形表。

將LP化為標準型，并加以整理。引入適當?shù)乃神Y變量、剩余變量和人工變量，使約束條件化為等式，并且約束方程組的系數(shù)陣中有一個單位陣。第四節(jié)單純形法計算步驟第一步：求初始基可行解，列出初始48cjc1…cm…cj…cnCB基bx1…xm…xj…xnc1c2.cmx1x2.xmb1b2.bm10.000.1a1ja2j.amja1na2n.amn

cj-zj0…0…cjc1…cm…cj…cnCB基bx1…xm…xj49第二步：最優(yōu)性檢驗計算檢驗數(shù)，檢查：所有檢驗數(shù)是否≤0？

是——結(jié)束，寫出最優(yōu)解和目標函數(shù)最優(yōu)值；還有正檢驗數(shù)——檢查相應系數(shù)列≤0？是——結(jié)束，該LP無界解。不屬于上述兩種情況，轉(zhuǎn)入下一步—基變換。確定是停止迭代還是轉(zhuǎn)入基變換？第二步：最優(yōu)性檢驗50

選擇（最大）正檢驗數(shù)對應的系數(shù)列為主元列，主元列對應的非基變量xk為換入變量；最小比值對應的行為主元行，主元行對應的基變量xl為換出變量。主元行和主元列的交叉元素alk稱為主元素。第三步：基變換選擇（最大）正檢驗數(shù)第三步：基變換51

利用矩陣的初等行變換把主元列變成單位向量，主元素變?yōu)?，進基變量對應的檢驗數(shù)變成0，從而得到一張新的單純形表，返回第二步。完成一次迭代，得到新的基可行解和相應的目標函數(shù)值利用矩陣的初等行變換把主元列變成單位向量，主元素變?yōu)?2該迭代過程直至下列情況之一發(fā)生時停止檢驗數(shù)行全部變?yōu)榉钦?；（得到最?yōu)解）或主元列≤0（無界）

該迭代過程直至下列情況之一發(fā)生時停止53例題：使用單純形法求解線性規(guī)劃問題解：化成標準形式例題：使用單純形法求解線性規(guī)劃問題解：化成標準形式54其約束條件系數(shù)矩陣的增廣矩陣為p3,p4,p5構成單位矩陣，對應的基變量x3,x4,x5,令非基變量x1,x2=0,找到一個初始基可行解X=(0,0,15,24,5)T,以此列出初始單純形表其約束條件系數(shù)矩陣的增廣矩陣為p3,p4,p5構成單位矩陣55Cj21000CB基bX1X2X3X4X50X315051000X424620100X5511001σj=Cj-Zj=Cj-(C1a1j+C2a2j+…+Cmamj)21000σ1=2-(0×0+0×6+0×1)=2;σ2=1-(0×5+0×2+0×1)=1σ3=0-(0×1+0×0+0×1)=0;σ4=0-(0×0+0×1+0×1)=0σ5=0-(0×0+0×0+0×1)=0

Cj21000CB基bX1X2X3X4X50X315051056檢驗數(shù)σ1和σ2均大于0，所以表中的基可行解不是最優(yōu)解。σ1>σ2，選擇最大正檢驗數(shù)對應的系數(shù)列為主元列，主元列對應的非基變量X1為換入變量；，檢驗數(shù)σ1和σ2均大于0，所以表中的基可行解不是最優(yōu)解。σ157Cj21000CB基bX1X2X3X4X50X315051000X424[6]20100X5511001σj=Cj-Zj=Cj-(C1a1j+C2a2j+…+Cmamj)21000θ最小比值對應的行為主元行，主元行對應的基變量X4為換出變量。得到一個新的基P3