第二章多目的規劃

〔MultipleObjectiveProgramming〕一、多目的決策問題實例干部評價－德、才兼備教師提升－教學、科研、論文等購買冰箱－價錢、質量、耗電、品牌等球員選擇－技術、體能、閱歷、心思找對象－容貌、學歷、氣質、家庭情況§1多目的決策簡介二、多目的決策與多目的規劃多目的決策多目的規劃〔MultipleObjectiveProgramming，決策變量延續〕多準那么決策〔MultipleCriteriaDecisionMaking，決策變量離散，即有限方案〕§1多目的決策簡介三、多目的決策與單目的決策區別點評價與向量評價 單目的：方案dj←評價值f(dj) 多目的：方案dj←評價向量(f1(dj)，f2(dj)…，fp(dj))全序與半序:方案di與dj之間 單目的問題:di<dj;di=dj;di>dj 多目的問題：除了這三種情況之外,還有一種情況 是不可比較大小決策者偏好：多目的決策過程中，反映決策者對 目的的偏好。§1多目的決策簡介解概念區別單目的決策的解只需一種〔絕對〕最優解;多目的決策的解有下面三種情況：絕對最優解d1807588d2758185d3767889d5787486d4858292絕對最優解數學外語專業解的類型解概念區別單目的決策的解只有一種〔絕對〕最優解;多目的決策的解有下面三種情況：d1807588有效解d2758185有效解d3767889有效解劣解d4787486數學外語專業解的類型絕對最優解劣解〔如d4劣于d1〕有效解(pareto解)——非劣解§2多目的規劃模型及其解的概念一、多目的規劃舉例例1：【喜糖問題】設市場上有甲級糖及乙級糖，單價分別為4元/斤及2元/斤。今要籌辦一樁喜事。“籌備小組〞方案總破費不超越40元，糖的總斤數不少于10斤，甲級糖不少于5斤。問如何確定最正確的采購方案。

約束條件：決策變量：甲級糖數量為x1，乙級糖數量為x2§2多目的規劃模型及其解的概念目的函數：何為最正確？〔1〕總破費最小：minf1(x1,x2)=4x1+2x2〔2〕糖的總數量最大：maxf2(x1,x2)=x1+x2〔3〕甲級糖的數量最大：maxf3(x1,x2)=x1多目的規劃問題§2多目的規劃模型及其解的概念例2【投資決策問題】某投資開發公司擁有總資金A萬元，今有n(≥2)個工程可供選擇。設投資第i(i=1,…,n)個工程要用資金ai萬元，估計可得到收益bi萬元。問應如何運用總資金A萬元，才干得到最正確的經濟效益？1，投資第i個工程0，不投資第i個工程解：令xi=約束條件：§2多目的規劃模型及其解的概念目的函數：何為最正確的經濟效益？〔1〕收益最大：〔2〕投資最少：多目的0-1規劃問題§2多目的規劃模型及其解的概念二、多目的規劃的模型決策變量：目的函數：…約束條件：向量數學規劃(VectorMathematicalProgramming)§2多目的規劃模型及其解的概念多目的規劃模型的向量表達方式記：那么模型為：或§2多目的規劃模型及其解的概念一、多目的規劃舉例二、多目的規劃的模型三、多目的規劃解的概念§2多目的規劃模型及其解的概念三、多目的規劃解的概念§2多目的規劃模型及其解的概念定義1設X*∈R，假設對恣意X∈R，均有F(X*)≦F(X)，那么稱X*為問題〔VMP〕的絕對最優解。其全體記為R*ab。0f1(x)f2(x)x絕對最優解表示圖x*f注：絕對最優解往往不存在！§2多目的規劃模型及其解的概念定義2設X0∈R，假設存在另一個可行解X1∈R，有F(X1)≤F(X0)，那么稱可行解X0相對于X1來說是劣解。注：決策中，劣解不會被思索！x0f1(x)f2(x)x1*Rpa*x2*f定義3設∈R，假設不存在X∈R，使F(X)≤F()，那么稱為問題的非劣解，又稱有效解，或Pareto解。其全體記為。§2多目的規劃模型及其解的概念定義4設∈R，假設不存在X∈R，使F(X)<F()，那么稱為問題的弱有效解。其全體記為。注：有效解必是弱有效解。x0Rwp*ff1(x)f2(x)§2多目的規劃模型及其解的概念f20f1ABCDE劣解與有效解兩個目的的最大化問題：§2多目的規劃模型及其解的概念多目的規劃——解的關系定理1，其中為單目的fi(X)上最優點集合。定理20Rwp*ff1(x)f2(x)xR1*R2*Rpa*=Rab*§2多目的規劃模型及其解的概念多目的規劃——解的關系定理3定理4§2多目的規劃模型及其解的概念多目的規劃——解的關系例1以下圖中，R1*=｛x1｝，R2*=｛x2｝，x0f1(x)f2(x)x1Rpa*x2f§2多目的規劃模型及其解的概念多目的規劃——解的關系

