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

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

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

4、等值線，與陰影部分的邊界相交于點Q(4,2) ，表明最優(yōu)生產(chǎn)計劃為：生產(chǎn)I產(chǎn)品4件，生產(chǎn)II產(chǎn)品2件。,10,例4,Z=36,11,3.圖解法的作用,能解決少量問題,LP問題,有可行解,有最優(yōu)解,唯一解 無窮多解,無最優(yōu)解（可行域為無界）,無可行解（無解）,規(guī)律1：,揭示了線性規(guī)劃問題的若干規(guī)律,12,規(guī)律2：,線性規(guī)劃問題的可行域為一凸集 線性規(guī)劃問題凸集的頂點個數(shù)是有限的 最優(yōu)解可在凸集的某頂點處達到,13,四、線性規(guī)劃問題的標準型,1.標準型,特點：目標最大化、約束為等式、 決策變量非負、右端項非負。,14,2.線性規(guī)劃標準型的向量和矩陣表達式,矩陣式: Max Z=CTX s.t. A

5、X=b X0,n 向量式: Max Z= cjxj j=1 n s.t. 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問題均可化為標準型,16,例5 化標準型,可化為,17,例6 化標準型,Max Z =x1+2x2+3x4-3x5+0 x6+0 x7 s.t. x1 -

6、x2 + x4 - x5+x6 = 7 x1+x2 + x4 - x5 - x7 = 2 -3x1 -x2+3x4 -3x5 = 5 x20 , xj0, j=1,4,5,6,7,18,課堂練習,19,五、標準型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， 求得的

7、一組基變量XB的值稱為基解。,基可行解 既是基本解，又是可行解。,結(jié)論：基可行解的個數(shù)基解的個數(shù)Cnm,23,線性規(guī)劃標準型問題解的關(guān)系,約束方程的 解空間,基解,可行解,非可行解,基可 行解,24,例1（書P8）： Max Z =2x1+3x2 s.t. x1+ 2x28 4x1 16 4x2 12 x1, x2 0,六、可行解、基解和基可行解舉例,x1+2x2=8,x1,標準型,25,例2,26,第二節(jié) LP問題的基本理論,一、基本概念,27,28,定理1 LP問題的可行域為一凸集。,二、基本定理,29,引理 線性規(guī)劃問題的可行解X=(x1, x2, , xn)T是基可行解的充要條件為X的

8、正分量所對應(yīng)的系數(shù)列向量是線性獨立的。,30,定理2 線性規(guī)劃問題的基可行解對應(yīng)于可行域的頂點。,（即：設(shè)X是LP問題的可行解，則X不是LP問題的基可行解當且僅當X不是可行域頂點）,31,32,33,定理3 若可行域有界，則LP問題的目標函數(shù)一定可以在其可行域的頂點上達到最優(yōu)。,34,總結(jié) 線性規(guī)劃問題的可行域是凸集(定理1)；凸集的頂點對應(yīng)于基可行解(定理2)，基可行解(頂點)的個數(shù)是有限的（不超過Cnm個）；若線性規(guī)劃有最優(yōu)解，必在可行域某頂點上達到(定理3)。因此,我們可以在有限個基可行解中尋找最優(yōu)解。,35,這就提供了尋求線性規(guī)劃問題最優(yōu)解的途徑：在有限個基可行解中尋求最優(yōu)解, 但窮舉

9、法仍然低效率的。針對線性規(guī)劃問題的特點，有效地求解方法是單純形方法。 單純形方法的基本思想是：開始于某一個可行基及其對應(yīng)的基可行解，從一個基可行解迭代到另一個基可行解，并且使目標函數(shù)值不斷增大，經(jīng)過有限步必能求得線性規(guī)劃問題的最優(yōu)解或者判定線性規(guī)劃問題無有界的最優(yōu)解。,36,第三節(jié) 單純形法,一、基本思想,化LP問題為標準型， 確定一個初始基可行解,檢驗解的 最優(yōu)性,結(jié)束,是,樞軸運算（旋轉(zhuǎn)運算） 確定另一個基可行解,否,37,二、舉例,例（書P8）： Max Z =2x1+3x2 s.t. x1+ 2x28 4x1 16 4x2 12 x1, x2 0,標準型,保證單位矩陣，如果找不到，后面

