管理運籌學（第三版） 韓伯棠課件第五章

81管理運籌學第五章單純形法§1§2§3§4單純形法的基本思路和原理單純形法的表格形式求目標函數(shù)值最小的線性規(guī)劃問題的單純形表解法幾種特殊情況82管理運籌學§1單純形法的基本思路和原理

單純形法的基本思路：從可行域中某一個頂點開始，判斷此頂點是否是最優(yōu)解，如不是，則再找另一個使得其目標函數(shù)值更優(yōu)的頂點，稱之為迭代，再判斷此點是否是最優(yōu)解，直到找到一個頂點為其最優(yōu)解，就是使得其目標函數(shù)值最優(yōu)的解，或者能判斷出線性規(guī)劃問題無最優(yōu)解為止。一、找出一個初始基本可行解 下面通過第二章例1的求解來介紹單純形法。 在加上松弛變量之后我們可得到此線性規(guī)劃的標準形式。 目標函數(shù)：max50x1+100x2

約束條件：x1+x2+s1=300，

2x1+x2+s2=400，

x2+s3=250，

xi≥0（i=1,2），sj≥0（j=1,2,3）。83管理運籌學??

§1單純形法的基本思路和原理

它的系數(shù)矩陣為：

?11100?

,p,p,p,p21010

?01001?

其中pj為系數(shù)矩陣A第j列的向量。A的秩為3,A的秩m小于此方程組的變量的個數(shù)n，為了找到一個初始基本可行解，先介紹以下幾個線性規(guī)劃的基本概念。 基：已知A是約束條件的m×n系數(shù)矩陣，其秩為m。若B是A中m×m階非奇異子矩陣（即可逆矩陣），則稱B是線性規(guī)劃問題中的一個基。 基向量：基B中的一列即稱為一個基向量?；鵅中共有m個基向量。 非基向量：在A中除了基B之外的一列則稱之為基B的非基向量。 基變量：與基向量pi相應的變量xi叫基變量，基變量有m個。84管理運籌學??

§1單純形法的基本思路和原理

非基變量：與非基向量pj相應的變量xj叫非基變量，非基變量有n?m個。 由線性代數(shù)的知識知道，如果我們在約束方程組系數(shù)矩陣中找到一個基，令這個基的非基變量為零，再求解這個m元線性方程組就可得到唯一的解了，這個解我們稱之為線性規(guī)劃的基本解。

?110?

100

?101?為零。這時約束方程就變?yōu)榛兞康募s束方程。85管理運籌學

§1單純形法的基本思路和原理

x2+s1=300，

x2=400，

x2+s3=250.

求解得到此線性規(guī)劃的一個基本解：

x1=0，x2=400，s1=?100，s2=0，s3=?150

由于在這個基本解中s1=?100，s3=?150，不滿足該線性規(guī)劃s1≥0，s3≥0的約束條件，顯然不是此線性規(guī)劃的可行解，一個基本解可以是可行解，也可以是非可行解，它們之間的主要區(qū)別在于其所有變量的解是否滿足非負的條件。我們把滿足非負條件的一個基本解叫做基本可行解，并把這樣的基叫做可行基。86管理運籌學??

§1單純形法的基本思路和原理

一般來說判斷一個基是否是可行基，只有在求出其基本解以后，當其基本解所有變量的解都大于等于零時，才能斷定這個解是基本可行解，這個基是可行基。那么我們能否在求解之前，就找到一個可行基呢？也就是說我們找到的一個基能保證在求解之后得到的解一定是基本可行解呢？由于在線性規(guī)劃的標準型中要求bj都大于等于零，如果我們能找到一個基是單位矩陣，或者說一個基是由單位矩陣的各列向量所組成（至于各列向量的前后順序是無關(guān)緊要的事）例如：

?001?

100

?010?

那么顯然所求得的基本解一定是基本可行解，這個單位矩陣或由單位矩陣各列向量組成的基一定是可行基。實際上這個基本可行解中的各個變量或等于某個bj或等于零。87管理運籌學??

