線性規(guī)劃概念和數(shù)學(xué)模型

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

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

3、量。的產(chǎn)量。 對(duì)約束條件加以圖解。對(duì)約束條件加以圖解。 畫出目標(biāo)函數(shù)等值線，結(jié)合目標(biāo)函畫出目標(biāo)函數(shù)等值線，結(jié)合目標(biāo)函數(shù)的要求求出最優(yōu)解最優(yōu)生產(chǎn)方案。數(shù)的要求求出最優(yōu)解最優(yōu)生產(chǎn)方案。線性規(guī)劃概念和數(shù)學(xué)模型 每一個(gè)約束不等式在平面直角坐標(biāo)系中都每一個(gè)約束不等式在平面直角坐標(biāo)系中都代表一個(gè)半平面，只要代表一個(gè)半平面，只要，然后，然后。 ? 以第一個(gè)約束條件（工時(shí)）以第一個(gè)約束條件（工時(shí)） x1+2 x2 8 為例為例 說明約束條件的圖解過程。說明約束條件的圖解過程。線性規(guī)劃概念和數(shù)學(xué)模型 如果全部的勞動(dòng)工時(shí)都用來生產(chǎn)如果全部的勞動(dòng)工時(shí)都用來生產(chǎn)甲甲 產(chǎn)品而不生產(chǎn)產(chǎn)品而不生產(chǎn)乙產(chǎn)品，那么乙產(chǎn)品，那么甲

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

5、性規(guī)劃概念和數(shù)學(xué)模型 令令 Z=2x1+3x2=c,其中其中，在圖中畫出，在圖中畫出直線直線 2x1+3x2=c,這條直線上的點(diǎn)即對(duì)應(yīng)著一個(gè)可行的生產(chǎn)方這條直線上的點(diǎn)即對(duì)應(yīng)著一個(gè)可行的生產(chǎn)方案，即使兩種產(chǎn)品的總利潤(rùn)達(dá)到案，即使兩種產(chǎn)品的總利潤(rùn)達(dá)到c。 這樣的直線有無數(shù)條，而且相互平行，稱這樣的直線為這樣的直線有無數(shù)條，而且相互平行，稱這樣的直線為。畫出畫出，比如令，比如令c0和和c=6，就能看出，就能看出 ， 用用這個(gè)方向。這個(gè)方向。 圖中兩條虛線圖中兩條虛線 l1和和l2就就 分別代表分別代表 目標(biāo)函數(shù)等值線目標(biāo)函數(shù)等值線 2x1+3x2=0 和和 2x1+3x2=6, 箭頭表示使兩種產(chǎn)品的

6、總箭頭表示使兩種產(chǎn)品的總 利潤(rùn)遞增的方向。利潤(rùn)遞增的方向。12345678912345x1+2x2 = 8ABDC4x1=16l1l2l3FEBA4x1=1224,2Q線性規(guī)劃概念和數(shù)學(xué)模型 的方向的方向目標(biāo)函數(shù)等值線，使其目標(biāo)函數(shù)等值線，使其, 點(diǎn)就是要求的最優(yōu)點(diǎn)，點(diǎn)就是要求的最優(yōu)點(diǎn)，它對(duì)應(yīng)的相應(yīng)坐標(biāo)它對(duì)應(yīng)的相應(yīng)坐標(biāo) x1=4,x2=2 就是最有利的產(chǎn)品就是最有利的產(chǎn)品組合，即生產(chǎn)組合，即生產(chǎn)甲甲產(chǎn)品產(chǎn)品4件件，乙乙產(chǎn)品產(chǎn)品2件能使兩種件能使兩種產(chǎn)品的總利潤(rùn)達(dá)到最大值產(chǎn)品的總利潤(rùn)達(dá)到最大值 Zmax=2 4+3 2=14(元元)，就是線性規(guī)劃模型的就是線性規(guī)劃模型的，線性規(guī)劃概念和數(shù)學(xué)模型

7、線性規(guī)劃概念和數(shù)學(xué)模型 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）線性規(guī)劃概念和數(shù)學(xué)模型一般線性規(guī)劃解的幾種不同情形：一般線性規(guī)劃解的幾種不同情形：無窮多最優(yōu)解（多重最優(yōu)解）無窮多最優(yōu)解（多重最優(yōu)解）12121212m ax24x +2x84x16. .4x12 x ,x0Zxxs t無界解無界解12121212m ax-2x +x4. .x2 x ,x0Zxxs tx線性規(guī)劃概念和數(shù)學(xué)模型無可行解無可行解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線性規(guī)劃概念和數(shù)學(xué)模型線性規(guī)劃概念和數(shù)學(xué)模型線性規(guī)劃概念和數(shù)學(xué)模型（1）標(biāo)準(zhǔn)形式）標(biāo)準(zhǔn)形式 1 12211 11221121 1222221 12212. .(,1,2,),Max00nnnnnnmmmnnminZc xc xc xa xa xa xba xa xa xbstima xaxaxbx xbx線性規(guī)劃概念和數(shù)學(xué)模型111,2,. .01,2,njjjnijjijjM

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

