運(yùn)籌學(xué)第一章線性規(guī)劃及單純形法

1、第一章第一章 線性規(guī)劃及單純形法線性規(guī)劃及單純形法目目 錄錄線性規(guī)劃介紹線性規(guī)劃介紹線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃的圖解法線性規(guī)劃的圖解法 線性規(guī)劃的單純形法線性規(guī)劃的單純形法問(wèn)題的提出v在現(xiàn)有各項(xiàng)資源條件的限制下，如何確定方在現(xiàn)有各項(xiàng)資源條件的限制下，如何確定方案，使預(yù)期目標(biāo)達(dá)到最優(yōu)；或?yàn)榱诉_(dá)到取其案，使預(yù)期目標(biāo)達(dá)到最優(yōu)；或?yàn)榱诉_(dá)到取其目標(biāo)，確定使資源消耗最少的方案。目標(biāo)，確定使資源消耗最少的方案。問(wèn)題的提出v例例1 美佳公司計(jì)劃制造美佳公司計(jì)劃制造i，ii兩種家電產(chǎn)品。兩種家電產(chǎn)品。已知各制造一件時(shí)分別占用的設(shè)備已知各制造一件時(shí)分別占用的設(shè)備a、b的臺(tái)的臺(tái)時(shí)、調(diào)試時(shí)間及時(shí)、調(diào)試時(shí)

2、間及a、b設(shè)備和調(diào)試工序每天可設(shè)備和調(diào)試工序每天可用于這兩種家電的能力、各售出一件時(shí)的獲用于這兩種家電的能力、各售出一件時(shí)的獲利情況如表利情況如表1-1所示。問(wèn)該公司應(yīng)制造所示。問(wèn)該公司應(yīng)制造a、b兩種家電各多少件，使獲取的利潤(rùn)為最大。兩種家電各多少件，使獲取的利潤(rùn)為最大。例例2、生產(chǎn)計(jì)劃問(wèn)題、生產(chǎn)計(jì)劃問(wèn)題 a b 備用資源備用資源 煤煤 1 2 30 勞動(dòng)日勞動(dòng)日 3 2 60 倉(cāng)庫(kù)倉(cāng)庫(kù) 0 2 24 利潤(rùn)利潤(rùn) 40 50 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0max z= 40 x1 +50 x2解解:設(shè)產(chǎn)品設(shè)產(chǎn)品a, b產(chǎn)量分別為變量產(chǎn)量分別為變量

3、x1 ， x2問(wèn)題的提出例例3：捷運(yùn)公司擬在下一年度的：捷運(yùn)公司擬在下一年度的1-4月的月的4個(gè)月內(nèi)需租個(gè)月內(nèi)需租用倉(cāng)庫(kù)堆放物資，已知各月所需倉(cāng)庫(kù)面積如表用倉(cāng)庫(kù)堆放物資，已知各月所需倉(cāng)庫(kù)面積如表1-2。倉(cāng)庫(kù)租借費(fèi)用隨合同期限而定，合同期越長(zhǎng)，折扣倉(cāng)庫(kù)租借費(fèi)用隨合同期限而定，合同期越長(zhǎng)，折扣越大，具體見表越大，具體見表1-3。租借倉(cāng)庫(kù)的合同每月初都可。租借倉(cāng)庫(kù)的合同每月初都可辦理，每份合同具體規(guī)定租用面積數(shù)和期限。該廠辦理，每份合同具體規(guī)定租用面積數(shù)和期限。該廠可在任何一月辦理租借合同，每次辦理一份或若干可在任何一月辦理租借合同，每次辦理一份或若干份均可。為使租借費(fèi)用最小，公司應(yīng)如何選擇簽訂份均

4、可。為使租借費(fèi)用最小，公司應(yīng)如何選擇簽訂合同的最優(yōu)決策？合同的最優(yōu)決策？月份1234所需倉(cāng)庫(kù)面積15102012合同租借期限1個(gè)月2個(gè)月3個(gè)月4個(gè)月合同期內(nèi)的租費(fèi)2800450060007300例例4求：最低成本的原料混合方案求：最低成本的原料混合方案 原料原料 a b 每單位成本每單位成本 1 4 1 0 2 2 6 1 2 5 3 1 7 1 6 4 2 5 3 8 每單位添每單位添 加劑中維生加劑中維生 12 14 8 素最低含量素最低含量解：設(shè)每單位添加劑中原料解：設(shè)每單位添加劑中原料i的用量為的用量為xi(i =1,2,3,4)minz= 2x1 + 5x2 +6x3+8x4 4x1

5、 + 6x2 + x3+2x4 12 x1 + x2 +7x3+5x4 14 2x2 + x3+3x4 8 xi 0 (i =1,4)補(bǔ)充作業(yè)、運(yùn)輸問(wèn)題補(bǔ)充作業(yè)、運(yùn)輸問(wèn)題 從倉(cāng)庫(kù)到工廠運(yùn)送單位原材料的成本，工廠對(duì)原從倉(cāng)庫(kù)到工廠運(yùn)送單位原材料的成本，工廠對(duì)原材料的需求量，倉(cāng)庫(kù)目前庫(kù)存分別如表所示，求成本材料的需求量，倉(cāng)庫(kù)目前庫(kù)存分別如表所示，求成本最低的運(yùn)輸方案。最低的運(yùn)輸方案。 工廠工廠 倉(cāng)庫(kù)倉(cāng)庫(kù) 1 2 3 庫(kù)存庫(kù)存 1 2 1 3 50 2 2 2 4 30 3 3 4 2 10 需求需求 40 15 35設(shè)設(shè)xij為為i 倉(cāng)庫(kù)運(yùn)到倉(cāng)庫(kù)運(yùn)到 j工廠的原棉數(shù)量工廠的原棉數(shù)量(i 1，2，3，

6、 j 1，2，3)minz= 2x11 + x12+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33x11 +x12+x13 50 x21+x22+x23 30 x31+x32+x33 10 x11 +x21+x31 = 40 x12 +x22+x32 = 15x13 +x23+x33 = 35 xij 0一、線性規(guī)劃模型特點(diǎn)一、線性規(guī)劃模型特點(diǎn)決策變量：向量決策變量：向量(x1 xn)t 決策人要考慮和決策人要考慮和控制的因素非負(fù)控制的因素非負(fù)約束條件：線性等式或不等式約束條件：線性等式或不等式目標(biāo)函數(shù)：目標(biāo)函數(shù)：z=(x1 xn) 線性式，求線性式，求z極大或

