教學(xué)第4章目標(biāo)規(guī)劃-教學(xué)第3節(jié)-解目標(biāo)規(guī)劃的單純形法教學(xué)第4節(jié)靈敏度分析教學(xué)第5節(jié)應(yīng)用舉例課件

第4章

目標(biāo)規(guī)劃

第3節(jié)

解目標(biāo)規(guī)劃的單純形法

第4節(jié)

靈敏度分析

第5節(jié)

應(yīng)用舉例

運(yùn)籌學(xué)（第二版）

刁在筠等編

高等教育出版社

第4章

目標(biāo)規(guī)劃1第3節(jié)解目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)與線性規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)形式上沒有本質(zhì)的區(qū)別，所以可用單純形法求解。但要考慮目標(biāo)規(guī)劃的數(shù)學(xué)模型一些特點，作以下規(guī)定：(1)因目標(biāo)規(guī)劃問題的目標(biāo)函數(shù)都是求最小化，所以以cj-zj≥0，j=1,2,…，n為最優(yōu)準(zhǔn)則。(2)因非基變量的檢驗數(shù)中含有不同等級的優(yōu)先因子，即第3節(jié)解目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)2因P1>>P2>>…>>PK；從每個檢驗數(shù)的整體來看：檢驗數(shù)的正、負(fù)首先決定于P1的系數(shù)α1j的正、負(fù)。若α1j=0，這時此檢驗數(shù)的正、負(fù)就決定于P2的系數(shù)α2j的正、負(fù)，下面可依此類推。

因P1>>P2>>…>>PK；從每個檢驗數(shù)的整體來看：檢驗數(shù)3解目標(biāo)規(guī)劃問題的單純形法的計算步驟：(1)建立初始單純形表，在表中將檢驗數(shù)行按優(yōu)先因子個數(shù)分別列成K行，置k=1。(2)檢查該行中是否存在負(fù)數(shù)，且對應(yīng)的前k-1行的系數(shù)是零。若有負(fù)數(shù)取其中最小者對應(yīng)的變量為換入變量，轉(zhuǎn)(3)。若無負(fù)數(shù)，則轉(zhuǎn)(5)。(3)按最小比值規(guī)則確定換出變量，當(dāng)存在兩個和兩個以上相同的最小比值時，選取具有較高優(yōu)先級別的變量為換出變量。(4)按單純形法進(jìn)行基變換運(yùn)算，建立新的計算表，返回(2)。(5)當(dāng)k=K時，計算結(jié)束。表中的解即為滿意解。否則置k=k+1，返回到(2)。解目標(biāo)規(guī)劃問題的單純形法的計算步驟：(1)建立初始單純形表4例4試用單純形法來求解例2。

將例2的數(shù)學(xué)模型化為標(biāo)準(zhǔn)型：

例4試用單純形法來求解例2。

將例2的數(shù)學(xué)模型化為標(biāo)準(zhǔn)型5

①

取xs，d1-，d2-，d3-為初始基變量，列初始單純形表，見表4-1。

①取xs，d1-，d2-，d3-為初始基變量，列初始單純6②取k=1，檢查P1行的檢驗數(shù)，因該行無負(fù)檢驗數(shù)，故轉(zhuǎn)(5)。③因k(=1)＜K(=3)，置k=k+1=2，返回到(2)。④當(dāng)k=2時,查出P2行檢驗數(shù)中有-1、-2；取min(-1,-2)=-2。它對應(yīng)的變量x2為換入變量，轉(zhuǎn)入(3)。⑤在表4-1上計算最小比值它對應(yīng)的變量d2-為換出變量，轉(zhuǎn)入(4)②取k=1，檢查P1行的檢驗數(shù)，因該行無負(fù)檢驗數(shù)，7⑥即進(jìn)行基變換運(yùn)算，計算結(jié)果見表4-2⑥即進(jìn)行基變換運(yùn)算，計算結(jié)果見表4-28表4-3返回到(2)。依此類推，直至得到最終表為止。見表4-3。

