1、L16 多目標(biāo)決策,詹文杰（教授/博導(dǎo)） Office: 611室 Tel:Email: ,學(xué)習(xí)目標(biāo),了解多目標(biāo)決策的特征； 了解常用的多目標(biāo)決策求解方法； 了解步驟法(STEM法)； 掌握目標(biāo)規(guī)劃方法(圖解法)。,16 多目標(biāo)決策,16.1 多目標(biāo)決策的特征 16.2 多目標(biāo)決策的求解 16.3 步驟法(STEM法) 16.4 目標(biāo)規(guī)劃方法,16.1 多目標(biāo)決策的特征,本章討論決策變量為連續(xù)型的多準(zhǔn)則決策問(wèn)題，即多目標(biāo)決策問(wèn)題(MODM)。 這類問(wèn)題的備選方案集由一集有因果關(guān)系的決策變量隱式地給出。 由于在求解這一類問(wèn)題時(shí)，尤其在生成非劣解過(guò)程中，決策分析人員的作

2、用十分重要，因此將特別關(guān)注分析人員如何與決策人結(jié)合去獲得決策人最滿意的方案。,16.1 多目標(biāo)決策的特征,一、解的特點(diǎn) 二、模型結(jié)構(gòu),在解決單目標(biāo)問(wèn)題時(shí)，我們的任務(wù)是選擇一個(gè)或一組變量X，使目標(biāo)函數(shù)f(X)取得最大（或最?。?。對(duì)于任意兩方案所對(duì)應(yīng)的解，只要比較它們相應(yīng)的目標(biāo)值，就可以判斷誰(shuí)優(yōu)誰(shuí)劣。 但在多目標(biāo)情況下，問(wèn)題卻不那么單純了。例如，有兩個(gè)目標(biāo)f1(X)，f2(X),希望它們都越大越好。下圖列出在這兩個(gè)目標(biāo)下共有8個(gè)解的方案。其中方案1，2，3，4稱為劣解，因?yàn)樗鼈冊(cè)趦蓚€(gè)目標(biāo)值上都比方案5差，是可以淘汰的解。而方案5，6，7，8是非劣解（或稱為有效解，滿意解），因?yàn)檫@些解都不能輕易被淘

3、汰掉，它們中間的一個(gè)與其余任何一個(gè)相比，總有一個(gè)指標(biāo)更優(yōu)越，而另一個(gè)指標(biāo)卻更差。,一、解的特點(diǎn),二、模型結(jié)構(gòu),多目標(biāo)決策問(wèn)題包含有三大要素：目標(biāo)、方案和決策者。 在多目標(biāo)決策問(wèn)題中，目標(biāo)有多層次的含義。從最高層次來(lái)看，目標(biāo)代表了問(wèn)題要達(dá)到的總目標(biāo)。如確定最滿意的投資項(xiàng)目、選擇最滿意的食品。從較低層次來(lái)看，目標(biāo)可看成是體現(xiàn)總目標(biāo)得以實(shí)現(xiàn)的各個(gè)具體的目標(biāo)，如投資項(xiàng)目的盈利要大、成本要低、風(fēng)險(xiǎn)要??；目標(biāo)也可看成衡量總目標(biāo)得以實(shí)現(xiàn)的各個(gè)準(zhǔn)則，如食品的味道要好，質(zhì)量要好，花費(fèi)要少。 多目標(biāo)決策問(wèn)題中的方案即為決策變量，也稱為多目標(biāo)問(wèn)題的解。備選方案即決策問(wèn)題的可行解。在多目標(biāo)決策中，有些問(wèn)題的方案是有限