§1單純形法的基本思路和原理

在本例題中我們就找到了一個基是單位矩陣。

?100?

010

?001?

在第一次找可行基時，所找到的基或為單位矩陣或為由單位矩陣的各列向量所組成，稱之為初始可行基，其相應的基本可行解叫初始基本可行解。如果找不到單位矩陣或由單位矩陣的各列向量組成的基作為初始可行基，我們將構(gòu)造初始可行基。88管理運籌學

§1單純形法的基本思路和原理二、最優(yōu)性檢驗 所謂最優(yōu)性檢驗就是判斷已求得的基本可行解是否是最優(yōu)解。

1．最優(yōu)性檢驗的依據(jù)——檢驗數(shù)σj

一般來說目標函數(shù)中既包括基變量，又包括非基變量?，F(xiàn)在我們要求只用非基變量來表示目標函數(shù)，這只要在約束等式中通過移項等處理就可以實現(xiàn)，然后用非基變量的表示式代替目標函數(shù)中的基變量，這樣目標函數(shù)中只含有非基變量了，或者說目標函數(shù)中基變量的系數(shù)都為零了。此時目標函數(shù)中所有變量的系數(shù)即為各變量的檢驗數(shù)，把變量xi的檢驗數(shù)記為σi。顯然所有基變量的檢驗數(shù)必為零。在本例題中目標函數(shù)為50x1+100x2。由于初始可行解中x1，x2為非基變量，所以此目標函數(shù)已經(jīng)用非基變量表示了，不需要再代換出基變量了。這樣我們可知σ1=50，σ2=100，σ3=0，σ4=0，σ5=0。89管理運籌學

§1單純形法的基本思路和原理2．最優(yōu)解判別定理數(shù)

對于求最大目標函數(shù)的問題中，對于某個基本可行解，如果所有檢驗σj≤0，則這個基本可行解是最優(yōu)解。下面我們用通俗的說法來解釋最優(yōu)解判別定理。設用非基變量表示的目標函數(shù)為如下形式

z=z0+∑σjxj j∈J

由于所有的xj的取值范圍為大于等于零，當所有的σj都小于等于零時，可知∑σjxj是一個小于等于零的數(shù)，要使z的值最大，顯然∑σjxj j∈Jj∈J只有為零。我們把這些xj取為非基變量（即令這些xj的值為零），所求得的基本可行解就使目標函數(shù)值最大為z0。 注：對于求目標函數(shù)最小值的情況，只需把σj≤0改為σj≥0。90管理運籌學

§1單純形法的基本思路和原理三、基變換 通過檢驗，我們知道這個初始基本可行解不是最優(yōu)解。下面介紹如何進行基變換，找到一個新的可行基，具體的做法是更換可行基中的一個列向量，得到一個新的可行基，并且求解得到新的基本可行解使其目標函數(shù)值更優(yōu)。為了換基就要確定換入變量與換出變量。

1．入基變量的確定 從最優(yōu)解判別定理知道，當某個σj＞0時，非基變量xj變?yōu)榛兞浚蝗×阒悼梢允鼓繕撕瘮?shù)值增大，故我們要選基檢驗數(shù)大于0的非基變量換到基變量中去（稱之為入基變量）。若有兩個以上的σj>0，則為了使目標函數(shù)更大些，一般選其中的σj較大者的非基變量為入基變量，在本例題中σ2=100是檢驗數(shù)中最大的正數(shù)，故選x2為入基變量。91管理運籌學

§1單純形法的基本思路和原理

2．出基變量的確定 在確定了x2為入基變量之后，我們要在原來的3個基變量s1，s2，s3中確定一個出基變量，也就是確定哪一個基變量變成非基變量呢。如果把s3作為出基變量，則新的基變量為x2，s1，s2，因為非基變量x1=s3=0，我們也可以從方程組

x2+s1=300，

x2+s2=400，

