第九講多目標規(guī)劃

目標規(guī)劃與多目標規(guī)劃一、目標規(guī)劃問題及其數(shù)學模型例1某工廠生產(chǎn)兩種產(chǎn)品，受到原材料和設備工時的限制，在單位利潤等有關數(shù)據(jù)已知的條件下，要求制訂一個獲利最大的生產(chǎn)計劃。具體數(shù)據(jù)見表4-1產(chǎn)品III限量原材料(kg)51060設備工時(h)4440利潤($/件)68表4-1解設產(chǎn)品I和II產(chǎn)量分別為x1和x2，建立線性規(guī)劃模型，李容單純形法求解得到x1=8,x2=2，最大獲利為64元。

作為線性規(guī)劃的例1，看起來已經(jīng)圓滿解決。但是，作為實際問題，就有幾個方面值得進一步考慮：（1）目標函數(shù)的選擇的單一化：一般來說，作為一個生產(chǎn)計劃，需要滿足多方面的要求。例如，財務部門希望利潤最大化；行政部門希望規(guī)模最大化；物資部門則希望物資消耗最小化；銷售部門希望產(chǎn)品多樣化以適應市場銷售，降低銷售風險；計劃部門產(chǎn)品批量盡可能大，便于安排生產(chǎn)等等。而這些目標有些是一致的，有些則是相互矛盾的，不可調和的。需要用數(shù)學模型來解決問題，怎么辦呢？

這時，有兩種方法可用，一是從總多矛盾的目標中，找出主要目標，忽略與之矛盾的其它目標。這樣考慮的決策者，就是要建立單目標模型。二是協(xié)調眾多目標，通過相互妥協(xié)達成可行的多目標規(guī)規(guī)劃。（2）在實際問題中，各類約束不一定相容。也就是說，建立的線性規(guī)劃模型不一定有可行解(或者說可行域可能是空集)。（3）在用數(shù)學方法解決實際問題時，只是強調數(shù)學模型與實際問題的相似性。而并非完全一致，一旦實際問題發(fā)生變化，則模型得到的可行解或最優(yōu)解就面臨著不能實施的可能。

