第3章-數(shù)學(xué)規(guī)劃基礎(chǔ)

1、第3章數(shù)學(xué)規(guī)劃根底所謂數(shù)學(xué)規(guī)劃，是指系統(tǒng)在一定約束條件下使某一評(píng)價(jià)目標(biāo)到達(dá)最優(yōu)極值的一種決策方法。數(shù)學(xué)規(guī)劃的關(guān)鍵是從系統(tǒng)思想出發(fā)，在定性分析的根底上建立其數(shù)學(xué)模型。數(shù)學(xué)規(guī)劃模型的一般形式為：系統(tǒng)在滿足條件G"j) b1Dj Xj Dj的情況下，使評(píng)價(jià)目標(biāo)到達(dá)最優(yōu)最大或最小值，即maXmin)Z f (X j) 2其中，式1是系統(tǒng)必須滿足的限制條件的數(shù)學(xué)描述，通常由等式或不等式組成，稱為約 束條件，簡(jiǎn)記為s.t.subject to,意為“受的限制；式2是系統(tǒng)評(píng)價(jià)目標(biāo)的數(shù)學(xué)描述， 稱為目標(biāo)函數(shù)。一、線性規(guī)劃所謂線性規(guī)劃，是指約束條件和目標(biāo)函數(shù)均為線性的數(shù)學(xué)規(guī)劃方法。根據(jù)系統(tǒng)評(píng)價(jià)目標(biāo)是單

2、個(gè)還是多個(gè)，可將線性規(guī)劃分為單目標(biāo)線性規(guī)劃和多目標(biāo)線性規(guī)劃。一單目標(biāo)線性規(guī)劃1. 問題的提出例1生產(chǎn)管理問題某工廠方案期內(nèi)要安排生產(chǎn)i、n兩種產(chǎn)品，生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及 A、B兩種原材料的消耗， 如表所示。該工廠每生產(chǎn)一件產(chǎn)品I可獲利 2元，每生產(chǎn)一件產(chǎn)品n可獲利3元，問如何安排生產(chǎn)方案才能使工廠獲利最多？產(chǎn)品I產(chǎn)品n限制設(shè)備臺(tái)時(shí)/件128臺(tái)時(shí)原材料A kg /件4016kg原材料B kg /件0412kg利潤(rùn)元/件23解 上述所謂的“安排生產(chǎn)方案問題，其實(shí)質(zhì)就是要尋求一個(gè)滿足設(shè)備和原材料資 源約束的可行的生產(chǎn)方案，以確保工廠能獲得最大的利潤(rùn)值。假設(shè)產(chǎn)品I、n的產(chǎn)量分別為X1、X2,那

3、么該工廠的獲利值f = 2 X1 + 3 X2。由于可行的生產(chǎn)方案需要考慮不能超出設(shè)備的有效臺(tái)時(shí)數(shù)限制，即X1+2 X2W 8;同時(shí),還要考慮滿足A、B原材料資源的約束條件，即 4X1W 16, 4X2< 12。因此，工廠的目標(biāo)是在 滿足設(shè)備和原材料資源限制的條件下， 如何確定兩種產(chǎn)品的產(chǎn)量 Xj、X2,使工廠的獲利最大。綜上所述，上述安排生產(chǎn)方案問題的數(shù)學(xué)模型為目標(biāo) max f2x1 3x2滿足約束條件s.t.X12x2 8設(shè)備約束4x116原材料A約束4x212原材料B約束X1 ,x20由此可見，將這類實(shí)際問題轉(zhuǎn)換為數(shù)學(xué)模型的根本步驟可歸納如下：1確定決策變量；2確定所要追求的目標(biāo)目

4、的；3確定約束條件；例2環(huán)保問題靠近某河流有兩個(gè)化工廠，流經(jīng)工廠1的河水流量是5 X 106m3/天，在兩個(gè)工廠之間有一條流量為2X 106m3/天的支流，如下列圖。工廠 1每天排放工業(yè)污水 2 X104m3x 104m3。從工廠1排出的污水流到工廠 2之前，有20%可自然凈化。根據(jù)環(huán)保要求， 河流中工業(yè)污水的含量不應(yīng)超過0.2%。假設(shè)這兩個(gè)工廠都各自處理一局部污水，工廠1處理污水的本錢是1000元/104m3,工廠2處理污水的本錢是 800元/104m3,試問在滿足環(huán)保要 求的條件下，各工廠應(yīng)分別處理多少污水，才能使兩個(gè)工廠處理污水的總費(fèi)用最??？C解假設(shè)工廠1和工廠2每天處理污水量分別為X1

5、104m3、X2104m3,那么兩個(gè)工廠處理污水的總費(fèi)用f = 1000x1 + 800 X2。根據(jù)環(huán)保要求，從工廠1到工廠2之間的河流中污水含量不超過0.2%，那么可得2 X10.2500100x11由于從工廠1排出的污水流到工廠 2之前有20%會(huì)自然凈化，且流經(jīng)工廠 2后河流中污水含量仍要不超過0.2%，故有(1 0.2)(2 X1)(1.4 X2)0.20.8x1X21.6500 200100此外，各工廠每天的污水處理量不應(yīng)超過其污水排放量，那么有X1< 2, X2< 1.4。因此，問題的目標(biāo)是要求兩個(gè)工廠處理污水的總費(fèi)用最小。綜上所述，上述環(huán)保問題的數(shù)學(xué)模型為目標(biāo)min f

6、 1000 x1800x2滿足約束條件s.t.x110.8為 x21.6x12x21.4x1, x202. 數(shù)學(xué)模型的建立應(yīng)用單目標(biāo)線性規(guī)劃來解決實(shí)際的最優(yōu)化問題時(shí)，必須符合以下特征參見P34:(1) 所求問題都有一個(gè)目標(biāo)要求，且相應(yīng)的目標(biāo)函數(shù)可以用最大或最小值的形式來表達(dá)；(2) 要到達(dá)最優(yōu)目標(biāo)，必須有多種方案可供選擇；注意：每一組決策變量X1, X2,Xn的取值就是一個(gè)具體方案。(3) 所尋求的目標(biāo)必然有條件約束；(4) 目標(biāo)函數(shù)和約束條件都是線性方程式，且決策變量具有非負(fù)性。因此，單目標(biāo)線性規(guī)劃問題的數(shù)學(xué)模型可歸納如下：n目標(biāo)函數(shù) max(min) fcjxjj i滿足約束條件s.t.n

