第二章線性規(guī)劃

1、1第二章第二章 線性規(guī)劃線性規(guī)劃12LPLPLPMkarmark ？條件（）數(shù)學(xué)模型（ ）各種解的概念：可行解（重點(diǎn)）基本概念 基本解（難點(diǎn)）基本可行解（重點(diǎn)）最優(yōu)解基本最優(yōu)解解的基本性質(zhì)：四個(gè)主要定理圖解法實(shí)際問(wèn)題模型大法基本方法 單純形法（原始單純形法、人工變量法）兩階段法對(duì)偶單純形法（求解）前提？步驟？修正單純形法對(duì)偶理論進(jìn)一步討論靈敏度分析參數(shù)規(guī)劃算法復(fù)雜性問(wèn)題哈奇揚(yáng)算法、arLPLPLP算法整數(shù)運(yùn)輸問(wèn)題特殊多目標(biāo)2第二章第二章 線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型 線性規(guī)劃 Linear Programming LP 規(guī)劃論中的靜態(tài)規(guī)劃 在有限資源的條件下，合理分配和利用資源，以期取

2、得最佳效益的優(yōu)化方法。 求解方法： 圖解法 單純形解法 3第一部分第一部分 線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型第二章第二章 線性規(guī)劃線性規(guī)劃第一節(jié)第一節(jié) 線性規(guī)劃一般模型線性規(guī)劃一般模型第二節(jié)第二節(jié) 線性規(guī)劃的圖解法線性規(guī)劃的圖解法第三節(jié)第三節(jié) 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型第四節(jié)第四節(jié) 線性規(guī)劃解的概念線性規(guī)劃解的概念第二部分第二部分 線性規(guī)劃的單純形法線性規(guī)劃的單純形法Homework4 工廠工廠 1 工廠工廠 2 工廠工廠 3 工廠工廠 4 庫(kù)存庫(kù)存 倉(cāng)庫(kù)倉(cāng)庫(kù) A 2 1 3 5 50 倉(cāng)庫(kù)倉(cāng)庫(kù) B 2 2 4 1 30 倉(cāng)庫(kù)倉(cāng)庫(kù) C 1 4 3 2 70 需求量需求量 40 50

3、25 35 現(xiàn)有三個(gè)倉(cāng)庫(kù)（A,B,C）的產(chǎn)品運(yùn)往四個(gè)紡織廠。運(yùn)費(fèi)情況如下： 問(wèn)應(yīng)當(dāng)怎樣調(diào)運(yùn)使運(yùn)費(fèi)最??？問(wèn)應(yīng)當(dāng)怎樣調(diào)運(yùn)使運(yùn)費(fèi)最??？5一、線性規(guī)劃問(wèn)題的三要素一、線性規(guī)劃問(wèn)題的三要素 決策變量決策變量 決策問(wèn)題待定的量值稱(chēng)為決策變量。 決策變量的取值要求非負(fù)非負(fù)。 約束條件約束條件 任何問(wèn)題都是限定在一定的條件下求解，把各種限制條件表示為一組等式或不等式，稱(chēng)之為約束條件約束條件。 約束條件是決策方案可行的保障。 LP的約束條件，都是決策變量的線性函數(shù)線性函數(shù)。 目標(biāo)函數(shù)目標(biāo)函數(shù) 衡量決策方案優(yōu)劣的準(zhǔn)則，如時(shí)間最省、利潤(rùn)最大、成本最低。 有的目標(biāo)要實(shí)現(xiàn)極大極大，有的則要求極小極小。 目標(biāo)函數(shù)是決策變

