运筹学多目标规划..教学内容

1、Tianjin University 运筹学多目标规划运筹学多目标规划.Tianjin University 二、多目标决策与多目标规划二、多目标决策与多目标规划多目标决策多目标决策多目标规划多目标规划（ Multiple Objective Programming， 决策变量连续）决策变量连续）多准则决策多准则决策（ Multiple Criteria Decision Making，决策变量离散，即有限方案）决策变量离散，即有限方案）1 1 多目标决策简介多目标决策简介Tianjin University 三、多目标决策与单目标决策区别三、多目标决策与单目标决策区别 点评价与向量评价点评价

2、与向量评价 单目标：单目标： 方案方案dj 评价值评价值f(dj) 多目标：方案多目标：方案dj评价向量评价向量(f1(dj)，f2(dj)，fp(dj) 全序与半序全序与半序: 方案方案di与与dj之间之间 单目标问题单目标问题: didj 多目标问题：除了这三种情况之外多目标问题：除了这三种情况之外,还有一种情况还有一种情况是不可比较大小是不可比较大小 决策者偏好：决策者偏好：多目标决策过程中，反映决策者对多目标决策过程中，反映决策者对目标的偏好。目标的偏好。1 1 多目标决策简介多目标决策简介Tianjin University 解概念区别解概念区别单目标单目标决策的解只有一种（绝对）最

3、优解决策的解只有一种（绝对）最优解;多目标多目标决策的解有下面三种情况：决策的解有下面三种情况： 绝对最优解绝对最优解d1807588d2758185d3767889d5787486d4858292绝对最优解绝对最优解数学数学外语外语专业专业解的类型解的类型Tianjin University 解概念区别解概念区别单目标单目标决策的解只决策的解只 有一种（绝对）最优解有一种（绝对）最优解;多目标多目标决策的解有下面三种情况：决策的解有下面三种情况：d1807588有效解有效解d2758185有效解有效解d3767889有效解有效解劣解劣解d4787486数学数学外语外语专业专业解的类型解的类型

4、 绝对最优解绝对最优解 劣解（劣解（如如d4劣于劣于d1 ） 有效解有效解(pareto解解)非劣解非劣解Tianjin University 2 2 多目标规划模型及其解的概念多目标规划模型及其解的概念一、多目标规划举例一、多目标规划举例例例1 1：【喜糖问题喜糖问题】设市场上有甲级糖及乙级糖，单价分别为设市场上有甲级糖及乙级糖，单价分别为4 4元元/ /斤及斤及2 2元元/ /斤。今要筹办一桩喜事。斤。今要筹办一桩喜事。“筹备小组筹备小组”计划总计划总花费不超过花费不超过4040元，糖的总斤数不少于元，糖的总斤数不少于1010斤，甲级糖不少于斤，甲级糖不少于5 5斤。问如何确定最佳的采购方

5、案。斤。问如何确定最佳的采购方案。 约束条件：约束条件：决策变量：决策变量：甲级糖数量为甲级糖数量为x1，乙级糖数量为，乙级糖数量为x2121211242401050,0 xxxxxxxTianjin University 2 2 多目标规划模型及其解的概念多目标规划模型及其解的概念目标函数：目标函数：何为何为最佳？最佳？（1）总花费最小：）总花费最小： min f1(x1,x2)=4x1+2x2 （2）糖的总数量最大：）糖的总数量最大： max f2(x1,x2)=x1+x2 （3）甲级糖的数量最大：）甲级糖的数量最大： max f3(x1,x2)=x1多目标规划问题多目标规划问题Tianj

6、in University 2 2 多目标规划模型及其解的概念多目标规划模型及其解的概念例例2【投资决策问题投资决策问题】某投资开发公司拥有总资某投资开发公司拥有总资金金A万元，今有万元，今有n(2)个项目可供选择。设投资第个项目可供选择。设投资第 i (i=1,n) 个项目要用资金个项目要用资金ai 万元，预计可得到万元，预计可得到收益收益bi万元。问应如何使用总资金万元。问应如何使用总资金A万元，才能万元，才能得到最佳的经济效益？得到最佳的经济效益？1， 投资第投资第i个项目个项目0，不，不投资第投资第i个项目个项目解：令解：令 xi =约束条件：约束条件： ), 1101nixAxain