4、的，有些問(wèn)題 的方案是無(wú)限的。方案有其特征或特性，稱之為屬性。,為決策變量,如對(duì)于求極大(max)型，其各種解定義如下： 絕對(duì)最優(yōu)解：若對(duì)于任意的X，都有F(X*) F(X); 有效解：若不存在X，使得 F(X*) F(X); 弱有效解：若不存在X，使得F(X*) F(X)。,多目標(biāo)決策的數(shù)學(xué)模型,絕對(duì)最優(yōu)解,不存在絕對(duì)最優(yōu)解的情況,設(shè)方案的效用是目標(biāo)屬性的函數(shù)：,并設(shè)：,且各個(gè)方案的效用函數(shù)分別為：,則多目標(biāo)優(yōu)選模型的結(jié)構(gòu)可表示如下：,多目標(biāo)決策的效用數(shù)學(xué)模型,16.2 多目標(biāo)決策的求解,一、主要目標(biāo)法 二、線性加權(quán)和法 三、平方加權(quán)和法 四、理想點(diǎn)法,一、主要目標(biāo)法,在有些多目標(biāo)決策問(wèn)題中

5、，各種目標(biāo)的重要性程度往往不一樣。其中一個(gè)重要性程度最高和最為關(guān)鍵的目標(biāo)，稱之為主要目標(biāo)法。其余的目標(biāo)則稱為非主要目標(biāo)。,例如，在上述多目標(biāo)問(wèn)題中，假定f1(x)為主要目標(biāo)，其余p-1個(gè)為非主要目標(biāo)。這時(shí)，希望主要目標(biāo)達(dá)到極大值，并要求其余的目標(biāo)滿足一定的條件，即：,例1：某工廠在一個(gè)計(jì)劃期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，各產(chǎn)品都要消耗A，B，C三種不同的資源。每件產(chǎn)品對(duì)資源的單位消耗、各種資源的限量以及各產(chǎn)品的單位價(jià)格、單位利潤(rùn)和所造成的單位污染如下表。假定產(chǎn)品能全部銷售出去，問(wèn)每期怎樣安排生產(chǎn)，才能使利潤(rùn)和產(chǎn)值都最大，且造成的污染最??？,解：?jiǎn)栴}的多目標(biāo)模型如下：,對(duì)于上述模型的三個(gè)目標(biāo)，工廠確定利

6、潤(rùn)最大為主要目標(biāo)。 另兩個(gè)目標(biāo)通過(guò)預(yù)測(cè)預(yù)先給定的希望達(dá)到的目標(biāo)值轉(zhuǎn)化為約束條件。 經(jīng)研究，工廠認(rèn)為總產(chǎn)值至少應(yīng)達(dá)到20000個(gè)單位，而污染控制在90個(gè)單位以下，即：,由主要目標(biāo)法化為單目標(biāo)問(wèn)題：,用單純形法求得其最優(yōu)解為：,在上述目標(biāo)規(guī)劃中，假定f1(X), f2(X), fp(X)具有相同的量綱,按照一定的規(guī)則分別給fk 賦予相同的權(quán)系數(shù)k，作線性加權(quán)和評(píng)價(jià)函數(shù)：,則多目標(biāo)問(wèn)題化為如下的單目標(biāo)問(wèn)題：,二、線性加權(quán)和法,二、線性加權(quán)和法,例2：求解 X=xR2|x1+2x210，x24，x10，x20 X是凸集，f1(x), f2(x), f3(x)都是X上的凸函數(shù)。,這里：,解：定義權(quán)系數(shù)w

7、k0 (k=1,2,3), 其中：w1+w2+w3=1. 構(gòu)造評(píng)價(jià)函數(shù)： 求解單目標(biāo)最優(yōu)目標(biāo)問(wèn)題： 顯然，對(duì)于不同的權(quán)系數(shù)，最優(yōu)解x*(w)是不同的，但是它們都是原多目標(biāo)問(wèn)題的非劣解，下面給出幾組權(quán)系數(shù)及其對(duì)應(yīng)的最優(yōu)解（表1）。,表1 線性加權(quán)法的最優(yōu)解,可以證明，這個(gè)問(wèn)題的全部非劣解為：,其中：,二、線性加權(quán)和法,線性加權(quán)和法中權(quán)系數(shù)確定方法： 1) 法 2) 法,1) 法,先對(duì)P個(gè)分量 fk(x)分別求極值(k=1,2,P)。假設(shè)得到P個(gè)相應(yīng)的極值點(diǎn)xk (k=1,2,P)，令：,然后把這個(gè)P個(gè)極值點(diǎn)分別代入評(píng)價(jià)函數(shù)U(x)中，得到P個(gè)方程：,其中：是待定常數(shù)，由此可以解出權(quán)系數(shù)。,例3：

