管理學(xué)管理運(yùn)籌學(xué)單純形法課件

此法是求解線性規(guī)劃問題的一種有效方法本章的學(xué)習(xí)內(nèi)容：§1、單純形法的基本思路和原理§2、單純形法的表格形式§3、求目標(biāo)函數(shù)值最小的問題的單純形表解法4、幾種特殊情況

第五章單純形法

圖解法只能解決僅含有兩個(gè)決策變量的線性規(guī)劃的問題，對多于兩個(gè)決策變量的線性規(guī)劃問題，圖解法就顯得無能為力了。在這一章里將介紹由美國數(shù)學(xué)家丹捷格(G·B·Dantgig)1947提出的，得到最廣泛應(yīng)用的線性規(guī)劃的代數(shù)算法——單純形法，這恐怕是在運(yùn)籌學(xué)發(fā)展史上最輝煌的一筆，此算法是對運(yùn)籌學(xué)算法的一次革命。在第三章所介紹的線性規(guī)劃問題的計(jì)算機(jī)解法就是基于單純形法原理來編程的。它可解決多個(gè)變量線性規(guī)劃問題。在后來研究上還發(fā)明其它求解線性規(guī)劃的方法,如前蘇聯(lián)科學(xué)家發(fā)明的內(nèi)點(diǎn)法、印度科學(xué)家發(fā)明的K算法等。

單純形法的基本思路：從可行域中某一個(gè)頂點(diǎn)開始，判斷此頂點(diǎn)是否是最優(yōu)解，如不是則再找另一個(gè)使得其目標(biāo)函數(shù)值更優(yōu)的頂點(diǎn)，稱之為迭代，再判斷此點(diǎn)是否是最優(yōu)解。直到找到一個(gè)頂點(diǎn)為其最優(yōu)解，就是使得其目標(biāo)函數(shù)值最優(yōu)的解，或者能判斷出線性規(guī)劃問題無最優(yōu)解為止。在這里，可行域的頂點(diǎn)已不再像圖解法中那樣直接可見了。在單純形法中的可行域的頂點(diǎn)叫做基本可行解，第一個(gè)找到的可行域的頂點(diǎn)叫做初始基本可行解。下面通過第二章例1來介紹單純形法?！?.1單純形法的基本思路和原理在第二章的例1中我們得到以下數(shù)學(xué)模型：目標(biāo)函數(shù)：maxZ=50X1+100X2約束條件：X1+X2≤300，2X1+X2≤400，X2≤250,X1≥0,X2≥0.加上松弛變量后得到如下標(biāo)準(zhǔn)型：目標(biāo)函數(shù)：maxZ=50X1+100X2

約束條件：X1+X2+S1=300,2X1+X2+S2=400,X2+S3=250,X1,X2,S1,S2,S3≥0一、找出一個(gè)初始基本可行解（可行域邊界上一個(gè)點(diǎn)）其中pj為系數(shù)矩陣A中第j列的向量。由于在A中存在一個(gè)不為零的三階子式，可知A的秩為3。因?yàn)锳的秩m小于此方程組的變量的個(gè)數(shù)n，從線性代數(shù)的知識可知其有無數(shù)多組解。為了找到一個(gè)初始基本可行解，先介紹一些線性規(guī)劃的基本概念。則約束條件組成的線性方程組的系數(shù)矩陣為：基：已知A是約束條件的m×n系數(shù)矩陣，其秩為m。若B是A中m×m階非奇異子矩陣(即可逆矩陣，｜B｜≠0)，則稱B是線性規(guī)劃問題中的一個(gè)基。也即任一m階的可逆矩陣都可作為基。

基向量：基B中的每一列即稱為一個(gè)基向量?；鵅中共有m個(gè)基向量，在此例中對于基B來說，三個(gè)列向量都是基向量，而且B只有這三個(gè)基向量。非基向量：在A中除了基B之外的每一列稱之為基B的非基向量?；兞浚号c基向量pi相應(yīng)的變量Xi叫基變量，基變量有m個(gè)，在此例題中X1，X2，S1都是B1的基變量，而S1，S2，S3是B2的基變量。

非基變量：與非基向量pj相應(yīng)的變量Xj叫非基變量，非基變量有n-m個(gè)，在此例題中，S2，S3是B1的非基變量。而X1，X2是B2的非基變量。基本解：由線性代數(shù)知識得：如果在約束方程組系數(shù)矩陣中找到一個(gè)基，令這個(gè)基的非基變量為零。再求解這個(gè)方程組就可得到唯一解了，這個(gè)解稱為線性規(guī)劃的基本解?？尚薪猓簼M足：最優(yōu)解：滿足目標(biāo)函數(shù)：maxZ=50X1+100X2