7、極大或極小極小線性規(guī)劃介紹二、線性規(guī)劃解決的管理問(wèn)題二、線性規(guī)劃解決的管理問(wèn)題： 合理利用線材問(wèn)題；合理利用線材問(wèn)題；配料問(wèn)題；配料問(wèn)題；投資問(wèn)題；投資問(wèn)題；產(chǎn)品生產(chǎn)計(jì)劃；產(chǎn)品生產(chǎn)計(jì)劃；勞動(dòng)力安排；勞動(dòng)力安排；運(yùn)輸問(wèn)題。運(yùn)輸問(wèn)題。線性規(guī)劃介紹要求達(dá)到某些數(shù)量上的最大化或最小化；要求達(dá)到某些數(shù)量上的最大化或最小化；在一定的約束條件下追求其目標(biāo)。在一定的約束條件下追求其目標(biāo)。三、線性規(guī)劃問(wèn)題的共同點(diǎn)三、線性規(guī)劃問(wèn)題的共同點(diǎn)： 線性規(guī)劃介紹線性規(guī)劃的數(shù)學(xué)模型一、線性規(guī)劃數(shù)學(xué)模型的一般形式一、線性規(guī)劃數(shù)學(xué)模型的一般形式二、線性規(guī)劃數(shù)學(xué)模型的標(biāo)準(zhǔn)形式二、線性規(guī)劃數(shù)學(xué)模型的標(biāo)準(zhǔn)形式用數(shù)學(xué)語(yǔ)言描述用數(shù)學(xué)語(yǔ)言

8、描述目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件解：用變量解：用變量x1和和x2分別表示美佳公司制造家電分別表示美佳公司制造家電i和和ii的數(shù)量。的數(shù)量。線性規(guī)劃的一般式max(min)z=c1x1+ c2x2+cnxna11x1+ a12x2+ a1nxn (=, (=, )b)b1 1a21x1+ a22x2+ a2nxn (=, (=, )b)b2 2 am1x1+ am2x2+ amnxn (=, (=, )b)bm mxj j 0(0(j=1,n) )簡(jiǎn)寫為：簡(jiǎn)寫為：njjjxcz1max(min), 2 , 1(0), 2 , 1(1njxmibxajinjjij用矩陣和向量形式表示：用矩陣和

9、向量形式表示：線性規(guī)劃標(biāo)準(zhǔn)形式), 2 , 1(0), 2 , 1(. .1njxmibxatsjinjjij線性規(guī)劃的標(biāo)準(zhǔn)形式線性規(guī)劃的標(biāo)準(zhǔn)形式目標(biāo)函數(shù)：目標(biāo)函數(shù)：max約束條件約束條件 ：=變量符號(hào)變量符號(hào) ：0njjjxcz1max（一）一般式（一）一般式（二）矩陣式（二）矩陣式（三）向量式（三）向量式返回返回線性規(guī)劃標(biāo)準(zhǔn)型的幾種表示法線性規(guī)劃標(biāo)準(zhǔn)型的幾種表示法(一一) 一般型一般型maxz=c1x1+ c2x2+cnxna11x1+ a12x2+ a1nxn =b=b1 1a21x1+ a22x2+ a2nxn =b=b2 2 am1x1+ am2x2+ amnxn =b=bm mxj

10、 j 0(0(j=1,2,n) )其中其中 bi 0 (0 (i=1,2,m) )返回返回(二二) 矩陣型矩陣型maxz=cxax=bx 0 0 p p1 1 p p2 2 p pn n a11 a12 a1n其中其中 a= a= a21 a22 a2n am1 am2 amn x1 x= x2 xnc=(c1 c2 cn ) b1 b= b2 bm返回返回(三三) 向量型向量型cxzmax01xbxpnjjj x1ax=(p1 p2 pn ) x2 = b xn p1 x1+ p2 x2 + +pn xn=b返回返回(四四) 化標(biāo)準(zhǔn)型化標(biāo)準(zhǔn)型 1. 約束條件約束條件 3. 變量變量 2. 目

11、標(biāo)函數(shù)目標(biāo)函數(shù)返回返回 4. 右端項(xiàng)系數(shù)右端項(xiàng)系數(shù)1. 約束條件約束條件x3為松弛變量為松弛變量x4為剩余變量為剩余變量 松弛變量或剩余變量在實(shí)際問(wèn)題中分別表示松弛變量或剩余變量在實(shí)際問(wèn)題中分別表示未被充分利用的資源和超出的資源數(shù)，均未轉(zhuǎn)化未被充分利用的資源和超出的資源數(shù)，均未轉(zhuǎn)化為價(jià)值和利潤(rùn)，所以引進(jìn)模型后它們?cè)谀繕?biāo)函數(shù)為價(jià)值和利潤(rùn)，所以引進(jìn)模型后它們?cè)谀繕?biāo)函數(shù)中的系數(shù)均為零。中的系數(shù)均為零。當(dāng)約束條件為當(dāng)約束條件為“”時(shí)，時(shí)，242621 xx如2426321xxx可化為當(dāng)約束條件為當(dāng)約束條件為“”時(shí)，時(shí)，18121021xx如181210321xxx可化為例例1 1maxz=2x1+ x

