會計學1單純形法大M法求解線性規劃問題2

考慮到如下線性規劃問題

其中Ａ一個m×n矩陣，且秩為m，ｂ總可以被調整為一個m維非負列向量，Ｃ為n維行向量，Ｘ為n維列向量。根據線性規劃基本定理：如果可行域Ｄ={Ｘ∈Ｒn/ＡＸ=ｂ，Ｘ≥0}非空有界，則Ｄ上的最優目標函數值Ｚ=ＣＸ一定可以在Ｄ的一個頂點上達到。這個重要的定理啟發了Dantzig的單純形法，即將尋優的目標集中在D的各個頂點上。單純形法的一般原理

第1頁/共69頁3

Dantzig的單純形法把尋優的目標集中在所有基本可行解（即可行域頂點）中。其基本思路是從一個初始的基本可行解出發，尋找一條達到最優基本可行解的最佳途徑。單純形法的一般步驟如下：（1）尋找一個初始的基本可行解。（2）檢查現行的基本可行解是否最優，如果為最優，則停止迭代，已找到最優解，否則轉一步。（3）移至目標函數值有所改善的另一個基本可行解，然后轉會到步驟（2）。第2頁/共69頁4

確定初始的基本可行解

確定初始的基本可行解等價于確定初始的可行基，一旦初始的可行基確定了，那么對應的初始基本可行解也就唯一確定

為了討論方便，不妨假設在標準型線性規劃中，系數矩陣Ａ中前m個系數列向量恰好構成一個可行基，即Ａ=（ＢＮ），其中Ｂ=（Ｐ1，Ｐ2，…Ｐm）為基變量x1，x2，…xm的系數列向量構成的可行基，Ｎ=(Ｐm+1，Pm+2，

…Pn)為非基變量xm+1，xm+2，

…xn的系數列向量構成的矩陣。第3頁/共69頁5所以約束方程就可以表示為

用可行基Ｂ的逆陣Ｂ-1左乘等式兩端，再通過移項可推得：若令所有非基變量,則基變量由此可得初始的基本可行解第4頁/共69頁6問題：要判斷m個系數列向量是否恰好構成一個基并不是一件容易的事。基由系數矩陣Ａ中m個線性無關的系數列向量構成。但是要判斷m個系數列向量是否線性無關并非易事。即使系數矩陣Ａ中找到了一個基B，也不能保證該基恰好是可行基。因為不能保證基變量ＸB=Ｂ-1b≥0。為了求得基本可行解，必須求基Ｂ的逆陣Ｂ-1。但是求逆陣Ｂ-1也是一件麻煩的事。結論：在線性規劃標準化過程中設法得到一個m階單位矩陣I作為初始可行基Ｂ，第5頁/共69頁7若在化標準形式前，約束方程中有“≥”不等式，那么在化標準形時除了在方程式左端減去剩余變量使不等式變成等式以外，還必須在左端再加上一個非負新變量，稱為人工變量．若在化標準形式前，約束方程中有等式方程，那么可以直接在等式左端添加人工變量。為了設法得到一個m階單位矩陣I作為初始可行基Ｂ，可在性規劃標準化過程中作如下處理：

若在化標準形式前，m個約束方程都是“≤”的形式，那么在化標準形時只需在一個約束不等式左端都加上一個松弛變量xn+i(i=12…m)。第6頁/共69頁8判斷現行的基本可行解是否最優

假如已求得一個基本可行解將這一基本可行解代入目標函數，可求得相應的目標函數值

其中分別表示基變量和非基變量所對應的價值系數子向量。第7頁/共69頁9

要判定是否已經達到最大值，只需將代入目標函數，使目標函數用非基變量表示，即：

其中稱為非基變量ＸN的檢驗向量，它的各個分量稱為檢驗數。若σN的每一個檢驗數均小于等于0，即σN≤0，那么現在的基本可行解就是最優解。第8頁/共69頁10定理1：最優解判別定理對于線性規劃問題若某個基本可行解所對應的檢驗向量，則這個基本可行解就是最優解。定理2：無窮多最優解判別定理

若是一個基本可行解，所對應的檢驗向量，其中存在一個檢驗數σm+k=0，則線性規劃問題有無窮多最優解。第9頁/共69頁11

基本可行解的改進