7、ajXj( , )bii 1,2, ,mj iXj 0j 1, 2,n其中，aij, bi, cj為常數(shù)。3. 數(shù)學(xué)模型的標(biāo)準(zhǔn)化將單目標(biāo)線性規(guī)劃的數(shù)學(xué)模型規(guī)定為以下標(biāo)準(zhǔn)形式：(1) 目標(biāo)函數(shù)是求最大值當(dāng)目標(biāo)函數(shù)是求最小值時(shí)，即nmin fCjXjj 1由于nmin fmax( f)cjxjj 1令f'=f,可得nmax fmin fcjxjj 1(2) 約束條件均用線性等式方程來表示，且右邊常數(shù)項(xiàng)均為非負(fù)值當(dāng)表達(dá)式中含“w時(shí)，可在約束條件左邊加上一個(gè)非負(fù)的變量一一松弛變量，使原 來的“w變?yōu)椤?；當(dāng)表達(dá)式中含時(shí)，可在約束條件左邊減去一個(gè)非負(fù)的變量一 剩余變量，使原來的變?yōu)椤?=。另外，

8、在標(biāo)準(zhǔn)型中要求約束條件右邊的常數(shù)項(xiàng)bi > 0,假設(shè)存在bi<0的情形，那么可在方程式兩邊各乘以 1,使所有bi > 0得到滿足。(3) 所有變量要求非負(fù)當(dāng)Xi w 0時(shí)，那么可令Xi' = Xi且Xi'?0；當(dāng)Xi為無約束的自由變量時(shí)，那么可令 Xi' Xi" = Xi 且 xi'、xi" > 0。綜上所述，可得 單目標(biāo)線性規(guī)劃模型的標(biāo)準(zhǔn)形式：目標(biāo)函數(shù) max fc jx jj1滿足約束條件 s.t.naij Xj bij1i 1, 2,mXj 0j 1, 2,n例 3 將例 1 生產(chǎn)管理問題的數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式。

9、 max f 2x1 3x2x1 2x2 84x1 16s.t. 14x2 12x1 ，x2 0解 例1的目標(biāo)函數(shù)是求最大值，各不等式均為“W形式的不等式，故需要在各不等式的左邊加上非負(fù)的松弛變量 X3, X4, X5,使不等式化為等式。由于所加變量X3, X4, X5表示未被利用的資源，那么也就沒有被轉(zhuǎn)化為價(jià)值，所以在目標(biāo)函數(shù)中X3, X4, X5的系數(shù)應(yīng)為零。因此，其標(biāo)準(zhǔn)形式為maX f 2X13X2 0X30X40X5X12X2 X384X1X416s.t.4X2X5 12X1，X2，X3，X4，X50例 4思考題 將例 2環(huán)保問題的數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式。例5將以下數(shù)學(xué)模型化為標(biāo)準(zhǔn)型。m

10、in fX1X24X33X24X39X1X26s.t.5X22X316X10，X20，x3為自由變量解令 Xi = xi'且 xi'?0X3 = X3'X3"且 X3'、X3" > 0將第一個(gè)約束條件兩端乘以1 并參加松弛變量X4,第二個(gè)約束條件減去剩余變量X5,第三個(gè)約束條件加上松弛變量X6，同時(shí)將目標(biāo)函數(shù)變?yōu)榍笞畲笾?，整理可得maX fmin fX1 X24X34X33X24X34X3X49X1 X2X56s.t.5X22X32X3X6 16X1 ，X2，X3，X3，X4，X5，X604. 圖解法對(duì)于一般單目標(biāo)線性規(guī)劃問題滿足 式的

11、點(diǎn)稱為該問題的解；而同時(shí)又滿足(3)式的點(diǎn)那么稱為 可行解。所有可行解組成的集合稱為可行域或可行解集?？尚杏蛏蠞M足(1) 式的點(diǎn)稱為最優(yōu)解，最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)nmax(min) fcjxjj 1(1)naijxj(,)bis.t.j 1i 1,2,m(2)xj 0j 1,2,n(3)值稱為最優(yōu)值。當(dāng)單目標(biāo)線性規(guī)劃問題中只有兩個(gè)決策變量.即二維線性規(guī)劃.時(shí)，可糾囲圖解法來求 解，以便直觀地理解該問題解的幾何意義。例6用圖解法求例1生產(chǎn)管理問題的解。max f 2x1 3x2X12x284x116s.t.4X212X1 ,X20解 1由約束條件畫出可行域因?yàn)閤1, X2 > 0,可行域在第

12、一象限。 第一個(gè)約束條件 Xl+2X2< 8表示以直線Xl+2X2= 8為 邊界的右下方平面；第二個(gè)約束條件4冷 16表示以X1= 4為邊界的左半平面；第三個(gè)約束條件4X2W 12表示以X2= 3為邊界的下半平面，因此， OABCD所圍成的凸多邊形即為可行f/打2考慮目標(biāo)函數(shù)的等值線和梯度方向?qū)δ繕?biāo)函數(shù)f= 2x1 +3x2,令c為參數(shù)，那么2xi +3x2 = c表示目標(biāo)函數(shù)的取值為 c的一簇平 行線，如圖中的虛線所示，且位于同一直線上的點(diǎn)具有相同的目標(biāo)函數(shù)值，故稱其為“等值線。當(dāng)c值由小變大時(shí)，直線 2xi +3x2 = c沿著其梯度方向，向右上方平行移動(dòng)。3求問題的最優(yōu)解當(dāng)目標(biāo)函數(shù)

