運(yùn)籌學(xué)Ch1線性規(guī)劃課件

1、2021-10-31運(yùn)籌學(xué)運(yùn)籌學(xué)operations researchchapter 1 線性規(guī)劃線性規(guī)劃linear programming1.1 lp的數(shù)學(xué)模型的數(shù)學(xué)模型 mathematical model of lp1.2 圖解法圖解法 graphical method1.3 標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型 standard form of lp1.4 基本概念基本概念 basic concepts1.5 單純形法單純形法 simplex method2021-10-311.1 數(shù)學(xué)模型數(shù)學(xué)模型 mathematical model 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線

2、性規(guī)劃linear programming page 3 2021-10-311.1 線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型 mathematical model of lp線性規(guī)劃線性規(guī)劃（linear programming,縮寫(xiě)為lp）通常研究資源通常研究資源的最優(yōu)利用、設(shè)備最佳運(yùn)行等問(wèn)題。例如，當(dāng)任務(wù)或目標(biāo)的最優(yōu)利用、設(shè)備最佳運(yùn)行等問(wèn)題。例如，當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源 （如資（如資金、設(shè)備、原標(biāo)材料、人工、時(shí)間等）去完成確定的任務(wù)金、設(shè)備、原標(biāo)材料、人工、時(shí)間等）去完成確定的任務(wù)或目標(biāo)；企業(yè)在一定的資源條件限制下

3、，如何組織安排生或目標(biāo)；企業(yè)在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多 、利潤(rùn)最大）。、利潤(rùn)最大）。 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 4 2021-10-31【例【例1-1】生產(chǎn)計(jì)劃問(wèn)題。某企業(yè)在計(jì)劃期內(nèi)計(jì)劃生產(chǎn)甲、乙兩】生產(chǎn)計(jì)劃問(wèn)題。某企業(yè)在計(jì)劃期內(nèi)計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品。按工藝資料規(guī)定，每件產(chǎn)品甲需要消耗材料種產(chǎn)品。按工藝資料規(guī)定，每件產(chǎn)品甲需要消耗材料a 2公斤，公斤，消耗材料消耗材料b 1公斤，每件產(chǎn)品乙需要消耗材料公斤，每件產(chǎn)品乙

4、需要消耗材料a 1公斤，消耗材公斤，消耗材料料b 1.5公斤。已知在計(jì)劃期內(nèi)可供材料分別為公斤。已知在計(jì)劃期內(nèi)可供材料分別為40、30公斤；每公斤；每生產(chǎn)一件甲、乙兩產(chǎn)品，企業(yè)可獲得利潤(rùn)分別為生產(chǎn)一件甲、乙兩產(chǎn)品，企業(yè)可獲得利潤(rùn)分別為300、400元，元，如表如表11所示。假定市場(chǎng)需求無(wú)限制。企業(yè)決策者應(yīng)如何安排所示。假定市場(chǎng)需求無(wú)限制。企業(yè)決策者應(yīng)如何安排生產(chǎn)計(jì)劃，使企業(yè)在計(jì)劃期內(nèi)總的利潤(rùn)收入最大。生產(chǎn)計(jì)劃，使企業(yè)在計(jì)劃期內(nèi)總的利潤(rùn)收入最大。1.1 線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型 mathematical model of lp1.1.1 應(yīng)用模型舉例應(yīng)用模型舉例 制作與教學(xué) 武漢理工

5、大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 5 2021-10-3112max300400zxx【解】設(shè)【解】設(shè)x1、x2分別為甲、乙產(chǎn)品的產(chǎn)量，數(shù)學(xué)模型為：分別為甲、乙產(chǎn)品的產(chǎn)量，數(shù)學(xué)模型為：1.1 線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型 mathematical model of lp 產(chǎn)品產(chǎn)品 資源資源 甲甲 乙乙現(xiàn)有資現(xiàn)有資源源材料材料a2140材料材料b11.530利潤(rùn)（元利潤(rùn)（元/件）件） 3004001212122401.5300,0 xxxxxx表表1-1 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性

6、規(guī)劃線性規(guī)劃linear programming page 6 2021-10-31線性規(guī)劃的數(shù)學(xué)模型由線性規(guī)劃的數(shù)學(xué)模型由決策變量決策變量 decision variables 目標(biāo)函數(shù)目標(biāo)函數(shù)objective function及約束條件及約束條件constraints構(gòu)成。稱為三個(gè)要素構(gòu)成。稱為三個(gè)要素。n其特征是：其特征是：n1解決問(wèn)題的目標(biāo)函數(shù)是多個(gè)決策變量的解決問(wèn)題的目標(biāo)函數(shù)是多個(gè)決策變量的 線性函數(shù)，通常是求最大值或線性函數(shù)，通常是求最大值或 最小值；最小值；n2解決問(wèn)題的解決問(wèn)題的是一組多個(gè)決策變量是一組多個(gè)決策變量 的線性不等式或等式。的線性不等式或等式。怎樣辨別一個(gè)模型是線

7、性規(guī)劃模型？怎樣辨別一個(gè)模型是線性規(guī)劃模型？1.1 線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型 mathematical model of lp 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 7 2021-10-31【例【例1-2】某商場(chǎng)決定：營(yíng)業(yè)員每周連續(xù)工作】某商場(chǎng)決定：營(yíng)業(yè)員每周連續(xù)工作5天后連續(xù)休息天后連續(xù)休息2天，天，輪流休息。根據(jù)統(tǒng)計(jì)，商場(chǎng)每天需要的營(yíng)業(yè)員如表輪流休息。根據(jù)統(tǒng)計(jì)，商場(chǎng)每天需要的營(yíng)業(yè)員如表1-2所示。所示。表表1-2 營(yíng)業(yè)員需要量統(tǒng)計(jì)表營(yíng)業(yè)員需要量統(tǒng)計(jì)表商場(chǎng)人力資源部應(yīng)如何安排每天的上班人數(shù)，使商