表4-3返回到(2)。依此類推，直至得到最終表為止。9表4-3所示的解x1*=2，x2*=4為例1的滿意解。此解相當(dāng)于圖4-1的G點。表4-3所示的解x1*=2，x2*=4為例1的滿意解。此解相10

檢查表4-3的檢驗數(shù)行，發(fā)現(xiàn)非基變量d3+的檢驗數(shù)為0，這表示存在多重解。在表4-3中以非基變量d3+為換入變量，d1-為換出變量，經(jīng)迭代得到表4-4。

檢查表4-3的檢驗數(shù)行，發(fā)現(xiàn)非基變量d3+的檢驗數(shù)為0，這11由表4-4得到解x1*=10/3，x2*=10/3，此解相當(dāng)于圖4-1的D點，G、D兩點的凸線性組合都是例1的滿意解由表4-4得到解x1*=10/3，x2*=10/3，此解相當(dāng)12第4節(jié)靈敏度分析目標(biāo)規(guī)劃的靈敏度分析方法與線性規(guī)劃相似，這里除分析各項系數(shù)的變化外，還有優(yōu)先因子的變化問題，下面舉例說明。改變目標(biāo)優(yōu)先等級的分析。第4節(jié)靈敏度分析13例5已知目標(biāo)規(guī)劃問題

例5已知目標(biāo)規(guī)劃問題

14在得到最終表后，見表4-5。目標(biāo)函數(shù)的優(yōu)先等級變化為：(1)minz=P1(2d1++32+)+P2d4++P3-(2)minz=P1d3-+P2(2d1++3d3+)+P3d4+試分析原解有什么變化。在得到最終表后，見表4-5。15表4-5表4-516解分析(1)，實際是將原目標(biāo)函數(shù)中d4+，d3-的優(yōu)先因子對換了一下。這時將表4-5的檢驗數(shù)中的P2、P3行和cj行的P2、P3對換即可。這時可見原解仍滿足最優(yōu)解條件。解分析(1)，實際是將原目標(biāo)函數(shù)中d4+，d3-的優(yōu)先因17分析(2)，將變化了的優(yōu)先等級直接反映到表4-5上。再計算檢驗數(shù)，得表4-6。然后進(jìn)行迭代，直到求得新的滿意解為止。從表4-7中得到新的滿意解x1*=4，x2*=12。分析(2)，將變化了的優(yōu)先等級直接反映到表4-5上。再計算檢18表4-6表4-619第5節(jié)應(yīng)用舉例

例6某單位領(lǐng)導(dǎo)在考慮本單位職工的升級調(diào)資方案時，依次遵守以下規(guī)定：(1)不超過年工資總額60000元；(2)每級的人數(shù)不超過定編規(guī)定的人數(shù)；(3)Ⅱ，Ⅲ級的升級面盡可能達(dá)到現(xiàn)有人數(shù)的20%，且無越級提升；(4)Ⅲ級不足編制的人數(shù)可錄用新職工，又Ⅰ級的職工中有10%要退休。有關(guān)資料匯總于表4-8中，問該領(lǐng)導(dǎo)應(yīng)如何擬訂一個滿意的方案。第5節(jié)應(yīng)用舉例

例6某單位領(lǐng)導(dǎo)在考慮本單位職20表4-8表4-821解設(shè)x1、x2、x3分別表示提升到Ⅰ、Ⅱ級和錄用到Ⅲ級的新職工人數(shù)。對各目標(biāo)確定的優(yōu)先因子為：P1——不超過年工資總額60000元；P2——每級的人數(shù)不超過定編規(guī)定的人數(shù)；P3——Ⅱ、Ⅲ級的升級面盡可能達(dá)到現(xiàn)有人數(shù)的20%。解設(shè)x1、x2、x3分別表示提升到Ⅰ、Ⅱ級和錄用到Ⅲ級的22先分別建立各目標(biāo)約束。

年工資總額不超過60000元2000(10-10×0.1+x1)+1500(12-x1+x2)+1000(15-x2+x3)+d1—-d1+

