1、線性規(guī)劃問題解的基本概念 單純形解法 解的最優(yōu)性檢驗 表解形式的單純形法 單純形解法的一些問題及其處理方法,1.3 單純形算法,max z = CX AX= b (1) X 0 (2),可行解：滿足約束(1)，(2)的X= (x1 , , xn)T 稱為LP問題的可行解，全部可行解的集合稱為可行域。,最優(yōu)解：使目標函數(shù)達到最大值的的可行解稱為LP問題的最優(yōu)解。,(LP),1.3 單純形算法,一、線性規(guī)劃問題解的基本概念,1、可行解與最優(yōu)解,s.t.,1.3 單純形算法,max z = CX s.t. AX = b X 0,max z = CX s.t. AX = b X 0,C = (c1 c

2、2 cn ),標準形的矩陣表示形式：,1.3 單純形法,基：設A是約束方程組mn維系數(shù)矩陣，其秩為m。B是系數(shù)矩陣A中mm階可逆子矩陣(即B0)，稱B是線性規(guī)劃問題的一個基矩陣（或簡稱基），也即矩陣B是由m個線性獨立的列向量組成(也即矩陣B是由m個線性無關的列向量組成),其余部分稱為非基矩陣，記為N。不失一般性,可假設,見下頁,1.3 單純形算法,2、基、基向量、基變量,基向量：基B中的列Pj (j=1,2,m）稱為基向量，其余稱為非基向量。 基變量：與基向量Pj相對應的變量(j=1,2,m)稱為基變量，記為XB；與非基向量對應的變量稱為非基變量，記其組成的向量為XN,1.3 單純形算法,基,

3、基向量,基變量,非基,非基向量,非基變量,1.3 單純形算法,1.3 單純形算法,1.3 單純形算法,3、基本解、基本可行解、可行基,當A中的基B取定后，不妨設B表示A中的前m 列，則可記A（B, N），相應 約束中的AX=b可表示為 ，即 ，當取 時，有 , 。也可見書P7,稱AX=b的解 ，為線性規(guī)劃的一個基本解；,基本解,基本可行解：滿足非負條件的基本解稱為基本可行解（簡稱基可行解）?；究尚薪獾姆?分量的數(shù)目不大于m，并且為非負。線性規(guī)劃問題的基本可行解X對應于可行域的頂點。,1.3 單純形算法,可見：一個基本解是由一個基決定的。注意：基本解僅是資源約束的解，并未要求其非負，因此其未必

4、可行。,可行基：對應于基本可行解的基稱為可行基。滿足約束方程組的基本解的數(shù)目至多是 個。,1.3 單純形算法,上二組概念間的聯(lián)系： 系數(shù)陣A中可找出若干個基B 每個基B都對應于一個基本解 非負的基本解就是基本可行解,幾種解之間的關系： 非可行解,1.3 單純形算法,1.3 單純形算法,在下面線性規(guī)劃中，找出滿足約束條件的所有基本解，并指出哪些是基本可行解，并帶入目標函數(shù)，確定哪一個是最優(yōu)解。,1.3 單純形算法,1）解：此線性規(guī)劃問題的系數(shù)矩陣A為 ，令 A=（P1,P2,P3,P4），則,P1,P2線性無關，選擇(P1,P2)為基，x1,x2為基變量 可得 2x1+3x2=8+x3+4x4，

5、令非基變量x3=x4=0,得 2x1+3x2=8 x1-2x2=-3-6x3+7x4 x1-2x2=-3,解得： x1=1,x2=2，基解x(1)=(1,2,0,0)T為可行解。Z1=21+32+40+70=8,1.3 單純形算法,(2) P1,P3線性無關，選擇(P1,P3)為基，x1,x3為基變量 可得 2x1-x3=8-3x2+4x4，令非基變量x2=x4=0,得 2x1-x3=8 x1+6x3=-3+2x2+7x4 x1+6x3=-3,解得：x1=45/13,x3=-14/13，基解x(2)=(45/13,0, -14/13,0)T為可行解。,(3) P1,P4線性無關，選擇(P1,P

6、4)為基，x1,x4為基變量 可得 2x1-4x4=8-3x2+x3，令非基變量x2=x3=0,得 2x1-4x4=8 x1-7x4=-3+2x2-6x3 x1-7x4=-3,解得：x1=34/5,x4=7/5，基解x(3)=(34/5, 0,0,7/5)T為可行解，Z3=234/5+30+40+77/5=117/5,1.3 單純形算法,解得：x2=45/16,x3=7/16，基解x(2)=(0, 45/16, 7/16 ,0)T為可行解。Z4=20+345/16+47/16+70=163/16,(5) P2,P4線性無關，選擇(P2,P4)為基，x2,x4為基變量 可得 3x2-4x4=8-

7、2x1+x3，令非基變量x1=x3=0,得 3x2-4x4=8 -2x2-7x4=-3-x1-6x3 -2x2-7x4=-3,解得：x2=68/29,x4=-7/29，基解x(3)=(0, 68/29,0,-7/29)T為非可行解,(4) P2,P3線性無關，選擇(P2,P3)為基，x2,x3為基變量 可得 3x2-x3=8-2x1+4x4，令非基變量x1=x4=0,得 3x2-x3=8 -2x1+6x3=-3-x1+7x4 -2x2+6x3=-3,1.3 單純形算法,(6) P3,P4線性無關，選擇(P3,P4)為基，x3,x4為基變量 可得 x3-4x4=8-2x1-3x2，令非基變量x1

8、=x2=0,得 x3-4x4=8 6x3-7x4=-3-x1+2x2 6x3-7x4=-3,解得：x3=-68/31,x4=-45/31，基解x(6)=(0, 0, -68/31,- 45/31)T為非可行解,比較Z1,Z3,Z4可知，Z3=117/5為最大值。,1.3 單純形算法,二、基本定理,1、線性規(guī)劃的可行域是一個凸多面體； 凸多面體是凸集的一種。所謂凸集是指：在集中任兩點的連線仍屬此集。直觀上講：凸集無凹入部分，其內(nèi)部沒有洞。,判斷下面圖形是否為凸集,凸集K內(nèi)任一點X（除頂點外），能用K內(nèi)的不同的兩個點X1,X2（X1,X2K）的線性組合表示為 頂點不位于凸集K中的任意不同兩點的連線

9、內(nèi)。,1.3 單純形算法,二、基本定理,2、線性規(guī)劃可行域的頂點與基本可行解一一對應。 3、線性規(guī)劃的最優(yōu)解（若存在的話）必能在可行域的頂點獲得。,單純形法是求解線性規(guī)劃的主要算法，1947年由美國斯坦福大學教授丹捷格提出。 盡管在其后的幾十年中，又有一些算法問世，但單純形法以其簡單實用的特色始終保持著絕對的“市場”占有率。,1.3 單純形算法,1.3 單純形算法,從某個角頂可行解開始-起步 向目標函數(shù)值更好的鄰近可行頂點移動 判斷此頂點是否為最優(yōu)解：檢查它是否比它的臨近頂點的目標函數(shù)值都好，若是，則是最優(yōu)解；若不是，則重復上述第二步。,單純形算法的基本思路,1.3 單純形算法,三、單純形法的

10、步驟,確定初始基本可行解,檢驗其是否最優(yōu)？,尋找更好的基本可行解,否,STOP,是,單純形法是 一種迭代的算 法，它的思想是 在可行域的頂 點基本可行 解中尋優(yōu)。由于 頂點是有限個,因 此，算法經(jīng)有限 步可終止。 方法前提：模型化為標準型,1.3 單純形算法,由于基可行解是由一個可行基決定的，因此，確定初始基可行解 相當于確定一個初始可行基 。 方法：若A中含有I，則 =I; 若A中不含I，可用人工變量法構造一個I 問題：若 =I，則 =?。 例1.1中的 =?,1、確定初始基可行解,例1.1,1.3 單純形算法,1.3 單純形算法,s.t.,若令XN=0則可以得到以下結(jié)論： （1）線性規(guī)劃的

11、目標函數(shù)值為CBB-1b； （2）基變量的解為B-1b； （3）對于給定的基，非基變量的檢驗數(shù)向量為N=CN-CBB-1N。 當所有非基變量檢驗數(shù)N0，則為最優(yōu)解。,線性規(guī)劃的典則形式：,線性規(guī)劃的典則形式：,s.t.,s.t.,max Z=CBB-1b+(CN-CBB-1N)XN XB=B-1b-B-1NXN XB,XN0,令 則目標函數(shù)可寫成,1.3 單純形算法,對線性規(guī)劃問題，如果令非基變量為0，代入目標函數(shù)，可以化簡得：,書(p13),（最優(yōu)解判定定理）若X(0)=(b1,b2, ,bm,0, ,0)T，對應于基B的基本可行解，且對于一切j=m+1, ,n，有j0，則X(0)為線性規(guī)劃

12、問題的最優(yōu)解。 （無窮多最優(yōu)解判別定理）若X(0)=(b1,b2, ,bm,0, ,0)T為對應于基B的基本可行解，且對于一切j=m+1, ,n，有j0，又存在某個非基變量的檢驗數(shù)m+k=0，則線性規(guī)劃問題有無窮多最優(yōu)解。 （無界解判定定理）若X(0)=(b1,b2, ,bm,0, ,0)T為對應于基B的基本可行解，有一個m+k0而對于i=1,2, ,m有ai,m+k 0則線性規(guī)劃問題為無界解。,1.3 單純形算法,1.3 單純形算法,方法：（1）計算每個xj 的檢驗數(shù)j= cj - CBB-1Pj （2）若所有j0 ，則當前解為最優(yōu)； 否則，至少有k0 ，轉(zhuǎn)步驟3。,1.3 單純形算法,3、

13、尋找更好的基可行解（基變換）,由于基可行解與基對應，即尋找一個新的基可行解，相當于從上一個基B0變換為下一個新的基B1，具體做法是從原可行基中用一個非基列向量換一個基列向量(換后當然要保證這些向量線性無關)，得到一個新的基。因此，本步驟也稱為基變換。,基變換的原則：,改善：Z1Z0 可行：B1-1b0,變換的方法：（P1, Pl, , Pk, , Pn） 換入變量（又稱進基）保證“改善”，令k0對應的Pk進基 換出變量（又稱出基）保證“可行”，由XB=B-1b-B-1NXN 0可決定出基,1.3 單純形算法,基變換：,（1）換入變量的確定（又成進基）保證“改善” ： 當某些非基變量的檢驗數(shù)j0

14、時，如果xj增加，則目標函數(shù)值增加。當由兩個或兩個以上j0時，選擇j0中的最大者，即j=maxll0，j對應的變量xj為換入變量（就是下一個基的基變量）。 （2）換出變量的確定（又稱出基）保證“可行”： 是使原基本可行解某一個正分量xl變?yōu)?，同時保持其余分量均為非負。按照“最小比例原則”，也稱原則。 即,選基變量xl為換出變量,1.3 單純形算法,在確定換入變量xj與換出變量xl后，要把xj和 xl位置對換，也即把xj所對應的列向量變成單位向量。只需對系數(shù)矩陣的增廣矩陣進行行變換即可，稱alj為旋轉(zhuǎn)元（也稱為主元）。也就是以主元行為基準，將主元變成1，主元列變成單位向量。同時在XB列中將xl

