1-1線性規(guī)劃概念與數(shù)學(xué)模型-wxp

1、12甲、乙產(chǎn)品每件獲利分別為2、3元，如何安排獲利最多？3 問題討論問題討論4121212232841 6. .41 20 ,1, 2jM a x Zxxxxxs txxj56一般形式一般形式 0,),(),(),(. .)(21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMinMax或7 8可行解：滿足所有約束條件的解可行解：滿足所有約束條件的解9 實(shí)施圖解法，以求出最優(yōu)生產(chǎn)計(jì)劃（實(shí)施圖解法，以求出最優(yōu)生產(chǎn)計(jì)劃（最優(yōu)解最優(yōu)解） 例例1 maxZ=2x1+3x2121212x +2x84x164x1

2、2 x ,x0s.t.工時(shí)工時(shí)原材料原材料10 由于線性規(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)量。的產(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)方案。11 每一個(gè)約束不等式在平面直角坐標(biāo)系中都每一個(gè)約束不等式在平面直角坐標(biāo)系中都

3、代表一個(gè)半平面，只要代表一個(gè)半平面，只要，然后，然后。 ? 以第一個(gè)約束條件（工時(shí)）以第一個(gè)約束條件（工時(shí)） x1+2 x2 8 為例為例 說明約束條件的圖解過程。說明約束條件的圖解過程。12 如果全部的勞動(dòng)工時(shí)都用來生產(chǎn)如果全部的勞動(dòng)工時(shí)都用來生產(chǎn)甲甲 產(chǎn)品而不生產(chǎn)產(chǎn)品而不生產(chǎn)乙產(chǎn)品，那么乙產(chǎn)品，那么甲甲產(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)得到約束

4、兩點(diǎn)得到約束 x1+2 x2 8 所代表的半平面所代表的半平面 的邊界的邊界: x1+2x2 8， 即直線即直線AB。12345678912345x1+2x2 = 8ABAB13 12345678912345EF4x2 = 124x1=16ABCDx1+4x2 = 801Q2Q3Q4Q14 令令 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ù)條，而且相互平

