1、目標(biāo)規(guī)劃與多目標(biāo)規(guī)劃一、 目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型例1 某工廠生產(chǎn)兩種產(chǎn)品，受到原材料和設(shè)備工時(shí)的限制，在 單位利潤(rùn)等有關(guān)數(shù)據(jù)已知的條件下，要求制訂一個(gè)獲利最大的生產(chǎn)計(jì)劃。具體數(shù)據(jù)見表4-1產(chǎn)品III限量原材料(kg)51060設(shè)備工時(shí)(h)4440利潤(rùn)($/件)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)圓滿解決。但是，作為實(shí)際問題，就有幾個(gè)方面值得進(jìn)一步考慮：（1）目標(biāo)函數(shù)的選擇的單一化：一般來說，作為

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

3、3）在用數(shù)學(xué)方法解決實(shí)際問題時(shí)，只是強(qiáng)調(diào)數(shù)學(xué)模型與實(shí)際問題的相似性。而并非完全一致，一旦實(shí)際問題發(fā)生變化，則模型得到的可行解或最優(yōu)解就面臨著不能實(shí)施的可能。 嚴(yán)格意義上講，數(shù)學(xué)模型相對(duì)于實(shí)際問題，都是實(shí)際問題“剛性”的本質(zhì)的抽象。線性規(guī)劃也一樣，由其“剛性”注定了其局限性?，F(xiàn)代決策者強(qiáng)調(diào)定性和定量分析相結(jié)合，強(qiáng)調(diào)硬技術(shù)和軟技術(shù)的結(jié)合，強(qiáng)調(diào)矛盾和沖突的合理性，強(qiáng)調(diào)妥協(xié)和讓步的必要性。所以線性規(guī)劃就不具備這樣的分析能力。 1961年，查恩斯(A.Charnes)和庫伯(W.W.Cooper)提出目標(biāo)規(guī)劃(goal programming)，就是彌補(bǔ)了上述線性規(guī)劃局限性。目標(biāo)規(guī)劃在處理實(shí)際問題時(shí)，承