x2=250， 求出基本解：x1=0，x2=250，s1=50，s2=150，s3=0。因為此解滿足非負條件，是基本可行解，故s3可以確定為出基變量。 能否在求出基本解以前來確定出基變量呢？ 下面就來看在找出了初始基本可行解和確定了入基變量之后，怎么樣的基變量可以確定為出基變量，或者說出基變量要具有什么條件。==300,==400,==250。92理籌學

§1單純形法的基本思路和原理

我們把確定出基變量的方法概括如下：把已確定的入基變量在各約束方程中的正的系數(shù)除其所在約束方程中的常數(shù)項的值，把其中最小比值所在的約束方程中的原基變量確定為出基變量。這樣在下一步迭代的矩陣變換中可以確保新得到的bj值都大于等于零。 在本例題中約束方程為

x1+x2+s1=300, 2x1+x2+s2=400,

x2+s3=250.

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

運250 1

b1a12b2a22管b3a3293管理運籌學

§1單純形法的基本思路和原理

bT

a32的基變量s3為出基變量，這樣可知x2，s1，s2為基變量，x1，s3為非基變量。 令非基變量為零，得

x2+s1=300,

x2+s2=400,

x2=250.

求解得到新的基本可行解x1=0,x2=250,s1=50,s2=150.

這時目標函數(shù)值為

50x1+100x2=50×0+100×250=25000

顯然比初始基本可行解x1=0，x2=0，s1=300，s3=250時的目標函數(shù)值為0要好得多。 下面我們再進行檢驗其最優(yōu)性，如果不是最優(yōu)解還要繼續(xù)進行基變換，直至找到最優(yōu)解，或者能夠判斷出線性規(guī)劃無最優(yōu)解為止。94管理運籌學§2單純形法的表格形式,n)

在講解單純形法的表格形式之前，先從一般數(shù)學模型里推導出檢驗數(shù)σj的表達式。 可行基為m階單位矩陣的線性規(guī)劃模型如下（假設其系數(shù)矩陣的前m列是單位矩陣）：

maxz=c1x1+c2x2++cnxnx1+a1,m+1xm+1+x2+a2,m+1xm+1+xm+am,m+1xm+1++a1,nxn=b1,

+a2,nxn=b2,

+am,nxn=bm,(j=1,2,xj≥0,m)表示基變量，用xj(j=m+1,m+2,,n)表示非

以下用xi(i=1,2,基變量。∑axz0=∑cjbjjjj;+cnxn=∑cixi+∑cx????∑(c∑σ,cm)??a2jzj=∑ciaij=c1a1j+c2a2j+95管學籌運理jij,m)

nj=m+1

§2單純形法的表格形式把第i個約束方程移項，就可以用非基變量來表示基變量xi，

xi=bi?ai,m+1xm+1?ai,m+2xm+2??ai,nxn=bi?(i=1,2,jjjjxj

nj=m+1mi=1

nj=m+1

nj=m+1把以上的表達式代入目標函數(shù)，就有

z=c1x1+c2x2+?zj)xj=z0+=z0+其中：

mi=1,σ=c?z

