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

運(yùn)籌學(xué)多目標(biāo)規(guī)劃演示文稿目前一頁\總數(shù)五十七頁\編于五點(diǎn)運(yùn)籌學(xué)多目標(biāo)規(guī)劃目前二頁\總數(shù)五十七頁\編于五點(diǎn)一、多目標(biāo)決策問題實(shí)例干部評估－德、才兼?zhèn)浣處煏x升－教學(xué)、科研、論文等購買冰箱－價(jià)格、質(zhì)量、耗電、品牌等球員選擇－技術(shù)、體能、經(jīng)驗(yàn)、心理找對象－容貌、學(xué)歷、氣質(zhì)、家庭狀況§1多目標(biāo)決策簡介目前三頁\總數(shù)五十七頁\編于五點(diǎn)二、多目標(biāo)決策與多目標(biāo)規(guī)劃多目標(biāo)決策多目標(biāo)規(guī)劃（MultipleObjectiveProgramming，決策變量連續(xù)）多準(zhǔn)則決策（MultipleCriteriaDecisionMaking，決策變量離散，即有限方案）§1多目標(biāo)決策簡介目前四頁\總數(shù)五十七頁\編于五點(diǎn)三、多目標(biāo)決策與單目標(biāo)決策區(qū)別點(diǎn)評價(jià)與向量評價(jià) 單目標(biāo)：方案dj←評價(jià)值f(dj)

多目標(biāo)：方案dj←評價(jià)向量(f1(dj)，f2(dj)…，fp(dj))全序與半序:

方案di與dj之間 單目標(biāo)問題:di<dj;di=dj;di>dj

多目標(biāo)問題：除了這三種情況之外,還有一種情況 是不可比較大小決策者偏好：多目標(biāo)決策過程中，反映決策者對 目標(biāo)的偏好?！?多目標(biāo)決策簡介目前五頁\總數(shù)五十七頁\編于五點(diǎn)

解概念區(qū)別單目標(biāo)決策的解只有一種（絕對）最優(yōu)解;多目標(biāo)決策的解有下面三種情況：絕對最優(yōu)解d1807588d2758185d3767889d5787486d4858292絕對最優(yōu)解數(shù)學(xué)外語專業(yè)解的類型目前六頁\總數(shù)五十七頁\編于五點(diǎn)

解概念區(qū)別單目標(biāo)決策的解只有一種（絕對）最優(yōu)解;多目標(biāo)決策的解有下面三種情況：d1807588有效解d2758185有效解d3767889有效解劣解d4787486數(shù)學(xué)外語專業(yè)解的類型

絕對最優(yōu)解劣解（如d4劣于d1

）有效解(pareto解)——非劣解目前七頁\總數(shù)五十七頁\編于五點(diǎn)§2多目標(biāo)規(guī)劃模型及其解的概念一、多目標(biāo)規(guī)劃舉例例1：【喜糖問題】設(shè)市場上有甲級糖及乙級糖，單價(jià)分別為4元/斤及2元/斤。今要籌辦一樁喜事?！盎I備小組”計(jì)劃總花費(fèi)不超過40元，糖的總斤數(shù)不少于10斤，甲級糖不少于5斤。問如何確定最佳的采購方案。

約束條件：決策變量：甲級糖數(shù)量為x1，乙級糖數(shù)量為x2目前八頁\總數(shù)五十七頁\編于五點(diǎn)§2多目標(biāo)規(guī)劃模型及其解的概念目標(biāo)函數(shù)：何為最佳？（1）總花費(fèi)最?。簃inf1(x1,x2)=4x1+2x2

（2）糖的總數(shù)量最大：maxf2(x1,x2)=x1+x2