嚴格意義上講，數(shù)學模型相對于實際問題，都是實際問題“剛性”的本質的抽象。線性規(guī)劃也一樣，由其“剛性”注定了其局限性?，F(xiàn)代決策者強調定性和定量分析相結合，強調硬技術和軟技術的結合，強調矛盾和沖突的合理性，強調妥協(xié)和讓步的必要性。所以線性規(guī)劃就不具備這樣的分析能力。1961年，查恩斯(A.Charnes)和庫伯(W.W.Cooper)提出目標規(guī)劃(goalprogramming)，就是彌補了上述線性規(guī)劃局限性。目標規(guī)劃在處理實際問題時，承認各決策要求(即變沖突的）的合理性；在作最終決策時，不強調絕對意義上的最優(yōu)性。因此目標規(guī)劃是更接近于實際決策過程的決策工具。2目標規(guī)劃的模型例2在上述例1的基礎上，計劃人員還要求考慮如下意見：（1）由于產(chǎn)品II銷售疲軟，故希望產(chǎn)品II的產(chǎn)量不超過產(chǎn)品I產(chǎn)量的一半；（2）原材料嚴重短缺，生產(chǎn)中應避免過量消耗；（3）最好能夠節(jié)約4小時設備工時；（4）計劃利潤不少于48元。分析：把這四條意見分別看成營銷部門、材料部門、設備管理部門、財務部門四個部門的目標愿望。那么在決策的時候，如何協(xié)調者四個部門的意愿呢。同等對待每個目標意愿，勢必陷于矛盾中。故當務之急是確定四個目標的重要程度或輕重緩急。然后根據(jù)重要程度逐一協(xié)調。下面引入一些新的變量來解決問題。1優(yōu)先因子和權系數(shù)不同目標的主次輕重有兩種差別：一種差別是絕對的，可用優(yōu)先因子PL來表示，只有在高級優(yōu)先因子對應的目標已滿足的基礎上，才能考慮較低級優(yōu)先因子所對應的目標；在考慮低級優(yōu)先因子對應的目標時，絕不允許違背已滿足的高級優(yōu)先因子對應的目標。因此，優(yōu)先因子的關系為PL>>PL+1,即PL對應的目標比PL+1對應的目標有絕對的優(yōu)先性。另外一種差別是相對的，這些目標具有相同的優(yōu)先因子，它們的重要程度可用權系數(shù)的不同來表示。

在給出點四個部門的目標中，計劃人員根據(jù)部門提出目標的口氣以及在生產(chǎn)中的實際地位來確定，決策者必須讓不同部門都參與確定優(yōu)先因子，達成一致后方可做下一步。例2的協(xié)調結果是：P1原材料使用限量不得突破；P2產(chǎn)品II產(chǎn)量優(yōu)先考慮；P3設備工時其次考慮；P4最后考慮計劃利潤的要求。

P1>>P2>>P3>>P4.2

列出每個部門的目標愿望分為決策值和目標值。決策值依賴于問題的決策變量，使決策變量的表達式，目標值是該決策值的一個愿望參考值。比如，設決策者決定生產(chǎn)產(chǎn)品Ix1件，產(chǎn)品IIx2件。則四個部門的目標決策值和目標值分別為部門目標決策值f目標值f*優(yōu)先級別P營銷部門X2-x1/20P2材料部門5x1+10x260P1設備管理4x1+4x240-4=36P3財務部門6x1+8x248P43偏差變量

對每一個決策目標，引入正負偏差變量d+和d-，分別表示決策值與目標值的偏差，d+表示決策值超過目標值部分，d-表示決策值不足目標值部分。顯然，根據(jù)定義，有那么，例2的四個目標的決策值和目標值的偏差表達為4各個目標的欲望表達

任何一個部門在表達自己的意見時，總是用某種語氣表達目標決策值和目標值之間的某種比較欲望。歸納起來，不外乎下面三種：（1）要求決策值不超過目標值min{d+}

或min{f(d+)}（2）要求決策值不低于目標值min{d-}或min{f(d-)}（3）要求決策值恰好達到目標值min{d-+d+}或min{f(d-+d+)}根據(jù)上面的定義，例2的四個部門的欲望可以表達為材料部門：mind1+

營銷部門：mind2+設備部門：mind3+財務部門：mind4-

對于材料部門，基于語氣的強硬，也可以把材料部門的欲望改為d1+=0。這樣的話這個約束就由可以商量（稱為軟約束）轉化為沒有商量的余地（稱為硬約束），并不改變問題的性質。根據(jù)上面引入的概念和分析，例2的規(guī)劃模型為

在建立目標規(guī)劃模型時，盡可能利用各種決策技術，盡量減少主觀性和片面性。目標規(guī)劃的一般形式硬約束軟約束例2多目標供給問題

已知三個工廠生產(chǎn)的產(chǎn)品供應給四個用戶，各工廠生產(chǎn)量、用戶需求量及從各個工廠到用戶的單位產(chǎn)品的運輸費用如表4-2所示。由于總生產(chǎn)量小于總需求量，上級部門經(jīng)研究決定，制定了調配方案的8項指標，并規(guī)定了重要性的次序。表4-2用戶1234生產(chǎn)量工廠1工廠2工廠3需求量534200255100642450763250300200400第一目標：用戶4為重要部門，需求量必須全部滿足；第二目標：供應用戶1的產(chǎn)品中，工廠3的產(chǎn)品不少于100個單位；第三目標：每個用戶的滿足率不低于80%；第四目標：應盡量滿足個用戶的要求；第五目標：新方案的總運費不超過原運輸問題的總運費的10%；第六目標：因道路問題，工廠2到用戶4的路線盡量避免運輸；第七目標：用戶1和用戶3的滿足率應盡量保持平衡；第八目標：力求減少總運費；請列出相應的目標規(guī)劃模型，并用Lingo求解。解設從工廠i向用戶j調運產(chǎn)品量為xij,i=1,2,3;j=1,2,3,4;Cij表示從工廠i向用戶j調運的單位產(chǎn)品的費用；ai表示工廠i的產(chǎn)量；i=1,2,3;bj表示用戶j的需求量，j=1,2,3,4;

由于目標5中需要用到不考慮任何目標的調運方案下的最小費用，故需要先求解如下線性規(guī)劃模型s.t.上述模型的求解程序及結果為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));@for(yhu(j):@sum(gch(i):x(i,j))<=b(j));data:a=300,200,400;b=200,100,450,250;c=526735464523;enddata計算得到最小運費為2950元.建立目標規(guī)劃引入p1,…,p8表示各個目標的優(yōu)先順序；di+，di-表示各個決策目標與參考目標的正偏差和負偏差;i=1,2,3,…下面寫出各個約束硬約束（供應約束）系列軟約束（1）用戶4必須全部滿足（2）供應用戶1的產(chǎn)品中，工廠3的產(chǎn)品不少于100單位（3）每個用戶的滿足率不低于80%；四個用戶的80%需求量分別為160,80,360,200，即（4）應盡量滿足個用戶的要求（5）新運費盡量不超過不考慮各個目標費用的10%：（6）因道路限制，工廠2到用戶4的路線的運輸任務應盡量避免：（7）用戶1和用戶3的滿足率盡量平衡：（8）力求減少總費用：變量要求按照優(yōu)先級別寫出目標函數(shù)s.t.硬約束（供應約束）軟約束二、利用lingo計算目標規(guī)劃

多目標規(guī)劃實質是一個多個目標的線性規(guī)劃問題，仍可以用Lingo求解，下面以例1和例題2為計算例子。5*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=0;d22=0;d32=0;min=d42;Globaloptimalsolutionfoundatiteration:4Objectivevalue:0.000000VariableValueReducedCostX16.0000000.000000X23.0000000.000000D110.0000000.000000D120.0000000.000000D210.0000000.000000D220.0000000.000000D310.0000000.000000D320.0000000.000000D4112.000000.000000D420.0000001.000000sets:chandi/1..3/:a;xiaodi/1..4/:b;link(chandi,xiaodi):c,x;endsets@for(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(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=526735464523;enddatad11=0;d21=0;d31=0;d41=0;d51=0;d61=0;d71+d81+d91+d101=100;d112=115;d122=0;d132+d131=0.15;min=d142;VariableValueReducedCostD3230.000000.000000D4220.000000.000000D6250.000000.000000D7110.000000.000000D9190.000000.000000D112115.00000.000000D1320.15000000.000000D142410.00000.