mi=1+cmamj=(c1,c2,?a1j??????amj?=(c1,c2,,cm)pj96管理運籌學

§2單純形法的表格形式

上面假設x1,x2,…xm是基變量，即第i行約束方程的基變量正好是xi，而經(jīng)過迭代后，基將發(fā)生變化，計算zj的式子也會發(fā)生變化。如果迭代后的第i行約束方程中的基變量為xBi，與xBi相應的目標函數(shù)系數(shù)為cBi，系數(shù)列向量為p′j(j=1,2,,n)則zj=(cB1,,cBm)p′j=(cB)p′j,

其中，(cB)是由第1列第m行各約束方程中的基變量相應的目標函數(shù)依次組成的有序行向量。 單純形法的表格形式是把用單純形法求出基本可行解、檢驗其最優(yōu)性、迭代等步驟都用表格的方式來計算求出，其表格的形式有些像增廣矩陣，而其計算的方法也大體上使用矩陣的行的初等變換。以下用單純形表格來求解第二章的例2-1。

max50x1+100x2+0?s1+0?s2+0?s3

x1+x2+s1=300，

2x1+x2+s2=400，

x2+s3=250，

x1,x2,s1,s2,s3≥0.

把上面的數(shù)據(jù)填入如表5-1所示的單純形表格。97管理運籌學§2單純形法的表格形式

表5-1基變量

s1

s2

s3cB000

x150 1 2 0

x2100 1 1 1s1

0 1 0 0s20010s30001

b300400250比值bi/aij300/1400/1250/1迭代次數(shù)

0

zjσj=cj?zj000

0050100000z=0按照線性規(guī)劃模型在表中填入相對應的值，如表5-1所示；在上表中有一個m×m的單位矩陣，對應的基變量為s1,s2,s3；在zj行中填入第j列與cB列中對應的元素相乘相加所得的值，如z2=0×1+0×1+0×1=0，所在zi行中的第2位數(shù)填入0；在σj=cj?zj行中填入cj-zj所得的值，如σ1=50?0=50；z表示把初始基本可行解代入目標函數(shù)求得的目標函數(shù)值，即b列乘以cB列；初始基本可行解為s1=300，s2=400，s3=250，x1=0，x2=0；由于σ2>σ1>0，因此確定x2為入基變量。由于250/1最小，因此確定s3為出基變量；出基變量所在行，入基變量所在列的交匯處為主元，這里是a32=1，在表中畫圈以示區(qū)別。98管理運籌學§2單純形法的表格形式以下進行第一次迭代，基變量為x2，s1，s2，通過矩陣行的初等變換，求出一個新的基本可行解，具體的做法用行的初等變換使得x2的系數(shù)向量p2變換成單位向量，由于主元在p2的第3分量上，所以這個單位向量是e3=(0,0,1)T也就是主元素變成1。這樣我們又得到的第1次迭代的單純表如5-2所示。

表5-2基變量

s1

s2

x2cB000

x150 1 2 0x2100 0 0 1s10 100s20 010s30-1-1 1

b50150250比值bi/aij

50/1150/2 —迭代次數(shù)

1

zjσj=cj?zj

05010000000100-10025000

在表5-2中第3個基變量s3已被x2代替，故基變量列中的第3個基變量應變?yōu)?/p>

x2。由于第0次迭代表中的主元a32已經(jīng)為1，因此第3行不變。為了使第1行 的a12為0，只需把第3行x(-1)加到第1行即可。同樣可以求得第2行。求得第1次迭代的基本可行解為s1=50，s2=150，x2=250，x1=0，s3=0，z=25000。99管理運籌學

§2單純形法的表格形式從表5-2可以看出，第一次迭代的σ1=50＞0，因此不是最優(yōu)解。設x1為入基變量，從此值可知b1/a11=50為最小正數(shù)，因此，s1為出基變量，a11為主元，繼續(xù)迭代如下表所示。

表5-3比值bi/aij基變量

x1

s2

x2

cB

50 0100

x150100

x2100

0 0 1s1

0

1-2 0s20010

s3

0-1 1 1

b

50 50250迭代次數(shù)

2

zjσj=cj?zj500100 0

50-5000

50-5027500從表5-3中可知第二次迭代得到的基本可行解為x1=50,x2=250,s1=0,s2=50,s3=0,這時z=27500。由于檢驗數(shù)都小于等于0，因此所求得的基本可行解為最優(yōu)解，z=27500為最優(yōu)目標函數(shù)值。實際上，我們可以連續(xù)地使用一個單純形表，不必一次迭代重畫一個表頭。100管理運籌學

§3求目標函數(shù)值最小的線性規(guī)劃問題的單純形表解法一、大M法 以第二章的例2來講解如何用單純形表的方法求解目標函數(shù)值最小的線性規(guī)劃問題。 目標函數(shù)：minf=2x1+3x2.

約束條件：

x1+x2≥350,

x1≥125, 2x1+x2≤600,

x1,x2≥0.

加入松弛變量和剩余變量變?yōu)闃藴市?，得到新的約束條件如下。

x1+x2?s1=350,

