【正文】 第九講 多目標(biāo)規(guī)劃方法 l多目標(biāo)規(guī)劃解的討論 —— 非劣解 l多目標(biāo)規(guī)劃及其求解技術(shù)簡介效用最優(yōu)化模型 罰款模型約束模型 目標(biāo)規(guī)劃模型目標(biāo)達(dá)到法l目標(biāo)規(guī)劃方法l目標(biāo)規(guī)劃模型l目標(biāo)規(guī)劃的圖解法 l求解目標(biāo)規(guī)劃的單純形方法l多目標(biāo)規(guī)劃應(yīng)用實(shí)例 1多目標(biāo)規(guī)劃是數(shù)學(xué)規(guī)劃的一個分支。研究 多于一個的目標(biāo)函數(shù) 在 給定區(qū)域 上的最優(yōu)化。又稱多目標(biāo)最優(yōu)化。通常記為 MOP(multiobjectiveprogramming)。在很多實(shí)際問題中，例如經(jīng)濟(jì)、管理、軍事、科學(xué)和工程設(shè)計(jì)等領(lǐng)域，衡量一個方案的好壞往往難以用一個指標(biāo)來判斷，而需要用多個目標(biāo)來比較，而這些目標(biāo)有時(shí)不甚協(xié)調(diào)，甚至是矛盾的。因此有許多學(xué)者致力于這方面的研究。1896年法國 經(jīng)濟(jì)學(xué)家 V.帕雷托最早研究 不可比較目標(biāo)的優(yōu)化問題，之后， 諾伊曼、 . 庫恩、 . 塔克、 數(shù)學(xué)家做了深入的探討 ，但是 尚未有一個完全令人滿意的定義 。 2求解多目標(biāo)規(guī)劃的方法大體上有以下幾種：一種是 化多為少的方法 ， 即把多目標(biāo)化為比較容易求解的單目標(biāo)或雙目標(biāo)，如主要目標(biāo)法、線性加權(quán)法、理想點(diǎn)法等；另一種叫 分層序列法 ，即把目標(biāo)按其重要性給出一個序列，每次都在前一目標(biāo)最優(yōu)解集內(nèi)求下一個目標(biāo)最優(yōu)解，直到求出共同的最優(yōu)解。對多目標(biāo)的線性規(guī)劃除以上方法外還可以適當(dāng) 修正單純形法 來求解；還有一種稱為 層次分析法 ，是由美國運(yùn)籌學(xué)家沙旦于 70年代提出的，這是一種定性與定量相結(jié)合的多目標(biāo)決策與分析方法，對于目標(biāo)結(jié)構(gòu)復(fù)雜且缺乏必要的數(shù)據(jù)的情況更為實(shí)用。 3 多目標(biāo)規(guī)劃模型（一）任何多目標(biāo)規(guī)劃問題，都由兩個基本部分組成： （ 1）兩個以上的目標(biāo)函數(shù)； （ 2）若干個約束條件。 （二）對于多目標(biāo)規(guī)劃問題，可以將其數(shù)學(xué)模型一般地描寫為如下形式： 一 多目標(biāo)規(guī)劃及其非劣解 式中： 為 決策變量向量 。 4縮寫形式：有 n個決策變量， k個目標(biāo)函數(shù)， m個約束方程，則：Z=F(X)是 k維函數(shù)向量，?(X)是 m維函數(shù)向量；G是 m維常數(shù)向量；（ 1）（ 2） 5 對于 線性多目標(biāo)規(guī)劃 問題，可以進(jìn)一步用矩陣表示：式中： X 為 n 維決策變量向量； C 為 k n 矩陣，即目標(biāo)函數(shù)系數(shù)矩陣； B 為 m n 矩陣，即約束方程系數(shù)矩陣； b 為 m 維的向量，即約束向量。 6多目標(biāo)規(guī)劃的非劣解 多目標(biāo)規(guī)劃問題的求解不能只追求一個目標(biāo)的最優(yōu)化（最大或最小），而不顧其它目標(biāo)。對于上述多目標(biāo)規(guī)劃問題，求解就意味著需要做出如下的復(fù)合選擇：▲ 每一個目標(biāo)函數(shù)取什么值，原問題可以得到 最滿意的解決？▲ 每一個決策變量取什么值，原問題可以得到 最滿意的解決 ？7在圖 1中， max(f1,f2).就方案 ① 和 ② 來說， ① 的 f2目標(biāo)值比 ② 大，但其目標(biāo)值 f1 比 ② 小，因此無法確定這兩個方案的優(yōu)與劣。在各個方案之間，顯然： ④ 比 ① 好， ⑤ 比④ 好 , ⑥ 比 ② 好 , ⑦ 比③ 好 …… 。 非劣解 可以用圖 1說明。圖 1 多目標(biāo)規(guī)劃的劣解與非劣解8而對于方案 ⑤ 、 ⑥、 ⑦ 之間則無法確定優(yōu)劣，而且又沒有比它們更好的其他方案，所以它們就被稱為多目標(biāo)規(guī)劃問題的 非劣解 或 有效解 ，其余方案都稱為 劣解 。所有非劣解構(gòu)成的集合稱為 非劣解集 。 當(dāng)目標(biāo)函數(shù)處于沖突狀態(tài)時(shí)，就不會存在使所有目標(biāo)函數(shù)同時(shí)達(dá)到最大或最小值的最優(yōu)解，于是我們只能尋求非劣解（又稱 非支配解或帕累托解 ）。 9252。 效用最優(yōu)化模型252。 罰款模型252。 約束模型252。 目標(biāo)達(dá)到法252。 目標(biāo)規(guī)劃模型二 多目標(biāo)規(guī)劃求解技術(shù)簡介 為了求得多目標(biāo)規(guī)劃問題的非劣解，常常需要將多目標(biāo)規(guī)劃問題轉(zhuǎn)化為單目標(biāo)規(guī)劃問題 去處理。實(shí)現(xiàn)這種轉(zhuǎn)化，有如下幾種建模方法。10?是與各目標(biāo)函數(shù)相關(guān)的 效用函數(shù)的 和函數(shù) 。 方法一 效 用最優(yōu)化模型 （ 線性加權(quán)法 ） （ 1） （ 2） 思想 ：規(guī)劃問題的各個目標(biāo)函數(shù)可以通過 一定 的 方式進(jìn)行 求和 運(yùn)算。這種方法將一系列的 目標(biāo)函數(shù) 與 效用函數(shù) 建立相關(guān)關(guān)系，各目標(biāo)之間通過效用函數(shù)協(xié)調(diào)，使多目標(biāo)規(guī)劃問題轉(zhuǎn)化為傳統(tǒng)的單目標(biāo)規(guī)劃問題： 11在 用效用函數(shù)作為規(guī)劃目標(biāo) 時(shí)，需要確定一組 權(quán)值 ?i 來反映原問題中各目標(biāo)函數(shù)在總體目標(biāo)中的權(quán)重，即：式中， ?i 應(yīng)滿足：向量形式：12方法二 罰款模型 （平方加權(quán)法） 思想 :規(guī)劃決策者對每一個目標(biāo)函數(shù)都能提出所 期望的值（或稱 滿意值 ）；通過比較實(shí)際值 fi與期望值 fi*之間的偏差來選擇問題的解，其數(shù)學(xué)表達(dá)式如下：或?qū)懗删仃囆问剑? 式中， 是與第 i個目標(biāo)函數(shù)相關(guān)的 權(quán)重 ；A是由 (i=1,2,…, k)組成的 mm對角矩陣。13理論依據(jù) ：若規(guī)劃問題的 某一目標(biāo) 可以給出一個可供選擇的范圍，則該目標(biāo)就可以 作為約束條件 而被排除出目標(biāo)組，進(jìn)入約束條件組中。假如，除第一個目標(biāo)外，其余目標(biāo)都可以提出一個可供選擇的范圍，則該多目標(biāo)規(guī)劃問題就可以轉(zhuǎn)化為單目標(biāo)規(guī)劃問題： 方法三 約束模型 （ 極大極小法 ） 14方法四 目標(biāo)達(dá)到法 首先將多目標(biāo)規(guī)劃模型化為如下標(biāo)準(zhǔn)形式： 15在求解之前，先設(shè)計(jì)與目標(biāo)函數(shù)相應(yīng)的一組目標(biāo)值理想化的期望目標(biāo) fi*(i=1,2,…, k),每一個目標(biāo)對應(yīng)的權(quán)重系數(shù)為 ?i*(i=1,2,…, k)，再設(shè) ?為一松弛因子。那么，多目標(biāo)規(guī)劃問題就轉(zhuǎn)化為： 16方法五 目標(biāo)規(guī)劃模型（目標(biāo)規(guī)劃法） 需要預(yù)先確定各個目標(biāo)的期望值 fi*，同時(shí)給每一個目標(biāo)賦予一個 優(yōu)先因子 和 權(quán)系數(shù) ，假定有 K個目標(biāo)， L個優(yōu)先級 (L≤K)，目標(biāo)規(guī)劃模型的數(shù)學(xué)形式為： 17式中：di+和 di－ 分別表示與 fi相應(yīng)的、與 fi*相比的目標(biāo)超過值和不足值，即正、負(fù)偏差變量； pl表示第 l個優(yōu)先級； ?lk+、 ?lk表示在同一優(yōu)先級 pl 中，不同目標(biāo)的正、負(fù)偏差變量的權(quán)系數(shù) 。 Kl表示處于第 l級的目標(biāo)函數(shù)個數(shù) .18三 目標(biāo)規(guī)劃方法通過前面的介紹和討論，我們知道，目標(biāo)規(guī)劃方法是解決多目標(biāo)規(guī)劃問題的重要技術(shù)之一。這一方法是美國學(xué)者查恩斯（ ）和庫伯（ ）于 1961年在線性規(guī)劃的基礎(chǔ)上提出來的。后來，查斯基萊恩（ ）和李（）等人，進(jìn)一步給出了求解目標(biāo)規(guī)劃問題的一般性方法 —— 單純形方法。 167。目標(biāo)規(guī)劃模型167。目標(biāo)規(guī)劃的圖解法167。求解目標(biāo)規(guī)劃的單純形方法19167。 目標(biāo)規(guī)劃模型 給定若干目標(biāo)以及實(shí)現(xiàn)這些目標(biāo)的優(yōu)先順序，在有限的資源條件下，使總的偏離目標(biāo)值的偏差最小。 ：例 1：某一個企業(yè)利用某種原材料和現(xiàn)有設(shè)備可生產(chǎn)甲、乙兩種產(chǎn)品，其中，甲、乙兩種產(chǎn)品的單價(jià)分別為 8萬元和 10萬元；生產(chǎn)單位甲、乙兩種產(chǎn)品需要消耗的原材料分別為 2個單位和 1個單位，需要占用的設(shè)備分別為 1單位臺時(shí)和 2單位臺時(shí)；原材料擁有量為 11個單位；可利用的設(shè)備總臺時(shí)為 10單位臺時(shí)。試問：如何確定其生產(chǎn)方案使得企業(yè)獲利最大？20由于決策者所追求的唯一目標(biāo)是使總產(chǎn)值達(dá)到最大，這個企業(yè)的生產(chǎn)方案可以由如下線性規(guī)劃模型給出：求 x1， x2，使 將上述問題化為標(biāo)準(zhǔn)后，用單純形方法求解可得最佳決策方案為 :（萬元）。 甲 乙 擁有量原材料 2 1 11設(shè)備 (臺時(shí) ) 1 2 10單件利潤 8 10生產(chǎn) 甲、乙兩種產(chǎn)品，有關(guān)數(shù)據(jù)如表所示。試求獲利最大的生產(chǎn)方案？21 但是，在實(shí)際決策時(shí)，企業(yè)領(lǐng)導(dǎo)者必須考慮市場等一系列其它條件，如：② 超過計(jì)劃供應(yīng)的 原材料 ，需用高價(jià)采購，這就會使生產(chǎn) 成本增加。③ 應(yīng)盡可能地 充分利用設(shè)備的有效臺時(shí) ，但 不希望加班 。④ 應(yīng)盡可能 達(dá)到并超過計(jì)劃產(chǎn)值指標(biāo) 56萬元 。 這樣，該企業(yè)生產(chǎn)方案的確定，便成為一個多目標(biāo)決策問題，這一問題可以運(yùn)用目標(biāo)規(guī)劃方法進(jìn)行求解。① 根據(jù)市場信息，甲種產(chǎn)品的需求量有下降的趨勢，因 此 甲種產(chǎn)品的產(chǎn)量不應(yīng)大于乙種產(chǎn)品的產(chǎn)量 。22假定有 L個目標(biāo)， K個優(yōu)先級 (K≤L)， n個變量。在同一優(yōu)先級 pk中不同目標(biāo)的正、負(fù)偏差變量的權(quán)系數(shù)分別為 ?kl+、 ?kl，則多目標(biāo)規(guī)劃問題可以表示為：n目標(biāo)規(guī)劃模型的一般形式 目標(biāo)函數(shù)目標(biāo)約束絕對約束非負(fù)約束23在以上各式中，??kl+、 ?kl、分別為賦予 pl優(yōu)先因子的第 k個目標(biāo)的正、負(fù)偏差變量的權(quán)系數(shù)，?gk為第 k個目標(biāo)的預(yù)期值，?xj為決策變量，?dk+、 dk、分別為第 k 個目標(biāo)的正、負(fù)偏差變量，目標(biāo)函數(shù)目標(biāo)約束絕對約束非負(fù)約束24目標(biāo)規(guī)劃數(shù)學(xué)模型中的有關(guān)概念。 (1)偏差變量在目標(biāo)規(guī)劃模型中，除了決策變量外，還需要引入 正、負(fù)偏差變量 d +、 d 。其中，正偏差變量表示決策值超過目標(biāo)值的部分，負(fù)偏差變量表示決策值未達(dá)到目標(biāo)值的部分。因?yàn)闆Q策值不可能既超過目標(biāo)值同時(shí)又未達(dá)到目標(biāo)值，故有 d +d =0成立。(2)絕對約束和目標(biāo)約束 絕對約束 ， 必須嚴(yán)格滿足的等式約束和不等式約束，譬如，線性規(guī)劃問題的所有約束條件都是絕對約束，不能滿足這些約束條件的解稱為非可行解，所以它們是 硬約束 。 25 目標(biāo)約束 ， 目標(biāo)規(guī)劃所特有的，可以將約束方程右端項(xiàng)看作是追求的目標(biāo)值，在達(dá)到此目標(biāo)值時(shí)允許發(fā)生正的或負(fù)的偏差 ，可加入正負(fù)偏差變量，是 軟約束 。 線性規(guī)劃問題的目標(biāo)函數(shù)，在給定目標(biāo)值和加入正、負(fù)偏差變量后可以轉(zhuǎn)化為目標(biāo)約束，也可以根據(jù)問題的需要將絕對約束轉(zhuǎn)化為目標(biāo)約束