多目標規(guī)劃方法

多目標規(guī)劃方法Multi-objectiveProgramming2背景介紹在地理學研究中，對于許多規(guī)劃問題，常常需要考慮多個目標，如經(jīng)濟效益目標，生態(tài)效益目標，社會效益目標，等等。為了滿足這類問題研究之需要，本章擬結(jié)合有關(guān)實例，對多目標規(guī)劃方法及其在地理學研究中的應用問題作一些簡單地介紹。多目標規(guī)劃及其求解技術(shù)簡介目標規(guī)劃方法多目標規(guī)劃應用實例大綱1多目標規(guī)劃及其非劣解多目標規(guī)劃及其非劣解多目標規(guī)劃求解技術(shù)簡介5（一）任何多目標規(guī)劃問題，都由兩個基本部分組成：（1）兩個以上的目標函數(shù)；（2）若干個約束條件。（二）對于多目標規(guī)劃問題，可以將其數(shù)學模型一般地描寫為如下形式：一、多目標規(guī)劃及其非劣解6一、多目標規(guī)劃及其非劣解（1.2）（1.1）式中：為決策變量向量。7一、多目標規(guī)劃及其非劣解如果將（1.1）和（1.2）式進一步縮寫，即：（1.3）

（1.4）式中：是k維函數(shù)向量，k是目標函數(shù)的個數(shù)；是m維函數(shù)向量；是m維常數(shù)向量；m是約束方程的個數(shù)。8一、多目標規(guī)劃及其非劣解對于線性多目標規(guī)劃問題，（1.3）和（1.4）式可以進一步用矩陣表示：（1.5）（1.6）式中：為n維決策變量向量；為k×n矩陣，即目標函數(shù)系數(shù)矩陣；為m×n矩陣，即約束方程系數(shù)矩陣；為m維的向量，約束向量。9對于上述多目標規(guī)劃問題，求解就意味著需要做出如下的復合選擇：▲每一個目標函數(shù)取什么值，原問題可以得到最滿意的解決？▲每一個決策變量取什么值，原問題可以得到最滿意的解決？多目標規(guī)劃問題的求解不能只追求一個目標的最優(yōu)化（最大或最小），而不顧其它目標。二、多目標規(guī)劃的非劣解10非劣解：可以用圖1.1說明。二、多目標規(guī)劃的非劣解圖1.1多目標規(guī)劃的劣解與非劣解11在圖1.1中，就方方案①和和②來說說，①的的目目標值比比②大，，但其目目標值比比②小，，因此無無法確定定這兩個個方案的的優(yōu)與劣劣。在各各個方案案之間，，顯然：：③比②②好，④④比①好好，⑦比比③好，，⑤比④④好。而而對于方方案⑤、、⑥、⑦⑦之間則則無法確確定優(yōu)劣劣，而且且又沒有有比它們們更好的的其他方方案，所所以它們們就被稱稱之為多多目標規(guī)規(guī)劃問題題的非劣劣解或有有效解，，其余方方案都稱稱為劣解解。所有有非劣解解構(gòu)成的的集合稱稱為非劣劣解集。。二、多目目標規(guī)劃劃的非劣劣解12當目標函函數(shù)處于于沖突狀狀態(tài)時，，就不會會存在使使所有目目標函數(shù)數(shù)同時達達到最大大或最小小值的最最優(yōu)解，，于是我我們只能能尋求非非劣解（（又稱非非支配解解或帕累累托解））。二、多目標規(guī)規(guī)劃的非劣解解2多目標規(guī)劃求求解技術(shù)簡介介為了求得多目目標規(guī)劃問題題的非劣解，，常常需要將將多目標規(guī)劃劃問題轉(zhuǎn)化為為單目標規(guī)劃劃問題去處理理。實現(xiàn)這種種轉(zhuǎn)化，有如如下幾種建模模方法。一、效用最優(yōu)優(yōu)化模型二、罰款模型型三、約束模型型四、目標規(guī)劃劃模型五、目標達到到法一、效用最優(yōu)優(yōu)化模型建摸依據(jù)：規(guī)規(guī)劃問題的各各個目標函數(shù)數(shù)可以通過一一定的方式進進行求和運算算。這種方法法將一系列的的目標函數(shù)與與效用函數(shù)建建立相關(guān)關(guān)系系，各目標之之間通過效用用函數(shù)協(xié)調(diào)，，使多目標規(guī)規(guī)劃問題轉(zhuǎn)化化為傳統(tǒng)的單單目標規(guī)劃問問題：是與各目標函函數(shù)相關(guān)的效效用函數(shù)的和和函數(shù)。（2.1）（2.2）在用效用函數(shù)數(shù)作為規(guī)劃目目標時，需要要確定一組權(quán)權(quán)值來反反映原問題中中各目標函數(shù)數(shù)在總體目標標中的權(quán)重，，即：式中，諸應應滿足：：若采用向量與與矩陣（2.3）（2.5）（2.6）（2.7）（2.4）二、罰款模型型規(guī)劃決策者對對每一個目標標函數(shù)都能提提出所期望的的值（或稱滿滿意值）；通過比較實際際值與與期望值值之之間的偏差差來選擇問題題的解，其數(shù)數(shù)學表達式如如下：（2.8）（2.9）或?qū)懗删仃囆涡问剑菏街?，是是與第i個目標函數(shù)相相關(guān)的權(quán)重；；A是由組組成成的m×m對角矩陣。（2.10）（2.11）三、約束模型型理論依據(jù)：：若規(guī)劃問題題的某一目標標可以給出一一個可供選擇擇的范圍，則則該目標就可可以作為約束束條件而被排排除出目標組組，進入約束束條件組中。。假如，除第一一個目標外，，其余目標都都可以提出一一個可供選擇擇的范圍，則則該多目標規(guī)規(guī)劃問題就可可以轉(zhuǎn)化為單單目標規(guī)劃問問題：采用矩陣可記記為：（2.17）（2.16）（2.15）（2.14）（2.13）（2.12）四、目標規(guī)劃劃模型也需要預先確確定各個目標標的期望值，，同時給每一一個目標賦予予一個優(yōu)先因因子和權(quán)系數(shù)數(shù)，假定有K個目標，L個優(yōu)先級，，目標規(guī)劃劃模型的數(shù)學學形式為：式中：和和分分別表表示與相相應的的、與相相比的目標超過值值和不足值，，即正、負偏偏差變量；表示第l個優(yōu)先級；、表表示在同一優(yōu)優(yōu)先級中中，不同同目標的正、、負偏差變量量的權(quán)系數(shù)。。（2.18）（2.19）（2.20）五、目標達到到法首先將多目標標規(guī)劃模型化化為如下標準準形式：（2.21）（2.22）在求解之前，，先設(shè)計與目目標函數(shù)相應應的一組目標標值理想化的的期望目標,每一個目標對對應的權(quán)重系系數(shù)為，，再再設(shè)為為一松弛因因子。那么，，多目標規(guī)劃劃問題（2.21）～（2.22）就轉(zhuǎn)化為：：（2.23）（2.25）（2.24）用目標達到法求求解多目標規(guī)規(guī)劃的計算過過程，可以通通過調(diào)用Matlab軟件系統(tǒng)優(yōu)化化工具箱中的的fgoalattain函數(shù)實現(xiàn)。該該函數(shù)的使用用方法，詳見見教材的配套套光盤。3目標規(guī)劃方法法通過上節(jié)的介介紹和討論，，我們知道，，目標規(guī)劃方方法是解決多多目標規(guī)劃問問題的重要技技術(shù)之一。這一方法是美美國學者查恩恩斯（A.Charnes）和庫伯（）于1961年在線性規(guī)劃劃的基礎(chǔ)上提提出來的。后后來，查斯基基萊恩（U.Jaashelainen）和李（Sang.Lee）等人，進一一步給出了求求解目標規(guī)劃劃問題的一般般性方法——單純形方法。。本節(jié)主要內(nèi)容容：目標規(guī)劃模型型求解目標規(guī)劃劃的單純形方方法一、目標規(guī)劃劃模型（一）基本思思想：給定若干目標標以及實現(xiàn)這這些目標的優(yōu)優(yōu)先順序，在在有限的資源源條件下，使使總的偏離目目標值的偏差差最小。（二）目標規(guī)規(guī)劃的有關(guān)概概念例1：某一個企業(yè)業(yè)利用某種原原材料和現(xiàn)有有設(shè)備可生產(chǎn)產(chǎn)甲、乙兩種種產(chǎn)品，其中中，甲、乙兩兩種產(chǎn)品的單單價分別為8元和10元；生產(chǎn)單位位甲、乙兩種種產(chǎn)品需要消消耗的原材料料分別為2個單位和1個單位，需要要占用的設(shè)備備分別為1臺時和2臺時；原材料料擁有量為11個單位；可利利用的設(shè)備總總臺時為10臺時。試問：：如何確定其其生產(chǎn)方案？？如果決策者所所追求的唯一一目標是使總總產(chǎn)值達到最最大，則這個個企業(yè)的生產(chǎn)產(chǎn)方案可以由由如下線性規(guī)規(guī)劃模型給出出：求，，，使使而且滿足：式中：和為決決策變量，為為目標函數(shù)值值。將上述問問題化為標準準后，用單純純形方法求解解可得最佳決決策方案為（（萬元元）（3.1）（3.2）（3.3）（3.4）但是，在實際際決策時，企企業(yè)領(lǐng)導者必必須考慮市場場等一系列其其它條件，如如：①根據(jù)市場信信息，甲種產(chǎn)產(chǎn)品的需求量量有下降的趨趨勢，因此甲甲種產(chǎn)品的產(chǎn)產(chǎn)量不應大于于乙種產(chǎn)品的的產(chǎn)量。②超過計劃供供應的原材料料，需用高價價采購，這就就會使生產(chǎn)成成本增加。③應盡可能地地充分利用設(shè)設(shè)備的有效臺臺時，但不希希望加班。④應盡可能達達到并超過計計劃產(chǎn)值指標標56元。這樣，該企業(yè)業(yè)生產(chǎn)方案的的確定，便成成為一個多目目標決策問題題，這一問題題可以運用目目標規(guī)劃方法法進行求解。。為了建立目標標規(guī)劃數(shù)學模模型，下面引引入有關(guān)概念念。1.偏差變量在目標規(guī)劃模模型中，除了了決策變量外外，還需要引引入正、負偏偏差變量、、。其其中，正偏差差變量表示決決策值超過目目標值的部分分，負偏差變變量表示決策策值未達到目目標值的部分分。因為決策值不不可能既超過過目標值同時時又未達到目目標值，故有有成成立。目標規(guī)劃模型型的有關(guān)概念念2、絕對約束和和目標約束絕對約束，必必須嚴格滿足足的等式約束束和不等式約約束，譬如，，線性規(guī)劃問問題的所有約約束條件都是是絕對約束，，不能滿足這這些約束條件件的解稱為非非可行解，所所以它們是硬硬約束。目標約束，目目標規(guī)劃所特特有的，可以以將約束方程程右端項看作作是追求的目目標值，在達達到此目標值值時允許發(fā)生生正的或負的的偏差，可可加入正負偏偏差變量，是是軟約束。線性規(guī)劃問題題的目標函數(shù)數(shù)，在給定目目標值和加入入正、負偏差差變量后可以以轉(zhuǎn)化為目標標約束，也可可以根據(jù)問題題的需要將絕絕對約束轉(zhuǎn)化化為目標約束束。目標規(guī)劃模型型的有關(guān)概念念3.優(yōu)先先因因子子（（優(yōu)優(yōu)先先等等級級））與與權(quán)權(quán)系系數(shù)數(shù)一個個規(guī)規(guī)劃劃問問題題,常常常有有若若干干個個目目標標，，決決策策者者對對各各個個目目標標的的考考慮慮,往往往是是有有主主次次或或輕輕重重緩緩急急的的。。凡凡要要求求第第一一位位達達到到的的目目標標賦賦予予優(yōu)優(yōu)先先因因子子，，次次位位的的目目標標賦賦予予優(yōu)優(yōu)先先因因子子，，………，并并規(guī)規(guī)定定表表示示比比有有更更大大的的優(yōu)優(yōu)先先權(quán)權(quán)。。這這就就是是說說，，首首先先保保證證級級目目標標的的實實現(xiàn)現(xiàn)，，這這時時可可以以不不考考慮慮次次級級目目標標；；而而級級目目標標是是在在實實現(xiàn)現(xiàn)級級目目標標的的基基礎(chǔ)礎(chǔ)上上考考慮慮的的；；依依此此類類推推。。若若要要區(qū)區(qū)別別具具有有相相同同優(yōu)優(yōu)先先因因子子的的目目標標的的差差別別，，就就可可以以分分別別賦賦予予它它們們不不同同的的權(quán)權(quán)系系數(shù)數(shù)。。這這些些優(yōu)優(yōu)先先因因子子和和權(quán)權(quán)系系數(shù)數(shù)都都由由決決策策者者按按照照具具體體情情況況而而定定。。目標標規(guī)規(guī)劃劃模模型型的的有有關(guān)關(guān)概概念念4.目標標函函數(shù)數(shù)目標標規(guī)規(guī)劃劃的的目目標標函函數(shù)數(shù)（（準準則則函函數(shù)數(shù)））是是按按照照各各目目標標約約束束的的正正、、負負偏偏差差變變量量和和賦賦予予相相應應的的優(yōu)優(yōu)先先因因子子而而構(gòu)構(gòu)造造的的。。當當每每一一目目標標確確定定后后，，盡盡可可能能縮縮小小與與目目標標值值的的偏偏離離。。因因此此，，目目標標規(guī)規(guī)劃劃的的目目標標函函數(shù)數(shù)只只能能是是：：基本本形形式式有有三三種種：：a)要求求恰恰好好達達到到目目標標值值，，就就是是正正、、負負偏偏差差變變量量都都要要盡盡可可能能小小,即目標標規(guī)規(guī)劃劃模模型型的的有有關(guān)關(guān)概概念念（3.5）（3.6）b)要求求不不超超過過目目標標值值，，即即允允許許達達不不到到目目標標值值，，就就是是正正偏偏差差變變量量要要盡盡可可能能小小，，即即c)要求求超超過過目目標標值值，，也也就就是是超超過過量量不不限限，，但但負負偏偏差差變變量量要要盡盡可可能能小小，，即即在實實際際問問題題中中，，可可以以根根據(jù)據(jù)決決策策者者的的要要求求，，引引入入正正、、負負偏偏差差變變量量和和目目標標約約束束，，并并給給不不同同目目標標賦賦予予相相應應的的優(yōu)優(yōu)先先因因子子和和權(quán)權(quán)系系數(shù)數(shù)，，構(gòu)構(gòu)造造目目標標函函數(shù)數(shù)，，建建立立模模型型。。目標規(guī)劃劃模型的的有關(guān)概概念（3.7）（3.8）例2：在例1中，如果果決策者者在原材材料供應應受嚴格格控制的的基礎(chǔ)上上考慮：：首先是是甲種產(chǎn)產(chǎn)品的產(chǎn)產(chǎn)量不超超過乙種種產(chǎn)品的的產(chǎn)量；；其次是是充分利利用設(shè)備備的有限限臺時，，不加班班；再次次是產(chǎn)值值不小于于56元。并分別別賦予這三三個目標優(yōu)優(yōu)先因子。。試建建立該問題題的目標規(guī)規(guī)劃模型。。解：根據(jù)題意意，這一決決策問題的的目標規(guī)劃劃模型是（3.9）（3.10）（3.11）（3.12）（3.13）（3.14）假定有L個目標，K個優(yōu)先級(K≤L)，n個變量。在在同一優(yōu)先先級中中不同目標標的正、負負偏差變量量的權(quán)系數(shù)數(shù)分別為、、，，則多多目標規(guī)劃劃問題可以以表示為：：（三）目標標規(guī)劃模型型的一般形形式（3.15）（3.16）（3.17）（3.18）（3.19）在以上各式式中，、分別別為賦予優(yōu)優(yōu)先因因子的第個個目標標的正、負負偏差變量量的權(quán)系數(shù)數(shù)，為第個個目標的預預期值，為決策變量量，、分別別為第個個目標的的正、負偏偏差變量，，（3.15）式為目標標函數(shù)，（（3.16）式為目標標約束，（（3.17）式為絕對對約束，（（3.18）式和（3.19）式為非負負約束，、、、、分分別為目標標約束和絕絕對約束中中決策變量量的系數(shù)及及約束值。。其中，；；；。。二、求解目目標規(guī)則的的單純形方方法目標規(guī)劃模型型仍可以用單單純形方法求求解，在求解時作作以下規(guī)定：：①因為目標函數(shù)數(shù)都是求最小小值，所以，，最優(yōu)判別檢檢驗數(shù)為：②因為非基變量量的檢驗數(shù)中中含有不同等等級的優(yōu)先因因子，所以檢驗數(shù)的的正、負首先先決定于的的系數(shù)的的正、負負，若，，則則檢驗數(shù)的正正、負就決定定于的系數(shù)的的正、負，，下面可依此此類推。據(jù)此，我們可可以總結(jié)出求求解目標規(guī)劃劃問題的單純純形方法的計計算步驟如下下：①建立初始單純純形表，在表表中將檢驗數(shù)數(shù)行按優(yōu)先因因子個數(shù)分別別排成L行，置。。②檢查該行中是是否存在負數(shù)數(shù)，且對應的的前L-1行的系數(shù)是零零。若有，取取其中最小者者對應的變量量為換入變量量，轉(zhuǎn)③。若若無負數(shù)，則則轉(zhuǎn)⑤。③按最小比值規(guī)規(guī)則（規(guī)規(guī)則）確定換換出變量，當當存在兩個和和兩個以上相相同的最小比比值時，選取取具有較高優(yōu)優(yōu)先級別的變變量為換出變變量。④按單純形法進進行基變換運運算，建立新新的計算表，，返回②。⑤當l=L時，計算結(jié)束束，表中的解解即為滿意解解。否則置l=l+1，返回②。。例3：試用單純形形法求解例2所描述的目標標規(guī)劃問題解：首先將這一問問題化為如下下標準形式：：①取為為初始始基變量，列列出初始單純純形表。表3.1②取，，檢查檢驗數(shù)數(shù)的行，，因該行無負負檢驗數(shù)，故故轉(zhuǎn)⑤。⑤因為，，置，，返回回②。②檢查發(fā)現(xiàn)現(xiàn)檢驗數(shù)行行中有，，，因因為有，所以為為換入變量，，轉(zhuǎn)入③。③按規(guī)則計計算：，，所所以為為換換出變量，轉(zhuǎn)轉(zhuǎn)入④。④進行換基基運算，得到到表3.2。以此類推，，直至得到最最終單純形表表為止，如表表3.3所示。表3.2表3.3由表可知，，，，，為為滿意解。檢檢查檢驗數(shù)行行，發(fā)現(xiàn)非基基變量的檢驗驗數(shù)為0，這表明該問問題存在多重重解。表2.4在表3.3中，以非基變變量為換換入變量，為換出變量，，經(jīng)迭代得到到表。從表3.4可以看出，，，也也是該該問題的滿意意解。一、土地利用用問題二、生產(chǎn)計劃劃問題三、投資問題題4多目標規(guī)劃應應用實例我們運用線性性規(guī)劃方法討討論了表1.4所描述的農(nóng)場作物種植植計劃的問題題。但是，由由于線性規(guī)劃劃只有單一的的目標函數(shù)，，所以當時我我們建立的作作物種植計劃劃模型屬于單單目標規(guī)劃模模型，給出的的種植計劃方案案，要么使總總產(chǎn)量最大，，要么使總產(chǎn)產(chǎn)值最大；兩兩個目標無法法兼得。那么么，究竟怎樣樣制定作物種種植計劃，才才能兼顧總產(chǎn)產(chǎn)量和總產(chǎn)值值雙重目標呢呢？下面我們們用多目標規(guī)規(guī)劃的思想方方法解決這個個問題。一、土地利用用問題取決策策變量，它表表示在第j等級的耕地上上種植第i種作物的面積積。如果追求求總產(chǎn)量最大大和總產(chǎn)值最最大雙重目標標，那么，目目標函數(shù)包括括：①追求總產(chǎn)量量最大②追求總產(chǎn)值值最大（4.1）（4.2）根據(jù)題意，約約束方程包括括：耕地面積約束束最低收獲量約約束（4.3）（4.4）非負約束（4.5）對上述多目標標規(guī)劃問題，，我們可以采采用如下方法法，求其非劣劣解。1.用線性加權(quán)方方法取，，重新構(gòu)造目目標函數(shù)：這樣，就將多多目標規(guī)劃轉(zhuǎn)轉(zhuǎn)化為單目標標線性規(guī)劃。。用單單純純形形方方法法對對該該問問題題求求解解，，可可以以得得到到一一個個滿滿意意解解（（非非劣劣解解））方方案案，，結(jié)結(jié)果果見見表表。此方方案案是是：：III等耕耕地地全全部部種種植植水水稻稻，，I等耕地地全部部種植植玉米米，II等耕地地種植植大豆豆19.1176公頃、、種植植玉米米280.8824公頃。。在此此方案案下，，線性性加權(quán)權(quán)目標標函數(shù)數(shù)的最最大取取值為為6445600。表4.1線性加加權(quán)目目標下下的非非劣解解方案案（單位位：hm2）2.目標規(guī)規(guī)劃方方法實際上上，除除了線線性加加權(quán)求求和法法以外外，我我們還還可以以用目目標規(guī)規(guī)劃方方法求求解上上述多多目標標規(guī)劃劃問題題。如如果我我們對對總產(chǎn)產(chǎn)量和和總總產(chǎn)值值，，分別別提出出一個個期望望目標標值（（kg），（（元）），并并將兩兩個目目標視視為相相同的的優(yōu)先先級。。如果、、分分別表示對對應第一個個目標期望望值的正、、負偏差變變量，、、分分別表示示對應于第第二個目標標期望值的的正、負偏偏差變量，，而且將每每一個目標標的正、負負偏差變量量同等看待待（即可將將它們的權(quán)權(quán)系數(shù)都賦賦為1），那么，，該目標規(guī)規(guī)劃問題的的目標函數(shù)數(shù)為：對應的兩個個目標約束束為：（4.8）（4.9）即：除了目標約約束以外，，該模型的的約束條件件，還包括括硬約束和和非負約束束的限制。。其中，硬硬約束包括括耕地面積積約束（4.3）式和最低低收獲量約約束（4.4）式；非負負約束，不不但包括決決策變量的的非負約束束（4.5）式，還包包括正、負負偏差變量量的非負約約束：解上述目標標規(guī)劃問題題，可以得得到一個非非劣解方案案，詳見表表。表4.2目標規(guī)劃的的非劣解方方案（單位：hm2）在此非劣解解方案下，，兩個目標標的正、負負偏差變量量分別為，，，，，，。。二、生產(chǎn)計計劃問題某企業(yè)擬生生產(chǎn)A和B兩種產(chǎn)品，，其生產(chǎn)投投資費用分分別為2100元/t和4800元/t。A、B兩種產(chǎn)品的的利潤分別別為3600元/t和6500元/t。A、B產(chǎn)品每月的的最大生產(chǎn)產(chǎn)能力分別別為5t和8t；市場對這這兩種產(chǎn)品品總量的需需求每月不不少于9t。試問該企企業(yè)應該如如何安排生生產(chǎn)計劃，，才能既能能滿足市場場需求，又又節(jié)約投資資，而且使使生產(chǎn)利潤潤達到最大大?該問題是一一個線性多多目標規(guī)