第六章多目標規劃方法第六章多目標規劃方法

同時考慮多個決策目標時，稱為多目標規劃問題。本章主要內容多目標規劃及其非劣解多目標規劃求解技術簡介多目標規劃方法多目標規劃應用實例在地理學研究中，對于許多規劃問題，常常需要考慮多個目標，如經濟效益目標、生態效益目標、社會效益目標等等。為了滿足這類問題研究之需要，本章擬結合有關實例，對多目標規劃方法及其在地理學研究中的應用問題作一些簡單地介紹。多目標最優化的思想萌芽于1776年經濟學中的效用理論。1896年，法國經濟學家V·Pareto首先在經濟理論的研究中提出了多目標最優化問題。1951年，美國數理經濟學家T·C·Koopans從生產和分配的活動分析中考慮了多目標決策問題，并首次提出了多目標最優化問題解的概念，將其命名為“Pareto解”(即有效解)。同年，H·W·Kuhn和A·W·Tucker從數學規劃論角度首次提出向量極值問題及有關概念。進入20世紀70年代，隨著第一次國際多目標決策研討會的召開及這方面專著的問世，多目標決策問題的研究工作迅速、蓬勃地開展起來，到目前為止，已取得若干有價值的研究成果。多目標規劃及其非劣解多目標規劃的非劣解第1節多目標規劃及其非劣解多目標規劃及其非劣解例1：【喜糖問題】設市場上有甲級糖及乙級糖，單價分別為4元/斤及2元/斤。今要籌辦一樁喜事。“籌備小組”計劃總花費不超過40元，糖的總斤數不少于10斤，甲級糖不少于5斤。問如何確定最佳的采購方案。我們先確定此問題應滿足的條件（即約束條件）。不難看出，當甲級糖數量為x1，乙級糖數量為x2時，有：多目標規劃及其非劣解在研究以什么為“最佳”的衡量標準時，“籌備小組”的成員們意見可能會發生分歧，其原因是他們會提出各種各樣的目標來。如果要求總花費最小，即要求：f1(x1,x2)=4x1+2x2→min如果要求糖的總數量最大，即要求：如果要求甲級糖的數量最大，即要求：易見，這是具有3個目標的規劃問題（由于約束及目標均為線性函數，故它為多目標線性規劃問題）。多目標規劃及其非劣解例2：【木梁設計問題】把橫截面為圓形的樹干加工成矩形橫截面的木梁。為使木梁滿足一定的規格和應力及強度條件，要求木梁的高度不超過H，橫截面的慣性矩不少于給定值W，且橫截面的高度要介于其寬度和4倍寬度之間。問應如何確定木梁尺寸，可使木梁的重量最輕，并且成本最低。設所設計的木梁橫截面的高為x1，寬為x2。為使具有一定長度的木梁重量最輕，應要求其橫截面面積x1x2為最小，即要求x1x2→min

x1

x2r多目標規劃及其非劣解由于矩形橫截面的木梁是由橫截面為圓形的樹干加工而成，故其成本與樹干橫截面面積的大小成正比。由此，為使木梁的成本最低還應要求盡可能的小，或即：根據問題的要求，應滿足下述約束條件：這是具有兩個目標的非線性規劃問題。多目標規劃及其非劣解例3：【投資決策問題】某投資開發公司擁有總資金A萬元，今有n(≥2)個項目可供選擇。設投資第i(i=1，2，……，n)個項目要用資金ai萬元，預計可得到收益bi萬元。問應如何使用總資金A萬元，才能得到最佳的經濟效益？xi=0或1多目標規劃及其非劣解所謂“最佳的經濟效益”，如果理解為“少花錢多辦事”，則變為兩個目標的問題，即投資最少，收益最大：這是具有兩個目標的0－1規劃問題。由以上實例可見，多目標最優化模型與單目標最優化模型的區別主要是目標多于一個。在這些目標中，有的是追求極大化，有的是追求極小化，而極大化與極小化是可以相互轉化的。因此，我們不難將多目標最優化模型統一成一般形式：決策變量：x1，……，xn目標函數：minf1(x1，……，xn)………………minfp(x1，……，xn)任何多目標規劃問題，都由兩個基本部分組成：(1)兩個以上的目標函數；(2)若干個約束條件。

