1、1,第一章 線性規(guī)劃與單純形法,本章重點(diǎn)內(nèi)容 線性規(guī)劃模型與解的主要概念 線性規(guī)劃的單純形法，線性規(guī)劃多解分析 線性規(guī)劃的應(yīng)用建模,2,第一節(jié) 線性規(guī)劃問題及數(shù)學(xué)模型,1939年，（蘇） 康托洛維奇 1941年，（美） Hichook 1947年，G. B. Dantzig 單純形法 1979年，（蘇） 哈奇安算法 1984年，Karmarkar算法,3,設(shè)I、II兩種產(chǎn)品的產(chǎn)量分別為x1, x2 。建立該問題的數(shù)學(xué)模型為:,例2 現(xiàn)要做100套鋼架，每套需2.9米、2.1米和1.5米的元鋼各一根。已知原料長7.4米，問如何下料，使余料最少？,一、實(shí)例,4,解：設(shè)I, II, III, IV,

2、 V分別代表五種不同的原料用量方案, x1, x2 , x3, x4 , x5分別代表采用各方案下料的元鋼的根數(shù)。,5,6,目標(biāo)函數(shù)用決策變量的線性函數(shù)來表示。按問題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。,每一個問題變量都用一組決策變量（x1, x2, , xn）表示方案，這組決策變量的值代表一個具體方案，這些變量是非負(fù)的。,存在一定的約束條件，這些約束條件可以用一組線性等式或線性不等式來表示。,結(jié)論：線性規(guī)劃是研究在一組線性不等式或線性等式約束下，使得某一線性目標(biāo)函數(shù)取最大或最小的極值問題。,二、線性規(guī)劃問題（LP問題）的共同特征,7,Max(Min) Z=c1x1+c2x2+cnxn a

3、11x1+a12x2+a1nxn ( =, ) b1 a21x1+a22x2+a2nxn ( =, ) b2 s.t. am1x1+am2x2+amnxn ( =, ) bm xj0, j=1,2, ，n n變量個數(shù)； m約束行數(shù)； cj價(jià)值系數(shù)； bi右端項(xiàng)； aij技術(shù)系數(shù),線性規(guī)劃模型的一般形式為：,8,1.線性不等式的幾何意義 半平面,作出LP問題的可行域 作出目標(biāo)函數(shù)的等值線 移動等值線到可行域邊界得到最優(yōu)點(diǎn),2.圖解法步驟,三、兩變量線性規(guī)劃問題的圖解法,9,4x1=16,4x2=12,x1+2x2=8,x1,x2,4,8,4,3,0,例3（書P8）：,Q(4,2),Z=2x1+3

4、x2,做目標(biāo)函數(shù)2x1+3x2的等值線，與陰影部分的邊界相交于點(diǎn)Q(4,2) ，表明最優(yōu)生產(chǎn)計(jì)劃為：生產(chǎn)I產(chǎn)品4件，生產(chǎn)II產(chǎn)品2件。,10,例4,Z=36,11,3.圖解法的作用,能解決少量問題,揭示了線性規(guī)劃問題的若干規(guī)律,12,規(guī)律2：,線性規(guī)劃問題的可行域?yàn)橥辜?線性規(guī)劃問題凸集的頂點(diǎn)個數(shù)是有限的 最優(yōu)解可在凸集的某頂點(diǎn)處達(dá)到,13,四、線性規(guī)劃問題的標(biāo)準(zhǔn)型,1.標(biāo)準(zhǔn)型,特點(diǎn)：目標(biāo)最大化、約束為等式、 決策變量非負(fù)、右端項(xiàng)非負(fù)。,14,2.線性規(guī)劃標(biāo)準(zhǔn)型的向量和矩陣表達(dá)式,矩陣式: Max Z=CTX s.t. AX=b X0,n 向量式: Max Z= cjxj j=1 n s.t.

