運(yùn)籌學(xué)多目標(biāo)規(guī)劃PPT

1、第二章 多目標(biāo)規(guī)劃（Multiple Objective Programming）,一、多目標(biāo)決策問題實(shí)例,干部評(píng)估德、才兼?zhèn)?教師晉升教學(xué)、科研、論文等 購買冰箱價(jià)格、質(zhì)量、耗電、品牌等 球員選擇技術(shù)、體能、經(jīng)驗(yàn)、心理 找對(duì)象容貌、學(xué)歷、氣質(zhì)、家庭狀況,1 多目標(biāo)決策簡介,二、多目標(biāo)決策與多目標(biāo)規(guī)劃,多目標(biāo)決策,多目標(biāo)規(guī)劃 （ Multiple Objective Programming， 決策變量連續(xù)）,多準(zhǔn)則決策 （ Multiple Criteria Decision Making，決策變量離散，即有限方案）,1 多目標(biāo)決策簡介,三、多目標(biāo)決策與單目標(biāo)決策區(qū)別,點(diǎn)評(píng)價(jià)與向量評(píng)價(jià) 單目標(biāo)

2、： 方案dj 評(píng)價(jià)值f(dj) 多目標(biāo)：方案dj評(píng)價(jià)向量(f1(dj)，f2(dj)，fp(dj) 全序與半序: 方案di與dj之間 單目標(biāo)問題: didj 多目標(biāo)問題：除了這三種情況之外,還有一種情況是不可比較大小 決策者偏好：多目標(biāo)決策過程中，反映決策者對(duì)目標(biāo)的偏好。,1 多目標(biāo)決策簡介,解概念區(qū)別,單目標(biāo)決策的解只有一種（絕對(duì)）最優(yōu)解; 多目標(biāo)決策的解有下面三種情況： 絕對(duì)最優(yōu)解,解概念區(qū)別,單目標(biāo)決策的解只 有一種（絕對(duì)）最優(yōu)解; 多目標(biāo)決策的解有下面三種情況：,數(shù)學(xué),外語,專業(yè),解的類型,絕對(duì)最優(yōu)解 劣解（如d4劣于d1 ） 有效解(pareto解)非劣解,2 多目標(biāo)規(guī)劃模型及其解的

3、概念,一、多目標(biāo)規(guī)劃舉例,例1：【喜糖問題】設(shè)市場上有甲級(jí)糖及乙級(jí)糖，單價(jià)分別為4元/斤及2元/斤。今要籌辦一樁喜事?！盎I備小組”計(jì)劃總花費(fèi)不超過40元，糖的總斤數(shù)不少于10斤，甲級(jí)糖不少于5斤。問如何確定最佳的采購方案。,約束條件：,決策變量：甲級(jí)糖數(shù)量為x1，乙級(jí)糖數(shù)量為x2,2 多目標(biāo)規(guī)劃模型及其解的概念,目標(biāo)函數(shù)：何為最佳？,（1）總花費(fèi)最小： min f1(x1,x2)=4x1+2x2,（2）糖的總數(shù)量最大： max f2(x1,x2)=x1+x2,（3）甲級(jí)糖的數(shù)量最大： max f3(x1,x2)=x1,2 多目標(biāo)規(guī)劃模型及其解的概念,例2【投資決策問題】某投資開發(fā)公司擁有總資金

4、A萬元，今有n(2)個(gè)項(xiàng)目可供選擇。設(shè)投資第 i (i=1,n) 個(gè)項(xiàng)目要用資金ai 萬元，預(yù)計(jì)可得到收益bi萬元。問應(yīng)如何使用總資金A萬元，才能得到最佳的經(jīng)濟(jì)效益？,約束條件：,2 多目標(biāo)規(guī)劃模型及其解的概念,目標(biāo)函數(shù)：何為最佳的經(jīng)濟(jì)效益？,（1）收益最大：,（2）投資最少：,2 多目標(biāo)規(guī)劃模型及其解的概念,二、多目標(biāo)規(guī)劃的模型,決策變量：,目標(biāo)函數(shù)：,約束條件：,向量數(shù)學(xué)規(guī)劃(Vector Mathematical Programming),2 多目標(biāo)規(guī)劃模型及其解的概念,多目標(biāo)規(guī)劃模型的向量表達(dá)形式,記：,則模型為：,或,2 多目標(biāo)規(guī)劃模型及其解的概念,一、多目標(biāo)規(guī)劃舉例 二、多目標(biāo)規(guī)劃

5、的模型 三、多目標(biāo)規(guī)劃解的概念,2 多目標(biāo)規(guī)劃模型及其解的概念,三、多目標(biāo)規(guī)劃解的概念,2 多目標(biāo)規(guī)劃模型及其解的概念,定義1 設(shè)X*R，若對(duì)任意XR，均有F(X*)F(X)，則稱X*為問題（VMP）的絕對(duì)最優(yōu)解。其全體記為R*ab 。,0,f1(x),f2(x),x,絕對(duì)最優(yōu)解示意圖,x*,f,注：絕對(duì)最優(yōu)解往往不存在！,2 多目標(biāo)規(guī)劃模型及其解的概念,定義2 設(shè)X0R，若存在另一個(gè)可行解X1R，有F(X1) F(X0)，則稱可行解X0相對(duì)于X1來說是劣解。,注：決策中，劣解不會(huì)被考慮！,定義3 設(shè) R，若不存在XR，使F(X)F( )，則稱 為問題的非劣解，又稱有效解，或Pareto解。其

6、全體記為 。,2 多目標(biāo)規(guī)劃模型及其解的概念,定義4 設(shè) R，若不存在XR，使 F(X)F( )，則稱 為問題的弱有效解。其全體記為 。,注：有效解必是弱有效解。,2 多目標(biāo)規(guī)劃模型及其解的概念,f2,0,f1,D,E,劣解與有效解,兩個(gè)目標(biāo)的最大化問題：,2 多目標(biāo)規(guī)劃模型及其解的概念,多目標(biāo)規(guī)劃解的關(guān)系,定理1 ，其中 為單目標(biāo) fi (X) 上 最優(yōu)點(diǎn)集合。,2 多目標(biāo)規(guī)劃模型及其解的概念,多目標(biāo)規(guī)劃解的關(guān)系,定理3,定理4,2 多目標(biāo)規(guī)劃模型及其解的概念,多目標(biāo)規(guī)劃解的關(guān)系,例1 下圖中，R1*=x1，R2*=x2，,2 多目標(biāo)規(guī)劃模型及其解的概念,多目標(biāo)規(guī)劃解的關(guān)系,1 多目標(biāo)決策簡

7、介 2 多目標(biāo)規(guī)劃模型及其解的概念 3 多目標(biāo)規(guī)劃的解法,多目標(biāo)規(guī)劃,3 多目標(biāo)規(guī)劃的解法,求：有效解或弱有效解,其中,準(zhǔn)備工作：目標(biāo)函數(shù)規(guī)范化,一、評(píng)價(jià)函數(shù)法:,3 多目標(biāo)規(guī)劃的解法,3 多目標(biāo)規(guī)劃的解法,3 多目標(biāo)規(guī)劃的解法,3 多目標(biāo)規(guī)劃的解法,一、評(píng)價(jià)函數(shù)法 1. 線性加權(quán)和法 2. 理想點(diǎn)法 3. 目標(biāo)規(guī)劃法 二、目標(biāo)排序法,3 多目標(biāo)規(guī)劃的解法,三種,3 多目標(biāo)規(guī)劃的解法,3 多目標(biāo)規(guī)劃的解法,確定權(quán)系數(shù)常用方法：特爾菲法、層次分析法、-法,-法的步驟（以兩個(gè)目標(biāo)為例）： UF(X)=1f1(X)+2f2(X),3 多目標(biāo)規(guī)劃的解法,（2）-方法的出發(fā)點(diǎn)：UF(X1)=UF(X2)

8、,3 多目標(biāo)規(guī)劃的解法,-方法的幾何意義：,目標(biāo)值空間,0,f2,f21,f22,A,U*=minU,f11,f12,f1,C,B,（1）平行直線簇 1f1+2f2=c ； （2）同一條直線上X1與X2有相同的評(píng)價(jià)值，即有 UF(X1)=UF(X2)。,3 多目標(biāo)規(guī)劃的解法,例 設(shè)有,試用-法求解。,解： 求解單目標(biāo)優(yōu)化問題，得,3 多目標(biāo)規(guī)劃的解法,一、評(píng)價(jià)函數(shù)法 1. 線性加權(quán)和法 （ -法確定權(quán)系數(shù)） 2. 理想點(diǎn)法 3. 目標(biāo)規(guī)劃法 二、目標(biāo)排序法,3 多目標(biāo)規(guī)劃的解法,2. 理想點(diǎn)法,基本思想：X的評(píng)價(jià)向量F(X)=(f1(X),f2(X),fp(X) 越接近理想點(diǎn)越好。 理想點(diǎn)：一

9、般指由各單目標(biāo)最優(yōu)值組成的p維點(diǎn),0,f1,f2,F(X),3 多目標(biāo)規(guī)劃的解法,理想點(diǎn)法的步驟：,（1）求理想點(diǎn)。求解p個(gè)單目標(biāo)最優(yōu)化問題,得理想點(diǎn)：,（2）檢驗(yàn)理想點(diǎn)。絕對(duì)最優(yōu)點(diǎn)，則輸出絕對(duì)最優(yōu)解，,，求解完畢。否則，轉(zhuǎn)（3）。,3 多目標(biāo)規(guī)劃的解法,理想點(diǎn)法的步驟：,（3）作評(píng)價(jià)函數(shù)。,（4）求解,Note: 上述評(píng)價(jià)函數(shù)是嚴(yán)格增函數(shù)，故按其求得的解是(VMP)的有效解。,3 多目標(biāo)規(guī)劃的解法,例：設(shè)f1(X)=-3x1+2x2，f2(X)=4x1+3x2都要求實(shí)現(xiàn)最大，約束集為RX|2x1+3x218，2x1+x210，x1，x20，XR2，試用理想點(diǎn)法求解。,解：先分別求解兩個(gè)單目標(biāo)

10、問題,3 多目標(biāo)規(guī)劃的解法,一、評(píng)價(jià)函數(shù)法 1. 線性加權(quán)和法 （ -法確定權(quán)系數(shù)） 2. 理想點(diǎn)法 3. 目標(biāo)規(guī)劃法 二、目標(biāo)排序法,3 目標(biāo)規(guī)劃法（Goal Programming）,是求解多目標(biāo)規(guī)劃的一種常用方法。 該方法不考慮對(duì)各個(gè)目標(biāo)進(jìn)行極小化或極大化，而是希望在約束條件的限制下，每一目標(biāo)盡可能地接近于事先給定的目的值。,（一）目標(biāo)規(guī)劃的思想,例：某工廠生產(chǎn)、兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下表：,決策者在原材料供應(yīng)受嚴(yán)格限制的基礎(chǔ)上，考慮盡量滿足如下條件： （1）首先，產(chǎn)品的產(chǎn)量不低于產(chǎn)品 的產(chǎn)量； （2）其次，充分利用設(shè)備有效臺(tái)時(shí)，不加班； （3）再次，利潤額不小于56元。,（二）目標(biāo)規(guī)劃的

11、數(shù)學(xué)模型,（1）在每個(gè)目標(biāo)fi(X)上預(yù)先確定一個(gè)希望達(dá)到的目標(biāo)值，得一目標(biāo)值向量,分析：,（2）構(gòu)造評(píng)價(jià)函數(shù),（3）多目標(biāo)決策問題,單目標(biāo)問題,（其中R為問題的可行域）,（4）為了求解(3)，引入類偏差變量,負(fù)偏差,正偏差,可以證明（3）等價(jià)于,實(shí)際問題中： 各目標(biāo)可賦于不同的優(yōu)先因子Pj ； 相同優(yōu)先因子的兩個(gè)目標(biāo)的差別，可分別賦于它們不同的權(quán)系數(shù)ij,于是得到目標(biāo)規(guī)劃模型：,目標(biāo)規(guī)劃模型的特點(diǎn)： （1）目標(biāo)函數(shù)都是最小化，只有偏差變量和優(yōu)先因子（不含一般決策變量）； （2）約束條件中既可包含目標(biāo)約束，還可包含絕對(duì)約束； （3）目標(biāo)約束均為等式；且一般在一個(gè)約束中同時(shí)含有正、負(fù)偏差變量；,

12、另外，根據(jù)決策者的不同要求，目標(biāo)函數(shù)有三種基本形式：,（2）要求超過目標(biāo)值，評(píng)價(jià)函數(shù)為,（1）要求恰好達(dá)到目標(biāo)值，評(píng)價(jià)函數(shù)為,（3）要求不超過目標(biāo)值，評(píng)價(jià)函數(shù)為,（三）目標(biāo)規(guī)劃建模舉例,例1：某工廠生產(chǎn)、兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下表：,決策者在原材料供應(yīng)受嚴(yán)格限制的基礎(chǔ)上，考慮盡量滿足如下條件： （1）首先，產(chǎn)品的產(chǎn)量不低于產(chǎn)品 的產(chǎn)量； （2）其次，充分利用設(shè)備有效臺(tái)時(shí)，不加班； （3）再次，利潤額不小于56元。,例1：某工廠生產(chǎn)、兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下表：,決策者在原材料供應(yīng)受嚴(yán)格限制的基礎(chǔ)上考慮： （1）首先，產(chǎn)品的產(chǎn)量不低于產(chǎn)品 的產(chǎn)量； （2）其次，充分利用設(shè)備有效臺(tái)時(shí)，不加班； （3）

13、再次，利潤額不小于56元。,有一紡織廠生產(chǎn)尼龍布和棉布，平均生產(chǎn)能力都是1km/h，工廠生產(chǎn)能力為每周80h。根據(jù)市場預(yù)測，下周最大銷售量為：尼龍布為70km，棉布45km。尼龍布利潤為2.5元/m，棉布利潤為1.5元/m。工廠領(lǐng)導(dǎo)的管理目標(biāo)如下：P1：保證職工正常上班，避免開工不足； P2：盡量達(dá)到最大銷售量； P3：盡量減少加班時(shí)間，限制加班時(shí)間不得超過10h。,解：設(shè)決策變量x1 、x2分別表示尼龍布和棉布的下周計(jì)劃產(chǎn)量,例2（P100例4.6）,（四）目標(biāo)規(guī)劃的求解,（1）圖解法,先考慮絕對(duì)約束；再考慮目標(biāo)約束，并令目標(biāo)約束中的偏差變量為0，作直線。,d1-,d1+,d2-,d2+,d

14、3-,d3+,Step1 P1 OBC,Step2 P2 線段ED,Step3 P3 目標(biāo)規(guī)劃的解：線段GD. 其中，G(2,4), D(10/3,10/3),注：該例求得最優(yōu)解，且Z*=0. 但大多問題可能無法滿足所有約束，此時(shí)求滿意解。,例：求解目標(biāo)規(guī)劃,分析： 1）目標(biāo)P1,P2 四邊形ABCD； 2）d3-的權(quán)系數(shù)大于d4-，故優(yōu)先考慮 min d3- 四邊形ABEF; 3)四邊形ABEF無法滿足d4-=0，故選取E為滿意解，使d4-盡量小。,（2）目標(biāo)規(guī)劃的單純形法,與一般單純形法的區(qū)別： （1）最優(yōu)性準(zhǔn)則：所有檢驗(yàn)數(shù) 0； （2）檢驗(yàn)數(shù)的正負(fù)，優(yōu)先取決于P1的系數(shù)，其次P2。 （3

15、）確定進(jìn)基變量時(shí)，其在所有更高級(jí)目標(biāo)函數(shù)下的檢驗(yàn)數(shù)為0，使低級(jí)目標(biāo)上的進(jìn)基不影響所有高級(jí)目標(biāo)上已獲目標(biāo)值。,（2）目標(biāo)規(guī)劃的單純形法,步驟： 1）建立初始單純形表，在表中將檢驗(yàn)數(shù)行按優(yōu) 先因子個(gè)數(shù)列成K行，置k=1. 2）檢查該行是否存在負(fù)數(shù)，且對(duì)應(yīng)的前k-1行的系數(shù)是0。若有負(fù)數(shù)，取最小者對(duì)應(yīng)的變量為進(jìn)基變量，轉(zhuǎn)3）。若無負(fù)數(shù)，轉(zhuǎn)（5）。 3）按最小比值規(guī)則確定出基變量，當(dāng)存在兩個(gè)及以上相同的最小比值時(shí)，選取優(yōu)先級(jí)較高的為出基變量。 4）按單純形法進(jìn)行基變換運(yùn)算，得新表，轉(zhuǎn)（2）。 5）當(dāng)k=K時(shí)，算法結(jié)束，得滿意解。否則置k=k+1,轉(zhuǎn)（2）。,3 多目標(biāo)規(guī)劃的解法,一、評(píng)價(jià)函數(shù)法 1. 線性加權(quán)和法 （ -法確定權(quán)系數(shù)） 2. 理想點(diǎn)法 3. 目標(biāo)規(guī)劃法 二、目標(biāo)排序法,3 多目