（3）甲級糖的數(shù)量最大：maxf3(x1,x2)=x1多目標(biāo)規(guī)劃問題目前九頁\總數(shù)五十七頁\編于五點(diǎn)§2多目標(biāo)規(guī)劃模型及其解的概念例2【投資決策問題】某投資開發(fā)公司擁有總資金A萬元，今有n(≥2)個(gè)項(xiàng)目可供選擇。設(shè)投資第i(i=1,…,n)個(gè)項(xiàng)目要用資金ai萬元，預(yù)計(jì)可得到收益bi萬元。問應(yīng)如何使用總資金A萬元，才能得到最佳的經(jīng)濟(jì)效益？1，投資第i個(gè)項(xiàng)目0，不投資第i個(gè)項(xiàng)目解：令

xi=約束條件：目前十頁\總數(shù)五十七頁\編于五點(diǎn)§2多目標(biāo)規(guī)劃模型及其解的概念目標(biāo)函數(shù)：何為最佳的經(jīng)濟(jì)效益？（1）收益最大：（2）投資最少：多目標(biāo)0-1規(guī)劃問題目前十一頁\總數(shù)五十七頁\編于五點(diǎn)§2多目標(biāo)規(guī)劃模型及其解的概念二、多目標(biāo)規(guī)劃的模型決策變量：目標(biāo)函數(shù)：…約束條件：目前十二頁\總數(shù)五十七頁\編于五點(diǎn)向量數(shù)學(xué)規(guī)劃(VectorMathematicalProgramming)§2多目標(biāo)規(guī)劃模型及其解的概念多目標(biāo)規(guī)劃模型的向量表達(dá)形式記：則模型為：或目前十三頁\總數(shù)五十七頁\編于五點(diǎn)§2多目標(biāo)規(guī)劃模型及其解的概念一、多目標(biāo)規(guī)劃舉例二、多目標(biāo)規(guī)劃的模型三、多目標(biāo)規(guī)劃解的概念目前十四頁\總數(shù)五十七頁\編于五點(diǎn)§2多目標(biāo)規(guī)劃模型及其解的概念三、多目標(biāo)規(guī)劃解的概念目前十五頁\總數(shù)五十七頁\編于五點(diǎn)§2多目標(biāo)規(guī)劃模型及其解的概念定義1

設(shè)X*∈R，若對任意X∈R，均有F(X*)≦F(X)，則稱X*為問題（VMP）的絕對最優(yōu)解。其全體記為R*ab。0f1(x)f2(x)x絕對最優(yōu)解示意圖

x*f注：絕對最優(yōu)解往往不存在！目前十六頁\總數(shù)五十七頁\編于五點(diǎn)§2多目標(biāo)規(guī)劃模型及其解的概念定義2設(shè)X0∈R，若存在另一個(gè)可行解X1∈R，有F(X1)≤F(X0)，則稱可行解X0相對于X1來說是劣解。注：決策中，劣解不會(huì)被考慮！x0f1(x)f2(x)x1*

Rpa*

x2*

f定義3

設(shè)∈R，若不存在X∈R，使F(X)≤F()，則稱為問題的非劣解，又稱有效解，或Pareto解。其全體記為。目前十七頁\總數(shù)五十七頁\編于五點(diǎn)§2多目標(biāo)規(guī)劃模型及其解的概念定義4

設(shè)∈R，若不存在X∈R，使F(X)<F()，則稱為問題的弱有效解。其全體記為。注：有效解必是弱有效解。x0

Rwp*

ff1(x)f2(x)目前十八頁\總數(shù)五十七頁\編于五點(diǎn)§2多目標(biāo)規(guī)劃模型及其解的概念f20f1ABCDE劣解與有效解兩個(gè)目標(biāo)的最大化問題：目前十九頁\總數(shù)五十七頁\編于五點(diǎn)§2多目標(biāo)規(guī)劃模型及其解的概念多目標(biāo)規(guī)劃——解的關(guān)系定理1

，其中為單目標(biāo)fi(X)上最優(yōu)點(diǎn)集合。定理20

Rwp*

ff1(x)f2(x)xR1*