13、沿其梯度方向平移至B點(diǎn)時(shí)，切點(diǎn)B即為最優(yōu)解。那么求出 B點(diǎn)的坐標(biāo)4為 16Xf 2x28得最優(yōu)解 xi = 4，X2 = 2 ；相應(yīng)的最優(yōu)值 fmax = 2xi +3x2 = 8+6 =14。討論：。假設(shè)例1是求最小值，那么在 0點(diǎn)處到達(dá)最優(yōu)解 xi*= X2*= 0，且相應(yīng)的最優(yōu)值 fmin = 0 ； 假設(shè)例1中的目標(biāo)函數(shù)變?yōu)?f = 2xi +4x2，那么等值線2xi +4x2 = c與約束條件xi+2x2W 8的邊界線相平行。當(dāng) c值由小變大并與線段 CB重合時(shí)，目標(biāo)函數(shù)值到達(dá)最大，那么表示線段CB上的任意一點(diǎn)都是最優(yōu)解，即該問題有無窮多個(gè)最優(yōu)解； 假設(shè)在例1的數(shù)學(xué)模型中再加一個(gè)約束

14、條件2X1+X2 > 4,那么可行域是空集，此時(shí)無可行解，當(dāng)然也就無最優(yōu)解。通過上述的圖解法可見，單目標(biāo)線性規(guī)劃問題中，所有可行解構(gòu)成的可行域一般是凸多邊形或是無界的，其最優(yōu)解具有以下重要特點(diǎn)：假設(shè)問題存在最優(yōu)解，那么一定在可行域的某個(gè)頂點(diǎn)上得到； 假設(shè)兩個(gè)頂點(diǎn)上同時(shí)得到最優(yōu)解，那么這兩個(gè)頂點(diǎn)連線上的任何一點(diǎn)都是最優(yōu)解； 假設(shè)可行解無界，那么可能發(fā)生無最優(yōu)解的情況； 假設(shè)無可行域，那么問題既無可行解也無最優(yōu)解。5. 單純形法單純形法是由美國數(shù)學(xué)家 G B. Dantzing于1947年首先提出的。它是借助于電腦，用于 求解多變量.多維.線性規(guī)劃的有效方法。(1)根本概念及其相關(guān)定理對(duì)于線

15、性規(guī)劃問題的標(biāo)準(zhǔn)型nmax f Cj Xjj inaijXj bii 1,2, , ms.t.j iXj 0j 1, 2,n用矩陣形式表示，那么可以寫成max f CXAX bs.t.X 0式中cC1C2CnTXX1X2Xna11a12a1 nAa21a22a2nam1am2amnbthb2bm其中，C是由價(jià)值系數(shù)Cj構(gòu)成的價(jià)值向量，X是由決策變量xj構(gòu)成的決策向量，A是由技術(shù) 系數(shù) 如構(gòu)成的mx n階約束系數(shù)矩陣，b是由資源系數(shù)bi構(gòu)成的資源向量。假設(shè)矩陣A的秩為m，B是A陣中mx m階非奇異矩陣| B |工0，那么稱B是線性規(guī)劃問題的一個(gè)基。也就是說，矩陣B是由m個(gè)線性獨(dú)立的列向量Pj組成

16、，即a11a12a1ma21a22a2mBR P2Pmam1am2amm那么稱Pjj = 1,2,，m為基向量，與基向量Pj相對(duì)應(yīng)的非零變量 xjj = 1,2,，m為基根底變量；其余的零變量 xjj = m+1, m+2,n為非基根底變量與基B對(duì)應(yīng)的線性規(guī)劃問題的解x-ix2XiX2xmxm 1Xm0TXnT0那么稱為線性規(guī)劃問題的 基解。由于滿足非負(fù)約束條件 X>0的解為線性規(guī)劃問題的可行解,那么滿足非負(fù)條件的基解就稱為基可行解，而對(duì)應(yīng)于基可行解的基就稱為可行基。定理1：線性規(guī)劃的可行解 X = Xi x2XnT為基可行解的充要條件是 X的正分量所 對(duì)應(yīng)的系數(shù)列向量是線性獨(dú)立的。因此

17、，為了簡(jiǎn)單起見，通常在單純形法中要求根底變量對(duì)應(yīng)的矩陣為單位矩陣假設(shè)在線性規(guī)劃問題的標(biāo)準(zhǔn)型中，與基 B對(duì)應(yīng)的基變量Xb = X1X2XmT，非基變量 Xn = Xm+1 Xm+2 XnT，且相應(yīng)的矩陣C = C B Cn，其中Cb = C1C2Cm, Cn = Cm+1Cm+2Cn，那么可以證明以下判別線性規(guī)劃問題最優(yōu)解的依據(jù)參見P40。定理2最優(yōu)解判別定理：在標(biāo)準(zhǔn)形式的線性規(guī)劃問題中，對(duì)于基 B,假設(shè)B 1b> 0, 且C CbB 1A W 0即檢驗(yàn)系數(shù)矩陣c = C CbB 1A那么對(duì)應(yīng)于基B的基解就是最優(yōu)解， 基B 就是最優(yōu)基。尤其是，當(dāng)最優(yōu)解判別定理中基矩陣B = Imx m階單

18、位陣時(shí)，那么對(duì)應(yīng)的基可行解為Xb = b且Xn = 0，其最優(yōu)解的判別式變?yōu)镃 CbAW 0。不失一般性，設(shè) Xb = X1 X2XmT , Cb = C1 C2Cm，系數(shù)矩陣A為100a1, m 1a1n01a2, m 2a2nA0001am, m 1amn對(duì)于基變量Xj j = 1,2,m來說，其檢驗(yàn)系數(shù)b j為零；對(duì)于非基變量 Xj j = m+1, , nm來說，其檢驗(yàn)系數(shù)j CjCiaj j = m+1,n當(dāng)w 0時(shí)，那么目前的根本可行解i1為最優(yōu)解。否那么，假設(shè)存在某個(gè)檢驗(yàn)系數(shù)bj >0,那么目前的根本可行解不是最優(yōu)解。特別要指出的是，假設(shè)存在某個(gè)b m+k = 0 ,而其它