=60000先分別建立各目標(biāo)約束。

年工資總額不超過60000元20023每級的人數(shù)不超過定編規(guī)定的人數(shù)：對Ⅰ級有10(1-0.1)+x1+d2-—d2+=12對Ⅱ級有12-x1+x2+d3-—d3+=15對Ⅲ級有15-x2+x3+d4-—d4+=15Ⅱ，Ⅲ級的升級面不大于現(xiàn)有人數(shù)的20%，但盡可能多提；對Ⅱ級有x1+d5-—d5+=12×0.2對Ⅲ級有x2+d6-—d6+=15×0.2目標(biāo)函數(shù)：minz=P1d1++P2(d2++d3++d4+)+P3(d5-+d6-)每級的人數(shù)不超過定編規(guī)定的人數(shù)：24以上目標(biāo)規(guī)劃模型可用單純形法求解，得到多重解?，F(xiàn)將這些解匯總于表4-9，這單位的領(lǐng)導(dǎo)再按具體情況，從表4-9中選一個執(zhí)行方案

以上目標(biāo)規(guī)劃模型可用單純形法求解，得到多重解?，F(xiàn)將這些解匯總25第4章目標(biāo)規(guī)劃-第3節(jié)-解目標(biāo)規(guī)劃的單純形法第4節(jié)靈敏度分析第5節(jié)應(yīng)用舉例課件26例7已知有三個產(chǎn)地給四個銷地供應(yīng)某種產(chǎn)品，產(chǎn)銷地之間的供需量和單位運(yùn)價見表4-10。有關(guān)部門在研究調(diào)運(yùn)方案時依次考慮以下七項目標(biāo)，并規(guī)定其相應(yīng)的優(yōu)先等級：

P1——B4是重點保證單位，必須全部滿足其需要；P2——A3向B1提供的產(chǎn)量不少于100；P3——每個銷地的供應(yīng)量不小于其需要量的80%；P4——所定調(diào)運(yùn)方案的總運(yùn)費不超過最小運(yùn)費調(diào)運(yùn)方案的10%；P5——因路段的問題，盡量避免安排將A2的產(chǎn)品往B4；P6——給B1和B3的供應(yīng)率要相同；P7——力求總運(yùn)費最省。試求滿意的調(diào)運(yùn)方案。例7已知有三個產(chǎn)地給四個銷地供應(yīng)某種產(chǎn)品，產(chǎn)銷地之間的供27表4-10表4-1028解

上作業(yè)法求得最小運(yùn)費的調(diào)運(yùn)方案見表4-11。這時得最小運(yùn)費為2950元，再根據(jù)提出的各項目標(biāo)的要求建立目標(biāo)規(guī)劃的模型。表4-11解上作業(yè)法求得最小運(yùn)費的調(diào)運(yùn)方案見表4-11。這時得最小29供應(yīng)約束x11+x12+x13+x14≤300x21+x22+x23+x24≤200x31+x32+x33+x34≤400需求約束：x11+x21+x31+d1--d1+=200x12+x22+x32+d2--d2+=100x13+x23+x33+d3--d3+=450x14+x24+x34+d4--d4+=250A3向B1提供的產(chǎn)品量不少于100x31+d5--d5+=100供應(yīng)約束x11+x12+x13+x14≤30030每個銷地的供應(yīng)量不小于其需要量的80%x11+x21+x31+d6--d6+=200×0.8x12+x22+x32+d7--d7+=100×0.8x13+x23+x33+d8--d8+=450×0.8x14+x24+x34+d9--d9+=250×0.8每個銷地的供應(yīng)量不小于其需要量的80%31調(diào)運(yùn)方案的總運(yùn)費不超過最小運(yùn)費調(diào)運(yùn)方案的10%調(diào)運(yùn)方案的總運(yùn)費不超過最小運(yùn)費調(diào)運(yùn)方案的10%32因路段的問題，盡量避免安排將A2的產(chǎn)品運(yùn)往B4x24+d11--d11+=0給B1和B3的供應(yīng)率要相同(x11+x21+x31)-(200/450)(x13+x23+x33)+d12--d12+=0因路段的問題，盡量避免安排將A2的產(chǎn)品運(yùn)往B433