12、2+0x3 +0x4+0x5 5x2 15 6x1 + 2x2 24 x1 + x2 5 xi 0+x3 =15 +x4 =24 +x5 = 5 松弛變量松弛變量例例2 2minz=2x1+ 5x2+6x3 +8x4 4x1 + 6x2 + x3+2x4 12 x1 + x2 +7x3+5x4 14 2x2 + x3+3x4 8 xi 0 (i =1,4)- x5 =12 - x6 =14 - x7 =8 剩余變量剩余變量 7）+0x5+0x6 +0x7 x1 +2x2 +x3 =30 3x1 +2x2 +x4 =60 2x2 +x5 =24 x1 , , x5 0 0 轉(zhuǎn)化為：轉(zhuǎn)化為：max

13、z=40 x1+ 50 x2+0 x3 +0 x4+0 x5 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0 例：例：max z= 40 x1 +50 x2松弛變量松弛變量例例: 4x1 + 6x2 + x3+2x4 12 x1 + x2 +7x3+5x4 14 2x2 + x3+3x4 8 xi 0 (i =1,4)4x1+6x2+x3 +2x4 - x5 =12 x1+ x2+7x3+5x4 - x6 =14 2x2+ x3+3x4 - x7 =8 x1 , , x7 0 0 剩余變量剩余變量返回返回njjjxcz1minnjjjxcz1max令令z = -

14、z2. 目標(biāo)函數(shù)目標(biāo)函數(shù)xoz-zminz=2x1+ 5x2+6x3 +8x4maxz= -2x1 - 5x2 -6x3 -8x4返回返回3.3.變量變量3 x1 -3 x1 +2x2 8 x1 - x1 4x2 14x1 , x1 ,x2 0 0a、x 0的情況的情況，3x1+2x2 8 x1 4x2 14 x2 0 0令令x1= x1- x1 b、x取值無(wú)約束的情況取值無(wú)約束的情況。令令x -x。令令x= x-xx1 +x2 11x1 16x1 , x2 0 0 c、x兩邊有約束的情況。兩邊有約束的情況。x1+x2 5-6 x1 10 x2 0 0-6+6 x1+6 10+6 令令x1 =

15、 x1 +6 0 x1 16x1 +x2+ x3 = 11x1 +x4 = 16x1 , x2 , x3 , x4 , 0 0將將 min z = -x1+2x2 3x3x1+x2 +x3 7x1 -x2 +x3 2 2x1，x2 0 0，x3無(wú)限制無(wú)限制化為標(biāo)準(zhǔn)型化為標(biāo)準(zhǔn)型例：例：解：解： 令令x3 =x4 - x5 加松弛變量加松弛變量x6加剩余變量加剩余變量x7 令令z= -zmaxz= x1 2x2 +3x4 3x5 x1 +x2 +x4 -x5 +x6 =7x1 -x2 +x4 -x5 -x7 =2x1 , x2 , x4 , , x7 0 0min z = -x1+2x2 3x3x

16、1+x2 +x3 7x1 -x2 +x3 2 2x1，x2 0 0，x3無(wú)限制無(wú)限制返回返回x1+x2 +x3 -9-x1-x2 -x3 94.4.右端項(xiàng)系數(shù)右端項(xiàng)系數(shù)返回返回例：例：將將 min z = -x1+2x2 -3x3x1+x2 +x3 7x1 -x2 +x3 2 2x1，x2 0 0，x3無(wú)限制無(wú)限制化為標(biāo)準(zhǔn)型化為標(biāo)準(zhǔn)型解：解： 令令x3 =x4 - x5 加松弛變量加松弛變量x6 加剩余變量加剩余變量x7 令令z= -zmaxz= x1 -2x2 +3x4 -3x5 x1 +x2 +x4 -x5 +x6 =7x1 -x2 +x4 -x5 - x7 =2x1 , x2 , x4

17、, , x7 0 0返回返回練練 習(xí)習(xí)線性規(guī)劃的圖解法線性規(guī)劃的圖解法maxz=cx (3)ax=b (1)x 0 (2)定義定義1 1：滿足約束：滿足約束(1)(1)、(2)(2)的的x=(x1 xn)t稱為稱為lp問(wèn)題的問(wèn)題的可行解可行解，全部可行解的集合稱為，全部可行解的集合稱為可行域可行域。定義定義2 2：滿足：滿足(3)(3)的可行解稱為的可行解稱為lp問(wèn)題的問(wèn)題的最優(yōu)解最優(yōu)解. .1、判別線性規(guī)劃問(wèn)題的求解結(jié)局；、判別線性規(guī)劃問(wèn)題的求解結(jié)局；2、是在存在最優(yōu)解的條件下，找出問(wèn)題的最優(yōu)解。、是在存在最優(yōu)解的條件下，找出問(wèn)題的最優(yōu)解。 1、在平面上建立直角坐標(biāo)系、在平面上建立直角坐標(biāo)系

18、2、圖示約束條件，找出可行域、圖示約束條件，找出可行域3、圖示目標(biāo)函數(shù)和尋找最優(yōu)解、圖示目標(biāo)函數(shù)和尋找最優(yōu)解圖解法求解的目的：圖解法求解的目的：圖解法的步驟：圖解法的步驟：例例1、maxz=40 x1+ 50 x2 x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 0 0(1)、建立坐標(biāo)系、建立坐標(biāo)系 x1+2x2 30 x1+2x2 =30 (0,15) (30,0)dabc3x1+2x2 =60(0,30) (20,0) 2x2 =24203010x1 x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 0x20102030 x1 0 x1 =0 (縱

19、縱) x2 0 x2=0 (橫橫)(2)、確定可行域、確定可行域 解：解： x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 0 0maxz=40 x1+ 50 x2(3)、求最優(yōu)解、求最優(yōu)解解：解：x1 = 15, x2 = 7.5z=40 x1+50 x2x2 =-4/5x1+z/50 x20102030203010 x1dabcc點(diǎn)：點(diǎn)： x1+2x2 =30 3x1+2x2 =60maxz =975 x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 0 0maxz=40 x1+ 50 x2z= 40 x1 + 80 x2 =0 x1 + 2x2

