多目標(biāo)規(guī)劃方法講義課件

多目標(biāo)規(guī)劃是數(shù)學(xué)規(guī)劃的一個(gè)分支。研究多于一個(gè)的目標(biāo)函數(shù)在給定區(qū)域上的最優(yōu)化。又稱多目標(biāo)最優(yōu)化。通常記為

MOP(multi-objectiveprogramming)。在很多實(shí)際問題中，例如經(jīng)濟(jì)、管理、軍事、科學(xué)和工程設(shè)計(jì)等領(lǐng)域，衡量一個(gè)方案的好壞往往難以用一個(gè)指標(biāo)來判斷，而需要用多個(gè)目標(biāo)來比較，而這些目標(biāo)有時(shí)不甚協(xié)調(diào)，甚至是矛盾的。因此有許多學(xué)者致力于這方面的研究。1896年法國(guó)經(jīng)濟(jì)學(xué)家

V.

帕雷托最早研究不可比較目標(biāo)的優(yōu)化問題，之后，J.馮·諾伊曼、H.W.庫(kù)恩、A.W.塔克、A.M.日夫里翁等數(shù)學(xué)家做了深入的探討，但是尚未有一個(gè)完全令人滿意的定義。多目標(biāo)規(guī)劃方法

多目標(biāo)規(guī)劃是數(shù)學(xué)規(guī)劃的一個(gè)分支。多目標(biāo)規(guī)劃方法求解多目標(biāo)規(guī)劃的方法大體上有以下幾種：一種是化多為少的方法

，

即把多目標(biāo)化為比較容易求解的單目標(biāo)或雙目標(biāo)，如主要目標(biāo)法、線性加權(quán)法、理想點(diǎn)法等；另一種叫分層序列法，即把目標(biāo)按其重要性給出一個(gè)序列，每次都在前一目標(biāo)最優(yōu)解集內(nèi)求下一個(gè)目標(biāo)最優(yōu)解，直到求出共同的最優(yōu)解。對(duì)多目標(biāo)的線性規(guī)劃除以上方法外還可以適當(dāng)修正單純形法來求解；還有一種稱為層次分析法，是由美國(guó)運(yùn)籌學(xué)家沙旦于70年代提出的，這是一種定性與定量相結(jié)合的多目標(biāo)決策與分析方法，對(duì)于目標(biāo)結(jié)構(gòu)復(fù)雜且缺乏必要的數(shù)據(jù)的情況更為實(shí)用。

求解多目標(biāo)規(guī)劃的方法大體上有以下幾種：

多目標(biāo)規(guī)劃模型（一）任何多目標(biāo)規(guī)劃問題，都由兩個(gè)基本部分組成：（1）兩個(gè)以上的目標(biāo)函數(shù)；（2）若干個(gè)約束條件。（二）對(duì)于多目標(biāo)規(guī)劃問題，可以將其數(shù)學(xué)模型一般地描寫為如下形式：

一多目標(biāo)規(guī)劃及其非劣解

式中：為決策變量向量。多目標(biāo)規(guī)劃模型（一）任何多目標(biāo)規(guī)劃問題，都由兩個(gè)基本部縮寫形式：有n個(gè)決策變量，k個(gè)目標(biāo)函數(shù)，m個(gè)約束方程，則：

Z=F(X)是k維函數(shù)向量，(X)是m維函數(shù)向量；

G是m維常數(shù)向量；

（1）（2）縮寫形式：有n個(gè)決策變量，k個(gè)目標(biāo)函數(shù)，m個(gè)約束方程，（1對(duì)于線性多目標(biāo)規(guī)劃問題，可以進(jìn)一步用矩陣表示：

式中：

X為n維決策變量向量；

C為k×n矩陣，即目標(biāo)函數(shù)系數(shù)矩陣；

A為m×n矩陣，即約束方程系數(shù)矩陣；

b為m維的向量，即約束向量。對(duì)于線性多目標(biāo)規(guī)劃問題，可以進(jìn)一步用矩陣表示：式中：多目標(biāo)規(guī)劃的非劣解

多目標(biāo)規(guī)劃問題的求解不能只追求一個(gè)目標(biāo)的最優(yōu)化（最大或最?。?，而不顧其它目標(biāo)。對(duì)于上述多目標(biāo)規(guī)劃問題，求解就意味著需要做出如下的復(fù)合選擇：▲每一個(gè)目標(biāo)函數(shù)取什么值，原問題可以得到最滿意的解決？▲每一個(gè)決策變量取什么值，原問題可以得到最滿意的解決？多目標(biāo)規(guī)劃的非劣解多目標(biāo)規(guī)劃問題的求解不能只追求一個(gè)目標(biāo)的

在圖1中，max(f1,f2).就方案①和②來說，①的f2目標(biāo)值比②大，但其目標(biāo)值f1比②小，因此無法確定這兩個(gè)方案的優(yōu)與劣。在各個(gè)方案之間，顯然：④比①好，⑤比④好,⑥比②好,

⑦比③好……。非劣解可以用圖1說明。圖1多目標(biāo)規(guī)劃的劣解與非劣解在圖1中，max(f1,f2).就方案①和②來說，①

而對(duì)于方案⑤、⑥、⑦之間則無法確定優(yōu)劣，而且又沒有比它們更好的其他方案，所以它們就被稱為多目標(biāo)規(guī)劃問題的非劣解或有效解，其余方案都稱為劣解。所有非劣解構(gòu)成的集合稱為非劣解集。

