1、 線性規(guī)劃與單純形法 線性規(guī)劃 （LP： Linear Programming） 規(guī)劃論中的靜態(tài)規(guī)劃 解決有限資源的最佳分配問題 求解方法： 圖解法 單純形解法 線性規(guī)劃簡介 19391939年蘇聯(lián)的康托洛維奇年蘇聯(lián)的康托洛維奇H.B.Kahtopob H.B.Kahtopob ）和美國的希奇）和美國的希奇柯克柯克F.L.HitchcockF.L.Hitchcock等人就在生產(chǎn)組織管理和制定交通等人就在生產(chǎn)組織管理和制定交通運輸方案方面首先研究和應(yīng)用一線性規(guī)劃方法。運輸方案方面首先研究和應(yīng)用一線性規(guī)劃方法。 19471947年旦茨格等人提出了求解線性規(guī)劃問題的單純形法，年旦茨格等人提出了求解線

2、性規(guī)劃問題的單純形法，為線性規(guī)劃的理論與計算奠定了基礎(chǔ)。為線性規(guī)劃的理論與計算奠定了基礎(chǔ)。 隨著電子計算機的出現(xiàn)和日益完善，規(guī)劃論得到迅速的發(fā)隨著電子計算機的出現(xiàn)和日益完善，規(guī)劃論得到迅速的發(fā)展，可用電子計算機來處理成千上萬個約束條件和變量的展，可用電子計算機來處理成千上萬個約束條件和變量的大規(guī)模線性規(guī)劃問題，從解決技術(shù)問題的最優(yōu)化，到工業(yè)、大規(guī)模線性規(guī)劃問題，從解決技術(shù)問題的最優(yōu)化，到工業(yè)、農(nóng)業(yè)、商業(yè)、交通運輸業(yè)以及決策分析部門都可以發(fā)揮作農(nóng)業(yè)、商業(yè)、交通運輸業(yè)以及決策分析部門都可以發(fā)揮作用。用。線性規(guī)劃問題的三個要素線性規(guī)劃問題的三個要素 決策變量 決策問題待定的量值稱為決策變量。 決策變

3、量的取值要求非負。 約束條件 任何問題都是限定在一定的條件下求解，把各種限制條件表示為一組等式或不等式，稱之為約束條件。 約束條件是決策方案可行的保障。 LP的約束條件，都是決策變量的線性函數(shù)。 目標函數(shù) 衡量決策方案優(yōu)劣的準則，如時間最省、利潤最大、成本最低。 目標函數(shù)是決策變量的線性函數(shù)。 有的目標要實現(xiàn)極大，有的則要求極小。1線性規(guī)劃問題及其數(shù)學(xué)模型 設(shè)設(shè) 備備原原料料A A原原料料B B 1 4 0 2 0 4 8臺時 16kg 12kg例 某工廠在計劃期內(nèi)要安排生產(chǎn)、兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時和原料A、B的消耗量如下表。 該工廠每生產(chǎn)一件產(chǎn)品可獲利2元，每生產(chǎn)一件產(chǎn)品可

4、獲利3元，問應(yīng)如何安排生產(chǎn)計劃能使該廠獲利最多？ 這個問題可以用下面的數(shù)學(xué)模型來描述，設(shè)計劃期內(nèi)產(chǎn)品、的產(chǎn)量分別為x1，x2，可獲利潤用z表示，則有：Max Z=2x1+3x2x1+2x284x1 16 4x212x1, x201.1問題的提出問題的提出又例又例 靠近某河流有兩個化工廠，靠近某河流有兩個化工廠，流經(jīng)第一化工廠的河流流量為每天流經(jīng)第一化工廠的河流流量為每天500萬萬m3，兩工廠之間有一條流量，兩工廠之間有一條流量為每天為每天200萬萬m3的支流見圖）。的支流見圖）。 第一化工廠每天排放污水第一化工廠每天排放污水2萬萬m3，第二化工廠每，第二化工廠每天排放污水天排放污水 1.4萬萬

5、m3。污水從工廠。污水從工廠1流到工廠流到工廠2前前會有會有20%自然凈化。根據(jù)環(huán)保要求，河水中污水自然凈化。根據(jù)環(huán)保要求，河水中污水的含量應(yīng)不大于的含量應(yīng)不大于0.2%。而工廠。而工廠1和工廠和工廠2處理污處理污水的成本分別為水的成本分別為1000元元/萬萬m3和和800元元/萬萬m3。問。問兩工廠各應(yīng)處理多少污水才能使處理污水的總費兩工廠各應(yīng)處理多少污水才能使處理污水的總費用最低？用最低？ 設(shè)工廠設(shè)工廠1和工廠和工廠2每每天分別處理污水天分別處理污水x1和和x2萬萬m3，則有：，則有：Min z=1000 x1+800 x2 (2-x1)/500 0.0020.8(2-x1)+1.4-x2