19、任何b j<0j = m+1,n且j工m+k, 那么線性規(guī)劃問題有無窮多個(gè)最優(yōu)解； 假設(shè)存在某個(gè)b m+k >0，且A的列向量Pm+k中的所有元 素均不大于 0,那么線性規(guī)劃問題無最優(yōu)解。2根本思路單純形法的基本思路是 ：根據(jù)線性規(guī)劃問題的標(biāo)準(zhǔn)型,從可行域中的一個(gè)頂點(diǎn)基可 行解開始,轉(zhuǎn)換到另一個(gè)頂點(diǎn)基可行解 ,并且使目標(biāo)函數(shù)的值逐步增大。當(dāng)目標(biāo)函數(shù) 到達(dá)最大值時(shí),就得到了問題的最優(yōu)解。以例 1 的生產(chǎn)管理問題為例,說明單純形法逐步迭代尋優(yōu)的原理和思路。該問題的數(shù)學(xué)標(biāo)準(zhǔn)型為maX f2X13X20X30X40X5X12X2X384X1X416s.t.4X2X512X1 ,X2,X3,

20、X4,X501第一輪：約束方程系數(shù)矩陣12100A40010P1 P2P3P4P504001顯然100P30P41P50001是線性獨(dú)立的,這些列向量構(gòu)成一個(gè)初始可行基 B100 B P3 P4 P50 1 0001X1和X2為非基變量。對(duì)應(yīng)于初始可行基 B , X3、X4和X5為初始基變量,由方程組 1 可得x3 8 x1 2x2 x4 16 4x1 x5 12 4x22令非基變量 x1、x2 為零，得到初始的基可行解為X (0) x1 x2 x3 x4 x5 T 0 0 8 16 12 T將方程組 2代入目標(biāo)函數(shù)，得f 2x1 3x23 將初始的根本可行解代入式 3，得 f (0) =0。

21、這個(gè)根本可行解表示：工廠沒有安排生產(chǎn)產(chǎn)品i、n；設(shè)備的有效臺(tái)時(shí)和原材料a、B沒有被利用，所以工廠的利潤(rùn)指標(biāo) f (0) =0。從式3目標(biāo)函數(shù)可以看到，Xi、X2即沒有安排生產(chǎn)的產(chǎn)品i,n的系數(shù)都是正 數(shù)，顯然將非基變量換成基變量，目標(biāo)函數(shù)的值就可能增大。 從經(jīng)濟(jì)意義上講，安排生產(chǎn)產(chǎn) 品I或n就可以使工廠的利潤(rùn)指標(biāo)增加，所以只要式3目標(biāo)函數(shù)中還存在有正系數(shù)的非基變量，那么目標(biāo)函數(shù)值利潤(rùn)還有增加的可能，就需要將非基變量與基變量進(jìn)行對(duì)換。一般選擇正系數(shù)最大的那個(gè)非基變量X2為換入變量即引入變量，將它換入到基變量中去，同時(shí)還要確定基變量中有一個(gè)要換出來成為非基變量。 可按以下方法來確定 換出變量即退

22、出變量?，F(xiàn)在分析方程組2，當(dāng)將X2定為換入變量后，必須要從X3、X4和X5中換出一個(gè)，并要保證其余的都是非負(fù)，即X3, X4, X5> 0。當(dāng) X1=0 時(shí)，由方程組 2可得X3 8 2X20X4 16 0X5 12 4X2 0 4 從方程組 4可見，只有選擇 X2 = min8/2 ， - ， 12/4=3 時(shí)，才能使式 4成立。當(dāng) X2=3 時(shí)，X5=0，這就決定了 X5為換出變量，用X2去替換X5。以上數(shù)學(xué)描述說明：每生產(chǎn)一件產(chǎn)品n,需要用掉設(shè)備臺(tái)時(shí)及原材料為2, 0, 4。這些資源能力中的薄弱環(huán)節(jié)就確定了產(chǎn)品n的產(chǎn)量，也就是由原料B的生產(chǎn)能力，確定了產(chǎn)品n的產(chǎn)量 X2=12/4=

23、3件。第二輪：X2與X5互換，即X2為基變量，X5為非基變量。那么互換后，X3、X4和X2為基變量，X1和X5為非基變量。為了求得新的基可行解，并將目標(biāo)函數(shù)f用非基變量XI、X5表示，以判別所求的基可行解是否為最優(yōu)解，那么需要用高斯消元法，將方程組2中第一個(gè)方程的X2消去，將第三個(gè)方程的X2移至左邊，并將系數(shù)化為1,于是有X3X416X21X1X524x11X545令非基變量XI、X5為零，得基可行解為XiX2X3X4TX50 3 2 16 0T將方程組5代入目標(biāo)函數(shù)中，得2X1 3x514 59。6 將X1=0，X5=0代入方程組6，可得目前基可行解的目標(biāo)值為由式6可知，非基變量 X1的系數(shù)

24、大于0，那么目前的基可行解不是最優(yōu)解， X1應(yīng)為換 入變量。在方程組5中，用各方程負(fù)的 Xi的系數(shù)如果xi在方程的左邊，那么用正的 xi 系數(shù)去除對(duì)應(yīng)的常數(shù)項(xiàng)，選最小者，即X1 = min 2/1，16/4，=2于是，方程組5中的第一個(gè)方程對(duì)應(yīng)的原基變量X3為換出變量。第三輪：X1與X3互換，那么互換后，X1、X4和X2為基變量，X3和X5為非基變量。將方程組5進(jìn) 行初等變換，使得由基變量X1、X4和X2所構(gòu)成的基為單位矩陣，即X12X32X5X484X32x5X231 X547令非基變量X3、X5為零，得基可行解X(2)x1X2X3X4TX52 3 0 8 0T將方程組7代入目標(biāo)函數(shù)中,13