x1?s2=125, 2x1+x2+s3=600,

x1,x2,s1,s2,s3≥0.101管理運籌學

§3求目標函數(shù)值最小的線性規(guī)劃問題的單純形表解法

至于目標函數(shù)，在標準型中并不一定要求求最大值或最小值，但是為了使單純形表解法有一個統(tǒng)一的解法，我們把所有求目標函數(shù)最小值的問題化成求目標函數(shù)最大值的問題。具體做法是把目標函數(shù)乘以-1。 要注意到人工變量是與松弛、剩余變量不同的。松弛變量、剩余變量可以取零值，也可以取正值，而人工變量只能取零值。一旦人工變量取正值，那么有人工變量的約束方程和原始的約束方程就不等價了，這樣所求得的解就不是原線性規(guī)劃的解了。為了竭盡全力地要求人工變量為零，我們規(guī)定人工變量在目標函數(shù)中的系數(shù)為-M，這里M為任意大的數(shù)。這樣只要人工變量＞0，所求的目標函數(shù)最大值就是一個任意小的數(shù)。這樣為了使目標函數(shù)實現(xiàn)最大就必須把人工變量從基變量中換出。如果一直到最后，人工變量仍不能從基變量中換出，也就是說人工變量仍不為零，則該問題無可行解。102管理運籌學

§3求目標函數(shù)值最小的線性規(guī)劃問題的單純形表解法

此例的數(shù)學模型如下所示。 目標函數(shù)：maxz=-2x1-3x2-Ma1-Ma2.

約束條件：x1+x2-s1+a1=350，

x1-s2+a2=125，

2x1+x2+s3=600，

x1，x2，s1，s2，s3，a1，a2≥0.

像這樣，為了構(gòu)造初始可行基得到初始可行解，把人工變量“強行”地加到原來的約束方程中去，又為了盡力地把人工變量從基變量中替換出來，就令人工變量在求最大值的目標函數(shù)里的系數(shù)為-M，這個方法叫做大M法，M叫做罰因子。s3s2103管理運籌學§3求目標函數(shù)值最小的線性規(guī)劃問題的單純形表解法

下面我們就用大M法來求解此題。

表5-4迭代次數(shù)基變量cB

x1?2x2?3s10s2

0s30

a1?M

a2?Mb比值

350/1 125/1 600/2 225 ----- 350/2 50/（1/2）300（/1/2）

175/（1/2013

a1?M a2?M

0

zjσj=cj?zj

a1?M x1

?2

s3

0

zjσj=cj?zj

a1?M x1?2 0

zjσj=cj?zj

1 1 2 ?2M?2+2M

0 1 0 ?2 0 0 1 0 ?2 0

1 0 1 ?M

?3+M

1 0 1 ?M

?3+M

1/2 1/2 1/2?M/2?1

M/2?2?1 0 0

M?M?1 0 0

M?M

?1

0 0

M?M

0 ?1 0

M

?M

1 ?1 2?M+2

M?2 0 0 1 0 0

0 0 1 0 0 0 0 1 0 0

?1/2 1/2 1/2

M/2?1?M/2+1

1 0 0?M

0 1 0 0?M

0 1 0 0?M

0

0 1 0 ?M

0 -1 1 -2M?22?2M

0 0 ?1 0 ?M

350 125 600 ?475M

225 125 350?225M?250

50 300 175?50M?600104管理運籌學§3求目標函數(shù)值最小的線性規(guī)劃問題的單純形表解法

表5-5比值基變量

x2

x1

s2cB?3?2 0x1?2 0 1 0x2?3100

s1

0?2 1 1

s2

0001s3

0-1 1 1

a1?M

2-1-1

a2?M

0 0?1

b100250125迭代次數(shù)

3

zjσj=cj?zj?2 0?3 0

4?400

1?1

?4?M+4

0?M?800