的可行解稱為最優(yōu)解。的解稱為可行解（注意包括了非負(fù)）。X1+X2+S1=3002X1+X2+S2=400X2+S3=250X1,X2,S1,S2,S3≥0由于在這個(gè)基本解中S1=-100，S3=-150，不滿足該線性規(guī)劃S1≥0，S3≥0的約束條件，顯然不是問題的可行解。X1+X2+S1=3002X1+X2+S2=400X2+S3=250X2+S1=300X2=400X2+S3=250一個(gè)基本解可以是可行解，也可以不是可行解。它們之間主要區(qū)別在于其所有變量的解是否滿足非負(fù)條件。把滿足非負(fù)條件的一個(gè)基本解叫做基本可行解，并把這樣的基叫做可行基。

可行解、基本解、基本可行解和最優(yōu)解的關(guān)系：可行解基本解基本可行解非可行解最優(yōu)解關(guān)于基本解，可行解和基本可行解的概念：注意首先要把模型變成標(biāo)準(zhǔn)型再判斷?？尚薪猓簼M足約束條件（包括非負(fù)性）的解稱為可行解，但不一定含有基?；窘猓赫页鲆粋€(gè)基，令非基變量為0，再求出解，此解不一定滿足非負(fù)性?；究尚薪猓杭葷M足非負(fù)性又滿足基本解的解稱為基本可行解。

由于所有變量的解都大于等于零，可知此基本解是基本可行解。所以

是可行基。

判斷一個(gè)基是否是可行基，只有在求出其基本解以后，當(dāng)其基本解所有變量的解都大于等于零，才能斷定這個(gè)解是基本可行解，這個(gè)基是可行基。那么能否在求解之前就找到一個(gè)可行基呢?也就是說你找到的一個(gè)可行基能否保證在求解之后得到的解一定是基本可行解嗎？當(dāng)然可以啊，如果找到一個(gè)基是單位矩陣，或者說一個(gè)基是由單位矩陣的各列向量所組成，則所求得的基本解一定是基本可行解！由于在線性規(guī)劃的標(biāo)準(zhǔn)型中要求bj都大于等于零，如果找到一個(gè)基是單位矩陣，或者說一個(gè)基是由單位矩陣的各列向量所組成(至于各列向量的前后順序是無關(guān)緊要的事),例如:那么所求得的基本解一定是基本可行解，這個(gè)單位矩陣或由單位矩陣各列向量組成的基一定是可行基，為什么呢？加上非基變量X1=0，X2=0，就得到了該線性規(guī)劃的一個(gè)基本可行解：X1=0,X2=0,S1=300,S2=400,S3=250.

實(shí)際上這個(gè)基本可行解中的各個(gè)變量或等于某個(gè)bj或等于零。在本例題中就找到了一個(gè)基是單位矩陣:令B2的非基變量x1，x2為零，則：X1+X2+S1=3002X1+X2+S2=400X2+S3=250S1=300S2=400S3=250像這樣在第一次找可行基時(shí)，所找到的基或?yàn)閱挝痪仃嚮驗(yàn)橛蓡挝痪仃嚨母髁邢蛄克M成，稱之為初始可行基，其相應(yīng)的基本可行解叫初始基本可行解。如果找不到單位矩陣或由單位矩陣的各列向量組成的基作為初始可行基，我們將構(gòu)造初始可行基，具體做法在以后詳細(xì)講述。

這就是單純形法的第一步。注解

所謂最優(yōu)性檢驗(yàn)就是判斷已求得的基本可行解是否是最優(yōu)解。1．最優(yōu)性檢驗(yàn)的依據(jù)——檢驗(yàn)數(shù)σj

一般來說目標(biāo)函數(shù)中既包括基變量，又包括非基變量。現(xiàn)在要求只用非基變量來表示目標(biāo)函數(shù)，這只要在約束等式中通過移項(xiàng)等處理就可以用非基變量來表示基變量，然后將非基變量的表示式代入目標(biāo)函數(shù)中，這樣目標(biāo)函數(shù)中只含有非基變量了，或者說目標(biāo)函數(shù)中基變量的系數(shù)都為零了。此時(shí)目標(biāo)函數(shù)中所有變量的系數(shù)稱為各變量的檢驗(yàn)數(shù)，把變量Xj的檢驗(yàn)數(shù)記為σj；

顯然所有基變量的檢驗(yàn)數(shù)必為零（因?yàn)榛兞恳驯环腔兞看媪耍６?、最?yōu)性檢驗(yàn)