對于多目標規劃問題，可以將其數學模型一般地描寫為如下形式

（）（）式中：，為決策變量向量。

如果將（）和（）式進一步縮寫，即（）

（）式中：是k維函數向量；

k是目標函數的個數；等是m維函數向量；是m維常數向量；

m是約束方程的個數。

對于線性多目標規劃問題，（6.1.3）和（6.1.4）式可以進一步用矩陣表示

（6.1.5）（6.1.6）式中：為n維決策變量向量；為k×n矩陣，即目標函數系數矩陣；為m×n矩陣，即約束方程系數矩陣；為m維的向量，約束向量。

二、多目標規劃的非劣解

對于上述多目標規劃問題，求解就意味著需要做出如下的復合選擇：每一個目標函數取什么值，原問題可以得到最滿意的解決？每一個決策變量取什么值，原問題可以得到最滿意的解決？多目標規劃問題的求解不能只追求一個目標的最優化（最大或最小），而不顧其他目標。在圖中，就方案①和②來說，①的目標值比②大，但其目標值比②小，因此無法確定這兩個方案的優與劣。在各個方案之間，顯然：③比②好，④比①好，⑦比③好，⑤比④好。而對于方案⑤、⑥、⑦之間則無法確定優劣，而且又沒有比它們更好的其他方案，所以它們就被稱之為多目標規劃問題的非劣解或有效解，其余方案都稱為劣解。所有非劣解構成的集合稱為非劣解集。多目標規劃的劣解與非劣解當目標函數處于沖突狀態時，就不會存在使所有目標函數同時達到最大或最小值的最優解，于是我們只能尋求非劣解（又稱非支配解或帕累托解）。

第2節多目標規劃求解技術

效用最優化模型罰款模型約束模型目標達到法目標規劃模型是與各目標函數相關的效用函數的和函數。

方法一效用最優化模型（線性加權法）

（1）

（2）

思想：規劃問題的各個目標函數可以通過一定的方式進行求和運算。這種方法將一系列的目標函數與效用函數建立相關關系，各目標之間通過效用函數協調，使多目標規劃問題轉化為傳統的單目標規劃問題：

在用效用函數作為規劃目標時，需要確定一組權值i來反映原問題中各目標函數在總體目標中的權重，即：式中，i

應滿足：向量形式：方法二罰款模型（理想點法）

思想:規劃決策者對每一個目標函數都能提出所期望的值（或稱滿意值）；通過比較實際值fi與期望值fi*之間的偏差來選擇問題的解，其數學表達式如下：或寫成矩陣形式：

式中，是與第i個目標函數相關的權重；

A是由(i=1,2,…,k)組成的m×m對角矩陣。理論依據：若規劃問題的某一目標可以給出一個可供選擇的范圍，則該目標就可以作為約束條件而被排除出目標組，進入約束條件組中。假如，除第一個目標外，其余目標都可以提出一個可供選擇的范圍，則該多目標規劃問題就可以轉化為單目標規劃問題：方法三約束模型（極大極小法）

方法四目標達到法

首先將多目標規劃模型化為如下標準形式：在求解之前，先設計與目標函數相應的一組目標值理想化的期望目標fi*(i=1,2,…,k),每一個目標對應的權重系數為i*(i=1,2,…,k)，再設為一松弛因子。那么，多目標規劃問題就轉化為：方法五目標規劃模型（目標規劃法）

需要預先確定各個目標的期望值fi*，同時給每一個目標賦予一個優先因子和權系數，假定有K個目標，L個優先級(L≤K)，目標規劃模型的數學形式為：