8、場(chǎng)總的營(yíng)業(yè)員商場(chǎng)人力資源部應(yīng)如何安排每天的上班人數(shù)，使商場(chǎng)總的營(yíng)業(yè)員最少。最少。 星期星期需要人數(shù)需要人數(shù)星期星期需要人數(shù)需要人數(shù)一一300五五480二二300六六600三三350日日550四四4001.1 線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型 mathematical model of lp 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 8 2021-10-31【解】【解】 設(shè)設(shè)xj (j=1，2，7)為休息為休息2天后星期一到星期日開(kāi)始上天后星期一到星期日開(kāi)始上班的營(yíng)業(yè)員，則這個(gè)問(wèn)題的線性規(guī)劃模型為班的營(yíng)業(yè)員，則

9、這個(gè)問(wèn)題的線性規(guī)劃模型為 145671256712367123471234523456345673003003504004806005500,1,2,7jxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxj1.1 線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型 mathematical model of lp星星期期需要需要人數(shù)人數(shù)星星期期需要需要人數(shù)人數(shù)一一300五五480二二300六六600三三350日日550四四4001234567minzxxxxxxx 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page

10、 9 2021-10-31【例【例1-3】合理用料問(wèn)題。某汽車(chē)需要用甲、乙、丙三種規(guī)格的軸各一根，這】合理用料問(wèn)題。某汽車(chē)需要用甲、乙、丙三種規(guī)格的軸各一根，這些軸的規(guī)格分別是些軸的規(guī)格分別是1.5，1，0.7（m），這些軸需要用同一種圓鋼來(lái)做，圓鋼長(zhǎng)），這些軸需要用同一種圓鋼來(lái)做，圓鋼長(zhǎng)度為度為4 m?，F(xiàn)在要制造?，F(xiàn)在要制造1000輛汽車(chē)，最少要用多少圓鋼來(lái)生產(chǎn)這些軸？輛汽車(chē)，最少要用多少圓鋼來(lái)生產(chǎn)這些軸？ 【解】這是一個(gè)條材下料問(wèn)題【解】這是一個(gè)條材下料問(wèn)題 ，設(shè)切口寬度為零。，設(shè)切口寬度為零。 設(shè)一根圓鋼切割成甲、設(shè)一根圓鋼切割成甲、乙、丙三種軸的根數(shù)分別為乙、丙三種軸的根數(shù)分別為y1，

11、y2，y3,則切割方式可用不等式則切割方式可用不等式1.5y1+y2+0.7y34表示，求這個(gè)不等式關(guān)于表示，求這個(gè)不等式關(guān)于y1，y2，y3的非負(fù)整數(shù)解。象這樣的非負(fù)整數(shù)解。象這樣的非負(fù)整數(shù)解共有的非負(fù)整數(shù)解共有10組，也就是有組，也就是有10種下料方式，如表種下料方式，如表1-3所示。所示。表表1-3 下料方案下料方案 方案方案規(guī)格規(guī)格 1234 5678910需求量需求量y1(根根) 221 11 0 00001000y2 102 10 4 32101000y3 010 23 0 12451000余料（余料（m）00.30.5 0.1o.4 00.30.60.20.51.1 線性規(guī)劃的數(shù)

12、學(xué)模型線性規(guī)劃的數(shù)學(xué)模型 mathematical model of lp 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 10 2021-10-31設(shè)設(shè)xj(j=1,2,10)為第為第j種下料方案所用圓鋼的根數(shù)。則用料最少種下料方案所用圓鋼的根數(shù)。則用料最少數(shù)學(xué)模型數(shù)學(xué)模型求下料方案時(shí)應(yīng)注意，余料不能超過(guò)最短毛坯的長(zhǎng)度；最好將毛求下料方案時(shí)應(yīng)注意，余料不能超過(guò)最短毛坯的長(zhǎng)度；最好將毛坯長(zhǎng)度按降的次序排列，即先切割長(zhǎng)度最長(zhǎng)的毛坯，再切割次長(zhǎng)坯長(zhǎng)度按降的次序排列，即先切割長(zhǎng)度最長(zhǎng)的毛坯，再切割次長(zhǎng)的，最后切割最短的，不能

13、遺漏了方案的，最后切割最短的，不能遺漏了方案 。如果方案較多，用計(jì)。如果方案較多，用計(jì)算機(jī)編程排方案，去掉余料較長(zhǎng)的方案，進(jìn)行初選。算機(jī)編程排方案，去掉余料較長(zhǎng)的方案，進(jìn)行初選。102 , 1, 010005423210002342100022min10987542987643154321101，jxxxxxxxxxxxxxxxxxxxxxzjjj1.1 線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型 mathematical model of lp 方案方案規(guī)格規(guī)格 1234 5678910需求量需求量y1(根根) 221 11 0 00001000y2 102 10 4 32101000y3 010