7、iii（或或Tianjin University 2 2 多目标规划模型及其解的概念多目标规划模型及其解的概念目标函数：目标函数：何为何为最佳的经济效益？最佳的经济效益？（1）收益最大：）收益最大：（2）投资最少：）投资最少： niiinxbxxf111),(max niiinxaxxf112),(min多目标多目标0-1规划问题规划问题Tianjin University 2 2 多目标规划模型及其解的概念多目标规划模型及其解的概念二、二、多目标规划的模型多目标规划的模型决策变量：决策变量：nxx,1目标函数：目标函数：),(min11nxxf),(min1npxxf约束条件：约束条件： 0

8、),(0),(111nmnxxgxxgTianjin University 2 2 多目标规划模型及其解的概念多目标规划模型及其解的概念多目标规划模型的向量表达形式多目标规划模型的向量表达形式记：记：T1),(nxxX 则模型为：则模型为：T1)(,),()(XfXfXFp miXgXRi, 1, 0)( miXgXfXfip, 1, 0)()(,),(min)VMP(1或或min()(VMP)F XXR Tianjin University 2 2 多目标规划模型及其解的概念多目标规划模型及其解的概念一、多目标规划举例一、多目标规划举例二、多目标规划的模型二、多目标规划的模型三、多目标规划解

9、的概念三、多目标规划解的概念Tianjin University 2 2 多目标规划模型及其解的概念多目标规划模型及其解的概念三、多目标规划解的概念三、多目标规划解的概念111122211212121212 () ()(1)1(2) 1ppppiiFffEFffEFFFFipffFFFFi 先先引引进进一一些些记记号号，记记， ：意意味味着着向向量量的的每每个个分分量量都都要要严严格格的的小小于于向向量量对对应应的的分分量量。即即对对于于， ，均均有有。 ：意意味味着着向向量量的的每每个个分分量量都都要要小小于于或或等等于于向向量量对对应应的的分分量量。即即对对于于，0012121212121

10、2121212(3)1iiiiiipffFFFFFFipffffFFFFFF 0000， ，均均有有。 ：意意味味着着向向量量的的每每个个分分量量都都要要小小于于或或等等于于向向量量对对应应的的分分量量，并并且且存存在在的的某某一一个个分分量量要要严严格格的的小小于于向向量量对对应应的的分分量量。即即对对于于， ，均均有有，并并且且要要至至少少存存在在某某个个i(1ip)i(1ip)，有有。 可可见见，等等价价于于且且。Tianjin University 2 2 多目标规划模型及其解的概念多目标规划模型及其解的概念定义定义1 设设X*R，若对任意，若对任意XR，均有，均有F(X*)F(X)，

11、则称，则称X*为问题（为问题（VMP）的）的绝对最优解绝对最优解。其全体记为。其全体记为R*ab 。 0f1(x)f2(x)x绝对最优解示意图 x*f注：注：绝对最优解往往不存在！Tianjin University 2 2 多目标规划模型及其解的概念多目标规划模型及其解的概念定义定义2 设设X0R，若存在另一个可行解，若存在另一个可行解X1R，有，有F(X1) F(X0)，则称可行解，则称可行解X0相对于相对于X1来说是来说是劣解劣解。注：注：决策中，决策中，劣解不会被考虑！劣解不会被考虑！x0 f1(x) f2(x) x1* Rpa* x2* f定义定义3 设设 R，若不存在，若不存在XR

12、，使，使F(X)F( )，则称则称 为问题的为问题的非劣解非劣解，又称，又称有效解有效解，或，或Pareto解解。其全体记为其全体记为 。XXX*paRTianjin University 2 2 多目标规划模型及其解的概念多目标规划模型及其解的概念定义定义4 设设 R，若不存在，若不存在XR，使，使 F(X)F( )，则称则称 为问题的为问题的弱有效解弱有效解。其全体记为。其全体记为 。XXX*wpR注：注：有效解必是弱有效解。有效解必是弱有效解。x0 Rwp * ff1(x)f2(x)Tianjin University 2 2 多目标规划模型及其解的概念多目标规划模型及其解的概念f20f

13、1ABCDE劣解与有效解劣解与有效解两个目标的最大化问题：两个目标的最大化问题：Tianjin University 2 2 多目标规划模型及其解的概念多目标规划模型及其解的概念多目标规划多目标规划解的关系解的关系定理定理1 ，其中，其中 为单目标为单目标 fi (X) 上上最优点集合。最优点集合。 piiabRR1* *iR定理定理2RRRRwppaab *0 Rwp * ff1(x)f2(x)x R1* R2* Rpa*= Rab*Tianjin University 2 2 多目标规划模型及其解的概念多目标规划模型及其解的概念多目标规划多目标规划解的关系解的关系定理定理3*wpiRR 定

14、理定理4piiwppiiabpaabRRRRRR1*1*21 ）；（）（，则则若若 Tianjin University 2 2 多目标规划模型及其解的概念多目标规划模型及其解的概念多目标规划多目标规划解的关系解的关系例例1 下图中，下图中，R1*=x1，R2*=x2， 21*,xxRRwppa x0 f1(x) f2(x) x1 Rpa* x2 fTianjin University 2 2 多目标规划模型及其解的概念多目标规划模型及其解的概念多目标规划多目标规划解的关系解的关系 R3*Rp=3 Rab*=p=3 Rab*RR1*R2*RpaRwp*Rab*=Rpa*R1*R2*R3*Tia

15、njin University 1 多目标决策简介多目标决策简介2 2 多目标规划模型及其解的概念多目标规划模型及其解的概念3 多目标规划的解法多目标规划的解法多目标规划多目标规划Tianjin University 3 多目标规划的解法多目标规划的解法 求：有效解或弱有效解求：有效解或弱有效解 ,)()(iiifXfXf )(maxXffiRXi 其中其中 方法分类方法分类评价函数法评价函数法目标排序法目标排序法 准备工作：目标函数规范化准备工作：目标函数规范化Tianjin University 一、评价函数法一、评价函数法: :1 ()()() ( ) min ()()( )()pXRh

16、 Fh ffVMPPh F Xh FPXVMP 评评价价函函数数法法就就是是利利用用一一个个复复合合函函数数: :，把把多多目目标标问问题题转转化化为为单单目目标标问问题题: :然然后后来来求求解解，而而单单目目标标问问题题的的解解法法我我们们是是熟熟知知的的。问问题题是是，用用评评价价函函数数得得到到的的的的最最优优解解是是否否为为原原问问题题的的有有效效解解或或弱弱有有效效解解？因因为为若若连连弱弱有有效效解解都都不不是是，那那显显然然是是不不足足取取的的。3 多目标规划的解法多目标规划的解法Tianjin University *121212 ()() ()()()()pawppppph

17、 FXRXRh FEFFFEFEh Fh Fh Fh FE 下下面面我我们们将将指指出出，当当评评价价函函数数具具有有某某种种“单单调调性性时时”，是是可可以以保保证证（或或）的的。为为此此，先先给给出出两两个个定定义义： 定定义义4 4 设设是是定定义义在在上上的的函函数数，若若对对于于任任意意满满足足的的，均均有有：则则称称为为严严格格单单调调函函数数。 定定义义5 5 设设是是定定义义在在上上的的函函数数，若若对对于于任任121212 ()()()ppFFFEFEh Fh Fh F 意意满满足足的的，均均有有：则则称称为为单单调调函函数数。3 多目标规划的解法多目标规划的解法Tianji