20、=30dabcx20 x1最優(yōu)解：最優(yōu)解：bc線段線段b點(diǎn)點(diǎn) c點(diǎn)點(diǎn)x(1)=(6,12) x(2)=(15,7.5)x= x(1)+(1- ) x(2) (0 1)求解求解例例2、 maxz=40 x1+ 80 x2 x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 0 0 x1 =6 + (1- )15x2=12 + (1- )7.5x1 =15-9 x2 =7.5+4.5 (0 1)maxz=1200 x= = +(1- )x1 6 15x2 12 7.5無(wú)界解無(wú)界解無(wú)有限最優(yōu)解無(wú)有限最優(yōu)解例例3、 maxz=2x1+ 4x2 2x1+x2 8 8-2x1+x2 2x

21、1 , x2 0 0z=02x1+ x2=8-2x1+ x2=28246x240 x1z=0例例4、 maxz=3x1+2x2 -x1 -x2 1 1x1 , x2 0 0無(wú)解無(wú)解無(wú)可行解無(wú)可行解-1x1-1x20max z=x1+3x2 x1+ x26s.t. -x1+2x28 x1 0, x20練練 習(xí)習(xí)max z=x1+3x2s.t. x1+ x26-x1+2x28x1 0, x20可行域可行域目標(biāo)函數(shù)等值線目標(biāo)函數(shù)等值線最優(yōu)解最優(yōu)解64-860 x1x2練練 習(xí)習(xí)由圖解法得到的啟示由圖解法得到的啟示(1)、線性規(guī)劃問(wèn)題的解的情況有四種：唯一最優(yōu)解；、線性規(guī)劃問(wèn)題的解的情況有四種：唯一最

22、優(yōu)解；無(wú)窮多最優(yōu)解；無(wú)界解；無(wú)可行解。無(wú)窮多最優(yōu)解；無(wú)界解；無(wú)可行解。(3)、若有最優(yōu)解，定可在可行域的頂點(diǎn)得到。、若有最優(yōu)解，定可在可行域的頂點(diǎn)得到。(2)、若線性規(guī)劃可行域存在，則可行域是一個(gè)凸集。、若線性規(guī)劃可行域存在，則可行域是一個(gè)凸集。(4)、解題思路是找出凸集的各頂點(diǎn)的最大目標(biāo)函數(shù)、解題思路是找出凸集的各頂點(diǎn)的最大目標(biāo)函數(shù)值。值。線性規(guī)劃解的情況線性規(guī)劃解的情況唯一解唯一解無(wú)窮多解無(wú)窮多解 無(wú)有限最優(yōu)解無(wú)有限最優(yōu)解 無(wú)可行解無(wú)可行解有解有解無(wú)解無(wú)解當(dāng)目標(biāo)函數(shù)的直線當(dāng)目標(biāo)函數(shù)的直線族與某約束條件直族與某約束條件直線平行，且該問(wèn)題線平行，且該問(wèn)題有解時(shí)。有解時(shí)。線性規(guī)劃解的情況線性規(guī)劃

23、解的情況唯一解唯一解無(wú)窮多解無(wú)窮多解 無(wú)有限最優(yōu)解無(wú)有限最優(yōu)解 無(wú)可行解無(wú)可行解有解有解無(wú)解無(wú)解有解但可行域可有解但可行域可伸展到無(wú)窮時(shí)伸展到無(wú)窮時(shí)線性規(guī)劃解的情況線性規(guī)劃解的情況唯一解唯一解無(wú)窮多解無(wú)窮多解 無(wú)有限最優(yōu)解無(wú)有限最優(yōu)解 無(wú)可行解無(wú)可行解有解有解無(wú)解無(wú)解約束條件直線無(wú)約束條件直線無(wú)公共區(qū)域。公共區(qū)域。線性規(guī)劃的單純形法一、線性規(guī)劃的基本概念一、線性規(guī)劃的基本概念二、單純形法的迭代原理二、單純形法的迭代原理三、單純形法的計(jì)算步驟三、單純形法的計(jì)算步驟四、單純形法的進(jìn)一步討論四、單純形法的進(jìn)一步討論五、單純形法小結(jié)五、單純形法小結(jié)線性規(guī)劃的相關(guān)概念線性規(guī)劃的相關(guān)概念 矩陣的秩矩陣a中

24、，不為零的子式的最高階數(shù)，稱為矩陣a的秩。逆矩陣設(shè)有n階方陣a，如果存在n階方陣b，滿足ab=ba=e，則稱a陣是可逆的，且稱b是a的逆矩陣。線性規(guī)劃的相關(guān)概念線性規(guī)劃的相關(guān)概念矩陣的初等變換：矩陣的初等變換：（1 1）對(duì)調(diào)矩陣的兩行或兩列；）對(duì)調(diào)矩陣的兩行或兩列；（2 2）以非零數(shù)）以非零數(shù)k k乘矩陣的某一行（列）的所有元素；乘矩陣的某一行（列）的所有元素；（3 3）以數(shù)）以數(shù)k k乘矩陣的某行（列）的所有元素加到另乘矩陣的某行（列）的所有元素加到另一行（列）的對(duì)應(yīng)元素上去。一行（列）的對(duì)應(yīng)元素上去。對(duì)方程組的系數(shù)矩陣對(duì)方程組的系數(shù)矩陣a a作初等行變換，得到新作初等行變換，得到新的方程組

25、與原方程組同解。的方程組與原方程組同解。目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件解：用變量解：用變量x1和和x2分別表示美佳公司制造家電分別表示美佳公司制造家電i和和ii的數(shù)量。的數(shù)量。 可行解可行解滿足方程約束條件的解滿足方程約束條件的解x（x1，x2，xn)t, 稱為線稱為線性規(guī)劃問(wèn)題的可行解。全部可行解的集合稱為可行域。性規(guī)劃問(wèn)題的可行解。全部可行解的集合稱為可行域。最優(yōu)解最優(yōu)解使目標(biāo)函數(shù)達(dá)到最大值的可行解稱為最優(yōu)解使目標(biāo)函數(shù)達(dá)到最大值的可行解稱為最優(yōu)解線性規(guī)劃的基本概念線性規(guī)劃的基本概念maxz=c1x1+ c2x2+cnxna11x1+ a12x2+ a1nxn =b=b1 1a21x1+

