運(yùn)籌學(xué)與目標(biāo)規(guī)劃.ppt

1、Chapter9 目標(biāo)規(guī)劃( Goal programming ),1.目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型 2.目標(biāo)規(guī)劃的圖解法 3.目標(biāo)規(guī)劃應(yīng)用舉例 4.用管理運(yùn)籌學(xué)軟件2.0求解目標(biāo)規(guī)劃的注意事項(xiàng),本章主要內(nèi)容：,1.目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型,問題的提出： 目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)經(jīng)濟(jì)管理多目標(biāo)決策的需要而由線性規(guī)劃逐步發(fā)展起來的一個分支。 由于現(xiàn)代化企業(yè)內(nèi)專業(yè)分工越來越細(xì)，組織機(jī)構(gòu)日益復(fù)雜，為了統(tǒng)一協(xié)調(diào)企業(yè)各部門圍繞一個整體的目標(biāo)工作，產(chǎn)生了目標(biāo)管理這種先進(jìn)的管理技術(shù)。目標(biāo)規(guī)劃是實(shí)行目標(biāo)管理的有效工具，它根據(jù)企業(yè)制定的經(jīng)營目標(biāo)以及這些目標(biāo)的輕重緩急次序，考慮現(xiàn)有資源情況，分析如何達(dá)到規(guī)

2、定目標(biāo)或從總體上離規(guī)定目標(biāo)的差距為最小。,例1 某企業(yè)計(jì)劃生產(chǎn)甲，乙兩種產(chǎn)品，這些產(chǎn)品分別要在A,B,C,D四種不同設(shè)備上加工。按工藝文件規(guī)定，如表所示。,問該企業(yè)應(yīng)如何安排計(jì)劃，使得計(jì)劃期內(nèi)的總利潤收入為最大？,解：設(shè)甲、乙產(chǎn)品的產(chǎn)量分別為x1，x2，建立線性規(guī)劃模型：,其最優(yōu)解為x14，x22，z14元,但企業(yè)的經(jīng)營目標(biāo)不僅僅是利潤，而且要考慮多個方面，如： 力求使利潤指標(biāo)不低于12元； 考慮到市場需求，甲、乙兩種產(chǎn)品的生產(chǎn)量需保持1:1的比例； C和D為貴重設(shè)備，嚴(yán)格禁止超時使用； 設(shè)備B必要時可以加班，但加班時間要控制；設(shè)備A即要求充分利用，又盡可能不加班。,要考慮上述多方面的目標(biāo)，需

3、要借助目標(biāo)規(guī)劃的方法。,線性規(guī)劃模型存在的局限性： 1）要求問題的解必須滿足全部約束條件，實(shí)際問題中并非所有約束都需要嚴(yán)格滿足。 2）只能處理單目標(biāo)的優(yōu)化問題。實(shí)際問題中，目標(biāo)和約束可以相互轉(zhuǎn)化。 3）線性規(guī)劃中各個約束條件都處于同等重要地位，但現(xiàn)實(shí)問題中，各目標(biāo)的重要性即有層次上的差別，同一層次中又可以有權(quán)重上的區(qū)分。 4）線性規(guī)劃尋求最優(yōu)解，但很多實(shí)際問題中只需找出滿意解就可以。,目標(biāo)規(guī)劃怎樣解決上述線性規(guī)劃模型建模中的局限性？,1）設(shè)置偏差變量，用來表明實(shí)際值同目標(biāo)值之間的差異,偏差變量用下列符號表示：,d+超出目標(biāo)的偏差，稱正偏差變量 d-未達(dá)到目標(biāo)的偏差，稱負(fù)偏差變量,正負(fù)偏差變量兩

4、者必有一個為0。 當(dāng)實(shí)際值超出目標(biāo)值時： d+0, d-=0; 當(dāng)實(shí)際值未達(dá)到目標(biāo)值時： d+=0, d-0; 當(dāng)實(shí)際值同目標(biāo)值恰好一致時： d+=0, d-=0; 故恒有d+d-=0,2）統(tǒng)一處理目標(biāo)和約束,對有嚴(yán)格限制的資源使用建立系統(tǒng)約束，數(shù)學(xué)形式同線性規(guī)劃中的約束條件。如C和D設(shè)備的使用限制。,對不嚴(yán)格限制的約束，連同原線性規(guī)劃建模時的目標(biāo)，均通過目標(biāo)約束來表達(dá)。,（1）例如要求甲、乙兩種產(chǎn)品保持1:1的比例，系統(tǒng)約束表達(dá)為： x1=x2。由于這個比例允許有偏差， 當(dāng)x1x2時，出現(xiàn)負(fù)偏差d-，即： x1+d- =x2或x1x2+d- =0 當(dāng)x1x2時，出現(xiàn)正偏差d+，即： x1-d

