1、線性規劃概念和數學模型線性規劃概念和數學模型甲乙設備128臺時原材料A4016千克原材料B0412千克甲、乙產品每件獲利分別為2、3元，如何安排獲利最多？線性規劃概念和數學模型 問題討論問題討論線性規劃概念和數學模型121212232841 6. .41 20 ,1, 2jM a x Zxxxxxs txxj線性規劃概念和數學模型線性規劃概念和數學模型一般形式一般形式 0,),(),(),(. .)(21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMinMax或線性規劃概念和數學模型 線性規劃概念和

2、數學模型可行解：滿足所有約束條件的解可行解：滿足所有約束條件的解線性規劃概念和數學模型 實施圖解法，以求出最優生產計劃（最優解）實施圖解法，以求出最優生產計劃（最優解） 例例1 maxZ=2x1+3x2121212x +2x84x164x12 x ,x0s.t.工時工時原材料原材料線性規劃概念和數學模型 由于線性規劃模型中只有兩個決策變量，由于線性規劃模型中只有兩個決策變量，因此只需建立平面直角坐標系就可進行圖解因此只需建立平面直角坐標系就可進行圖解.建立平面直角坐標系，標出建立平面直角坐標系，標出, 和和。 用用x1軸表示產品軸表示產品甲甲的產量，用的產量，用x2軸表示產軸表示產品品乙乙的產

3、量。的產量。 對約束條件加以圖解。對約束條件加以圖解。 畫出目標函數等值線，結合目標函畫出目標函數等值線，結合目標函數的要求求出最優解最優生產方案。數的要求求出最優解最優生產方案。線性規劃概念和數學模型 每一個約束不等式在平面直角坐標系中都每一個約束不等式在平面直角坐標系中都代表一個半平面，只要代表一個半平面，只要，然后，然后。 ? 以第一個約束條件（工時）以第一個約束條件（工時） x1+2 x2 8 為例為例 說明約束條件的圖解過程。說明約束條件的圖解過程。線性規劃概念和數學模型 如果全部的勞動工時都用來生產如果全部的勞動工時都用來生產甲甲 產品而不生產產品而不生產乙產品，那么乙產品，那么甲

4、甲產品的最大可能產量為產品的最大可能產量為8噸，計算噸，計算過程為：過程為： x1+20 8 x1 8 這個結果對應著下圖中的點這個結果對應著下圖中的點B(8,0),同樣我們可同樣我們可以找到以找到B產品最大可能生產量對應的點產品最大可能生產量對應的點A(0,4)。連接。連接A、B兩點得到約束兩點得到約束 x1+2 x2 8 所代表的半平面所代表的半平面 的邊界的邊界: x1+2x2 8， 即直線即直線AB。12345678912345x1+2x2 = 8ABAB線性規劃概念和數學模型 12345678912345EF4x2 = 124x1=16ABCDx1+4x2 = 801Q2Q3Q4Q線

5、性規劃概念和數學模型 令令 Z=2x1+3x2=c,其中其中，在圖中畫出，在圖中畫出直線直線 2x1+3x2=c,這條直線上的點即對應著一個可行的生產方這條直線上的點即對應著一個可行的生產方案，即使兩種產品的總利潤達到案，即使兩種產品的總利潤達到c。 這樣的直線有無數條，而且相互平行，稱這樣的直線為這樣的直線有無數條，而且相互平行，稱這樣的直線為。畫出畫出，比如令，比如令c0和和c=6，就能看出，就能看出 ， 用用這個方向。這個方向。 圖中兩條虛線圖中兩條虛線 l1和和l2就就 分別代表分別代表 目標函數等值線目標函數等值線 2x1+3x2=0 和和 2x1+3x2=6, 箭頭表示使兩種產品的

6、總箭頭表示使兩種產品的總 利潤遞增的方向。利潤遞增的方向。12345678912345x1+2x2 = 8ABDC4x1=16l1l2l3FEBA4x1=1224,2Q線性規劃概念和數學模型 的方向的方向目標函數等值線，使其目標函數等值線，使其, 點就是要求的最優點，點就是要求的最優點，它對應的相應坐標它對應的相應坐標 x1=4,x2=2 就是最有利的產品就是最有利的產品組合，即生產組合，即生產甲甲產品產品4件件，乙乙產品產品2件能使兩種件能使兩種產品的總利潤達到最大值產品的總利潤達到最大值 Zmax=2 4+3 2=14(元元)，就是線性規劃模型的就是線性規劃模型的，線性規劃概念和數學模型

7、線性規劃概念和數學模型 0 1 2 3 4 5 6 7 8 9 x1 5 4 3 2 1x2（8，0）C=6（0，4）C=012121212m ax23x +2x84x16. .4x12 x ,x0Zxxs ts.t.Q2（4，2）線性規劃概念和數學模型一般線性規劃解的幾種不同情形：一般線性規劃解的幾種不同情形：無窮多最優解（多重最優解）無窮多最優解（多重最優解）12121212m ax24x +2x84x16. .4x12 x ,x0Zxxs t無界解無界解12121212m ax-2x +x4. .x2 x ,x0Zxxs tx線性規劃概念和數學模型無可行解無可行解1212121212m

8、ax24x +2x84x16. .4x1224 x ,x0Zxxs txx 0 1 2 3 4 5 6 7 8 9 x1 5 4 3 2 1x2-2 -14x1=124x1=16x1+2x2 = 8-2x1+x2 = 4線性規劃概念和數學模型線性規劃概念和數學模型線性規劃概念和數學模型（1）標準形式）標準形式 1 12211 11221121 1222221 12212. .(,1,2,),Max00nnnnnnmmmnnminZc xc xc xa xa xa xba xa xa xbstima xaxaxbx xbx線性規劃概念和數學模型111,2,. .01,2,njjjnijjijjM

9、axZc xa xbimstxjn線性規劃概念和數學模型（3）向量）向量矩陣形式：矩陣形式：1. .0,1, 2.,njjjjM axC XP xbs txjn其中：其中：1212(,) ,( ,) ,TTjjjmjmPaaabb bb),(21ncccCTnxxxX),.,(21線性規劃概念和數學模型（4）矩陣形式）矩陣形式. .0M axC XAXbs tX其中其中 : 11121212221200;00.0nnmmmnaaaaaaAaaa 線性規劃概念和數學模型21kkkxxx線性規劃概念和數學模型符號不受限制321321321321321,0,1382310.32xxxxxxxxxxx

10、xtsxxxMinZ討論：討論：如何下手？標準化過程排序如何下手？標準化過程排序 -課堂練習課堂練習1線性規劃概念和數學模型令令433xxx線性規劃概念和數學模型0,1)(38)(2310)(. .00)(3265432143216432154321654321xxxxxxxxxxxxxxxxxxxxtsxxxxxxZMax0,1382310. .32654321432164321543214321xxxxxxxxxxxxxxxxxxxxtsxxxxZMax線性規劃概念和數學模型線性規劃概念和數學模型12,.,nxxx可行解可行解：滿足滿足LP約束條件的解約束條件的解 稱為稱為LP的可行解的可

11、行解,其中使目標函數達到最大（或最小）值的可其中使目標函數達到最大（或最?。┲档目尚薪鉃樾薪鉃樽顑灲庾顑灲??？尚杏蚩尚杏颍核锌尚薪獾募?。所有可行解的集合。 最優值最優值：與與LP問題最優解問題最優解x*對應的目標函數的取值對應的目標函數的取值Zmax叫最優值。叫最優值。 注意注意：LPLP問題求解結果包括兩部分：問題求解結果包括兩部分： 最優解最優解x x* *（列列向量）向量） 最優值最優值Z Zmaxmax（數值）（數值）線性規劃概念和數學模型n基基 設設LP標準型中約束方程組系數矩陣標準型中約束方程組系數矩陣A是是mn階矩陣，秩為階矩陣，秩為m，B是是A中中mm階非奇異階非奇異子矩陣

12、（子矩陣（|B|0），則稱），則稱B是是LP問題的一個基問題的一個基。123111,147111111,141747ABBB x1， x2， x3 （P1，P2，P3） 線性規劃概念和數學模型n基向量：基向量：設設B為為LP問題的一個基，即問題的一個基，即 B=(Pr1, Pr2, Prm)。則稱線性獨立列向量。則稱線性獨立列向量Prj = (a1,rj, a2,rj, an,rj)T, j=1,2,m 為基向量。因此，一個基對應為基向量。因此，一個基對應m個個基向量?；蛄?。n基變量基變量,非基變量：非基變量：與基向量與基向量Prj對應的決策變對應的決策變量量 xrj (j=1,2, m)稱

13、基變量；其他稱基變量；其他n-m個決策變量個決策變量xrj (j=m+1,m+2, n)稱為非基變量。稱為非基變量。線性規劃概念和數學模型基本解基本解 :設設B是是LP問題的一個基，令與問題的一個基，令與B的列不相對的列不相對應的應的n-m個決策變量個決策變量(即非基變量即非基變量)等于等于 0，對應方程組，對應方程組的解稱為方程組的解稱為方程組AX=b關于基關于基B的解，也叫的解，也叫LP問題的一問題的一個基本解個基本解.注意注意：可以看出可以看出,有一個基就有一個基本解，基本解有一個基就有一個基本解，基本解的個數等于基的個數，總是小于等于的個數等于基的個數，總是小于等于 。當一個基。當一個

14、基解中的非零分量小于解中的非零分量小于m時，該基解是一個退化解。時，該基解是一個退化解。 mnC*12(,.,0,0,.,0)TmXxxx基本解：基可行解：基可行解：滿足非負條件的基本解叫基可行解，其滿足非負條件的基本解叫基可行解，其對應的基稱為可行基?；究尚薪獾姆橇惴至烤鶠檎龑幕Q為可行基?；究尚薪獾姆橇惴至烤鶠檎至?，分量的個數分量，分量的個數m。 線性規劃概念和數學模型n解的關系解的關系可行解可行解 基本基本 可行解可行解線性規劃概念和數學模型1212121212Max25422. .2,0Zxxxxxxstxxx x求解線性規劃問題：求解線性規劃問題：線性規劃概念和數學模型 討

15、論求取基本解的步驟：討論求取基本解的步驟：將線性規劃標準化；將線性規劃標準化； s.t. AX=b 111 0 0A1201 011 0 0 1 1212312412512345Max25422. .2,0Zxxxxxxxxstxxxx x x x x線性規劃概念和數學模型 1)1)尋找基尋找基( (不超過不超過 個個);); 2) 2)確定基變量與非基變量；確定基變量與非基變量； 例如，基變量例如，基變量( x3, x4, x5 ) 3) 3)令非基變量取值為令非基變量取值為0 0； 令令x1=x2=0 4)( 4)(基變量基變量, , 非基變量非基變量) )構成基本解。構成基本解。 (0,

16、0,4,2,2)(0,0,4,2,2)mnC 然后按照基本解的定義：然后按照基本解的定義： 線性規劃概念和數學模型 H(6,4,-6,0,0)T, C(3,1,0,3,0)T, B(2,2,0,0,2)T, D(2,0,2,4,0)T, F(-2,0,6,0,4)T, I(4,0,0,6,-2)T, E(0,-2,6,6,0)T, A(0,1,3,0,3)T, G(0,4,0,-8,6)T, O(0,0,4,2,2)T.對于上例對于上例,共有共有10個基本解個基本解線性規劃概念和數學模型求得的基本解和圖解法對照，找出相應的點。求得的基本解和圖解法對照，找出相應的點。 為何為何紅點和綠點紅點和綠點是基本解卻不是基本可行解是基本解卻不是基本可行解?12343210X2X1x1-x2=2