8、 用法求本節(jié)例2的權(quán)系數(shù)。,從表1知，3個(gè)單目標(biāo)分量單獨(dú)求極小化，所得3個(gè)極小點(diǎn)是：,將3個(gè)極小點(diǎn)依次代入目標(biāo)函數(shù)U(x)后，可以構(gòu)造線性方程組如下：,不難解出，這個(gè)方程組有唯一解：,其相應(yīng)的線性加權(quán)和問(wèn)題（P2）的最優(yōu)解為： ， 它也是多目標(biāo)問(wèn)題（P0）的非劣解，這時(shí)：,2) 法,化為單目標(biāo)決策問(wèn)題：,適用條件：fk*0。,多目標(biāo)決策問(wèn)題：,其中，,三、平方加權(quán)和法,先求各分量的最優(yōu)值：,再分別賦以權(quán)系數(shù)wk (k=1,2,.,P)，作平方加權(quán)和評(píng)價(jià)函數(shù)：,則多目標(biāo)問(wèn)題化為如下的單目標(biāo)問(wèn)題：,意義：目標(biāo)fk(x)與規(guī)定值fk*相差盡量?。╧=1, 2, , P）。,四、理想點(diǎn)法,則稱：,為理

9、想點(diǎn)。,若所有xk都相同，記為 x*，則x*就是所求的多目標(biāo)決策問(wèn)題的最優(yōu)解； 若不然，則考慮求解下面的單目標(biāo)決策問(wèn)題：,先求各分量的最優(yōu)值：,例4：設(shè)有多目標(biāo)決策問(wèn)題,解：1. 先求各分量的最優(yōu)值，得：,2. 構(gòu)造目標(biāo)函數(shù)：,3. 用理想點(diǎn)法化為單目標(biāo)決策問(wèn)題,16.3 步驟法(STEM法),STEM法，它是英文“Step Method”的縮寫。這個(gè)方法是一種迭代方法。 它和目的規(guī)劃法不同，在求解過(guò)程中的每一步，分析人和決策人之間都有對(duì)話。分析人把分析的結(jié)果告訴決策人，并征求他的意見。 如果決策人認(rèn)為滿意，則迭代終止； 如果決策人認(rèn)為不夠滿意，則分析人根據(jù)他的意見再重復(fù)計(jì)算，去改進(jìn)他的結(jié)果。

10、 由于它是逐步進(jìn)行的，故稱步驟法。,設(shè)有多目標(biāo)線性規(guī)劃問(wèn)題：,其中：,STEM法的求解步驟：,分別求解k個(gè) 單目標(biāo)線性規(guī)劃問(wèn)題：,得到的最優(yōu)解記為x(i)，其相應(yīng)的目標(biāo)函數(shù)值記為fi*（i=1, 2, , k），并x(i)代入其它目標(biāo)函數(shù)：,結(jié)果可列表給出（稱為支付表）。,步驟1：,支付表（ STEM法）,求權(quán)系數(shù)：從支付表中得到,為找出目標(biāo)值的偏差以及消除不同目標(biāo)值的量綱不同的問(wèn)題，進(jìn)行如下處理：,歸一化后得權(quán)系數(shù)：,步驟2：,求解：,（使目標(biāo)與理想值的最大加權(quán)偏差最?。?該線性規(guī)劃問(wèn)題的最優(yōu)解記為x0 。,步驟3：,將x0 和相應(yīng)的目標(biāo)值,交給決策者判斷。,決策者把這些目標(biāo)值與理想值進(jìn)行比