如果現行的基本可行解Ｘ不是最優解，即在檢驗向量中存在正的檢驗數，則需在原基本可行解Ｘ的基礎上尋找一個新的基本可行解，并使目標函數值有所改善。具體做法是：先從檢驗數為正的非基變量中確定一個換入變量，使它從非基變量變成基變量（將它的值從零增至正值），再從原來的基變量中確定一個換出變量，使它從基變量變成非基變量（將它的值從正值減至零）。由此可得一個新的基本可行解，由可知，這樣的變換一定能使目標函數值有所增加。第10頁/共69頁12

換入變量和換出變量的確定：換入變量的確定—

最大增加原則

假設檢驗向量，若其中有兩個以上的檢驗數為正，那么為了使目標函數值增加得快些，通常要用“最大增加原則”，即選取最大正檢驗數所對應的非基變量為換入變量，即若

則選取對應的為換入變量，由于且為最大，因此當由零增至正值，可使目標函數值最大限度的增加。第11頁/共69頁13

換出變量的確定—

最小比值原則如果確定為換入變量，方程

其中為Ａ中與對應的系數列向量。現在需在中確定一個基變量為換出變量。當由零慢慢增加到某個值時，的非負性可能被打破。為保持解的可行性，可以按最小比值原則確定換出變量：若則選取對應的基變量為換出變量。第12頁/共69頁14

定理3：無最優解判別定理若是一個基本可行解，有一個檢驗數，但是，則該線性規劃問題無最優解。證：令，則得新的可行解將上式代入

因為,故當λ→+∞時，Z→+∞。第13頁/共69頁15

用初等變換求改進了的基本可行解

假設Ｂ是線性規劃的可行基，則令非基變量，則基變量。可得基本可行解。用逆陣左乘約束方程組的兩端，等價于對方程組施以一系列的初等“行變換”。變換的結果是將系數矩陣Ａ中的可行基Ｂ變換成單位矩陣I，把非基變量系數列向量構成的矩陣Ｎ變換成，把資源向量b變換成。第14頁/共69頁16

且改進了的基本可行解只是在Ｘ的基變量的基礎上用一個換入變量替代其中一個換出變量，其它的基變量仍然保持不變。這些基變量的系數列向量是單位矩陣I中的單位向量。為了求得改進的基本可行解，只需對增廣矩陣施行初等行變換，將換入變量的系數列向量變換成換出變量所對應的單位向量即可。

由于行初等變換后的方程組與原約束方程組或同解第15頁/共69頁17例1解：(１)確定初始的基本可行解。，基變量，非基變量。第16頁/共69頁18(2)檢驗

是否最優。檢驗向量

因為σ1=3，σ3=4均大于零，所以不是最優解。第17頁/共69頁19（3）基本可行解的改進①

選取換入變量因為max{3，4}=4，取x3為換入變量。②

選取換出變量且，選取x4為換出變量.第18頁/共69頁20（4）求改進了的基本可行解對約束方程組的增廣矩陣施以初等行變換，使換入變量x3所對應的系數列向量變換成換出變量x4所對應的單位向量,注意保持基變量x5的系數列向量為單位向量不變。第一行除以２第二行減去第一行第19頁/共69頁21——————————————————————————可得改進的基本可行解。

，基變量，非基變量。

基本可行解

目標函數值易見目標函數值比原來的Z=-1增加了，再轉向步驟(2)第20頁/共69頁22（2）檢驗

是否最優。檢驗向量

因為，所以仍不是最優解。第21頁/共69頁23（3）基本可行解的改進①

選取換入變量因為，取為換入變量。②

選取換出變量且，選取為換出變量.第22頁/共69頁24（4）求改進了的基本可行解對約束方程組的增廣矩陣施以初等行變換，使換入變量所對應的系數列向量變換成換出變量所對應的單位向量

,第二行乘以２/５第一行減以第二行的１/２倍第23頁/共69頁25——————————————————————————可得改進的基本可行解。

，基變量，非基變量

基本可行解

目標函數值比Z=15增加了，再轉向步驟(2)第24頁/共69頁26（2）檢驗

是否最優。檢驗向量

因為所有檢驗數均小于零，所以是最優解，第25頁/共69頁27表格單純形法

通過例１我們發現，在單純形法的求解過程中，有下列重要指標：每一個基本可行解的檢驗向量根據檢驗向量可以確定所求得的基本可行解是否為最優解。如果不是最優又可以通過檢驗向量確定合適的換入變量。每一個基本可行解所對應的目標函數值通過目標函數值可以觀察單純形法的每次迭代是否能使目標函數值有效地增加，直至求得最優目標函數為止。

在單純形法求解過程中，每一個基本可行解Ｘ都以某個經過初等行變換的約束方程組中的單位矩陣Ι為可行基。當Ｂ=Ｉ時，Ｂ-1=Ｉ，易知：第26頁/共69頁28