25、2X31J5X5的系數(shù)大于0，那么目前的基可行解不是最優(yōu)解，X5為換入8 由式8可知，非基變量變量，因?yàn)?min ，8/2，3/(1/4)=4，故取&為換出變量。 第四輪：X5與X4互換，那么互換后，X1、X5和X2為基變量，X3和X4為非基變量。用高斯消元法對(duì) 方程組7進(jìn)行初等變換，使得每個(gè)約束方程中只含有一個(gè)基變量且基變量的系數(shù)為1，即XiX54x222x312X418X49令非基變量X3、X4為零，得基可行解為T 為 X2 X3 X4 X5將方程組9代入目標(biāo)函數(shù)中，得18X410由式10可見，X3與X4的系數(shù)均為負(fù)數(shù)，說明假設(shè)想使用剩余的設(shè)備臺(tái)時(shí)和原材料A，就必須支付附加費(fèi)用。所

26、以當(dāng)X3 = X4 =0時(shí)，即不再利用這些設(shè)備能力和原材料時(shí)，目標(biāo)函數(shù)到達(dá)最大fmax=14，于是基可行解X(3)TX1X2X3X4X5為最優(yōu)解。3單純形表max f對(duì)于標(biāo)準(zhǔn)化的線性規(guī)劃模型CnXnX1a1, m 1Xm 1X2a2, m 1Xm 1S.t.Xmam, m 1 Xm 1X1, X2 , Xn0a1 n Xnb1a2nXnb2ammXnbm式中，X1, X2,，Xm為基變量，且對(duì)應(yīng)的基為 B = Imx m階單位陣。所設(shè)計(jì)的初始單 純形表如表1所示。表1初始單純形表CC1CmCm+1Cn9 iCbXbbX1XmXm+1XnC1X1b110a1, m+1a1ne 1C2X2b200