式中：

di+和di－分別表示與fi相應的、與fi*相比的目標超過值和不足值，即正、負偏差變量；pl表示第l個優先級；lk+、lk-表示在同一優先級pl中，不同目標的正、負偏差變量的權系數。用目標達到法求解多目標規劃的計算過程，可以通過調用Matlab軟件系統優化工具箱中的fgoalattain函數實現。第3節目標規劃方法

目標規劃模型

求解目標規劃的單純形方法通過上節的介紹和討論，我們知道，目標規劃方法是解決多目標規劃問題的重要技術之一。這一方法是美國學者查恩斯（A.Charnes）和庫伯（）于1961年在線性規劃的基礎上提出來的。后來，查斯基萊恩（U.Jaashelainen）和李（S.Lee）等人，進一步給出了求解目標規劃問題的一般性方法——單純形方法。一、目標規劃模型

給定若干目標以及實現這些目標的優先順序，在有限的資源條件下，使總的偏離目標值的偏差最小。（一）基本思想例1：某一個企業利用某種原材料和現有設備可生產甲、乙兩種產品，其中，甲、乙兩種產品的單價分別為8元和10元；生產單位甲、乙兩種產品需要消耗的原材料分別為2個單位和1個單位，需要占用的設備分別為1臺時和2臺時；原材料擁有量為11個單位；可利用的設備總臺時為10臺時。試問：如何確定其生產方案？（二）目標規劃的有關概念如果決策者所追求的唯一目標是使總產值達到最大，則這個企業的生產方案可以由如下線性規劃模型給出：求，，使

（）

而且滿足

式中：和為決策變量，z為目標函數值。將上述問題化為標準后，用單純形方法求解可得最佳決策方案為（萬元）。但是，在實際決策時，企業領導者必須考慮市場等一系列其他條件，如：①根據市場信息，甲種產品的需求量有下降的趨勢，因此甲種產品的產量不應大于乙種產品的產量。②超過計劃供應的原材料，需用高價采購，這就會使生產成本增加。③應盡可能地充分利用設備的有效臺時，但不希望加班。④應盡可能達到并超過計劃產值指標56萬元。這樣，該企業生產方案的確定，便成為一個多目標決策問題，這一問題可以運用目標規劃方法進行求解。為了建立目標規劃數學模型，下面引入有關概念。

偏差變量在目標規劃模型中，除了決策變量外，還需要引入正、負偏差變量、。其中，正偏差變量表示決策值超過目標值的部分，負偏差變量表示決策值未達到目標值的部分。因為決策值不可能既超過目標值同時又未達到目標值，故有成立。絕對約束和目標約束絕對約束，必須嚴格滿足的等式約束和不等式約束，譬如，線性規劃問題的所有約束條件都是絕對約束，不能滿足這些約束條件的解稱為非可行解，所以它們是硬約束。目標約束，目標規劃所特有的，可以將約束方程右端項看做是追求的目標值，在達到此目標值時允許發生正的或負的偏差，可加入正負偏差變量，是軟約束。線性規劃問題的目標函數，在給定目標值和加入正、負偏差變量后可以轉化為目標約束，也可以根據問題的需要將絕對約束轉化為目標約束。優先因子（優先等級）與權系數

一個規劃問題,常常有若干個目標，決策者對各個目標的考慮,往往是有主次或輕重緩急的。凡要求第一位達到的目標賦予優先因子，次位的目標賦予優先因子，…并規定表示比有更大的優先權。這就是說，首先保證級目標的實現，這時可以不考慮次級目標；而級目標是在實現級目標的基礎上考慮的；依此類推。，若要區別具有相同優先因子的目標的差別，就可以分別賦予它們不同的權系數。這些優先因子和權系數都由決策者按照具體情況而定。目標函數

