1、第五章,單純形法 與單純形表,線性規(guī)劃 Linear Programming（LP）,圖解法的啟示 線性規(guī)劃問題解的可能情況 a.唯一最優(yōu)解 b.無窮多最優(yōu)解 c.無解（沒有有界最優(yōu)解，無可行解） 若線性規(guī)劃問題的可行域非空，則可行域是一個(gè)凸集； 若線性規(guī)劃問題的最優(yōu)解存在，則一定可以在可行域的凸集的某個(gè)頂點(diǎn)上達(dá)到。,線性規(guī)劃 Linear Programming（LP）,單純形法 單純形方法是G.B.Danzig于1947年首先發(fā)明的。近50年來，一直是求解線性規(guī)劃的最有效的方法之一，被廣泛應(yīng)用于各種線性規(guī)劃問題的求解。本節(jié)討論單純形法的基本概念、原理及算法。,線性規(guī)劃 Linear Pro

2、gramming（LP）,單純形法 給定線性規(guī)劃問題（標(biāo)準(zhǔn)形式）,max z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 s .t. am1x1 + am2x2 + amnxn = bm xj 0 （j=1，2 n）,線性規(guī)劃 Linear Programming（LP）,單純形法 一、線性規(guī)劃問題的解的概念 可行解 最優(yōu)解 基 基解（基本解） 基可行解 可行基,線性規(guī)劃 Linear Programming（LP）,單純形法 二、凸集及其頂點(diǎn) 凸集 頂點(diǎn)（極點(diǎn)）,凸集,凹集,線性規(guī)劃

3、 Linear Programming（LP）,1,2,3,4,5,6,7,8,線性規(guī)劃 Linear Programming（LP）,單純形法 三、線性規(guī)劃基本定理 基本定理 1 線性規(guī)劃所有可行解組成的集合S= X | AX = b，X 0 是凸集。 基本定理 2 X是線性規(guī)劃問題的基本可行解的充要條件為是 X 是凸集S= X | AX = b，X 0 的極點(diǎn)。 基本定理 3 給定線性規(guī)劃問題， A是秩為 m 的 mn 矩陣， （i） 若線性規(guī)劃問題存在可行解，則必存在基本可行解 （ii）若線性規(guī)劃問題存在有界最優(yōu)解，則必存在有界最優(yōu)基本可行解。,線性規(guī)劃 Linear Programmi

4、ng（LP）,單純形法 單純形法迭代原理及其思路 單純形法的初步討論 例1.8 求解LP問題,化為標(biāo)準(zhǔn)型,線性規(guī)劃 Linear Programming（LP）,單純形法 此線性規(guī)劃問題轉(zhuǎn)化為了一個(gè)含有四個(gè)變量的標(biāo)準(zhǔn)形線性規(guī)劃問題，X3，X4為松弛變量。為求解上面的LP問題，我們要考慮滿足約束條件s.t.并使 Z 取得Max的X1，X2，X3，X4的值，由此分析如下-,線性規(guī)劃 Linear Programming（LP）,單純形法 確定初始基可行解： 通過觀察可以發(fā)現(xiàn)，松弛變量X3和X4對(duì)應(yīng)的等式約束條件中的系數(shù)矩陣為單位矩陣可以作為初始可行基矩陣。因此 取 X3，X4為基變量；X1，X2為

5、非基變量。則（1.18）可變?yōu)椋?線性規(guī)劃 Linear Programming（LP）,單純形法 典式 （1.19）或（1.18）稱為關(guān)于基的典式 1、等式約束條件中顯含基可行解 2、目標(biāo)函數(shù)中不含基變量,線性規(guī)劃 Linear Programming（LP）,單純形法 在典式（1.19）中令： X1=X2 =0， 我們得到一個(gè)基本可行解 X1 =（ X1，X2，X3，X4 ）T=（0，0，120，50）T ， 其對(duì)應(yīng)的目標(biāo)函數(shù)值 Z1 = 50X1 + 30X2 = 0,線性規(guī)劃 Linear Programming（LP）,單純形法 最優(yōu)性檢驗(yàn)： 基本可行解 X1 是最優(yōu)解嗎？顯然不是。