R3*Rp=3Rab*=φp=3Rab*≠φRR1*R2*RpaRwp*Rab*=Rpa*R1*R2*R3**§1多目的決策簡介§2多目的規劃模型及其解的概念§3多目的規劃的解法多目的規劃§3多目的規劃的解法求：有效解或弱有效解其中

方法分類評價函數法目的排序法預備任務：目的函數規范化一、評價函數法:§3多目的規劃的解法§3多目的規劃的解法§3多目的規劃的解法§3多目的規劃的解法一、評價函數法1.線性加權和法2.理想點法3.目的規劃法二、目的排序法§3多目的規劃的解法三種§3多目的規劃的解法§3多目的規劃的解法確定權系數常用方法：特爾菲法、層次分析法、α-法α-法的步驟〔以兩個目的為例〕：U［F(X)］=α1f1(X)+α2f2(X)(1)求解單目的優化問題(問題一)，記(問題二)，記§3多目的規劃的解法〔2〕α-方法的出發點：U［F(X1)］=U［F(X2)］

(3)求解得X*§3多目的規劃的解法α-方法的幾何意義：目的值空間0f2f21f22AU*=minUf11f12f1CB〔1〕平行直線簇α1f1+α2f2=c；〔2〕同一條直線上X1與X2有一樣的評價值，即有U［F(X1)］=U［F(X2)］。§3多目的規劃的解法例設有試用α-法求解。解：求解單目的優化問題，得求解LP§3多目的規劃的解法一、評價函數法1.線性加權和法〔α-法確定權系數〕2.理想點法3.目的規劃法二、目的排序法§3多目的規劃的解法2.理想點法根本思想：X的評價向量F(X)=(f1(X),f2(X),……,fp(X))越接近理想點越好。理想點：普通指由各單目的最優值組成的p維點0f1f2F(X)§3多目的規劃的解法理想點法的步驟：〔1〕求理想點。求解p個單目的最優化問題得理想點：〔2〕檢驗理想點。絕對最優點，那么輸出絕對最優解，，求解終了。否那么，轉〔3〕。§3多目的規劃的解法理想點法的步驟：〔3〕作評價函數。〔4〕求解Note:上述評價函數是嚴厲增函數，故按其求得的解是(VMP)的有效解。§3多目的規劃的解法例：設f1(X)=-3x1+2x2，f2(X)=4x1+3x2都要務虛現最大，約束集為R＝｛X|2x1+3x2≤18，2x1+x2≤10，x1，x2≥0，X∈R2｝，試用理想點法求解。解：先分別求解兩個單目的問題X(1)=(0,6),f1*=12；X(2)=(3,4)，f2*=24理想點F*=(f1*,f2*)=(12,24)評價函數X*=(0.53,5.65)，f1*=9.72,f2*=19.06。§3多目的規劃的解法一、評價函數法1.線性加權和法〔α-法確定權系數〕2.理想點法3.目的規劃法二、目的排序法3目的規劃法

