第一講 線性規(guī)劃應(yīng)用舉例與單純形法

1、運(yùn)籌學(xué)運(yùn)籌學(xué)Operations Research第一講第一講 線性規(guī)劃線性規(guī)劃Linear Programming一、一、 線性規(guī)劃的線性規(guī)劃的數(shù)學(xué)模型與應(yīng)用舉例數(shù)學(xué)模型與應(yīng)用舉例 【例例1】最優(yōu)生產(chǎn)計(jì)劃問(wèn)題最優(yōu)生產(chǎn)計(jì)劃問(wèn)題。某企業(yè)在計(jì)劃期內(nèi)計(jì)劃。某企業(yè)在計(jì)劃期內(nèi)計(jì)劃生產(chǎn)甲、乙、丙三種產(chǎn)品。這些產(chǎn)品分別需要在設(shè)生產(chǎn)甲、乙、丙三種產(chǎn)品。這些產(chǎn)品分別需要在設(shè)備備A、B上加工，需要消耗材料上加工，需要消耗材料C、D，按工藝資料規(guī)，按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工及所需要的資源如定，單件產(chǎn)品在不同設(shè)備上加工及所需要的資源如表表1所示。已知在計(jì)劃期內(nèi)設(shè)備的加工能力各為所示。已知在計(jì)劃期內(nèi)設(shè)備的

2、加工能力各為200臺(tái)時(shí)，可供材料分別為臺(tái)時(shí)，可供材料分別為360、300公斤；每生產(chǎn)一件公斤；每生產(chǎn)一件甲、乙、丙三種產(chǎn)品，企業(yè)可獲得利潤(rùn)分別為甲、乙、丙三種產(chǎn)品，企業(yè)可獲得利潤(rùn)分別為40、30、50元，假定市場(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)收入最大？最大？ 產(chǎn)品產(chǎn)品 資源資源 甲甲 乙乙丙丙現(xiàn)有資源現(xiàn)有資源設(shè)備設(shè)備A 3 1 2 200設(shè)備設(shè)備B 2 2 4 200材料材料C 4 5 1 360材料材料D 2 3 5 300利潤(rùn)利潤(rùn)(元元/件件) 40 30 50表表1 產(chǎn)品

3、資源消耗產(chǎn)品資源消耗線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP321503040maxxxxZ0003005323605420042220023321321321321321xxxxxxxxxxxxxxx，【解解】 設(shè)設(shè)x1、x2、x3 分別為甲、乙、丙三種產(chǎn)品的產(chǎn)分別為甲、乙、丙三種產(chǎn)品的產(chǎn)量量, 則則 數(shù)學(xué)模型為：數(shù)學(xué)模型為： 產(chǎn)品產(chǎn)品 資源資源甲甲 乙乙丙丙現(xiàn)有現(xiàn)有資源資源設(shè)備設(shè)備A 3 1 2 200設(shè)備設(shè)備B 2 2 4 200材料材料C 4 5 1 360材料材料D 2 3 5 300利潤(rùn)利潤(rùn)(元元/件件) 40 30 50線性規(guī)劃的數(shù)學(xué)

4、模型線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP【例例2】某飼料公司用甲、乙兩種原料配制飼料，甲乙某飼料公司用甲、乙兩種原料配制飼料，甲乙兩種原料的營(yíng)養(yǎng)成份及配合飼料中所含各營(yíng)養(yǎng)成份最低兩種原料的營(yíng)養(yǎng)成份及配合飼料中所含各營(yíng)養(yǎng)成份最低量由表量由表2 2給出。已知單位甲、乙原料的價(jià)格分別為給出。已知單位甲、乙原料的價(jià)格分別為1010元元和和2020元，求滿足營(yíng)養(yǎng)需要的飼料最小成本配方。元，求滿足營(yíng)養(yǎng)需要的飼料最小成本配方。 線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP【解解】 設(shè)設(shè)x1、x2分別為甲、乙兩種原料的用料數(shù)量分別為甲、

