1、多目的規(guī)劃方法Multi-objective Programming.2背景引見在地理學(xué)研討中，對于許多規(guī)劃問題，經(jīng)常需求思索多個目的，如經(jīng)濟(jì)效益目的，生態(tài)效益目的，社會效益目的，等等。為了滿足這類問題研討之需求，本章擬結(jié)合有關(guān)實例，對多目的規(guī)劃方法及其在地理學(xué)研討中的運用問題作一些簡單地引見。.多目的規(guī)劃及其求解技術(shù)簡介目的規(guī)劃方法 多目的規(guī)劃運用實例 大綱.1 多目的規(guī)劃及其非劣解多目的規(guī)劃及其非劣解多目的規(guī)劃求解技術(shù)簡介.5一任何多目的規(guī)劃問題，都由兩個根本部分組成：1兩個以上的目的函數(shù)；2假設(shè)干個約束條件。二對于多目的規(guī)劃問題，可以將其數(shù)學(xué)模 型普通地描寫為如下方式： 一、多目的規(guī)劃及

2、其非劣解.6一、多目的規(guī)劃及其非劣解1.21.1式中： 為決策變量向量。 .7一、多目的規(guī)劃及其非劣解 假設(shè)將1.1和1.2式進(jìn)一步縮寫， 即： 1.3 1.4 式中： 是k維函數(shù)向量，k是目的函數(shù)的個數(shù)； 是m維函數(shù)向量； 是m維常數(shù)向量；m是約束方程的個數(shù)。 .8一、多目的規(guī)劃及其非劣解 對于線性多目的規(guī)劃問題，1.3和1.4式可以進(jìn)一步用矩陣表示： 1.5 1.6式中： 為n維決策變量向量； 為kn矩陣，即目的函數(shù)系數(shù)矩陣； 為mn矩陣，即約束方程系數(shù)矩陣； 為m維的向量，約束向量。 .9對于上述多目的規(guī)劃問題，求解就意味著需求做出如下的復(fù)合選擇：每一個目的函數(shù)取什么值，原問題可以得到最

3、稱心的處理？每一個決策變量取什么值，原問題可以得到最稱心的處理 ？多目的規(guī)劃問題的求解不能只追求一個目的的最優(yōu)化最大或最小，而不顧其它目的。二、多目的規(guī)劃的非劣解 .10非劣解：可以用圖1.1闡明。二、多目的規(guī)劃的非劣解 圖1.1 多目的規(guī)劃的劣解與非劣解.11在圖1.1中，就方案和來說，的 目的值比大，但其目的值 比小，因此無法確定這兩個方案的優(yōu)與劣。在各個方案之間，顯然：比好，比好，比好，比好。而對于方案、之間那么無法確定優(yōu)劣，而且又沒有比它們更好的其他方案，所以它們就被稱之為多目的規(guī)劃問題的非劣解或有效解，其他方案都稱為劣解。一切非劣解構(gòu)成的集合稱為非劣解集。二、多目的規(guī)劃的非劣解 .1

4、2當(dāng)目的函數(shù)處于沖突形狀時，就不會存在使一切目的函數(shù)同時到達(dá)最大或最小值的最優(yōu)解，于是我們只能尋求非劣解又稱非支配解或帕累托解。二、多目的規(guī)劃的非劣解 .2 多目的規(guī)劃求解技術(shù)簡介為了求得多目的規(guī)劃問題的非劣解，經(jīng)常需求將多目的規(guī)劃問題轉(zhuǎn)化為單目的規(guī)劃問題去處置。實現(xiàn)這種轉(zhuǎn)化，有如下幾種建模方法。一、成效最優(yōu)化模型 二、罰款模型 三、約束模型 四、目的規(guī)劃模型 五、目的到達(dá)法.一、成效最優(yōu)化模型 建摸根據(jù)：規(guī)劃問題的各個目的函數(shù)可以經(jīng)過一定的方式進(jìn)展求和運算。這種方法將一系列的目的函數(shù)與成效函數(shù)建立相關(guān)關(guān)系，各目的之間經(jīng)過成效函數(shù)協(xié)調(diào)，使多目的規(guī)劃問題轉(zhuǎn)化為傳統(tǒng)的單目的規(guī)劃問題： 是與各目的函