力求總運(yùn)費最省

力求總運(yùn)費最省34

目標(biāo)函數(shù)為：

目標(biāo)函數(shù)為：

35計算結(jié)果，得到滿意調(diào)運(yùn)方案見

表4-12。計算結(jié)果，得到滿意調(diào)運(yùn)方案見

表4-12。36

總運(yùn)費為3360元。

總運(yùn)費為3360元。

37第4章結(jié)束第4章結(jié)束38第4章目標(biāo)規(guī)劃-第3節(jié)-解目標(biāo)規(guī)劃的單純形法第4節(jié)靈敏度分析第5節(jié)應(yīng)用舉例課件39第4章目標(biāo)規(guī)劃-第3節(jié)-解目標(biāo)規(guī)劃的單純形法第4節(jié)靈敏度分析第5節(jié)應(yīng)用舉例課件40第4章目標(biāo)規(guī)劃-第3節(jié)-解目標(biāo)規(guī)劃的單純形法第4節(jié)靈敏度分析第5節(jié)應(yīng)用舉例課件41

第4章

目標(biāo)規(guī)劃

第3節(jié)

解目標(biāo)規(guī)劃的單純形法

第4節(jié)

靈敏度分析

第5節(jié)

應(yīng)用舉例

運(yùn)籌學(xué)（第二版）

刁在筠等編

高等教育出版社

第4章

目標(biāo)規(guī)劃42第3節(jié)解目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)與線性規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)形式上沒有本質(zhì)的區(qū)別，所以可用單純形法求解。但要考慮目標(biāo)規(guī)劃的數(shù)學(xué)模型一些特點，作以下規(guī)定：(1)因目標(biāo)規(guī)劃問題的目標(biāo)函數(shù)都是求最小化，所以以cj-zj≥0，j=1,2,…，n為最優(yōu)準(zhǔn)則。(2)因非基變量的檢驗數(shù)中含有不同等級的優(yōu)先因子，即第3節(jié)解目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)43因P1>>P2>>…>>PK；從每個檢驗數(shù)的整體來看：檢驗數(shù)的正、負(fù)首先決定于P1的系數(shù)α1j的正、負(fù)。若α1j=0，這時此檢驗數(shù)的正、負(fù)就決定于P2的系數(shù)α2j的正、負(fù)，下面可依此類推。

因P1>>P2>>…>>PK；從每個檢驗數(shù)的整體來看：檢驗數(shù)44解目標(biāo)規(guī)劃問題的單純形法的計算步驟：(1)建立初始單純形表，在表中將檢驗數(shù)行按優(yōu)先因子個數(shù)分別列成K行，置k=1。(2)檢查該行中是否存在負(fù)數(shù)，且對應(yīng)的前k-1行的系數(shù)是零。若有負(fù)數(shù)取其中最小者對應(yīng)的變量為換入變量，轉(zhuǎn)(3)。若無負(fù)數(shù)，則轉(zhuǎn)(5)。(3)按最小比值規(guī)則確定換出變量，當(dāng)存在兩個和兩個以上相同的最小比值時，選取具有較高優(yōu)先級別的變量為換出變量。(4)按單純形法進(jìn)行基變換運(yùn)算，建立新的計算表，返回(2)。(5)當(dāng)k=K時，計算結(jié)束。表中的解即為滿意解。否則置k=k+1，返回到(2)。解目標(biāo)規(guī)劃問題的單純形法的計算步驟：(1)建立初始單純形表45例4試用單純形法來求解例2。

將例2的數(shù)學(xué)模型化為標(biāo)準(zhǔn)型：

例4試用單純形法來求解例2。

將例2的數(shù)學(xué)模型化為標(biāo)準(zhǔn)型46

①