目標規劃的目標函數（準則函數）是按照各目標約束的正、負偏差變量和賦予相應的優先因子而構造的。當每一目標確定后，盡可能縮小與目標值的偏離。因此，目標規劃的目標函數只能是基本形式有3種：）

①要求恰好達到目標值，就是正、負偏差變量都要盡可能小,即

（）

②要求不超過目標值，即允許達不到目標值，就是正偏差變量要盡可能小，即（）

③要求超過目標值，也就是超過量不限，但負偏差變量要盡可能小，即

（）

在實際問題中，可以根據決策者的要求，引入正、負偏差變量和目標約束，并給不同目標賦予相應的優先因子和權系數，構造目標函數，建立模型。

例2：在例1中，如果決策者在原材料供應受嚴格控制的基礎上考慮：首先是甲種產品的產量不超過乙種產品的產量；其次是充分利用設備的有限臺時，不加班；再次是產值不小于56萬元。并分別賦予這3個目標優先因子。試建立該問題的目標規劃模型。解：根據題意，這一決策問題的目標規劃模型是（）（）（）（）（）（）假定有L個目標，K個優先級(K≤L)，n個變量。在同一優先級中不同目標的正、負偏差變量的權系數分別為、，則多目標規劃問題可以表示為（三）目標規劃模型的一般形式（）（）（）（）（）目標函數目標約束絕對約束非負約束在以上各式中：、分別為賦予優先因子的第個目標的正、負偏差變量的權系數；為第個目標的預期值；為決策變量；、分別為第個目標的正、負偏差變量。（）式為目標函數;（）式為目標約束;（）式為絕對約束;（）式和（）式為非負約束;、、分別為目標約束和絕對約束中決策變量的系數及約束值。其中：

；；；。二、求解目標規則的單純形方法目標規劃模型仍可以用單純形方法求解，在求解時作以下規定：①因為目標函數都是求最小值，所以，最優判別檢驗數為②因為非基變量的檢驗數中含有不同等級的優先因子

所以檢驗數的正、負首先決定于的系數的正、負，若，則檢驗數的正、負就決定于的系數的正、負，下面可依此類推。據此，我們可以總結出求解目標規劃問題的單純形方法的計算步驟如下：①建立初始單純形表，在表中將檢驗數行按優先因子個數分別排成L行，置。②檢查該行中是否存在負數，且對應的前L-1行的系數是零。若有，取其中最小者對應的變量為換入變量，轉③。若無負數，則轉⑤。③按最小比值規則（規則）確定換出變量，當存在兩個和兩個以上相同的最小比值時，選取具有較高優先級別的變量為換出變量。④按單純形法進行基變換運算，建立新的計算表，返回②。⑤當l=L時，計算結束，表中的解即為滿意解。否則置l=l+1，返回②。例3：試用單純形法求解例2所描述的目標規劃問題解：首先將這一問題化為如下標準形式

(1)取,,,,為初始基變量，列出初始單純形表。表(2)取，檢查檢驗數的行，因該行無負檢驗數，故轉(5)。(5)因為，置，返回(2)。(2)檢查發現檢驗數行中有，，因為有，所以為換入變量，轉入(3)。