15、換成xj，在CB列中將Cl換成Cj,（3）旋轉(zhuǎn)運算（迭代運算）,1.3 單純形算法,（3）旋轉(zhuǎn)運算（迭代運算）,以表中元素 alj 進行基變換：將第 l 行每個元素除以alj， 再將第l行每個元素乘以 -aij/alj 加到第 i 行（i1，2， m，il），將第 l 行每個元素乘以 -j/alj 加到檢驗數(shù)行。,1.3 單純形算法,總結(jié)單純形法的具體步驟：,1、將線性規(guī)劃問題標準化，確定初始可行基，建立初始單純形表。據(jù)此可寫出初始基本可行解和相應的目標函數(shù)值。 2、檢查檢驗數(shù)行中對應于非基變量的各個檢驗數(shù)k，若所有的k0，則由最優(yōu)性判別準則，現(xiàn)行表的基本可行解就是最優(yōu)解，停止計算，否則轉(zhuǎn)入下

16、一步。 3、在所有k0中，如果有一個j對應的系數(shù)列向量pj0(也就是與它同列的各個aij0)，則此問題沒有有限最優(yōu)解，停止計算，否則轉(zhuǎn)入下一步。,1.3 單純形算法,4、根據(jù)j=maxkk0，kIN（ IN 為非基變量指標集），確定xj為換入變量（即新基的基變量），再根據(jù) 5、以alj為主元素進行基變換，在表中用 把alj表示出來，利用矩陣初等行變換，以主元行為基準，將主元素alj變成1，主元列變成單位向量。同時在XB列中將xl換成xj，在CB列中將Cl換成Cj。 6、得到新的單純形表，重復以上步驟，直至得到最優(yōu)解為止。,單純形法的具體步驟：,確定xl為換出變量（即新基的非基變量）,1.3 單

17、純形算法,利用單純形算法求解例1.1,1.3 單純形算法,解：化成標準型,1.3 單純形算法,解：建立單純形表,解：確定換入變量和換出變量，進行初等變換,1.3 單純形算法,1.3 單純形算法,此時，檢驗數(shù)全部小于等于0，目標函數(shù)值已不可能再增大，于是得最優(yōu)解X*=(2,5,0,4,0)T，目標函數(shù)的最大值Z*=19,1.3 單純形算法,例1.10 利用單純形法求解線性規(guī)劃問題,Max Z = 2x1+3x2 2x1+2x212 x1+2x28 4x1 16 4x2 12 x1,x2,x3,x40,s.t.,1.3 單純形算法,解：化成標準型,1.3 單純形算法,解：建立單純形表,1.3 單純形算法,解：化成標準型,當出現(xiàn)兩個或更多的相同時，我們稱出現(xiàn)退化問題。此時，在相同對應的變量中選擇下標最大的那個基變量為換出變量；同時如果下弧線有兩個或更多最大的檢驗數(shù)大于零且相同時，在相同對應的變量中選擇下標最小的那個基變量為換入變量。,所有檢驗數(shù)都小于等于0，目標函數(shù)已不可能再增大，得最優(yōu)解為X*=(4