6、/700 0.002 x12, x21.4 x1, x20以上兩例都有一些共同的特征：以上兩例都有一些共同的特征：用一組變量表示某個方案，一用一組變量表示某個方案，一般這些變量取值是非負的。般這些變量取值是非負的。存在一定的約束條件，可以用存在一定的約束條件，可以用線性等式或線性不等式來表示。線性等式或線性不等式來表示。都有一個要達到的目標，可以都有一個要達到的目標，可以用決策變量的線性函數(shù)來表示。用決策變量的線性函數(shù)來表示。 滿足以上條件的數(shù)學(xué)模型稱為線性規(guī)劃模型。線性規(guī)劃模型的一般形式如下：0,),(),(),(max(min)21221122222121112121112211nmnmn

7、mmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcz其中：其中：cj為價值系數(shù)；為價值系數(shù)；aij為技術(shù)系數(shù)；為技術(shù)系數(shù)；bi為限額系數(shù)；為限額系數(shù)；xj為非負變量為非負變量 圖解法即是用圖示的方法來求解線性規(guī)劃問圖解法即是用圖示的方法來求解線性規(guī)劃問題。題。 一個二維的線性規(guī)劃問題，可以在平面圖上一個二維的線性規(guī)劃問題，可以在平面圖上求解，三維的線性規(guī)劃則要在立體圖上求解，求解，三維的線性規(guī)劃則要在立體圖上求解，這就比較麻煩，而維數(shù)再高以后就不能圖示這就比較麻煩，而維數(shù)再高以后就不能圖示了。了。1.2線性規(guī)劃的圖解法線性規(guī)劃的圖解法可行域的確定可行域的確定 例例:數(shù)

8、學(xué)模型為數(shù)學(xué)模型為 maxZ= 3x1 +5 x2 x1 8 2x2 12 3x1 +4 x2 36 x1 0, x2 0S.t.x1 =82x2 =123x1 +4 x2 =36x1x24812369 五邊形五邊形OABCD內(nèi)內(nèi)(含邊界含邊界)的任意一點的任意一點 (x1，x2) 都是滿足所有都是滿足所有約束條件的一個解，稱之可行解約束條件的一個解，稱之可行解 。 滿足所有約束條件的解的集合，稱之為可行域。即所有約束滿足所有約束條件的解的集合，稱之為可行域。即所有約束條件共同圍城的區(qū)域。條件共同圍城的區(qū)域。最優(yōu)解的確定最優(yōu)解的確定Z=30Z=42Z=15 目標函數(shù) Z= 3x1 +5 x2

9、代表以Z為參數(shù)的一族平行線。x1 =82x2 =123x1 +4 x2 =36x1x24812369 等值線：位于同一直線上的點的目標函數(shù)值相同。等值線：位于同一直線上的點的目標函數(shù)值相同。 最優(yōu)解：可行解中使目標函數(shù)最優(yōu)最優(yōu)解：可行解中使目標函數(shù)最優(yōu)(極大或極小極大或極小)的解的解 由線性不等式組成的可行域是凸集由線性不等式組成的可行域是凸集(凸集的定凸集的定義是：集合內(nèi)部任意兩點連線上的點都屬于這義是：集合內(nèi)部任意兩點連線上的點都屬于這個集合個集合)。 可行域有有限個頂點。設(shè)規(guī)劃問題有可行域有有限個頂點。設(shè)規(guī)劃問題有n個變量，個變量，m個約束，則頂點的個數(shù)不多于個約束，則頂點的個數(shù)不多于C

10、nm個。個。 目標函數(shù)最優(yōu)值一定在可行域的邊界達到，而目標函數(shù)最優(yōu)值一定在可行域的邊界達到，而不可能在其內(nèi)部。不可能在其內(nèi)部。幾點說明幾點說明解的可能性解的可能性x1 =82x2 =123x1 +4 x2 =36x1x24812369上例的數(shù)學(xué)模型變?yōu)樯侠臄?shù)學(xué)模型變?yōu)?maxZ= 3x1 +4 x2 x1 8 2x2 12 3x1 +4 x2 36 x1 0, x2 0S.t.Z=24Z=36Z=12 唯一最優(yōu)解：只有一個最優(yōu)點。 多重最優(yōu)解：無窮多個最優(yōu)解。若在兩個頂點同時得到最優(yōu)解，則它們連線上的每一點都是最優(yōu)解。 無界解：線性規(guī)劃問題的可行域無界，使目標函數(shù)無限增大而無界。（缺乏必要的

11、約束條件）例如例如 maxZ= 3x1 +2 x2 -2x1 + x2 2 x1 -3 x2 3 x1 0, x2 0-2x1 + x2 =2x1 -3 x2 =3x2123-1x1123-1Z=6Z=12S.t. 無可行解：若約束條件相互矛盾，則可行域為空集例如例如 maxZ= 3x1 +2 x2 -2x1 + x2 2 x1 -3 x2 3 x1 0, x2 0-2x1 + x2 =2x1 -3 x2 =3x2123-1x1123-1S.t.唯一最優(yōu)解無窮多最優(yōu)解x1x2x1x2無界解無可行解當(dāng)線性規(guī)劃的可行域非空它是有界或無界凸多邊形，若存在最優(yōu)解，則最優(yōu)解一定在可行域的的某個頂點或頂點

12、的連線取得，也即有唯一最優(yōu)解或無窮多最優(yōu)解圖解法雖然簡單直觀，但是只能解決兩個變量練習(xí):用圖解法求解以下LP模型無符號限制21212121,2322265maxxxxxxxxxzAnswerx1x2-2x1+3x2=2x1-2x2=20Ax1= -10,x2= -6,z= -861.3 線性規(guī)劃的標準型 線性規(guī)劃問題的數(shù)學(xué)模型有各種不同的形式，如 目標函數(shù)有極大化和極小化； 約束條件有“”、“”和“”三種情況； 決策變量一般有非負性要求，有的則沒有。 為了求解方便，特規(guī)定一種線性規(guī)劃的標準形式，非標準型可以轉(zhuǎn)化為標準型。標準形式為： 目標函數(shù)極大化 約束條件為等式 右端常數(shù)項bi0 決策變量非