取xs，d1-，d2-，d3-為初始基變量，列初始單純形表，見表4-1。

①取xs，d1-，d2-，d3-為初始基變量，列初始單純47②取k=1，檢查P1行的檢驗數(shù)，因該行無負(fù)檢驗數(shù)，故轉(zhuǎn)(5)。③因k(=1)＜K(=3)，置k=k+1=2，返回到(2)。④當(dāng)k=2時,查出P2行檢驗數(shù)中有-1、-2；取min(-1,-2)=-2。它對應(yīng)的變量x2為換入變量，轉(zhuǎn)入(3)。⑤在表4-1上計算最小比值它對應(yīng)的變量d2-為換出變量，轉(zhuǎn)入(4)②取k=1，檢查P1行的檢驗數(shù)，因該行無負(fù)檢驗數(shù)，48⑥即進(jìn)行基變換運(yùn)算，計算結(jié)果見表4-2⑥即進(jìn)行基變換運(yùn)算，計算結(jié)果見表4-249表4-3返回到(2)。依此類推，直至得到最終表為止。見表4-3。

表4-3返回到(2)。依此類推，直至得到最終表為止。50表4-3所示的解x1*=2，x2*=4為例1的滿意解。此解相當(dāng)于圖4-1的G點。表4-3所示的解x1*=2，x2*=4為例1的滿意解。此解相51

檢查表4-3的檢驗數(shù)行，發(fā)現(xiàn)非基變量d3+的檢驗數(shù)為0，這表示存在多重解。在表4-3中以非基變量d3+為換入變量，d1-為換出變量，經(jīng)迭代得到表4-4。

檢查表4-3的檢驗數(shù)行，發(fā)現(xiàn)非基變量d3+的檢驗數(shù)為0，這52由表4-4得到解x1*=10/3，x2*=10/3，此解相當(dāng)于圖4-1的D點，G、D兩點的凸線性組合都是例1的滿意解由表4-4得到解x1*=10/3，x2*=10/3，此解相當(dāng)53第4節(jié)靈敏度分析目標(biāo)規(guī)劃的靈敏度分析方法與線性規(guī)劃相似，這里除分析各項系數(shù)的變化外，還有優(yōu)先因子的變化問題，下面舉例說明。改變目標(biāo)優(yōu)先等級的分析。第4節(jié)靈敏度分析54例5已知目標(biāo)規(guī)劃問題

例5已知目標(biāo)規(guī)劃問題

55在得到最終表后，見表4-5。目標(biāo)函數(shù)的優(yōu)先等級變化為：(1)minz=P1(2d1++32+)+P2d4++P3-(2)minz=P1d3-+P2(2d1++3d3+)+P3d4+試分析原解有什么變化。在得到最終表后，見表4-5。56表4-5表4-557解分析(1)，實際是將原目標(biāo)函數(shù)中d4+，d3-的優(yōu)先因子對換了一下。這時將表4-5的檢驗數(shù)中的P2、P3行和cj行的P2、P3對換即可。這時可見原解仍滿足最優(yōu)解條件。解分析(1)，實際是將原目標(biāo)函數(shù)中d4+，d3-的優(yōu)先因58分析(2)，將變化了的優(yōu)先等級直接反映到表4-5上。再計算檢驗數(shù)，得表4-6。然后進(jìn)行迭代，直到求得新的滿意解為止。從表4-7中得到新的滿意解x1*=4，x2*=12。分析(2)，將變化了的優(yōu)先等級直接反映到表4-5上。再計算檢59表4-6表4-660第5節(jié)應(yīng)用舉例

例6某單位領(lǐng)導(dǎo)在考慮本單位職工的升級調(diào)資方案時，依次遵守以下規(guī)定：(1)不超過年工資總額60000元；(2)每級的人數(shù)不超過定編規(guī)定的人數(shù)；(3)Ⅱ，Ⅲ級的升級面盡可能達(dá)到現(xiàn)有人數(shù)的20%，且無越級提升；(4)Ⅲ級不足編制的人數(shù)可錄用新職工，又Ⅰ級的職工中有10%要退休。有關(guān)資料匯總于表4-8中，問該領(lǐng)導(dǎo)應(yīng)如何擬訂一個滿意的方案。第5節(jié)應(yīng)用舉例

