运筹学多目标规划

1、第二章 多目标规划（multiple objective programming）,一、多目标决策问题实例,干部评估德、才兼备 教师晋升教学、科研、论文等 购买冰箱价格、质量、耗电、品牌等 球员选择技术、体能、经验、心理 找对象容貌、学历、气质、家庭状况,1 多目标决策简介,二、多目标决策与多目标规划,多目标决策,多目标规划 （ multiple objective programming， 决策变量连续）,多准则决策 （ multiple criteria decision making，决策变量离散，即有限方案）,1 多目标决策简介,三、多目标决策与单目标决策区别,点评价与向量评价 单目标

2、： 方案dj 评价值f(dj) 多目标：方案dj评价向量(f1(dj)，f2(dj)，fp(dj) 全序与半序: 方案di与dj之间 单目标问题: didj 多目标问题：除了这三种情况之外,还有一种情况是不可比较大小 决策者偏好：多目标决策过程中，反映决策者对目标的偏好。,1 多目标决策简介,解概念区别,单目标决策的解只有一种（绝对）最优解; 多目标决策的解有下面三种情况： 绝对最优解,解概念区别,单目标决策的解只 有一种（绝对）最优解; 多目标决策的解有下面三种情况：,数学,外语,专业,解的类型,绝对最优解 劣解（如d4劣于d1 ） 有效解(pareto解)非劣解,2 多目标规划模型及其解的

3、概念,一、多目标规划举例,例1：【喜糖问题】设市场上有甲级糖及乙级糖，单价分别为4元/斤及2元/斤。今要筹办一桩喜事。“筹备小组”计划总花费不超过40元，糖的总斤数不少于10斤，甲级糖不少于5斤。问如何确定最佳的采购方案。,约束条件：,决策变量：甲级糖数量为x1，乙级糖数量为x2,2 多目标规划模型及其解的概念,目标函数：何为最佳？,（1）总花费最小： min f1(x1,x2)=4x1+2x2,（2）糖的总数量最大： max f2(x1,x2)=x1+x2,（3）甲级糖的数量最大： max f3(x1,x2)=x1,2 多目标规划模型及其解的概念,例2【投资决策问题】某投资开发公司拥有总资金

4、a万元，今有n(2)个项目可供选择。设投资第 i (i=1,n) 个项目要用资金ai 万元，预计可得到收益bi万元。问应如何使用总资金a万元，才能得到最佳的经济效益？,约束条件：,2 多目标规划模型及其解的概念,目标函数：何为最佳的经济效益？,（1）收益最大：,（2）投资最少：,2 多目标规划模型及其解的概念,二、多目标规划的模型,决策变量：,目标函数：,约束条件：,向量数学规划(vector mathematical programming),2 多目标规划模型及其解的概念,多目标规划模型的向量表达形式,记：,则模型为：,或,2 多目标规划模型及其解的概念,一、多目标规划举例 二、多目标规划

5、的模型 三、多目标规划解的概念,2 多目标规划模型及其解的概念,三、多目标规划解的概念,2 多目标规划模型及其解的概念,定义1 设x*r，若对任意xr，均有f(x*)f(x)，则称x*为问题（vmp）的绝对最优解。其全体记为r*ab 。,0,f1(x),f2(x),x,绝对最优解示意图,x*,f,注：绝对最优解往往不存在！,2 多目标规划模型及其解的概念,定义2 设x0r，若存在另一个可行解x1r，有f(x1) f(x0)，则称可行解x0相对于x1来说是劣解。,注：决策中，劣解不会被考虑！,定义3 设 r，若不存在xr，使f(x)f( )，则称 为问题的非劣解，又称有效解，或pareto解。其

6、全体记为 。,2 多目标规划模型及其解的概念,定义4 设 r，若不存在xr，使 f(x)f( )，则称 为问题的弱有效解。其全体记为 。,注：有效解必是弱有效解。,2 多目标规划模型及其解的概念,f2,0,f1,d,e,劣解与有效解,两个目标的最大化问题：,2 多目标规划模型及其解的概念,多目标规划解的关系,定理1 ，其中 为单目标 fi (x) 上 最优点集合。,2 多目标规划模型及其解的概念,多目标规划解的关系,定理3,定理4,2 多目标规划模型及其解的概念,多目标规划解的关系,例1 下图中，r1*=x1，r2*=x2，,2 多目标规划模型及其解的概念,多目标规划解的关系,1 多目标决策简

7、介 2 多目标规划模型及其解的概念 3 多目标规划的解法,多目标规划,3 多目标规划的解法,求：有效解或弱有效解,其中,准备工作：目标函数规范化,一、评价函数法:,3 多目标规划的解法,3 多目标规划的解法,3 多目标规划的解法,3 多目标规划的解法,一、评价函数法 1. 线性加权和法 2. 理想点法 3. 目标规划法 二、目标排序法,3 多目标规划的解法,三种,3 多目标规划的解法,3 多目标规划的解法,确定权系数常用方法：特尔菲法、层次分析法、-法,-法的步骤（以两个目标为例）： uf(x)=1f1(x)+2f2(x),3 多目标规划的解法,（2）-方法的出发点：uf(x1)=uf(x2)

8、,3 多目标规划的解法,-方法的几何意义：,目标值空间,0,f2,f21,f22,a,u*=minu,f11,f12,f1,c,b,（1）平行直线簇 1f1+2f2=c ； （2）同一条直线上x1与x2有相同的评价值，即有 uf(x1)=uf(x2)。,3 多目标规划的解法,例 设有,试用-法求解。,解： 求解单目标优化问题，得,3 多目标规划的解法,一、评价函数法 1. 线性加权和法 （ -法确定权系数） 2. 理想点法 3. 目标规划法 二、目标排序法,3 多目标规划的解法,2. 理想点法,基本思想：x的评价向量f(x)=(f1(x),f2(x),fp(x) 越接近理想点越好。 理想点：一

9、般指由各单目标最优值组成的p维点,0,f1,f2,f(x),3 多目标规划的解法,理想点法的步骤：,（1）求理想点。求解p个单目标最优化问题,得理想点：,（2）检验理想点。绝对最优点，则输出绝对最优解，,，求解完毕。否则，转（3）。,3 多目标规划的解法,理想点法的步骤：,（3）作评价函数。,（4）求解,note: 上述评价函数是严格增函数，故按其求得的解是(vmp)的有效解。,3 多目标规划的解法,例：设f1(x)=-3x1+2x2，f2(x)=4x1+3x2都要求实现最大，约束集为rx|2x1+3x218，2x1+x210，x1，x20，xr2，试用理想点法求解。,解：先分别求解两个单目标

10、问题,3 多目标规划的解法,一、评价函数法 1. 线性加权和法 （ -法确定权系数） 2. 理想点法 3. 目标规划法 二、目标排序法,3 目标规划法（goal programming）,是求解多目标规划的一种常用方法。 该方法不考虑对各个目标进行极小化或极大化，而是希望在约束条件的限制下，每一目标尽可能地接近于事先给定的目的值。,（一）目标规划的思想,例：某工厂生产、两种产品，有关数据如下表：,决策者在原材料供应受严格限制的基础上，考虑尽量满足如下条件： （1）首先，产品的产量不低于产品 的产量； （2）其次，充分利用设备有效台时，不加班； （3）再次，利润额不小于56元。,（二）目标规划的

11、数学模型,（1）在每个目标fi(x)上预先确定一个希望达到的目标值，得一目标值向量,分析：,（2）构造评价函数,（3）多目标决策问题,单目标问题,（其中r为问题的可行域）,（4）为了求解(3)，引入类偏差变量,负偏差,正偏差,可以证明（3）等价于,实际问题中： 各目标可赋于不同的优先因子pj ； 相同优先因子的两个目标的差别，可分别赋于它们不同的权系数ij,于是得到目标规划模型：,目标规划模型的特点： （1）目标函数都是最小化，只有偏差变量和优先因子（不含一般决策变量）； （2）约束条件中既可包含目标约束，还可包含绝对约束； （3）目标约束均为等式；且一般在一个约束中同时含有正、负偏差变量；,

12、另外，根据决策者的不同要求，目标函数有三种基本形式：,（2）要求超过目标值，评价函数为,（1）要求恰好达到目标值，评价函数为,（3）要求不超过目标值，评价函数为,（三）目标规划建模举例,例1：某工厂生产、两种产品，有关数据如下表：,决策者在原材料供应受严格限制的基础上，考虑尽量满足如下条件： （1）首先，产品的产量不低于产品 的产量； （2）其次，充分利用设备有效台时，不加班； （3）再次，利润额不小于56元。,例1：某工厂生产、两种产品，有关数据如下表：,决策者在原材料供应受严格限制的基础上考虑： （1）首先，产品的产量不低于产品 的产量； （2）其次，充分利用设备有效台时，不加班； （3）

13、再次，利润额不小于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+,d

14、3-,d3+,step1 p1 obc,step2 p2 线段ed,step3 p3 目标规划的解：线段gd. 其中，g(2,4), d(10/3,10/3),注：该例求得最优解，且z*=0. 但大多问题可能无法满足所有约束，此时求满意解。,例：求解目标规划,分析： 1）目标p1,p2 四边形abcd； 2）d3-的权系数大于d4-，故优先考虑 min d3- 四边形abef; 3)四边形abef无法满足d4-=0，故选取e为满意解，使d4-尽量小。,（2）目标规划的单纯形法,与一般单纯形法的区别： （1）最优性准则：所有检验数 0； （2）检验数的正负，优先取决于p1的系数，其次p2。 （3

15、）确定进基变量时，其在所有更高级目标函数下的检验数为0，使低级目标上的进基不影响所有高级目标上已获目标值。,（2）目标规划的单纯形法,步骤： 1）建立初始单纯形表，在表中将检验数行按优 先因子个数列成k行，置k=1. 2）检查该行是否存在负数，且对应的前k-1行的系数是0。若有负数，取最小者对应的变量为进基变量，转3）。若无负数，转（5）。 3）按最小比值规则确定出基变量，当存在两个及以上相同的最小比值时，选取优先级较高的为出基变量。 4）按单纯形法进行基变换运算，得新表，转（2）。 5）当k=k时，算法结束，得满意解。否则置k=k+1,转（2）。,3 多目标规划的解法,一、评价函数法 1. 线性加权和法 （ -法确定权系数） 2. 理想点