13、負。一一 、標準型、標準型1. 代數(shù)式二、標準型的表達方式二、標準型的表達方式 有代數(shù)式、矩陣式：有代數(shù)式、矩陣式：maxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxnbm x1,x2,xn 0maxZ= cjxj aijxjbi ( i=1,2,m) xj0 ( j=1,2,n)nj1nj1簡記2. 矩陣式矩陣式 0. .maxXbAXtsXCZ),(21ncccC價值向量mnmmnnaaaaaaaaaA212222111211技術(shù)矩陣mbbbb21資源向量nxxxX21決策向量三、非標

14、準型向標準型轉(zhuǎn)化三、非標準型向標準型轉(zhuǎn)化 標準型 例例1 maxZ= 3x1 +5 x2 x1 8 2x2 12 3x1 +4 x2 36 x1 0, x2 0S.t. x1 +x3 =8 2x2 +x4 = 12 3x1 +4 x2 +x5= 36 x1, x2 , x3 , x4 , x5 0 maxZ= 3x1 +5 x2 +0 x3 +0 x4+0 x5 minZ= x1 +2 x2 +3 x3 x1 +2 x2 + x35 2x1 +3 x2 + x36 -x1 - x2 - x3 -2 x1 0, x30 例例2 minZ= x1 +2 x2 -3 x3 x1 +2 x2 - x3

15、 5 2x1 +3 x2 - x3 6 -x1 - x2 + x3 -2 x1 0, x3 0 標準化標準化1S.t. 標準化標準化2 minZ= x1 +2 (x2-x 2) +3 x3 x1 +2 (x2-x 2) + x35 2x1 +3 (x2-x 2) + x36 - x1 - (x2-x 2) - x3 -2 x1, x2,x 2 , x3 0 標準化標準化3 minZ= x1 +2 (x2-x 2 ) +3 x3 x1 +2 (x2-x 2 ) + x35 2x1 +3 (x2-x 2 ) + x36 x1 + (x2-x 2 ) + x3 2 x1, x2, x 2, x3 0

16、 標準化標準化4 minZ= x1 +2 (x2-x 2) +3 x3 x1 +2 (x2-x 2) + x3+ x4 =5 2x1 +3 (x2-x 2) + x36 x1 + (x2-x 2 ) + x3 2 x1, x2, x 2, x3, x4 0 標準化標準化5 minZ= x1 +2 (x2-x 2) +3 x3 x1 +2 (x2-x 2) + x3+ x4 =5 2x1 +3 (x2-x 2) + x3 - x5 = 6 x1 + (x2-x 2 ) + x3 2 x1, x2, x 2, x3, x4 , x5 0 標準化標準化6 minZ= x1 +2 (x2-x 2) +

17、3 x3 x1 +2 (x2-x 2) + x3+ x4 =5 2x1 +3 (x2-x 2) + x3 - x5 = 6 x1 + (x2-x 2 ) - x3 + x6= 2 x1, x2, x 2, x3, x4 , x5 , x6 0 標準化標準化7 maxZ= -x1 -2 (x2-x 2) - 3x3+0 x4+0 x5+0 x6 x1 +2 (x2-x 2) + x3+ x4 =5 2x1 +3 (x2-x 2) + x3 - x5 = 6 x1 + (x2-x 2 ) - x3 + x6 = 2 x1, x2, x 2, x3, x4 , x5 , x6 0 可行解： 滿足約束

18、條件AX=b, X0的解。 最優(yōu)解： 使目標函數(shù)達到最大的可行解，稱為最優(yōu)解。 基 設(shè)A是約束方程組的mn維系數(shù)矩陣，其秩為m，B是矩陣A中的mm階非奇異子矩陣，則稱B是線性規(guī)劃問題的一個基。 mn，且m個方程線性無關(guān)，即矩陣A的秩為m；根據(jù)線性代數(shù)定理可知，nm，則方程組有多個解，這也正是線性規(guī)劃尋求最優(yōu)解的余地所在。 一、線性規(guī)劃解的概念一、線性規(guī)劃解的概念 1.4 線性規(guī)劃問題的解的概念線性規(guī)劃問題的解的概念 線性方程組的增廣矩陣 例例 maxZ= 3x1 +5 x2 +0 x3 +0 x4+0 x5 x1 +x3 =8 2x2 +x4 = 12 3x1 +4 x2 +x5= 36 x1

19、, x2 , x3 , x4 , x5 036101201800043020101Ax1x2x3x4x5 基矩陣： 系數(shù)矩陣A中任意m列所組成的m階非奇異子矩陣，稱為該線性規(guī)劃問題的一個基矩陣。 或稱為一個基，用B表示。 稱基矩陣的列為基向量，用Pj表示(j=1,2,m) 。100100043020101A的基矩陣的基矩陣B最多最多C53=10，如下：，如下：100010001x3x4 x5103010001x1x4 x5104012000 x2x4 x5130000011x3x1 x5140020001x3x2 x5300010101x3x4 x1400210001x3x4 x2043020

20、101x1x2 x5x1x2 x4043120001x1x2 x5143020001 基變量： 與基向量Pj相對應(yīng)的m個變量xj稱為基變量， 其余的m-n個變量為非基變量。 基解： 令所有非基變量等于零，對m個基變量所求的解 對應(yīng)一個特定的基矩陣能求得一組唯一解，這個對應(yīng)于基的解稱為基解。 結(jié)合圖解來看，基解是各約束方程及坐標軸之間交點的坐標。 100010001Bx3x4x5基變量是基變量是x3, x4, x5非基變量是非基變量是x1, x2令非基變量令非基變量x1=x2=0，得到一個基解，得到一個基解 x3=8，x4=12， x5=36 基可行解：滿足非負性約束的基解稱為基可行解。 可行基

21、：對應(yīng)于基可行解的基，稱為可行基。 最優(yōu)基：最優(yōu)解對應(yīng)的基矩陣，稱為最優(yōu)基。 可行解基解基可行解二、線性規(guī)劃的基本定理二、線性規(guī)劃的基本定理 線性規(guī)劃問題可以有無數(shù)個可行解，最優(yōu)解只可能在線性規(guī)劃問題可以有無數(shù)個可行解，最優(yōu)解只可能在頂點上達到，而有限個頂點對應(yīng)的是基可行解，故只頂點上達到，而有限個頂點對應(yīng)的是基可行解，故只要在有限個基可行解中尋求最優(yōu)解即可。要在有限個基可行解中尋求最優(yōu)解即可。 從一個頂點出發(fā)找到一個可行基，得到一組基可行解，從一個頂點出發(fā)找到一個可行基，得到一組基可行解，拿目標函數(shù)做尺度衡量一下看是否最優(yōu)。拿目標函數(shù)做尺度衡量一下看是否最優(yōu)。 如若不是，則向鄰近的頂點轉(zhuǎn)移，

22、換一個基再行求解、如若不是，則向鄰近的頂點轉(zhuǎn)移，換一個基再行求解、檢驗，如此迭代循環(huán)目標值逐步改善，直至求得最優(yōu)檢驗，如此迭代循環(huán)目標值逐步改善，直至求得最優(yōu)解。解。 三、線性規(guī)劃的解題思路三、線性規(guī)劃的解題思路 例maxz=2x1+3x2St:X1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5=12 Xi=0 1 2 1 0 0 A= 4 0 0 1 0 0 4 0 0 1令非基變量X4=X5=0，則可解出X1=4, X2=3, X3=-2所以得出基解 X1=（4，2，-2，0，0），但由于X30,所以X2是可行解，相應(yīng)的B2為可行基若用以上方法可枚舉出此線性規(guī)劃問題的基可行解

23、分別為X3(4,0,4,0,12)， X4(0,3,2,16,0)，X52，3，0，8，0和X64，2，0，0，4），將這些解代入目標函數(shù)，可知X6可使得Z最大，所以X6為最優(yōu)解2 單純形法單純形法 單純形法的思路：先找到一個初始可行基，求出這個基可行解，然后判斷該基可行解是否為最優(yōu)解，若是最優(yōu)解，則求解結(jié)束，若不是，則進行基變換，得到一個新的可行基，再進行判斷該基可行解是否為最優(yōu)解。每次基變換后的目標函數(shù)不斷增大，一直到找到最優(yōu)解為止。單純形法基本思路是否最優(yōu)解求最優(yōu)目標函數(shù)值是基變換,迭代否確定初始可行解2.1單純形法的原理例： maxz=2X1+3X2+0X3+0X4+0X5 st X1

24、+2X2+X3=8 4X1+X4=16 4X2+X5=12 Xj 0系數(shù)子矩陣 1 2 1 0 0A=（P1 P2 P3 P4 P5）= 4 0 01 0 0 4 0 0 1初始可行基 1 0 0 B1= 0 1 0 0 0 1（1）所以：X3=8-X1-2X2 X4=16-4X1 X5=12-4X2將此代入目標函數(shù)將此代入目標函數(shù)Z=2X1+3X2，令非基變量等于，令非基變量等于0，則得到一個基可行解則得到一個基可行解X0=（0 0 8 16 12），目標函），目標函數(shù)值等于數(shù)值等于0。但是從目標函數(shù)可知，因。但是從目標函數(shù)可知，因X1，X2的價的價值系數(shù)均大于值系數(shù)均大于0，當(dāng)，當(dāng)X1或或

25、X2由非基變量變成基變量由非基變量變成基變量時，目標函數(shù)就會增加，所以此解并非最優(yōu)解。時，目標函數(shù)就會增加，所以此解并非最優(yōu)解。將x2換入，x2換入后，需從X3,X4,X5中換出一個變量，并保證所有變量非負X3=8-2X2 X4=16X5=12-4X2當(dāng)X2增大時，要滿足X3，X4，X5 0，所以x2的最大只能取3，且此時x5為換出變量（2基變換 新基變量為X3，X4，X2），得X3=2-X1+0.5X5X4=16-4X1X2=3-0.25X5代入目標函數(shù)得Z=9+2X1-0.75X5因為x1的系數(shù)為正，依然不是最優(yōu)解，換入x1，再經(jīng)過迭代最后的最優(yōu)解4 2 0 0 4）2.2單純形法求解單純

26、形法求解（1初始基可行解的確定初始基可行解的確定a 直接觀察法直接觀察法b 構(gòu)造法構(gòu)造法方式，加松弛變量方式，加松弛變量方式方式,減松弛變量后加人工變量具體求解要用大法或減松弛變量后加人工變量具體求解要用大法或二階段法）二階段法）目的目的:使初始可行基為單位陣使初始可行基為單位陣,令非基變量等于零令非基變量等于零,因為因為b0,即可以得到初始基可行解即可以得到初始基可行解.（2最優(yōu)性檢驗與解的判最優(yōu)性檢驗與解的判別別四種情況四種情況:唯一最優(yōu)解唯一最優(yōu)解無窮多最優(yōu)解無窮多最優(yōu)解無界解無界解無可行解無可行解 一般情況下一般情況下,經(jīng)過迭代后經(jīng)過迭代后jnmjmiijijimiijnmjijiix

27、accbczmixabx)(), 2 , 1(1111z0j 對于對于 a.最優(yōu)解的判別定理最優(yōu)解的判別定理:假設(shè)假設(shè) 為對應(yīng)于基為對應(yīng)于基B的一個基可行解的一個基可行解,且對于一切且對于一切j=m+1,n有有j0,那么那么 為最優(yōu)解為最優(yōu)解.稱稱j為檢為檢驗數(shù)驗數(shù).21)0()0 , 0 ,(mbbbX)0(Xnmjjjxzz10 證明證明:因?qū)σ磺蟹腔兞康慕窍聵艘驅(qū)σ磺蟹腔兞康慕窍聵薺，均有均有0，顯然，對于任一可行解，顯然，對于任一可行解均有均有zz0,但基本可行解但基本可行解 能使等能使等式成立，故為最優(yōu)解式成立，故為最優(yōu)解)0(X)0(Xjb.無窮多最優(yōu)解的判別定理無窮多最優(yōu)解的

28、判別定理:假設(shè)假設(shè) 為一個基可行解為一個基可行解,且對于一切且對于一切j=m+1,n有有j0,又存在某個非基變量的檢驗數(shù)又存在某個非基變量的檢驗數(shù)m+k=0,則線性規(guī)劃問題有無窮多最優(yōu)解則線性規(guī)劃問題有無窮多最優(yōu)解21)0()0 , 0 ,(mbbbXc.無界解無有限最優(yōu)解判別定理無界解無有限最優(yōu)解判別定理假設(shè)假設(shè)為一基可行解，有一個為一基可行解，有一個m+k，并且對，并且對i=1,2,m有有ai,m+k0,那么該線性規(guī)劃問題具有無界解無最那么該線性規(guī)劃問題具有無界解無最優(yōu)解）優(yōu)解）21)0()0 , 0 ,(mbbbXd.無可行解無可行解約束條件相互矛盾，可行域為空集約束條件相互矛盾，可行域

29、為空集最終計算表中人工變量仍然為基變量最終計算表中人工變量仍然為基變量（3基變換基變換當(dāng)初始基可行解不是最優(yōu)解及不能判別無界時當(dāng)初始基可行解不是最優(yōu)解及不能判別無界時,需要找需要找一個新的基可行解一個新的基可行解,具體是從原可行解基中換一個列向具體是從原可行解基中換一個列向量量,得到一個新的可行基得到一個新的可行基,稱為基變換稱為基變換.基變換的關(guān)鍵是如何選擇換入變量和換出變量這兩個問基變換的關(guān)鍵是如何選擇換入變量和換出變量這兩個問題題.(原則和原則和原則原則)a.換入變量：當(dāng)換入變量：當(dāng)j0時取時取j中最大的所對應(yīng)的非基變量中最大的所對應(yīng)的非基變量xk 。b.換出變量：換出變量：=bi/ai

30、k(aik0)中最小的所對應(yīng)的中最小的所對應(yīng)的xl為換為換出變量。出變量。經(jīng)過基變換得到的解是基可行解經(jīng)過基變換得到的解是基可行解,目標函數(shù)值增加目標函數(shù)值增加（4迭代運算迭代運算將將xk和和xl進行對換，即把進行對換，即把Pk變?yōu)閱挝涣邢蛄咳∽優(yōu)閱挝涣邢蛄咳〈鶳l,可通過系數(shù)矩陣的增廣矩陣的初等變換可通過系數(shù)矩陣的增廣矩陣的初等變換來實現(xiàn)來實現(xiàn)將增廣矩陣的第將增廣矩陣的第l行除以行除以alk將將k列除列除alk變換為變換為1以外，其他都變成以外，其他都變成0。alk稱之為主元素，稱之為主元素，k列成為主元列，列成為主元列，l行稱為主行稱為主遠行。遠行。2.3 單純形表 單純形表，是對上節(jié)討

