運(yùn)籌學(xué)多目標(biāo)規(guī)劃..教學(xué)內(nèi)容

1、Tianjin University 運(yùn)籌學(xué)多目標(biāo)規(guī)劃運(yùn)籌學(xué)多目標(biāo)規(guī)劃.Tianjin University 二、多目標(biāo)決策與多目標(biāo)規(guī)劃二、多目標(biāo)決策與多目標(biāo)規(guī)劃多目標(biāo)決策多目標(biāo)決策多目標(biāo)規(guī)劃多目標(biāo)規(guī)劃（ Multiple Objective Programming， 決策變量連續(xù)）決策變量連續(xù)）多準(zhǔn)則決策多準(zhǔn)則決策（ Multiple Criteria Decision Making，決策變量離散，即有限方案）決策變量離散，即有限方案）1 1 多目標(biāo)決策簡介多目標(biāo)決策簡介Tianjin University 三、多目標(biāo)決策與單目標(biāo)決策區(qū)別三、多目標(biāo)決策與單目標(biāo)決策區(qū)別 點(diǎn)評(píng)價(jià)與向量評(píng)價(jià)點(diǎn)評(píng)價(jià)

2、與向量評(píng)價(jià) 單目標(biāo)：單目標(biāo)： 方案方案dj 評(píng)價(jià)值評(píng)價(jià)值f(dj) 多目標(biāo)：方案多目標(biāo)：方案dj評(píng)價(jià)向量評(píng)價(jià)向量(f1(dj)，f2(dj)，fp(dj) 全序與半序全序與半序: 方案方案di與與dj之間之間 單目標(biāo)問題單目標(biāo)問題: didj 多目標(biāo)問題：除了這三種情況之外多目標(biāo)問題：除了這三種情況之外,還有一種情況還有一種情況是不可比較大小是不可比較大小 決策者偏好：決策者偏好：多目標(biāo)決策過程中，反映決策者對(duì)多目標(biāo)決策過程中，反映決策者對(duì)目標(biāo)的偏好。目標(biāo)的偏好。1 1 多目標(biāo)決策簡介多目標(biāo)決策簡介Tianjin University 解概念區(qū)別解概念區(qū)別單目標(biāo)單目標(biāo)決策的解只有一種（絕對(duì)）最

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

4、 絕對(duì)最優(yōu)解絕對(duì)最優(yōu)解 劣解（劣解（如如d4劣于劣于d1 ） 有效解有效解(pareto解解)非劣解非劣解Tianjin University 2 2 多目標(biāo)規(guī)劃模型及其解的概念多目標(biāo)規(guī)劃模型及其解的概念一、多目標(biāo)規(guī)劃舉例一、多目標(biāo)規(guī)劃舉例例例1 1：【喜糖問題喜糖問題】設(shè)市場上有甲級(jí)糖及乙級(jí)糖，單價(jià)分別為設(shè)市場上有甲級(jí)糖及乙級(jí)糖，單價(jià)分別為4 4元元/ /斤及斤及2 2元元/ /斤。今要籌辦一樁喜事。斤。今要籌辦一樁喜事?！盎I備小組籌備小組”計(jì)劃總計(jì)劃總花費(fèi)不超過花費(fèi)不超過4040元，糖的總斤數(shù)不少于元，糖的總斤數(shù)不少于1010斤，甲級(jí)糖不少于斤，甲級(jí)糖不少于5 5斤。問如何確定最佳的采購方

5、案。斤。問如何確定最佳的采購方案。 約束條件：約束條件：決策變量：決策變量：甲級(jí)糖數(shù)量為甲級(jí)糖數(shù)量為x1，乙級(jí)糖數(shù)量為，乙級(jí)糖數(shù)量為x2121211242401050,0 xxxxxxxTianjin University 2 2 多目標(biāo)規(guī)劃模型及其解的概念多目標(biāo)規(guī)劃模型及其解的概念目標(biāo)函數(shù)：目標(biāo)函數(shù)：何為何為最佳？最佳？（1）總花費(fèi)最?。海┛偦ㄙM(fèi)最?。?min f1(x1,x2)=4x1+2x2 （2）糖的總數(shù)量最大：）糖的總數(shù)量最大： max f2(x1,x2)=x1+x2 （3）甲級(jí)糖的數(shù)量最大：）甲級(jí)糖的數(shù)量最大： max f3(x1,x2)=x1多目標(biāo)規(guī)劃問題多目標(biāo)規(guī)劃問題Tianj

6、in University 2 2 多目標(biāo)規(guī)劃模型及其解的概念多目標(biāo)規(guī)劃模型及其解的概念例例2【投資決策問題投資決策問題】某投資開發(fā)公司擁有總資某投資開發(fā)公司擁有總資金金A萬元，今有萬元，今有n(2)個(gè)項(xiàng)目可供選擇。設(shè)投資第個(gè)項(xiàng)目可供選擇。設(shè)投資第 i (i=1,n) 個(gè)項(xiàng)目要用資金個(gè)項(xiàng)目要用資金ai 萬元，預(yù)計(jì)可得到萬元，預(yù)計(jì)可得到收益收益bi萬元。問應(yīng)如何使用總資金萬元。問應(yīng)如何使用總資金A萬元，才能萬元，才能得到最佳的經(jīng)濟(jì)效益？得到最佳的經(jīng)濟(jì)效益？1， 投資第投資第i個(gè)項(xiàng)目個(gè)項(xiàng)目0，不，不投資第投資第i個(gè)項(xiàng)目個(gè)項(xiàng)目解：令解：令 xi =約束條件：約束條件： ), 1101nixAxain