11、較后，若認(rèn)為滿意了，則可停止計(jì)算； 若認(rèn)為相差太遠(yuǎn)，則考慮適當(dāng)修正 。如：考慮對(duì)第r個(gè)目標(biāo)讓一點(diǎn)步，降低一點(diǎn)目標(biāo)值fr 。,步驟4：,求解：,求得解后，再與決策者對(duì)話，如此重復(fù)，直至決策者認(rèn)為滿意了為止。,步驟5：,例5：某公司考慮生產(chǎn)甲、乙兩種太陽(yáng)能電池，生產(chǎn)過(guò)程會(huì)在空氣中引起放射性污染，因此決策者有兩個(gè)目標(biāo)：極大化利潤(rùn)與極小化總的放射性污染。已知在一個(gè)生產(chǎn)周期內(nèi)，每單位甲產(chǎn)品的收益是1元，每單位乙產(chǎn)品的收益是3元；每單位甲產(chǎn)品的放射性污染是1.5單位，每單位乙產(chǎn)品的放射性污染是1單位，由于機(jī)器能力（小時(shí)）、裝配能力（人時(shí)）和可用的原材料（單位）的限制，約束條件是（ x1、x2分別為甲、乙產(chǎn)

12、品的產(chǎn)量）：,例5：,該問(wèn)題的目標(biāo)函數(shù)為：,該問(wèn)題的約束條件為：,例5：,步驟1：先分別求解,得： x(1)=(7.25, 12.75)T， x(2)=(0, 0)T f1*=45.5， f2*=0,例5：,步驟1：得到如下支付表,例5：,步驟2：求權(quán)系數(shù)。從支付表中得到：,歸一化后得權(quán)系數(shù)：,步驟3：求解,最優(yōu)解為x0=(0, 9.57)T, f1(x0)=28.71, f2(x0)=-9.57,例5：,步驟5：修改約束集,求解得x1=(0, 10)T, f1(x1)=30, f2(x0)=-10。 若決策者認(rèn)為滿意，停止迭代。,例5：,步驟4：將x0=(0, 9.57)T, f1(x0)=

13、28.71, f2(x0)=-9.57 交給決策者判斷。,決策者將其與理想值（45.5, 0）進(jìn)行比較后，認(rèn)為f2 是滿意的，但利潤(rùn)太低。且認(rèn)為可以接受污染值為10個(gè)單位。,16.4 目標(biāo)規(guī)劃方法,目標(biāo)規(guī)劃是求解多目標(biāo)線性規(guī)劃的方法之一。 目標(biāo)規(guī)劃的基本方法： 對(duì)每一個(gè)目標(biāo)函數(shù)引進(jìn)一個(gè)期望值； 引入正、負(fù)偏差變量，表示實(shí)際值與期望值的偏差，并將目標(biāo)函數(shù)轉(zhuǎn)化為約束條件，與原有約束條件構(gòu)成新的約束條件組； 引入目標(biāo)的優(yōu)先等級(jí)和權(quán)系數(shù)，構(gòu)造新的單一的目標(biāo)函數(shù)，將多目標(biāo)問(wèn)題轉(zhuǎn)化為單目標(biāo)問(wèn)題求解。,例6：某廠生產(chǎn)甲、乙兩種產(chǎn)品，每件產(chǎn)品的單位利潤(rùn)、所消耗的原材料及設(shè)備工時(shí)、材料和設(shè)備工時(shí)的限額如下表所示

14、。,決策者根據(jù)市場(chǎng)需求等一系列因素，提出下列目標(biāo)（依重要程度排列）： 首要目標(biāo)是保證甲、乙產(chǎn)品的產(chǎn)量盡可能接近。 盡可能充分利用工時(shí)，但又不希望加班； 確保達(dá)到計(jì)劃利潤(rùn)30元。,試對(duì)廠家生產(chǎn)作出決策分析。設(shè)甲、乙產(chǎn)品的產(chǎn)量分別為x1、x2件。,該問(wèn)題的目標(biāo)函數(shù)為：,該問(wèn)題的約束條件為：,1)目標(biāo)函數(shù)的期望值ek 對(duì)于多目標(biāo)線性規(guī)劃的每一個(gè)目標(biāo)函數(shù)值Zk(k=1, 2, , K)，根據(jù)實(shí)際情況和決策者的希望，確定一個(gè)期望值ek 。 在例6中: 乙產(chǎn)品與甲產(chǎn)品產(chǎn)量之差的目標(biāo)值可定為0； 生產(chǎn)工時(shí)的目標(biāo)值為26（工時(shí)）； 利潤(rùn)的目標(biāo)值為30（元）。,16.4 目標(biāo)規(guī)劃方法,2、正負(fù)偏差變量 對(duì)每一個(gè)