則非基變量為X1，X2。由于初始可行解中X1，X2為非基變量，所以此目標(biāo)函數(shù)已經(jīng)用非基變量表示了，不需要用約束條件代換出基變量了。這樣可知σ1=50,σ2=100,σ3=0,σ4=0,σ5=0。在本例題中目標(biāo)函數(shù)為50X1+100X2。如果取基變量為：如果取基變量為B1：為求得檢驗(yàn)數(shù)，通過移項(xiàng)等處理就可以用非基變量來表示基變量，基變量為X1、S1、S3，則非基變量為X2、S2。故在目標(biāo)函數(shù)為Z=50X1+100X2中，只需將X1換為X2及S2的表達(dá)式即可。在約束條件X1+X2+S1=300，2X1+X2+S2=400，X2+S3=250只將二式變?yōu)閄1=200-X2/2-S2/2代入目標(biāo)函數(shù)得：Z=1000+75X2-25S2，可知σ1=0,σ2=75,σ3=0,σ4=-25,σ5=0。

其中，z0為常數(shù)項(xiàng)，J是所有非基變量的下標(biāo)集。由于所有的xj的取值范圍為大于等于零，當(dāng)所有的σj都小于等于零時(shí)，則∑σjXj≤0，要使目標(biāo)函數(shù)（1）式的值最大，顯然只有當(dāng)∑σjXj

為零才最大。即把這些Xj取為非基變量(即令這些Xj的值為零)，所求得的基本可行解就使目標(biāo)函數(shù)值最大為z0。2.最優(yōu)解判別定理在求最大值目標(biāo)函數(shù)的問題中，對于某個(gè)基本可行解，如果所有檢驗(yàn)數(shù)σj≤0，則這個(gè)基本可行解是最優(yōu)解。下面來解釋最優(yōu)解判別定理。設(shè)用非基變量表示的目標(biāo)函數(shù)為如下形式

由于σ1=50，σ2=100都大于零，顯然這個(gè)基本可行解不是最優(yōu)解，實(shí)際上讓X1，X2為非基變量(即令其值為0)是最失策的，X1,X2在大于等于零的范圍內(nèi)，X1，X2不管取什么值也比其取零值要好，就能使得目標(biāo)函數(shù)Z的值比零更大。所以要找更好的基本可行解。而對于第二種情況取基變量為X1、S1、S3，檢驗(yàn)數(shù)為σ1=0,σ2=75,σ3=0,σ4=-25,σ5=0。也不是都小于等于0,也不是最優(yōu)解。

對于求目標(biāo)函數(shù)最小值的情況，只需把上述的定理中的σj≤0，改為σj≥0即可。至于如何來判斷無最優(yōu)解的方法將在后面用具體實(shí)例予以闡述。在本例題中當(dāng)取基變量為

下面介紹如何進(jìn)行基變換找到一個(gè)新的可行基，具體的做法是從可行基中換一個(gè)列向量，得到一個(gè)新的可行基，使得求解得到的新的基本可行解，使得其目標(biāo)函數(shù)值更優(yōu)。為了換基就要確定換入變量與換出變量。

三、基變換x1x2基變換的實(shí)質(zhì)就是從一個(gè)頂點(diǎn)換到另一個(gè)頂點(diǎn)。

從最優(yōu)解判別定理知道，當(dāng)某個(gè)σj>0時(shí)，非基變量xj變?yōu)榛兞浚床蝗×阒担┛梢允鼓繕?biāo)函數(shù)值增大，故我們要選基檢驗(yàn)數(shù)大于0的非基變量換到基變量中去(稱之為入基變量)。若有兩個(gè)以上的σj>0，則為了使目標(biāo)函數(shù)增加得更大些，一般選其中的σj最大者的非基變量為入基變量，在本例題中σ2=

100是檢驗(yàn)數(shù)中最大的正數(shù)，故選X2為入基變量。1．入基變量的確定

求得基本解：X1=0,X2=300,S1=0,S2=100,S3=-50.顯然這不是基本可行解，因?yàn)镾3<0,

所以S1不能作為出基變量。2．出基變量的確定在確定了X2為入基變量之后，要在原來的3個(gè)基變量S1,S2,S3中確定一個(gè)出基變量，也就是確定哪一個(gè)基變量變成非基變量呢?如果確定S1為出基變量，則新的基變量為X2,S2,S3，因?yàn)榉腔兞縓1=S1=0，則：X1+X2+S1=3002X1+X2+S2=400X2+S3=250X2=300X2+S2=400X2+S3=250如果把s3作為出基變量呢？

求得基本解：X1=0,X2=250,S1=50,S2=150,S3=0.