〔GoalProgramming〕是求解多目的規劃的一種常用方法。該方法不思索對各個目的進展極小化或極大化，而是希望在約束條件的限制下，每一目的盡能夠地接近于事先給定的目的值。〔一〕目的規劃的思想例：某工廠消費Ⅰ、Ⅱ兩種產品，有關數據如下表：ⅠⅡ資源量原材料2111設備1210利潤810決策者在原資料供應受嚴厲限制的根底上，思索盡量滿足如下條件：〔1〕首先，產品Ⅱ的產量不低于產品Ⅰ的產量；〔2〕其次，充分利用設備有效臺時，不加班；〔3〕再次，利潤額不小于56元。〔二〕目的規劃的數學模型〔1〕在每個目的fi(X)上預先確定一個希望到達的目的值，得一目的值向量分析：〔2〕構造評價函數〔3〕多目的決策問題單目的問題〔其中R為問題的可行域〕〔4〕為了求解(3)，引入類偏向變量負偏向正偏向可以證明〔3〕等價于目的約束〔軟約束〕絕對約束〔硬約束〕實踐問題中：①各目的可賦于不同的優先因子Pj；②一樣優先因子的兩個目的的差別，可分別賦于它們不同的權系數ωij于是得到目的規劃模型：目的規劃模型的特點：〔1〕目的函數都是最小化，只需偏向變量和優先因子〔不含普通決策變量〕；〔2〕約束條件中既可包含目的約束，還可包含絕對約束；〔3〕目的約束均為等式；且普通在一個約束中同時含有正、負偏向變量；另外，根據決策者的不同要求，目的函數有三種根本方式：〔2〕要求超越目的值，評價函數為〔1〕要求恰好到達目的值，評價函數為〔3〕要求不超越目的值，評價函數為〔三〕目的規劃建模舉例例1：某工廠消費Ⅰ、Ⅱ兩種產品，有關數據如下表：ⅠⅡ資源量原材料2111設備1210利潤810決策者在原資料供應受嚴厲限制的根底上，思索盡量滿足如下條件：〔1〕首先，產品Ⅱ的產量不低于產品Ⅰ的產量；〔2〕其次，充分利用設備有效臺時，不加班；〔3〕再次，利潤額不小于56元。例1：某工廠消費Ⅰ、Ⅱ兩種產品，有關數據如下表：ⅠⅡ資源量原材料2111設備1210利潤810決策者在原資料供應受嚴厲限制的根底上思索：〔1〕首先，產品Ⅱ的產量不低于產品Ⅰ的產量；〔2〕其次，充分利用設備有效臺時，不加班；〔3〕再次，利潤額不小于56元。有一紡織廠消費尼龍布和棉布，平均消費才干都是1km/h，工廠消費才干為每周80h。根據市場預測，下周最大銷售量為：尼龍布為70km，棉布45km。尼龍布利潤為2.5元/m，棉布利潤為1.5元/m。工廠指點的管理目的如下：P1：保證職工正常上班，防止開工缺乏；P2：盡量到達最大銷售量；P3：盡量減少加班時間，限制加班時間不得超越10h。解：設決策變量x1、x2分別表示尼龍布和棉布的下周方案產量例2〔P100例4.6〕〔四〕目的規劃的求解〔1〕圖解法先思索絕對約束；再思索目的約束，并令目的約束中的偏向變量為0，作直線。①d1-d1+d2-d2+d3-d3+CBADHGEFx1x2O③②Step1P1→△OBCStep2P2→線段EDStep3P3→目的規劃的解：線段GD.其中，G(2,4),D(10/3,10/3)注：該例求得最優解，且Z*=0.但大多問題能夠無法滿足一切約束，此時求稱心解。例：求解目的規劃①d4-d2-d2+d3-d3+CBADHGEF③②x1x2Od1+d1-d4+④分析：1〕目的P1,P2→四邊形ABCD；2〕d3-的權系數大于d4-，故優先思索mind3-→四邊形ABEF;3)四邊形ABEF無法滿足d4-=0，應選取E為稱心解，使d4-盡量小。〔2〕目的規劃的單純形法與普通單純形法的區別：〔1〕最優性準那么：一切檢驗數≥0；〔2〕檢驗數的正負，優先取決于P1的系數，其次P2……。〔3〕確定進基變量時，其在一切更高級目的函數下的檢驗數為0，使低級目的上的進基不