31、論的方法步驟進行具體化、規(guī)范化、表格化的結(jié)果。 CjC1C2CjCn比值CBXBbx1x2xjxnCB1xB1b1a11a12a1ja1n1CB2xB2b2a21a22a2ja2n2CBnxBnbmam1am2amjamnm檢驗數(shù)j-Z12jn將線性規(guī)劃問題化成標準型。找出或構(gòu)造一個m階單位矩陣作為初始可行基，建立初始單純形表。計算各非基變量xj的檢驗數(shù)j=Cj-CBPj ，若所有j0，則問題已得到最優(yōu)解，停止計算，否則轉(zhuǎn)入下步。在大于0的檢驗數(shù)中，若某個k所對應(yīng)的系數(shù)列向量Pk0，則此問題是無界解，停止計算，否則轉(zhuǎn)入下步。根據(jù)maxjj0=k原則，確定xk為換入變量(進基變量)，再按規(guī)則計算

32、：=minbi/aik| aik0=bl/ aik 確定xBl為換出變量。建立新的單純形表，此時基變量中xk取代了xBl的位置。以aik為主元素進行迭代，把xk所對應(yīng)的列向量變?yōu)閱挝涣邢蛄浚碼ik變?yōu)?，同列中其它元素為0，轉(zhuǎn)第 步。 單純形法的計算步驟單純形法的計算步驟 maxZ=3x1 +5 x2 +0 x3 +0 x4+0 x5 =0 x1 + x3 =8 2x2 + x4 =12 3x1 +4 x2 + x5=36 單純形法計算舉例單純形法計算舉例Cj比值CBXBb檢驗數(shù)jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=