R2*Rpa*=Rab*目前二十頁\總數(shù)五十七頁\編于五點(diǎn)§2多目標(biāo)規(guī)劃模型及其解的概念多目標(biāo)規(guī)劃——解的關(guān)系定理3定理4目前二十一頁\總數(shù)五十七頁\編于五點(diǎn)§2多目標(biāo)規(guī)劃模型及其解的概念多目標(biāo)規(guī)劃——解的關(guān)系例1下圖中，R1*=｛x1｝，R2*=｛x2｝，

x0f1(x)f2(x)x1Rpa*

x2f目前二十二頁\總數(shù)五十七頁\編于五點(diǎn)§2多目標(biāo)規(guī)劃模型及其解的概念多目標(biāo)規(guī)劃——解的關(guān)系

R3*Rp=3Rab*=φp=3Rab*≠φRR1*R2*RpaRwp*Rab*=Rpa*R1*R2*R3**目前二十三頁\總數(shù)五十七頁\編于五點(diǎn)§1多目標(biāo)決策簡介§2多目標(biāo)規(guī)劃模型及其解的概念§3多目標(biāo)規(guī)劃的解法多目標(biāo)規(guī)劃目前二十四頁\總數(shù)五十七頁\編于五點(diǎn)§3多目標(biāo)規(guī)劃的解法

求：有效解或弱有效解其中

方法分類評價(jià)函數(shù)法目標(biāo)排序法

準(zhǔn)備工作：目標(biāo)函數(shù)規(guī)范化目前二十五頁\總數(shù)五十七頁\編于五點(diǎn)一、評價(jià)函數(shù)法:§3多目標(biāo)規(guī)劃的解法目前二十六頁\總數(shù)五十七頁\編于五點(diǎn)§3多目標(biāo)規(guī)劃的解法目前二十七頁\總數(shù)五十七頁\編于五點(diǎn)§3多目標(biāo)規(guī)劃的解法目前二十八頁\總數(shù)五十七頁\編于五點(diǎn)§3多目標(biāo)規(guī)劃的解法一、評價(jià)函數(shù)法

1.線性加權(quán)和法

2.理想點(diǎn)法

3.目標(biāo)規(guī)劃法二、目標(biāo)排序法目前二十九頁\總數(shù)五十七頁\編于五點(diǎn)§3多目標(biāo)規(guī)劃的解法三種目前三十頁\總數(shù)五十七頁\編于五點(diǎn)§3多目標(biāo)規(guī)劃的解法目前三十一頁\總數(shù)五十七頁\編于五點(diǎn)§3多目標(biāo)規(guī)劃的解法

確定權(quán)系數(shù)常用方法：特爾菲法、層次分析法、α-法

α-法的步驟（以兩個(gè)目標(biāo)為例）：

U［F(X)］=α1f1(X)+α2f2(X)

(1)求解單目標(biāo)優(yōu)化問題(問題一)，記(問題二)，記目前三十二頁\總數(shù)五十七頁\編于五點(diǎn)§3多目標(biāo)規(guī)劃的解法（2）α-方法的出發(fā)點(diǎn)：U［F(X1)］=U［F(X2)］

(3)求解得X*

目前三十三頁\總數(shù)五十七頁\編于五點(diǎn)§3多目標(biāo)規(guī)劃的解法α-方法的幾何意義：目標(biāo)值空間0f2f21f22AU*=minUf11f12f1CB（1）平行直線簇α1f1+α2f2=c

；（2）同一條直線上X1與X2有相同的評價(jià)值，即有U［F(X1)］=U［F(X2)］。

目前三十四頁\總數(shù)五十七頁\編于五點(diǎn)§3多目標(biāo)規(guī)劃的解法例設(shè)有試用α-法求解。解：求解單目標(biāo)優(yōu)化問題，得求解LP目前三十五頁\總數(shù)五十七頁\編于五點(diǎn)§3多目標(biāo)規(guī)劃的解法一、評價(jià)函數(shù)法