6、應(yīng)尋找更好的解。從問題的數(shù)學(xué)角度分析，在典式（1.19）的目標(biāo)函數(shù)中，非基變量X1，X2前的系數(shù)都為正，而此時(shí)的X1，X2均取零值，表明只要增加其值，則目標(biāo)函數(shù)值有增加的可能。因此，將目標(biāo)函數(shù)中系數(shù)為正的某一非基變量與某一基變量地位對(duì)換。,線性規(guī)劃 Linear Programming（LP）,單純形法 換基迭代： 進(jìn)行換基就是要從非基變量中選一個(gè)變量入基，再?gòu)幕兞恐羞x一個(gè)變量出基。并且換基后仍需滿足： 新的解仍是基本可行解； 目標(biāo)函數(shù)值將得到改善。,線性規(guī)劃 Linear Programming（LP）,單純形法 選擇入基變量： 由于在目標(biāo)函數(shù) Z1 =50X1+30X2 中X1，X2的系

7、數(shù)都為正，哪一個(gè)入基都可使目標(biāo)函數(shù)值得到改善。對(duì)于求目標(biāo)函數(shù)極大化的問題，我們希望目標(biāo)值增加得越快越好，因此系數(shù)最大的X1入基。 選擇出基變量： X1入基后，其值從零增加并由于約束條件的原因會(huì)引起其他變量的變化。由典式（1.19）以及變量必須取正值（可行）的條件，我們可以得到下列不等式關(guān)系： X3 = 120 - 4X1- 3X2 0 X4= 50 - 2X1- X2 0,線性規(guī)劃 Linear Programming（LP）,單純形法 因?yàn)榈骕2仍為非基變量（仍會(huì)令其取值為零），則上式可簡(jiǎn)化為： 120 - 4X1 0 ，且 50 - 2X1 0 ， 由此可以看出，雖然我們希望X1入基后

8、取正值，取值越大目標(biāo)值增加越大，但是 X1又得受到以上約束（保證其可行）。 顯然，當(dāng)取 X1 =min（120/4，50/2）=25時(shí)，才能使上述不等式成立，且此時(shí)恰使基變量X4變?yōu)榱?，這正好滿足非基變量必須取值零的條件，所以可令X4 出基，這樣，新的基變量變?yōu)閄3 ，X1 ，而 X2 ，X4 成了非基變量，則,線性規(guī)劃 Linear Programming（LP）,單純形法 約束方程變?yōu)椋?4X1+ X3 =120 - 3X2 2X1 = 50 - X2 - X4 化簡(jiǎn)后得：新的典式方程 X3 = 20 - X2 + 2X4 X1 = 25 -0.5X2 -0.5X4,線性規(guī)劃 Linear

9、 Programming（LP）,單純形法 代入目標(biāo)函數(shù)可得： Z2 =1250+5X2-25X4 令非基變量X2 =X4 = 0，即可得一個(gè)新的基本可行解 X2 =（ 25，0，20，0）T ，其對(duì)應(yīng)的目標(biāo)函數(shù)值Z2 =1250，并完成了第一次迭代。由于目標(biāo)函數(shù) Z2 =1250+5X2-25X4中X2的系數(shù)仍為正，該解X2仍不是最優(yōu)解。重復(fù)上述迭代過程得到：X2入基，X3出基，則新的典式方程變?yōu)椋?X1 = 15 +0.5X3 - 1.5X4 X2 =20 - X3 + 2X4 Z3 =1350 -5X3 - 15X4,線性規(guī)劃 Linear Programming（LP）,單純形法 第三