33、636/4=9miijBjjaCCi1檢驗數(shù)j81010060101/2012300-21x3x2x5050-30300-5/208-4Cj比值CBXBb檢驗數(shù)jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9Cj比值CBXBb檢驗數(shù)jx1x2x3x4x53500081010060101/2012300-21x3x2x5050-30300-5/208-4檢驗數(shù)j40012/3-1/360101/204100-2/31/3x3x2x1053-42000-1/2-1最優(yōu)解最優(yōu)解 :X*=(4,6,4,0,0)T，Z*=4

34、2 最優(yōu)基 Cj35000比值CBXBbx1x2x3x4x50 x340012/3-1/35x260101/203x14100-2/31/3檢驗數(shù)j-42000-1/2-1340020101*Bx3 x2x1313200210313211*B 最優(yōu)基的逆最優(yōu)基的逆 最優(yōu)基和最優(yōu)基的逆最優(yōu)基和最優(yōu)基的逆又例又例Max z=2x1+3x2 x1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5=12 x1, x2, x3 ,x4,x50 此問題的最優(yōu)解為此問題的最優(yōu)解為:x1*=4, x2*=2, x5*=4, x3*= x4*= x1*=0, z*=24+32=14例Max z=2x1

35、+3x2 x1+2x2 8 4x1 16 4x2 12 x1, x2 0 例如例如 maxZ= 3x1 +2 x2 -2x1 + x2 2 x1 -3 x2 3 x1 , x2 0S.t. 標準化標準化 maxZ= 3x1 +2 x2 -2x1 + x2 + x3 =2 x1 -3 x2 + x4 =3 x1 , x2 , x3, x4 0Cj比值CBXBb檢驗數(shù)jx1x2x3x432002-211031-301x3x40003200-3檢驗數(shù)j80-512x3x103-31-301-90110-3 此時，檢驗數(shù)2=11 0，還沒有得到最優(yōu)解。 確定x2進基，但x2所在列的系數(shù)向量元素非正，無

