第十三章 線性規(guī)劃的單純形算法

1、第十三章 單純形法13.1 單純形法原理求解線性規(guī)劃的單純形方法（Simplex Method）是美國GDDantzig在1947年提出來的，是一種有效的實用算法。單純形法是根據(jù)線性規(guī)劃的基本原理，在基可行解上進行迭代的一種算法。此方法的特點是：將線性規(guī)劃化為標準形，從一個初始基可行解開始迭代，使之改進得到另一個基可行解。每迭代一次，目標函數(shù)值絕不會變?。▽?max 問題），如果非退化，目標函數(shù)值就嚴格增大。若有最優(yōu)解，經(jīng)有限次迭代就得到基本最優(yōu)解。標準形式線性規(guī)劃問題求解的主要途徑是通過樞軸運算把約束方程組變?yōu)榈浞缎蛠磉M行的。這個過程實質(zhì)上就是古典的高斯-約當消去法求解線性規(guī)劃的過程。 下列

2、運算可以將一組線性方程變換為另一組等價的線性方程。將一個方程乘上一個常數(shù)k（k0）將方程用替換這樣的運算稱為線性方程組的初等變換，或稱為基本行運算。下面分別說明樞軸運算（Pivot Operation）和典范型（Canonical form）13.1.1 樞軸運算樞軸運算就是通過一系列的基本行運算，使某一選定的變量在方程組的某一方程中系數(shù)是1，而這個變量在其他方程中的系數(shù)均為0.具體步驟是：在方程Er的s列中選取arsxs作為樞軸元素，條件是樞軸元素所在的行稱為樞軸行，樞軸元素所在的列稱為樞軸列。將方程Er除以 ，使樞軸元素系數(shù)為1。對方程以外的方程，用來代替 。例13.1.1：在下列方程組中

3、對變量進行樞軸運算：解： 選中2,為樞軸項將除以2化為：對進行基本運算：即以代替 得： 對進行基本運算：即以代替得：13.1.2 典范型線性方程組對n個變量m個方程的線性方程組可以通過對各個基變量逐一進行樞軸運算，將這m 個基變量的系數(shù)距陣變換成m m單位陣。這樣的等價線性方程組就是典范型線性方程組。這樣就可以直接求出一個基本解：如果常數(shù)項均非負，則得到的就是基本可行解。用矩陣符號表示就是：約束方程為： 變量分成基變量和非基變量兩部分,系數(shù)距陣中相應(yīng)分成B和N兩塊。即A=（B;N）則約束方程組可以寫成：左乘以得： 即 當非基變量取0時，則基變量的解為 由于基本解最多有個，因而基可行解也不超過個

4、。如果全部的基可行解找出來了，就有可能求出最優(yōu)基本解。但這樣做是不能實現(xiàn)的。單純形法（Simplex Method）就是沿一個初始基可行解出發(fā)，找出下一個更優(yōu)的基可行解，而不找所有的基可行解。13.1.3 單純形法的一般步驟 如果線性規(guī)劃問題存在可行解，就可以找出一個基可行解，作為初始可行解。 為尋找基可行解，約束方程組以典范型方程組表示。 如果線性規(guī)劃問題不存在可行解（約束條件有矛盾）則由找基可行解的過程可以得知問題無解。 以中找到的基可行解為起點，找出具有較佳目標值的另一基可行解。這一步驟稱為迭代。 重復(fù)。直到目標函數(shù)再也不能改善，就得到問題最優(yōu)解。 若問題的最優(yōu)解是無界的，在迭代過程中就

5、可以知道問題有無窮解，終止迭代。例13.1.2： 求解 s.t 解：這是一個標準形線性規(guī)劃問題，可以化為等價的典范型方程組：令，由上述典范型方程組直接得到一個基本解。顯然這個基本解是可行解。相應(yīng)目標函數(shù)值為現(xiàn)在要判斷一下這個目標函數(shù)的值是否能改進，故換基變量就可能獲得另一個基本可行解和相應(yīng)的目標函數(shù)值。這樣可用或來取代或成為基變量，因此目前的基本可行解有許多相鄰的基本可行解。單純形法就是在得到一個基本可行解后，在它的相鄰基可行解中選取能使目標函數(shù)值最大程度改進的基本可行解。選取的原則是看哪一個非基變量改為基變量后能夠使目標函數(shù)有更多的改進。具體地，可以在滿足方程組的情況下，分別將各非基變量增加