5、乙兩種原料的用料數(shù)量, 則則 數(shù)學(xué)模型為：數(shù)學(xué)模型為：線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP12min1020Zxx121212121031561500 xxxxxxxx，1 1解決問(wèn)題的目標(biāo)函數(shù)是多個(gè)決策變量的線性函數(shù)，通常是解決問(wèn)題的目標(biāo)函數(shù)是多個(gè)決策變量的線性函數(shù)，通常是 求最大值或最小值求最大值或最小值；2 2解決問(wèn)題的解決問(wèn)題的是一組多個(gè)決策變量的線性不等式或是一組多個(gè)決策變量的線性不等式或等式等式。線性規(guī)劃數(shù)學(xué)模型的線性規(guī)劃數(shù)學(xué)模型的特征：特征：線性規(guī)劃數(shù)學(xué)模型的線性規(guī)劃數(shù)學(xué)模型的三要素：三要素：決策變量決策變量( Decision

6、variables); 目標(biāo)函數(shù)目標(biāo)函數(shù)(Objective function);約束條件約束條件(Constraints);建立一個(gè)問(wèn)題的線性規(guī)劃模型的建立一個(gè)問(wèn)題的線性規(guī)劃模型的一般步驟：一般步驟：確定決策變量；確定決策變量； (2)(2)確定目標(biāo)函數(shù)；確定目標(biāo)函數(shù)； (3)(3)確定約束條件；確定約束條件； (4)(4)確定變量是否有非負(fù)約束。確定變量是否有非負(fù)約束。線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP線性規(guī)劃的一般模型線性規(guī)劃的一般模型一般地一般地，假設(shè)線性規(guī)劃數(shù)學(xué)模型中假設(shè)線性規(guī)劃數(shù)學(xué)模型中, ,有有m個(gè)約束個(gè)約束, ,有有n個(gè)決策變

7、量個(gè)決策變量xj(j=1,2,n)，目標(biāo)函數(shù)的變量系數(shù)用目標(biāo)函數(shù)的變量系數(shù)用cj表示表示, , cj稱為稱為價(jià)值系數(shù)價(jià)值系數(shù)。約束條件的變量系數(shù)用約束條件的變量系數(shù)用aij表示表示，aij稱為稱為工藝系數(shù)工藝系數(shù)。約束條件右約束條件右端的常數(shù)用端的常數(shù)用bi 表示表示，bi 稱為稱為資源限量資源限量。則線性規(guī)劃數(shù)學(xué)模型的則線性規(guī)劃數(shù)學(xué)模型的一般表達(dá)式可寫(xiě)成一般表達(dá)式可寫(xiě)成1 1221111221121 1222221 122max(min)(, )(, )(, )0,1,2,nnnnnnmmmnnmjZc xc xc xa xa xa xba xa xa xba xaxaxbxjn 或或或LL

8、LL L L L L L L L L L L L L L LLL線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP11max(min)(, )1,2,0,1,2,njjjnijjijjZc xa xbimxjn 或LL在實(shí)際中一般在實(shí)際中一般xj0, 但有時(shí)但有時(shí) xj0或或 xj 無(wú)符號(hào)限制。無(wú)符號(hào)限制。為了書(shū)寫(xiě)方便，上式也可寫(xiě)成：為了書(shū)寫(xiě)方便，上式也可寫(xiě)成： 線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 【例例3】某農(nóng)戶計(jì)劃用某農(nóng)戶計(jì)劃用12公頃耕地生產(chǎn)玉米，大豆和公頃耕地生產(chǎn)玉米，大豆和地瓜，可投入地瓜，可投入

9、48個(gè)勞動(dòng)日，資金個(gè)勞動(dòng)日，資金360元。生產(chǎn)玉米元。生產(chǎn)玉米1公公頃，需頃，需6個(gè)勞動(dòng)日，資金個(gè)勞動(dòng)日，資金36元，可獲凈收入元，可獲凈收入200元；生元；生產(chǎn)產(chǎn)1公頃大豆，需公頃大豆，需6個(gè)勞動(dòng)日，資金個(gè)勞動(dòng)日，資金24元，可獲凈收入元，可獲凈收入150元；生產(chǎn)元；生產(chǎn)1公頃地瓜需公頃地瓜需2個(gè)勞動(dòng)日，資金個(gè)勞動(dòng)日，資金18元，可元，可獲凈收入獲凈收入120元，問(wèn)怎樣安排才能使總的凈收入最高。元，問(wèn)怎樣安排才能使總的凈收入最高。 【解解】 設(shè)農(nóng)戶種玉米、大豆及地瓜的數(shù)量分別為設(shè)農(nóng)戶種玉米、大豆及地瓜的數(shù)量分別為x1、x2、x3 公頃，公頃， 則數(shù)學(xué)模型為：則數(shù)學(xué)模型為：線性規(guī)劃的數(shù)學(xué)模型線

10、性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP123max200150120Zxxx1231231231231266248362418360000 xxxxxxxxxxxx，線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP【例例4】某商場(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è)員如表如表3所示。所示。表表3 營(yíng)業(yè)員需要量統(tǒng)計(jì)表營(yíng)業(yè)員需要量統(tǒng)計(jì)表問(wèn)：?jiǎn)枺荷虉?chǎng)人力資源部應(yīng)如何安排每天的上班人數(shù)，使商商場(chǎng)人力資源部