10、xtsxxxMinZ討論：討論：如何下手？標(biāo)準(zhǔn)化過程排序如何下手？標(biāo)準(zhǔn)化過程排序 -課堂練習(xí)課堂練習(xí)1線性規(guī)劃概念和數(shù)學(xué)模型令令433xxx線性規(guī)劃概念和數(shù)學(xué)模型0,1)(38)(2310)(. .00)(3265432143216432154321654321xxxxxxxxxxxxxxxxxxxxtsxxxxxxZMax0,1382310. .32654321432164321543214321xxxxxxxxxxxxxxxxxxxxtsxxxxZMax線性規(guī)劃概念和數(shù)學(xué)模型線性規(guī)劃概念和數(shù)學(xué)模型12,.,nxxx可行解可行解：滿足滿足LP約束條件的解約束條件的解 稱為稱為L(zhǎng)P的可行解的可

11、行解,其中使目標(biāo)函數(shù)達(dá)到最大（或最?。┲档目善渲惺鼓繕?biāo)函數(shù)達(dá)到最大（或最小）值的可行解為行解為最優(yōu)解最優(yōu)解。可行域可行域：所有可行解的集合。所有可行解的集合。 最優(yōu)值最優(yōu)值：與與LP問題最優(yōu)解問題最優(yōu)解x*對(duì)應(yīng)的目標(biāo)函數(shù)的取值對(duì)應(yīng)的目標(biāo)函數(shù)的取值Zmax叫最優(yōu)值。叫最優(yōu)值。 注意注意：LPLP問題求解結(jié)果包括兩部分：?jiǎn)栴}求解結(jié)果包括兩部分： 最優(yōu)解最優(yōu)解x x* *（列列向量）向量） 最優(yōu)值最優(yōu)值Z Zmaxmax（數(shù)值）（數(shù)值）線性規(guī)劃概念和數(shù)學(xué)模型n基基 設(shè)設(shè)LP標(biāo)準(zhǔn)型中約束方程組系數(shù)矩陣標(biāo)準(zhǔn)型中約束方程組系數(shù)矩陣A是是mn階矩陣，秩為階矩陣，秩為m，B是是A中中mm階非奇異階非奇異子矩陣

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

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

14、基解中的非零分量小于解中的非零分量小于m時(shí)，該基解是一個(gè)退化解。時(shí)，該基解是一個(gè)退化解。 mnC*12(,.,0,0,.,0)TmXxxx基本解：基可行解：基可行解：滿足非負(fù)條件的基本解叫基可行解，其滿足非負(fù)條件的基本解叫基可行解，其對(duì)應(yīng)的基稱為可行基?；究尚薪獾姆橇惴至烤鶠檎龑?duì)應(yīng)的基稱為可行基。基本可行解的非零分量均為正分量，分量的個(gè)數(shù)分量，分量的個(gè)數(shù)m。 線性規(guī)劃概念和數(shù)學(xué)模型n解的關(guān)系解的關(guān)系可行解可行解 基本基本 可行解可行解線性規(guī)劃概念和數(shù)學(xué)模型1212121212Max25422. .2,0Zxxxxxxstxxx x求解線性規(guī)劃問題：求解線性規(guī)劃問題：線性規(guī)劃概念和數(shù)學(xué)模型 討

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

16、0,4,2,2)(0,0,4,2,2)mnC 然后按照基本解的定義：然后按照基本解的定義： 線性規(guī)劃概念和數(shù)學(xué)模型 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.對(duì)于上例對(duì)于上例,共有共有10個(gè)基本解個(gè)基本解線性規(guī)劃概念和數(shù)學(xué)模型求得的基本解和圖解法對(duì)照，找出相應(yīng)的點(diǎn)。求得的基本解和圖解法對(duì)照，找出相應(yīng)的點(diǎn)。 為何為何紅點(diǎn)和綠點(diǎn)紅點(diǎn)和綠點(diǎn)是基本解卻不是基本可行解是基本解卻不是基本可行解?12343210X2X1x1-x2=2