6、一個單位。比較目標值由此發(fā)生的變化，從而選取能使目標函數(shù)值有最大增加的非基變量作為新的基變量。相應(yīng)的目標值為：現(xiàn)在考慮非基變量，假定 增加一個單位，而其余的非基變量暫不考慮，仍為0。則約束方程可表示為：由第一個方程可見，由01，則由108。由第二個方程可見，由01，則由63。因此在滿足上述方程組的條件下，增加1得到新可行解為：相應(yīng)的目標值為： 所以 x3 增加1個單位，目標函數(shù)z的變化值為： z的舊值 - z的新值=22-（25）= -3稱這個值為非基變量x3 的檢驗值（判別數(shù)）。因為可以用它來判別把x3 改為基變量后，能否改進目標值。這個檢驗數(shù)的絕對值有時也稱為相對收益系數(shù)。由于檢驗數(shù)為負，

7、增加x3可以增加目標函數(shù)值。這證明目前的基可行解不是最優(yōu)解，如將x3改為基變量就可以改進目標值。類似的可以算 4, 的檢驗數(shù)。比較所得到的幾個檢驗數(shù)，決定把哪個非基變量換為基變量對目標函數(shù)的改進有利。檢驗數(shù)也可以用消去目標函數(shù)z中x1, x2的代入法來得到。將代入目標函數(shù) 的：由此可知當取x1和x2為基變量時， x3, x4, x5的檢驗數(shù)分別為-3，0和-2。目標值為22。x3, x4或x5每增加一個單位，z的值就相應(yīng)增加3，0，個單位，所以把x3作為新基變量對改進目標函數(shù)最有利。 現(xiàn)在的問題是x3增加多少仍能滿足約束條件，仍然以x4, x5 作非基變量。這時約束條件為：從第一個方程看， 最

8、多增到，若再大，成為負值。從第一個方程看，最多增到，若再大，成為負值。因此為保證最大增加值由這兩個值中較小的一個來決定。即：當由02后，新的目標值為z=28 。這個目標值的改進是通過將非基變量 改為基變量，而基變量 改為非基變量得到的。 新引進的非基變量稱為進基變量。換出的基變量則稱為出基變量。選擇進基變量的原則一般可以按負檢驗數(shù)絕對值大的先進基。選擇出基變量的原則是最小比值原則。一般先決定進基變量，再決定出基變量。當前得到的基可行解是否已最優(yōu)還要重復(fù)上述算法，重新計算在目前的基可行解中所有非基變量的檢驗數(shù)。如果檢驗數(shù)中至少有一個負數(shù)，那么就可以得到另一個相鄰基本可行解能使目標函數(shù)值進一步有所

9、改進。重復(fù)這一過程，直到所有檢驗數(shù)都不為負值。則此時的基可行解就是最優(yōu)解。用 來表示非基變量的檢驗數(shù)，以表示檢驗數(shù)組成的向量。注意一般在線性規(guī)劃中，檢驗數(shù)取下面形式：13.1.4 判別數(shù)最優(yōu)判別定理設(shè)是（SLP）的一個基變量，對應(yīng)C中的系數(shù)構(gòu)成m維向量 定義13.1.1：對于基B，稱為基B的判別數(shù)。判別數(shù)也可以用向量及距陣表示。因為 從而 若令 則下面我們來用表格形式說明如何計算判別數(shù)。 作形如下面的表格。表13.1.1求 與 的內(nèi)積。即上表中箭頭所示兩列對應(yīng)元素乘積相加得：把與 下面的數(shù) 相減得： 由于 是基變量，因而對于基變量的判別數(shù)即基變量對應(yīng)判別數(shù)等于0。因而只需計算非基變量的n-m個

10、判別數(shù)就可以了。n個判別數(shù)組成一個n維向量也可以用矩陣向量形式表出：下面導(dǎo)出矩陣形式的最優(yōu)判別定理。為此先定義基B單純形乘子。定義13.1.2 稱為基B的單純形乘子，記為可知單純形乘子是一m維向量。記為定理13.1.1：設(shè)B是（SLP）的一個基，若滿足且CBB-1A-C =0, 則對應(yīng)基B的基可行解就是最優(yōu)解。（稱為基本最優(yōu)解，基B稱為最優(yōu)基）證明： 因。表明基變量取非負值。則基B對應(yīng)的基本解為基本可行解。記為，其目標值記為，又設(shè)是（SLP）的任意可行解，即 則目標值 要證是基本最優(yōu)解，只須證明 。用基B的單純形乘子乘兩邊得：此式與相減得： 根據(jù)定理條件 CBB-1A-C =0及x=0故對（C