27、a2, m+1a2n9 2CmXmbm01am, m+1amne mmGbi 100mCm 1Ciai, m 1i 1mCnCi ai ni 1(T j表中，Xb列中填入基變量，這里是 X1, X2,，Xm；Cb列中填入基變量的價(jià)值系數(shù)，這里是C1, C2,，Cm,它們隨基變量改變而改變,并與基變量相對(duì)應(yīng)；b列中填入約束方程組右端的常數(shù)；X行填入決策變量名；在X行上面的C行，相應(yīng)填入各決策變量的價(jià)值系數(shù)；最后一行是檢驗(yàn)數(shù)行，對(duì)應(yīng)各非基變量Xj的檢驗(yàn)數(shù)是mj CjCiaij (j m 1,n)i 1e i列的數(shù)字是在確定換入變量后，按e規(guī)那么計(jì)算后填入表中的。單純形表要求初始可行基 B=I，這時(shí)

28、可以從表上直接得到基可行解，即XiX2XmXm 1TXnbib2bm 0m且該基可行解的目標(biāo)值為cb。i 1單純形法就是以上述形式的初始單純形表為起點(diǎn)進(jìn)行迭代，每迭代一次后，得到使新 的基B'=I的另一個(gè)單純形表；從表上得到新的基可行解和目標(biāo)值，并進(jìn)行最優(yōu)判別，直到 找到最優(yōu)解為止。(4) 單純形法小結(jié)下面將單純形法的計(jì)算步驟歸納如下：第一步，建立線性規(guī)劃的數(shù)學(xué)模型，并使其標(biāo)準(zhǔn)化。標(biāo)準(zhǔn)化的要求為： 。目標(biāo)函數(shù)化成求最大值問題；囤 約束條件均表達(dá)為等式關(guān)系必要時(shí)引入松弛變量和剩余變量；模型存在一個(gè)初始可行基一一單位矩陣必要時(shí)引入人工變量。第二步，建立初始單純形表，如表1所示。第三步，檢驗(yàn)

29、各非基變量Xj的檢驗(yàn)數(shù)mj CjCi ai ji 1假設(shè)所有b jW 0j = m+1，n，那么已得到最優(yōu)解，可停止計(jì)算，否那么轉(zhuǎn)入下一步。第四步，在b j >0, j = m+1，n中，假設(shè)有某個(gè)b k >0對(duì)應(yīng)的Xk的系數(shù)列向量Pk W 0, 那么此問題無最優(yōu)解，停止計(jì)算，否那么轉(zhuǎn)入下一步。第五步，根據(jù)max b j >0= b k，在單純形表中b k所在的列為主元列即關(guān)鍵列，主元列 所對(duì)應(yīng)的變量Xk為換入變量入基變量。再根據(jù)e規(guī)那么計(jì)算，有e i = bi /aikaik >0, i =1 , 2,，m，e l = min( e i) = bi /aik,確定e

30、i所在的行為 主元行即關(guān)鍵行，主元行在單純 形表中所對(duì)應(yīng)的基變量 Xi為換出變量出基變量。主元行與主元列相交的元素 aik為主元素即關(guān)鍵元素，用方括號(hào)標(biāo)明，轉(zhuǎn)入下一步。aik第六步，以aik為主元素，用高斯消元法進(jìn)行約束方程組的初等變換，將主元列中主元素P kalk a2kalkTa mk將Xb列中的XI轉(zhuǎn)換為Xk, Cb列中的ci換成ck，得到新的單純形表。重復(fù)第三步 第六步, 直到算法終止。例6用單純形法計(jì)算例1生產(chǎn)管理問題的最優(yōu)解。解 第一步，將模型標(biāo)準(zhǔn)化后，即為max f 2x13x2OX30x40X5X12X2X384x1X416s.t.4X2X512X1 ,X2,X3, X4,X5

31、0模型中已存在一個(gè)初始可行基，對(duì)應(yīng)的基變量為X3、X4和X5,那么令非基變量X1、X2為零，可得初始基可行解為X(0)X1X2X3X4TX500 816 12T且相應(yīng)的目標(biāo)函數(shù)值 f°=0。第二步，將有關(guān)內(nèi)容填入表中，得到如表2所示的初始單純形表。表2初始單純形表230009 iCbXbbX1X2X3X4X50X381210040X41640010一0X512040013b j23000第三步，計(jì)算各非基變量的檢驗(yàn)數(shù)，bi =2，2 =3，故存在b j >0,目前的解不是最優(yōu)解，轉(zhuǎn)入下一步。第四步，Pi, P2均有正分量存在，轉(zhuǎn)入下一步。第五步，經(jīng)比擬 max b j >

32、0= b 2,確定X2為換入變量，X2所在列為主元列；計(jì)算 9 i =8/2=4 , 9 3=12/4=3，取最小值者為9 3,于是9 3所在的行為主元行，主元行所對(duì)應(yīng)的基變 量X5為換出變量，主元行與主元列相交的元素4為主元素。第六步，以4為主元素，用高斯消元法進(jìn)行初等行變換，使對(duì)應(yīng)主元列的列向量P2變換為0 0 1T，在Xb列中將X5替換為X2，于是得到表3。表3 X5替換為X2后的單純形表Ci230009 iCbXbbX1X2X3X4X50X3210101/220X4164001043X2301001/4一20003/4這樣，得到新的根本可行解TXiX2X3X4X50 3 2 16且相應(yīng)

33、的目標(biāo)函數(shù)值 f (1) =9。第七步，重復(fù)第三步第六步的計(jì)算步驟，由于表 3中檢驗(yàn)數(shù)b 1 =2>0，那么目前的解不 是最優(yōu)解。同理可以確定 X1為換入變量，X3為換出變量，于是得到表4。X(2)TX1 X2X3X4X5表4 X3替換為X1后的單純形表Cj23000e iCbXbbX1X2X3X4X52X1210101/2一0X480041243X2301001/412b j00-201/4那么其新的根本可行解且相應(yīng)的目標(biāo)函數(shù)值f=13。第八步，再次重復(fù)第三步第六步的計(jì)算步驟，由于表4中檢驗(yàn)數(shù)b 5 =1/4>0 ,那么目前的 解還不是最優(yōu)解。同理可以確定X5為換入變量，X4為換

34、出變量，于是得到表5。表5 X4替換為X5后的單純形表最優(yōu)單純形表Cj23000e iCbXbbX1X2X3X4X52X141001/40一0X540021/21一3X22011/21/80一b j003/21/80第九步，表5最后一行的所有檢驗(yàn)數(shù)b j都已為負(fù)或零，這表示目標(biāo)函數(shù)值已不可能再增大，于是得到最優(yōu)解X X(3)x1x2x3X4x4 2 0 0 4且相應(yīng)的最優(yōu)值即工廠的最大獲利f*= f=14。6.對(duì)偶問題在線性規(guī)劃問題中，任何一個(gè)求最大值的規(guī)劃問題必有一個(gè)求最小值的規(guī)劃問題與之 相對(duì)應(yīng)，二者含有相同的數(shù)據(jù)，且它們的解也有密切聯(lián)系，反之亦然。假設(shè)兩個(gè)問題中，其 中一個(gè)稱為原問題，那

35、么另一個(gè)就稱為對(duì)偶問題。(1) 對(duì)偶問題的關(guān)系以下兩個(gè)線性規(guī)劃問題i、n是互為對(duì)偶的，其中max f 2x1 5x2 7x3問題1：2x1 3x2 3x312s.t. x1 2x2 x313X1,X2,X3min f 12y1 13y22y1 y2 2問題n：3y1 2y2 5 s.t.3y1 y2 7y1,y2 0不難發(fā)現(xiàn)， 互為對(duì)偶的兩個(gè)問題之間具有以下關(guān)系 ：。一個(gè)問題目標(biāo)函數(shù)的系數(shù)是另一個(gè)問題約束條件右端的常數(shù)；囤一個(gè)問題第i個(gè)約束條件的各系數(shù)是另一個(gè)問題第i個(gè)變量的約束條件系數(shù)；一個(gè)問題是求目標(biāo)函數(shù)的最大值，其約束條件均為“w形式，而另一個(gè)問題那么是求目標(biāo)函數(shù)的最小值，其約束條件均為

36、形式；® 兩個(gè)問題的變量均是非負(fù)的。2對(duì)偶問題的轉(zhuǎn)化一個(gè)線性規(guī)劃問題，在實(shí)際應(yīng)用中通?？梢愿鶕?jù)具體情況將原問題轉(zhuǎn)化為對(duì)偶問題，其具體方法如下 ：如果目標(biāo)函數(shù)是求最大值，首先應(yīng)將約束條件全部轉(zhuǎn)化為“w形式，即。原約束條件為形式時(shí)，那么可在該不等式兩邊同乘以1，使其變?yōu)椤皐形式； 原約束條件為等式時(shí)，那么可將該式再將形式轉(zhuǎn)化為“w形式；原問題中有自由變量時(shí)，那么可用兩個(gè)非負(fù)變量相減來代替， 如Xi為自由變量，令Xi = Xi' Xi"且 Xi'、Xi"> 0。然后，再根據(jù)對(duì)偶問題的關(guān)系進(jìn)行轉(zhuǎn)化。同理，如果目標(biāo)函數(shù)是求最小值，那么應(yīng)先將約束條件全部

37、轉(zhuǎn)化為形式，然后再 轉(zhuǎn)化為相應(yīng)的對(duì)偶問題。例 7 試寫出以下線性規(guī)劃問題的對(duì)偶問題min f 5X1 8X2 20X3X1 6X2 12X3 1X1 7X2 9X3 2s.t.X1 3X2 9X333X1 5X2 9X3 4X!為自由變量，x2 , x30解 令X1 = X1' X1"且X1'、X1" > 0,并將第四個(gè)約束條件轉(zhuǎn)化為兩個(gè)不等式，那么原問題可改寫為min f 5x1 5x1 8x2 20x3x1 x1 6x2 12x3 1x1 x1 7x2 9x3 2s.t.x1x13x29x333x13x15x29x343x13x15x29x34x1

