第4章目標(biāo)規(guī)劃-第3-5節(jié)ppt課件

1、第3節(jié) 解目的規(guī)劃的單純形法 目的規(guī)劃的數(shù)學(xué)模型構(gòu)造與線性規(guī)劃的數(shù)學(xué)模型構(gòu)造方式上沒有本質(zhì)的區(qū)別，所以可用單純形法求解。但要思索目的規(guī)劃的數(shù)學(xué)模型一些特點(diǎn)，作以下規(guī)定：(1) 因目的規(guī)劃問題的目的函數(shù)都是求最小化，所以以cj-zj0，j=1,2,，n為最優(yōu)準(zhǔn)那么。(2) 因非基變量的檢驗(yàn)數(shù)中含有不同等級(jí)的優(yōu)先因子，即因P1P2PK；從每個(gè)檢驗(yàn)數(shù)的整體來看：檢驗(yàn)數(shù)的正、負(fù)首先決議于P1的系數(shù)1j的正、負(fù)。假設(shè)1j=0，這時(shí)此檢驗(yàn)數(shù)的正、負(fù)就決議于P2的系數(shù)2j的正、負(fù)，下面可依此類推。 解目的規(guī)劃問題的單純形法的計(jì)算步驟：(1) 建立初始單純形表，在表中將檢驗(yàn)數(shù)行按優(yōu)先因子個(gè)數(shù)分別列成K行，置k

2、=1。(2) 檢查該行中能否存在負(fù)數(shù)，且對(duì)應(yīng)的前k-1行的系數(shù)是零。假設(shè)有負(fù)數(shù)取其中最小者對(duì)應(yīng)的變量為換入變量，轉(zhuǎn)(3)。假設(shè)無負(fù)數(shù)，那么轉(zhuǎn)(5)。(3) 按最小比值規(guī)那么確定換出變量，當(dāng)存在兩個(gè)和兩個(gè)以上一樣的最小比值時(shí)，選取具有較高優(yōu)先級(jí)別的變量為換出變量。(4) 按單純形法進(jìn)展基變換運(yùn)算，建立新的計(jì)算表，前往(2)。(5) 當(dāng)k=K時(shí)，計(jì)算終了。表中的解即為稱心解。否那么置k=k+1，前往到(2)。例4 試用單純形法來求解例2。將例2的數(shù)學(xué)模型化為規(guī)范型： 取xs，d1-，d2-，d3-為初始基變量，列初始單純形表，見表4-1。 取k=1，檢查P1行的檢驗(yàn)數(shù)，因該行無負(fù)檢驗(yàn)數(shù)， 故轉(zhuǎn)(5

3、)。 因k(=1)K(=3)，置k=k+1=2，前往到(2)。 當(dāng)k=2時(shí),查出P2行檢驗(yàn)數(shù)中有-1、-2； 取min(-1,-2)=-2。 它對(duì)應(yīng)的變量x2為換入變量，轉(zhuǎn)入(3)。 在表4-1上計(jì)算最小比值它對(duì)應(yīng)的變量d2-為換出變量，轉(zhuǎn)入(4) 即進(jìn)展基變換運(yùn)算，計(jì)算結(jié)果見表4-2 表4-3前往到(2)。依此類推，直至得到最終表為止。見表4-3。表4-3所示的解x1*=2，x2*=4為例1的稱心解。此解相當(dāng)于圖4-1的G點(diǎn)。檢查表4-3的檢驗(yàn)數(shù)行，發(fā)現(xiàn)非基變量d3+的檢驗(yàn)數(shù)為0，這表示存在多重解。在表4-3中以非基變量d3+為換入變量，d1-為換出變量，經(jīng)迭代得到表4-4。由表4-4得到解

4、x1*=10/3，x2*=10/3，此解相當(dāng)于圖4-1的D點(diǎn)，G、D兩點(diǎn)的凸線性組合都是例1的稱心解第4節(jié) 靈敏度分析 目的規(guī)劃的靈敏度分析方法與線性規(guī)劃類似，這里除分析各項(xiàng)系數(shù)的變化外，還有優(yōu)先因子的變化問題，下面舉例闡明。 改動(dòng)目的優(yōu)先等級(jí)的分析。例5 知目的規(guī)劃問題在得到最終表后，見表4-5。目的函數(shù)的優(yōu)先等級(jí)變化為：(1) min z=P1(2d1+32+)+P2d4+P3-(2) min z= P1d3-+P2(2d1+3d3+)+P3d4+試分析原解有什么變化。表4-5解 分析(1)，實(shí)踐是將原目的函數(shù)中d4+，d3-的優(yōu)先因子對(duì)換了一下。這時(shí)將表4-5的檢驗(yàn)數(shù)中的P2、P3行和c