當(dāng)目標(biāo)函數(shù)處于沖突狀態(tài)時(shí)，就不會(huì)存在使所有目標(biāo)函數(shù)同時(shí)達(dá)到最大或最小值的最優(yōu)解，于是我們只能尋求非劣解（又稱非支配解或帕累托解）。而對(duì)于方案⑤、⑥、⑦之間則無法確定優(yōu)劣，而且效用最優(yōu)化模型理想點(diǎn)模型約束模型目標(biāo)達(dá)到法目標(biāo)規(guī)劃模型二多目標(biāo)規(guī)劃求解

為了求得多目標(biāo)規(guī)劃問題的非劣解，常常需要將多目標(biāo)規(guī)劃問題轉(zhuǎn)化為單目標(biāo)規(guī)劃問題去處理。實(shí)現(xiàn)這種轉(zhuǎn)化，有如下幾種建模方法。效用最優(yōu)化模型二多目標(biāo)規(guī)劃求解為了求得多目標(biāo)規(guī)是與各目標(biāo)函數(shù)相關(guān)的效用函數(shù)的和函數(shù)。

方法一效用最優(yōu)化模型（線性加權(quán)法）

（1）

（2）

思想：規(guī)劃問題的各個(gè)目標(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ī)劃問題：

是與各目標(biāo)函數(shù)相關(guān)的效用函數(shù)的和函數(shù)。方法一效在用效用函數(shù)作為規(guī)劃目標(biāo)時(shí)，需要確定一組權(quán)值

i

來反映原問題中各目標(biāo)函數(shù)在總體目標(biāo)中的權(quán)重，即：式中，i

應(yīng)滿足：向量形式：在用效用函數(shù)作為規(guī)劃目標(biāo)時(shí)，需要確定一組權(quán)值i來反映原方法二理想點(diǎn)模型（罰款模型）

思想:規(guī)劃決策者對(duì)每一個(gè)目標(biāo)函數(shù)都能提出所期望的值（或稱滿意值）；通過比較實(shí)際值fi與期望值fi*之間的偏差來選擇問題的解，其數(shù)學(xué)表達(dá)式如下：或?qū)懗删仃囆问剑?/p>

式中，是與第i個(gè)目標(biāo)函數(shù)相關(guān)的權(quán)重；

A是由(i=1,2,…,k)組成的m×m對(duì)角矩陣。方法二理想點(diǎn)模型（罰款模型）思想:規(guī)劃決策者對(duì)每一理論依據(jù)：若規(guī)劃問題的某一目標(biāo)可以給出一個(gè)可供選擇的范圍，則該目標(biāo)就可以作為約束條件而被排除出目標(biāo)組，進(jìn)入約束條件組中。假如，除第一個(gè)目標(biāo)外，其余目標(biāo)都可以提出一個(gè)可供選擇的范圍，則該多目標(biāo)規(guī)劃問題就可以轉(zhuǎn)化為單目標(biāo)規(guī)劃問題：方法三約束模型（極大極小法）

理論依據(jù)：若規(guī)劃問題的某一目標(biāo)可以給出一個(gè)可供選擇的范圍，方法四目標(biāo)達(dá)到法

首先將多目標(biāo)規(guī)劃模型化為如下標(biāo)準(zhǔn)形式：方法四目標(biāo)達(dá)到法首先將多目標(biāo)規(guī)劃模型化為如下標(biāo)準(zhǔn)形式：在求解之前，先設(shè)計(jì)與目標(biāo)函數(shù)相應(yīng)的一組目標(biāo)值理想化的期望目標(biāo)fi*(i=1,2,…,k),每一個(gè)目標(biāo)對(duì)應(yīng)的權(quán)重系數(shù)為i*(i=1,2,…,k)，再設(shè)為一松弛因子。那么，多目標(biāo)規(guī)劃問題就轉(zhuǎn)化為：在求解之前，先設(shè)計(jì)與目標(biāo)函數(shù)相應(yīng)的一組目標(biāo)值理想化的期望目標(biāo)目標(biāo)規(guī)劃(Goalprogramming)目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃概述目標(biāo)規(guī)劃目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)

目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)經(jīng)濟(jì)管理中多目標(biāo)決策的需要而逐步發(fā)展起來的一個(gè)分支。

2、線性規(guī)劃求最優(yōu)解；目標(biāo)規(guī)劃是找到一個(gè)滿意解。1、線性規(guī)劃只討論一個(gè)線性目標(biāo)函數(shù)在一組線性約束條件下的極值問題；而目標(biāo)規(guī)劃是多個(gè)目標(biāo)決策，可求得更切合實(shí)際的解。一、目標(biāo)規(guī)劃概述（一）、目標(biāo)規(guī)劃與線性規(guī)劃的比較目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)經(jīng)濟(jì)管理中多4、線性規(guī)劃的最優(yōu)解是絕對(duì)意義下的最優(yōu)，但需花去大量的人力、物力、財(cái)力才能得到；實(shí)際過程中，只要求得滿意解，就能滿足需要（或更能滿足需要）。3、線性規(guī)劃中的約束條件是同等重要的，是硬約束；而目標(biāo)規(guī)劃中有輕重緩急和主次之分，即有優(yōu)先權(quán)。目前，已經(jīng)在經(jīng)濟(jì)計(jì)劃、生產(chǎn)管理、經(jīng)營(yíng)管理、市場(chǎng)分析、財(cái)務(wù)管理等方面得到了廣泛的應(yīng)用。4、線性規(guī)劃的最優(yōu)解是絕對(duì)意義下的最優(yōu)，但需花去大量的人