5、數(shù)相關(guān)的成效函數(shù)的和函數(shù)。 2.1 2.2 .在用成效函數(shù)作為規(guī)劃目的時，需求確定一組權(quán)值 來反映原問題中各目的函數(shù)在總體目的中的權(quán)重，即：式中，諸 應(yīng)滿足：假設(shè)采用向量與矩陣 2.3 2.5 2.62.7 2.4 .二、罰款模型規(guī)劃決策者對每一個目的函數(shù)都能提出所期望的值或稱稱心值；經(jīng)過比較實踐值 與期望值 之間的偏向來選擇問題的解，其數(shù)學(xué)表達(dá)式如下：2.8 2.9 .或?qū)懗删仃嚪绞剑?式中， 是與第i個目的函數(shù)相關(guān)的權(quán)重； A是由 組成的mm對角矩陣。2.10 2.11 .三、約束模型 實際根據(jù) ：假設(shè)規(guī)劃問題的某一目的可以給出一個可供選擇的范圍，那么該目的就可以作為約束條件而被排除出目的

6、組，進(jìn)入約束條件組中。假設(shè)，除第一個目的外，其他目的都可以提出一個可供選擇的范圍，那么該多目的規(guī)劃問題就可以轉(zhuǎn)化為單目的規(guī)劃問題： .采用矩陣可記為： 2.17 2.16 2.15 2.14 2.13 2.12 .四、目的規(guī)劃模型 也需求預(yù)先確定各個目的的期望值 ，同時給每一個目的賦予一個優(yōu)先因子和權(quán)系數(shù)，假定有K個目的，L個優(yōu)先級 ，目的規(guī)劃模型的數(shù)學(xué)方式為：.式中： 和 分別表示與 相應(yīng)的、與 相比 的目的超越值和缺乏值，即正、負(fù)偏向變量； 表示第l個優(yōu)先級； 、 表示在同一優(yōu)先級 中，不同目的的正、負(fù)偏向變量的權(quán)系數(shù)。 2.18 2.19 2.20 .五、目的到達(dá)法 首先將多目的規(guī)劃模型

7、化為如下規(guī)范方式： 2.21 2.22 .在求解之前，先設(shè)計與目的函數(shù)相應(yīng)的一組目的值理想化的期望目的 ,每一個目的對應(yīng)的權(quán)重系數(shù)為 ，再設(shè) 為一松弛因子。那么，多目的規(guī)劃問題2.212.22就轉(zhuǎn)化為： 2.23 2.25 2.24 . 用目的到達(dá)法求解多目的規(guī)劃的計算過程，可以經(jīng)過調(diào)用Matlab軟件系統(tǒng)優(yōu)化工具箱中的fgoalattain函數(shù)實現(xiàn)。該函數(shù)的運用方法，詳見教材的配套光盤。 .3 目的規(guī)劃方法經(jīng)過上節(jié)的引見和討論，我們知道，目的規(guī)劃方法是處理多目的規(guī)劃問題的重要技術(shù)之一。這一方法是美國學(xué)者查恩斯A.Charnes和庫伯W.W.Cooper于1961年在線性規(guī)劃的根底上提出來的。

8、后來，查斯基萊恩U.Jaashelainen和李Sang.Lee等人，進(jìn)一步給出了求解目的規(guī)劃問題的普通性方法單純形方法。 .本節(jié)主要內(nèi)容：目的規(guī)劃模型 求解目的規(guī)劃的單純形方法.一、目的規(guī)劃模型一根本思想 ：給定假設(shè)干目的以及實現(xiàn)這些目的的優(yōu)先順序，在有限的資源條件下，使總的偏離目的值的偏向最小。.二目的規(guī)劃的有關(guān)概念例1：某一個企業(yè)利用某種原資料和現(xiàn)有設(shè)備可消費甲、乙兩種產(chǎn)品，其中，甲、乙兩種產(chǎn)品的單價分別為8元和10元；消費單位甲、乙兩種產(chǎn)品需求耗費的原資料分別為2個單位和1個單位，需求占用的設(shè)備分別為1臺時和2臺時；原資料擁有量為11個單位；可利用的設(shè)備總臺時為10臺時。試問：如何確定