4、量的線性函數(shù)線性函數(shù)。第一節(jié)第一節(jié) 線性規(guī)劃一般模型線性規(guī)劃一般模型6二、線性規(guī)劃的定義二、線性規(guī)劃的定義第一節(jié)第一節(jié) 線性規(guī)劃一般模型線性規(guī)劃一般模型7 某飲料公司在國(guó)內(nèi)有三個(gè)生產(chǎn)廠，分布在城市某飲料公司在國(guó)內(nèi)有三個(gè)生產(chǎn)廠，分布在城市A1、A2、A3,其一級(jí)承銷(xiāo)商有其一級(jí)承銷(xiāo)商有4個(gè)，分布在城市個(gè)，分布在城市B1、B2、B3、B4，已知各廠的產(chǎn)量、各承銷(xiāo)商的銷(xiāo)售量及從已知各廠的產(chǎn)量、各承銷(xiāo)商的銷(xiāo)售量及從Ai到到Bj的每的每噸飲料運(yùn)費(fèi)為噸飲料運(yùn)費(fèi)為Cij，為發(fā)揮集團(tuán)優(yōu)勢(shì)，公司要統(tǒng)一籌劃，為發(fā)揮集團(tuán)優(yōu)勢(shì)，公司要統(tǒng)一籌劃運(yùn)銷(xiāo)問(wèn)題，求運(yùn)費(fèi)最小的調(diào)運(yùn)方案。運(yùn)銷(xiāo)問(wèn)題，求運(yùn)費(fèi)最小的調(diào)運(yùn)方案。 銷(xiāo)地銷(xiāo)地產(chǎn)地

5、產(chǎn)地B1 B2 B3 B4產(chǎn)量產(chǎn)量A1A2A3 6 3 2 5 7 5 8 4 3 2 9 7523銷(xiāo)量銷(xiāo)量 2 3 1 4第一節(jié)第一節(jié) 線性規(guī)劃一般模型線性規(guī)劃一般模型二、線性規(guī)劃模型的構(gòu)建二、線性規(guī)劃模型的構(gòu)建8。 決策的是調(diào)運(yùn)量，因此決策變量為：從Ai到Bj的運(yùn)輸量為xij，。運(yùn)費(fèi)最小的目標(biāo)函數(shù)為minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34 。產(chǎn)量之和等于銷(xiāo)量之和,故要滿足：x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34 =3 銷(xiāo)售平衡條件銷(xiāo)售平衡條件x

6、11+x21+x31=2x12+x22+x32=3x13+x23+x33=1x14+x24+x34=4 供應(yīng)平衡條件供應(yīng)平衡條件 非負(fù)性約束非負(fù)性約束 xij0 (i=1,2,3；j=1,2,3,4) 第一節(jié)第一節(jié) 線性規(guī)劃一般模型線性規(guī)劃一般模型9minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34 綜上所述，該問(wèn)題的數(shù)學(xué)模型表示為綜上所述，該問(wèn)題的數(shù)學(xué)模型表示為 x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34 =3x11+x21+x31=2x12+x22+x32=

7、3x13+x23+x33=1x14+x24+x34=4xij0 (i=1,2,3；j=1,2,3,4) s.t.第一節(jié)第一節(jié) 線性規(guī)劃一般模型線性規(guī)劃一般模型subject to10 某廠生產(chǎn)兩種產(chǎn)品，需要三種資源，已知各產(chǎn)品的利潤(rùn)、各資源的限量和各產(chǎn)品的資源消耗系數(shù)如下表：產(chǎn)品A產(chǎn)品B資源限量勞動(dòng)力設(shè) 備原材料9434510360200300利潤(rùn)元/kg70120第一節(jié)第一節(jié) 線性規(guī)劃一般模型線性規(guī)劃一般模型11 問(wèn)題：如何安排生產(chǎn)計(jì)劃，使得獲利最多？ 步驟：1、確定決策變量：設(shè)生產(chǎn)A產(chǎn)品x1 kg；B產(chǎn)品x2 kg2、確定目標(biāo)函數(shù)：maxZ=70X1+120X23、確定約束條件：勞動(dòng)力約束