38、,x1, x2, x303x13x15x2 9x3由原問題與對(duì)偶問題的關(guān)系可得，相應(yīng)的對(duì)偶問題為max f y1 2y2 3y3 4y4 4y5y1 y2 y3 3y4 3y5 5y1 y2 y3 3y4 3y55s.t. 6y1 7y2 3y3 5y4 5y5 812y1 9y2 9y3 9y4 9y5 20y1，y2，y3， y4，y5 03) 對(duì)偶問題最優(yōu)解的關(guān)系 互為對(duì)偶的兩個(gè)問題最優(yōu)解之間的關(guān)系為 ：3求最小問題的任意可行解對(duì)應(yīng)的目標(biāo)函數(shù)值都不小于求最大問題的最優(yōu)目標(biāo)函數(shù)值，而 求最大問題的任意可行解的目標(biāo)函數(shù)值都不大于求最小問題的最優(yōu)目標(biāo)函數(shù)值；32 如果一個(gè)線性規(guī)劃問題有最優(yōu)解，

39、那么其對(duì)偶問題也一定有最優(yōu)解，且兩個(gè)問題的最優(yōu)目 標(biāo)函數(shù)值相等； 最大值問題的原變量 Xj的值等于最小值對(duì)偶問題的第 j個(gè)剩余變量的檢驗(yàn)數(shù)。 二多目標(biāo)線性規(guī)劃這種通常，在實(shí)際情況下，希望得到的某個(gè)行動(dòng)方案并不像前面介紹的單目標(biāo)規(guī)劃那樣， 只是使一個(gè)目標(biāo)函數(shù)到達(dá)最優(yōu)值， 而是希望該方案盡可能同時(shí)接近幾個(gè)預(yù)定的目標(biāo)值， 數(shù)學(xué)方法就稱為 多目標(biāo)規(guī)劃法 ，簡(jiǎn)稱 目標(biāo)規(guī)劃 。目標(biāo)規(guī)劃是由 Charnes 和 Cooper 于 1961 年 首次提出的。這里，著重介紹線性目標(biāo)規(guī)劃的有關(guān)問題。1. 問題的提出 在實(shí)際問題中，常需要研究在某些限制條件下，同時(shí)考慮多個(gè)目標(biāo)的最優(yōu)化問題。例如，人們?cè)谫徶靡患路r(shí)

40、，往往需要考慮質(zhì)量、顏色、式樣、大小、價(jià)格這五個(gè)目標(biāo)；又 如在選擇一個(gè)新廠址時(shí)， 除了要考慮運(yùn)費(fèi)、造價(jià)、 燃料供應(yīng)費(fèi)等經(jīng)濟(jì)指標(biāo)以外，還要考慮對(duì) 環(huán)境影響等社會(huì)因素； 再如在設(shè)計(jì)貨船時(shí)， 通常要考慮選取使船舶的試航速率最大， 年貨運(yùn) 量最多和運(yùn)輸本錢最低等多個(gè)目標(biāo)都盡可能好的方案。例8投資決策問題 某投資開發(fā)公司擁有總資金 A萬元，今有n 5?2個(gè)投資項(xiàng) 目可供選擇。設(shè)投資第i i = 1,2,n個(gè)工程需用資金 a萬元，預(yù)計(jì)可獲利 bi萬元，試 問應(yīng)如何決策投資方案？解 一個(gè)好的投資方案應(yīng)該是投資少，收益大的方案。設(shè)投資決策變量xi1,決定投資第i個(gè)工程0,決定不投資第i個(gè)工程(i 1,2, ,

41、n)由題意可知，投資第i i = 1,2,n個(gè)工程需用資金aixi萬元，那么為了使總投資金額 盡可能地少，即有nmin f1ai xii1同時(shí)，投資第ii = 1,2,n個(gè)工程預(yù)計(jì)可獲利 biXi萬元，那么為了使獲得的收益最大，又 應(yīng)要求nmax f 2bi xii1此外，由于該公司的總資金為 A 萬元，故有限制條件nai xiAi1而投資決策變量 xi 只能取 1 或 0，即滿足xi(1 xi) 0，i 1, 2, ,n綜上所述，所考慮的投資決策問題可歸納為以下具有兩個(gè)目標(biāo)的最優(yōu)化問題： nnmin f1aixi， max f2bixii1i1nai xi As.t. i 1 i ixi (

42、1 xi ) 0， i 1, 2, ,n2. 數(shù)學(xué)模型的建立建立目標(biāo)規(guī)劃模型的基本思路是 ：(1) 確定決策定量 為，選擇約束條件和各個(gè)目標(biāo)函數(shù)，構(gòu)造出多目標(biāo)的線性規(guī)劃；(2) 根據(jù)決策者的意圖， 對(duì)各個(gè)目標(biāo)函數(shù)確定相應(yīng)的目標(biāo)值， 并在這些目標(biāo)函數(shù)方程中加 入偏離系數(shù)di、di + ,組成一組新的約束條件；(3) 用這些偏離系數(shù)產(chǎn)生目標(biāo)規(guī)劃的目標(biāo)函數(shù)F,再根據(jù)各目標(biāo)的輕重緩急賦予不同優(yōu)先 級(jí)別的權(quán)因子3 i，使目標(biāo)規(guī)劃的目標(biāo)函數(shù)到達(dá)最小。目標(biāo)規(guī)劃數(shù)學(xué)模型的一般形式為 ： mmin F i (di di )i1naij xj didibij1s.t.di ? di0xj 0 bi，di ，di0