例6某單位領(lǐng)導(dǎo)在考慮本單位職61表4-8表4-862解設(shè)x1、x2、x3分別表示提升到Ⅰ、Ⅱ級和錄用到Ⅲ級的新職工人數(shù)。對各目標(biāo)確定的優(yōu)先因子為：P1——不超過年工資總額60000元；P2——每級的人數(shù)不超過定編規(guī)定的人數(shù)；P3——Ⅱ、Ⅲ級的升級面盡可能達(dá)到現(xiàn)有人數(shù)的20%。解設(shè)x1、x2、x3分別表示提升到Ⅰ、Ⅱ級和錄用到Ⅲ級的63先分別建立各目標(biāo)約束。

年工資總額不超過60000元2000(10-10×0.1+x1)+1500(12-x1+x2)+1000(15-x2+x3)+d1—-d1+

=60000先分別建立各目標(biāo)約束。

年工資總額不超過60000元20064每級的人數(shù)不超過定編規(guī)定的人數(shù)：對Ⅰ級有10(1-0.1)+x1+d2-—d2+=12對Ⅱ級有12-x1+x2+d3-—d3+=15對Ⅲ級有15-x2+x3+d4-—d4+=15Ⅱ，Ⅲ級的升級面不大于現(xiàn)有人數(shù)的20%，但盡可能多提；對Ⅱ級有x1+d5-—d5+=12×0.2對Ⅲ級有x2+d6-—d6+=15×0.2目標(biāo)函數(shù)：minz=P1d1++P2(d2++d3++d4+)+P3(d5-+d6-)每級的人數(shù)不超過定編規(guī)定的人數(shù)：65以上目標(biāo)規(guī)劃模型可用單純形法求解，得到多重解。現(xiàn)將這些解匯總于表4-9，這單位的領(lǐng)導(dǎo)再按具體情況，從表4-9中選一個執(zhí)行方案

以上目標(biāo)規(guī)劃模型可用單純形法求解，得到多重解?，F(xiàn)將這些解匯總66第4章目標(biāo)規(guī)劃-第3節(jié)-解目標(biāo)規(guī)劃的單純形法第4節(jié)靈敏度分析第5節(jié)應(yīng)用舉例課件67例7已知有三個產(chǎn)地給四個銷地供應(yīng)某種產(chǎn)品，產(chǎn)銷地之間的供需量和單位運(yùn)價見表4-10。有關(guān)部門在研究調(diào)運(yùn)方案時依次考慮以下七項目標(biāo)，并規(guī)定其相應(yīng)的優(yōu)先等級：

P1——B4是重點保證單位，必須全部滿足其需要；P2——A3向B1提供的產(chǎn)量不少于100；P3——每個銷地的供應(yīng)量不小于其需要量的80%；P4——所定調(diào)運(yùn)方案的總運(yùn)費不超過最小運(yùn)費調(diào)運(yùn)方案的10%；P5——因路段的問題，盡量避免安排將A2的產(chǎn)品往B4；P6——給B1和B3的供應(yīng)率要相同；P7——力求總運(yùn)費最省。試求滿意的調(diào)運(yùn)方案。例7已知有三個產(chǎn)地給四個銷地供應(yīng)某種產(chǎn)品，產(chǎn)銷地之間的供68表4-10表4-1069解

上作業(yè)法求得最小運(yùn)費的調(diào)運(yùn)方案見表4-11。這時得最小運(yùn)費為2950元，再根據(jù)提出的各項目標(biāo)的要求建立目標(biāo)規(guī)劃的模型。表4-11解上作業(yè)法求得最小運(yùn)費的調(diào)運(yùn)方案見表4-11。這時得最小70供應(yīng)約束x11+x12+x13+x14≤300x21+