因?yàn)榇私鉂M足非負(fù)條件，是基本可行解，故s3可以確定為出基變量。同學(xué)們可試試能否把S2作為出基變量？（不能因?yàn)榇藭r(shí)解為X1=S2=0,S1=-100,S3=-150,X2=400）則新的基變量為X2,S1,S2，因?yàn)榉腔兞縓1=S3=0，則從下式：X1+X2+S1=3002X1+X2+S2=400X2+S3=250X2=300X2+S1=400X2+S2=250

以下就來看在找出了初始基本可行解和確定了入基變量之后，怎么樣的基變量可以確定為出基變量呢?確定出基變量的方法：把已確定的入基變量在各約束方程中的正的系數(shù)除其所在約束方程中的常數(shù)項(xiàng)的值，把其中最小比值所在的約束方程中的原基變量確定為出基變量。這樣在下一步迭代的矩陣變換中可以確保新得到的bj值都大于等于零。

能否在求出基本解以前來確定出基變量呢?證明過程略。詳情見P77-P80?。≈匾?/p>

在本例題中約束方程為

X1+X2+S1=

300，2X1+X2+S2=400，X2+S3=250

在第二步中已經(jīng)知道X2為入基變量，把各約束方程中X2的為正的系數(shù)除對應(yīng)的常量，得：

b1/a12=300/1=300,b2/a22=400/1=400,b3/a32=250/1=250

其中a12,a22,a32分別為X2所在約束方程的正系數(shù)，

b1,b2b3分別對應(yīng)約束方程常數(shù)項(xiàng)的值。其中b3/a32的值最小，所以可以知道在原基變量中系數(shù)向量為e3=(0，0，1)′的基變量S3為出基變量，這樣可知X2,S1，S2為基變量，X1，S3為非基變量。令非基變量為零，得：

X2+S1=

300，X2+S2=400，

X2=250求得新的可行解：X1=0,X2=250,S1=50,S2=150.

這時(shí)目標(biāo)函數(shù)值為50X1+l00X2=50×0+100×250=25000，顯然比初始基本可行解X1=0，X2=0，S1=300，S2=400，S3=250時(shí)的目標(biāo)函數(shù)值50×0+100×0=0要好得多。下面我們再進(jìn)行檢驗(yàn)其最優(yōu)性，不是最優(yōu)解還要繼續(xù)進(jìn)行基變換，直至找到最優(yōu)解，或者能夠判斷出線性規(guī)劃無最優(yōu)解為止。為了使單純形法更加簡潔明了下面用表格來做。此表稱為單純形法表。

在講單純形法的表格形式之前，先從一般數(shù)學(xué)模型里推導(dǎo)出檢驗(yàn)數(shù)σj的表達(dá)式?？尚谢鶠閙階單位矩陣的線性規(guī)劃模型如下(假設(shè)其系數(shù)矩陣的前m列是單位矩陣)：

maxz=c1x1+c2x2+…+cnxn

x1+a1,m+1xm+1+…+a1,nxn=b1,

x2+a2,m+1xm+1+…+a2,nxn=b2,………………

xm+am,m+1xm+1+…+am,nxn=bm,

xj≥0,(j=1,2,…,n)

以下用Xi

(i=1，2，…，m)表示基變量，用Xj(j=m+1,m+2,…,n)表示非基變量?！?.2單純形法的表格形式把第i個(gè)約束方程移項(xiàng)，就可用非基變量表示基變量:

單純形法的表格形式是把用單純形法求出基本可行解、檢驗(yàn)其最優(yōu)性、迭代某步驟都用表格的方式來計(jì)算求出，其表格的形式有些像增廣矩陣，而其計(jì)算的方法也大體上使用矩陣的行的初等變換。以下用單純形表格來求解第二章的例1。1、max50X1+100X2+0S1+0S2+0S3，X1+X2+S1=300,2X1+X2+S2=400,X2+S3=250,X1,X2,S1,S2,S3≥0把上面的數(shù)據(jù)填入如下的單純形表格迭代次數(shù)基變量CBX1X2S1S2S3b比值

bi/ai2

501000000S1S2

S3

000

111002101001001

300400250

Zj

σj=Cj-Zj

max50X1+100X2+0S1+0S2+0S3，X1+X2+S1=300,2X1+X2+S2=400,X2+S3=250,基變量S1、S2、S3的順序不能填錯(cuò)，在S1,S2,S3

的右邊CB列中填入這些變量在目標(biāo)函數(shù)中的系數(shù)。在Zj行中填入各列的∑Ci

a

ij的值，也就是把系數(shù)矩陣的第j列與CB列中對應(yīng)元素相乘相加所得的值，如Z2=0×1+0×1+0×1=0，所在Zj行中的第2位數(shù)填入0。迭代次數(shù)基變量CBX1X2S1S2S3b比值