1.線性加權(quán)和法（α-法確定權(quán)系數(shù)）

2.理想點(diǎn)法

3.目標(biāo)規(guī)劃法二、目標(biāo)排序法目前三十六頁\總數(shù)五十七頁\編于五點(diǎn)§3多目標(biāo)規(guī)劃的解法2.理想點(diǎn)法基本思想：X的評價(jià)向量F(X)=(f1(X),f2(X),……,fp(X))越接近理想點(diǎn)越好。理想點(diǎn)：一般指由各單目標(biāo)最優(yōu)值組成的p維點(diǎn)0f1f2F(X)目前三十七頁\總數(shù)五十七頁\編于五點(diǎn)§3多目標(biāo)規(guī)劃的解法理想點(diǎn)法的步驟：（1）求理想點(diǎn)。求解p個(gè)單目標(biāo)最優(yōu)化問題

得理想點(diǎn)：（2）檢驗(yàn)理想點(diǎn)。絕對最優(yōu)點(diǎn)，則輸出絕對最優(yōu)解，，求解完畢。否則，轉(zhuǎn)（3）。目前三十八頁\總數(shù)五十七頁\編于五點(diǎn)§3多目標(biāo)規(guī)劃的解法理想點(diǎn)法的步驟：（3）作評價(jià)函數(shù)。（4）求解Note:

上述評價(jià)函數(shù)是嚴(yán)格增函數(shù)，故按其求得的解是(VMP)的有效解。目前三十九頁\總數(shù)五十七頁\編于五點(diǎn)§3多目標(biāo)規(guī)劃的解法例：設(shè)f1(X)=-3x1+2x2，f2(X)=4x1+3x2都要求實(shí)現(xiàn)最大，約束集為R＝｛X|2x1+3x2≤18，2x1+x2≤10，x1，x2≥0，X∈R2｝，試用理想點(diǎn)法求解。

解：先分別求解兩個(gè)單目標(biāo)問題X(1)=(0,6),f1*=12；X(2)=(3,4)

，f2*=24

理想點(diǎn)F*=(f1*,f2*)=(12,24)

評價(jià)函數(shù)

X*=(0.53,5.65)，f1*=9.72,f2*=19.06。

目前四十頁\總數(shù)五十七頁\編于五點(diǎn)§3多目標(biāo)規(guī)劃的解法一、評價(jià)函數(shù)法

1.線性加權(quán)和法（α-法確定權(quán)系數(shù)）

2.理想點(diǎn)法

3.目標(biāo)規(guī)劃法二、目標(biāo)排序法目前四十一頁\總數(shù)五十七頁\編于五點(diǎn)3目標(biāo)規(guī)劃法

（GoalProgramming）

是求解多目標(biāo)規(guī)劃的一種常用方法。該方法不考慮對各個(gè)目標(biāo)進(jìn)行極小化或極大化，而是希望在約束條件的限制下，每一目標(biāo)盡可能地接近于事先給定的目的值。

（一）目標(biāo)規(guī)劃的思想目前四十二頁\總數(shù)五十七頁\編于五點(diǎn)例：某工廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下表：ⅠⅡ資源量原材料2111設(shè)備1210利潤810決策者在原材料供應(yīng)受嚴(yán)格限制的基礎(chǔ)上，考慮盡量滿足如下條件：（1）首先，產(chǎn)品Ⅱ的產(chǎn)量不低于產(chǎn)品Ⅰ的產(chǎn)量；（2）其次，充分利用設(shè)備有效臺時(shí)，不加班；（3）再次，利潤額不小于56元。目前四十三頁\總數(shù)五十七頁\編于五點(diǎn)（二）目標(biāo)規(guī)劃的數(shù)學(xué)模型（1）在每個(gè)目標(biāo)fi(X)上預(yù)先確定一個(gè)希望達(dá)到的目標(biāo)值，得一目標(biāo)值向量分析：（2）構(gòu)造評價(jià)函數(shù)