10、會介紹人工變量法。 對上述約束等式變形得：,38,39,40,41,42,問題： (1) 為何最后目標函數(shù)表達式無正系數(shù)時，得到最優(yōu)解；何時出現(xiàn)無窮多解以及無界解？ (2) 每次如何選取進基變量和出基變量？,43,三、進基變量的選擇,44,45,結(jié)論：每次進基變量選擇當前檢驗數(shù)最大的 非基變量，這樣能使目標函數(shù)值盡快 增大。,46,四、最優(yōu)性檢驗與解的判別,47,三、檢驗數(shù)的意義,結(jié)論：如果LP問題通過單純形法迭代到某步時，所有檢驗數(shù)0,則該LP問題已得到最優(yōu)解。,Max Z=CTX s.t. AX=b X0,若cj-CBB-1Pj=j0, 則ZZ0, Z0即為最優(yōu)解. (基變量的檢驗數(shù)必為0

11、),令A(yù)=(B,N), X= XB ,CT=(CBT,CNT) XN,48,一、步驟,Step 1. 化LP問題為標準型,建立初始單純形表; Step 2. 若所有檢驗數(shù)0,則最優(yōu)解已達到。 否則,計算 , 選取k 所對應(yīng)的變量xk 為進基變量; Step 3. 計算 ,選取l 所對應(yīng)的變量xl 為出基變量; Step 4. 以alk為主元素進行旋轉(zhuǎn)運算,轉(zhuǎn)Step 2;,第四節(jié) 單純形法的步驟,49,基可行解： x1=b1, x2=b2, , xm=bm , xm+1=xm+2= =xn= 0,1.初始單純形表,c1 c2 cm cm+1 cn,c1 x1 c2 x2 cm xm,b1 b2

12、 bm,1 0 0 a1, m+1 a1n 0 1 0 a2, m+1 a2n 0 0 1 am, m+1 amn,0 0 0 m+1 n,-CBTB-1b,50,2.進基變量的選擇,選取 所對應(yīng)的變量xk 為進基變量。,51,3.出基變量的選擇,選取 所對應(yīng)的變量xl 為出基變量。,52,4.旋轉(zhuǎn)運算,ck xk,bl /alk,0 1/alk 0 al, m+1/alk1 aln/alk,b1,1 -a1k/alk 0 a1, m+1 0 a1n,bm,0 -amk/alk1 am, m+1 0 amn,53,二、實例,化為標準型,54,單純形表算法,以4為樞軸元素進行旋轉(zhuǎn)運算，x2為換入

13、變量，x5為換出變量,以1為樞軸元素進行運算，x1為換入變量， x3為換出變量,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,55,以2為樞軸元素進行運算，x5為換入變量， x4為換出變量,此時達到最優(yōu)解：X*=(4, 2)T, Max Z=14。,56,1 D. Goldfarb and J.K. Reid, A practicable steepest-edge simplex algorithm, Mathematical Programming,12,361-371,(1

14、977).,2 J.J.Forrest and D. Goldfarb, Steepest-edge simplex algorithms for linear programming, Mathematical Programming,57,341-374,(1992).,參考文獻：,最陡邊下降法,57,一、人工變量法,第五節(jié) LP問題的進一步討論,58,1.大M法（M為任意大的正數(shù)）,加入松弛變量x4;剩余變量x5;人工變量x6, x7,59,1) 人工變量的識別,2) 目標函數(shù)的處理,3) 計算(單純形法),60,注意：本例是求最小值，所以用所有 來判別目標函數(shù)是否實現(xiàn)了最小化。因而換入

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

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

17、“攝動法”、“辭典序法”、 Bland規(guī)則等,1974年Bland提出Bland算法規(guī)則：,70,3.最小比值原則失效,經(jīng)過一次迭代后可得右表,當用單純形法求解LP問題迭代到某步時,存在某k0, 而k對應(yīng)列向量Pk0, 則此LP問題有無界解.,71,4.在最優(yōu)表中出現(xiàn)某非基變量檢驗數(shù)為0,72,73,例1 某工廠要用三種原材料C、P、H混合調(diào)配出三種不同規(guī)格的產(chǎn)品A、B、C。已知產(chǎn)品的規(guī)格要求、單價和原材料的供應(yīng)量、單價。該廠應(yīng)如何安排生產(chǎn)使利潤最大？,第六節(jié) 應(yīng)用舉例,74,用單純型法計算得結(jié)果：每天生產(chǎn)A產(chǎn)品200kg,分別需要原料:C為100kg;P為50kg;H為50kg. 總利潤收入Z=500元/天.,75,先考慮一月份的線性規(guī)劃模型:,例2,76,以一月份內(nèi)各種設(shè)備的生產(chǎn)能力總和為分母,生產(chǎn)產(chǎn)品所需要的各類設(shè)備的總臺時數(shù)為分子,可計算出一月份的平均設(shè)備利用系數(shù)Z,將Z作為目標函數(shù),可得下面的模型:,77,考慮二月份線性規(guī)劃模型時:(1)從全年計劃中減去一月份已生產(chǎn)的數(shù)量;(2)對批量小的產(chǎn)品,如一月份已經(jīng)安排較大產(chǎn)量的,二月份將剩余部分安排生產(chǎn);(3)保證第4號產(chǎn)品在月底前交貨.,這樣,我們可以依次對12個月列出線性規(guī)劃模型并求解,再根據(jù)具體情況對計算結(jié)果進行必要調(diào)整。,78,例3 某部門在今后5年內(nèi)連續(xù)給以下項目投資：,項目