bi/ai2

501000000S1S2

S3

000

111002101001001

300400250

Zj

σj=Cj-Zj

00000Z=0

50100000在σj=Cj–Zj，則σ1=50-0=50,σ2=100,σ3=0,σ4=0,σ5=0，Z值表示把初始基本可行解代入目標(biāo)函數(shù)所得的函數(shù)值。Z的值就等于約束方程的常數(shù)項(xiàng)bi乘以此約束方程的基變量在目標(biāo)函數(shù)中的系數(shù)之和，Z=300×0+400×0+250×0=0，故Z=0。迭代次數(shù)基變量CBX1X2S1S2S3b比值

bi/ai2

501000000S1S2

S3

000

111002101001001

300400250

Zj

σj=Cj-Zj

00000Z=0

50100000填完了此表，得初始基本可行解，S1=300，S2=400，S3=250，X1=0，X2=0，(因X1，X2是非基變量，非基變量取零值)，其目標(biāo)函數(shù)值Z=0，同時(shí)在σj=Cj

–Zj一欄中可知σ1=50，σ2=100，σ3=σ4=σ5=0?？芍@個(gè)基本可行解不是最優(yōu)解（因?yàn)闄z驗(yàn)數(shù)>0)，迭代次數(shù)基變量CBX1X2S1S2S3b比值

bi/ai2

501000000S1S2

S3

000

111002101001001

300400250

Zj

σj=Cj-Zj

00000Z=0

50100000迭代次數(shù)基變量CBX1X2S1S2S3b比值

bi/ai2

501000000S1S2

S3

000

111002101001001

300400250

Zj

σj=Cj-Zj

00000Z=0

50100000想想，如何進(jìn)行迭代？為什么選取X2作為入基變量？迭代次數(shù)基變量CBX1X2S1S2S3b比值

bi/ai2

501000000S1S2

S3

000

111002101001001

300400250300/1400/1250/1

Zj

σj=Cj-Zj

00000Z=0

50100000你怎么知道S3為出基變量?。喀?2=1叫主元？郁悶！迭代次數(shù)基變量CBX1X2S1S2S3b

501000001S1S2

X2

00100

01001

250

Zj

σj=Cj-Zj

迭代迭代迭代迭代迭代3行×(-1)+2行3行×(-1)+1行150-15000201-110111100300210104000100125050/1150/2比值

bi/ai201000010050000-100Z=25000又從σ1=50>0可知這個(gè)基本可行解也不是最優(yōu)解。從σj我們知道σ1為最大的正數(shù)，可知X1為入基變量，從此值可知b1/a11=50為bi/ai1中最小的正數(shù)，可知S1為出基變量，a11為主元，這樣我們可以進(jìn)行第2次迭代后得下表：迭代次數(shù)基變量CBX1X2S1S2S3b比值

bi/ai2

501000002X1S2

X2

500100

1010-1

00-21101001

505025050/1150/2

Zj

σj=Cj-Zj

5010050050

00-500-50Z=27500

從表中可知基本可行解為X1=50，X2=250，S1=0,S2=50,S3=0，這時(shí)Z=27500。由于檢驗(yàn)σj都小于等于零，此基本可行解為最優(yōu)解，Z=27500為最優(yōu)目標(biāo)函數(shù)值。迭代次數(shù)基變量CBX1X2S1S2S3b比值

bi/ai2

501000002X1S2

X2

500100

1010-1

00-21101001

505025050/1150/2

Zj

σj=Cj-Zj

5010050050

00-500-50Z=27500第二章例2的數(shù)學(xué)模型如下：目標(biāo)函數(shù):minf=2X1+3X2.

約束條件：X1+X2≥350，

X1≥125，

2X1+X2≤600，X1，X2≥0．

其約束條件的標(biāo)準(zhǔn)型如下：

X1+X2-S1=350，X1-S2=125，2X1+X2+S3=600，X1，X2,,S1,S2，S3≥0．§5.3求目標(biāo)函數(shù)值最小的線性規(guī)劃問題的單純形表解法至于目標(biāo)函數(shù)，在標(biāo)準(zhǔn)型中并不一定要求求最大值或最小值，但是為了使單純形表解法有一個(gè)統(tǒng)一的解法，我們把所有求目標(biāo)函數(shù)最小值的問題化成求目標(biāo)函數(shù)最大值的問題。具體做法只要把目標(biāo)函數(shù)乘以(-1)，就把原來求目標(biāo)函數(shù)最小值的問題化成了求目標(biāo)函數(shù)最大值的問題。本例題的目標(biāo)函數(shù)就化為了：目標(biāo)函數(shù)：max(-f)=-2X1-X2．為了統(tǒng)一符號，不妨設(shè)Z=-f，這樣目標(biāo)函數(shù)就寫成:maxZ=-2X1-3X2在標(biāo)準(zhǔn)型的約束方程的系數(shù)矩陣?yán)铮也坏?階單位陣或單位向量