9、其消費方案？. 假設(shè)斷策者所追求的獨一目的是使總產(chǎn)值到達(dá)最大，那么這個企業(yè)的消費方案可以由如下線性規(guī)劃模型給出：求 ， ，使 而且滿足： 式中：和為決策變量，為目的函數(shù)值。將上述問題化為規(guī)范后，用單純形方法求解可得最正確決策方案為 萬元3.1 3.2 3.3 3.4 . 但是，在實踐決策時，企業(yè)指點者必需思索市場等一系列其它條件，如：根據(jù)市場信息，甲種產(chǎn)品的需求量有下降的趨勢，因此甲種產(chǎn)品的產(chǎn)量不應(yīng)大于乙種產(chǎn)品的產(chǎn)量。超越方案供應(yīng)的原資料，需用高價采購，這就會使消費本錢添加。應(yīng)盡能夠地充分利用設(shè)備的有效臺時，但不希望加班。應(yīng)盡能夠到達(dá)并超越方案產(chǎn)值目的56元。 這樣，該企業(yè)消費方案確實定，便成

10、為一個多目的決策問題，這一問題可以運用目的規(guī)劃方法進(jìn)展求解。.為了建立目的規(guī)劃數(shù)學(xué)模型，下面引入有關(guān)概念。1.偏向變量在目的規(guī)劃模型中，除了決策變量外，還需求引入正、負(fù)偏向變量 、 。其中，正偏向變量表示決策值超越目的值的部分，負(fù)偏向變量表示決策值未到達(dá)目的值的部分。由于決策值不能夠既超越目的值同時又未到達(dá)目的值，故有 成立。 目的規(guī)劃模型的有關(guān)概念.2、絕對約束和目的約束 絕對約束，必需嚴(yán)厲滿足的等式約束和不等式約束，譬如，線性規(guī)劃問題的一切約束條件都是絕對約束，不能滿足這些約束條件的解稱為非可行解，所以它們是硬約束。 目的約束，目的規(guī)劃所特有的，可以將約束方程右端項看作是追求的目的值，在到

11、達(dá)此目的值時允許發(fā)生正的或負(fù)的偏向 ，可參與正負(fù)偏向變量，是軟約束。 線性規(guī)劃問題的目的函數(shù)，在給定目的值和參與正、負(fù)偏向變量后可以轉(zhuǎn)化為目的約束，也可以根據(jù)問題的需求將絕對約束轉(zhuǎn)化為目的約束。 目的規(guī)劃模型的有關(guān)概念.3.優(yōu)先因子優(yōu)先等級與權(quán)系數(shù) 一個規(guī)劃問題,經(jīng)常有假設(shè)干個目的，決策者對各個目的的思索,往往是有主次或輕重緩急的。凡要求第一位到達(dá)的目的賦予優(yōu)先因子 ，次位的目的賦予優(yōu)先因子 ，并規(guī)定 表示 比 有更大的優(yōu)先權(quán)。這就是說，首先保證 級目的的實現(xiàn)，這時可以不思索次級目的；而 級目的是在實現(xiàn) 級目的的根底上思索的；依此類推。假設(shè)要區(qū)別具有一樣優(yōu)先因子 的目的的差別，就可以分別賦予它

12、們不同的權(quán)系數(shù) 。這些優(yōu)先因子和權(quán)系數(shù)都由決策者按照詳細(xì)情況而定。 目的規(guī)劃模型的有關(guān)概念.4.目的函數(shù) 目的規(guī)劃的目的函數(shù)準(zhǔn)那么函數(shù)是按照各目的約束的正、負(fù)偏向變量和賦予相應(yīng)的優(yōu)先因子而構(gòu)造的。當(dāng)每一目確實定后，盡能夠減少與目的值的偏離。因此，目的規(guī)劃的目的函數(shù)只能是：根本方式有三種： a) 要求恰好到達(dá)目的值，就是正、負(fù)偏向變量都要盡能夠小,即 目的規(guī)劃模型的有關(guān)概念3.5 3.6 .b) 要求不超越目的值，即允許達(dá)不到目的值，就是正偏向變量要盡能夠小，即 c) 要求超越目的值，也就是超越量不限，但負(fù)偏向變量要盡能夠小，即在實踐問題中，可以根據(jù)決策者的要求，引入正、負(fù)偏向變量和目的約束，并