15、目標(biāo)函數(shù)值，分別引入正、負(fù)偏差變量：,正負(fù)偏差變量分別表示實(shí)際目標(biāo)值超過(guò)和低于期望值的數(shù)值。 引入偏差變量之后，目標(biāo)就變成了約束條件，成為約束條件組的一部分。,16.4 目標(biāo)規(guī)劃方法,在例6中，令： d1+, d1-分別表示乙產(chǎn)品與甲產(chǎn)品產(chǎn)量之差超過(guò)和達(dá)不到目標(biāo)值的偏差變量； d2+, d2-分別表示生產(chǎn)工時(shí)超過(guò)和達(dá)不到目標(biāo)值的偏差變量； d3+, d3-分別利潤(rùn)超過(guò)和達(dá)不到目標(biāo)值的偏差變量； 則三個(gè)目標(biāo)可化為含有偏差變量的約束條件：,16.4 目標(biāo)規(guī)劃方法,3、優(yōu)先因子（優(yōu)先等級(jí)）和權(quán)系數(shù) 如何區(qū)別不同目標(biāo)的主次輕重？ 凡要求第一位達(dá)到的目標(biāo)賦于優(yōu)先因子P1，次位的目標(biāo)賦于優(yōu)先因子P2，并規(guī)

16、定PkPk+1（表示Pk比Pk+1有更大的優(yōu)先權(quán)，Pk+1級(jí)目標(biāo)是在保證Pk 級(jí)目標(biāo)實(shí)現(xiàn)的基礎(chǔ)上才能考慮的）（k1,2，K） 為區(qū)別具有相同優(yōu)先因子的兩個(gè)目標(biāo)的差別，可分別賦于它們不同的權(quán)系數(shù)j 優(yōu)先等級(jí)及權(quán)數(shù)的賦值由決策者確定。,16.4 目標(biāo)規(guī)劃方法,4、達(dá)成函數(shù)(準(zhǔn)則函數(shù))：目標(biāo)規(guī)劃模型的目標(biāo)函數(shù)。 準(zhǔn)則函數(shù)由各目標(biāo)約束的正、負(fù)偏差變量及相應(yīng)的優(yōu)先因子和權(quán)系數(shù)構(gòu)造而成。 注：目標(biāo)規(guī)劃模型的目標(biāo)函數(shù)是對(duì)各目標(biāo)的偏差的綜合（將多目標(biāo)化為單目標(biāo)），在目標(biāo)函數(shù)中不包含原決策變量，且一定是極小型的（偏差最?。?16.4 目標(biāo)規(guī)劃方法,4、達(dá)成函數(shù)(準(zhǔn)則函數(shù)),當(dāng)每一目標(biāo)值確定后，決策者的要求是偏

17、差變量盡可能小，因此其目標(biāo)函數(shù)只能是極小形式，具體有以下三種基本形式：,2）要求不超過(guò)目標(biāo)值(正偏差應(yīng)盡可能小),3）要求不低于目標(biāo)值(負(fù)偏差應(yīng)盡可能小),1）要求恰好達(dá)到目標(biāo)值(正、負(fù)偏差都要盡可能小),在例6中： 首要目標(biāo)是保證乙產(chǎn)品的產(chǎn)量大于甲產(chǎn)品產(chǎn)量，賦于優(yōu)先因子P1，目標(biāo)為d1-和d2都盡可能??； 次級(jí)目標(biāo)是生產(chǎn)工時(shí)恰好達(dá)到目標(biāo)值，賦于優(yōu)先因子P2，目標(biāo)為d2-和d2都要??； 最后的目標(biāo)是利潤(rùn)不低于30元，賦于優(yōu)先因子P3，目標(biāo)為d3-盡可能小。 因此，可構(gòu)造準(zhǔn)則函數(shù)如下：,16.4 目標(biāo)規(guī)劃方法,例6：目標(biāo)規(guī)劃模型,線性規(guī)劃 vs. 目標(biāo)規(guī)劃,目標(biāo)規(guī)劃的一般模型,（1）假設(shè)決策變量