5、j行的P2、P3對(duì)換即可。這時(shí)可見原解仍滿足最優(yōu)解條件。分析(2)，將變化了的優(yōu)先等級(jí)直接反映到表4-5上。再計(jì)算檢驗(yàn)數(shù)，得表4-6。然后進(jìn)展迭代，直到求得新的稱心解為止。從表4-7中得到新的稱心解x1*=4，x2*=12。表4-6第5節(jié) 應(yīng) 用 舉 例例6 某單位指點(diǎn)在思索本單位職工的晉級(jí)調(diào)資方案時(shí)，依次遵守以下規(guī)定：(1) 不超越年工資總額60000元；(2) 每級(jí)的人數(shù)不超越定編規(guī)定的人數(shù)；(3) ，級(jí)的晉級(jí)面盡能夠到達(dá)現(xiàn)有人數(shù)的20%，且無越級(jí)提升；(4) 級(jí)缺乏編制的人數(shù)可錄用新職工，又級(jí)的職工中有10%要退休。有關(guān)資料匯總于表4-8中，問該指點(diǎn)應(yīng)如何擬訂一個(gè)稱心的方案。表4-8解

6、設(shè)x1、x2、x3分別表示提升到、級(jí)和錄用到級(jí)的新職工人數(shù)。對(duì)各目確實(shí)定的優(yōu)先因子為：P1不超越年工資總額60000元；P2每級(jí)的人數(shù)不超越定編規(guī)定的人數(shù)；P3、級(jí)的晉級(jí)面盡能夠到達(dá)現(xiàn)有人數(shù)的20%。先分別建立各目的約束。年工資總額不超越60000元 2000(10-100.1+x1)+ 1500(12-x1+x2)+1000(15-x2+x3)+ d1-d1+ =60000每級(jí)的人數(shù)不超越定編規(guī)定的人數(shù)：對(duì)級(jí)有 10(1-0.1)+x1+d2-d2+=12對(duì)級(jí)有 12-x1+x2+d3-d3+=15對(duì)級(jí)有 15-x2+x3+d4-d4+=15，級(jí)的晉級(jí)面不大于現(xiàn)有人數(shù)的20%，但盡能夠多提；

7、對(duì)級(jí)有 x1+d5-d5+=120.2對(duì)級(jí)有 x2+d6-d6+=150.2目的函數(shù)：min z=P1d1+P2(d2+d3+d4+)+P3(d5-+d6-)以上目的規(guī)劃模型可用單純形法求解，得到多重解。現(xiàn)將這些解匯總于表4-9，這單位的指點(diǎn)再按詳細(xì)情況，從表4-9中選一個(gè)執(zhí)行方案 例7 知有三個(gè)產(chǎn)地給四個(gè)銷地供應(yīng)某種產(chǎn)品，產(chǎn)銷地之間的供需量和單位運(yùn)價(jià)見表4-10。有關(guān)部門在研討調(diào)運(yùn)方案時(shí)依次思索以下七工程標(biāo)，并規(guī)定其相應(yīng)的優(yōu)先等級(jí)：P1B4是重點(diǎn)保證單位，必需全部滿足其需求；P2A3向B1提供的產(chǎn)量不少于100；P3每個(gè)銷地的供應(yīng)量不小于其需求量的80%；P4所定調(diào)運(yùn)方案的總運(yùn)費(fèi)不超越最小運(yùn)

8、費(fèi)調(diào)運(yùn)方案的10%；P5因路段的問題，盡量防止安排將A2的產(chǎn)品往B4；P6給B1和B3的供應(yīng)率要一樣；P7力求總運(yùn)費(fèi)最省。試求稱心的調(diào)運(yùn)方案。表4-10解 上作業(yè)法求得最小運(yùn)費(fèi)的調(diào)運(yùn)方案見表4-11。這時(shí)得最小運(yùn)費(fèi)為2950元，再根據(jù)提出的各工程標(biāo)的要求建立目的規(guī)劃的模型。表4-11供應(yīng)約束 x11+x12+x13+x14300 x21+x22+x23+x24200 x31+x32+x33+x34400需求約束：x11+x21+x31+d1-d1+=200 x12+x22+x32+d2-d2+=100 x13+x23+x33+d3-d3+=450 x14+x24+x34+d4-d4+=250A3向B1提供的產(chǎn)品量不少于100 x31+d5-d5+=100每個(gè)銷地的供應(yīng)量不小于其需求量的80%x11+x21+x31+d6-d6+=2000.8x12+x22+x32+d7-d7+=1000.8x13+x23+x33+d8-d8+=4500.8x14+x24+x34+d9-d9+=2500.8調(diào)運(yùn)方案的總運(yùn)費(fèi)不超越最小運(yùn)費(fèi)調(diào)運(yùn)方案的10%因路段的問題，盡量防止