4、認(rèn)各決策要求(即變沖突的）的合理性；在作最終決策時(shí)，不強(qiáng)調(diào)絕對(duì)意義上的最優(yōu)性。因此目標(biāo)規(guī)劃是更接近于實(shí)際決策過程的決策工具。2目標(biāo)規(guī)劃的模型例2 在上述例1的基礎(chǔ)上，計(jì)劃人員還要求考慮如下意見：（1）由于產(chǎn)品II銷售疲軟，故希望產(chǎn)品II的產(chǎn)量不超過產(chǎn)品I產(chǎn)量的一半；（2）原材料嚴(yán)重短缺，生產(chǎn)中應(yīng)避免過量消耗；（3）最好能夠節(jié)約4小時(shí)設(shè)備工時(shí)；（4）計(jì)劃利潤(rùn)不少于48元。分析：把這四條意見分別看成營(yíng)銷部門、材料部門、設(shè)備管理部門、財(cái)務(wù)部門四個(gè)部門的目標(biāo)愿望。那么在決策的時(shí)候，如何協(xié)調(diào)者四個(gè)部門的意愿呢。同等對(duì)待每個(gè)目標(biāo)意愿，勢(shì)必陷于矛盾中。故當(dāng)務(wù)之急是確定四個(gè)目標(biāo)的重要程度或輕重緩急。然后根據(jù)重

5、要程度逐一協(xié)調(diào)。下面引入一些新的變量來解決問題。1優(yōu)先因子和權(quán)系數(shù)不同目標(biāo)的主次輕重有兩種差別： 一種差別是絕對(duì)的，可用優(yōu)先因子PL來表示，只有在高級(jí)優(yōu)先因子對(duì)應(yīng)的目標(biāo)已滿足的基礎(chǔ)上，才能考慮較低級(jí)優(yōu)先因子所對(duì)應(yīng)的目標(biāo)；在考慮低級(jí)優(yōu)先因子對(duì)應(yīng)的目標(biāo)時(shí)，絕不允許違背已滿足的高級(jí)優(yōu)先因子對(duì)應(yīng)的目標(biāo)。因此，優(yōu)先因子的關(guān)系為PLPL+1,即PL對(duì)應(yīng)的目標(biāo)比PL+1對(duì)應(yīng)的目標(biāo)有絕對(duì)的優(yōu)先性。 另外一種差別是相對(duì)的，這些目標(biāo)具有相同的優(yōu)先因子，它們的重要程度可用權(quán)系數(shù)的不同來表示。 在給出點(diǎn)四個(gè)部門的目標(biāo)中，計(jì)劃人員根據(jù)部門提出目標(biāo)的口氣以及在生產(chǎn)中的實(shí)際地位來確定，決策者必須讓不同部門都參與確定優(yōu)先因子

6、，達(dá)成一致后方可做下一步。例2的協(xié)調(diào)結(jié)果是：P1原材料使用限量不得突破；P2產(chǎn)品II產(chǎn)量?jī)?yōu)先考慮；P3設(shè)備工時(shí)其次考慮；P4最后考慮計(jì)劃利潤(rùn)的要求。 P1P2P3P4.2 列出每個(gè)部門的目標(biāo)愿望分為決策值和目標(biāo)值。決策值依賴于問題的決策變量，使決策變量的表達(dá)式，目標(biāo)值是該決策值的一個(gè)愿望參考值。比如，設(shè)決策者決定生產(chǎn)產(chǎn)品I x1件，產(chǎn)品II x2件。則四個(gè)部門的目標(biāo)決策值和目標(biāo)值分別為部門目標(biāo)決策值f目標(biāo)值f*優(yōu)先級(jí)別P營(yíng)銷部門X2-x1/20P2材料部門5x1+10 x260P1設(shè)備管理4x1+4x240-4=36P3財(cái)務(wù)部門6x1+8x248P43偏差變量 對(duì)每一個(gè)決策目標(biāo)，引入正負(fù)偏差變

7、量d+和d-，分別表示決策值與目標(biāo)值的偏差，d+表示決策值超過目標(biāo)值部分，d-表示決策值不足目標(biāo)值部分。dff *, df *f顯然，根據(jù)定義，有那么，例2的四個(gè)目標(biāo)的決策值和目標(biāo)值的偏差表達(dá)為121112221233124412ii5x10 xdd60 xxdd024x4xdd366x8xdd48x ,x0d ,d0,i1,2,3,40dd0d,d4各個(gè)目標(biāo)的欲望表達(dá) 任何一個(gè)部門在表達(dá)自己的意見時(shí)，總是用某種語氣表達(dá)目標(biāo)決策值和目標(biāo)值之間的某種比較欲望。歸納起來，不外乎下面三種：（1）要求決策值不超過目標(biāo)值min d+ 或min f(d+)（2）要求決策值不低于目標(biāo)值min d- 或min

8、 f(d-)（3）要求決策值恰好達(dá)到目標(biāo)值min d-+d+ 或 min f(d-+d+)根據(jù)上面的定義，例2的四個(gè)部門的欲望可以表達(dá)為材料部門：min d1+ 營(yíng)銷部門：min d2+設(shè)備部門：min d3+財(cái)務(wù)部門：min d4- 對(duì)于材料部門，基于語氣的強(qiáng)硬，也可以把材料部門的欲望改為d1+=0。這樣的話這個(gè)約束就由可以商量（稱為軟約束）轉(zhuǎn)化為沒有商量的余地（稱為硬約束），并不改變問題的性質(zhì)。根據(jù)上面引入的概念和分析，例2的規(guī)劃模型為11223344121112221233124412iimin p d ,p d ,p d ,p d 5x10 xdd60 xxdd024x4xdd366x

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

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