5、 Pjxj=b j=1 xj 0, j=1,2, . ,n,其中：C = (c1 , c2 , . , cn)T b = (b1 , b2 , . , bm)T X = (x1 , x2 , . , xn)T a11 a12 . a1n A= a21 a22 . a2n . . am1 am2 . amn = ( P1 , P2 , . , Pn ),15,3.所有LP問題均可化為標(biāo)準(zhǔn)型,16,例5 化標(biāo)準(zhǔn)型,可化為,17,例6 化標(biāo)準(zhǔn)型,Max Z =x1+2x2+3x4-3x5+0 x6+0 x7 s.t. x1 - x2 + x4 - x5+x6 = 7 x1+x2 + x4 - x5

6、- x7 = 2 -3x1 -x2+3x4 -3x5 = 5 x20 , xj0, j=1,4,5,6,7,18,課堂練習(xí),19,五、標(biāo)準(zhǔn)型LP問題解的概念,20,21,令B = =( P1 , P2 , , Pm ) 且| B | 0 ，則稱Pj (j=1,2,m) 為基向量。 與基向量Pj對應(yīng)的變量xj稱為基變量， 記為XB = ( x1 , x2 , , xm )T，其余的變量稱為非基變量，記為 XN = ( xm+1 , xm+2 , , xm+n ) T 。,基變量：,22,基解 令非基變量XN = 0， 求得的一組基變量XB的值稱為基解。,基可行解（頂點(diǎn)） 既是基本解，又是可行解。

7、,結(jié)論：基可行解的個數(shù)基解的個數(shù)Cnm,23,線性規(guī)劃標(biāo)準(zhǔn)型問題解的關(guān)系,約束方程的 解空間,基解,可行解,非可行解,基可 行解,24,例7 Max Z =2x1+3x2 s.t. x1+ 2x28 4x1 16 4x2 12 x1, x2 0,六、可行解、基解和基可行解舉例,4x1=16,4x2=12,x1+2x2=8,x1,x2,0,Z=2x1+3x2,A,B,C,D,E,F,G,H,標(biāo)準(zhǔn)型,25,例8,26,第二節(jié) LP問題的基本理論,一、基本概念,27,定理1 LP問題的可行域?yàn)橐煌辜?二、基本定理,28,引理 線性規(guī)劃問題的可行解X=(x1, x2, , xn)T是基可行解的充要條

8、件為X的正分量所對應(yīng)的系數(shù)列向量是線性獨(dú)立的。,29,定理2 線性規(guī)劃問題的基可行解對應(yīng)于可行域的頂點(diǎn)。,（即：若X是LP問題的可行解，則“X是LP問題的基可行解”等價(jià)于“X是LP問題可行域頂點(diǎn)”）,30,31,32,定理3 若可行域有界，則LP問題的目標(biāo)函數(shù)一定可以在其可行域的頂點(diǎn)上達(dá)到最優(yōu)。,引理 若S是有界凸集，則任何一點(diǎn)XS可表示為S的頂點(diǎn)的凸組合。,33,線性規(guī)劃問題的可行域是凸集(定理1)；凸集的頂點(diǎn)對應(yīng)于基可行解(定理2)，基可行解(頂點(diǎn))的個數(shù)是有限的；若線性規(guī)劃有最優(yōu)解，必在可行域某頂點(diǎn)上達(dá)到(定理3)。因此,我們可以在有限個基可行解中尋找最優(yōu)解。,34,第三節(jié) 單純形法,一

9、、基本思想,檢驗(yàn)解的 最優(yōu)性,結(jié)束,Y,樞軸運(yùn)算（旋轉(zhuǎn)運(yùn)算） 確定另一個基本可行解,N,化LP問題為標(biāo)準(zhǔn)型， 確定一個初始基本可行解,35,以x2為主元素,以x1為主元素,例 2x1+ x2+ 2x3=10 (1) 3x1+ 3x2+ x3= 6 (2),二、樞軸運(yùn)算,36,三、檢驗(yàn)數(shù)的意義,結(jié)論：如果LP問題通過單純形法迭代到某步時(shí)，所有檢驗(yàn)數(shù)0,則該LP問題已得到最優(yōu)解。,Max Z=CTX s.t. AX=b X0,若cj-CBTB-1Pj=j0, 則ZZ0, Z0即為最優(yōu)解. (基變量的檢驗(yàn)數(shù)必為0),令A(yù)=(B,N), X= XB ,CT=(CBT,CNT) XN,37,一、步驟,S