26、a22x2+ a2nxn =b=b2 2 am1x1+ am2x2+ amnxn =b=bm mxj j 0(0(j=1,2,n) )基(基陣) 設(shè)a為約束方程組約束方程組的mn階系數(shù)矩陣系數(shù)矩陣, (n=m)，設(shè)其秩為m，b是矩陣a中的一個(gè)mm階的滿秩子矩陣，稱b是線性規(guī)劃問(wèn)題的一個(gè)基。線性規(guī)劃的基本概念線性規(guī)劃的基本概念如果矩陣如果矩陣a的滿秩子矩陣不是唯一的，的滿秩子矩陣不是唯一的，則基陣也是不唯一的則基陣也是不唯一的b=(p1,p2,pm)基向量基陣b中的每一個(gè)列向量pj稱為基向量，基變量與基向量對(duì)應(yīng)的變量稱為基變量，非基變量基變量外的其他變量稱為非基變量。線性規(guī)劃的基本概念線性規(guī)劃的

27、基本概念a= (p1 pm pm+1 pn )= (b n) 基向量基向量 非基向量非基向量 基陣基陣 非基矩陣非基矩陣x= (x1 xm xm+1 xn )t=(xb xn)t 基變量基變量 非基變量非基變量 xb xnmax z=2x1+3x2+x3s.t. x1+3x2+x315 2x1+3x2-x3 18 x1- x2+x3 3 x1,x2,x30max z=2x1+3x2+x3s.t. x1+3x2+x3+x4 =15 2x1+3x2-x3 +x5 =18 x1-x2+x3 +x6 =3 x1,x2,x3 ,x4,x5 ,x6,0100111010132001131max z=2x1

28、+3x2+x3s.t. x1+3x2+x3+x4 =15 2x1+3x2-x3 +x5 =18 x1-x2+x3 +x6 =3 x1,x2,x3 ,x4,x5 ,x6,0100111010132001131maxz=c1x1+ c2x2+cnxna11x1+ a12x2+ a1nxn =b=b1 1a21x1+ a22x2+ a2nxn =b=b2 2 am1x1+ am2x2+ amnxn =b=bm mxj j 0(0(j=1,2,n) )其中其中 bi 0 (0 (i=1,2,m) )n=m線性規(guī)劃的基本概念線性規(guī)劃的基本概念找出該線性規(guī)劃問(wèn)題的全部基解，指出其中的基可行解，并確定最找出

29、該線性規(guī)劃問(wèn)題的全部基解，指出其中的基可行解，并確定最優(yōu)解優(yōu)解線性規(guī)劃的基本概念線性規(guī)劃的基本概念maxz=2x1+ 3x2+x3x1+ + x3 =5=5x1 + 2x2 + x4 =10=10 x2 +x5 =4=4xj j 0(0(j=1,2,5) )序號(hào)x1x2x3x4x5z是否可是否可行解行解10051045是20452017是35005410是40550-120否5100-50415否652.5001.517.5 是7540-3022否82430019是maxz=2x1+ 3x2+x3x1+ + x3 =5=5x1 + 2x2 + x4 =10=10 x2 +x5 =4=4xj j

30、 0(0(j=1,2,5) )為何不選為何不選x2、x4 、 x5作為基變量？作為基變量？v定理定理1 若線性規(guī)劃問(wèn)題存在可行解，則問(wèn)題的可行若線性規(guī)劃問(wèn)題存在可行解，則問(wèn)題的可行域是凸集。域是凸集。v定理定理2 線性規(guī)劃問(wèn)題的基可行解線性規(guī)劃問(wèn)題的基可行解x對(duì)應(yīng)線性規(guī)劃問(wèn)對(duì)應(yīng)線性規(guī)劃問(wèn)題可行域的頂點(diǎn)。題可行域的頂點(diǎn)。v定理定理3 若線性規(guī)劃問(wèn)題有最優(yōu)解，一定存在一個(gè)基若線性規(guī)劃問(wèn)題有最優(yōu)解，一定存在一個(gè)基可行解是最優(yōu)解可行解是最優(yōu)解線性規(guī)劃的基本定理線性規(guī)劃的基本定理ax=b的求解的求解xb xn(b n) = bbxb +nxn=bbxb =b-nxnb-1 bxb = b-1 （b-nx

31、n）xb = b-1 b - b-1n xna=(b n)x=(xb xn )t1. xn0， b-1 b 0則則 xb = b-1 b，即，即x= 為為 ax=b的一個(gè)解。的一個(gè)解。2.若同時(shí)若同時(shí)b為單位矩陣，為單位矩陣，則則 xb = b，即即x=(b，0)為為ax=b的一個(gè)解的一個(gè)解線性規(guī)劃的基本概念線性規(guī)劃的基本概念a= (p1 pm pm+1 pn )= (b n) 基向量基向量 非基向量非基向量 基陣基陣 非基矩陣非基矩陣x= (x1 xm xm+1 xn )t=(xb xn)t 基變量基變量 非基變量非基變量 xb xn返回返回序號(hào)x1x2x3x4x5z是否可是否可行解行解10

32、051045是20452017是35005410是40550-120否5100-50415否652.5001.517.5 是7540-3022否82430019是maxz=2x1+ 3x2+x3x1+ + x3 =5=5x1 + 2x2 + x4 =10=10 x2 +x5 =4=4xj j 0(0(j=1,2,5) )驗(yàn)證驗(yàn)證例：例：max z=2x1+3x2+x3s.t. x1+3x2+x315 2x1+3x2-x3 18 x1- x2+x3 3 x1,x2,x30max z=2x1+3x2+x3s.t. x1+3x2+x3+x4 =15 2x1+3x2-x3 +x5 =18 x1-x2+