例一、某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料如表所示。試制定生產(chǎn)計(jì)劃，使獲得的利潤(rùn)最大？同時(shí)，根據(jù)市場(chǎng)預(yù)測(cè)，甲的銷路不是太好，應(yīng)盡可能少生產(chǎn)；乙的銷路較好，可以擴(kuò)大生產(chǎn)。試建立此問題的數(shù)學(xué)模型。12070單件利潤(rùn)3000103設(shè)備臺(tái)時(shí)200054煤炭360049鋼材資源限制乙甲單位產(chǎn)品資源消耗（二）、目標(biāo)規(guī)劃的基本概念例一、某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，設(shè)：甲產(chǎn)品x1

，乙產(chǎn)品x2

一般有：maxZ=70x1

+120x29x1+4x2≤36004x1+5x2≤20003x1+10x2≤3000

x1，

x2≥0同時(shí)：maxZ1=70x1

+120x2minZ2=x1maxZ3=x29x1+4x2≤36004x1+5x2≤20003x1+10x2≤3000

x1，

x2≥0顯然，這是一個(gè)多目標(biāo)規(guī)劃問題，用線性規(guī)劃方法很難找到最優(yōu)解。設(shè)：甲產(chǎn)品x1，乙產(chǎn)品x2一般有：m

目標(biāo)規(guī)劃通過引入目標(biāo)值和偏差變量，可以將目標(biāo)函數(shù)轉(zhuǎn)化為目標(biāo)約束。目標(biāo)值：是指預(yù)先給定的某個(gè)目標(biāo)的一個(gè)期望值。實(shí)現(xiàn)值或決策值：是指當(dāng)決策變量xj

選定以后，目標(biāo)函數(shù)的對(duì)應(yīng)值。偏差變量（事先無法確定的未知數(shù)）：是指實(shí)現(xiàn)值和目標(biāo)值之間的差異,記為d。正偏差變量：表示實(shí)現(xiàn)值超過目標(biāo)值的部分，記為d＋。負(fù)偏差變量：表示實(shí)現(xiàn)值未達(dá)到目標(biāo)值的部分，記為d－。1、目標(biāo)值和偏差變量1、目標(biāo)值和偏差變量

當(dāng)完成或超額完成規(guī)定的指標(biāo)則表示：d＋≥0,d－＝0當(dāng)未完成規(guī)定的指標(biāo)則表示：d＋＝0,d－≥0當(dāng)恰好完成指標(biāo)時(shí)則表示：d＋＝0,d－＝0∴d＋×d－

＝0成立。

引入了目標(biāo)值和正、負(fù)偏差變量后，就對(duì)某一問題有了新的限制，既目標(biāo)約束。目標(biāo)約束即可對(duì)原目標(biāo)函數(shù)起作用，也可對(duì)原約束起作用。目標(biāo)約束是目標(biāo)規(guī)劃中特有的，是軟約束。在一次決策中，實(shí)現(xiàn)值不可能既超過目標(biāo)值又未達(dá)到目標(biāo)值，故有d＋×d－

＝0,并規(guī)定d＋≥0,d－≥02、目標(biāo)約束和絕對(duì)約束引入了目標(biāo)值和正、負(fù)偏差變量后，就對(duì)絕對(duì)約束（系統(tǒng)約束）是指必須嚴(yán)格滿足的等式或不等式約束。如線性規(guī)劃中的所有約束條件都是絕對(duì)約束，否則無可行解。所以，絕對(duì)約束是硬約束。例如：在例一中，規(guī)定Z1的目標(biāo)值為50000,正、負(fù)偏差為d＋、d－,則目標(biāo)函數(shù)可以轉(zhuǎn)換為目標(biāo)約束，既70x1

+120x2＋＝50000，

同樣，若規(guī)定Z2＝200，Z3＝250

則有若規(guī)定3600的鋼材必須用完，原式9x1+4x2≤3600則變?yōu)榻^對(duì)約束（系統(tǒng)約束）是指必須嚴(yán)格滿足的等式或不等式約

達(dá)成函數(shù)是一個(gè)使總偏差量為最小的目標(biāo)函數(shù)，記為minZ=f（d＋、d－）。

一般說來，有以下三種情況，但只能出現(xiàn)其中之一：⑴.要求恰好達(dá)到規(guī)定的目標(biāo)值，即正、負(fù)偏差變量要盡可能小，則minZ=f（d＋＋d－）。⑵.要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值，也就是正偏差變量盡可能小，則minZ=f（d＋）。⑶.要求超過目標(biāo)值，即超過量不限，但不低于目標(biāo)值，也就是負(fù)偏差變量盡可能小，則minZ=f（d－）。

對(duì)于由絕對(duì)約束轉(zhuǎn)化而來的目標(biāo)函數(shù)，也照上述處理即可。3、達(dá)成函數(shù)（即目標(biāo)規(guī)劃中的目標(biāo)函數(shù)）達(dá)成函數(shù)是一個(gè)使總偏差量為最小的目標(biāo)函數(shù)，記為m優(yōu)先因子Pk