11、,2,3;j=1,2,3,4;Cij表示從工廠i向用戶j調(diào)運(yùn)的單位產(chǎn)品的費(fèi)用；ai表示工廠i的產(chǎn)量；i=1,2,3;bj表示用戶j的需求量，j=1,2,3,4; 由于目標(biāo)5中需要用到不考慮任何目標(biāo)的調(diào)運(yùn)方案下的最小費(fèi)用，故需要先求解如下線性規(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

12、):sum(yhu(j):x(i,j)=a(i);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計(jì)算得到最小運(yùn)費(fèi)為2950元.建立目標(biāo)規(guī)劃引入p1,p8表示各個(gè)目標(biāo)的優(yōu)先順序；di+，di-表示各個(gè)決策目標(biāo)與參考目標(biāo)的正偏差和負(fù)偏差;i=1,2,3,下面寫出各個(gè)約束硬約束（供應(yīng)約束）,400 xxxx,200 xxxx,300 xxxx343332312423222114131211系列軟約束（1）用戶4必須全部滿足;250ddxxx11

13、3424141dmin（2）供應(yīng)用戶1的產(chǎn)品中，工廠3的產(chǎn)品不少于100單位;100ddx2231-2dmin（3）每個(gè)用戶的滿足率不低于80%；四個(gè)用戶的80%需求量分別為160,80,360,200，即,200ddxxx,360ddxxx,80ddxxx,160ddxxx66342414553323134432221233312111654-3ddddmin（4）應(yīng)盡量滿足個(gè)用戶的要求,250ddxxx,450ddxxx,100ddxxx,200ddxxx10103424149933231388322212773121111098-7ddddmin（5）新運(yùn)費(fèi)盡量不超過不考慮各個(gè)目標(biāo)費(fèi)用的

14、10%：,324529501 .1ddxc111131i41jijij11dmin（6）因道路限制，工廠2到用戶4的路線的運(yùn)輸任務(wù)應(yīng)盡量避免：, 0ddx12122412dmin（7） 用戶1和用戶3的滿足率盡量平衡：, 0dd450 xxx200 xxx13133323133121111313ddmin（8）力求減少總費(fèi)用：,2950ddxc141431i41jijij 14dmin變量要求14,2, 1i ,0d,d4, 3 ,2, 1j;3 ,2, 1i ,0 xiiij按照優(yōu)先級(jí)別寫出目標(biāo)函數(shù)14813137126115109874654332211dp)dd(pdpdp)dddd(p

15、)dddd(pdpdpmins.t.硬約束（供應(yīng)約束）,400 xxxx,200 xxxx,300 xxxx343332312423222114131211;250ddxxx11342414;100ddx2231軟約束,200ddxxx,360ddxxx,80ddxxx,160ddxxx66342414553323134432221233312111,250ddxxx,450ddxxx,100ddxxx,200ddxxx1010342414993323138832221277312111,324529501 .1ddxc111131i41jijij, 0ddx121224, 0dd450 xx

16、x200 xxx1313332313312111,2950ddxc141431i41jijij 14,2, 1i ,0d,d4, 3 ,2, 1j;3 ,2, 1i ,0 xiiij二、利用lingo計(jì)算目標(biāo)規(guī)劃 多目標(biāo)規(guī)劃實(shí)質(zhì)是一個(gè)多個(gè)目標(biāo)的線性規(guī)劃問題，仍可以用Lingo求解，下面以例1和例題2為計(jì)算例子。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

17、*x1+4*x2-d31+d32=36;6*x1+8*x2-d41+d42=48;d12=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 D3

18、1 0.000000 0.000000 D32 0.000000 0.000000 D41 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-d

19、42=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(i):x(i,3)/450+d131-d132=0;sum(link:c*x)+d141-d142=2950;data:a=300,200,400;b=200,100,450,250;c=5 2 6 73 5 4 64 5 2 3;enddatad11=0;d21=0;d31=0;d41=0;d51=0;d61=0;d71+d81+d91+d101=1