10、tep 1. 化LP問題為標(biāo)準(zhǔn)型,建立初始單純形表; Step 2. 若所有檢驗(yàn)數(shù)0,則最優(yōu)解已達(dá)到。 否則,計(jì)算 , 選取k 所對應(yīng)的變量xk 為換入變量; Step 3. 計(jì)算 ,選取l 所對應(yīng)的變量xl 為換出變量; Step 4. 以alk為主元素進(jìn)行旋轉(zhuǎn)運(yùn)算,轉(zhuǎn)Step 2;,第四節(jié) 單純形法的步驟,38,初始基可行解：x1=0, x2=0, x3=8 , x4=16, x5= 12,1.初始單純形表,0 x3 0 x4 0 x5,2 3 0 0 0,8 16 12,1 2 1 0 0 4 0 0 1 0 0 4 0 0 1,39,2.換入變量的選擇,選取 所對應(yīng)的變量xk 為換入變

11、量。,0 x3 0 x4 0 x5,2 3 0 0 0,8 16 12,1 2 1 0 0 4 0 0 1 0 0 4 0 0 1,2 3 0 0 0,0,檢驗(yàn)數(shù)j 的計(jì)算方法：j = cj-CBTB-1Pj 基變量的檢驗(yàn)數(shù)必為0，只需計(jì)算非基變量檢驗(yàn)數(shù)。方法是：將左列基變量價(jià)值系數(shù)與所求非基變量系數(shù)列分別相乘再相加，然后被該非基變量價(jià)值系數(shù)減去。,40,3.換出變量的選擇,選取 所對應(yīng)的變量xl 為換出變量。,0 x3 0 x4 0 x5,2 3 0 0 0,8 16 12,1 2 1 0 0 4 0 0 1 0 0 4 0 0 1,2 3 0 0 0,0,4 - 3,最小比值 的計(jì)算方法：

12、 以b列為分子，換入變量列元素(0)為分母，計(jì)算各行比值，其最小者為。,41,4.旋轉(zhuǎn)運(yùn)算,x2為換入變量，x5為換出變量，以4為主元素進(jìn)行旋轉(zhuǎn)運(yùn)算,0 x3 0 x4 0 x5,2 3 0 0 0,8 16 12,1 2 1 0 0 4 0 0 1 0 0 4 0 0 1,2 3 0 0 0,0,4 - 3,42,二、實(shí)例,化為標(biāo)準(zhǔn)型,43,單純形表算法,x2為換入變量，x5為換出變量，以4為樞軸元素進(jìn)行旋轉(zhuǎn)運(yùn)算,x1為換入變量， x3為換出變量，以1為樞軸元素進(jìn)行運(yùn)算,0 x3 0 x4 0 x5,2 3 0 0 0,8 16 12,1 2 1 0 0 4 0 0 1 0 0 4 0 0

13、1,2 3 0 0 0,0,4 - 3,44,x5為換入變量， x4為換出變量，以2為樞軸元素進(jìn)行運(yùn)算,此時(shí)達(dá)到最優(yōu)解：X*=(4, 2)T, Max Z=14。,45,4x1=16,4x2=12,x1+2x2=8,x1,x2,4,8,4,O,三、單純形表與圖解法的對應(yīng)關(guān)系,Q1,Q2,Q,Q3,圖解法：,單純形表算法：,46,1 D. Goldfarb and J.K. Reid, A practicable steepest-edge simplex algorithm, Mathematical Programming,12,361-371,(1977).,2 J.J.Forrest a

14、nd D. Goldfarb, Steepest-edge simplex algorithms for linear programming, Mathematical Programming,57,341-374,(1992).,參考文獻(xiàn)：,最陡邊下降法,47,一、人工變量法,第五節(jié) LP問題的進(jìn)一步討論,48,1.大M法（M為任意大的正數(shù)）,加入松弛變量x4;剩余變量x5;人工變量x6, x7,49,1) 人工變量的識別,2) 目標(biāo)函數(shù)的處理,3) 計(jì)算(單純形法),50,注意：本例是求最小值，所以用所有 來判別目標(biāo)函數(shù)是否實(shí)現(xiàn)了最小化。因而換入變量xk的選取標(biāo)準(zhǔn)為,51,結(jié)果得: X*