從表5-5中可知檢驗數(shù)都小于等于零。已求得最優(yōu)解為x1=250,x2=100,s1=0,s2=125,s3=0,a1=0,a2=0，其最優(yōu)值為f=?z=?(?800)=800。105管理運籌學§3求目標函數(shù)值最小的線性規(guī)劃問題的單純形表解法二、兩階段法 兩階段法是處理人工變量的另一種方法，這種方法是將加入人工變量后的線性規(guī)劃劃分兩階段求解，仍以上面的例題為例，闡述兩階段法的求解過程。 第一階段：要判斷原線性規(guī)劃是否有基本可行解，方法是先求解下列線性規(guī)劃問題： 目標函數(shù)：maxz=?a1?a2;

約束條件：

x1+x2?s1+a1=350,

x1?s2+a2=125, 2x1+x2+s3=600,

x1,x2,s1,s2,s3,a1,a2≥0.106管理運籌學

§3求目標函數(shù)值最小的線性規(guī)劃問題的單純形表解法

注意：此線性規(guī)劃的約束條件與原線性規(guī)劃一樣，而目標函數(shù)是求人工變量的相反數(shù)之和的最大值。如果此值大于零，則不存在使所有人工變量都為零的可行解，停止計算。如果此值為零，即說明存在一個可行解，使得所有的人工變量都為零。 第二階段：將第一階段的最終單純形表中的人工變量取消，將目標函數(shù)換成原問題的目標函數(shù)，把此可行解作為初始可行解進行計算。s3107學籌運理管§3求目標函數(shù)值最小的線性規(guī)劃問題的單純形表解法

表5-6基變量

a1

a2

a3cB?1?1 0s30001x10112x20101

s1

0?1 0 0

s2

0 0?1 0a1?1 1 0 0a2?1 0 1 0

b350125600比值350/1125/1600/2迭代次數(shù)

0

zjσj=cj?zj?2 2?1 1

1?1

1?100?1 0?1 0?475a1x1?1 00110?1 0

1?1?1 110002251251s30

zjσj=cj?zj

1?1 1000

0 1?1

2?1 1100

0?1 0?2 1?2

350?225x2x1000110?1 0

1?10010?1 12251252

0

zjσj=cj?zj000000100100100?1 0 0?1 0 0125 0108管理運籌學§3求目標函數(shù)值最小的線性規(guī)劃問題的單純形表解法

表5-7x1?2s30x2

?3s1

0基變量

x2

x1

s3cB?3?2 0010?1 0 1

s2

0 1?1 1001100

b225125125比值225/1125/1zj迭代次數(shù)

0σj=cj?zj?2?33?1000?310?925x1x2?3?200?1 10110?2 11002501x30

zjσj=cj?zj

0?3 0

0?2 0

1 4?4100

1 1?1

125?800

從表5-7中可知其基本可行解x1=250,x2=100,s1=0,s2=125,s3=0是本例的最優(yōu)解，其最優(yōu)值為z=?(?800)=800。109管理運籌學§4幾種特殊情況一、無可行解 例1．用單純形表求解下列線性規(guī)劃問題 目標函數(shù)maxz=20x1+30x2

約束條件3x1+10x2≤150,

x1≤30,

x1+x2≥40,

x1,x2≥0.解：在上述問題的約束條件中加入松弛變量、剩余變量、人工變量得到： 目標函數(shù)maxz=20x1+30x2?Ma1

約束條件3x1+10x2+s1=150,

x1+s2=30,

x1+x2?s3+a1=40,

x1,x2,s1,s2,s3,a1≥0.填入單純形表計算，如表5-8所示。110學管理運籌§4幾種特殊情況

表5-8基變量

s1

s2

a1

cB

0 0?Mx120311x23010

0 1s10100s20010s3

0 0 0?1a1?M

0 0 1

b150 30 40

比值150/10 — 40/1迭代次數(shù)

0

zjcj?zj

?M20+M

?M30+M0000

M?M?M

0?40Mx2s2a130

0?M3/10

17/101001/10

0?1/100100

0?100115302515/(3/10)

30/125/(7/10)1

zjcj?zj

9?7/10M11+7/10M30 03+M/10?3?M/1000

M?M?M