11、應(yīng)如何安排每天的上班人數(shù)，使商場(chǎng)總的營(yíng)業(yè)員最少？場(chǎng)總的營(yíng)業(yè)員最少？ 星期星期需要人數(shù)需要人數(shù)星期星期需要人數(shù)需要人數(shù)一一300五五480二二300六六600三三350日日550四四400線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP7,2, 1,0550600480400350300300min765436543254321743217632176521765417654321jxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZj線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP【

12、解解】 設(shè)設(shè) ( j=1,2, ,7)為休息為休息2天后星期一到星期日天后星期一到星期日開(kāi)始上班的營(yíng)業(yè)員，則這個(gè)問(wèn)題的線性規(guī)劃模型為開(kāi)始上班的營(yíng)業(yè)員，則這個(gè)問(wèn)題的線性規(guī)劃模型為 jx【例例5】投資問(wèn)題。某投資公司在第一年有投資問(wèn)題。某投資公司在第一年有200萬(wàn)元資萬(wàn)元資金，每年都有如下的投資方案可供考慮采納：金，每年都有如下的投資方案可供考慮采納：“假使第假使第一年投入一筆資金，第二年又繼續(xù)投入此資金的一年投入一筆資金，第二年又繼續(xù)投入此資金的50%，那么到第三年就可回收第一年投入資金的一倍金額那么到第三年就可回收第一年投入資金的一倍金額”。投資公司決定最優(yōu)的投資策略使第六年所掌握的資金投資公

13、司決定最優(yōu)的投資策略使第六年所掌握的資金最多。最多。【解解】設(shè)設(shè) x1：第一年的投資；：第一年的投資； x2：第一年的預(yù)留資金；：第一年的預(yù)留資金； x3：第二年新的投資；：第二年新的投資；x4：第二年的預(yù)留資金；：第二年的預(yù)留資金； x5：第三年新的投資；：第三年新的投資； x6：第三年的預(yù)留資金；：第三年的預(yù)留資金； x7：第四年新的投資；：第四年新的投資； x8：第四年的預(yù)留資金；：第四年的預(yù)留資金； x9：第五年的預(yù)留資金；：第五年的預(yù)留資金； 線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 第五年：第五年：(x7/2+x9)=x8+2x5 第三

14、年：第三年：(x3/2+x5)+x6=x4+2x1 第四年：第四年：(x5/2+x7)+x8=x6+2x3 到第六年實(shí)有資金總額為到第六年實(shí)有資金總額為x9+2x7，整理后得到下列線性，整理后得到下列線性 規(guī)劃模型規(guī)劃模型 第一年：第一年：x1+x2=200(萬(wàn)元萬(wàn)元)第二年：第二年：(x1/2 +x3)+x4=x27912123413456356785789max22002220422204222042200,1,2,9jZxxxxxxxxxxxxxxxxxxxxxxxj線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP【例例6】均衡配套生產(chǎn)問(wèn)題。某產(chǎn)品由

15、均衡配套生產(chǎn)問(wèn)題。某產(chǎn)品由2件甲零件和件甲零件和3件乙零件組裝而成。兩種零件必須經(jīng)過(guò)設(shè)備件乙零件組裝而成。兩種零件必須經(jīng)過(guò)設(shè)備A、B上加工，每件甲零件在上加工，每件甲零件在A、B上的加工時(shí)間分別為上的加工時(shí)間分別為5分鐘和分鐘和9分鐘，每件乙零件在分鐘，每件乙零件在A、B上的加工時(shí)間分上的加工時(shí)間分別為別為4分鐘和分鐘和10分鐘。現(xiàn)有分鐘?，F(xiàn)有2臺(tái)設(shè)備臺(tái)設(shè)備A和和3臺(tái)設(shè)備臺(tái)設(shè)備B，每天可供加工時(shí)間為每天可供加工時(shí)間為8小時(shí)。為了保持兩種設(shè)備均小時(shí)。為了保持兩種設(shè)備均衡負(fù)荷生產(chǎn)，要求一種設(shè)備每天的加工總時(shí)間不超衡負(fù)荷生產(chǎn)，要求一種設(shè)備每天的加工總時(shí)間不超過(guò)另一種設(shè)備總時(shí)間過(guò)另一種設(shè)備總時(shí)間1小時(shí)