可將這些重要結論的計算設計成如下一個簡單的表格，即單純形表來完成：C

CBCN

θ

CB

XB

b

X1X2

···Xm

Xm+1Xm+2···Xn

C1C2..Cm

X1X2

.Xm

b1b2..bm

I

N

θ1θ2..θm

Z

CBb

0

CN-CBN

第27頁/共69頁29例2、試利用單純形表求例1中的最優解解：

得初始的單純形表：初始基本可行解，Z=-1，122108x4-130400-1Z341017x51x1x2x3x4x5bXBCBΘ523-11C第28頁/共69頁30

換入變量，換出變量，２為主元進行旋轉變換基本可行解，Z=15，1/2

1

1

1/2

04x331-40-2015Z5/230-1/213x51

x1

x2

x3

x4

x5bXBCBΘ523-11C122108x4-130400-1Z341017x51x1x2x3x4x5bXBCBΘ523-11C8/27/1第29頁/共69頁31

最優解最優值

換入變量，換出變量，５/２為主元進行旋轉變換4/1/21/2

1

1

1/2

04x331-40-2015Z3/5/25/230-1/213x51

x1

x2

x3

x4

x5bXBCBΘ523-11C02/513/5-1/517/5x330-26/50-9/5-2/581/5Z16/50-1/52/56/5x15x1x2x3x4x5bXBCBΘ523-11C第30頁/共69頁32例3、用單純形方法求解線性規劃問題解：本題的目標函數是求極小化的線性函數，可以令則這兩個線性規劃問題具有相同的可行域和最優解，只是目標函數相差一個符號而已。

第31頁/共69頁33010103x220012-12x30-010103x224/1101004x303/1010103x40_101004x300000-18Z’100-212x11100-206Z’2/1100-212x50120000Z’8/2120018x50x1x2x3x4x5bXBCBΘ12000C最優解最優值2/23/1-第32頁/共69頁34

因為非基變量x4的檢驗數σ4=0，由無窮多最優解判別定理，本例的線性規劃問題存在無窮多最優解。事實上若以x4為換入變量，以x3為換出變量，再進行一次迭代，可得一下單純形表：最優解最優值最優解的一般表示式C12000ΘCBXBbx1x2x3x4x5021x4x2x1124001/21-1/201-1/201/210100Z’80000-1第33頁/共69頁35對于極小化的線性規劃問題的處理：先化為標準型，即將極小化問題變換為極大化問題，然后利用單純形方法求解．直接利用單純形方法求解，但是檢驗是否最優的準則有所不同，即：若某個基本可行解的所有非基變量對應的檢驗數（而不是≤０），則基本可行解為最優解．否則采用最大減少原則（而非最大增加原則）來確定換入變量，即：若則選取對應的非基變量xm+k為換入變量．確定了換入變量以后，換出變量仍采用最小比值原則來確定。第34頁/共69頁36借助人工變量求初始的基本可行解

若約束方程組含有“≥”不等式，那么在化標準形時除了在方程式左端減去剩余變量，還必須在左端加上一個非負的人工變量。因為人工變量是在約束方程已為等式的基礎上，人為的加上去的一個新變量，因此加入人工變量后的約束方程組與原約束方程組是不等價的。加上人工變量以后，線性規劃的基本可行解不一定是原線性規劃的問題的基本可行解。只有當基本可行解中所有人工變量都為取零值的非基變量時，該基本可行解對原線性規劃才有意義。因為此時只需去掉基本可行解中的人工變量部分，剩余部分即為原線性規劃的一個基本可行解．而這正是我們引入人工變量的主要目的。第35頁/共69頁37

考慮線性規劃問題：為了在約束方程組的系數矩陣中得到一個m階單位矩陣作為初始可行基，在每個約束方程組的左端加上一個人工變量

可得到：

第36頁/共69頁38

————————————————————————

添加了m個人工變量以后，在系數矩陣中得到一個m階單位矩陣，以該單位矩陣對應的人工變量為基變量，即可得到一個初始的基本可行解這樣的基本可行解對原線性規劃沒有意義的。但是我們可以從X(0)出發進行迭代，一旦所有的人工變量都從基變量迭代出來，變成只能取零值的非基變量，那么我們實際上已經求得了原線性規劃問題的一個初始的基本可行解。此時可以把所有人工變量剔除，開始正式進入求原線性規劃最優解的過程。第37頁/共69頁39

大M法