是將決策目標(biāo)按其重要程度排序并表示出來。P1>>P2>>…>>Pk>>Pk+1>>…>>PK，k=1.2…K。權(quán)系數(shù)ωk區(qū)別具有相同優(yōu)先因子的兩個(gè)目標(biāo)的差別，決策者可視具體情況而定。對(duì)于這種解來說，前面的目標(biāo)可以保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，而后面的目標(biāo)就不一定能保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，有些可能就不能實(shí)現(xiàn)。4、優(yōu)先因子（優(yōu)先等級(jí)）與優(yōu)先權(quán)系數(shù)5、滿意解（具有層次意義的解）優(yōu)先因子Pk是將決策目標(biāo)按其重要程度排序并表示若在例一中提出下列要求：1、完成或超額完成利潤(rùn)指標(biāo)50000元；2、產(chǎn)品甲不超過200件，產(chǎn)品乙不低于250件；3、現(xiàn)有鋼材3600噸必須用完。試建立目標(biāo)規(guī)劃模型。分析：題目有三個(gè)目標(biāo)層次，包含四個(gè)目標(biāo)值。第一目標(biāo)：第二目標(biāo)：有兩個(gè)要求即甲，乙，但兩個(gè)具有相同的優(yōu)先因子，因此需要確定權(quán)系數(shù)。本題可用單件利潤(rùn)比作為權(quán)系數(shù)即70:120，化簡(jiǎn)為7:12。例二、若在例一中提出下列要求：分析：題目有第三目標(biāo)：目標(biāo)規(guī)劃模型為：第三目標(biāo)：目標(biāo)規(guī)劃模型為：某廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，有關(guān)數(shù)據(jù)如表所示。試求獲利最大的生產(chǎn)方案？ⅠⅡ擁有量原材料2111設(shè)備(臺(tái)時(shí))1210單件利潤(rùn)810在此基礎(chǔ)上考慮：1、產(chǎn)品Ⅱ的產(chǎn)量不低于產(chǎn)品Ⅰ的產(chǎn)量；2、充分利用設(shè)備有效臺(tái)時(shí)，不加班；3、利潤(rùn)不小于56元。解:分析第一目標(biāo)：即產(chǎn)品Ⅰ的產(chǎn)量不大于Ⅱ的產(chǎn)量。第二目標(biāo)：例三：某廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，有關(guān)數(shù)據(jù)如表所示。第三目標(biāo)：規(guī)劃模型：第三目標(biāo)：規(guī)劃模型：（一）、模型的一般形式二、目標(biāo)規(guī)劃的數(shù)學(xué)模型（一）、模型的一般形式二、目標(biāo)規(guī)劃的數(shù)學(xué)模型（二）、建模的步驟1、根據(jù)要研究的問題所提出的各目標(biāo)與條件，確定目標(biāo)值，列出目標(biāo)約束與絕對(duì)約束；4、對(duì)同一優(yōu)先等級(jí)中的各偏差變量，若需要可按其重要程度的不同，賦予相應(yīng)的權(quán)系數(shù)。3、給各目標(biāo)賦予相應(yīng)的優(yōu)先因子Pk（k=1.2…K）。2、可根據(jù)決策者的需要，將某些或全部絕對(duì)約束轉(zhuǎn)化為目標(biāo)約束。這時(shí)只需要給絕對(duì)約束加上負(fù)偏差變量和減去正偏差變量即可。（二）、建模的步驟1、根據(jù)要研究的問題所提出的各目標(biāo)與5、根據(jù)決策者的要求，按下列情況之一構(gòu)造一個(gè)由優(yōu)先因子和權(quán)系數(shù)相對(duì)應(yīng)的偏差變量組成的，要求實(shí)現(xiàn)極小化的目標(biāo)函數(shù)，即達(dá)成函數(shù)。⑴.恰好達(dá)到目標(biāo)值，取。⑵.允許超過目標(biāo)值，取。⑶.不允許超過目標(biāo)值，取。5、根據(jù)決策者的要求，按下列情況之一構(gòu)造一個(gè)由⑴.恰（三）、小結(jié)線性規(guī)劃LP目標(biāo)規(guī)劃GP目標(biāo)函數(shù)min,max系數(shù)可正負(fù)min,偏差變量系數(shù)≥0變量xi,xsxa

xixsxad約束條件系統(tǒng)約束（絕對(duì)約束）目標(biāo)約束系統(tǒng)約束解最優(yōu)最滿意（三）、小結(jié)線性規(guī)劃LP目標(biāo)規(guī)劃GP目標(biāo)函數(shù)min,圖解法同樣適用兩個(gè)變量的目標(biāo)規(guī)劃問題，但其操作簡(jiǎn)單，原理一目了然。同時(shí)，也有助于理解一般目標(biāo)規(guī)劃的求解原理和過程。圖解法解題步驟如下：1、確定各約束條件的可行域，即將所有約束條件（包括目標(biāo)約束和絕對(duì)約束，暫不考慮正負(fù)偏差變量）在坐標(biāo)平面上表示出來；2、在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、負(fù)偏差變量值增大的方向；三、目標(biāo)規(guī)劃的圖解法圖解法同樣適用兩個(gè)變量的目標(biāo)規(guī)劃問題，但其操作簡(jiǎn)單3、求滿足最高優(yōu)先等級(jí)目標(biāo)的解；4、轉(zhuǎn)到下一個(gè)優(yōu)先等級(jí)的目標(biāo)，在不破壞所有較高優(yōu)先等級(jí)目標(biāo)的前提下，求出該優(yōu)先等級(jí)目標(biāo)的解；5、重復(fù)4，直到所有優(yōu)先等級(jí)的目標(biāo)都已審查完畢為止；6、確定最優(yōu)解和滿意解。例一、用圖解法求解目標(biāo)規(guī)劃問題3、求滿足最高優(yōu)先等級(jí)目標(biāo)的解；例一、用圖解法求解012345678123456⑴⑵⑶Ax2

x1BC