8、 9X1+4X2360 設(shè)備約束 4X1+5X2 200 原材料約束3X1+10X2 300 非負(fù)性約束X10 X20第一節(jié)第一節(jié) 線性規(guī)劃一般模型線性規(guī)劃一般模型12 用一組用一組非負(fù)決策變量非負(fù)決策變量表示一個(gè)決策問(wèn)題，表示一個(gè)決策問(wèn)題， 存在一定的等式或不等式的存在一定的等式或不等式的線性約束條件線性約束條件， 有一個(gè)希望達(dá)到的目標(biāo)，可表示成決策變量的有一個(gè)希望達(dá)到的目標(biāo)，可表示成決策變量的線線性函數(shù)性函數(shù)?？赡苁亲畲蠡部赡苁亲钚』??？赡苁亲畲蠡?，也可能是最小化。 線性規(guī)劃一般模型的代數(shù)式線性規(guī)劃一般模型的代數(shù)式 為：為：四、線性規(guī)劃的一般模型四、線性規(guī)劃的一般模型 max(min)

9、Z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn (,)b1a21x1+a22x2+a2nxn (,)b2 am1x1+am2x2+amnxn(,)bmx1,x2,xn ()0第一節(jié)第一節(jié) 線性規(guī)劃一般模型線性規(guī)劃一般模型13 用圖示的方法來(lái)求解線性規(guī)劃問(wèn)題。 一個(gè)二維的線性規(guī)劃問(wèn)題，可以在平面圖上求解，三維的線性規(guī)劃則要在立體圖上求解，而維數(shù)再高以后就不能圖示了。一、圖解法的基本步驟一、圖解法的基本步驟第二節(jié)第二節(jié) LP問(wèn)題的圖解法問(wèn)題的圖解法(1) 可行域的確定可行解(2) 最優(yōu)解141. 可行域的確定可行域的確定 例例3的數(shù)學(xué)模型為的數(shù)學(xué)模型為 maxZ= 3x1 +

10、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)(含邊界含邊界)的任意一點(diǎn)的任意一點(diǎn) (x1，x2) 都是滿足所有都是滿足所有約束條件的一個(gè)解，稱(chēng)之可行解約束條件的一個(gè)解，稱(chēng)之可行解 。 滿足所有約束條件的解的集合，稱(chēng)之為可行域。即所有約束滿足所有約束條件的解的集合，稱(chēng)之為可行域。即所有約束條件共同圍城的區(qū)域。條件共同圍城的區(qū)域。第二節(jié)第二節(jié) LP問(wèn)題的圖解法問(wèn)題的圖解法152. 最優(yōu)解的確定最優(yōu)解的確定Z=30Z=42Z=15 目標(biāo)函數(shù)目標(biāo)函數(shù) Z= 3

11、x1 +5 x2 代表以代表以Z為參數(shù)的一族為參數(shù)的一族平行線平行線。x1 =82x2 =123x1 +4 x2 =36x1x24812369 等值線：位于同一直線上的點(diǎn)的目標(biāo)函數(shù)值相同。等值線：位于同一直線上的點(diǎn)的目標(biāo)函數(shù)值相同。 最優(yōu)解：可行解中使目標(biāo)函數(shù)最優(yōu)最優(yōu)解：可行解中使目標(biāo)函數(shù)最優(yōu)(極大或極小極大或極小)的解的解第二節(jié)第二節(jié) LP問(wèn)題的圖解法問(wèn)題的圖解法?16 由線性不等式組成的可行域是凸集(凸集的定義是：集合內(nèi)部任意兩點(diǎn)連線上的點(diǎn)都屬于這個(gè)集合)。 可行域有有限個(gè)頂點(diǎn)。設(shè)規(guī)劃問(wèn)題有n個(gè)變量，m個(gè)約束，則頂點(diǎn)的個(gè)數(shù)不多于Cnm個(gè)。 目標(biāo)函數(shù)最優(yōu)值（如果存在）一定在可行域的邊界達(dá)到，

12、而不可能在其內(nèi)部。二、說(shuō)明二、說(shuō)明第二節(jié)第二節(jié) LP問(wèn)題的圖解法問(wèn)題的圖解法17 例: 求解下列線性規(guī)劃問(wèn)題 MaxZ=4X1-3X2 S.T. X1+2X210 X16 X24 X11 X1,X20第二節(jié)第二節(jié) LP問(wèn)題的圖解法問(wèn)題的圖解法18X1X1=1X1=6X2=4X2X1+2X2=10ABCDE4X1-3X2=0 MAXZ=4X1-3X2 S.T. X1+2X210 X16 X24 X11 X1,X20X2 0X1 019第二節(jié)第二節(jié) LP問(wèn)題的圖解法問(wèn)題的圖解法 唯一最優(yōu)解唯一最優(yōu)解：只有一個(gè)最優(yōu)點(diǎn)。 多重最優(yōu)解多重最優(yōu)解：無(wú)窮多個(gè)最優(yōu)解。若在兩個(gè)相鄰頂點(diǎn)相鄰頂點(diǎn)同時(shí)得到最優(yōu)解，則

