运筹学多目标规划..

第二章多目标规划（MultipleObjectiveProgramming）TianjinUniversity一、多目标决策问题实例•干部评估－德、才兼备•教师晋升－教学、科研、论文等•购买冰箱－价格、质量、耗电、品牌等•球员选择－技术、体能、经验、心理•找对象－容貌、学历、气质、家庭状况§1多目标决策简介TianjinUniversity二、多目标决策与多目标规划多目标决策多目标规划（MultipleObjectiveProgramming，决策变量连续）多准则决策（MultipleCriteriaDecisionMaking，决策变量离散，即有限方案）§1多目标决策简介TianjinUniversity三、多目标决策与单目标决策区别•点评价与向量评价单目标：方案dj←评价值f(dj)多目标：方案dj←评价向量(f1(dj)，f2(dj)…，fp(dj))•全序与半序:方案di与dj之间单目标问题:didj;di=dj;didj多目标问题：除了这三种情况之外,还有一种情况是不可比较大小•决策者偏好：多目标决策过程中，反映决策者对目标的偏好。§1多目标决策简介TianjinUniversity•解概念区别单目标决策的解只有一种（绝对）最优解;多目标决策的解有下面三种情况：绝对最优解d1807588d2758185d3767889d5787486d4858292绝对最优解数学外语专业解的类型TianjinUniversity•解概念区别单目标决策的解只有一种（绝对）最优解;多目标决策的解有下面三种情况：d1807588有效解d2758185有效解d3767889有效解劣解d4787486数学外语专业解的类型绝对最优解劣解（如d4劣于d1）有效解(pareto解)——非劣解TianjinUniversity§2多目标规划模型及其解的概念一、多目标规划举例例1：【喜糖问题】设市场上有甲级糖及乙级糖，单价分别为4元/斤及2元/斤。今要筹办一桩喜事。“筹备小组”计划总花费不超过40元，糖的总斤数不少于10斤，甲级糖不少于5斤。问如何确定最佳的采购方案。约束条件：决策变量：甲级糖数量为x1，乙级糖数量为x2121211242401050,0xxxxxxxTianjinUniversity§2多目标规划模型及其解的概念目标函数：何为最佳？（1）总花费最小：minf1(x1,x2)=4x1+2x2（2）糖的总数量最大：maxf2(x1,x2)=x1+x2（3）甲级糖的数量最大：maxf3(x1,x2)=x1多目标规划问题TianjinUniversity§2多目标规划模型及其解的概念例2【投资决策问题】某投资开发公司拥有总资金A万元，今有n(≥2)个项目可供选择。设投资第i(i=1,…,n)个项目要用资金ai万元，预计可得到收益bi万元。问应如何使用总资金A万元，才能得到最佳的经济效益？1，投资第i个项目0，不投资第i个项目解：令xi=约束条件：),,1101nixAxainiii（或TianjinUniversity§2多目标规划模型及其解的概念目标函数：何为最佳的经济效益？（1）收益最大：（2）投资最少：niiinxbxxf111),,(maxniiinxaxxf112),,(min多目标0-1规划问题TianjinUniversity§2多目标规划模型及其解的概念二、多目标规划的模型决策变量：nxx,,1目标函数：),,(min11nxxf…),,(min1npxxf约束条件：0),,(0),,(111nmnxxgxxgTianjinUniversity向量数学规划(VectorMathematicalProgramming)§2多目标规划模型及其解的概念多目标规划模型的向量表达形式记：T1),,(nxxX则模型为：T1))(,),(()(XfXfXFpmiXgXRi,,1,0)(miXgXfXfip,,1,0)()(,),((min)VMP(1或min()(VMP)FXXRTianjinUniversity§2多目标规划模型及其解的概念一、多目标规划举例二、多目标规划的模型三、多目标规划解的概念TianjinUniversity§2多目标规划模型及其解的概念三、多目标规划解的概念111122211212121212()()(1)1(2)1ppppiiFffEFffEFFFFipffFFFFi先引进一些记号，记，……，，……，：意味着向量的每个分量都要严格的小于向量对应的分量。即对于，……，，均有。：意味着向量的每个分量都要小于或等于向量对应的分量。即对于，00121212121212121212(3)1iiiiiipffFFFFFFipffffFFFFFF00……，，均有。：意味着向量的每个分量都要小于或等于向量对应的分量，并且存在的某一个分量要严格的小于向量对应的分量。即对于，……，，均有，并且要至少存在某个i(1ip)，有。可见，等价于且。TianjinUniversity§2多目标规划模型及其解的概念定义1设X*∈R，若对任意X∈R，均有F(X*)≦F(X)，则称X*为问题（VMP）的绝对最优解。其全体记为R*ab。0f1(x)f2(x)x绝对最优解示意图x*f注：绝对最优解往往不存在！TianjinUniversity§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解。其全体记为。XXX*paRTianjinUniversity§2多目标规划模型及其解的概念定义4设∈R，若不存在X∈R，使F(X)F()，则称为问题的弱有效解。其全体记为。XXX*wpR注：有效解必是弱有效解。x0Rwp*ff1(x)f2(x)TianjinUniversity§2多目标规划模型及其解的概念f20f1ABCDE劣解与有效解两个目标的最大化问题：TianjinUniversity§2多目标规划模型及其解的概念多目标规划——解的关系定理1，其中为单目标fi(X)上最优点集合。piiabRR1***iR定理2RRRRwppaab***0Rwp*ff1(x)f2(x)xR1*R2*Rpa*=Rab*TianjinUniversity§2多目标规划模型及其解的概念多目标规划——解的关系定理3**wpiRR定理4piiwppiiabpaabRRRRRR1**1****21）；（）（，则若TianjinUniversity§2多目标规划模型及其解的概念多目标规划——解的关系例1下图中，R1*=｛x1｝，R2*=｛x2｝，21**,xxRRwppax0f1(x)f2(x)x1Rpa*x2fTianjinUniversity§2多目标规划模型及其解的概念多目标规划——解的关系Rp=3Rab*=φp=3Rab*≠φRR1*R2*RpaRwp*Rab*=Rpa*R1*R2*R3**TianjinUniversity§1多目标决策简介§2多目标规划模型及其解的概念§3多目标规划的解法多目标规划TianjinUniversity§3多目标规划的解法求：有效解或弱有效解,)()(iiifXfXf)(maxXffiRXi其中方法分类评价函数法目标排序法准备工作：目标函数规范化TianjinUniversity一、评价函数法:1()()()()min[()]()()()pXRhFhffVMPPhFXhFPXVMP评价函数法就是利用一个复合函数:，……，把多目标问题转化为单目标问题:然后来求解，而单目标问题的解法我们是熟知的。问题是，用评价函数得到的的最优解是否为原问题的有效解或弱有效解？因为若连弱有效解都不是，那显然是不足取的。§3多目标规划的解法TianjinUniversity**121212()()()()()()pawppppphFXRXRhFEFFFEFEhFhFhFhFE下面我们将指出，当评价函数具有某种“单调性时”，是可以保证（或）的。为此，先给出两个定义：定义4设是定义在上的函数，若对于任意满足的，，均有：则称为严格单调函数。定义5设是定义在上的函数，若对于任121212()()()ppFFFEFEhFhFhF意满足的，，均有：则称为单调函数。§3多目标规划的解法TianjinUniversity**()()min[()]()()()[()][()]()pXRpapahFEXphFXXRXRYRFYFXhFhFYhFXXp定理6若为定义在上的严格单调函数，为规划问题的最优解，则。证：用反证法。若，则存在，有，由的严格单调性，有这与为问题的最优**()()min[()]papXRwpXRhFEXphFXXR解矛盾，故。定理7若为定义在上的单调函数，为规划问题的最优解，则。证明方法与定理6雷同。§3多目标规划的解法TianjinUniversity§3多目标规划的解法一、评价函数法1.线性加权和法2.理想点法3.目标规划法二、目标排序法TianjinUniversity111111()011pppppiiihFffip下面介绍两种常用的评价函数方法。、线性加权和法该方法就是取评价函数为各目标函数的线性加权和，即其中，……，为相应目标的权系数。线性加权和法的步骤如下：(1)依目标的重要程度给出一组权系数，……，，其中，，……，，。§3多目标规划的解法三种TianjinUniversity1***(2)()()min()()(3)()0101()0piiXRiwpipaipaiVMPPfXPXXVMPXRipXRiphFXR将转化为单目标问题求解得最优解。可以证明，是的弱有效解，即。进一步，若所有权系数均为正，即，，，，则。事实上，当，，，时，为严格单调函数，故；而当，*1()wpiphFXR，，时，为单调函数，故。§3多目标规划的解法TianjinUniversity§3多目标规划的解法确定权系数常用方法：特尔菲法、层次分析法、α-法α-法的步骤（以两个目标为例）：U［F(X)］=α1f1(X)+α2f2(X)(1)求解单目标优化问题)()(min111XfXfRX(问题一)，记)(),(12121111XffXff(问题二)，记)(),(21212222XffXff)()(min222XfXfRXTianjinUniversity§3多目标规划的解法（2）α-方法的出发点：U［F(X1)］=U［F(X2)］121222211122111ffff;2111122212221ffffff2111122221112ffffff(3)求解，)()(min)(min2211XfXfXFURXRX得X*TianjinUniversity§3多目标规划的解法α-方法的几何意义：;:),(12111点AffX点BffX:),(22212目标值空间0f2f21f22AU*=minUf11f12f1CB（1）平行直线簇α1f1+α2f2=c；（2）同一条直线上X1与X2有相同的评价值，即有U［F(X1)］=U［F(X2)］。TianjinUniversity§3多目标规划的解法例设有min23)(,min4)(212211xxXfxxXf},0,,3,42|{2212121RXxxxxxxXR试用α-法求解。