14、 23 0 12451000余料（余料（m）00.30.5 0.1o.4 00.30.60.20.5 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 11 2021-10-311.1.2 線性規(guī)劃的一般模型線性規(guī)劃的一般模型一般地，假設(shè)線性規(guī)劃數(shù)學(xué)模型中，有一般地，假設(shè)線性規(guī)劃數(shù)學(xué)模型中，有m個(gè)約束，有個(gè)約束，有n個(gè)決策變量個(gè)決策變量xj, j=1,2,n，目標(biāo)函數(shù)的變量系數(shù)用，目標(biāo)函數(shù)的變量系數(shù)用cj表示表示, cj稱為稱為價(jià)值系數(shù)價(jià)值系數(shù)。約。約束條件的變量系數(shù)用束條件的變量系數(shù)用aij表示，表示，aij稱為稱為工

15、藝系數(shù)工藝系數(shù)。約束條件右端的。約束條件右端的常數(shù)用常數(shù)用bi表示，表示，bi稱為稱為資源限量資源限量。則線性規(guī)劃數(shù)學(xué)模型的一般表達(dá)。則線性規(guī)劃數(shù)學(xué)模型的一般表達(dá)式可寫(xiě)成式可寫(xiě)成1 1221111221121 1222221 122max(min)(, )(, )(, )0,1,2,nnnnnnmmmnnmjzc xc xc xa xa xa xba xa xa xba xaxaxbxjn 或或或?yàn)榱藭?shū)寫(xiě)方便，上式也可寫(xiě)成：為了書(shū)寫(xiě)方便，上式也可寫(xiě)成： 1.1 線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型 mathematical model of lp 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 cha

16、pter 1 線性規(guī)劃線性規(guī)劃linear programming page 12 2021-10-3111max(min)(, )1,2,0,1,2,njjjnijjijjzc xa xbimxjn 或在實(shí)際中一般在實(shí)際中一般xj0,但有時(shí)但有時(shí)xj0或或xj無(wú)符號(hào)限制。無(wú)符號(hào)限制。1.1 線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型 mathematical model of lp 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 13 2021-10-311.什么是線性規(guī)劃，掌握線性規(guī)劃在管理中的什么是線性規(guī)劃，掌握線性規(guī)

17、劃在管理中的幾個(gè)應(yīng)用例子幾個(gè)應(yīng)用例子2.線性規(guī)劃數(shù)學(xué)模型的組成及其特征線性規(guī)劃數(shù)學(xué)模型的組成及其特征3.線性規(guī)劃數(shù)學(xué)模型的一般表達(dá)式。線性規(guī)劃數(shù)學(xué)模型的一般表達(dá)式。作業(yè)：教材習(xí)題作業(yè)：教材習(xí)題 1.11.61.1 線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型 mathematical model of lp下一節(jié)：圖解法下一節(jié)：圖解法2021-10-311.2 圖解法圖解法 graphical method 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 15 2021-10-31x1x2o1020304010203040(3

18、00,400)(15,10)最優(yōu)解最優(yōu)解x=(15,10)最優(yōu)值最優(yōu)值z(mì)=850040221xx305 . 121xx0, 0305 . 1402212121xxxxxx例例1-712max300400zxx1.2 圖解法圖解法the graphical method 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 16 2021-10-31246x1x2246最優(yōu)解最優(yōu)解x=(3,1)最優(yōu)值最優(yōu)值z(mì)=5(3,1)006346321212121xxxxxxxx、min z=x1+2x2例例1-8(1,2)1.2 圖解法

19、圖解法the graphical method 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 17 2021-10-31246x1x2246x（2）（3,1）x（1）（1,3）(5,5)006346321212121xxxxxxxx、min z=5x1+5x2例例1-9有無(wú)窮多個(gè)最優(yōu)解有無(wú)窮多個(gè)最優(yōu)解即具有多重解即具有多重解,通解為通解為 01 ,)1 ()2() 1 (xxx 當(dāng)當(dāng)=0.5時(shí)時(shí)=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2) 1.2 圖解法圖解法the graphical metho

20、d 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 18 2021-10-31246x1x2246(1,2)006346321212121xxxxxxxx、無(wú)界解無(wú)界解(無(wú)最優(yōu)解無(wú)最優(yōu)解)max z=x1+2x2例例1-101.2 圖解法圖解法the graphical method 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 19 2021-10-31x1x2o102030401020304050500,050305 .140221212

21、121xxxxxxxx無(wú)可行解無(wú)可行解即無(wú)最優(yōu)解即無(wú)最優(yōu)解max z=10 x1+4x2例例1-111.2 圖解法圖解法the graphical method 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 20 2021-10-31由以上例題可知，線性規(guī)劃的解有由以上例題可知，線性規(guī)劃的解有4種形式種形式：1.有唯一最優(yōu)解有唯一最優(yōu)解(例例1-7例例1-8)2.有多重解有多重解(例例1-9)3.有無(wú)界解有無(wú)界解(例例1-10)4.無(wú)可行解無(wú)可行解(例例1-11)1、2情形為有最優(yōu)解情形為有最優(yōu)解3、4情形為無(wú)最優(yōu)解

22、情形為無(wú)最優(yōu)解1.2 圖解法圖解法the graphical method 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 21 2021-10-31圖解法的步驟：圖解法的步驟：1.求可行解集合。求可行解集合。分別求出滿足每個(gè)約束包括變量非分別求出滿足每個(gè)約束包括變量非 負(fù)要求負(fù)要求的區(qū)域，其交集就是可行解集合，或稱為的區(qū)域，其交集就是可行解集合，或稱為可行域可行域；2.繪制目標(biāo)函數(shù)圖形。繪制目標(biāo)函數(shù)圖形。先過(guò)原點(diǎn)作一條矢量指向點(diǎn)（先過(guò)原點(diǎn)作一條矢量指向點(diǎn)（c1,c2)，矢，矢量的方向就是目標(biāo)函數(shù)增加的方向，稱為梯度方