13、給不同目的賦予相應(yīng)的優(yōu)先因子和權(quán)系數(shù)，構(gòu)造目的函數(shù)，建立模型。 目的規(guī)劃模型的有關(guān)概念3.7 3.8 .例2：在例1中，假設(shè)斷策者在原資料供應(yīng)受嚴(yán)厲控制的根底上思索：首先是甲種產(chǎn)品的產(chǎn)量不超越乙種產(chǎn)品的產(chǎn)量；其次是充分利用設(shè)備的有限臺時，不加班；再次是產(chǎn)值不小于56元。并分別賦予這三個目的優(yōu)先因子 。試建立該問題的目的規(guī)劃模型。.解：根據(jù)題意，這一決策問題的目的規(guī)劃模型是4.假定有L個目的，K個優(yōu)先級(KL)，n個變量。在同一優(yōu)先級 中不同目的的正、負(fù)偏向變量的權(quán)系數(shù)分別為 、 ，那么多目的規(guī)劃問題可以表示為：三目的規(guī)劃模型的普通方式 3.153.1

14、938.在以上各式中， 、 分別為賦予 優(yōu)先因子的第 個目的的正、負(fù)偏向變量的權(quán)系數(shù)， 為第 個目的的預(yù)期值， 為決策變量， 、 分別為第 個目的的正、負(fù)偏向變量，3.15式為目的函數(shù)，3.16式為目的約束，3.17式為絕對約束，3.18式和3.19式為非負(fù)約束， 、 、 分別為目的約束和絕對約束中決策變量的系數(shù)及約束值。其中， ； ； 。 .二、求解目的規(guī)那么的單純形方法 目的規(guī)劃模型仍可以用單純形方法求解 ，在求解時作以下規(guī)定：由于目的函數(shù)都是求最小值，所以，最優(yōu)判別檢驗數(shù)為：由于非基變量的檢驗數(shù)中含有不同等級的優(yōu)先因子， 40.所以檢驗數(shù)的正、負(fù)首先決議于 的系數(shù)

15、 的正、負(fù)，假設(shè) ，那么檢驗數(shù)的正、負(fù)就決議于 的系數(shù) 的正、負(fù)，下面可依此類推。 據(jù)此，我們可以總結(jié)出求解目的規(guī)劃問題的單純形方法的計算步驟如下：建立初始單純形表，在表中將檢驗數(shù)行按優(yōu)先因子個數(shù)分別排成L行，置 。 .檢查該行中能否存在負(fù)數(shù)，且對應(yīng)的前L-1行的系數(shù)是零。假設(shè)有，取其中最小者對應(yīng)的變量為換入變量，轉(zhuǎn)。假設(shè)無負(fù)數(shù)，那么轉(zhuǎn)。按最小比值規(guī)那么 規(guī)那么確定換出變量，當(dāng)存在兩個和兩個以上一樣的最小比值時，選取具有較高優(yōu)先級別的變量為換出變量。按單純形法進(jìn)展基變換運算，建立新的計算表，前往。當(dāng)l=L時，計算終了，表中的解即為稱心解。否那么置l=l+1，前往 。.例3：試用單純形法求解例2

16、所描畫的目的規(guī)劃問題解：首先將這一問題化為如下規(guī)范方式： .取 為初始基變量，列出初始單純形表。表3.1. 取 ，檢查檢驗數(shù)的 行，因該行無負(fù)檢驗數(shù)，故轉(zhuǎn)。 由于 ，置 ，前往。 檢查發(fā)現(xiàn)檢驗數(shù) 行中有 ， ，由于有 ，所以 為換入變量，轉(zhuǎn)入。 按 規(guī)那么計算： ，所以 為換出變量，轉(zhuǎn)入。 進(jìn)展換基運算，得到表3.2。以此類推，直至得到最終單純形表為止，如表3.3所示。 .表3.2.表3.3由表6.2.3可知， ， ，為稱心解。檢查檢驗數(shù)行，發(fā)現(xiàn)非基變量的檢驗數(shù)為0，這闡明該問題存在多重解。.表2.4 在表3.3中，以非基變量 為換入變量， 為換出變量，經(jīng)迭代得到表6.3.4。 從表3.4可以