0450?25Mx2x1a13020?M011/10?3/1000630 42

zjcj?zj10200

0 030 0

0

?1/103+M/10?3?M/10

1

?7/10 11+7M/10?11?7M/10

0?1

M?M

0 1?M

0780?4M111管理運籌學§4幾種特殊情況

從第二次迭代的檢驗數(shù)都小于等于零來看，可知第二次迭代所得的基本可行解已經(jīng)是最優(yōu)解了，其最大的目標函數(shù)值為780?4M。我們把最優(yōu)解x1=30，x2=6，s1=0，s2=0，s3=0，a1=4，代入第三個約束方程得x1+x2?0+4=40，即有：x1+x2=36≤40.

并不滿足原來的約束條件3，可知原線性規(guī)劃問題無可行解，或者說其可行域為空集，當然更不可能有最優(yōu)解了。 像這樣只要求出線性規(guī)劃的最優(yōu)解里有人工變量大于零，則此線性規(guī)劃無可行解。二、無界解 在求目標函數(shù)最大值的問題中，所謂無界解是指在約束條件下目標函數(shù)值可以取任意的大。下面我們用單純形表來求第二章中的例子。

例2．用單純形表求解下面線性規(guī)劃問題。目標函數(shù)maxz=x1+x2

約束條件x1?x2≤1,

?3x1+2x2≤6,

x1,x2≥0.112學籌運理管?3x1+2x2+s2=6,x1,x2,s1,s2≥0.§4幾種特殊情況解：在上述問題的約束條件中加入松弛變量，得標準型如下。 目標函數(shù)maxz=x1+x2

約束條件x1?x2+s1=1,填入單純形表計算得到表5-9。表5-9迭代次數(shù)基變量

s1s2CB

00x111x2

1?1s1

0 1s200b1比值

1—0

zjcj?zj?3 0 120100010060x1s2101?110191

zjcj?zj010?1?1 2

3 1?11001113管理運籌學§4幾種特殊情況

從單純形表中，從第一次迭代x2的檢驗數(shù)等于2，可知所得的基本可行解x1=1,x2=0,s1=0,s2=9不是最優(yōu)解。同時我們也知道如果進行第2次迭代，那么就選x2為入基變量，但是在選擇出基變量時遇到了問題：a12=?1，a22=?1，找不到大于零的ai2來確定出基變量。事實上如果我們碰到這種情況就可以斷定這個線性規(guī)劃問題是無界的，也就是說在此線性規(guī)劃的約束條件下，此目標函數(shù)值可以取得無限大。從1次迭代的單純形表中，得到約束方程：x1?x2+s1=1,?x2+3s1+s2=9.移項可得：x1=1+x2?s1,s2=x2?3s1+9.不妨設x2=M,s1=0,可得一組解：x1=M+1,x2=M,s1=0,s2=M+9.顯然這是線性規(guī)劃的可行解，此時目標函數(shù)z=x1+x2=M+1+M=2M+1.114管理運籌學§4幾種特殊情況

由于M可以是任意大的正數(shù)，可知此目標函數(shù)值無界。 上述的例子告訴我們在單純形表中識別線性規(guī)劃問題是無界的方法：在某次迭代的單純形表中，如果存在著一個大于零的檢驗數(shù)σij，并且該列的系數(shù)向量的每個元素aij(i=1,2,…,m)都小于或等于零，則此線性規(guī)劃問題是無界的，一般地說此類問題的出現(xiàn)是由于建模的錯誤所引起的。三、無窮多最優(yōu)解 例3．用單純形法表求解下面的線性規(guī)劃問題。 目標函數(shù)maxz=50x1+50x2

約束條件x1+x2≤300, 2x1+x2≤400,

x2≤250,

x1,x2≥0.115管理運籌學§4幾種特殊情況解：此題我們用圖解法已求了解，現(xiàn)在用單純形表來求解。

加入松弛變量s1,s2,s3，我們得到標準形： 目標函數(shù)maxz=50x1+50x2

約束條件x1+x2+s1=300, 2x1+x2+s2=400,