16、。怎樣安排設(shè)備的加工小時(shí)。怎樣安排設(shè)備的加工時(shí)間使每天產(chǎn)品的產(chǎn)量最大。時(shí)間使每天產(chǎn)品的產(chǎn)量最大。線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP【解解】 設(shè)設(shè)x1、x2為每天加工甲、乙兩種零件的件數(shù)，為每天加工甲、乙兩種零件的件數(shù)，則產(chǎn)品的產(chǎn)量是則產(chǎn)品的產(chǎn)量是)31,21min(21xxy 設(shè)備設(shè)備A、B每天加工工時(shí)的約束為每天加工工時(shí)的約束為60831096082452121xxxx要求一種設(shè)備每臺(tái)每天的加工時(shí)間不超過(guò)另一種設(shè)備要求一種設(shè)備每臺(tái)每天的加工時(shí)間不超過(guò)另一種設(shè)備1小時(shí)的約束為小時(shí)的約束為 60)109()452121xxxx（線性規(guī)劃的數(shù)學(xué)模

17、型線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP目標(biāo)函數(shù)線性化。產(chǎn)品的產(chǎn)量目標(biāo)函數(shù)線性化。產(chǎn)品的產(chǎn)量 y 等價(jià)于等價(jià)于2131,21xyxy約束線性化。將絕對(duì)值約束寫(xiě)成兩個(gè)不等式約束線性化。將絕對(duì)值約束寫(xiě)成兩個(gè)不等式60)109()45(60)109()45(21212121xxxxxxxx線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP線性規(guī)劃模型為線性規(guī)劃模型為121212121212m a x1213549 6 091 01 4 4 0466 0466 00Zyyxyxxxxxxxxxyxx、線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型

18、 Mathematical Model of LP線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型線性規(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約束條件都為等式方程約束條件都為等式方程3變量變量xj非負(fù)非負(fù)4常數(shù)常數(shù)bi非負(fù)非負(fù) 在用單純法求解線性規(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 12211 11221121 1222221 122max0,1,2,0,1,2,nnnnnnmmmnnmj

19、izc xc xc xa xa xa xba xa xa xba xaxaxbxjnbim線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型Standard form of LPnjjjxcZ1maxnjxmibxajnjijij, 2 , 1, 0, 2 , 1,10maxXbAXCXZ或?qū)懗上铝行问交驅(qū)懗上铝行问剑?或用矩陣形式或用矩陣形式線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型Standard form of LP1112111212222212nnmmmnnmaaaxbaaaxbAXbaaaxb；稱稱為約束方程的系數(shù)矩陣，為約束方程的系數(shù)矩陣，m是約束方程的個(gè)數(shù)，是約束方程的個(gè)數(shù)，n是決策變量的個(gè)數(shù)，一般情況是

20、決策變量的個(gè)數(shù)，一般情況mn，且，且r()m。其中其中:12,)nCc cc(線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型Standard form of LP一般形式線性規(guī)劃模型的標(biāo)準(zhǔn)化準(zhǔn)則一般形式線性規(guī)劃模型的標(biāo)準(zhǔn)化準(zhǔn)則: （前提（前提 b bi 0 ）cxZ min.1injjijbxa1. 2injjijbxa1. 3cxZmax01iniinnjjijxbxxa01iniinnjjijxbxxa無(wú)符號(hào)要求ix.40, 0, iiiiixxxxx5. xj0令令xj = xj , xj 0 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型Standard form of LP【例例7】將下列線性規(guī)劃化為標(biāo)準(zhǔn)型將下

21、列線性規(guī)劃化為標(biāo)準(zhǔn)型 3213minxxxZ無(wú)符號(hào)要求、32132132132100) 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其中線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型Standard form of LP (3)第二個(gè)約束條件是第二個(gè)約束條件是“”號(hào)，在號(hào)，在“”號(hào)左端減去剩余號(hào)左端減去剩余變量變量(surplus variable) x5 ，x50，也稱松馳變量；，也稱松馳變量；(2) 第一個(gè)

22、約束條件是第一個(gè)約束條件是“”號(hào)，號(hào)，在在“”號(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ù)是最小值，為了化為求最大值，令目標(biāo)函數(shù)是最小值，為了化為求最大值，令Z=Z,得到得到 max Z=Z，即當(dāng)，即當(dāng)Z達(dá)到最小值時(shí)達(dá)到最小值時(shí)Z達(dá)到最大值。達(dá)到最大值。 3213minxxxZ無(wú)符號(hào)要求、32132132132100) 3(523)2(3) 1 (8

23、2xxxxxxxxxxxx線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型Standard form of LP綜合起來(lái)得到下列標(biāo)準(zhǔn)型綜合起來(lái)得到下列標(biāo)準(zhǔn)型 332133maxxxxxZ 05)(233826543321633215332143321xxxxxxxxxxxxxxxxxxxxxx、線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型Standard form of LP當(dāng)某個(gè)約束是絕對(duì)值不等式時(shí)，將絕對(duì)值不等式化為當(dāng)某個(gè)約束是絕對(duì)值不等式時(shí)，將絕對(duì)值不等式化為兩個(gè)不等式，再化為等式，例如約束兩個(gè)不等式，再化為等式，例如約束 974321xxx將其化為兩個(gè)不等式將其化為兩個(gè)不等式 974974321321xxxxxx

24、再加入松馳變量化為等式。再加入松馳變量化為等式。 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型Standard form of LP 設(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，顯然，顯然A中至少中至少有一個(gè)有一個(gè)mm子矩陣子矩陣B，使得，使得r(B)=m。線性規(guī)劃的有關(guān)概念線性規(guī)劃的有關(guān)概念 可行解可行解(feasible solution): 滿足式滿足式(1.2)及及(1.3)的解的解X=（x1, x2 , xn)T 稱為可行解；稱為可行解；基基 (basis)：A中中 mm子矩

25、陣子矩陣 B 并且有并且有r(B)=m，則稱，則稱B是線性規(guī)劃的一個(gè)是線性規(guī)劃的一個(gè)基基(或或基矩陣基矩陣basis matrix )。線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型Standard form of LP當(dāng)確定某一矩陣為基矩陣時(shí)，則基矩陣對(duì)應(yīng)的列向量當(dāng)確定某一矩陣為基矩陣時(shí)，則基矩陣對(duì)應(yīng)的列向量稱為稱為基向量基向量(basic vector)，其余列向量稱為，其余列向量稱為非基向量非基向量; 基向量對(duì)應(yīng)的變量稱為基向量對(duì)應(yīng)的變量稱為基變量基變量(basic variable)，非基向量對(duì)應(yīng)的變量稱為非基向量對(duì)應(yīng)的變量稱為非基變量非基變量 ；注：注：基變量、非基變量是針對(duì)某一確定基而言的基變量

26、、非基變量是針對(duì)某一確定基而言的，不不同的基對(duì)應(yīng)的基變量和非基變量也不同。同的基對(duì)應(yīng)的基變量和非基變量也不同。 基本概念基本概念Basic Concepts 基本可行解基本可行解(basic feasible solution): 若基本解是可行解若基本解是可行解 則稱為是基本可行解（也稱基可行解）。則稱為是基本可行解（也稱基可行解）。 基本解基本解(basic solution) : 對(duì)某一確定的基對(duì)某一確定的基B，令，令非基變量非基變量 等于零等于零，利用式，利用式(1.2)解出基變量，則這組解稱為基解出基變量，則這組解稱為基 的的基本解。基本解。 最優(yōu)解最優(yōu)解(optimal solut

27、ion): 滿足式滿足式(1.1)的可行解稱為的可行解稱為最優(yōu)解，即使得目標(biāo)函數(shù)達(dá)到最優(yōu)解，即使得目標(biāo)函數(shù)達(dá)到最大值最大值的的可行解可行解就是就是最優(yōu)解；最優(yōu)解；非可行解非可行解(infeasible solution) 無(wú)界解無(wú)界解 (unbounded solution)注注： （1）只要基本解中的基變量的解滿足式只要基本解中的基變量的解滿足式(1.3)的的非負(fù)要求，那么這個(gè)基本解就是基本可行解。非負(fù)要求，那么這個(gè)基本解就是基本可行解。 （2）可行解不一定是基本可行解，同樣基本解也不可行解不一定是基本可行解，同樣基本解也不一定是可行解。一定是可行解。可行基可行基: 基可行解對(duì)應(yīng)的基稱為可行

28、基；基可行解對(duì)應(yīng)的基稱為可行基；最優(yōu)基最優(yōu)基: 基本最優(yōu)解對(duì)應(yīng)的基稱為最優(yōu)基；基本最優(yōu)解對(duì)應(yīng)的基稱為最優(yōu)基；基本最優(yōu)解基本最優(yōu)解: 最優(yōu)解是基本解稱為基本最優(yōu)解。最優(yōu)解是基本解稱為基本最優(yōu)解。 基本概念基本概念Basic Concepts 凸集凸集(Convex set): 設(shè)設(shè) K 是是 n 維空間維空間 Rn 的一個(gè)點(diǎn)集，對(duì)的一個(gè)點(diǎn)集，對(duì)任意兩點(diǎn)任意兩點(diǎn) 時(shí)，則稱時(shí)，則稱K為凸集。為凸集。,)2()1(KXX、) 10()1 ()2()1(KXXX當(dāng) 就是以就是以X(1)、X(2)為端點(diǎn)的線為端點(diǎn)的線段方程段方程, 點(diǎn)點(diǎn)X的位置由的位置由的值確定的值確定, 當(dāng)當(dāng)=0時(shí)時(shí), X=X(2),

29、當(dāng)當(dāng)=1時(shí)時(shí)X=X(1)。)2()1()1 (XXX凸組合凸組合(Convex combination) : 設(shè)設(shè)是是Rn中的點(diǎn)，若存在中的點(diǎn)，若存在 使得使得 成立，成立， 稱稱X為為 的凸組合的凸組合)()2() 1 (,KXXXX12,0Ki ,且及11Kii( )1KiiiXX)()2() 1 (,KXXX 基本概念基本概念Basic Concepts 極點(diǎn)極點(diǎn)(Extreme point): : 設(shè)設(shè)K是凸集，是凸集， ，若，若X不能用不能用K中中兩個(gè)不同的點(diǎn)兩個(gè)不同的點(diǎn) 的凸組合表示為的凸組合表示為KX )2()1 (, XX )10()1 ()2()1( 0i表表6(1)XBx1

30、x2x3x4bx3211040 x4130130j3400 (2)x3x2j (3)x1 x2 j 基變量基變量110001/301/3105/31- -1/3405/30- -4/330103/5- -1/51801- -1/5 2/5400- -1- -1將將3化為化為1乘乘以以1/3后后得得到到3018單純形法單純形法 Simplex Method注注: : (1) 在選進(jìn)基變量時(shí)，一般選在選進(jìn)基變量時(shí)，一般選k 0 中較大者所對(duì)應(yīng)的變量進(jìn)基，中較大者所對(duì)應(yīng)的變量進(jìn)基，也可任選一個(gè)也可任選一個(gè)k 0 所對(duì)應(yīng)的變量進(jìn)基，還可第一個(gè)所對(duì)應(yīng)的變量進(jìn)基，還可第一個(gè)k 0 所對(duì)應(yīng)所對(duì)應(yīng)的變量進(jìn)基。

31、的變量進(jìn)基。 (2) 選出基變量時(shí)，必須遵循最小比值原則選出基變量時(shí)，必須遵循最小比值原則( (保證從一個(gè)可行基保證從一個(gè)可行基換到另一個(gè)可行基換到另一個(gè)可行基) )，若有兩個(gè)或兩個(gè)以上相同最小的比值，若有兩個(gè)或兩個(gè)以上相同最小的比值，則任選一個(gè)最小比值所對(duì)應(yīng)的基變量出基，這時(shí)下一個(gè)基可行則任選一個(gè)最小比值所對(duì)應(yīng)的基變量出基，這時(shí)下一個(gè)基可行解中存在為解中存在為0 的基變量，稱之為退化的基可行解。的基變量，稱之為退化的基可行解。(3) 表表( (1.5) )中的每一張表對(duì)應(yīng)的模型都是典式，從一個(gè)可行基中的每一張表對(duì)應(yīng)的模型都是典式，從一個(gè)可行基換到另一個(gè)可行基，接下來(lái)的任務(wù)就是從當(dāng)前典式換到另

32、一個(gè)換到另一個(gè)可行基，接下來(lái)的任務(wù)就是從當(dāng)前典式換到另一個(gè)典式。典式。(4) 當(dāng)目標(biāo)函數(shù)是求最大值時(shí)當(dāng)目標(biāo)函數(shù)是求最大值時(shí),j0(j=1，n)時(shí)達(dá)到最優(yōu)解時(shí)達(dá)到最優(yōu)解； 當(dāng)目標(biāo)函數(shù)是求最小值時(shí)當(dāng)目標(biāo)函數(shù)是求最小值時(shí),j 0(j=1，n)時(shí)達(dá)到最優(yōu)解。時(shí)達(dá)到最優(yōu)解。單純形法單純形法 Simplex Method單純形法的單純形法的計(jì)算步驟計(jì)算步驟：1. 找一個(gè)找一個(gè)初始可行基初始可行基，寫(xiě)出對(duì)應(yīng)的典式，列出初始單，寫(xiě)出對(duì)應(yīng)的典式，列出初始單純形表純形表,其中基變量的檢驗(yàn)數(shù)必為零；其中基變量的檢驗(yàn)數(shù)必為零； 2. 判斷：判斷：(a)若若j( j，n)，則得到最優(yōu)解則得到最優(yōu)解；(b)若存在某個(gè)若存

33、在某個(gè)k0且且aik(i=1，2,m)，則線性則線性規(guī)劃具有無(wú)界解規(guī)劃具有無(wú)界解；(c)若存在若存在k0且且aik (i=1,m)不全非正，則進(jìn)行換基不全非正，則進(jìn)行換基；3. 換基：換基：(a)選選進(jìn)基變量進(jìn)基變量：設(shè)：設(shè)k=max j | j 0, 選第選第k列所對(duì)應(yīng)列所對(duì)應(yīng)的變量的變量xk為進(jìn)基變量為進(jìn)基變量。單純形法單純形法 Simplex Method第第個(gè)比值最小，選最小比值對(duì)應(yīng)行的基變量為出基個(gè)比值最小，選最小比值對(duì)應(yīng)行的基變量為出基變量，若有相同最小比值，則任選一個(gè)變量，若有相同最小比值，則任選一個(gè)aLk為主元素為主元素。 (c)求新的基可行解求新的基可行解：用初等行變換方法將

34、：用初等行變換方法將aLk化為化為, 第第 k 列其它元素化為零（包括檢驗(yàn)數(shù)行）得到新的可列其它元素化為零（包括檢驗(yàn)數(shù)行）得到新的可行基及基本可行解，再判斷是否得到最優(yōu)解。行基及基本可行解，再判斷是否得到最優(yōu)解。(b)選選出基變量出基變量 ：求最小比值：求最小比值0|minikikiLaab單純形法單純形法 Simplex Method【例例9】 用單純形法求解用單純形法求解3212maxxxxZ02053115232321321321xxxxxxxxx、 【解解】將數(shù)學(xué)模型化為標(biāo)準(zhǔn)型：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)型：3212maxxxxZ5 , 2 , 1, 0205311523253214321jx