。注意負(fù)的單位向量與單位向量是不同的，用負(fù)的單位向量作基向量求得的基本解一般不滿足非負(fù)條件，不是可行解。這樣我們就分別在第1、第2個(gè)約束方程中加上人工變量a1,a2(aartificial的第一個(gè)字母)，這樣的約束條件就變成了如下的形式：

X1+X2-S1+a1=350，X1-S2+a2=125，2X1+X2+S3=600，X1，X2,,S1,S2,a1,a2≥0．這樣在約束方程的系數(shù)矩陣中就可找到單位向量e3，e1，e2了,這時(shí)可知基變量為s3,a1,a2，初始基本可行解為X1=0,X2=0,S1=0,S2=0,S3=600,a1=350,a2=125.人工變量的含義

人工變量是與松弛、剩余變量不同的。松弛變量、剩余變量它們可以取零值，也可以取正值，而人工變量只能取零值。一旦人工變量取正值，則有人工變量的約束方程和原始的約束方程就不等價(jià)了，這樣所求得的解就不是原線性規(guī)劃的解了。為了保證人工變量為零，規(guī)定人工變量在目標(biāo)函數(shù)中的系數(shù)為-M，這里M為任意大的數(shù)。這樣只要人工變量>0，所求的目標(biāo)函數(shù)最大值就是一個(gè)任意小的數(shù)。這樣為了使目標(biāo)函數(shù)實(shí)現(xiàn)最大就必須把人工變量從基變量中換出。如果一直到最后，人工變量仍不能從基變量中換出，即人工變量仍不為零，則該問題無可行解。這樣此例的目標(biāo)函數(shù)就寫為：maxZ=-2X1-3X2-Ma1-Ma2此例的數(shù)學(xué)模型如下所示：maxz=-2X1-3X2-Ma1-Ma2s.tX1+X2-S1+a1=350，

X1-S2+a2=125，2X1+X2+S3=600，X1，X2,,S1,S2,a1,a2≥0．像這樣，為了構(gòu)造初始可行基得到初始可行解，把人工變量“強(qiáng)行”地加到原來的約束方程中去，又為了盡力地把人工變量從基變量中替換出來，就令人工變量在求最大值的目標(biāo)函數(shù)里的系數(shù)為-M，這個(gè)方法叫做大M法，M叫做罰因子。下面我們就用大M法來求解此題。迭代次數(shù)基變量CBx1x2s1s2s3a1a2b比值-2-3000-M-M0a1-M11-10010350350/1a2-M100-1001125125/1s302100100600600/2

Zj

σj=cj-zj-2M-MMM0-M-M-475M-2+2M-3+M-M-M0001a1-M01-1101-1225225x1-2100-1001125s30010210-2350350/2

Zjσj=cj-zj-2-MM-M+20-MM-2-225M-2500-3+M-MM-2002-2M迭代次數(shù)基變量CBx1x2s1s2s3a1a2b比值-2-3000-M-M2a1-M01/2-10-1/2105050/(1/2)x1-211/2001/200300300/(1/2)s2001/2011/20-1175175/(1/2)

Zj

σj=cj-zj-2-M/2-1M0-M/2-1-M0-50M-6000M/2-2-M0M/2+10-M3x2-301-20-120100x1-210101-10250s2000111-1-1125

Zjσj=cj-zj-2-3401-40-80000-40-1-M+4-M

在第2次迭代的檢驗(yàn)數(shù)中X2的檢驗(yàn)數(shù)為M/2-2，S3的檢驗(yàn)數(shù)為M/2+1，由于M為任意大的數(shù)，我們可以認(rèn)為這兩個(gè)數(shù)一樣大，這時(shí)最好選決策變量而不是選松弛、剩余或人工變量為入基變量。這樣就可能用較少次的迭代就能找到最優(yōu)解，注意?。纳媳碇锌芍浠究尚薪猓篨1=250,X2=100,S1=0,S2=125,S3=0,a1=0,a2=0是本例題的最優(yōu)解，其最優(yōu)值為f=-z=-(-800)=800。因?yàn)榈?次迭代的所有的檢驗(yàn)數(shù)都小于等于零。如果沒有單位矩陣，約束條件的等式也可設(shè)計(jì)人工變量例如MaxZ=3X1-X2-X3

