第二章線性規(guī)劃

1、1第二章第二章 線性規(guī)劃線性規(guī)劃12LPLPLPMkarmark ？條件（）數(shù)學(xué)模型（ ）各種解的概念：可行解（重點(diǎn)）基本概念 基本解（難點(diǎn)）基本可行解（重點(diǎn)）最優(yōu)解基本最優(yōu)解解的基本性質(zhì)：四個(gè)主要定理圖解法實(shí)際問題模型大法基本方法 單純形法（原始單純形法、人工變量法）兩階段法對偶單純形法（求解）前提？步驟？修正單純形法對偶理論進(jìn)一步討論靈敏度分析參數(shù)規(guī)劃算法復(fù)雜性問題哈奇揚(yáng)算法、arLPLPLP算法整數(shù)運(yù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 庫存庫存 倉庫倉庫 A 2 1 3 5 50 倉庫倉庫 B 2 2 4 1 30 倉庫倉庫 C 1 4 3 2 70 需求量需求量 40 50

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

4、量的線性函數(shù)線性函數(shù)。第一節(jié)第一節(jié) 線性規(guī)劃一般模型線性規(guī)劃一般模型6二、線性規(guī)劃的定義二、線性規(guī)劃的定義第一節(jié)第一節(jié) 線性規(guī)劃一般模型線性規(guī)劃一般模型7 某飲料公司在國內(nèi)有三個(gè)生產(chǎn)廠，分布在城市某飲料公司在國內(nèi)有三個(gè)生產(chǎn)廠，分布在城市A1、A2、A3,其一級(jí)承銷商有其一級(jí)承銷商有4個(gè)，分布在城市個(gè)，分布在城市B1、B2、B3、B4，已知各廠的產(chǎn)量、各承銷商的銷售量及從已知各廠的產(chǎn)量、各承銷商的銷售量及從Ai到到Bj的每的每噸飲料運(yùn)費(fèi)為噸飲料運(yùn)費(fèi)為Cij，為發(fā)揮集團(tuán)優(yōu)勢，公司要統(tǒng)一籌劃，為發(fā)揮集團(tuán)優(yōu)勢，公司要統(tǒng)一籌劃運(yùn)銷問題，求運(yùn)費(fèi)最小的調(diào)運(yùn)方案。運(yùn)銷問題，求運(yùn)費(fèi)最小的調(diào)運(yùn)方案。 銷地銷地產(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銷量銷量 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)量之和等于銷量之和,故要滿足：x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34 =3 銷售平衡條件銷售平衡條件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 綜上所述，該問題的數(shù)學(xué)模型表示為綜上所述，該問題的數(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)品的利潤、各資源的限量和各產(chǎn)品的資源消耗系數(shù)如下表：產(chǎn)品A產(chǎn)品B資源限量勞動(dòng)力設(shè) 備原材料9434510360200300利潤元/kg70120第一節(jié)第一節(jié) 線性規(guī)劃一般模型線性規(guī)劃一般模型11 問題：如何安排生產(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è)決策問題，表示一個(gè)決策問題， 存在一定的等式或不等式的存在一定的等式或不等式的線性約束條件線性約束條件， 有一個(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 用圖示的方法來求解線性規(guī)劃問題。 一個(gè)二維的線性規(guī)劃問題，可以在平面圖上求解，三維的線性規(guī)劃則要在立體圖上求解，而維數(shù)再高以后就不能圖示了。一、圖解法的基本步驟一、圖解法的基本步驟第二節(jié)第二節(jié) LP問題的圖解法問題的圖解法(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è)解，稱之可行解約束條件的一個(gè)解，稱之可行解 。 滿足所有約束條件的解的集合，稱之為可行域。即所有約束滿足所有約束條件的解的集合，稱之為可行域。即所有約束條件共同圍城的區(qū)域。條件共同圍城的區(qū)域。第二節(jié)第二節(jié) LP問題的圖解法問題的圖解法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問題的圖解法問題的圖解法?16 由線性不等式組成的可行域是凸集(凸集的定義是：集合內(nèi)部任意兩點(diǎn)連線上的點(diǎn)都屬于這個(gè)集合)。 可行域有有限個(gè)頂點(diǎn)。設(shè)規(guī)劃問題有n個(gè)變量，m個(gè)約束，則頂點(diǎn)的個(gè)數(shù)不多于Cnm個(gè)。 目標(biāo)函數(shù)最優(yōu)值（如果存在）一定在可行域的邊界達(dá)到，

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

13、它們連線上的每一點(diǎn)都是最優(yōu)解。 無界解無界解：線性規(guī)劃問題的可行域無界，使目標(biāo)函數(shù)無限增大而無界。（缺乏必要的約束條件）。 無可行解無可行解：若約束條件相互矛盾，則可行域?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=存在無窮

14、多解存在無窮多解 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可行域無界可行域無界 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可行域無界可行域無界X1 0X2 024 線性規(guī)劃問題的數(shù)學(xué)模型有各種不同的形式，如線性規(guī)劃問題的數(shù)學(xué)模型有各種不同的形式，如 目標(biāo)函數(shù)有極大化和極小化；目標(biāo)函數(shù)有極大化和極小化； 約束條件有約束條件有“”、“”和和“”三種情況；三種情況； 決策變量一般有非負(fù)性要求，有的則沒有。決策變量一般有非負(fù)性要求，有的則沒有。 為了求解方便，特規(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é)第三節(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大化問題。 因?yàn)閙inZ=-max (-Z)=CX，令Z= -Z，則maxZ=-CX 兩端同乘以 -1 當(dāng)約束方程為“”時(shí)，左端加入一個(gè)非負(fù)的松弛變量，就把不等式變成了等式； 當(dāng)約束條件為“”時(shí)，不等式左端減去一個(gè)非負(fù)的剩余變量(也可稱松弛變量)即可。 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ī)則簡要：轉(zhuǎn)化規(guī)則簡要：第三節(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問題的基本性質(zhì)問

24、題的基本性質(zhì)一一LP解的基本概念解的基本概念 可行解：可行解： 滿足約束條件AX=b, X0的解。 最優(yōu)解最優(yōu)解： 使目標(biāo)函數(shù)最優(yōu)的可行解，稱為最優(yōu)解。 基基 n元線性約束方程組，m個(gè)方程線性無關(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問題的基本性質(zhì)問題的基本性質(zhì)40 基（基矩陣）基（基矩陣）： 系數(shù)矩陣系數(shù)矩陣A中任意中任意m列所組成的列所組成的m階非奇異子矩陣，稱為該線性階非奇異子矩陣，稱為該線性規(guī)劃問題的一個(gè)基矩陣。規(guī)劃問題的一個(gè)基矩陣。 或稱為一個(gè)基，用或稱為一個(gè)基，用B表示。表示。 稱基矩陣的列為基向量，用稱基矩陣的列為基向量，用P

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

27、于零，對m個(gè)基變量所求的解， 對應(yīng)一個(gè)特定的基矩陣能求得一組唯一解，這個(gè)對應(yīng)于基的解稱為基解。 結(jié)合圖解來看，基解是各約束方程及坐標(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問題的基本性質(zhì)問題的基本性質(zhì)42 基可行解：基可行解：滿足非負(fù)性約束的基解稱為基可行解。 可行基：可行基：對應(yīng)于基可行解的基，稱為可行基。 最優(yōu)基：最優(yōu)基：最優(yōu)解對應(yīng)的基矩陣，稱為最優(yōu)基。 非可行解可行解基解基可行解第四節(jié)第四節(jié) LP問題的基本性質(zhì)問題的基本性質(zhì)43例2-2 某線性規(guī)劃問題的約束方程為 X1+3X2+4X3+X4=8 2X1+2X2+X3+X5=1 Xj0, j=1,2,3,4,5nmnmmnPPPaaaaaaA, 212111211A為為m n矩陣（矩陣（ m為約束方程個(gè)