第六講多目標(biāo)規(guī)劃ppt課件

1、目的規(guī)劃與多目的規(guī)劃一、 目的規(guī)劃問題及其數(shù)學(xué)模型例1 某工廠消費兩種產(chǎn)品，遭到原資料和設(shè)備工時的限制，在 單位利潤等有關(guān)數(shù)據(jù)知的條件下，要求制定一個獲利最大的消費方案。詳細(xì)數(shù)據(jù)見表4-1產(chǎn)品III限量原材料(kg)51060設(shè)備工時(h)4440利潤($/件)68表4-1解 設(shè)產(chǎn)品I和II產(chǎn)量分別為x1和x2，建立線性規(guī)劃模型，李容單純形法求解得到x1=8,x2=2，最大獲利為64元。12121212maxz6x8x5x10 x604x4x40 x , x0 作為線性規(guī)劃的例1，看起來曾經(jīng)圓滿處理。但是，作為實踐問題，就有幾個方面值得進(jìn)一步思索：1目的函數(shù)的選擇的單一化：普通來說，作為一個消

2、費方案，需求滿足多方面的要求。例如，財務(wù)部門希望利潤最大化；行政部門希望規(guī)模最大化；物資部門那么希望物資耗費最小化；銷售部門希望產(chǎn)品多樣化以順應(yīng)市場銷售，降低銷售風(fēng)險；方案部門產(chǎn)品批量盡能夠大，便于安排消費等等。而這些目的有些是一致的，有些那么是相互矛盾的，不可調(diào)和的。需求用數(shù)學(xué)模型來處理問題，怎樣辦呢？ 這時，有兩種方法可用，一是從總多矛盾的目的中，找出主要目的，忽略與之矛盾的其它目的。這樣思索的決策者，就是要建立單目的模型。二是協(xié)調(diào)眾多目的，經(jīng)過相互妥協(xié)達(dá)成可行的多目的規(guī)規(guī)劃。2在實踐問題中，各類約束不一定相容。也就是說，建立的線性規(guī)劃模型不一定有可行解(或者說可行域能夠是空集)。3在用數(shù)

3、學(xué)方法處理實踐問題時，只是強調(diào)數(shù)學(xué)模型與實踐問題的類似性。而并非完全一致，一旦實踐問題發(fā)生變化，那么模型得到的可行解或最優(yōu)解就面臨著不能實施的能夠。 嚴(yán)厲意義上講，數(shù)學(xué)模型相對于實踐問題，都是實踐問題“剛性的本質(zhì)的籠統(tǒng)。線性規(guī)劃也一樣，由其“剛性注定了其局限性?，F(xiàn)代決策者強調(diào)定性和定量分析相結(jié)合，強調(diào)硬技術(shù)和軟技術(shù)的結(jié)合，強調(diào)矛盾和沖突的合理性，強調(diào)妥協(xié)和退讓的必要性。所以線性規(guī)劃就不具備這樣的分析才干。 1961年，查恩斯(A.Charnes)和庫伯(W.W.Cooper)提出目的規(guī)劃(goal programming)，就是彌補了上述線性規(guī)劃局限性。目的規(guī)劃在處置實踐問題時，成認(rèn)各決策要求