x2+s3=250,

x1,x2,s1,s2,s3≥0.填入單純形表計算，如表5-10所示。116學理運§4幾種特殊情況

表5-10基變量

s1

s2

s3cB000x150 1 2 0x250 1 1 1s10100s20010s30001

b300400250

比值300/1400/1250/1迭代次數(shù)

0

zjcj?zj

050

0500000000s1s2x2

0 050120001100010?1?1 1

50150250

50/1150/2 —1

zjcj?zj

05050 00000

50?5012500x1s2x250 050100001

1?2 0010?1

1

1

50 50250

— 50/1250/12

zjcj?zj50 0

50 0管

50?50

籌000015000117管理運籌學§4幾種特殊情況

這樣我們求得了最優(yōu)解為x1=50,x2=250,s1=0,s2=50,s3=0，此線性規(guī)劃的最優(yōu)值為15000。這個最優(yōu)解是否是唯一的呢？由于在第2次迭代的檢驗數(shù)中除了基變量的檢驗數(shù)σ1,σ2,σ4等于零外，非基變量s3的檢驗數(shù)也等于零，這樣我們可以斷定此線性規(guī)劃問題有無窮多最優(yōu)解。不妨我們把檢驗數(shù)也為零的非基變量選為入基變量進行第3次迭代。可求得另一個基本可行解，如表5-11所示。

表5-11cB50 050迭代次數(shù)

3基變量

x1

s3

x2

zj

cj?zjx150 1 0 050 0x250 0 0 150 0

s1

0

?1

?2

2 50?50s2

0 1 1?1 0 0s3001000

b

100 50 20015000118管理運籌學§4幾種特殊情況

從檢驗數(shù)可知此基本可行解x1=100，x2=200，s1=0，s2=0，s3=50，也 是最優(yōu)解，從圖解法可知連接這兩點的線段上的任一點都是此線性規(guī)劃的 最優(yōu)解，不妨用向量Z1，Z2表示上述兩個最優(yōu)解即Z1=（50，250，0，50，

0），Z2=（100，200，0，0，50），則此線段上的任一點，即可表示為αZ1+（1?α）Z2，其中0≤α≤1。如圖5-1所示。

圖5-1+cmams?cs=0，也就是cs=∑ciais。119管理運籌學§4幾種特殊情況01000

在一個已得到最優(yōu)解的單純形表中，如果存在一個非基變量的檢驗數(shù)σs為零，為什么我們把這個非基變量xs作為入基變量進行迭代時，得到的最優(yōu)解仍為最優(yōu)解呢？ 不妨設出基變量為xk，則原最優(yōu)單純形表可表示如下。

xkxsckcsx1c10a1sck?1

ckck+1

cmak?1,s

ak,sak+1,s

am,s

0mi=1

xk?1

xk

xk+1

xmσj=cj?zj由此可知σs=0,即有c1a1s+c2a2s+1??1?∑(?ciis)+∑(?ciis)?+?cs1????1???∑ciais?+?ckaks?+?cs把cs=∑ciais，代入上式得：[?cs+ckaks]+?cs=ck，zk=120管理運籌學§4幾種特殊情況通過迭代，我們得到了新的單純形表，其中xs為基變量，而xk為非基變量。我們可得到：xkckxscs00100cs0

x1xk?1

xsxk+1

xm

c1

ck?1

cs

ck+1

cm

zjcj?zj

?a1s

aks?a(k?1)s

aks

1

aks?a(k+1)s

aks

?ams

aks

zkck?zk

k?1m其中zk=aa aks?i=1i=k+1?aks m

=

aks??i=1??aks m i=1

11

aksaks

即又可得到：ck?zk=ck?ck=0。目標函數(shù)maxz=2x1+x3121管理運籌學32約束條件x1?x2≤2, 2x1+x3≤4,

x1+x2+x3≤3,

x1,x2,x3≥0.§4幾種特殊情況

顯然，在新的單純形表中，基變量的檢驗數(shù)為零，用同樣的方法可證明其他