36、界 值不存在，有進基變量但無離基變量。 用單純形法解題時，需要有一個單位矩陣作為初始基。 當(dāng)約束條件都是“”時，加入松弛變量就形成了初始基。 但實際存在“”或“”型的約束，沒有現(xiàn)成的單位矩陣。 采用人造基的辦法：人工構(gòu)造單位矩陣采用人造基的辦法：人工構(gòu)造單位矩陣 在沒有單位列向量的等式約束中加入人工變量，構(gòu)成原線在沒有單位列向量的等式約束中加入人工變量，構(gòu)成原線性規(guī)劃問題的伴隨問題，從而得到一個初始基。性規(guī)劃問題的伴隨問題，從而得到一個初始基。 人工變量是在等式中人為加進的，只有它等于人工變量是在等式中人為加進的，只有它等于0時，約束條時，約束條件才是它本來的意義。件才是它本來的意義。 處理方

37、法有兩種：處理方法有兩種： 大大M 法法 兩階段法兩階段法3.單純形法的進一步討論 沒有單位矩陣，不符合構(gòu)造初始基的條件，需加入人工變量 。 人工變量最終必須等于0才能保持原問題性質(zhì)不變。 為保證人工變量為0，在目標函數(shù)中令其系數(shù)為-M。 M為無限大的正數(shù)，這是一個懲罰項，倘若人工變量不為零，則目標函數(shù)就永遠達不到最優(yōu)，所以必須將人工變量逐步從基變量中替換出去。 如若到最終表中人工變量仍沒有置換出去，那么這個問題就沒有可行解，當(dāng)然亦無最優(yōu)解。 大大M法法 例如例如 maxZ= 3x1 - x2 -2 x3 3x1 + 2 x2 -3 x3 =6 x1 - 2 x2 + x3 =4 x1 , x

38、2 , x3 0S.t. 按大按大M法構(gòu)造人造基，引入人工變量法構(gòu)造人造基，引入人工變量x4 , x5 的輔助問題如的輔助問題如下：下： maxZ= 3x1 - x2 -2 x3 -M x4 -M x5 3x1 + 2 x2 -3 x3 + x4 =6 x1 - 2 x2 + x3 + x5 =4 x1 , x2 , x3 , x4 , x5 0Cj比值CBXBb檢驗數(shù)jx1x2x3x4x53-1-2-M-M632-31041-210100-2-2M-13+4M-10Mx4x5-M-M24miijBjjaCCi1Cj比值CBXBb檢驗數(shù)jx1x2x3x4x53-1-2-M-M632-31041