5、+ =x2或x1x2-d+ =0,正負(fù)偏差不可能同時出現(xiàn)，故總有： x1x2+d-d+ =0,若希望甲的產(chǎn)量不低于乙的產(chǎn)量，即不希望d-0,用目標(biāo)約束可表為:,若希望甲的產(chǎn)量低于乙的產(chǎn)量，即不希望d0,用目標(biāo)約束可表為:,若希望甲的產(chǎn)量恰好等于乙的產(chǎn)量，即不希望d0,也不希望d-0用目標(biāo)約束可表為:,(3）設(shè)備B必要時可加班及加班時間要控制，目標(biāo)約束表示為：,(2）力求使利潤指標(biāo)不低于12元，目標(biāo)約束表示為：,(4)設(shè)備A既要求充分利用，又盡可能不加班，目標(biāo)約束表示為：,由上可知，目標(biāo)規(guī)劃的目標(biāo)函數(shù)只能是 minZ = f（ d +，d - ） 其基本形式有三種： （1） 要求恰好達(dá)到目標(biāo)值，

6、即正、負(fù)偏差變量都要盡可能地小 minZ = f（ d + d - ） （2） 要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值，即正偏差變量要盡可能地小 minZ = f（ d +） （3） 要求超過目標(biāo)值，即超過量不限，但必須是即負(fù)偏差變量要盡可能地小 minZ = f（ d -）,3)目標(biāo)的優(yōu)先級與權(quán)系數(shù),在一個目標(biāo)規(guī)劃的模型中，為達(dá)到某一目標(biāo)可犧牲其他一些目標(biāo)，稱這些目標(biāo)是屬于不同層次的優(yōu)先級。優(yōu)先級層次的高低可分別通過優(yōu)先因子P1,P2,表示。對于同一層次優(yōu)先級的不同目標(biāo)，按其重要程度可分別乘上不同的權(quán)系數(shù)。權(quán)系數(shù)是一個個具體數(shù)字(權(quán)系數(shù)可以根據(jù)具體情況而定)，乘上的權(quán)系數(shù)越大，表明該目標(biāo)越重要

7、。,現(xiàn)假定：,第1優(yōu)先級P1企業(yè)利潤； 第2優(yōu)先級P2甲乙產(chǎn)品的產(chǎn)量保持1:1的比例 第3優(yōu)先級P3設(shè)備A,B盡量不超負(fù)荷工作。其中設(shè)備A的重要性比設(shè)備B大三倍。,上述目標(biāo)規(guī)劃模型可以表示為：,達(dá)成函數(shù),目標(biāo)約束,其中：gk為第k個目標(biāo)約束的預(yù)期目標(biāo)值， 和 為pl 優(yōu)先因子對應(yīng)各目標(biāo)的權(quán)系數(shù)。,絕對約束,目標(biāo)規(guī)劃數(shù)學(xué)模型的一般形式,用目標(biāo)規(guī)劃求解問題的過程：,明確問題，列出目標(biāo)的優(yōu)先級和權(quán)系數(shù),構(gòu)造目標(biāo)規(guī)劃模型,求出滿意解,滿意否？,分析各項(xiàng)目標(biāo)完成情況,據(jù)此制定出決策方案,N,Y,2.目標(biāo)規(guī)劃的圖解法,適用兩個變量的目標(biāo)規(guī)劃問題，但其操作簡單，原理一目了然。同時，也有助于理解一般目標(biāo)規(guī)劃的

8、求解原理和過程。,圖解法解題步驟：,1. 將所有約束條件（包括目標(biāo)約束和絕對約束，暫不考慮正負(fù)偏差變量）的直線方程分別標(biāo)示于坐標(biāo)平面上。 2. 確定系統(tǒng)約束的可行域。 3. 在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、負(fù)偏差變量值增大的方向。 4. 求滿足最高優(yōu)先等級目標(biāo)的解 5. 轉(zhuǎn)到下一個優(yōu)先等級的目標(biāo)，再不破壞所有較高優(yōu)先等級目標(biāo)的前提下，求出該優(yōu)先等級目標(biāo)的解 6. 重復(fù)5，直到所有優(yōu)先等級的目標(biāo)都已審查完畢為止 7. 確定最優(yōu)解和滿意解。,例2 用圖解法求解下列目標(biāo)規(guī)劃問題,(a),(b),(c),(d ),x2,x1,(e),(f),d1-,d1+,d2+,d2-,d3-,d3+,d

9、4-,d4+,滿意解(3,3),0,4,6,8,3,4,6,2,2,x1,x2,(a),(b),d1+,d1-,(c),d2-,d2+,(d),d3-,d3+,G,D,滿意解是線段GD上任意點(diǎn),其中G點(diǎn)X(2,4),D點(diǎn)X(10/3,10/3),0,5.5,10,5,5.6,11,2,4,10/3,10/3,5,10,7,例3,O,x1,x2,20,40,60,50,20,40,60,50,a,b,d1-,d1+,d2-,d2+,c,d,d3-,d3+,d4-,d4+,(24,26),滿意解X=(24，26),例4,3.目標(biāo)規(guī)劃應(yīng)用舉例,例5 已知一個生產(chǎn)計(jì)劃的線性規(guī)劃模型如下，其中目標(biāo)函數(shù)為

10、總利潤，x1,x2 為產(chǎn)品A、B產(chǎn)量。,現(xiàn)有下列目標(biāo)： 1. 要求總利潤必須超過 2500 元； 2. 考慮產(chǎn)品受市場影響，為避免積壓，A、B的生產(chǎn)量不超過 60 件和 100 件； 3. 由于甲資源供應(yīng)比較緊張，不要超過現(xiàn)有量140。 試建立目標(biāo)規(guī)劃模型，并用圖解法求解。,解：以產(chǎn)品 A,B 的單件利潤比 2.5 :1 為權(quán)系數(shù)，模型如下：,0,x2,0,x1,140 120 100 80 60 40 20,20 40 60 80 100,A,B,C,D,故: C(60 ,58.3)為所求的滿意解。,(24,26),例6 某單位領(lǐng)導(dǎo)在考慮本單位職工的升級調(diào)資方案時，依次遵守以下規(guī)定： (1)

11、 不超過年工資總額60000元； (2) 每級的人數(shù)不超過定編規(guī)定的人數(shù)； (3) ，級的升級面盡可能達(dá)到現(xiàn)有人數(shù)的20%，且無越級提升； (4) 級不足編制的人數(shù)可錄用新職工，又級的職工中有10%要退休。 有關(guān)資料匯總于下表中，問該領(lǐng)導(dǎo)應(yīng)如何擬訂一個滿意的方案。,解：設(shè)x1、x2、x3分別表示提升到、級和錄用到級的新職工人數(shù)。對各目標(biāo)確定的優(yōu)先因子為： P1不超過年工資總額60000元； P2每級的人數(shù)不超過定編規(guī)定的人數(shù)； P3、級的升級面盡可能達(dá)到現(xiàn)有人數(shù)的20%。 先分別建立各目標(biāo)約束。 年工資總額不超過60000元 2000(10100.1+x1)+1500(12x1+x2)+100

12、0(15x2+x3)+d1-d1+=60000 每級的人數(shù)不超過定編規(guī)定的人數(shù)： 對級有 10(1 0.1)+x1+d2d2+=12 對級有 12 x1+x2+d3d3+=15 對級有 15 x2+x3+d4 d4+=15 ，級的升級面不大于現(xiàn)有人數(shù)的20%，但盡可能多提： 對級有 x1+d5 d5+=120.2 對級有 x2+d6 d6+=150.2 目標(biāo)函數(shù)：min z=P1d1+P2(d2+d3+d4+)+P3(d5+d6),以上目標(biāo)規(guī)劃可用單純形法求解，得到多重解。將這些解匯總于下表，單位領(lǐng)導(dǎo)再按具體情況，從中選出執(zhí)行方案。,例7 已知有三個產(chǎn)地給四個銷地供應(yīng)某種產(chǎn)品，產(chǎn)銷地之間的供需

13、量和單位運(yùn)價見下表。有關(guān)部門在研究調(diào)運(yùn)方案時依次考慮以下七項(xiàng)目標(biāo)，并規(guī)定其相應(yīng)的優(yōu)先等級： P1B4是重點(diǎn)保證單位，必須全部滿足其需要； P2A3向B1提供的產(chǎn)量不少于100； P3每個銷地的供應(yīng)量不小于其需要量的80%； P4所定調(diào)運(yùn)方案的總運(yùn)費(fèi)不超過最小運(yùn)費(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)方案。,解 上作業(yè)法求得最小運(yùn)費(fèi)的調(diào)運(yùn)方案見下表。這時得最小運(yùn)費(fèi)為2950元，再根據(jù)提出的各項(xiàng)目標(biāo)的要求建立目標(biāo)規(guī)劃的模型。,供應(yīng)約束 x11+x12+x13+x14300 x21+x22+x23

14、+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+=250 A3向B1提供的產(chǎn)品量不少于100 x31+d5 d5+=100,每個銷地的供應(yīng)量不小于其需要量的80% x11+x21+x31+d6d6+=2000.8 x12+x22+x32+d7 d7+=1000.8 x13+x23+x33+d8 d8+=4500.8 x14+x24+x34+d9 d9+=2500.8 調(diào)運(yùn)方案的總運(yùn)費(fèi)不超過最小運(yùn)費(fèi)調(diào)運(yùn)方案的10%,因路段的問題，盡量避免安排將A2的產(chǎn)品運(yùn)往B4 x24+d11d11+=0 給B1和B3的供應(yīng)率要相同 (x1