B(0.6250,4.6875)C(0,5.2083)，B、C線段上的所有點(diǎn)均是該問題的解（無窮多最優(yōu)解）。01234例二、已知一個(gè)生產(chǎn)計(jì)劃的線性規(guī)劃模型為其中目標(biāo)函數(shù)為總利潤(rùn)，x1,x2為產(chǎn)品A、B產(chǎn)量?，F(xiàn)有下列目標(biāo)：1、要求總利潤(rùn)必須超過2500元；2、考慮產(chǎn)品受市場(chǎng)影響，為避免積壓，A、B的生產(chǎn)量不超過60件和100件；3、由于甲資源供應(yīng)比較緊張，不要超過現(xiàn)有量140。試建立目標(biāo)規(guī)劃模型，并用圖解法求解。例二、已知一個(gè)生產(chǎn)計(jì)劃的線性規(guī)劃模型為其中目標(biāo)解：以產(chǎn)品A、B的單件利潤(rùn)比2.5：1為權(quán)系數(shù)，模型如下：解：以產(chǎn)品A、B的單件利潤(rùn)比2.5：1為權(quán)系數(shù)0x2

0⑴x11401201008060402020406080100⑵⑶⑷ABCD結(jié)論：C(60,58.3)為所求的滿意解。作圖：0x20⑴x1140204060檢驗(yàn)：將上述結(jié)果帶入模型，因＝＝0；

＝＝0；

＝0，存在；＝0，存在。所以，有下式：minZ=P3

將x1＝60，x2

＝58.3帶入約束條件，得30×60＋12×58.3＝2499.6≈2500；2×60+58.3=178.3>140；1×60＝601×58.3＝58.3<100由上可知：若A、B的計(jì)劃產(chǎn)量為60件和58.3件時(shí)，所需甲資源數(shù)量將超過現(xiàn)有庫(kù)存。在現(xiàn)有條件下，此解為非可行解。為此，企業(yè)必須采取措施降低A、B產(chǎn)品對(duì)甲資源的消耗量，由原來的100％降至78.5％（140÷178.3＝0.785），才能使生產(chǎn)方案（60，58.3）成為可行方案。檢驗(yàn)：將上述結(jié)果帶入模型，因＝＝練習(xí)：用圖解法求解下列目標(biāo)規(guī)劃問題練習(xí)：用圖解法求解下列目標(biāo)規(guī)劃問題⑴⑵⑶⑷CD結(jié)論：有無窮多最優(yōu)解。C（2，4）D（10/3，10/3）⑴⑵⑶⑷CD結(jié)論：有無窮多最優(yōu)解。C（2，4）D（10/3，多目標(biāo)規(guī)劃是數(shù)學(xué)規(guī)劃的一個(gè)分支。研究多于一個(gè)的目標(biāo)函數(shù)在給定區(qū)域上的最優(yōu)化。又稱多目標(biāo)最優(yōu)化。通常記為

MOP(multi-objectiveprogramming)。在很多實(shí)際問題中，例如經(jīng)濟(jì)、管理、軍事、科學(xué)和工程設(shè)計(jì)等領(lǐng)域，衡量一個(gè)方案的好壞往往難以用一個(gè)指標(biāo)來判斷，而需要用多個(gè)目標(biāo)來比較，而這些目標(biāo)有時(shí)不甚協(xié)調(diào)，甚至是矛盾的。因此有許多學(xué)者致力于這方面的研究。1896年法國(guó)經(jīng)濟(jì)學(xué)家

V.

帕雷托最早研究不可比較目標(biāo)的優(yōu)化問題，之后，J.馮·諾伊曼、H.W.庫(kù)恩、A.W.塔克、A.M.日夫里翁等數(shù)學(xué)家做了深入的探討，但是尚未有一個(gè)完全令人滿意的定義。多目標(biāo)規(guī)劃方法

多目標(biāo)規(guī)劃是數(shù)學(xué)規(guī)劃的一個(gè)分支。多目標(biāo)規(guī)劃方法求解多目標(biāo)規(guī)劃的方法大體上有以下幾種：一種是化多為少的方法

，

即把多目標(biāo)化為比較容易求解的單目標(biāo)或雙目標(biāo)，如主要目標(biāo)法、線性加權(quán)法、理想點(diǎn)法等；另一種叫分層序列法，即把目標(biāo)按其重要性給出一個(gè)序列，每次都在前一目標(biāo)最優(yōu)解集內(nèi)求下一個(gè)目標(biāo)最優(yōu)解，直到求出共同的最優(yōu)解。對(duì)多目標(biāo)的線性規(guī)劃除以上方法外還可以適當(dāng)修正單純形法來求解；還有一種稱為層次分析法，是由美國(guó)運(yùn)籌學(xué)家沙旦于70年代提出的，這是一種定性與定量相結(jié)合的多目標(biāo)決策與分析方法，對(duì)于目標(biāo)結(jié)構(gòu)復(fù)雜且缺乏必要的數(shù)據(jù)的情況更為實(shí)用。

求解多目標(biāo)規(guī)劃的方法大體上有以下幾種：

多目標(biāo)規(guī)劃模型（一）任何多目標(biāo)規(guī)劃問題，都由兩個(gè)基本部分組成：（1）兩個(gè)以上的目標(biāo)函數(shù)；（2）若干個(gè)約束條件。（二）對(duì)于多目標(biāo)規(guī)劃問題，可以將其數(shù)學(xué)模型一般地描寫為如下形式：

一多目標(biāo)規(guī)劃及其非劣解

式中：為決策變量向量。多目標(biāo)規(guī)劃模型（一）任何多目標(biāo)規(guī)劃問題，都由兩個(gè)基本部縮寫形式：有n個(gè)決策變量，k個(gè)目標(biāo)函數(shù)，m個(gè)約束方程，則：

Z=F(X)是k維函數(shù)向量，(X)是m維函數(shù)向量；

G是m維常數(shù)向量；