11、BB-1A-C ）=0因此 對任意 ，0因 是第一階段最優(yōu)解,代入其目標函數(shù)得.又假定了原問題有可行解，設(shè)為，那么(,0)T 是第一階段的可行解，它對應(yīng)的目標值記為，：=-（0+0+.+0=0但此目標值不應(yīng)超過最優(yōu)值 ， 即矛盾， 故y*=0 。 定理證畢。現(xiàn)在來進一步分析第一階段結(jié)束時與原問題的關(guān)系.設(shè)第一階段的最優(yōu)基B*對應(yīng)基本最優(yōu)解為： 第一 若 是非基變量。因為非基變量取值為零，則 =0那么就是原（SLP）的一個基本可行解。這是一種重要情形，這樣可求得原問題的一個初始基本可行解x*及初始基B=B*，于是就可以求解原問題了。第二 某些yj是基變量，且y*0，則由定理5知原問題無可行解。第

12、三 某些yj是基變量，且y* =0.這時 是第一階段的退化的基本可行解，由于已假定第一階段的是非退化的，所以不會出現(xiàn)這種情況。但在實際問題中，第三種情況中的退化情形是可能出現(xiàn)的。這時又如何得到原問題的基本可行解呢？設(shè)在第一階段的的基本最優(yōu)解中第t個基本變量是y的某分量，無妨設(shè)為yt(1tm)，且yt=0那么在第一階段最優(yōu)單純形表的第t行。對應(yīng)的約束方程為： 其中yt為基變量.，分別為x，y中非基變量的下標集合.（1） 若所有j， ，即有：這時原問題中的約束方程Ax=b的第t個方程是多余的，但若假定原問題的約束方程系數(shù)陣A的秩是m,就不會有多余的方程（否則可以去掉這個方程）。因此這種情形可不考慮

13、.2） 若有k， .則以為樞軸進行樞軸運算，旋出基變量yt，旋入基變量xk，從而把y中分量yt排出基外。若還有y中分量留在基內(nèi)，則同樣辦法，可在有限步內(nèi)將y的分量全部排出基外，于是就化為yj全為非基變量的情形了。13.4 退化與克服循環(huán)的方法（LP）中退化的基本可行解是指基可行解中有取零值的基變量的情形。我們以前的計算都是假設(shè)在非退化的情形下進行的，并證明了單純形法收斂性。但實際上，往往會出現(xiàn)退化的基可行解，這時單純法會出現(xiàn)循環(huán)。先看一個有退化基的例子，來說明一個基可能重復(fù)出現(xiàn)，從而出現(xiàn)循環(huán)代。Beale 的例： 利用前面的 單純形法求解:表13.4.1此最后一表與最開始一表 完全一致.如果繼

14、續(xù)同樣迭代下去.運算將會循環(huán)不止，造成循環(huán)的原因是迭代過程中=0目標函數(shù)值始終不變。 這是一個人造例子。實際中，退化的情形很多，但循環(huán)情形極少。但從數(shù)學(xué)理論的完整性考慮，研究避免發(fā)生循環(huán)的方法是必要的。下面介紹克服循環(huán)的-攝動法。避免循環(huán)的攝動法. 如果（SLP）有一個退化的基本可行解.即B0b0中有0分量.于是就不滿足單純形法迭代收斂定理的條件，不能保證有限次迭代內(nèi)解決此問題。上面的Beale 例即說明了此種情況。攝動法的基本內(nèi)容就是：將向量b作一微小的變動，變?yōu)閎（）。使得 。而對于攝動問題應(yīng)了非退化的基本可行解。如果能進一步證明：在的某一取值范圍內(nèi)攝動問題是一個非退化的（LP），那么它滿

15、足單純形法迭代收斂條件，經(jīng)過有限次迭代就能解決此問題。如果攝動問題有最優(yōu)解，再把b（）b，就得到原問題的最優(yōu)解。下面來具體構(gòu)造攝動問題。設(shè)是（SLP）的一個可行基，或者退化，或者在單純形迭代時，由決定的出基變量標號jl時l不唯一。引進攝動問題的目的就是為了在單純形迭代中能確定唯一的l, 并能使原問題避免循環(huán)。為方便起見，不妨假設(shè)（SLP）的基變量標號調(diào)換為1，2，m的順序，即調(diào)換后的基變量為x1 ,x2，xm調(diào)換后的規(guī)劃問題仍記為：（SLP） s.t.已知A的前m列組成基B0=（P1P2Pm），在單純形迭代時確定不了唯一的l，或者B0是退化的可行基。構(gòu)造攝動問題: s.t. x0其中b()=b