23、向，再作一量的方向就是目標(biāo)函數(shù)增加的方向，稱為梯度方向，再作一條與矢量垂直的直線，這條直線就是目標(biāo)函數(shù)圖形；條與矢量垂直的直線，這條直線就是目標(biāo)函數(shù)圖形；3.求最優(yōu)解。求最優(yōu)解。依據(jù)目標(biāo)函數(shù)求最大或最小移動(dòng)目標(biāo)函數(shù)直線，依據(jù)目標(biāo)函數(shù)求最大或最小移動(dòng)目標(biāo)函數(shù)直線，直線與可行域相交的點(diǎn)對(duì)應(yīng)的坐標(biāo)就是直線與可行域相交的點(diǎn)對(duì)應(yīng)的坐標(biāo)就是最優(yōu)解。最優(yōu)解。一般地，將目標(biāo)函數(shù)直線放在可行域中一般地，將目標(biāo)函數(shù)直線放在可行域中 求最大值時(shí)直線沿著矢量方向移動(dòng)求最大值時(shí)直線沿著矢量方向移動(dòng) 求最小值時(shí)沿著矢量的反方向移動(dòng)求最小值時(shí)沿著矢量的反方向移動(dòng)1.2 圖解法圖解法the graphical method

24、制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 22 2021-10-311.通過(guò)圖解法了解線性規(guī)劃有幾種解的形式通過(guò)圖解法了解線性規(guī)劃有幾種解的形式2.作圖的關(guān)鍵有三點(diǎn)作圖的關(guān)鍵有三點(diǎn) (1)可行解區(qū)域要畫(huà)正確可行解區(qū)域要畫(huà)正確 (2)目標(biāo)函數(shù)增加的方向不能畫(huà)錯(cuò)目標(biāo)函數(shù)增加的方向不能畫(huà)錯(cuò) (3)目標(biāo)函數(shù)的直線怎樣平行移動(dòng)目標(biāo)函數(shù)的直線怎樣平行移動(dòng)作業(yè)：教材習(xí)題作業(yè)：教材習(xí)題 1.7 1.2 圖解法圖解法the graphical method下一節(jié)：線性規(guī)劃的標(biāo)準(zhǔn)型下一節(jié)：線性規(guī)劃的標(biāo)準(zhǔn)型2021-10-311.3

25、線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型standard form of lp 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 24 2021-10-31 在用單純法求解線性規(guī)劃問(wèn)題時(shí)，為了討論問(wèn)題在用單純法求解線性規(guī)劃問(wèn)題時(shí)，為了討論問(wèn)題方便，需將線性規(guī)劃模型化為統(tǒng)一的標(biāo)準(zhǔn)形式。方便，需將線性規(guī)劃模型化為統(tǒng)一的標(biāo)準(zhǔn)形式。1.3 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型standard form of lp線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型為線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型為:1目標(biāo)函數(shù)求最大值（或求最小值）目標(biāo)函數(shù)求最大值（或求最小值）2約束條件都為等式方程

26、約束條件都為等式方程3變量變量xj非負(fù)非負(fù)4常數(shù)常數(shù)bi非負(fù)非負(fù) 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 25 2021-10-31mibnjxbxaxaxabxaxaxabxaxaxaijmnmnmmnnnn,2, 1,0,2, 1,02211222222111212111max(或min)z=c1x1+c2x2+cnxn1.3 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型standard form of lp注：本教材默認(rèn)目標(biāo)函數(shù)是注：本教材默認(rèn)目標(biāo)函數(shù)是 max 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter

27、 1 線性規(guī)劃線性規(guī)劃linear programming page 26 2021-10-31njjjxcz1maxminjxbxajnjijij, 2 , 1, 2 , 1, 010maxxbaxcxz或?qū)懗上铝行问交驅(qū)懗上铝行问剑?或用矩陣形式或用矩陣形式1.3 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型standard form of lp 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 27 2021-10-31111211121222221212, , , )nnnmmm nnmaaaxbaaaxbaxbcc cca

28、aaxb ； (通常通常x記為：記為： 稱為約束方稱為約束方程的系數(shù)矩陣，程的系數(shù)矩陣，m是約束方程的個(gè)數(shù)，是約束方程的個(gè)數(shù)，n是決策變量的個(gè)數(shù)，是決策變量的個(gè)數(shù)，一般情況一般情況mn，且，且r()m。tnxxxx),21（m ax0zc xa xbx其中其中:1.3 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型standard form of lp 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 28 2021-10-31【例【例1-12】將下列線性規(guī)劃化為標(biāo)準(zhǔn)型】將下列線性規(guī)劃化為標(biāo)準(zhǔn)型 3213minxxxz無(wú)符號(hào)要求、32