13、它們連線上的每一點(diǎn)都是最優(yōu)解。 無(wú)界解無(wú)界解：線性規(guī)劃問(wèn)題的可行域無(wú)界，使目標(biāo)函數(shù)無(wú)限增大而無(wú)界。（缺乏必要的約束條件）。 無(wú)可行解無(wú)可行解：若約束條件相互矛盾，則可行域?yàn)榭占?。二、解的可能性二、解的可能?0X1X1=1X1=6X2=4X2X1+2X2=10ABCDE4X1-3X2=0 MAXZ=4X1-3X2 S.T. X1+2X210 X16 X24 X11 X1,X20唯一的最優(yōu)解唯一的最優(yōu)解X1 0X2 021X1X1=1X1=6X2=4X2X1+2X2=10ABCDE MAXZ=2X1+4X2 S.T. X1+2X210 X16 X24 X11 X1,X202X1+4X2=存在無(wú)窮

14、多解存在無(wú)窮多解 MAXZ=4X1-3X2 S.T. X1+2X210 X16 X24 X11 X1,X20X1 0X2 022X1X1=1X1=6X2=4X2X1+2X2=0ADE4X1-3X2=0 MAXZ=4X1-3X2 S.T. X1+2X20 X16 X24 X11 X1,X20可行域無(wú)界可行域無(wú)界 MAXZ=4X1-3X2 S.T. X1+2X210 X16 X24 X11 X1,X20X1 0X2 023X1X1=1X2X1+2X2=104X1-3X2=0 MAXZ=4X1-3X2 S.T. X1+2X2 10 X11 X1,X20 MAXZ=4X1-3X2 S.T. X1+2X

15、210 X16 X24 X11 X1,X20可行域無(wú)界可行域無(wú)界X1 0X2 024 線性規(guī)劃問(wèn)題的數(shù)學(xué)模型有各種不同的形式，如線性規(guī)劃問(wèn)題的數(shù)學(xué)模型有各種不同的形式，如 目標(biāo)函數(shù)有極大化和極小化；目標(biāo)函數(shù)有極大化和極小化； 約束條件有約束條件有“”、“”和和“”三種情況；三種情況； 決策變量一般有非負(fù)性要求，有的則沒(méi)有。決策變量一般有非負(fù)性要求，有的則沒(méi)有。 為了求解方便，特規(guī)定一種線性規(guī)劃的標(biāo)準(zhǔn)形式，非為了求解方便，特規(guī)定一種線性規(guī)劃的標(biāo)準(zhǔn)形式，非標(biāo)準(zhǔn)型可以轉(zhuǎn)化為標(biāo)準(zhǔn)型。標(biāo)準(zhǔn)形式為：標(biāo)準(zhǔn)型可以轉(zhuǎn)化為標(biāo)準(zhǔn)型。標(biāo)準(zhǔn)形式為： 目標(biāo)函數(shù)極大化，目標(biāo)函數(shù)極大化， 約束條件為等式，約束條件為等式， 右

16、端常數(shù)項(xiàng)右端常數(shù)項(xiàng)bi0， 決策變量非負(fù)。決策變量非負(fù)。一一 、標(biāo)準(zhǔn)型、標(biāo)準(zhǔn)型第三節(jié)第三節(jié) 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型251. 標(biāo)準(zhǔn)形式的特點(diǎn) 2. 非標(biāo)準(zhǔn)型向標(biāo)準(zhǔn)型的轉(zhuǎn)化 （1）.目標(biāo)函數(shù)：MAX （1）.MIN （2）.約束方程右端常數(shù)：非負(fù) （2）.約束方程右端常數(shù)為負(fù)值 （3）.變量符號(hào)：非負(fù) （3）.變量符號(hào)不確定 自由變量 （4）.約束條件：等號(hào) （4）.不等式約束 第三節(jié)第三節(jié) 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型26minZ=X1+3X2 S.T. 6X1+7X28 -X1+3X2-6 X1-X2=3 X10不符合線性規(guī)劃的標(biāo)準(zhǔn)形式目標(biāo)函數(shù)“極小值”約束方程右端存在負(fù)數(shù)約束方