39、-21013+4M-1-2-2M00 x4x5-M-M24檢驗數(shù)j212/3-11/3020-8/32-1/310-1-4M/31+2M-3-8M/30 x1x53-M-1檢驗數(shù)j31-2/301/61/210-4/31-1/61/20-5/30-M-5/6-M-1/2x1x33-2用計算機處理數(shù)據(jù)時，只能用很大的數(shù)代替用計算機處理數(shù)據(jù)時，只能用很大的數(shù)代替M,M,可能造可能造成計算機上的錯誤，故多采用兩階段法。成計算機上的錯誤，故多采用兩階段法。 第一階段：第一階段： 在原線性規(guī)劃問題中加入人工變量，構(gòu)造如下模型：在原線性規(guī)劃問題中加入人工變量，構(gòu)造如下模型： 0 00min11111111

40、111mnmmnnmnmnnnnmnnxxbxxaxabxxaxaxxxxW兩階段法兩階段法 對上述模型求解單純形法），若對上述模型求解單純形法），若W=0,W=0,說明問題存在基本可行解，可以進行說明問題存在基本可行解，可以進行第二個階段；否則，原問題無可行解，停第二個階段；否則，原問題無可行解，停止運算。止運算。 第二階段：在第一階段的最終表中，第二階段：在第一階段的最終表中，去掉人工變量，將目標函數(shù)的系數(shù)換成原去掉人工變量，將目標函數(shù)的系數(shù)換成原問題的目標函數(shù)系數(shù)，作為第二階段計算問題的目標函數(shù)系數(shù)，作為第二階段計算的初始表用單純形法計算）。的初始表用單純形法計算）。單純形法補遺 進基變

41、量相持： 單純形法運算過程中，同時出現(xiàn)多個相同的j最大。 在符合要求的j(目標為max：j0，min：j0)中，選取下標最小的非基變量為換入變量； 離基變量相持： 單純形法運算過程中，同時出現(xiàn)多個相同的最小值。 繼續(xù)迭代，便有基變量為0，稱這種情況為退化解。 選取其中下標最大的基變量做為換出變量。 多重最優(yōu)解： 最優(yōu)單純形表中，存在非基變量的檢驗數(shù)j=0。 讓這個非基變量進基，繼續(xù)迭代，得另一個最優(yōu)解。 無界解： 大于0的檢驗數(shù)中，若某個k所對應(yīng)的系數(shù)列向量Pk0，則解無界。 無可行解： 最終表中存在人工變量是基變量。 4.線性規(guī)劃的運用解解 先看有多少種裁料方案，再進行組合和選擇。方案：先看

42、有多少種裁料方案，再進行組合和選擇。方案：套裁下料套裁下料 現(xiàn)要做一百套鋼管現(xiàn)要做一百套鋼管, 每套要長為每套要長為2.9m、2.1m和和1.5m的鋼管各的鋼管各一根。已知原料長一根。已知原料長7.4m，問應(yīng)如何下料，使用的原料最省。，問應(yīng)如何下料，使用的原料最省。 設(shè)用方案設(shè)用方案, ,分分別裁原料鋼管別裁原料鋼管x1,x2,.x5根根, 那那么：么：Min z= 0 x1+0.1 x2+0.2 x3+0.3x4+ 0.8x5x1+ 2x2 + x4 =100 2x3+2x4+x5 =100 3x1+x2 +2x3 +x5 =100 x1, x2, x3, x4, x5 0 例例 某工廠要用

43、三種原材料某工廠要用三種原材料C,P,HC,P,H混合調(diào)配出三種不同規(guī)混合調(diào)配出三種不同規(guī)格的產(chǎn)品格的產(chǎn)品A,B,DA,B,D。已知產(chǎn)品的規(guī)格要求、單價和原料的。已知產(chǎn)品的規(guī)格要求、單價和原料的供應(yīng)量、單價如下表。該廠應(yīng)如何安排生產(chǎn)，能使利潤供應(yīng)量、單價如下表。該廠應(yīng)如何安排生產(chǎn)，能使利潤最大？最大？產(chǎn)產(chǎn)品品名名規(guī)規(guī)格格要要求求單單價價A原原料料 C 不不少少于于 50%原原料料 P 不不超超過過 25%50 元/KGB原原料料 C 不不少少于于 25%原原料料 P 不不超超過過 50%35 元/KGD不不限限25 元/KG配料問題配料問題根據(jù)產(chǎn)品要求有：根據(jù)產(chǎn)品要求有： AC0.5A, AP

44、0.25A BC0.25B, BP0.5B AC+AP+AH=A BC+BP+BH=B根據(jù)原料供應(yīng)量有：根據(jù)原料供應(yīng)量有： AC+BC+DC100 AP+BP+DP100 AH+BH+DH60設(shè)設(shè)AC,AP,DH分別為分別為x1,x2,x9，有有Max z=50(x1+x2+x3)+35(x4+x5+x6) +25(x7+x8+x9) - 65(x1+x4+x7) - 25(x2+x5+x8) - 35(x3 +x6 +x9) x10.5(x1+ x2+ x3) x2 0.25(x1+ x2+ x3) x4 0.25(x4+ x5+ x6) x5 0.5(x4+ x5+ x6) x1+ x4+