16、+1p1+2p2 + n pn =b+下面證明，正數(shù)足夠小時 , ，這表明B0是攝動問題非退化可行基。因則設(shè) 的第i分量為是m維列向量，第i分量為 則：或?qū)懗梢?，則又當0足夠小時，總可以使若，則任0均可，若0，即所以當正數(shù)足夠小時，B。是攝動問題的非退化可行基。下面進一步證明當0足夠小時，攝動問題是非退化的。定理13.4.1 攝動問題 s.t. x0存在00, 使得對任何滿足 00，對任意：00，使0比所有這些正根還要小。則當：00，任意：00，攝動問題任何一個基變量不可能為0。由于多項式是的連續(xù)函數(shù)，而區(qū)間 (0, 0 )又沒有這些多項式的根，故每一多項式在（0，0 ）內(nèi)或者恒大于零，或者恒

17、小于零，二者必居其一。如果某一多項式在（0，0）內(nèi)恒大于零，則對于任意的，00足夠小，（1）若是攝動問題的基可行解，令=0，則是原問題的一個基可行解。（2）若攝動問題的基本最優(yōu)解。則是原問題的基本最優(yōu)解。 證明：（1）設(shè)攝動問題的一個基可行解，對應(yīng)基B。并設(shè)的分量為 (i=1m),由（*）式知基變量取值為：上式中令=0，則的基變量取值，(i=1m）因此，要證（1）只須證0，(=1m)（用反證法）若不然，存在 ，則對于充分小的0必有：（這與前面一開始的證明方法一樣可證），但這與攝動問題的基可行解矛盾。因而問題得證。并且這兩個問題的基本可行解與對應(yīng)同一可行基B。（2）現(xiàn)在取充分小后，用單純形法解攝

18、動問題，在迭代 過程中得到一系列的基本可行解, 因定理6已證明攝動問題是非退化的，則由單純形法收斂定理知若攝動問題有最優(yōu)解，必在有限步迭代得到基本最優(yōu)解，令=0，由上面（1）的結(jié)論知：相應(yīng)得到一系列原問題的基可行解：下面證明：是原問題的基本最優(yōu)解。因,對應(yīng)同一個B，判別數(shù)向量與向量b, b(）無關(guān)，而由于攝動問題和原問題有相同的A，B，C，所以對于同一個基B，兩者的判別數(shù)也相同，因此，如果攝動問題的基本最優(yōu)解，則也是原問題的基本最優(yōu)解。因為攝動問題是非退化的（00）且有了一個可行基B0，因而可通過有限次單純形法迭代，或求出基本最優(yōu)解）,那么也求得了原問題的基本最優(yōu)解，或判斷攝動問題有無界解，則

19、原問題也有無界解）。求攝動問題時，不必先求出的范圍只須讓正充分小就可以了。用單純形法求解攝動問題的過程基本上與原來的單純形放一致。13.5 Bland的避免循環(huán)的方法1776，R.G.Bland提出并說明了一種新的方法，避免單純形迭代出現(xiàn)循環(huán)。當時在國際上引起了很多人重視，并認為是線性規(guī)劃的一項很好成果。在方法上，比前面的都要簡單些，只須按下面規(guī)則選取基和出基變量，就不會產(chǎn)生循環(huán) 。規(guī)則I 若有幾個判別數(shù),則選取其中下極數(shù)小的標號作為K，（即選表上判別數(shù)小于0的最左邊一個），即若k=min ,則選為入基變量。規(guī)則 若有幾個同時達到最小那么選取其中下標最小的基變量作為出基變量，即若 則選為出基變

20、量。 定理8 （Bland規(guī)則）對SLP，在進行單純形法迭代才時，如果按照上面的規(guī)則和選取基 變量和出基變量，就不會出現(xiàn)循環(huán)。 此定理的證明見管梅谷，鄭漢鼎線性規(guī)劃P69-72。此方法也不舉例詳敘了 。注意，Bland 方法理論上很重要，但實際上迭代次數(shù)不一定比攝動法少。由于實際問題中出現(xiàn)循環(huán)，可在設(shè)計程序是安置一條打印目標函數(shù)值的命令，如果目標出數(shù)值長久不變，則表明出現(xiàn)循環(huán)，此時再采用一些簡單補救措施也就可以了，這樣做程序簡單，工作量也小。13.6 修正單純形法修正單純形法手算沒有優(yōu)越性，但在計算機上是極有用的，減少存貯空間，減少計算工作量，減少迭代誤差。此方法不便詳細運算，不講述，但務(wù)必要求學(xué)生掌握?，F(xiàn)在我們用-攝動法求解Bland 的例子。原問題有一個退化可行基，基變量是 退化基可行解（0，0，0，0，0，0，1），首先改變變量下標，使是基變量（5，6，7，1，2，3；1，2，3，4，4，5，6，7）得到問題的形式如下：st 相應(yīng)的攝動問題為：（充分?。㎝ax