大M法首先將線性規劃問題化為標準型。如果約束方程組中包含有一個單位矩陣I，那么已經得到了一個初始可行基。否則在約束方程組的左邊加上若干個非負的人工變量，使人工變量對應的系數列向量與其它變量的系數列向量共同構成一個單位矩陣。以單位矩陣為初始基，即可求得一個初始的基本可行解。為了求得原問題的初始基本可行解，必須盡快通過迭代過程把人工變量從基變量中替換出來成為非基變量。為此可以在目標函數中賦予人工變量一個絕對值很大的負系數-Ｍ。這樣只要基變量中還存在人工變量，目標函數就不可能實現極大化。以后的計算與單純形表解法相同，Ｍ只需認定是一個很大的正數即可。假如在單純形最優表的基變量中還包含人工變量，則說明原問題無可行解。否則最優解中剔除人工變量的剩余部分即為原問題的初始基本可行解。第38頁/共69頁40例4、用大M法求解下面的線性規劃問題:解：首先將原問題化為標準型添加人工變量，并在目標函數中分別賦予-Ｍ

第39頁/共69頁41-01-1/2-1/201/21/23/2X2210-1/21/201/2-1/21/2X1-1--110-10011X221/220-1101-11X6-M1/1-110-10011X7-M2/111-100102X6-M001/23/20-1/2-M-3/2-M5/2Z001/21/21-1/2-1/23/2X501+2M0-M2+M00-2-2M2-MZ2/1100110-12X50-12+2M-M-M000-3MZ3/101001003X50

X1x2x3x4x5x6x7bXBCBθ

-12000-M-MC第40頁/共69頁4201001003X22100110-12X4011-100102X2220-1101-11X40-01-1/2-1/201/21/23/2X221/2/1/210-1/21/201/2-1/21/2X1-1-1000-2-M-M6Z-10101-101X30-30200-2-M-M4Z-10101-101X50001/23/20-1/2-M-3/2-M5/2Z3/2/1/2001/21/21-1/2-1/23/2X50X1x2x3x4x5x6x7bXBCBθ-12000-M-MC最優解最優值第41頁/共69頁43兩階段法

兩階段法引入人工變量的目的和原則與大M法相同，所不同的是處理人工變量的方法。兩階段法的步驟：求解一個輔助線性規劃。目標函數取所有人工變量之和，并取極小化；約束條件為原問題中引入人工變量后包含一個單位矩陣的標準型的約束條件。如果輔助線性規劃存在一個基本可行解，使目標函數的最小值等于零，則所有人工變量都已經“離基”。表明原問題已經得了一個初始的基本可行解，可轉入第二階段繼續計算；否則說明原問題沒有可行解，可停止計算。求原問題的最優解。在第一階段已求得原問題的一個初始基本可行解的基礎上，繼續用單純形法求原問題的最優解第42頁/共69頁44例5、用兩階段法求解例4中的線性規劃問題。解：首先將問題化為標準型添加人工變量x6,x7,并建立輔助線性規劃如下：由于輔助線性規劃的目標函數是極小化，因此最優解的判別準則應為：第43頁/共69頁4501-1/2-1/201/21/23/2X2010-1/21/201/2-1/21/2X10--110-10011X201/220-1101-11X611/1-110-10011X712/111-100102X6100000110W001/21/21-1/2-1/23/2X50-201-10021W2/1100110-12X500-2110003W3/101001003X50x1x2x3x4x5x6x7bXBCBθ0000011C輔助規劃所有檢驗數：原問題已得一個初始基本可行解，第44頁/共69頁46由上表可知，通過若干次旋轉變換，原問題的約束方程組已變換成包含一個單位矩陣的約束方程組該約束方程組可作為第二階段初始約束方程組，將目標函數則還原成原問題的目標函數，可繼續利用單純形表求解。第45頁/共69頁47-1000-26Z1001101001-10101231X4X2X3020-302004Z20-11011-100-10101121X4X2X5020

001/23/205/2Z1/2/1/2-3/2/1/210-1/21/2001-1/2-1/20001/21/211/23/23/2X1X2X5-120

x1x2x3x4x5

bXBCBθ

-12000C可得最優解，目標函數值maxZ=6，與用大M法的結果完全相同。第46頁/共69頁48單純形表與線性規劃問題的討論

無可行解

通過大Ｍ法或兩階段法求初始的基本可行解。但是如果在大Ｍ法的最優單純形表的基變量中仍含有人工變量，或者兩階段法的輔助線性規劃的目標函數的極小值大于零，那么該線性規劃就不存在可行解。人工變量的值不能取零，說明了原線性規劃的數學模型的約束條件出現了相互矛盾的約束方程。此時線性規劃問題的可行域為空集。第47頁/共69頁49例6、求解下列線性規劃問題解：首先將問題化為標準型令，則