stX1-2X2+X3≤11

-4X1+X2+2X3≥3

-2X1+X3=1X1,X2,X3≥0約束條件加上松馳和剩余變量后為：

X1-2X2+X3+S1=11-4X1+X2+2X3-S2=3-2X1+X3=1X1,X2,X3≥0

仍未有單位矩陣，在第二、三約束上分別加上人工變量a1,a2得：MaxZ=3X1-X2-X3-Ma1-Ma2

st

X1-2X2+X3+S1=11-4X1+X2+2X3-S2+a1=3-2X1+X3+a2=1X1,X2,X3≥0則基變量為S1，a1,a2。這樣就可進(jìn)行求解了。除了大M法外，還有兩階段法（略）一、無可行解.例1．求解下列線性規(guī)劃問題目標(biāo)函數(shù)：maxZ=20X1+30X2

約束條件：3X1+10X2≤150，

X1≤30，X1+X2≥40，X1,X2≥0．

解：在上述問題的約束條件中加入松弛變量，剩余變量，人工變量得到：目標(biāo)函數(shù)：maxZ=20X1+30X2-Ma1

約束條件：3X1+10X2+S1=150，X1+S2=30,X1+X2-S3+a1=40X1,X2,S1,S2,S3,a1≥0

§5.4．幾種特殊情況迭代次數(shù)基變量CBx1x2s1s2s3a1b比值2030000-M0s103101000150150/10s2010010030a1-M1100-114040/1

Zj

σj=cj-zj-M-M00M-M-40M20+M30+M00-M01x2303/1011/100001515/(3/10)s201001003030/1a1-M7/100-1/100-112525/(7/10)

Zjσj=cj-zj9-7M/10303+M/100M-M450-25M11+7M/100-3-M/100-M0所有的檢驗(yàn)數(shù)σj都小于等于零，可知最優(yōu)解為：X1=30,X2=6,S1=0,S2=0,S3=0,a1=4≠0，其目標(biāo)函數(shù)值為780-4M。把最優(yōu)解S3=0,a1=4代入第3個(gè)約束方程得X1+X2-S3+a1=40，即有：X1+X2=36<40．并不滿足原來的約束條件3:X1+X2≥40,可知原線性規(guī)劃問題無可行解，或者說其可行域?yàn)榭占９蔬@樣只要線性規(guī)劃的最優(yōu)解里有人工變量大于零，則此問題無可行解。迭代次數(shù)基變量CBX1X2S1S2S3a1b比值2030000-M2X230011/10-3/10006X12010010030a1-M00-1/10-7/10-114

Zj

σj=cj-zj20303+M/1011+7M/10M-M780-4M00-3-M/10-11-7M/10-M0

如果在最后的迭代時(shí)，所有檢驗(yàn)數(shù)都小于或等于零，而人工變量仍然是基變量，但人工變量取值為零，這時(shí)問題有解嗎？在求目標(biāo)函數(shù)最大值的問題中，所謂無界解是指在約束條件下目標(biāo)函數(shù)值可以取得任意的大。下面用單純形表來求解第二章中的例子（P15）。

例2、用單純形表求：目標(biāo)函數(shù)：maxZ=X1+X2，

約束條件：X1-X2≤1,-3X1+2X2≤6，X1≥0，X2≥0．解：在上述的約束條件中加入松弛變量，得標(biāo)準(zhǔn)型如下：

maxZ=X1+X2，S.t.X1-X2+S1=1,-3X1+2X2+S2=6，X1≥0，X2≥0．二、無界解從第1次迭代的σ2=2，得基本可行解X1=1,X2=0,S1=0，S2=9不是最優(yōu)解。如果進(jìn)行第2次迭代，那么選X2為入基變量，因?yàn)閍12=-1，a22=-1,

找不到大于零的aij來確定出基變量。碰到這種情況可以斷定此問題是無界的，即此目標(biāo)函數(shù)值可以取到無限大。迭代次數(shù)基變量CBX1X2S1S2b比值11000S1S2001-110161-3201

Zj

σj=cj-zj0000Z=011001X1S2101-110190-131

Zjσj=cj-zj1

-11

0102-1

0從1次迭代的單純形表中，得到約束方程:

X1-X2+S1=1-X2+3S1+S2=9移項(xiàng)得：X1=1+X2-S1S2=X2-3S1+9，不妨設(shè)X2=M,S1=0,得一組解：

X1=M+1,X2=M,S1=0,S2=M+9,顯然這是此線性規(guī)劃的可行解，此時(shí)目標(biāo)函數(shù):

Z=X1+X2=M+1+M=2M+1