43、式中，3 i為決策者根據(jù)具體情況選定的各目標(biāo)優(yōu)先級(jí)的權(quán)因子；di、di+分別表示未到達(dá)目標(biāo)或超過目標(biāo)的偏離系數(shù)，且對(duì)于任何目標(biāo)都只能取二者 之一，故有 di ?di+=0 條件成立。示，試求獲利最大的生產(chǎn)方案。數(shù)據(jù)甲乙擁有量原材料kg/件2111 kg設(shè)備臺(tái)時(shí)/件1210臺(tái)時(shí)利潤(rùn)f元/件810解 這是個(gè)單目標(biāo)線性規(guī)劃問題，設(shè)甲、乙產(chǎn)品的產(chǎn)量分別為Xi、X2,那么其數(shù)學(xué)模型為max f 8x110x22x1 x211s.t.x1 2x2x1, x2010用單純形法求得最優(yōu)決策方案為：X1 =4， X2 = 3， f = 62元。但實(shí)際上工廠在作決策時(shí)，還要考慮市場(chǎng)等一系列其它條件，譬如 。嚴(yán)格限

44、制原材料供應(yīng)； 產(chǎn)品乙的產(chǎn)量不低于產(chǎn)品甲的產(chǎn)量； 充分利用設(shè)備的有效臺(tái)時(shí)，但不希望加班；利潤(rùn)額不小于56元。同時(shí)希望將O2作為第一優(yōu)先目標(biāo)，將O 3作為第二優(yōu)先目標(biāo)，將O 4作為第三優(yōu)先目標(biāo)。先對(duì)條件O ,可引入偏離系數(shù)變量 d1+、d1 ,建立目標(biāo)約束X2 X1 d1+d1 =0,并使3 1d1 tmin ;再對(duì)條件O3，可引入偏離系數(shù)變量d2+、d2，建立目標(biāo)約束 X1+2X2 d2+d2 =10,并使3 2d2+d2 t min ;最后對(duì)條件O 4，可引入偏離系數(shù)變量d3+、d3，建立目標(biāo)約束8x1+10x2 d3+d3 =56，并使3 3d3 t min。因此，建立相應(yīng)的目標(biāo)規(guī)劃數(shù)學(xué)模

45、型為X1,X2,di ,di其中，權(quán)因子 1(i 1,2,3)minF1d1 2 (d2 d2 )2x1x211X2X1d1d10s.t.X12x2 d2 d2108x110x2 d3 d3563d3由此可見，在建立目標(biāo)規(guī)劃數(shù)學(xué)模型時(shí)，需要確定目標(biāo)值、優(yōu)先次序以及相應(yīng)的權(quán)系 數(shù)等，它們都具有一定的主觀性和模糊性，可以通過組織專家進(jìn)行評(píng)估給以量化。3. 圖解法例10用圖解法求解例9的生產(chǎn)管理問題。解1在平面直角坐標(biāo)系中，做出約束條件所確定的區(qū)域，如下列圖O先畫出絕對(duì)約束條件 1畫法同線性規(guī)劃圖解法，即三角形區(qū)域 OAB ;O再畫出目標(biāo)約束條件 24。先令di =di+ =0 ,做出相應(yīng)直線；然后

46、在直線旁標(biāo)上di、di+，說明目標(biāo)約束可沿著 di、di+所示方向平移平移方向是使di+或 di增加的方向。2根據(jù)目標(biāo)函數(shù)中的優(yōu)先因子來分析求解 先考慮第一優(yōu)先因子3 1,即要求實(shí)現(xiàn) min di。由圖可見，可以滿足 di =0，這時(shí)， xi、X2的取值范圍只能在三角形 OBC上； 再考慮第二優(yōu)先因子3 2,即要求實(shí)現(xiàn) min(d2+d2)。當(dāng)d2+= d2 =0時(shí)，xi、X2可在線 段ED上取值； 最后考慮第三優(yōu)先因子3 3,即要求實(shí)現(xiàn) mind3。從圖中可以看到，要使 d3 =0, xi、 X2只能在多邊形BCJF取值；因此，線段GD上的點(diǎn)即為該目標(biāo)規(guī)劃的最優(yōu)解有效解。4. 分層單純形法目

47、標(biāo)規(guī)劃與線性規(guī)劃的數(shù)學(xué)模型沒有本質(zhì)區(qū)別，因而也可以用單純形法求解，但考慮 到目標(biāo)規(guī)劃的某些特點(diǎn)，做出以下規(guī)定：j > 0j =1,2,n為最1由于目標(biāo)規(guī)劃問題的目標(biāo)函數(shù)均為求最小值，故以檢驗(yàn)數(shù)b 優(yōu)準(zhǔn)那么;b n=C CbA，所以各檢驗(yàn)數(shù)b j中含有1,2, ,n2由于目標(biāo)規(guī)劃的檢驗(yàn)系數(shù)矩陣b = b 1 b 2 不同優(yōu)先級(jí)的權(quán)因子3k，即mMj cjciai jk j ki 1k 1當(dāng)權(quán)因子3 1> 3 2>3 M時(shí)，從各檢驗(yàn)數(shù)的整體來看，各檢驗(yàn)數(shù)的正負(fù)首先決定于31的系數(shù)B 1 j的正負(fù)；假設(shè)卩1 j =0，那么檢驗(yàn)數(shù)的正負(fù)就取決于32的系數(shù)B 2 j的正負(fù)；以此類推。注意：在目標(biāo)規(guī)劃的分層單純形法中，其基變量的檢驗(yàn)數(shù)同樣為零向量。求解目標(biāo)規(guī)劃問題的.分層.單純形法計(jì)算步驟為：1建立初始單純形表，在表中將檢驗(yàn)數(shù)行按優(yōu)先因子個(gè)數(shù)分別列成M行，令k=1 ；2檢查該檢驗(yàn)數(shù)行中是否存在負(fù)數(shù)，且對(duì)應(yīng)的前k 1行的系數(shù)是零。假設(shè)有負(fù)數(shù)，那么取其中最小者對(duì)應(yīng)的變量為換入變量，并轉(zhuǎn)至3；假設(shè)無負(fù)數(shù)，那么轉(zhuǎn)至