17、程還不是等式約束 存在自由變量X2第三節(jié)第三節(jié) 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型271. 代數(shù)式代數(shù)式二、標(biāo)準(zhǔn)型的表達(dá)方式（二、標(biāo)準(zhǔn)型的表達(dá)方式（代數(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簡(jiǎn)記第三節(jié)第三節(jié) 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型282. 矩陣式矩陣式 0. .maxXbAXtsXCZ),(21ncccC價(jià)值向量mn

18、mmnnaaaaaaaaaA212222111211技術(shù)矩陣mbbbb21資源向量nxxxX21決策向量第三節(jié)第三節(jié) 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型29 minZ=CX，只需將等式兩端乘以 -1 即變?yōu)闃O大化問(wèn)題。 因?yàn)閙inZ=-max (-Z)=CX，令Z= -Z，則maxZ=-CX 兩端同乘以 -1 當(dāng)約束方程為“”時(shí)，左端加入一個(gè)非負(fù)的松弛變量，就把不等式變成了等式； 當(dāng)約束條件為“”時(shí)，不等式左端減去一個(gè)非負(fù)的剩余變量(也可稱(chēng)松弛變量)即可。 k 令xk=xk-x k，xk 0，x k 0，用xk-x k 取代模型中xk三、非標(biāo)準(zhǔn)型向標(biāo)準(zhǔn)型轉(zhuǎn)化三、非標(biāo)準(zhǔn)型向標(biāo)準(zhǔn)型轉(zhuǎn)化 第三節(jié)第三節(jié)

19、 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型30 y 3 y=f (x) 1 0 2 5 x -1 y = -f (x) -3 kkkxxx轉(zhuǎn)化規(guī)則簡(jiǎn)要：轉(zhuǎn)化規(guī)則簡(jiǎn)要：第三節(jié)第三節(jié) 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型31 例例3 minZ= x1 +2 x2 -3 x3 x1 +2 x2 - x3 5 2x1 +3 x2 - x3 6 -x1 - x2 + x3 -2 x1 0, x3 0S.t.第三節(jié)第三節(jié) 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型 Step-1 minZ= x1 +2 x2 +3 x3 x1 +2 x2 + x35 2x1 +3 x2 + x36 -x1 - x2 - x3 -2 x1 0,

20、x30 S.t.32 Step-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 Step-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第三節(jié)第三節(jié) 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型S.t.S.t.33 Step-4 minZ= x1 +

21、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 Step-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第三節(jié)第三節(jié) 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型S.t.S.t.34 Step-6 minZ= x1 +

22、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 + x6= 2 x1, x2, x 2, x3, x4 , x5 , x6 0 Step-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

23、0 第三節(jié)第三節(jié) 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型S.t.S.t.35 例例4 maxZ= 3x1 +5 x2 x1 8 2x2 12 3x1 +4 x2 36 x1 0, x2 0S.t.第三節(jié)第三節(jié) 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型 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 S.t.標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型作作 業(yè)業(yè) ： 1、教材后作業(yè)9（建立數(shù)學(xué)模型） 2、教材后作業(yè)1（化標(biāo)準(zhǔn)型） 3、教材后作業(yè)2的（圖解法）37第四節(jié)第四節(jié) LP問(wèn)題的基本性質(zhì)問(wèn)