（3）多目標(biāo)決策問題單目標(biāo)問題（其中R為問題的可行域）目前四十四頁\總數(shù)五十七頁\編于五點(diǎn)（4）為了求解(3)，引入類偏差變量負(fù)偏差正偏差可以證明（3）等價(jià)于目標(biāo)約束（軟約束）絕對約束（硬約束）目前四十五頁\總數(shù)五十七頁\編于五點(diǎn)實(shí)際問題中：①各目標(biāo)可賦于不同的優(yōu)先因子Pj；②相同優(yōu)先因子的兩個(gè)目標(biāo)的差別，可分別賦于它們不同的權(quán)系數(shù)ωij

于是得到目標(biāo)規(guī)劃模型：目前四十六頁\總數(shù)五十七頁\編于五點(diǎn)目標(biāo)規(guī)劃模型的特點(diǎn)：（1）目標(biāo)函數(shù)都是最小化，只有偏差變量和優(yōu)先因子（不含一般決策變量）；（2）約束條件中既可包含目標(biāo)約束，還可包含絕對約束；（3）目標(biāo)約束均為等式；且一般在一個(gè)約束中同時(shí)含有正、負(fù)偏差變量；目前四十七頁\總數(shù)五十七頁\編于五點(diǎn)

另外，根據(jù)決策者的不同要求，目標(biāo)函數(shù)有三種基本形式：

（2）要求超過目標(biāo)值，評價(jià)函數(shù)為

（1）要求恰好達(dá)到目標(biāo)值，評價(jià)函數(shù)為

（3）要求不超過目標(biāo)值，評價(jià)函數(shù)為目前四十八頁\總數(shù)五十七頁\編于五點(diǎn)（三）目標(biāo)規(guī)劃建模舉例例1：某工廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下表：ⅠⅡ資源量原材料2111設(shè)備1210利潤810決策者在原材料供應(yīng)受嚴(yán)格限制的基礎(chǔ)上，考慮盡量滿足如下條件：（1）首先，產(chǎn)品Ⅱ的產(chǎn)量不低于產(chǎn)品Ⅰ的產(chǎn)量；（2）其次，充分利用設(shè)備有效臺時(shí)，不加班；（3）再次，利潤額不小于56元。目前四十九頁\總數(shù)五十七頁\編于五點(diǎn)例1：某工廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下表：ⅠⅡ資源量原材料2111設(shè)備1210利潤810決策者在原材料供應(yīng)受嚴(yán)格限制的基礎(chǔ)上考慮：（1）首先，產(chǎn)品Ⅱ的產(chǎn)量不低于產(chǎn)品Ⅰ

的產(chǎn)量；（2）其次，充分利用設(shè)備有效臺時(shí)，不加班；（3）再次，利潤額不小于56元。目前五十頁\總數(shù)五十七頁\編于五點(diǎn)有一紡織廠生產(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）目前五十一頁\總數(shù)五十七頁\編于五點(diǎn)（四）目標(biāo)規(guī)劃的求解（1）圖解法先考慮絕對約束；再考慮目標(biāo)約束，并令目標(biāo)約束中的偏差變量為0，作直線。①d1-d1+d2-d2+d3-d3+CBADHGEFx1x2O③②

Step1P1→△OBC

Step2P2→線段ED

Step3P3→目標(biāo)規(guī)劃的解：線段GD.其中，G(2,4),D(10/3,10/3)

注：該例求得最優(yōu)解，且Z*=0.但大多問題可能無法滿足所有約束，此時(shí)求滿意解。目前五十二頁\總數(shù)五十七頁\編于五點(diǎn)例：求解目標(biāo)規(guī)劃①d4-d2-d2+d3-d3+CBADHGEF③②x1x2Od1+d1-d4+④分析：1）目標(biāo)P1,P2→四邊形ABCD；2）d3-的權(quán)系數(shù)大于d