15、=(4,1,9,0,0,0,0) Z*=-2,（接上表）,52,兩階段法 (將LP問題分成兩個階段來考慮),第I 階段: 不考慮原問題是否存在可行解，給原LP問題加入人工變量，并構(gòu)造僅含人工變量的目標(biāo)函數(shù)和要求最小化；然后用單純形法求解，若得W=0，則進(jìn)行第二階段計(jì)算，否則無可行解。,第II 階段：將第一階段得到的最終表除去人工變量，將目標(biāo)函數(shù)行的系數(shù)換為原問題的系數(shù)，作為第二階段的初始表。,53,加入松弛變量x4;剩余變量x5;人工變量x6,x7,用單純形法求解第一階段的結(jié)果得：,54,此時(shí)，達(dá)到第一階段的最優(yōu)解，W=0,55,由于人工變量x6 =x7=0,所以(0, 1, 1, 12, 0

16、)T 是該線性規(guī)劃問題的基可行解。于是轉(zhuǎn)入第二階段運(yùn)算：,此時(shí)達(dá)到該LP問題的最優(yōu)解：x1=4, x2=1, x3=9; 目標(biāo)函數(shù)值Z= -2。,56,1.存在兩個以上的最大正檢驗(yàn)數(shù)。選擇任何變量（對應(yīng)最大正檢驗(yàn)數(shù)）作為進(jìn)基變量。,2.最小比值相同。此時(shí)LP問題出現(xiàn)退化現(xiàn)象。,二、單純形法中存在的問題,如果在一個基本可行解的基變量中至少有一個分量為0，則稱此基本可行解是退化的基本可行解。,57,58,選取 x1 為換入變量；選取下標(biāo)最小的 x5 為換出變量，得下表：,此時(shí)換出變量為x1，換入變量為x4，迭代后目標(biāo)函數(shù)值不變。,59,解決退化的方法有： “攝動法”、“辭典序法”、 Bland規(guī)則

17、等,1974年Bland提出Bland算法規(guī)則：,60,3.最小比值原則失效,經(jīng)過一次迭代后可得右表,當(dāng)用單純形法求解LP問題迭代到某步時(shí),存在某k0, 而k對應(yīng)列向量Pk0, 則此LP問題有無界解.,61,4.在最優(yōu)表中出現(xiàn)某非基變量檢驗(yàn)數(shù)為0,62,63,例1 某工廠要用三種原材料D、P、H混合調(diào)配出三種不同規(guī)格的產(chǎn)品A、B、C。已知產(chǎn)品的規(guī)格要求、單價(jià)和原材料的供應(yīng)量、單價(jià)。該廠應(yīng)如何安排生產(chǎn)使利潤最大？,第六節(jié) 應(yīng)用舉例,解：設(shè)A中D、P、H的含量為x11、x12、x13 B中D、P、H的含量為x21、x22、x23 C中D、P、H的含量為x31、x32、x33,64,用單純形法計(jì)算得

18、結(jié)果：每天生產(chǎn)A產(chǎn)品200kg,分別需要原料:D為100kg;P為50kg;H為50kg. 總利潤收入Z=500元/天.,65,先考慮一月份的線性規(guī)劃模型:,例2,66,以一月份內(nèi)各種設(shè)備的生產(chǎn)能力總和為分母,生產(chǎn)產(chǎn)品所需要的各類設(shè)備的總臺時(shí)數(shù)為分子,可計(jì)算出一月份的平均設(shè)備利用系數(shù)Z,將Z作為目標(biāo)函數(shù),可得下面的模型:,67,考慮二月份線性規(guī)劃模型時(shí):(1)從全年計(jì)劃中減去一月份已生產(chǎn)的數(shù)量;(2)對批量小的產(chǎn)品,如一月份已經(jīng)安排較大產(chǎn)量的,二月份將剩余部分安排生產(chǎn);(3)保證第4號產(chǎn)品在月底前交貨.,這樣,我們可以依次對12個月列出線性規(guī)劃模型并求解,再根據(jù)具體情況對計(jì)算結(jié)果進(jìn)行必要調(diào)整。,68,例3 某部門在今后5年內(nèi)連續(xù)給以下項(xiàng)目投資：,