18、； （2）建立約束條件； （3）建立各個(gè)目標(biāo)函數(shù)； （4）確定各目標(biāo)期望值，引入偏差變量，將目標(biāo)函數(shù)化為約束方程； （5）確定各目標(biāo)優(yōu)先級(jí)別和權(quán)系數(shù)，構(gòu)造準(zhǔn)則函數(shù)。,目標(biāo)規(guī)劃的建模步驟,例7(10.2): 圖解法-目標(biāo)規(guī)劃,某車間生產(chǎn)甲、乙兩種產(chǎn)品，產(chǎn)量分別為x1和x2，產(chǎn)品甲每單位需2個(gè)單位的勞動(dòng)力和3個(gè)單位原料，利潤(rùn)為2；生產(chǎn)每單位產(chǎn)品乙需3個(gè)單位勞動(dòng)力和1.5個(gè)單位原料，利潤(rùn)為3。在下一計(jì)劃期間車間有12單勞動(dòng)力12單位原料。假定車間主任有如下目標(biāo)： 利潤(rùn)至少為6個(gè)單位； 兩種產(chǎn)品產(chǎn)量經(jīng)盡可能保持x1 : x2 = 3 : 2； 勞動(dòng)力充分利用（不允許加班）。,解答1: 線性規(guī)劃,解答2

19、：目標(biāo)規(guī)劃,利潤(rùn)是目標(biāo)函數(shù)中的第一優(yōu)先級(jí)，因此用d1表示利潤(rùn)偏差；因?yàn)槔麧?rùn)可以超過(guò)目的值，正偏差d1+可以大于0，取w1+ =0，使不在目標(biāo)函數(shù)中出現(xiàn)；負(fù)偏差d1-則是越小越好，把它作為第一優(yōu)先級(jí)放到目標(biāo)函數(shù)中。 產(chǎn)量比例屬于第二優(yōu)先級(jí)，用d2表示產(chǎn)量比例偏差，由于正、負(fù)偏差都不好，要將d2+和d2-同時(shí)加入目標(biāo)函數(shù)中。 第三個(gè)目的是充分利用勞動(dòng)力，因此用d3表示勞動(dòng)力偏差，因?yàn)椴辉试S加班，勞動(dòng)力不能出現(xiàn)正偏差，即d3+ 0，所以約束條件和目標(biāo)函數(shù)中均無(wú)d3+出現(xiàn)； d3-則作為第三個(gè)優(yōu)先級(jí)放入約束條件和目標(biāo)函數(shù)中。 決策人未對(duì)原材料提任何要求，但是按常理， d4作為原材料偏差，與勞動(dòng)力一樣，只會(huì)出現(xiàn)負(fù)偏差d4- ，正偏差d4+ 0。,解答2:目標(biāo)規(guī)劃（續(xù)1）,解答2:目標(biāo)規(guī)劃（續(xù)2）,例8（10.3）：圖解法,例8（10.3）：(續(xù)上例) 由于上面的例子中數(shù)據(jù)選擇比較特殊，決策人的所有目的均可滿足；為了更好地說(shuō)明問(wèn)題，把已知條件中產(chǎn)品甲利潤(rùn)改為4，其余均不變；車間主任的目的改為：最低利潤(rùn)12單位；產(chǎn)量比例為1，即x1x2；充分利用原料。,解:目的規(guī)劃,利潤(rùn)是目標(biāo)函數(shù)中的第一優(yōu)先級(jí)，因此用d1表示利潤(rùn)偏差；因?yàn)槔麧?rùn)可以超過(guò)目的值，正偏差d1+可以大于