（1）（2）縮寫形式：有n個(gè)決策變量，k個(gè)目標(biāo)函數(shù)，m個(gè)約束方程，（1對(duì)于線性多目標(biāo)規(guī)劃問題，可以進(jìn)一步用矩陣表示：

式中：

X為n維決策變量向量；

C為k×n矩陣，即目標(biāo)函數(shù)系數(shù)矩陣；

A為m×n矩陣，即約束方程系數(shù)矩陣；

b為m維的向量，即約束向量。對(duì)于線性多目標(biāo)規(guī)劃問題，可以進(jìn)一步用矩陣表示：式中：多目標(biāo)規(guī)劃的非劣解

多目標(biāo)規(guī)劃問題的求解不能只追求一個(gè)目標(biāo)的最優(yōu)化（最大或最?。?，而不顧其它目標(biāo)。對(duì)于上述多目標(biāo)規(guī)劃問題，求解就意味著需要做出如下的復(fù)合選擇：▲每一個(gè)目標(biāo)函數(shù)取什么值，原問題可以得到最滿意的解決？▲每一個(gè)決策變量取什么值，原問題可以得到最滿意的解決？多目標(biāo)規(guī)劃的非劣解多目標(biāo)規(guī)劃問題的求解不能只追求一個(gè)目標(biāo)的

在圖1中，max(f1,f2).就方案①和②來說，①的f2目標(biāo)值比②大，但其目標(biāo)值f1比②小，因此無法確定這兩個(gè)方案的優(yōu)與劣。在各個(gè)方案之間，顯然：④比①好，⑤比④好,⑥比②好,

⑦比③好……。非劣解可以用圖1說明。圖1多目標(biāo)規(guī)劃的劣解與非劣解在圖1中，max(f1,f2).就方案①和②來說，①

而對(duì)于方案⑤、⑥、⑦之間則無法確定優(yōu)劣，而且又沒有比它們更好的其他方案，所以它們就被稱為多目標(biāo)規(guī)劃問題的非劣解或有效解，其余方案都稱為劣解。所有非劣解構(gòu)成的集合稱為非劣解集。

當(dāng)目標(biāo)函數(shù)處于沖突狀態(tài)時(shí)，就不會(huì)存在使所有目標(biāo)函數(shù)同時(shí)達(dá)到最大或最小值的最優(yōu)解，于是我們只能尋求非劣解（又稱非支配解或帕累托解）。而對(duì)于方案⑤、⑥、⑦之間則無法確定優(yōu)劣，而且效用最優(yōu)化模型理想點(diǎn)模型約束模型目標(biāo)達(dá)到法目標(biāo)規(guī)劃模型二多目標(biāo)規(guī)劃求解

為了求得多目標(biāo)規(guī)劃問題的非劣解，常常需要將多目標(biāo)規(guī)劃問題轉(zhuǎn)化為單目標(biāo)規(guī)劃問題去處理。實(shí)現(xiàn)這種轉(zhuǎn)化，有如下幾種建模方法。效用最優(yōu)化模型二多目標(biāo)規(guī)劃求解為了求得多目標(biāo)規(guī)是與各目標(biāo)函數(shù)相關(guān)的效用函數(shù)的和函數(shù)。

方法一效用最優(yōu)化模型（線性加權(quán)法）

（1）

（2）

思想：規(guī)劃問題的各個(gè)目標(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ī)劃問題：

是與各目標(biāo)函數(shù)相關(guān)的效用函數(shù)的和函數(shù)。方法一效在用效用函數(shù)作為規(guī)劃目標(biāo)時(shí)，需要確定一組權(quán)值

i

來反映原問題中各目標(biāo)函數(shù)在總體目標(biāo)中的權(quán)重，即：式中，i

應(yīng)滿足：向量形式：在用效用函數(shù)作為規(guī)劃目標(biāo)時(shí)，需要確定一組權(quán)值i來反映原方法二理想點(diǎn)模型（罰款模型）

思想:規(guī)劃決策者對(duì)每一個(gè)目標(biāo)函數(shù)都能提出所期望的值（或稱滿意值）；通過比較實(shí)際值fi與期望值fi*之間的偏差來選擇問題的解，其數(shù)學(xué)表達(dá)式如下：或?qū)懗删仃囆问剑?/p>

式中，是與第i個(gè)目標(biāo)函數(shù)相關(guān)的權(quán)重；

A是由(i=1,2,…,k)組成的m×m對(duì)角矩陣。方法二理想點(diǎn)模型（罰款模型）思想:規(guī)劃決策者對(duì)每一理論依據(jù)：若規(guī)劃問題的某一目標(biāo)可以給出一個(gè)可供選擇的范圍，則該目標(biāo)就可以作為約束條件而被排除出目標(biāo)組，進(jìn)入約束條件組中。假如，除第一個(gè)目標(biāo)外，其余目標(biāo)都可以提出一個(gè)可供選擇的范圍，則該多目標(biāo)規(guī)劃問題就可以轉(zhuǎn)化為單目標(biāo)規(guī)劃問題：方法三約束模型（極大極小法）

理論依據(jù)：若規(guī)劃問題的某一目標(biāo)可以給出一個(gè)可供選擇的范圍，方法四目標(biāo)達(dá)到法

首先將多目標(biāo)規(guī)劃模型化為如下標(biāo)準(zhǔn)形式：方法四目標(biāo)達(dá)到法首先將多目標(biāo)規(guī)劃模型化為如下標(biāo)準(zhǔn)形式：在求解之前，先設(shè)計(jì)與目標(biāo)函數(shù)相應(yīng)的一組目標(biāo)值理想化的期望目標(biāo)fi*(i=1,2,…,k),每一個(gè)目標(biāo)對(duì)應(yīng)的權(quán)重系數(shù)為i*(i=1,2,…,k)，再設(shè)為一松弛因子。那么，多目標(biāo)規(guī)劃問題就轉(zhuǎn)化為：在求解之前，先設(shè)計(jì)與目標(biāo)函數(shù)相應(yīng)的一組目標(biāo)值理想化的期望目標(biāo)目標(biāo)規(guī)劃(Goalprogramming)目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃概述目標(biāo)規(guī)劃目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)