24、題的基本性質(zhì)一一LP解的基本概念解的基本概念 可行解：可行解： 滿足約束條件AX=b, X0的解。 最優(yōu)解最優(yōu)解： 使目標(biāo)函數(shù)最優(yōu)的可行解，稱(chēng)為最優(yōu)解。 基基 n元線性約束方程組，m個(gè)方程線性無(wú)關(guān)； 即矩陣A的秩R(A)=m；根據(jù)線性代數(shù)定理可知，nm，則方程組有多個(gè)解，這也正是線性規(guī)劃尋求最優(yōu)解的余地所在。 ?秩的定義秩的定義n元線性方程組元線性方程組Ax=b解的討論解的討論X1X1=1X1=6X2=4X2X1+2X2=10ABCDE MAXZ=4X1-3X2 S.T. X1+2X210 X16 X24 X11 X1,X20X2 0X1 0可行域可行解39 線性方程組的增廣矩陣 例例1 的標(biāo)

25、準(zhǔn)型的標(biāo)準(zhǔn)型 maxZ= 3x1 +5 x2 +0 x3 +0 x4+0 x5 x1 +x3 =8 2x2 +x4 = 12 3x1 +4 x2 +x5= 36 x1, x2 , x3 , x4 , x5 036101201800043020101Ax1x2x3x4x5第四節(jié)第四節(jié) LP問(wèn)題的基本性質(zhì)問(wèn)題的基本性質(zhì)40 基（基矩陣）基（基矩陣）： 系數(shù)矩陣系數(shù)矩陣A中任意中任意m列所組成的列所組成的m階非奇異子矩陣，稱(chēng)為該線性階非奇異子矩陣，稱(chēng)為該線性規(guī)劃問(wèn)題的一個(gè)基矩陣。規(guī)劃問(wèn)題的一個(gè)基矩陣。 或稱(chēng)為一個(gè)基，用或稱(chēng)為一個(gè)基，用B表示。表示。 稱(chēng)基矩陣的列為基向量，用稱(chēng)基矩陣的列為基向量，用P

26、j表示表示(j=1,2,m) 。100100043020101A的基矩陣的基矩陣B最多最多C53=10，如下：，如下：100010001x3x4x5103010001x1x4x5104012000 x2x4x5130000011x3x1x5140020001x3x2x5300010101x3x4x1400210001x3x4x2043020101x1x2x5x1x2x4043120001x1x2x5143020001第四節(jié)第四節(jié) LP問(wèn)題的基本性質(zhì)問(wèn)題的基本性質(zhì)?41 基變量：基變量： 與基向量Pj相對(duì)應(yīng)的m個(gè)變量xj稱(chēng)為基變量， 其余的m-n個(gè)變量為非基變量。 基解：基解： 令所有非基變量等

27、于零，對(duì)m個(gè)基變量所求的解， 對(duì)應(yīng)一個(gè)特定的基矩陣能求得一組唯一解，這個(gè)對(duì)應(yīng)于基的解稱(chēng)為基解。 結(jié)合圖解來(lái)看，基解是各約束方程及坐標(biāo)軸之間交點(diǎn)的坐標(biāo)。 100010001Bx3x4x5基變量是基變量是x3, x4, x5非基變量是非基變量是x1, x2令非基變量令非基變量x1=x2=0，得到一個(gè)基解，得到一個(gè)基解 x3=8，x4=12， x5=36第四節(jié)第四節(jié) LP問(wèn)題的基本性質(zhì)問(wèn)題的基本性質(zhì)42 基可行解：基可行解：滿足非負(fù)性約束的基解稱(chēng)為基可行解。 可行基：可行基：對(duì)應(yīng)于基可行解的基，稱(chēng)為可行基。 最優(yōu)基：最優(yōu)基：最優(yōu)解對(duì)應(yīng)的基矩陣，稱(chēng)為最優(yōu)基。 非可行解可行解基解基可行解第四節(jié)第四節(jié) LP問(wèn)題的基本性質(zhì)問(wèn)題的基本性質(zhì)43例2-2 某線性規(guī)劃問(wèn)題的約束方程為 X1+3X2+4X3+X4=8 2X1+2X2+X3+X5=1 Xj0, j=1,2,3,4,5nmnmmnPPPaaaaaaA, 212111211A為為m n矩陣（矩陣（ m為約束方程個(gè)