5、行，稱這樣的直線為。畫出畫出，比如令，比如令c0和和c=6，就能看出，就能看出 ， 用用這個(gè)方向。這個(gè)方向。 圖中兩條虛線圖中兩條虛線 l1和和l2就就 分別代表分別代表 目標(biāo)函數(shù)等值線目標(biāo)函數(shù)等值線 2x1+3x2=0 和和 2x1+3x2=6, 箭頭表示使兩種產(chǎn)品的總箭頭表示使兩種產(chǎn)品的總 利潤(rùn)遞增的方向。利潤(rùn)遞增的方向。12345678912345x1+2x2 = 8ABDC4x1=16l1l2l3FEBA4x1=1224,2Q15 的方向的方向目標(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 就是最

6、有利的產(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ī)劃模型的，16 17 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）18一般線性規(guī)劃解的幾種不同情形：一般線性規(guī)劃解的幾種不同情形：無窮多最優(yōu)解（多重最優(yōu)解）無窮多最優(yōu)解（多重最優(yōu)解）12121212m ax24x +2

7、x84x16. .4x12 x ,x0Zxxs t無界解無界解12121212m ax-2x +x4. .x2 x ,x0Zxxs tx19無可行解無可行解1212121212m 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 = 4202122（1）標(biāo)準(zhǔn)形式）標(biāo)準(zhǔn)形式 1 12211 11221121 1222221 12212. .(,1,2,),Max00nnnnnnmmmnnminZc xc xc xa xa xa xba

8、 xa xa xbstima xaxaxbx xbx 23111,2,. .01,2,njjjnijjijjMaxZc xa xbimstxjn24（3）向量）向量矩陣形式：矩陣形式：1. .0,1, 2.,njjjjM axC XP xbs txjn其中：其中：1212(,) ,( ,) ,TTjjjmjmPaaabb bb),(21ncccCTnxxxX),.,(2125（4）矩陣形式）矩陣形式. .0M axC XAXbs tX其中其中 : 11121212221200;00.0nnmmmnaaaaaaAaaa 2621kkkxxx27符號(hào)不受限制321321321321321,0,13

9、82310.32xxxxxxxxxxxxtsxxxMinZ討論：討論：如何下手？標(biāo)準(zhǔn)化過程排序如何下手？標(biāo)準(zhǔn)化過程排序 -課堂練習(xí)課堂練習(xí)128令令433xxx293012,.,nxxx可行解可行解：滿足滿足LP約束條件的解約束條件的解 稱為稱為L(zhǎng)P的可行解的可行解,其中使目標(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é)果包括兩部

10、分： 最優(yōu)解最優(yōu)解x x* *（列列向量）向量） 最優(yōu)值最優(yōu)值Z Zmaxmax（數(shù)值）（數(shù)值）31n基基 設(shè)設(shè)LP標(biāo)準(zhǔn)型中約束方程組系數(shù)矩陣標(biāo)準(zhǔn)型中約束方程組系數(shù)矩陣A是是mn階矩陣，階矩陣，秩秩為為m，B是是A中中mm階非奇異階非奇異子矩陣（子矩陣（|B|0），則稱），則稱B是是LP問題的一個(gè)基問題的一個(gè)基。123111,147111111,141747ABBB x1， x2， x3 （P1，P2，P3） 32n基向量基向量：設(shè)設(shè)B為為L(zhǎng)P問題的一個(gè)基，即問題的一個(gè)基，即 B=(Pr1, Pr2, Prm)。則稱線性獨(dú)立列向量。則稱線性獨(dú)立列向量Prj = (a1,rj, a2,rj, a

11、n,rj)T, j=1,2,m 為基向量。因此，一個(gè)基對(duì)應(yīng)為基向量。因此，一個(gè)基對(duì)應(yīng)m個(gè)個(gè)基向量。基向量。n基變量基變量,非基變量非基變量：與基向量與基向量Prj對(duì)應(yīng)的決策變對(duì)應(yīng)的決策變量量 xrj (j=1,2, m)稱基變量；其他稱基變量；其他n-m個(gè)決策變量個(gè)決策變量xrj (j=m+1,m+2, n)稱為非基變量。稱為非基變量。33基本解基本解 :設(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問

12、題的一問題的一個(gè)基本解個(gè)基本解.注意注意：可以看出可以看出,有一個(gè)基就有一個(gè)基本解，基本解有一個(gè)基就有一個(gè)基本解，基本解的個(gè)數(shù)等于基的個(gè)數(shù)，總是小于等于的個(gè)數(shù)等于基的個(gè)數(shù)，總是小于等于 。當(dāng)一個(gè)。當(dāng)一個(gè)基解中的非零分量小于基解中的非零分量小于m時(shí)，該基解是一個(gè)退化解。時(shí)，該基解是一個(gè)退化解。 mnC*12(,.,0,0,.,0)TmXxxx基本解：基可行解基可行解：滿足非負(fù)條件的基本解叫基可行解，其滿足非負(fù)條件的基本解叫基可行解，其對(duì)應(yīng)的基稱為對(duì)應(yīng)的基稱為可行基可行基?；究尚薪獾姆橇惴至烤鶠檎??；究尚薪獾姆橇惴至烤鶠檎至浚至康膫€(gè)數(shù)分量，分量的個(gè)數(shù)m。 34n解的關(guān)系解的關(guān)系可行解可行解

13、 基本基本 可行解可行解351212121212Max25422. .2,0Zxxxxxxstxxx x求解線性規(guī)劃問題：求解線性規(guī)劃問題：36 討論求取基本解的步驟：討論求取基本解的步驟：將線性規(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 x37 1)1)尋找基尋找基( (不超過不超過 個(gè)個(gè));); 2) 2)確定基變量與非基變量；確定基變量與非基變量； 例如，基變量例如，基變量( x3, x4, x5 ) 3) 3)令非基變量取值為令非

14、基變量取值為0 0； 令令x1=x2=0 4)( 4)(基變量基變量, , 非基變量非基變量) )構(gòu)成基本解。構(gòu)成基本解。 (0,0,4,2,2)(0,0,4,2,2)mnC 然后按照基本解的定義：然后按照基本解的定義： 38 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è)基本解39求得的基本解和圖解法對(duì)照，找出相應(yīng)的點(diǎn)。求得的基本解和圖解法對(duì)照，找出相應(yīng)的點(diǎn)。 為何為何紅點(diǎn)和綠點(diǎn)紅點(diǎn)和綠點(diǎn)是基本解卻不是基本可行解是基本解卻不是基本可行解?12343210X2X1x1-x2=2-