45、 x7100 x2+ x5+ x8100 x3+ x6+ x960 xj0, j=1,2,3,4,5,6,7,8,9解：記產(chǎn)品解：記產(chǎn)品A A、B B、D D中中C C、P P、H H的含量分別為：的含量分別為：ACAC、APAP、AHAH、BCBC、BPBP、BHBH、DCDC、DPDP、DHDH。 例例 某單位有資金某單位有資金10萬元，在今后萬元，在今后5年內(nèi)可考慮下列投年內(nèi)可考慮下列投資項目，知：資項目，知： 項目項目A：從第：從第1到第到第4年每年初可投資，并于次年末年每年初可投資，并于次年末回收本利回收本利115%； 項目項目B：第：第3年初需要投資，到第年初需要投資，到第5年末回

46、收本利年末回收本利125%，但最大投資額不超過，但最大投資額不超過4萬元；萬元； 項目項目C：第：第2年初需要投資，到第年初需要投資，到第5年末能回收本利年末能回收本利140%，但最大投資額不超過，但最大投資額不超過3萬元；萬元； 項目項目D：5年內(nèi)每年初可購買公債，當(dāng)年末回收本利年內(nèi)每年初可購買公債，當(dāng)年末回收本利106%。 問它應(yīng)該如何安排每年的投資，使到問它應(yīng)該如何安排每年的投資，使到5年末擁有的年末擁有的資金最多？資金最多？投資計劃投資計劃 x2A+x2C+x2D=1.06x1D解：每年的投資額應(yīng)不超過手中的資金。由于項目解：每年的投資額應(yīng)不超過手中的資金。由于項目D每每年都可投資，且

47、當(dāng)年末就可收回。所以該單位每年必年都可投資，且當(dāng)年末就可收回。所以該單位每年必然把資金全部投出去，即投資額等于手中的資金數(shù)。然把資金全部投出去，即投資額等于手中的資金數(shù)。設(shè)第設(shè)第i年投資各項目的資金為年投資各項目的資金為xiA、xib、xiC、xiD ，數(shù)學(xué)模型為：數(shù)學(xué)模型為：Max z=1.15x4A+1.4x2C+1.25x3B+1.06x5D x1A+x1D=10 x3A+x3B+x3D=1.15x1A+1.06x2Dx4A+x4D=1.15x2A+1.06x3D x5D=1.15x3A+1.06x4DxiA,xib,xiC,xiD0例某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機和乘務(wù)人員

48、數(shù)如下： 設(shè)司機和乘務(wù)人員分別在各時間段一開始時上班，并連續(xù)工作八小時，問該公交線路怎樣安排司機和乘務(wù)人員，既能滿足工作需要，又配備最少司機和乘務(wù)人員?人力資源分配的問題人力資源分配的問題解：設(shè) xi 表示第i班次時開始上班的司機和乘務(wù)人員數(shù),這樣我們建立如下的數(shù)學(xué)模型。目標函數(shù)： Min x1 + x2 + x3 + x4 + x5 + x6 約束條件：s.t. x1 + x6 60 x1 + x2 70 x2 + x3 60 x3 + x4 50 x4 + x5 20 x5 + x6 30 x1,x2,x3,x4,x5,x6 0 例：明興公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過鑄造、例：明興

49、公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過鑄造、機加工和裝配三個車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，機加工和裝配三個車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如下表。問：公司為了獲得最大利潤，甲、乙、丙三種產(chǎn)品各如下表。問：公司為了獲得最大利潤，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外包協(xié)作各應(yīng)多少件？包協(xié)作各應(yīng)多少件？生產(chǎn)計劃生產(chǎn)計劃解：設(shè) x1,x2,x3 分別為三道工序都由本公司加工的甲、乙、丙三

50、種產(chǎn)品的件數(shù)， x4,x5 分別為由外協(xié)鑄造再由本公司機加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。 求 xi 的利潤：利潤 = 售價 - 各成本之和可得到 xii=1,2,3,4,5的利潤分別為15、10、7、13、9元。這樣我們建立如下的數(shù)學(xué)模型。目標函數(shù)： Max 15x1 + 10 x2 + 7x3 + 13x4 + 9x5 約束條件： s.t. 5x1 + 10 x2 + 7x3 8000 6x1 + 4x2 + 8x3 + 6x4 + 4x5 12000 3x1 + 2x2 + 2x3 + 3x4 + 2x5 10000 x1,x2,x3,x4,x5 0練習(xí)：某廠生產(chǎn)練習(xí)：某廠生產(chǎn)、三種產(chǎn)品，均要經(jīng)過三種產(chǎn)品，均要經(jīng)過A A、B B 兩道工序兩道工序加工。假設(shè)有兩種規(guī)格的設(shè)備加工。假設(shè)有兩種規(guī)格的設(shè)備A1A1、A2A2能完成能完成 A A 工序；有三種工序；有三種規(guī)格的設(shè)備規(guī)格的設(shè)備B1B1、B2B2、B3B3能完成能完成 B B 工序。工序?？稍诳稍贏 A、B B的任何規(guī)的任何規(guī)格的設(shè)備上加工；格的設(shè)備上加工； 可在任意規(guī)格的可在任意規(guī)格的A A設(shè)備上加工，但對設(shè)備上加工，但對B B工工序，只