目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)經(jīng)濟(jì)管理中多目標(biāo)決策的需要而逐步發(fā)展起來的一個(gè)分支。

2、線性規(guī)劃求最優(yōu)解；目標(biāo)規(guī)劃是找到一個(gè)滿意解。1、線性規(guī)劃只討論一個(gè)線性目標(biāo)函數(shù)在一組線性約束條件下的極值問題；而目標(biāo)規(guī)劃是多個(gè)目標(biāo)決策，可求得更切合實(shí)際的解。一、目標(biāo)規(guī)劃概述（一）、目標(biāo)規(guī)劃與線性規(guī)劃的比較目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)經(jīng)濟(jì)管理中多4、線性規(guī)劃的最優(yōu)解是絕對(duì)意義下的最優(yōu)，但需花去大量的人力、物力、財(cái)力才能得到；實(shí)際過程中，只要求得滿意解，就能滿足需要（或更能滿足需要）。3、線性規(guī)劃中的約束條件是同等重要的，是硬約束；而目標(biāo)規(guī)劃中有輕重緩急和主次之分，即有優(yōu)先權(quán)。目前，已經(jīng)在經(jīng)濟(jì)計(jì)劃、生產(chǎn)管理、經(jīng)營(yíng)管理、市場(chǎng)分析、財(cái)務(wù)管理等方面得到了廣泛的應(yīng)用。4、線性規(guī)劃的最優(yōu)解是絕對(duì)意義下的最優(yōu)，但需花去大量的人

例一、某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料如表所示。試制定生產(chǎn)計(jì)劃，使獲得的利潤(rùn)最大？同時(shí)，根據(jù)市場(chǎng)預(yù)測(cè)，甲的銷路不是太好，應(yīng)盡可能少生產(chǎn)；乙的銷路較好，可以擴(kuò)大生產(chǎn)。試建立此問題的數(shù)學(xué)模型。12070單件利潤(rùn)3000103設(shè)備臺(tái)時(shí)200054煤炭360049鋼材資源限制乙甲單位產(chǎn)品資源消耗（二）、目標(biāo)規(guī)劃的基本概念例一、某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，設(shè)：甲產(chǎn)品x1

，乙產(chǎn)品x2

一般有：maxZ=70x1

+120x29x1+4x2≤36004x1+5x2≤20003x1+10x2≤3000

x1，

x2≥0同時(shí)：maxZ1=70x1

+120x2minZ2=x1maxZ3=x29x1+4x2≤36004x1+5x2≤20003x1+10x2≤3000

x1，

x2≥0顯然，這是一個(gè)多目標(biāo)規(guī)劃問題，用線性規(guī)劃方法很難找到最優(yōu)解。設(shè)：甲產(chǎn)品x1，乙產(chǎn)品x2一般有：m

目標(biāo)規(guī)劃通過引入目標(biāo)值和偏差變量，可以將目標(biāo)函數(shù)轉(zhuǎn)化為目標(biāo)約束。目標(biāo)值：是指預(yù)先給定的某個(gè)目標(biāo)的一個(gè)期望值。實(shí)現(xiàn)值或決策值：是指當(dāng)決策變量xj

選定以后，目標(biāo)函數(shù)的對(duì)應(yīng)值。偏差變量（事先無法確定的未知數(shù)）：是指實(shí)現(xiàn)值和目標(biāo)值之間的差異,記為d。正偏差變量：表示實(shí)現(xiàn)值超過目標(biāo)值的部分，記為d＋。負(fù)偏差變量：表示實(shí)現(xiàn)值未達(dá)到目標(biāo)值的部分，記為d－。1、目標(biāo)值和偏差變量1、目標(biāo)值和偏差變量

當(dāng)完成或超額完成規(guī)定的指標(biāo)則表示：d＋≥0,d－＝0當(dāng)未完成規(guī)定的指標(biāo)則表示：d＋＝0,d－≥0當(dāng)恰好完成指標(biāo)時(shí)則表示：d＋＝0,d－＝0∴d＋×d－

＝0成立。

引入了目標(biāo)值和正、負(fù)偏差變量后，就對(duì)某一問題有了新的限制，既目標(biāo)約束。目標(biāo)約束即可對(duì)原目標(biāo)函數(shù)起作用，也可對(duì)原約束起作用。目標(biāo)約束是目標(biāo)規(guī)劃中特有的，是軟約束。在一次決策中，實(shí)現(xiàn)值不可能既超過目標(biāo)值又未達(dá)到目標(biāo)值，故有d＋×d－

＝0,并規(guī)定d＋≥0,d－≥02、目標(biāo)約束和絕對(duì)約束引入了目標(biāo)值和正、負(fù)偏差變量后，就對(duì)絕對(duì)約束（系統(tǒng)約束）是指必須嚴(yán)格滿足的等式或不等式約束。如線性規(guī)劃中的所有約束條件都是絕對(duì)約束，否則無可行解。所以，絕對(duì)約束是硬約束。例如：在例一中，規(guī)定Z1的目標(biāo)值為50000,正、負(fù)偏差為d＋、d－,則目標(biāo)函數(shù)可以轉(zhuǎn)換為目標(biāo)約束，既70x1