(3按規則計算：，所以為換出變量，轉入(4)。(4)進行換基運算，得到表。以此類推，直至得到最終單純形表為止，如表所示。

①取為初始基變量，列出初始單純形表。②取l=1，檢查檢驗數的p1行，因該行無負檢驗數，故轉⑤。⑤因為l=1<L=3，置l=l+1=2，返回②。②檢查發現檢驗數p2行中有-1，-2，因為有min{-1,-2}=-2，所以x2為換入變量，轉入③。

③按規則計算：，所以d2-為換出變量，轉入④。

④進行換基運算，得表3。以此類推，直至得到最終單純形表4為止。由表3可知，x1*=2，x2*=4，為滿意解。檢查檢驗數行，發現非基變量d3+的檢驗數為0，這表明該問題存在多重解。

在表3中，以非基變量d3+為換入變量，d1-為換出變量，經迭代得到表4。

從表4可以看出，x1*=10/3，x2*=10/3也是該問題的滿意解。多目標規劃的Matlab求解

用目標達到法求解多目標規劃的計算過程，可以通過調用Matlab軟件系統優化工具箱中的fgoalattain函數實現。該函數的使用方法，如下:X=FGOALATTAIN(FUN,X0,GOAL,WEIGHT)X=FGOALATTAIN(FUN,X0,GOAL,WEIGHT,A,B,Aeq,Beq,LB,UB)

[X,FVAL,ATTAINFACTOR,EXITFLAG,OUTPUT]=FGOALATTAIN(FUN,X0,...)在MATLAB中，多目標問題的標準形式為:其中：x、b、beq、lb、ub是向量；A、Aeq為矩陣；C(x)、Ceq(x)和F(x)是返回向量的函數；F(x)、C(x)、Ceq(x)可以是非線性函數；weight為權值系數向量，用于控制對應的目標函數與用戶定義的目標函數值的接近程度；goal為用戶設計的與目標函數相應的目標函數值向量；為一個松弛因子標量；F(x)為多目標規劃中的目標函數向量。多目標規劃的Matlab求解例：某工廠因生產需要，欲采購一種原料，市場上這種原材料有兩個等級，甲級單價2元/kg,乙級單價1元/kg，現要求總費用不超過200元，購得原料總量不少于100kg,其中甲級原料不少于50kg，問如何確定最好的采購方案。分析:列出方程

x1≥50;2x1+x2≤200;x1+x2≥100;x1,x2≥0化為標準形minf1=2x1+x2minf2=－

x1－

x2minf3=－

x1s.t

:

2x1+x2≤200

－

x1－

x2≤－

100

－

x1≤－

50

x1,x2≥0多目標規劃的Matlab求解matlab程序

fun='[2*x(1)+x(2),-x(1)-x(2),-x(1)]';a=[21;-1-1;-10];b=[200-100-20]';goal=[200,-100,-50];weight=goal;x0=[55,55];lb=[0,0]';[X,FVAL,ATTAINFACTOR,EXITFLAG,OUTPUT,LAMBDA]=fgoalattain(fun,x0,goal,weight,a,b,[],[],lb,[])

化為標準形minf1=2x1+x2minf2=－

x1－

x2minf3=－

x1s.t

:

2x1+x2≤200

－

x1－

x2≤－

100

－

x1≤－

50

x1,x2≥0多目標規劃的Matlab求解Optimizationterminated:Searchdirectionlessthan2*options.TolX

andmaximumconstraintviolationislessthanoptions.TolCon.

Activeinequalities(towithinoptions.TolCon=1e-006):

lower

upper

ineqlin

ineqnonlin

2

2

3x=

50.0000

50.0000fval=

150.0000-100.0000

-50.0000attainfactor=

-1.4476e-024exitflag=

4

多目標規劃的Matlab求解土地利用問題

生產計劃問題投資問題第4節多目標規劃應用實例

第5章第1節中，我們運用線性規劃方法討論了表所描述的農場作物種植計劃的問題。但是，由于線性規劃只有單一的目標函數，所以當時我們建立的作物種植計劃模型屬于單目標規劃模型，給出的種植計劃方案，要么使總產量最大，要么使總產值最大；兩個目標無法兼得。那么，究竟怎樣制定作物種植計劃，才能兼顧總產量和總產值雙重目標呢？下面我們用多目標規劃的思想方法解決這個問題。

一、土地利用問題取為決策變量，它表示在第j等級的耕地上種植第i種作物的面積。如果追求總產量最大和總產值最大雙重目標，那么，目標函數包括：①追求總產量最大（）

②追求總產值最大（）

根據題意，約束方程包括：耕地面積約束最低收獲量約束（）

（）

（）

非負約束

對上述多目標規劃問題，我們可以采用如下方法，求其非劣解。用線性加權方法

取，重新構造目標函數

這樣，就將多目標規劃轉化為單目標線性規劃。

用單純形方法對該問題求解，可以得到一個滿意解（非劣解）方案，結果見表。此方案是：III等耕地全部種植水稻，I等耕地全部種植玉米，II等耕地種植大豆19.1176hm2、種植玉米280.8824hm2。在此方案下，線性加權目標函數的最大取值為6445600。表6.4.1線性加權目標下的非劣解方案（單位：hm2）

目標規劃方法實際上，除了線性加權求和法以外，我們還可以用目標規劃方法求解上述多目標規劃問題。如果我們對總產量和總產值，分別提出一個期望目標值（kg）（元）并將兩個目標視為相同的優先級。

如果、分別表示對應第1個目標期望值的正、負偏差變量，、分別表示對應于第2個目標期望值的正、負偏差變量，而且將每一個目標的正、負偏差變量同等看待（即可將它們的權系數都賦為1），那么，該目標規劃問題的目標函數為

對應的兩個目標約束為（）

（）即

除了目標約束以外，該模型的約束條件，還包括硬約束和非負約束的限制。其中，硬約束包括耕地面積約束（）式和最低收獲量約束（）式；非負約束，不但包括決策變量的非負約束（）式，還包括正、負偏差變量的非負約束

解上述目標規劃問題，可以得到一個非劣解方案，詳見表。

表6.4.2目標規劃的非劣解方案（單位:hm2）

在此非劣解方案下，兩個目標的正、負差變量分為，，，。二、生產計劃問題某企業擬生產A和B兩種產品，其生產投資費用分別為2100元/t和4800元/t。A、B兩種產品的利潤分別為3600元/t和6500元/t。A、B產品每月的最大生產能力分別為5t和8t；市場對這兩種產品總量的需求每月不少于9t。試問該企業應該如何安排生產計劃，才能既能滿足市場需求，又節約投資，而且使生產利潤達到最大?

該問題是一個線性多目標規劃問題。如果計劃決策變量用和表示，它們分別代表A、B產品每月的生產量（單位：t）；表示生產A、B兩種產品的總投資費用（單位：元）；表示生產A、B兩種產品獲得的總利潤（單位：元）。那么，該多目標規劃問題就是：求和，使

而且滿足

對于上述多目標規劃問題，如果決策者提出的期望目標是：（1）每個月的總投資不超30000元；（2）每個月的總利潤達到或超過45000元；（3）兩個目標同等重要。那么，借助Matlab軟件系統中的優化計算工具進行求解，可以得到一個非劣解方案為

按照此方案進行生產，該企業每個月可以獲得利潤44000元，同時需要投資29700元。

某企業擬用1000萬元投資于A、B兩個項目的技術改造。設、分別表示分配給A、B項目的投資（萬元）。據估計，投資項目A、B的年收益分別為投資的60%和70%；但投資風險損失，與總投資和單項投資均有關系據市場調查顯示，A項目的投資前景好于B項目，因此希望A項目的投資額不小B項目。試問應該如何在A、B兩個項目之間分配投資，才能既使年利潤最大，又使風險損失為最小？三、投資問題該問題是一個非線性多目標規劃問題，將它用數學語言描述出來，就是：求、，使

而且滿足

對于上述多目標規劃問題，如果決策者提出的期望目標是：（1）每一年的總收益不小于600萬元；（2）希望投資風險損失不超過800萬元；（3）兩個目標同等重要。那么，借助Matlab軟件中的優化計算工具進行求解，可以得到一個非劣解方案為＝750.00萬元，＝250.00萬元matlab程序

fun='[-0.60*x(1)-0.70*x(2),0.001*x(1)^2+0.002*x(2)^2+0.001*x(1)*x(2)]';a=[