17、看出， ， 也是該問題的稱心解。 .一、土地利用問題 二、消費方案問題 三、投資問題 4 多目的規(guī)劃運用實例 49.我們運用線性規(guī)劃方法討論了表1.4所描畫的農(nóng)場作物種植方案的問題。但是，由于線性規(guī)劃只需單一的目的函數(shù)，所以當(dāng)時我們建立的作物種植方案模型屬于單目的規(guī)劃模型，給出的種植方案方案，要么使總產(chǎn)量最大，要么使總產(chǎn)值最大；兩個目的無法兼得。那么，終究怎樣制定作物種植方案，才干兼顧總產(chǎn)量和總產(chǎn)值雙重目的呢？下面我們用多目的規(guī)劃的思想方法處理這個問題。 一、土地利用問題50. 取 決策變量，它表示在第 j 等級的耕地上種植第i種作物的面積。假設(shè)追求總產(chǎn)量最大和總產(chǎn)值最大雙重目的，那么，目的函

18、數(shù)包括： 追求總產(chǎn)量最大 追求總產(chǎn)值最大 4.1 4.2 .根據(jù)題意，約束方程包括：耕地面積約束最低收獲量約束4.3 4.4 非負(fù)約束4.5 對上述多目的規(guī)劃問題，我們可以采用如下方法，求其非劣解。. 1.用線性加權(quán)方法 取 ，重新構(gòu)造目的函數(shù)： 這樣，就將多目的規(guī)劃轉(zhuǎn)化為單目的線性規(guī)劃。 . 用單純形方法對該問題求解，可以得到一個稱心解非劣解方案，結(jié)果見表6.4.1。 此方案是：III等耕地全部種植水稻，I等耕地全部種植玉米，II等耕地種植大豆19.1176公頃、種植玉米280.8824公頃。在此方案下，線性加權(quán)目的函數(shù)的最大取值為6445600。 .表4.1 線性加權(quán)目的下的非劣解方案單位

19、：hm2 .2.目的規(guī)劃方法 實踐上，除了線性加權(quán)求和法以外，我們還可以用目的規(guī)劃方法求解上述多目的規(guī)劃問題。假設(shè)我們對總產(chǎn)量 和總產(chǎn)值 ，分別提出一個期望目的值 kg， 元，并將兩個目的視為一樣的優(yōu)先級。 假設(shè) 、 分別表示對應(yīng)第一個目的期望值的正、負(fù)偏向變量， 、 分別表示對應(yīng)于第二個目的期望值的正、負(fù)偏向變量，而且將每一個目的的正、負(fù)偏向變量同等對待即可將它們的權(quán)系數(shù)都賦為1，那么，該目的規(guī)劃問題的目的函數(shù)為： .對應(yīng)的兩個目的約束為： 4.8 4.9即： . 除了目的約束以外，該模型的約束條件，還包括硬約束和非負(fù)約束的限制。其中，硬約束包括耕地面積約束4.3式和最低收獲量約束4.4式；

20、非負(fù)約束，不但包括決策變量的非負(fù)約束4.5式，還包括正、負(fù)偏向變量的非負(fù)約束： 解上述目的規(guī)劃問題，可以得到一個非劣解方案，詳見表6.4.2。 .表4.2 目的規(guī)劃的非劣解方案單位：hm2 在此非劣解方案下，兩個目的的正、負(fù)偏向變量分別為 ， ， ， 。. 二、消費方案問題 某企業(yè)擬消費A和B兩種產(chǎn)品，其消費投資費用分別為2100元/t和4800元/t。A、B兩種產(chǎn)品的利潤分別為3600元/t和6500元/t。A、B產(chǎn)品每月的最大消費才干分別為5t和8t；市場對這兩種產(chǎn)品總量的需求每月不少于9t。試問該企業(yè)應(yīng)該如何安排消費方案，才干既能滿足市場需求，又節(jié)約投資，而且使消費利潤到達(dá)最大? 60. 該問題是一個線性多目的規(guī)劃問題。假設(shè)方案決策變量用 和 表示，它