4、(即變沖突的的合理性；在作最終決策時，不強調(diào)絕對意義上的最優(yōu)性。因此目的規(guī)劃是更接近于實踐決策過程的決策工具。2目的規(guī)劃的模型例2 在上述例1的根底上，方案人員還要求思索如下意見：1由于產(chǎn)品II銷售疲軟，故希望產(chǎn)品II的產(chǎn)量不超越產(chǎn)品I產(chǎn)量的一半；2原資料嚴(yán)重短缺，消費中應(yīng)防止過量耗費；3最好可以節(jié)約4小時設(shè)備工時；4方案利潤不少于48元。分析：把這四條意見分別看成營銷部門、資料部門、設(shè)備管理部門、財務(wù)部門四個部門的目的愿望。那么在決策的時候，如何協(xié)調(diào)者四個部門的志愿呢。同等對待每個目的志愿，勢必陷于矛盾中。故當(dāng)務(wù)之急是確定四個目的的重要程度或輕重緩急。然后根據(jù)重要程度逐一協(xié)調(diào)。下面引入一些新

5、的變量來處理問題。1優(yōu)先因子和權(quán)系數(shù)不同目的的主次輕重有兩種差別： 一種差別是絕對的，可用優(yōu)先因子PL來表示，只需在高級優(yōu)先因子對應(yīng)的目的已滿足的根底上，才干思索較低級優(yōu)先因子所對應(yīng)的目的；在思索低級優(yōu)先因子對應(yīng)的目的時，絕不允許違背已滿足的高級優(yōu)先因子對應(yīng)的目的。因此，優(yōu)先因子的關(guān)系為PLPL+1,即PL對應(yīng)的目的比PL+1對應(yīng)的目的有絕對的優(yōu)先性。 另外一種差別是相對的，這些目的具有一樣的優(yōu)先因子，它們的重要程度可用權(quán)系數(shù)的不同來表示。 在給出點四個部門的目的中，方案人員根據(jù)部門提出目的的口氣以及在消費中的實踐位置來確定，決策者必需讓不同部門都參與確定優(yōu)先因子，達(dá)成一致后方可做下一步。例2

6、的協(xié)調(diào)結(jié)果是：P1原資料運用限量不得突破；P2產(chǎn)品II產(chǎn)量優(yōu)先思索；P3設(shè)備工時其次思索；P4最后思索方案利潤的要求。 P1P2P3P4.2 列出每個部門的目的愿望分為決策值和目的值。決策值依賴于問題的決策變量，使決策變量的表達(dá)式，目的值是該決策值的一個愿望參考值。比如，設(shè)決策者決議消費產(chǎn)品I x1件，產(chǎn)品II x2件。那么四個部門的目的決策值和目的值分別為部門目標(biāo)決策值f目標(biāo)值f*優(yōu)先級別P營銷部門X2-x1/20P2材料部門5x1+10 x260P1設(shè)備管理4x1+4x240-4=36P3財務(wù)部門6x1+8x248P43偏向變量 對每一個決策目的，引入正負(fù)偏向變量d+和d-，分別表示決策值

7、與目的值的偏向，d+表示決策值超越目的值部分，d-表示決策值缺乏目的值部分。dff *, df *f顯然，根據(jù)定義，有那么，例2的四個目的的決策值和目的值的偏向表達(dá)為121112221233124412ii5x10 xdd60 xxdd024x4xdd366x8xdd48x ,x0d ,d0,i1,2,3,40dd0d,d4各個目的的愿望表達(dá) 任何一個部門在表達(dá)本人的意見時，總是用某種語氣表達(dá)目的決策值和目的值之間的某種比較愿望。歸納起來，不外乎下面三種：1要求決策值不超越目的值min d+ 或min f(d+)2要求決策值不低于目的值min d- 或min f(d-)3要求決策值恰好到達(dá)目的

8、值min d-+d+ 或 min f(d-+d+)根據(jù)上面的定義，例2的四個部門的愿望可以表達(dá)為資料部門：min d1+ 營銷部門：min d2+設(shè)備部門：min d3+財務(wù)部門：min d4- 對于資料部門，基于語氣的強硬，也可以把資料部門的愿望改為d1+=0。這樣的話這個約束就由可以商量稱為軟約束轉(zhuǎn)化為沒有商量的余地稱為硬約束，并不改動問題的性質(zhì)。根據(jù)上面引入的概念和分析，例2的規(guī)劃模型為11223344121112221233124412iimin p d ,p d ,p d ,p d 5x10 xdd60 xxdd024x4xdd366x8xdd48x ,x0d ,d0,i1,2,3,

9、4 在建立目的規(guī)劃模型時，盡能夠利用各種決策技術(shù)，盡量減少客觀性和片面性。目的規(guī)劃的普通方式L,.,2, 1i ,0d,dn,.,2, 1j,0 x,L,.2, 1i ,gddxc,m,.,2, 1i ,b),(xa. t . s)dwdw(pzminiijiiin1jjijin1jjijq1kL1jjkjjkjk硬約束軟約束例2 多目的供應(yīng)問題 知三個工廠消費的產(chǎn)品供應(yīng)給四個用戶，各工廠消費量、用戶需求量及從各個工廠到用戶的單位產(chǎn)品的運輸費用如表4-2所示。由于總消費量小于總需求量，上級部門經(jīng)研討決議，制定了調(diào)配方案的8項目的，并規(guī)定了重要性的次序。表4-2用 戶 1 2 3 4 消費量工廠

10、1工廠2工廠3需求量534200255100642450763250300200400第一目的：用戶4為重要部門，需求量必需全部滿足；第二目的：供應(yīng)用戶1的產(chǎn)品中，工廠3的產(chǎn)品不少于100個單位；第三目的：每個用戶的滿足率不低于80%；第四目的：應(yīng)盡量滿足個用戶的要求；第五目的：新方案的總運費不超越原運輸問題的總運費的10%；第六目的：因道路問題，工廠2到用戶4的道路盡量防止運輸；第七目的：用戶1和用戶3的滿足率應(yīng)盡量堅持平衡；第八目的：力求減少總運費；請列出相應(yīng)的目的規(guī)劃模型，并用Lingo求解。解設(shè)從工廠i向用戶j調(diào)運產(chǎn)品量為xij,i=1,2,3;j=1,2,3,4;Cij表示從工廠i向

11、用戶j調(diào)運的單位產(chǎn)品的費用；ai表示工廠i的產(chǎn)量；i=1,2,3;bj表示用戶j的需求量，j=1,2,3,4; 由于目的5中需求用到不思索任何目的的調(diào)運方案下的最小費用，故需求先求解如下線性規(guī)劃模型3i41jijijxczmin, 3 ,2, 1j; 3 ,2, 1i ,0 x4, 3 ,2, 1j,bx3 ,2, 1i ,axijj31iiji41jijs.t.上述模型的求解程序及結(jié)果為sets:gch/1.3/:a;yhu/1.4/:b;link(gch,yhu):x,c;endsetsmin=sum(link:c*x);for(gch(i):sum(yhu(j):x(i,j)=a(i);

12、for(yhu(j):sum(gch(i):x(i,j)=b(j);data:a=300,200,400;b=200,100,450,250;c=5 2 6 73 5 4 64 5 2 3;enddata計算得到最小運費為2950元.建立目的規(guī)劃引入p1,p8表示各個目的的優(yōu)先順序；di+，di-表示各個決策目的與參考目的的正偏向和負(fù)偏向;i=1,2,3,下面寫出各個約束硬約束供應(yīng)約束,400 xxxx,200 xxxx,300 xxxx343332312423222114131211系列軟約束1用戶4必需全部滿足;250ddxxx113424141dmin2供應(yīng)用戶1的產(chǎn)品中，工廠3的產(chǎn)品不

13、少于100單位;100ddx2231-2dmin3每個用戶的滿足率不低于80%；四個用戶的80%需求量分別為160,80,360,200，即,200ddxxx,360ddxxx,80ddxxx,160ddxxx66342414553323134432221233312111654-3ddddmin4應(yīng)盡量滿足個用戶的要求,250ddxxx,450ddxxx,100ddxxx,200ddxxx10103424149933231388322212773121111098-7ddddmin5新運費盡量不超越不思索各個目的費用的10%：,324529501 .1ddxc111131i41jijij11

14、dmin6因道路限制，工廠2到用戶4的道路的運輸義務(wù)應(yīng)盡量防止：, 0ddx12122412dmin7 用戶1和用戶3的滿足率盡量平衡：, 0dd450 xxx200 xxx13133323133121111313ddmin8力求減少總費用：,2950ddxc141431i41jijij 14dmin變量要求14,2, 1i ,0d,d4, 3 ,2, 1j;3 ,2, 1i ,0 xiiij按照優(yōu)先級別寫出目的函數(shù)14813137126115109874654332211dp)dd(pdpdp)dddd(p)dddd(pdpdpmins.t.硬約束供應(yīng)約束,400 xxxx,200 xxxx

15、,300 xxxx343332312423222114131211;250ddxxx11342414;100ddx2231軟約束,200ddxxx,360ddxxx,80ddxxx,160ddxxx66342414553323134432221233312111,250ddxxx,450ddxxx,100ddxxx,200ddxxx1010342414993323138832221277312111,324529501 .1ddxc111131i41jijij, 0ddx121224, 0dd450 xxx200 xxx1313332313312111,2950ddxc141431i41jij

16、ij 14,2, 1i ,0d,d4, 3 ,2, 1j;3 ,2, 1i ,0 xiiij二、利用lingo計算目的規(guī)劃 多目的規(guī)劃本質(zhì)是一個多個目的的線性規(guī)劃問題，仍可以用Lingo求解，下面以例1和例題2為計算例子。11223344121112221233124412iimin p d ,p d ,p d ,p d 5x10 xdd60 xxdd024x4xdd366x8xdd48x ,x0d ,d0,i1,2,3,45*x1+10*x2-d11+d12=60;x2-x1/2-d21+d22=0;4*x1+4*x2-d31+d32=36;6*x1+8*x2-d41+d42=48;d12=

17、0;d22=0;d32=0;min=d42; Global optimal solution found at iteration: 4 Objective value: 0.000000 Variable Value Reduced Cost X1 6.000000 0.000000 X2 3.000000 0.000000 D11 0.000000 0.000000 D12 0.000000 0.000000 D21 0.000000 0.000000 D22 0.000000 0.000000 D31 0.000000 0.000000 D32 0.000000 0.000000 D41

18、 12.00000 0.000000 D42 0.000000 1.000000sets:chandi/1.3/:a;xiaodi/1.4/:b;link(chandi,xiaodi):c,x;endsetsfor(chandi(i):sum(xiaodi(j):x(i,j)=a(i);sum(chandi(i):x(i,4)+d11-d12=250;x(3,1)+d21-d22=100;sum(chandi(i):x(i,1)+d31-d32=160;sum(chandi(i):x(i,2)+d41-d42=80;sum(chandi(i):x(i,3)+d51-d52=360;sum(chandi(i):x(i,4)+d61-d62=200;sum(chandi(i):x(i,1)+d71-d72=200;sum(chandi(i):x(i,2)+d81-d82=100;sum(chandi(i):x(i,3)+d91-d92=450;sum(chandi(i):x(i,4)+d101-d102=250;sum(link:c*x)+d111-d112=1.1*2950;x(2,4)+d121-d122=0;sum(chandi(i):x(i,1)/200-sum(chandi