35、xxxxxxxxj單純形法單純形法 Simplex MethodCj12100bCBXBx1x2x3x4x50 x423210150 x51/3150120j12100 0 x42x2j 1x1 2x2 j 表表71/3150120301713751/309022025601017/31/31250128/91/92/335/30098/91/97/3最優(yōu)解最優(yōu)解X=(25，35/3，0，0，0)T，最優(yōu)值，最優(yōu)值 Z =145/3單純形法單純形法 Simplex Method【例例10】用單純形法求解用單純形法求解 42122minxxxZ5 , 1, 0212665521421321jxx

36、xxxxxxxxj【解解】 這是一個(gè)這是一個(gè)極小化極小化的線性規(guī)劃問(wèn)題的線性規(guī)劃問(wèn)題, 可以將其化可以將其化為極大化問(wèn)題求解為極大化問(wèn)題求解, 也可直接求解也可直接求解, 這時(shí)這時(shí)判斷標(biāo)準(zhǔn)判斷標(biāo)準(zhǔn)是是: : j0(j=1, , n)得到最優(yōu)解得到最優(yōu)解。容易觀察到系數(shù)矩陣中有容易觀察到系數(shù)矩陣中有一個(gè)一個(gè)3階單位矩陣階單位矩陣, x3、x4、x5為基變量。為基變量。12121222(6)6Zxxxxxx 單純形法單純形法 Simplex MethodXBx1x2x3x4x5bx3x4x51- -1611210001000156215621/2j1- -1000 x2x4x51- -241001