10、個(gè)基本可行解 X3 =（ 15，20，0，0）T，其對(duì)應(yīng)的目標(biāo)函數(shù)值 Z3 = 1350 。此時(shí)松弛變量 都是非基變量（取值為零），這表明資源已用盡；并且目標(biāo)函數(shù)值 Z3 =1350 -5X3 - 15X4中非基變量X3，X4的系數(shù)全為負(fù)值，說明目標(biāo)函數(shù)已無法進(jìn)一步改善，因此該解已是最優(yōu)解。,線性規(guī)劃 Linear Programming（LP）,單純形法小結(jié)： 單純形法是這樣一種迭代算法如下圖 當(dāng) Zk 中非基變量的系數(shù)的系數(shù)全為負(fù)值時(shí)，這時(shí)的基本可行解 Xk 即是 線性規(guī)劃問題的最優(yōu)解，迭代結(jié)束。,X1,Z1,保持單調(diào)增,保持可行性,保持可行性,保持可行性,保持可行性,保持單調(diào)增,保持單調(diào)

11、增,保持單調(diào)增,X2,X3,.,Xk,Z2,Z3,.,Zk,當(dāng) Zk 中非基變量的系數(shù)的系數(shù)全為負(fù)值時(shí)，這時(shí)的基本可行解 Xk 即是線性規(guī)劃問題的最優(yōu)解，迭代結(jié)束。,線性規(guī)劃 Linear Programming（LP）,單純形表 對(duì)于給定的線性規(guī)劃問題：,max Z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + + a1nxn b1 a21x1 + a22x2 + + a2nxn b2 s.t. am1x1 + am2x2 + + amnxn bm xj 0 （j=1，2 n）,對(duì)此問題添加m個(gè)松弛變量后，可得下面線性規(guī)劃問題并且是典式的形式。,線性規(guī)劃 Li

12、near Programming（LP）,單純形表 線性規(guī)劃的典式,max Z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn + xn+1 = b1 a21x1 + a22x2 + a2nxn + xn+2 = b2 s.t. am1x1 + am2x2 + amnxn + xn+m = bm xj 0 （j=1，2 n，n+1，n+2，n+m）,線性規(guī)劃 Linear Programming（LP）,單純形表： 將上面典式中各變量及系數(shù)填寫在一張表格中就形成下面的單純形表,線性規(guī)劃 Linear Programming（LP）,單純形表： 上面的單

13、純形表還可以表示成矩陣的形式,或,線性規(guī)劃 Linear Programming（LP）,單純形法 由單純形表進(jìn)行迭代步驟： 選擇 Xj 入基：當(dāng) j 行中 j= max i i 0 選擇 Xi 出基：當(dāng) i = min bi/aijaij 0 換基迭代：當(dāng)確定了入基變量 Xj 、出基變量 Xi 后，以 aij 作為主元對(duì)單純形表進(jìn)行取主運(yùn)算， 取主運(yùn)算即采用初等行變換將主元 aij 所在列，除將 aii 變換為1而外，該列中的其余元素都變換為 0。注意這種變換只能采用初等行變換!,線性規(guī)劃 Linear Programming（LP）,單純形法 最優(yōu)解檢驗(yàn)： 當(dāng)?shù)M(jìn)行至某一步時(shí)，j 行中所

14、有檢驗(yàn)數(shù)均小于等于零，則迭代結(jié)束。表中當(dāng)前所指基本可行解即為最優(yōu)解。 當(dāng)?shù)M(jìn)行至某一步時(shí)，j 行中所有檢驗(yàn)數(shù)均小于等于零，且此時(shí)至少有一個(gè)非基變量所對(duì)應(yīng)的檢驗(yàn)數(shù)k 等于零，則原線性規(guī)劃問題有無窮多個(gè)最優(yōu)解。 當(dāng)?shù)M(jìn)行至某一步時(shí)，j 行中至少有一個(gè)檢驗(yàn)數(shù) k 大于零，且該檢驗(yàn)數(shù)對(duì)應(yīng)的列中a1k ，a2k ， amk ，均小于等于零，則原線性規(guī)劃問題最優(yōu)解無界（ max Z +）。,線性規(guī)劃 Linear Programming（LP）,單純形方法的矩陣描述： 設(shè)線性規(guī)劃問題 max Z = CX max Z = CX + 0XS s.t. AX b s.t. AX + I XS = b （I