33、x3 +x6 =3 x1,x2,x3 ,x4,x5 ,x6,0 x1+3x2+x3=152x1+3x2-x3=18x1-x2+x3=3x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3基變量基變量x1、x2、x3，非基變量，非基變量x4、x5、x6基礎(chǔ)解為（基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0）是基礎(chǔ)可行解，表示可行域的一個(gè)極點(diǎn)。是基礎(chǔ)可行解，表示可行域的一個(gè)極點(diǎn)。目標(biāo)函數(shù)值為：目標(biāo)函數(shù)值為：z=20 x1+3x2+x4=152x1+3x2=18x1-x2=3基變量基變量x1、x2、x4，非基變量，非基變量x3、x5、x

34、6基礎(chǔ)解為基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0）是基礎(chǔ)可行解，表示可行域的一個(gè)極點(diǎn)。是基礎(chǔ)可行解，表示可行域的一個(gè)極點(diǎn)。目標(biāo)函數(shù)值為：目標(biāo)函數(shù)值為：z=18x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3x1+3x2=152x1+3x2+x5=18x1-x2=3x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3基變量基變量x1、x2、x5，非基變量，非基變量x3、x4、x6基礎(chǔ)解為（基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0）是基礎(chǔ)解

35、，但不是可行解，不是一個(gè)極點(diǎn)。是基礎(chǔ)解，但不是可行解，不是一個(gè)極點(diǎn)。x1+3x2=152x1+3x2=18x1-x2+x6=3基變量基變量x1、x2、x6，非基變量，非基變量x3、x4、x5基礎(chǔ)解為（基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4）是基礎(chǔ)可行解，表示可行域的一個(gè)極點(diǎn)。是基礎(chǔ)可行解，表示可行域的一個(gè)極點(diǎn)。目標(biāo)函數(shù)值為：目標(biāo)函數(shù)值為：z=18x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=33x2+x3+x4=153x2-x3=18-x2+x3=3基變量基變量x2、x3、x4，非基變量，非基變量x1、x5、x6基礎(chǔ)解為

36、基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，0）是基礎(chǔ)解，但不是可行解。是基礎(chǔ)解，但不是可行解。x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=33x2+x3=153x2-x3+x5=18-x2+x3=3基變量基變量x1、x2、x3，非基變量，非基變量x4、x5、x6基礎(chǔ)解為（基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0）是基礎(chǔ)可行解，表示可行域的一個(gè)極點(diǎn)。是基礎(chǔ)可行解，表示可行域的一個(gè)極點(diǎn)。目標(biāo)函數(shù)值為：目標(biāo)函數(shù)值為：z=15x1+3x2+x3+x4=152x1+3x2-x3+x5=

37、18x1-x2+x3+x6=33x2+x3=153x2-x3=18-x2+x3+x6=3基變量基變量x1、x2、x3，非基變量，非基變量x4、x5、x6基礎(chǔ)解為基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10）是基礎(chǔ)解但不是可行解。是基礎(chǔ)解但不是可行解。x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3 基本解中最多有基本解中最多有m m個(gè)非零分量。個(gè)非零分量。 基本解的數(shù)目不超過(guò)基本解的數(shù)目不超過(guò) cnm = 個(gè)。個(gè)。n!m!(n-m)!例例1、 x1+2x2 +x3 =30 3x1+2x2 +x4 =60 2x2

38、+x5=24 x1 x5 0 01 2 1 0 03 2 0 1 00 2 0 0 1p1 p2 p3 p4 p5a=基陣基陣b非基陣非基陣n求出一個(gè)基本解，并判斷是不是可行解？求出一個(gè)基本解，并判斷是不是可行解？令令x1 = x2 =0, 則則 x3=30, x4=60, x5=24x= = = xn 0 xb b-1 b00306024例：給定約束條件例：給定約束條件 -x3+x4 =0=0 x2 +x3 +x4 =3 -x1 +x2 +x3+x4 =2 xj 0 0 ( j=1,2,3,4 )求出基變量是求出基變量是x1 , x3 , x4的基解，是不是可行解？的基解，是不是可行解？ 0

39、 -1 1解：解：b=(p1 p3 p4)= 0 1 1 -1 1 1 0 1 -1 0b-1= -1/2 1/2 0 3 1/2 1/2 0 2b= x1 x3 = b-1 b x4 xb = x=(1, 0, 3/2, 3/2)t 是是 基本可行解基本可行解 0 1 -1 0 1 = -1/2 1/2 0 3 = 3/2 1/2 1/2 0 2 3/2單純形法的迭代原理找出一個(gè)基找出一個(gè)基可行解可行解判斷是判斷是否最優(yōu)否最優(yōu)轉(zhuǎn)換到相鄰的轉(zhuǎn)換到相鄰的基可行解基可行解找到最優(yōu)解找到最優(yōu)解否否是是單純形法計(jì)算步驟v1.求初始基可行解，列出單純形表求初始基可行解，列出單純形表cxz max01xb

40、xpnjjj例題例題5：用單純形法求解線性規(guī)劃問(wèn)題：用單純形法求解線性規(guī)劃問(wèn)題0,524261552max212121221xxxxxxxxxz解：解： 1、先將上述問(wèn)題化成標(biāo)準(zhǔn)形式、先將上述問(wèn)題化成標(biāo)準(zhǔn)形式有有找到一個(gè)初始基可行解找到一個(gè)初始基可行解max z=2x1+x2+0 x3+0 x4+0 x5 5x2+x3 =156x1+2x2 +x4 =24 x1+ x2 +x5=5x=(0,0,15,24,5)t15245p1p2p3p4p52、列初始單純形表：、列初始單純形表：cjcbxbb j=cj-zjmax z=2x1+x2+0 x3+0 x4+0 x5 5x2+x3 =156x1+2