故引入人工變量，并利用大M法求解第48頁/共69頁50C

-3-2-1000-M-M

CB

XB

b

x1x2x3x4x5x6x7x8

θ

0-M-M

x4x7x8

643

1111000010-10-101001-100-101

6/1-3/1

Z’

-7M

-6-4M

-15-M

-3+M-2+M-1-2M0-M-M00

0-M-2

x4x7x2

343

1021010-110-10-101001-100-101

3/14/1-

Z’

Z’

-3+M0-3-M0-M-202-M

-3-M-2

x1x7x2

313

1021010-100-3-1-1-11101-100-101

003-3M3-M-M1-M0-1

在以上最優單純形表中，所有非基變量檢驗數都小于零，但在該表中人工變量x7=1為基變量，所以原線性規劃不存在可行解。第49頁/共69頁51無最優解

無最優解與無可行解時兩個不同的概念。無可行解是指原規劃不存在可行解，從幾何的角度解釋是指線性規劃問題的可行域為空集；無最優解則是指線性規劃問題存在可行解，但是可行解的目標函數達不到最優值，即目標函數在可行域內可以趨于無窮大（或者無窮小）。無最優解也稱為有限最優解，或無界解。

判別方法：無最優解判別定理在求解極大化的線性規劃問題過程中，若某單純形表的檢驗行存在某個大于零的檢驗數，但是該檢驗數所對應的非基變量的系數列向量的全部系數都為負數或零，則該線性規劃問題無最優解，可以可以第50頁/共69頁52例7、試用單純形法求解下列線性規劃問題：解：引入松弛變量x3,x4化為標準型C2200θ

CXB

B

x1

x2

x3

x4

0X3

1-11100X4

2-1/2101Z02200因但所以原問題無最優解第51頁/共69頁53

退化解

當線性規劃問題的基本可行解中有一個或多個基變量取零值時，稱此基本可行解為退化解。產生的原因：在單純形法計算中用最小比值原則確定換出變量時，有時存在兩個或兩個以上相同的最小比值θ，那么在下次迭代中就會出現一個甚至多個基變量等于零。遇到的問題：當某個基變量為零，且下次迭代以該基變量作為換出變量時，目標函數并不能因此得到任何改變（由旋轉變換性質可知，任何一個換入變量只能仍取零值，其它基變量的取值保持不變）。通過基變換以后的前后兩個退化的基本可行解的坐標形式完全相同。從幾何角度來解釋，這兩個退化的基本可行解對應線性規劃可行域的同一個頂點，解決的辦法：最小比值原則計算時存在兩個及其以上相同的最小比值時，選取下標最大的基變量為換出變量，按此方法進行迭代一定能避免循環現象的產生（攝動法原理）。第52頁/共69頁54例8、求解下述線性規劃問題：解：引入松弛變量化標準型第53頁/共69頁55000-242-8030Z-5-60-420-805Z10001001x3

212060-2411x1

3321300-803x5

00-30-425-800Z11001001x7

00106-1-2410x1

30-1130-3-800x5

0-11001001x7

000106-1-2410x6

0000136-4-3210x5

0x7

x6

x5

x4

x3

x2

x1

b

XB

CB

000-242-803C

θ

第一次迭代中使用了攝動法原理，選擇下標為6的基變量x6離基。可得最優解，目標函數值maxZ=５，第54頁/共69頁56

無窮多最優解

無窮多最優解判別原理：若線性規劃問題某個基本可行解所有的非基變量檢驗數都小于等于零，但其中存在一個檢驗數等于零，那么該線性規劃問題有無窮多最優解。例３：最優表：非基變量檢驗數，

所以有無窮多最優解。最優解集為可行域兩個頂點的凸組合：C12000θCBXBbx1x2x3x4x5021x3x2x12320012-101010100-212/23/1-Z’80000-1第55頁/共69頁57改進單純形法的特點

利用單純形表求解線性規劃時，每一次迭代都把整個單純形表計算一遍，事實上我們關心的只是以下一些數據：基本可行解，其相應的目標函數值，非基變量檢驗數，及其換入變量，設主元列元素，及其換出變量，設

利用它們可得到一組新的基變量以及新的可行基Ｂ1。改進單純形法為基變量下標為非基變量下標第56頁/共69頁58

對任一基本可行解Ｘ，只要知道，上述關鍵數據都可以從線性規劃問