由于M可以是任意大的正數(shù)，可知此目標(biāo)函數(shù)值無界。警告各位！在某次迭代的單純形表中（不要求是最終單純形表），如果存在著一個(gè)大于零的檢驗(yàn)數(shù)σj，并且該列的系數(shù)向量的每個(gè)元素aij

(i=1，2,…,m)都小于或等于零，則此線性規(guī)劃問題是無界的，一般地說此類問題的出現(xiàn)是由于建模的錯(cuò)誤所引起的。

例3．用單純形表求解下面的線性規(guī)劃問題。目標(biāo)函數(shù)：maxZ=50X1+50X2，

約束條件：X1+X2≤300，2X1+X2≤400，X2≤250,X1≥0,X2≥0.解：用單純形表來解，引入松弛變量S1,S2,S3,得標(biāo)準(zhǔn)型：

maxZ=50X1+50X2，X1+X2+S1=300,2X1+X2+S2=400,X2+S3=250,X1,X2,S1,S2,S3≥0，填入單純形表得：三、無窮多最優(yōu)解迭代次數(shù)基變量CBX1X2S1S2S3b比值50500000S1S2S300011100300400250300/1400/1250/121010

01001

Zj

σj=cj-zj00000050500001S1S2X2005010101150/22001-1

01001

Zjσj=cj-zj050005012500500000得最優(yōu)解為X1=50,X2=250,S1=0,S2=50,S3=0,最優(yōu)值為15000。這個(gè)最優(yōu)解是否是唯一的呢?由于在第2次迭代中除了基變量的檢驗(yàn)數(shù)σ1,σ2,σ4

等于零外，非基變量s3的檢驗(yàn)數(shù)也等于零，這樣可以斷定此問題有無窮多最優(yōu)解。不妨把檢驗(yàn)數(shù)也為零的非基變量選為入基變量進(jìn)行第3次迭代?？汕蟮昧硪粋€(gè)基本可行解：迭代次數(shù)基變量CBX1X2S1S2S3b比值50500002X1S2X2500501010-1505025050/1250/100-211

01001

Zj

σj=cj-zj505050001500000-5000從檢驗(yàn)數(shù)可知此基本可行解X1=100,X2=200,S1=0,S2=0,S3=50，也是最優(yōu)解。迭代次數(shù)基變量CBX1x2s1s2s3b比值50500003x1s3x25005010-1101005020000-211

012-10

Zj

σj=cj-zj505050001500000-5000從圖解法可知連接這兩點(diǎn)的線段上的任一點(diǎn)都是此線性規(guī)劃的最優(yōu)解，不妨用向量Z1，Z2表示上述兩個(gè)最優(yōu)解即Z1=(50，250，0，50，0)，Z2=(100，200，0，0，50)，則線段上的任一點(diǎn)，即可表示為αZ1+（1-α）Z2，其中0≤α≤l。如下圖所示：x2100400100300x1Z2250200Z1X1+X2=3002X1+X2=400目標(biāo)函數(shù)Z=50x1+50x25000=50x1+50x2問題：在一個(gè)已得到最優(yōu)解的單純形表中，如果存在一個(gè)非基變量的檢驗(yàn)數(shù)σs為零，為什么當(dāng)把這個(gè)非基變量xs作為入基變量進(jìn)行迭代時(shí)得到的新的基本解仍為最優(yōu)解呢?

判斷線性規(guī)劃有無窮多最優(yōu)解的方法：對于某個(gè)最優(yōu)的基本可行解，如果存在某個(gè)（或1個(gè)以上）非基變量的檢驗(yàn)數(shù)為零，則此線性規(guī)劃問題有無窮多最優(yōu)解。證明過程略，詳見P92-P93（即證明了其他非基變量的檢驗(yàn)數(shù)不變，仍然是小于等于零，估新的基本可行解仍然是最優(yōu)解）在單純形法計(jì)算過程中，確定出基變量時(shí)有時(shí)存在兩個(gè)以上相同的最小比值，這樣在下一次迭代中就有了一個(gè)或幾個(gè)基變量等于零，這稱之為退化。例4、用單純形表求解下列線性規(guī)劃問題。目標(biāo)函數(shù)：maxZ=2X1+3X3/2

約束條件：X1-X2≤2,2X1+X3≤4,X1+X2+X3≤3,X1,

X2,X3≥0加上松弛變量S1，S2,S3

化為標(biāo)準(zhǔn)型并填入單純形表得：四、退化問題迭代次數(shù)基變量CBX1X2X3

S1S2S3b比值203/20000S1S2S30001-101002432/14/23/1201010

111001

Zj

σj=cj-zj00