41、x2 +x4 =24 x1+ x2 +x5=5x1進(jìn)基；進(jìn)基；cj21000cbxbbx1x2x3x4x50 x315051000 x424620100 x5511001 j=cj-zjx4出基；出基；-4521000max z=2x1+x2+0 x3+0 x4+0 x5 5x2+x3 =156x1+2x2 +x4 =24 x1+ x2 +x5=5cj21000cbxbbx1x2x3x4x50 x315051000 x424620100 x5511001 j=cj-zjx120 x315051002x124/612/601/600 x5511001 j=cj-zj3、列新單純形表：、列新單純形

42、表：cj21000cbxbbx1x2x3x4x50 x315051002x1412/601/600 x5104/60-1/61 j=cj-zj01/30-1/300 x315051002x1412/601/600 x5104/60-1/61 j=cj-zj3123/2x2進(jìn)基；進(jìn)基；x5出基；出基；cj21000cbxbbx1x2x3x4x50 x315051002x1412/601/600 x5104/60-1/61 j=cj-zj0 x315051002x1412/601/601x23/2010-1/43/2 j=cj-zjx21cj21000cbxbbx1x2x3x4x50 x31505

43、1002x1412/601/601x23/2010-1/43/2 j=cj-zj0 x315051002x17/21001/4-1/21x23/2010-1/43/2 j=cj-zj0 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2 j=cj-zj4 4、列新單純形表：、列新單純形表：解為：解為：x=(7/2,3/2,15/2,0,0)。cj21000cbxbbx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2000-1/43/2 j=cj-zj000-1/4-1/2目標(biāo)函數(shù)值為目標(biāo)函數(shù)值為

44、:maxz=2x1+x2+0 x3+0 x4+0 x5 =27/2+13/2+015/2+0+0=8.50,51253553max432143421321421xxxxxxxxxxxxxxxz 解：解：練習(xí)題練習(xí)題原問(wèn)題化為標(biāo)準(zhǔn)型原問(wèn)題化為標(biāo)準(zhǔn)型0,51253553max72174364215321421xxxxxxxxxxxxxxxxxz列初始單純形表列初始單純形表cj3501000cbxbbx1x2x3x4x5x6x70 x53511101000 x612510-10100 x7500-11001 j=cj-zj0,51253553max72174364215321421xxxxxxxxx

45、xxxxxxxxz列初始單純形表列初始單純形表35010003512cj3501000cbxbbx1x2x3x4x5x6x70 x53511101000 x612510-10100 x7500-11001 j=cj-zjx2入基，入基， x6出基出基cj3501000cbxbbx1x2x3x4x5x6x70 x53511101005x212510-10100 x7500-11001 j=cj-zj23-40111-10-220060-502350 x523-40111-105x212510-10101x4500-11001 j=cj-zjx518-40201-1-11751-10011-220