+120x2＋＝50000，

同樣，若規(guī)定Z2＝200，Z3＝250

則有若規(guī)定3600的鋼材必須用完，原式9x1+4x2≤3600則變?yōu)榻^對(duì)約束（系統(tǒng)約束）是指必須嚴(yán)格滿足的等式或不等式約

達(dá)成函數(shù)是一個(gè)使總偏差量為最小的目標(biāo)函數(shù)，記為minZ=f（d＋、d－）。

一般說來，有以下三種情況，但只能出現(xiàn)其中之一：⑴.要求恰好達(dá)到規(guī)定的目標(biāo)值，即正、負(fù)偏差變量要盡可能小，則minZ=f（d＋＋d－）。⑵.要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值，也就是正偏差變量盡可能小，則minZ=f（d＋）。⑶.要求超過目標(biāo)值，即超過量不限，但不低于目標(biāo)值，也就是負(fù)偏差變量盡可能小，則minZ=f（d－）。

對(duì)于由絕對(duì)約束轉(zhuǎn)化而來的目標(biāo)函數(shù)，也照上述處理即可。3、達(dá)成函數(shù)（即目標(biāo)規(guī)劃中的目標(biāo)函數(shù)）達(dá)成函數(shù)是一個(gè)使總偏差量為最小的目標(biāo)函數(shù)，記為m優(yōu)先因子Pk

是將決策目標(biāo)按其重要程度排序并表示出來。P1>>P2>>…>>Pk>>Pk+1>>…>>PK，k=1.2…K。權(quán)系數(shù)ωk區(qū)別具有相同優(yōu)先因子的兩個(gè)目標(biāo)的差別，決策者可視具體情況而定。對(duì)于這種解來說，前面的目標(biāo)可以保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，而后面的目標(biāo)就不一定能保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，有些可能就不能實(shí)現(xiàn)。4、優(yōu)先因子（優(yōu)先等級(jí)）與優(yōu)先權(quán)系數(shù)5、滿意解（具有層次意義的解）優(yōu)先因子Pk是將決策目標(biāo)按其重要程度排序并表示若在例一中提出下列要求：1、完成或超額完成利潤(rùn)指標(biāo)50000元；2、產(chǎn)品甲不超過200件，產(chǎn)品乙不低于250件；3、現(xiàn)有鋼材3600噸必須用完。試建立目標(biāo)規(guī)劃模型。分析：題目有三個(gè)目標(biāo)層次，包含四個(gè)目標(biāo)值。第一目標(biāo)：第二目標(biāo)：有兩個(gè)要求即甲，乙，但兩個(gè)具有相同的優(yōu)先因子，因此需要確定權(quán)系數(shù)。本題可用單件利潤(rùn)比作為權(quán)系數(shù)即70:120，化簡(jiǎn)為7:12。例二、若在例一中提出下列要求：分析：題目有第三目標(biāo)：目標(biāo)規(guī)劃模型為：第三目標(biāo)：目標(biāo)規(guī)劃模型為：某廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，有關(guān)數(shù)據(jù)如表所示。試求獲利最大的生產(chǎn)方案？ⅠⅡ擁有量原材料2111設(shè)備(臺(tái)時(shí))1210單件利潤(rùn)810在此基礎(chǔ)上考慮：1、產(chǎn)品Ⅱ的產(chǎn)量不低于產(chǎn)品Ⅰ的產(chǎn)量；2、充分利用設(shè)備有效臺(tái)時(shí)，不加班；3、利潤(rùn)不小于56元。解:分析第一目標(biāo)：即產(chǎn)品Ⅰ的產(chǎn)量不大于Ⅱ的產(chǎn)量。第二目標(biāo)：例三：某廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，有關(guān)數(shù)據(jù)如表所示。第三目標(biāo)：規(guī)劃模型：第三目標(biāo)：規(guī)劃模型：（一）、模型的一般形式二、目標(biāo)規(guī)劃的數(shù)學(xué)模型（一）、模型的一般形式二、目標(biāo)規(guī)劃的數(shù)學(xué)模型（二）、建模的步驟1、根據(jù)要研究的問題所提出的各目標(biāo)與條件，確定目標(biāo)值，列出目標(biāo)約束與絕對(duì)約束；4、對(duì)同一優(yōu)先等級(jí)中的各偏差變量，若需要可按其重要程度的不同，賦予相應(yīng)的權(quán)系數(shù)。3、給各目標(biāo)賦予相應(yīng)的優(yōu)先因子Pk（k=1.2…K）。2、可根據(jù)決策者的需要，將某些或全部絕對(duì)約束轉(zhuǎn)化為目標(biāo)約束。這時(shí)只需要給絕對(duì)約束加上負(fù)偏差變量和減去正偏差變量即可。（二）、建模的步驟1、根據(jù)要研究的問題所提出的各目標(biāo)與5、根據(jù)決策者的要求，按下列情況之一構(gòu)造一個(gè)由優(yōu)先因子和權(quán)系數(shù)相對(duì)應(yīng)的偏差變量組成的，要求實(shí)現(xiàn)極小化的目標(biāo)函數(shù)，即達(dá)成函數(shù)。⑴.恰好達(dá)到目標(biāo)值，取。⑵.允許超過目標(biāo)值，取。⑶.不允許超過目標(biāo)值，取。5、根據(jù)決策者的要求，按下列情況之一構(gòu)造一個(gè)由⑴.?。ㄈ?、小結(jié)線性規(guī)劃LP目標(biāo)規(guī)劃GP目標(biāo)函數(shù)min,max系數(shù)可正負(fù)min,偏差變量系數(shù)≥0變量xi,xsxa

x