29、132132132100)3(523)2(3) 1 (82xxxxxxxxxxxx【解】（）因?yàn)椤窘狻浚ǎ┮驗(yàn)閤3無(wú)符號(hào)要求無(wú)符號(hào)要求 ，即，即x3取正值也取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以令可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以令 0,33333 xxxxx其中1.3 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型standard form of lp 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 29 2021-10-31 (3)第二個(gè)約束條件是第二個(gè)約束條件是號(hào)，在號(hào)，在號(hào)號(hào) 左左端減去剩余變量端減去剩余變量(sur

30、plus variable)x5，x50。也稱松馳變。也稱松馳變量量3213minxxxz無(wú)符號(hào)要求、32132132132100) 3(523)2(3) 1 (82xxxxxxxxxxxx1.3 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型standard form of lp(2) 第一個(gè)約束條件是第一個(gè)約束條件是號(hào)，在號(hào)，在左端左端加入松馳變量加入松馳變量 (slack variable) x4，x40,化為等式；化為等式；(4)第三個(gè)約束條件是第三個(gè)約束條件是號(hào)且常數(shù)項(xiàng)為負(fù)數(shù)，因此在號(hào)且常數(shù)項(xiàng)為負(fù)數(shù)，因此在左邊加入松左邊加入松馳變量馳變量x6，x60，同時(shí)兩邊乘以，同時(shí)兩邊乘以1。 （5）目標(biāo)函數(shù)

31、是最小值，為了化為求最大值，令）目標(biāo)函數(shù)是最小值，為了化為求最大值，令z=z,得到得到max z=z，即當(dāng)，即當(dāng)z達(dá)到最小值時(shí)達(dá)到最小值時(shí)z達(dá)到最大值，反之亦然。達(dá)到最大值，反之亦然。 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 30 2021-10-31綜合起來(lái)得到下列標(biāo)準(zhǔn)型綜合起來(lái)得到下列標(biāo)準(zhǔn)型 332133maxxxxxz 05)(233826543321633215332143321xxxxxxxxxxxxxxxxxxxxxx、1.3 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型standard form of lp

32、制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 31 2021-10-31 當(dāng)某個(gè)變量當(dāng)某個(gè)變量xj0時(shí)時(shí),令令x/j=xj 。 當(dāng)某個(gè)約束是絕對(duì)值不等式當(dāng)某個(gè)約束是絕對(duì)值不等式時(shí)，將絕對(duì)值不等式化為兩個(gè)不等式，再化為等式，例如約束時(shí)，將絕對(duì)值不等式化為兩個(gè)不等式，再化為等式，例如約束 974321xxx將其化為兩個(gè)不等式將其化為兩個(gè)不等式 974974321321xxxxxx再加入松馳變量化為等式。再加入松馳變量化為等式。 1.3 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型standard form of lp 制作與教學(xué) 武

33、漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 32 2021-10-31【例例1-13】將下例線性規(guī)劃化為標(biāo)準(zhǔn)型】將下例線性規(guī)劃化為標(biāo)準(zhǔn)型無(wú)約束、211212145|maxxxxxxxxz【解】解】 此題關(guān)鍵是將目標(biāo)函數(shù)中的絕對(duì)值去掉。此題關(guān)鍵是將目標(biāo)函數(shù)中的絕對(duì)值去掉。令令 0000000000002222222211111111xxxxxxxxxxxxxxxx，222222111111,|,|xxxxxxxxxxxx 則有則有1.3 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型standard form of lp 制作與教學(xué) 武漢理工大

34、學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 33 2021-10-31得到線性規(guī)劃的標(biāo)準(zhǔn)形式得到線性規(guī)劃的標(biāo)準(zhǔn)形式 112211223114112234max()()540zxxxxxxxxxxxxxxxxxx 、 、 、 、 、1.3 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型standard form of lp對(duì)于對(duì)于axb(a、b均大于零均大于零)的有界變量化為標(biāo)準(zhǔn)形式有兩種方的有界變量化為標(biāo)準(zhǔn)形式有兩種方法。法。 一種方法是增加兩個(gè)約束一種方法是增加兩個(gè)約束xa及及xb 另一種方法是令另一種方法是令x=xa，則，則axb等價(jià)于等價(jià)于0

35、xba，增加，增加一個(gè)約束一個(gè)約束xba并且將原問(wèn)題所有并且將原問(wèn)題所有x用用x= x+a替換。替換。 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 34 2021-10-311.如何化標(biāo)準(zhǔn)形式？如何化標(biāo)準(zhǔn)形式？ 可以對(duì)照四條標(biāo)準(zhǔn)逐一判斷！可以對(duì)照四條標(biāo)準(zhǔn)逐一判斷！ 標(biāo)準(zhǔn)形式是人為定義的，目標(biāo)函數(shù)可以是求最小值。標(biāo)準(zhǔn)形式是人為定義的，目標(biāo)函數(shù)可以是求最小值。2.用用winqsb軟件求解時(shí)，不必化成標(biāo)準(zhǔn)型。軟件求解時(shí)，不必化成標(biāo)準(zhǔn)型。圖解法時(shí)不必化為標(biāo)準(zhǔn)型。圖解法時(shí)不必化為標(biāo)準(zhǔn)型。3.單純形法求解時(shí)一定要化為標(biāo)準(zhǔn)型。單

36、純形法求解時(shí)一定要化為標(biāo)準(zhǔn)型。作業(yè)：教材習(xí)題作業(yè)：教材習(xí)題 1.81.3 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型standard form of lp下一節(jié)：基本概念下一節(jié)：基本概念2021-10-311.4 線性規(guī)劃的有關(guān)概念線性規(guī)劃的有關(guān)概念basic concepts of lp 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 36 2021-10-31 設(shè)線性規(guī)劃的標(biāo)準(zhǔn)型設(shè)線性規(guī)劃的標(biāo)準(zhǔn)型 max z=cx （1.1） ax=b （1.2） x 0 （1.3）式中式中a 是是mn矩陣，矩陣，mn并且并且r（a）=m，

37、顯然，顯然a中至少有中至少有一個(gè)一個(gè)mm子矩陣子矩陣b，使得，使得r（b）=m。1.4 基本概念基本概念basic concepts 基基 (basis)a中中mm子矩陣子矩陣b并且有并且有r（b）=m，則稱，則稱b是線性規(guī)是線性規(guī)劃的一個(gè)基（或基矩陣劃的一個(gè)基（或基矩陣basis matrix ）。當(dāng)）。當(dāng)m=n時(shí)，基矩陣唯一，時(shí)，基矩陣唯一，當(dāng)當(dāng)mn時(shí)，基矩陣就可能有多個(gè)，但數(shù)目不超過(guò)時(shí)，基矩陣就可能有多個(gè)，但數(shù)目不超過(guò)mnc 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 37 2021-10-31【例【例1-1

38、4】線性規(guī)劃】線性規(guī)劃 32124maxxxxz5 , 1, 0226103553214321jxxxxxxxxxj 求所有基矩陣求所有基矩陣。 【解】約束方程的系數(shù)矩陣為【解】約束方程的系數(shù)矩陣為25矩陣矩陣 10261001115a,610151b,010152b,110053b26114b10019b,12017b,02118b,16016b,06115b容易看出容易看出r(a)=2，2階子矩陣有階子矩陣有c52=10個(gè)，其中第個(gè)，其中第1列與第列與第3列構(gòu)成列構(gòu)成的的2階矩陣不是一個(gè)基，基矩陣只有階矩陣不是一個(gè)基，基矩陣只有9個(gè)，即個(gè)，即1.4 基本概念基本概念basic concep

39、ts 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 38 2021-10-31由線性代數(shù)知，基矩陣由線性代數(shù)知，基矩陣b必為非奇異矩陣并且必為非奇異矩陣并且|b|0。當(dāng)矩。當(dāng)矩陣陣b的行列式等式零即的行列式等式零即|b|=0時(shí)就不是基時(shí)就不是基 當(dāng)確定某一矩陣為基矩陣時(shí)，則基矩陣對(duì)應(yīng)的列向量稱為當(dāng)確定某一矩陣為基矩陣時(shí)，則基矩陣對(duì)應(yīng)的列向量稱為基基向量向量(basis vector)，其余列向量稱為，其余列向量稱為非基向量非基向量 基向量對(duì)應(yīng)的變量稱為基向量對(duì)應(yīng)的變量稱為基變量基變量(basis variable)，

40、非基向量，非基向量對(duì)應(yīng)的變量稱為對(duì)應(yīng)的變量稱為非基變量非基變量 在上例中在上例中b2的基向量是的基向量是a中的第一列和第四列，其余列向量中的第一列和第四列，其余列向量是非基向量，是非基向量，x1、x4是基變量，是基變量，x2、x3、x5是非基變量。基變是非基變量?；兞?、非基變量是針對(duì)某一確定基而言的，不同的基對(duì)應(yīng)的基量、非基變量是針對(duì)某一確定基而言的，不同的基對(duì)應(yīng)的基變量和非基變量也不同。變量和非基變量也不同。010152b10261001115a1.4 基本概念基本概念basic concepts 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear p

41、rogramming page 39 2021-10-31可行解可行解(feasible solution) 滿足式（滿足式（1.2）及（）及（1.3）的解）的解x=（x1,x2，xn)t 稱為可行解稱為可行解 ?；究尚薪饣究尚薪?basis feasible solution) 若基本解是可行解則稱若基本解是可行解則稱為是基本可行解（也稱基可行解）。為是基本可行解（也稱基可行解）。 例如，例如， 與與x=（0，0，0，3，2，）都是例，）都是例1 的可行解。的可行解。 tx) 1 ,27,21, 0 , 0( 基本解基本解(basis solution) 對(duì)某一確定的基對(duì)某一確定的基b，

42、令非基變量等于零，令非基變量等于零，利用式（利用式（1.） 解出基變量，則這組解稱為基解出基變量，則這組解稱為基的基的基本解。本解。 最優(yōu)解最優(yōu)解(optimal solution) 滿足式滿足式 （1 .1）的可行解稱為最優(yōu)解，）的可行解稱為最優(yōu)解，即是使得目標(biāo)函數(shù)達(dá)到最大值的可行解就是最優(yōu)解，例即是使得目標(biāo)函數(shù)達(dá)到最大值的可行解就是最優(yōu)解，例如可行解如可行解 是例是例2的最優(yōu)解。的最優(yōu)解。tx)8 ,0,0,0,53(非可行解非可行解(infeasible solution) 無(wú)界解無(wú)界解 (unbound solution)1.4 基本概念基本概念basic concepts 制作與教學(xué)

43、 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 40 2021-10-31顯然，只要基本解中的基變量的解滿足式（顯然，只要基本解中的基變量的解滿足式（1.）的非負(fù)要求，）的非負(fù)要求，那么這個(gè)基本解就是基本可行解。那么這個(gè)基本解就是基本可行解。 在例在例1-13中，對(duì)中，對(duì)來(lái)說(shuō)，來(lái)說(shuō)，x1,x2是基變量，是基變量，x3,x4，x5是非基變量，是非基變量，令令x3=x4=x5=0，則式（，則式（1.）為）為2610352121xxxx,610151b對(duì)對(duì)b2來(lái)說(shuō)，來(lái)說(shuō)，x1,x4,為基變量，令非基變量為基變量，令非基變量x2,x3,

44、x5為零，由式為零，由式（1.2）得到）得到 ，x4=4，511x因因|b1|，由克萊姆法則知，由克萊姆法則知，x1、x2有唯一解有唯一解x12/5,x2=1則則 基基本解為本解為tx)0 , 0 , 0 , 1 ,52()1(1.4 基本概念基本概念basic concepts 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 41 2021-10-31由于由于 是基本解，從而它是基本可行解，在是基本解，從而它是基本可行解，在 中中x10i表表1-6(a)xbx1x2x3x4bx3211040 x413/20130j3

45、0040000 (b)x3x2j (c)x1 x210 j 基變量基變量120002/302/3204/31- -2/340100/30- -800/330103/4- -1/21501- -1/2 11000- -25- -250將將3/2化為化為11.5 單純形法單純形法 simplex method2015 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 54 2021-10-31最優(yōu)解最優(yōu)解x=(15，10，0，0)t，最優(yōu)值，最優(yōu)值z(mì)=8500x(1)=(0,0)x11.5 單純形法單純形法 simplex

46、methodx1x2o102030401020304040221xx305 . 121xx0, 0305 . 1402212121xxxxxx12max300400zxxx(2)=(0,20)x(3)=(15,10) 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 55 2021-10-31單純形法全過(guò)程的計(jì)算，可以用列表的方法計(jì)算更為簡(jiǎn)潔，單純形法全過(guò)程的計(jì)算，可以用列表的方法計(jì)算更為簡(jiǎn)潔，這種表格稱為單純形表（表這種表格稱為單純形表（表1-6）。）。計(jì)算步驟：計(jì)算步驟：1.求初始基可行解，列出初始單純形表，求出檢驗(yàn)

47、數(shù)。其中求初始基可行解，列出初始單純形表，求出檢驗(yàn)數(shù)。其中基變量的檢驗(yàn)數(shù)必為零；基變量的檢驗(yàn)數(shù)必為零； 2.判斷：判斷： （a）若）若j（j，n）得到最優(yōu)解；）得到最優(yōu)解； （b）某個(gè)）某個(gè)k0且且aik（i=1，2,m）則線性規(guī)劃具有無(wú)）則線性規(guī)劃具有無(wú)界解界解(見(jiàn)例見(jiàn)例1-18)。 （c）若存在）若存在k0且且aik (i=1,m)不全非正，則進(jìn)行換基；不全非正，則進(jìn)行換基；1.5 單純形法單純形法 simplex method 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 56 2021-10-31min0,0

48、,iilikikikikbbaam maa當(dāng) 時(shí)為任意大的正數(shù)第第個(gè)比值最小個(gè)比值最小 ，選最小比值對(duì)應(yīng)行的基變量為出基變量，選最小比值對(duì)應(yīng)行的基變量為出基變量，若有相同最小比值，則任選一個(gè)。若有相同最小比值，則任選一個(gè)。alk為主元素；為主元素； (c）求新的基可行解：用初等行變換方法將）求新的基可行解：用初等行變換方法將alk 化為化為,k列列其它元素化為零（包括檢驗(yàn)數(shù)行）得到新的可行基及基本可其它元素化為零（包括檢驗(yàn)數(shù)行）得到新的可行基及基本可行解，再判斷是否得到最優(yōu)解。行解，再判斷是否得到最優(yōu)解。（b）選出基變量）選出基變量 ，求最小比值：，求最小比值：1.5 單純形法單純形法 sim

49、plex method3.換基：換基：（a）選進(jìn)基變量）選進(jìn)基變量設(shè)設(shè)k=max j | j 0,xk為進(jìn)基變量為進(jìn)基變量 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 57 2021-10-31【例【例1-16】 用單純形法求解用單純形法求解3212maxxxxz02053115232321321321xxxxxxxxx、【解】將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：【解】將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：3212maxxxxz5 , 2 , 1, 0205311523253214321jxxxxxxxxxj不難看出不難看出x4、x5可作為

50、初始基變量，單純法計(jì)算結(jié)果如可作為初始基變量，單純法計(jì)算結(jié)果如表表 1-7所示所示 。 1.5 單純形法單純形法 simplex method 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 58 2021-10-31cj12100bcbxbx1x2x3x4x50 x423210150 x51/3150120j12100 0 x42x2j 1x1 2x2 j 表表171/3150120301713751/30902m2025601017/31/31250128/91/92/335/30098/91/97/3最優(yōu)解最優(yōu)解

51、x=(25，35/3，0，0，0)t，最優(yōu)值，最優(yōu)值z(mì)=145/31.5 單純形法單純形法 simplex method 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 59 2021-10-31【例【例1-17】用單純形法求解】用單純形法求解 42122minxxxz5 , 1, 0212665521421321jxxxxxxxxxxj【解】【解】 這是一個(gè)極小化的線性規(guī)劃問(wèn)題這是一個(gè)極小化的線性規(guī)劃問(wèn)題,可以將其化為極大化問(wèn)可以將其化為極大化問(wèn)題求解題求解,也可以直接求解也可以直接求解,這時(shí)判斷標(biāo)準(zhǔn)是：這時(shí)判斷標(biāo)準(zhǔn)

52、是：j0(j=1，n)時(shí)得時(shí)得到最優(yōu)解到最優(yōu)解。容易觀察到容易觀察到,系數(shù)矩陣中有一個(gè)系數(shù)矩陣中有一個(gè)3階單位矩陣階單位矩陣,x3、x4、x5為基變量為基變量。目標(biāo)函數(shù)中含有基變量。目標(biāo)函數(shù)中含有基變量x4,由第二個(gè)約束得到由第二個(gè)約束得到x4=6+x1x2，并代，并代入目標(biāo)函數(shù)消去入目標(biāo)函數(shù)消去x4得得12121222(6)6zxxxxxx 1.5 單純形法單純形法 simplex method 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 60 2021-10-31xbx1x2x3x4x5bx3x4x51- -1

53、611210001000156215621/2j1- -1000 x2x4x51- -241001- -1- -20100015111 j20100 表中表中j0,j=1,2,5所以最優(yōu)解為所以最優(yōu)解為x=(0,5,0,1,11,)最優(yōu)值最優(yōu)值 z=2x12x2x4=251=11極小值問(wèn)題極小值問(wèn)題,注意判斷標(biāo)準(zhǔn)注意判斷標(biāo)準(zhǔn),選進(jìn)基變量時(shí)選進(jìn)基變量時(shí),應(yīng)選應(yīng)選j0, x2進(jìn)基，而進(jìn)基，而a120，a220且且aik（i=1，2,m）則線）則線性規(guī)劃具有無(wú)界解性規(guī)劃具有無(wú)界解退化基本可行解的判斷退化基本可行解的判斷:存在某個(gè)基變量為零的基本可存在某個(gè)基變量為零的基本可行解。行解。1.5 單純形法

54、單純形法 simplex method 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 67 2021-10-31在實(shí)際問(wèn)題中有些模型并不含有單位矩陣，為了得到一組基向在實(shí)際問(wèn)題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大基稱為人工基，用大m法或兩階段法求解，這種用人工變量作法或兩階段法求

55、解，這種用人工變量作橋梁的求解方法稱為人工變量法。橋梁的求解方法稱為人工變量法。【例【例1-20】用大】用大m法解法解 下列線性規(guī)劃下列線性規(guī)劃012210243423max321321321321321xxxxxxxxxxxxxxxz、1. 大大m 單純形法單純形法1.5.2大大m和兩階段單純形法和兩階段單純形法1.5 單純形法單純形法 simplex method 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 68 2021-10-31【解】首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式【解】首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式5 , 2 ,

56、 1, 012210243423max32153214321321jxxxxxxxxxxxxxxxzj式中式中x4，x5為松弛變量，為松弛變量，x5可作為可作為一個(gè)基變量，第一、三約束中分一個(gè)基變量，第一、三約束中分別加入人工變量別加入人工變量x6、x7，目標(biāo)函，目標(biāo)函數(shù)中加入數(shù)中加入mx6mx7一項(xiàng)，得到一項(xiàng)，得到人工變量單純形法數(shù)學(xué)模型人工變量單純形法數(shù)學(xué)模型用前面介紹的單純形法求用前面介紹的單純形法求解，見(jiàn)下表。解，見(jiàn)下表。 7 , 2 , 1, 012210243423max732153216432176321jxxxxxxxxxxxxxxmxmxxxxzj1.5 單純形法單純形法 s

57、implex method2021-10-31cj32100mmbcbxbx1x2x3x4x5x6x7m0mx6x5x74123121211000101000014101j3-2m2+m-1+2mm000m01x6x5x3632532001100010100381j5-6m5m0m00201x2x5x36/53/52/51000011/53/52/50103/531/511/5j50000231x2x1x301010000111025/32/31331/319/3j0005-25/3 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programmin

58、g page 70 2021-10-31（2）初始表中的檢驗(yàn)數(shù)有兩種算法，第一種算）初始表中的檢驗(yàn)數(shù)有兩種算法，第一種算法是利用第一、三約束將法是利用第一、三約束將x6、x7的表達(dá)式代入目的表達(dá)式代入目標(biāo)涵數(shù)消去標(biāo)涵數(shù)消去x6和和x7，得到用非基變量表達(dá)的目標(biāo)，得到用非基變量表達(dá)的目標(biāo)函數(shù)，其系數(shù)就是檢驗(yàn)數(shù)；第二種算法是利用公函數(shù)，其系數(shù)就是檢驗(yàn)數(shù)；第二種算法是利用公式計(jì)算，如式計(jì)算，如最優(yōu)解最優(yōu)解x（31/3，13，19/3，0，0)t；最優(yōu)值；最優(yōu)值z(mì)152/3注意：注意：1.5 單純形法單純形法 simplex method11143( m,0, m)123( m) ( 4)0 1( m

59、)232mbcc p (1) m是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，可是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個(gè)確定數(shù)值以理解為它能大于給定的任何一個(gè)確定數(shù)值 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 71 2021-10-31【例【例1-21】求解線性規(guī)劃】求解線性規(guī)劃 0,426385min21212121xxxxxxxxz【解】加入松馳變量【解】加入松馳變量x3、x4化為標(biāo)準(zhǔn)型化為標(biāo)準(zhǔn)型4 , 2 , 1, 0426385min42132121jxxxxxxxxxz

60、j在第二個(gè)方程中加入人工變量在第二個(gè)方程中加入人工變量x5，目標(biāo)函數(shù)中加上，目標(biāo)函數(shù)中加上m x5一項(xiàng)，一項(xiàng)，得到得到 1.5 單純形法單純形法 simplex method 制作與教學(xué) 武漢理工大學(xué)管理學(xué)院 熊偉 chapter 1 線性規(guī)劃線性規(guī)劃linear programming page 72 2021-10-315 , 2 , 1, 0426385min5421321521jxxxxxxxxmxxxzj用單純形法計(jì)算如下表所示。用單純形法計(jì)算如下表所示。 cj5800mbcbxbx1x2x3x4x50mx3x5311210010164j5m8+2m0m0 5mx1x5101/37/