46、600-5690 x318-40201-1-15x21751-100111x4500-11001 j=cj-zj14-20010.5-0.50.5-10000-3-2-39-20100.5-0.5-0.52631000.50.50.5144)0 , 0 , 0 ,14, 9 ,26, 0(*zx最優(yōu)值最優(yōu)解cj3501000cbxbbx1x2x3x4x5x6x70 x39-20100.5-0.5-0.55x22631000.50.50.51x414-20010.5-0.50.5 j=cj-zj-10000-3-2-3作業(yè)：作業(yè)：人工變量法人工變量法v當(dāng)化為標(biāo)準(zhǔn)形后的約束條件的系數(shù)矩陣中當(dāng)化為標(biāo)

47、準(zhǔn)形后的約束條件的系數(shù)矩陣中不存在單位矩陣時(shí)，可以人為地增加變量，不存在單位矩陣時(shí)，可以人為地增加變量，在最優(yōu)解中人工變量取值必須為零。為此，在最優(yōu)解中人工變量取值必須為零。為此，令目標(biāo)函數(shù)中人工變量的系數(shù)為任意大的令目標(biāo)函數(shù)中人工變量的系數(shù)為任意大的負(fù)值負(fù)值m m。這種人為增加變量的方法稱為人。這種人為增加變量的方法稱為人工變量法，亦稱大工變量法，亦稱大m m法。法。例例1 1：max z= 6x1 +4x2 2x1 +3x2 1004x1 +2x2 120 x1 = =14 x2 22x1 ,x2 0maxz=6x1+4x22x1 +3x2 +x3 = =1004x1 +2x2 +x4 =

48、120 x1 =14 x2 - x5 = 22x1 x5 0解：解：maxz= 6x1 +4x2 2x1 +3x2 1004x1 +2x2 120 x1 = =14 x2 22x1 x2 0化成標(biāo)準(zhǔn)型化成標(biāo)準(zhǔn)型maxz=6x1+4x22x1 +3x2 +x3 = =1004x1 +2x2 +x4 = =120 x1 = =14 x2 - x5 = 22x1 x7 0加人工變量加人工變量+x6+x7-mx6 -mx7cj64000-m-mcbxbbx1x2x3x4x5x6x70 x310023100000 x41204201000-mx6141000010-mx7220100-101 j=cj-

49、zj列初始單純形表列初始單純形表 6 4 0 0 0 - 6 4 0 0 0 - m - - m cb xb b x1 x2 x3 x4 x5 x6 x70 0 x3 100 2 3 1 0 0 0 0 100 2 3 1 0 0 0 0 0 0 x4 120120 4 4 2 0 1 0 0 0 2 0 1 0 0 0 -m x6 14 1 0 0 0 0 1 0 14 1 0 0 0 0 1 0 -m x7 22 0 1 0 0 -1 0 1 - -36 36 m m +6 +6 m +4 0 0 - +4 0 0 - m 0 0 0 0cj0 0 x3 72 0 3 1 0 0 -2 0

50、 72 0 3 1 0 0 -2 0 0 0 x4 64 0 64 0 2 0 1 0 -4 0 2 0 1 0 -4 0 6 x1 14 1 0 0 0 0 1 0 14 1 0 0 0 0 1 0 -m x7 22 0 1 0 0 -1 0 1 8484-22m 0 0 m+4 0 0 - 0 0 -m 6-m 0cj0 0 x3 6 0 0 1 0 (3) -2 -3 6 0 0 1 0 (3) -2 -3 0 0 x4 2020 0 0 0 0 0 1 2 -4 -2 0 1 2 -4 -2 6 x1 14 1 0 0 0 0 1 0 14 1 0 0 0 0 1 0 4 x2 22

51、0 1 0 0 -1 0 1 172172 0 0 0 0 4 0 0 4 6- 6-m 4- 4-m0 0 x5 2 0 0 1/3 0 1 -2/3 -1 2 0 0 1/3 0 1 -2/3 -1 0 0 x4 1 16 0 6 0 0 -2/3 1 0 -8/3 0 0 -2/3 1 0 -8/3 0 6 x1 14 1 0 0 0 0 1 0 14 1 0 0 0 0 1 0 x2 24 0 1 1/3 0 0 -2/3 -2 180180 0 0 0 -4/3 0 -4/3 0 0 -m-10/3 -m 6 4 0 0 0 - 6 4 0 0 0 - m - - m cb xb b

52、 x1 x2 x3 x4 x5 x6 x7解為：解為：x=(14,24,0,16,2)。 目標(biāo)函數(shù)值為目標(biāo)函數(shù)值為:maxz=6x1+4x2 =614+424=180練練 習(xí)習(xí)用大用大m法求解下列問(wèn)題：法求解下列問(wèn)題：兩階段法兩階段法對(duì)添加人工變量后的線性規(guī)劃問(wèn)題分兩個(gè)對(duì)添加人工變量后的線性規(guī)劃問(wèn)題分兩個(gè)階段來(lái)計(jì)算，稱為兩階段法。階段來(lái)計(jì)算，稱為兩階段法。兩階段法兩階段法 第一階段是先求解一個(gè)目標(biāo)函數(shù)中第一階段是先求解一個(gè)目標(biāo)函數(shù)中只包只包含人工變量的線性規(guī)劃問(wèn)題含人工變量的線性規(guī)劃問(wèn)題，即令目標(biāo)函數(shù)中，即令目標(biāo)函數(shù)中其它變量的系數(shù)取零，人工變量的系數(shù)取某個(gè)其它變量的系數(shù)取零，人工變量的系數(shù)取

53、某個(gè)正的常數(shù)正的常數(shù)( (一般取一般取1)1)，在，在保持原問(wèn)題約束條件保持原問(wèn)題約束條件不變不變的情況下求這個(gè)目標(biāo)函數(shù)的情況下求這個(gè)目標(biāo)函數(shù)極小化極小化時(shí)的解。時(shí)的解。作輔助問(wèn)題作輔助問(wèn)題原問(wèn)題原問(wèn)題njjjxcz1max0),.,2 , 1(1jnjijijxmibxamiiyw1min0),.,2 , 1(1jnjijijxmibxaiyiy,兩階段法兩階段法在第一階段中，當(dāng)人工變量取值為在第一階段中，當(dāng)人工變量取值為0 0時(shí)，目標(biāo)時(shí)，目標(biāo)函數(shù)值也為函數(shù)值也為0 0。這時(shí)候的最優(yōu)解就是原線性規(guī)。這時(shí)候的最優(yōu)解就是原線性規(guī)劃問(wèn)題的一個(gè)基可行解。劃問(wèn)題的一個(gè)基可行解。如果第一階段求解結(jié)如果第

54、一階段求解結(jié)果最優(yōu)解的目標(biāo)函數(shù)值不為果最優(yōu)解的目標(biāo)函數(shù)值不為0 0，也即最優(yōu)解的，也即最優(yōu)解的基變量中含有非零的人工變量，表明原線性規(guī)基變量中含有非零的人工變量，表明原線性規(guī)劃問(wèn)題無(wú)可行解。劃問(wèn)題無(wú)可行解。解題過(guò)程：解題過(guò)程：第第1階段階段：解輔助問(wèn)題：解輔助問(wèn)題當(dāng)進(jìn)行到最優(yōu)表時(shí)，當(dāng)進(jìn)行到最優(yōu)表時(shí)，若若w=0, 則得到原問(wèn)題的一個(gè)則得到原問(wèn)題的一個(gè) 基本可行解，轉(zhuǎn)基本可行解，轉(zhuǎn)入第入第2階段。階段。若若w0, 則判定原問(wèn)題無(wú)可行解。則判定原問(wèn)題無(wú)可行解。 第第2 2階段階段：去除人工變量，：去除人工變量，求解原問(wèn)題。第一階段求解原問(wèn)題。第一階段的最優(yōu)解為原問(wèn)題的初始基可行解。的最優(yōu)解為原問(wèn)題的

55、初始基可行解。maxz= -x1 +2x2 x1 +x2 2-x1 +x2 1 x2 3 3x1 x2 0例：例： x1 +x2 -x3 = =2-x1 +x2 -x4 = =1 x2 +x5 = =3x1 x5 01.化標(biāo)準(zhǔn)型：化標(biāo)準(zhǔn)型：maxz= -x1 +2x2 +x6+x72.增加人工變量，構(gòu)造單位矩陣：增加人工變量，構(gòu)造單位矩陣：,x6, x7 03. 3. 建立只包含人工變量的輔助問(wèn)題。建立只包含人工變量的輔助問(wèn)題。minw=x6 +x7 x1 +x2 -x3 +x6 = =2-x1 +x2 -x4 +x7 = =1 x2 +x5 = =3x1 x7 0cj0000011cbxbbx1x2x3x4x5x6x71x6211-100101x71-110-10010 x530100100 j=cj-zj0-2110002133 0 0 0 0 0 1 1 cb xb b x1 x2 x3 x4 x5 x6 x71 x6 2 1 1 -1 0 0 1 0 1 x7 1 -1 (1) 0 -1 0 0 1 0 x5 3 0 1 0 0 1 0 0 3 0