7、iii（或或Tianjin University 2 2 多目標(biāo)規(guī)劃模型及其解的概念多目標(biāo)規(guī)劃模型及其解的概念目標(biāo)函數(shù)：目標(biāo)函數(shù)：何為何為最佳的經(jīng)濟(jì)效益？最佳的經(jīng)濟(jì)效益？（1）收益最大：）收益最大：（2）投資最少：）投資最少： niiinxbxxf111),(max niiinxaxxf112),(min多目標(biāo)多目標(biāo)0-1規(guī)劃問題規(guī)劃問題Tianjin University 2 2 多目標(biāo)規(guī)劃模型及其解的概念多目標(biāo)規(guī)劃模型及其解的概念二、二、多目標(biāo)規(guī)劃的模型多目標(biāo)規(guī)劃的模型決策變量：決策變量：nxx,1目標(biāo)函數(shù)：目標(biāo)函數(shù)：),(min11nxxf),(min1npxxf約束條件：約束條件： 0

8、),(0),(111nmnxxgxxgTianjin University 2 2 多目標(biāo)規(guī)劃模型及其解的概念多目標(biāo)規(guī)劃模型及其解的概念多目標(biāo)規(guī)劃模型的向量表達(dá)形式多目標(biāo)規(guī)劃模型的向量表達(dá)形式記：記：T1),(nxxX 則模型為：則模型為：T1)(,),()(XfXfXFp miXgXRi, 1, 0)( miXgXfXfip, 1, 0)()(,),(min)VMP(1或或min()(VMP)F XXR Tianjin University 2 2 多目標(biāo)規(guī)劃模型及其解的概念多目標(biāo)規(guī)劃模型及其解的概念一、多目標(biāo)規(guī)劃舉例一、多目標(biāo)規(guī)劃舉例二、多目標(biāo)規(guī)劃的模型二、多目標(biāo)規(guī)劃的模型三、多目標(biāo)規(guī)劃解

9、的概念三、多目標(biāo)規(guī)劃解的概念Tianjin University 2 2 多目標(biāo)規(guī)劃模型及其解的概念多目標(biāo)規(guī)劃模型及其解的概念三、多目標(biāo)規(guī)劃解的概念三、多目標(biāo)規(guī)劃解的概念111122211212121212 () ()(1)1(2) 1ppppiiFffEFffEFFFFipffFFFFi 先先引引進(jìn)進(jìn)一一些些記記號(hào)號(hào)，記記， ：意意味味著著向向量量的的每每個(gè)個(gè)分分量量都都要要嚴(yán)嚴(yán)格格的的小小于于向向量量對(duì)對(duì)應(yīng)應(yīng)的的分分量量。即即對(duì)對(duì)于于， ，均均有有。 ：意意味味著著向向量量的的每每個(gè)個(gè)分分量量都都要要小小于于或或等等于于向向量量對(duì)對(duì)應(yīng)應(yīng)的的分分量量。即即對(duì)對(duì)于于，0012121212121

10、2121212(3)1iiiiiipffFFFFFFipffffFFFFFF 0000， ，均均有有。 ：意意味味著著向向量量的的每每個(gè)個(gè)分分量量都都要要小小于于或或等等于于向向量量對(duì)對(duì)應(yīng)應(yīng)的的分分量量，并并且且存存在在的的某某一一個(gè)個(gè)分分量量要要嚴(yán)嚴(yán)格格的的小小于于向向量量對(duì)對(duì)應(yīng)應(yīng)的的分分量量。即即對(duì)對(duì)于于， ，均均有有，并并且且要要至至少少存存在在某某個(gè)個(gè)i(1ip)i(1ip)，有有。 可可見見，等等價(jià)價(jià)于于且且。Tianjin University 2 2 多目標(biāo)規(guī)劃模型及其解的概念多目標(biāo)規(guī)劃模型及其解的概念定義定義1 設(shè)設(shè)X*R，若對(duì)任意，若對(duì)任意XR，均有，均有F(X*)F(X)，

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

12、，使，使F(X)F( )，則稱則稱 為問題的為問題的非劣解非劣解，又稱，又稱有效解有效解，或，或Pareto解解。其全體記為其全體記為 。XXX*paRTianjin University 2 2 多目標(biāo)規(guī)劃模型及其解的概念多目標(biāo)規(guī)劃模型及其解的概念定義定義4 設(shè)設(shè) R，若不存在，若不存在XR，使，使 F(X)F( )，則稱則稱 為問題的為問題的弱有效解弱有效解。其全體記為。其全體記為 。XXX*wpR注：注：有效解必是弱有效解。有效解必是弱有效解。x0 Rwp * ff1(x)f2(x)Tianjin University 2 2 多目標(biāo)規(guī)劃模型及其解的概念多目標(biāo)規(guī)劃模型及其解的概念f20f

13、1ABCDE劣解與有效解劣解與有效解兩個(gè)目標(biāo)的最大化問題：兩個(gè)目標(biāo)的最大化問題：Tianjin University 2 2 多目標(biāo)規(guī)劃模型及其解的概念多目標(biāo)規(guī)劃模型及其解的概念多目標(biāo)規(guī)劃多目標(biāo)規(guī)劃解的關(guān)系解的關(guān)系定理定理1 ，其中，其中 為單目標(biāo)為單目標(biāo) fi (X) 上上最優(yōu)點(diǎn)集合。最優(yōu)點(diǎn)集合。 piiabRR1* *iR定理定理2RRRRwppaab *0 Rwp * ff1(x)f2(x)x R1* R2* Rpa*= Rab*Tianjin University 2 2 多目標(biāo)規(guī)劃模型及其解的概念多目標(biāo)規(guī)劃模型及其解的概念多目標(biāo)規(guī)劃多目標(biāo)規(guī)劃解的關(guān)系解的關(guān)系定理定理3*wpiRR 定

14、理定理4piiwppiiabpaabRRRRRR1*1*21 ）；（）（，則則若若 Tianjin University 2 2 多目標(biāo)規(guī)劃模型及其解的概念多目標(biāo)規(guī)劃模型及其解的概念多目標(biāo)規(guī)劃多目標(biāo)規(guī)劃解的關(guān)系解的關(guān)系例例1 下圖中，下圖中，R1*=x1，R2*=x2， 21*,xxRRwppa x0 f1(x) f2(x) x1 Rpa* x2 fTianjin University 2 2 多目標(biāo)規(guī)劃模型及其解的概念多目標(biāo)規(guī)劃模型及其解的概念多目標(biāo)規(guī)劃多目標(biāo)規(guī)劃解的關(guān)系解的關(guān)系 R3*Rp=3 Rab*=p=3 Rab*RR1*R2*RpaRwp*Rab*=Rpa*R1*R2*R3*Tia

15、njin University 1 多目標(biāo)決策簡介多目標(biāo)決策簡介2 2 多目標(biāo)規(guī)劃模型及其解的概念多目標(biāo)規(guī)劃模型及其解的概念3 多目標(biāo)規(guī)劃的解法多目標(biāo)規(guī)劃的解法多目標(biāo)規(guī)劃多目標(biāo)規(guī)劃Tianjin University 3 多目標(biāo)規(guī)劃的解法多目標(biāo)規(guī)劃的解法 求：有效解或弱有效解求：有效解或弱有效解 ,)()(iiifXfXf )(maxXffiRXi 其中其中 方法分類方法分類評(píng)價(jià)函數(shù)法評(píng)價(jià)函數(shù)法目標(biāo)排序法目標(biāo)排序法 準(zhǔn)備工作：目標(biāo)函數(shù)規(guī)范化準(zhǔn)備工作：目標(biāo)函數(shù)規(guī)范化Tianjin University 一、評(píng)價(jià)函數(shù)法一、評(píng)價(jià)函數(shù)法: :1 ()()() ( ) min ()()( )()pXRh

16、 Fh ffVMPPh F Xh FPXVMP 評(píng)評(píng)價(jià)價(jià)函函數(shù)數(shù)法法就就是是利利用用一一個(gè)個(gè)復(fù)復(fù)合合函函數(shù)數(shù): :，把把多多目目標(biāo)標(biāo)問問題題轉(zhuǎn)轉(zhuǎn)化化為為單單目目標(biāo)標(biāo)問問題題: :然然后后來來求求解解，而而單單目目標(biāo)標(biāo)問問題題的的解解法法我我們們是是熟熟知知的的。問問題題是是，用用評(píng)評(píng)價(jià)價(jià)函函數(shù)數(shù)得得到到的的的的最最優(yōu)優(yōu)解解是是否否為為原原問問題題的的有有效效解解或或弱弱有有效效解解？因因?yàn)闉槿羧暨B連弱弱有有效效解解都都不不是是，那那顯顯然然是是不不足足取取的的。3 多目標(biāo)規(guī)劃的解法多目標(biāo)規(guī)劃的解法Tianjin University *121212 ()() ()()()()pawppppph

17、 FXRXRh FEFFFEFEh Fh Fh Fh FE 下下面面我我們們將將指指出出，當(dāng)當(dāng)評(píng)評(píng)價(jià)價(jià)函函數(shù)數(shù)具具有有某某種種“單單調(diào)調(diào)性性時(shí)時(shí)”，是是可可以以保保證證（或或）的的。為為此此，先先給給出出兩兩個(gè)個(gè)定定義義： 定定義義4 4 設(shè)設(shè)是是定定義義在在上上的的函函數(shù)數(shù)，若若對(duì)對(duì)于于任任意意滿滿足足的的，均均有有：則則稱稱為為嚴(yán)嚴(yán)格格單單調(diào)調(diào)函函數(shù)數(shù)。 定定義義5 5 設(shè)設(shè)是是定定義義在在上上的的函函數(shù)數(shù)，若若對(duì)對(duì)于于任任121212 ()()()ppFFFEFEh Fh Fh F 意意滿滿足足的的，均均有有：則則稱稱為為單單調(diào)調(diào)函函數(shù)數(shù)。3 多目標(biāo)規(guī)劃的解法多目標(biāo)規(guī)劃的解法Tianji