37、- -1- -20100015111 j20100 表中表中j0( j=1,2,5), 所以最優(yōu)解為所以最優(yōu)解為X=(0,5,0,1,11 )T , 最最優(yōu)值優(yōu)值 Z=2x12x2x4=251=11。表表8單純形法單純形法 Simplex Method21maxxxZ0,42123212121xxxxxx 【例例11】求解線性規(guī)劃求解線性規(guī)劃 【解解】化為標(biāo)準(zhǔn)型化為標(biāo)準(zhǔn)型21maxxxZ4 , 1, 042123421321jxxxxxxxj單純形法單純形法 Simplex Method初始單純形表為初始單純形表為XBx1x2x3x4bx3x43221100114j1100 2=10, x2進(jìn)

38、基，而進(jìn)基，而a120，a220且且aik(i=1, 2, , m)，則線，則線性規(guī)劃具有無(wú)界解。性規(guī)劃具有無(wú)界解。退化基本可行解的判斷退化基本可行解的判斷: 存在某個(gè)基變量為零的基本存在某個(gè)基變量為零的基本可行解。可行解。單純形法單純形法 Simplex Method設(shè)有線性規(guī)劃設(shè)有線性規(guī)劃0maxXbAXCXZ其中矩陣其中矩陣Amn 且且 r(A)=m,12( ,)nCc ccTmbbbb),(21X0理解為理解為X大于等于零的向量，即大于等于零的向量，即xj0( j=1,2,n)。TnxxxX),(21計(jì)算公式計(jì)算公式單純形法單純形法 Simplex Method不妨假設(shè)不妨假設(shè)A(P1

39、, P2, ,Pn)中前中前m個(gè)列向量構(gòu)成一個(gè)可個(gè)列向量構(gòu)成一個(gè)可行基，記為行基，記為B=(P1, P2 , , Pm)。矩陣。矩陣A中后中后nm列構(gòu)列構(gòu)成的矩陣記為成的矩陣記為N(Pm+1, ,Pn), 則則A可以寫(xiě)成分塊矩陣可以寫(xiě)成分塊矩陣A=(B，N)。對(duì)于基對(duì)于基B，基變量為，基變量為XB=(x1, x2, , xm )T, 非基變量為非基變量為XN=(xm+1, xm+2, , xn)T。 則則X可表示成可表示成 , 同理將同理將C 寫(xiě)成分塊矩陣寫(xiě)成分塊矩陣C=(CB, CN)，NBXXX CB=(C1,C2, ,Cm), CN=(Cm+1, Cm+2 , , cn), 則則 AX=

40、b 可寫(xiě)成可寫(xiě)成bNXBXXXNBNBNB)( ，單純形法單純形法 Simplex Method因?yàn)橐驗(yàn)閞(B)=m(或或|B|0)所以所以B -1存在，因此可有存在，因此可有 NNBNBNXBbBNXbBXNXbBX111)(令非基變量令非基變量XN=0，XB=B1b，由，由B是可行基的假設(shè)，是可行基的假設(shè)，則得到基本可行解則得到基本可行解X=(B1b，0)T消去目標(biāo)函數(shù)中的基變量，于是目標(biāo)函數(shù)可寫(xiě)成消去目標(biāo)函數(shù)中的基變量，于是目標(biāo)函數(shù)可寫(xiě)成 NNBBNBNBXCXCXXCCZ),(1111()()BNNNBNBNCB bB NXC XC B bCC B N X單純形法單純形法 Simple

41、x MethodNBNBXNBCCbBCZ)(11得到下列五個(gè)計(jì)算公式：得到下列五個(gè)計(jì)算公式：104.BZC B b13.NNBCC B NiijijjaccjijNBa)(1其中ABCCB111.BXB b12.NB N稱為單純形乘子1. 5BCB(令令XN=0) 單純形法單純形法 Simplex Method上述公式可用下面較簡(jiǎn)單的矩陣表格運(yùn)算得到，將目上述公式可用下面較簡(jiǎn)單的矩陣表格運(yùn)算得到，將目標(biāo)函數(shù)寫(xiě)成標(biāo)函數(shù)寫(xiě)成CBXB+CNXN Z=0, 約束為約束為BXB+NXN=b將將B化為化為E(E為為m階單位矩陣階單位矩陣), 即求基本可行解。即求基本可行解。用用B1左乘表中第二行左乘表中

42、第二行,得到表得到表10XBXNbXBE B-1NB-1bCBCN0XBXNbXBBNbCBCN0表表10單純形法單純形法 Simplex Method將第二行左乘將第二行左乘CB后加到第三行后加到第三行,得到得到XBZ0XBXNbXBEB- -1NB- -1 1bCj Zj0CN- -CBB1NCBB1bN表表11將將CB化為零化為零, 即求檢驗(yàn)數(shù)即求檢驗(yàn)數(shù):單純形法單純形法 Simplex Method對(duì)于如下形式的線性規(guī)劃問(wèn)題：對(duì)于如下形式的線性規(guī)劃問(wèn)題：0maxXbAXCXZ引入松弛變量引入松弛變量 化為標(biāo)準(zhǔn)形如下：化為標(biāo)準(zhǔn)形如下：TmnnnsxxxX),(210, 00maxsssXXbEXAXXCXZ單純形法單純形法 Simplex Method 記記 則上述標(biāo)準(zhǔn)形式為則上述標(biāo)準(zhǔn)形式為,0,CCEAAXXXs0maxXbXAXCZ由于由于 對(duì)應(yīng)的系數(shù)矩陣為單位陣，故容易確定初始基變對(duì)應(yīng)的系數(shù)矩陣為單位陣，故容易確定初始基變量為量為 ，得到如下初始單純形表，得到如下初始單純形表: :sXsXXXsbXsAEbC00單純形法單純形法 Simplex MethodXXsbXBB-