15、 式） X 0 X ，XS 0 其中 b 0 ，I 是 mm 單位矩陣。 對(duì)上面（I 式）經(jīng)過迭代，并設(shè)最終的最優(yōu)基矩陣為B（不妨設(shè)B 為A 的首m 列，則將（I 式）改寫后有,線性規(guī)劃 Linear Programming（LP）,單純形方法的矩陣描述：,max Z = CBXB + CNXN + 0XS s.t. BXB + NXN + I XS = b XB ，XN，XS 0,max Z = CB B -1+（CN- CB B -1）XN - CB B -1XS s.t. XB + B -1NXN + B -1XS = B -1b XB ，XN，XS 0,B 式中最優(yōu)目標(biāo)函數(shù)值Z*= C

16、B B -1 ， 檢驗(yàn)數(shù) CN - CB B -1 0 ， - CB B -1 0,單純形方法迭代,（I 式）,（B 式）,線性規(guī)劃 Linear Programming（LP）,單純形方法的矩陣描述：,對(duì)應(yīng)I 式的單純形表 I 表,對(duì)應(yīng)B 式的單純形表 B 表,迭代,線性規(guī)劃 Linear Programming（LP）,單純形表計(jì)算步驟舉例 給定線性規(guī)劃問題,max z = 50X1 + 30X2 s.t. 4X1+3X2 120 2X1+ X2 50 X1，X2 0,max z = 50X1 + 30X2 s.t. 4X1+ 3X2 + X3 = 120 2X1+ X2 + X4 = 5

17、0 X1， X2 ，X3 ，X4 0,線性規(guī)劃 Linear Programming（LP）,單純形表計(jì)算步驟舉例,max z = 50X1 + 30X2 s.t. 4X1+ 3X2 + X3 = 120 2X1+ X2 + X4 = 50 X1， X2 ，X3 ，X4 0,2,120/4,50/2,X1,1,1/2,0,1/2,25,0,20,1,- 2,0,5,0,- 25,20/1,252,1,1,X2,15,0,- 1/2,3/2,1,0,- 5,- 15,線性規(guī)劃 Linear Programming（LP）,單純形法的進(jìn)一步討論 人工變量法： 當(dāng)一般線性規(guī)劃問題標(biāo)準(zhǔn)化之后，我們或可

18、得到一個(gè)顯然的基本可行解（如松弛變量作為基變量的一個(gè)初始基本可行解），這樣我們就可以馬上進(jìn)入單純形表的運(yùn)算步驟。然而，并非所有問題標(biāo)準(zhǔn)化之后我們都可得到一個(gè)顯然的初始基本可行解，這時(shí)就需要我們首先確定出一個(gè)基本可行解作為初始基本可行解。通常采用的是人工變量法來確定這樣的初始基本可行解。這種情況下一般有兩種方法： 大M法（罰因子法） 兩階段法,線性規(guī)劃 Linear Programming（LP）,單純形法的進(jìn)一步討論 1、大 M 法（罰因子法）,線性規(guī)劃 Linear Programming（LP）,1、大 M 法,線性規(guī)劃 Linear Programming（LP）,1、大 M 法,線性規(guī)劃 Linear Programming（LP）,1、大 M 法,線性規(guī)劃 Linear Programming（LP）,1、大 M 法,線性規(guī)劃 Linear Programming（LP）,1、大 M 法,線性規(guī)劃 Linear Programming（LP）,采用大 M 法求解線性規(guī)劃問題時(shí)可能出現(xiàn)的幾種情況： 當(dāng)采用單純形法求解 LPM 得到最優(yōu)解時(shí)，基變量不含任何人工變量，則所得到的最優(yōu)解就是原問題的最優(yōu)解； 當(dāng)采用單純形法求解 LPM 得到最優(yōu)解時(shí)，基變量至少含有一個(gè)人工變量且非零，則原問題無可行解； 當(dāng)采用單純形法求解 LPM 得到最優(yōu)解時(shí)，基變量至少含有一個(gè)人