运筹学多目标规划.ppt
第二章 多目标规划（Multiple Objective Programming）,一、多目标决策问题实例,干部评估德、才兼备教师晋升教学、科研、论文等购买冰箱价格、质量、耗电、品牌等球员选择技术、体能、经验、心理找对象容貌、学历、气质、家庭状况,1 多目标决策简介,二、多目标决策与多目标规划,多目标决策,多目标规划（Multiple Objective Programming，决策变量连续）,多准则决策（Multiple Criteria Decision Making，决策变量离散，即有限方案）,1 多目标决策简介,三、多目标决策与单目标决策区别,点评价与向量评价 单目标：方案dj 评价值f(dj)多目标：方案dj评价向量(f1(dj)，f2(dj)，fp(dj)全序与半序:方案di与dj之间 单目标问题:didj 多目标问题：除了这三种情况之外,还有一种情况是不可比较大小决策者偏好：多目标决策过程中，反映决策者对目标的偏好。,1 多目标决策简介,解概念区别,单目标决策的解只有一种（绝对）最优解;多目标决策的解有下面三种情况：绝对最优解,解概念区别,单目标决策的解只 有一种（绝对）最优解;多目标决策的解有下面三种情况：,数学,外语,专业,解的类型,绝对最优解 劣解（如d4劣于d1）有效解(pareto解)非劣解,2 多目标规划模型及其解的概念,一、多目标规划举例,例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【投资决策问题】某投资开发公司拥有总资金A万元，今有n(2)个项目可供选择。设投资第 i(i=1,n)个项目要用资金ai 万元，预计可得到收益bi万元。问应如何使用总资金A万元，才能得到最佳的经济效益？,约束条件：,2 多目标规划模型及其解的概念,目标函数：何为最佳的经济效益？,（1）收益最大：,（2）投资最少：,2 多目标规划模型及其解的概念,二、多目标规划的模型,决策变量：,目标函数：,约束条件：,向量数学规划(Vector Mathematical Programming),2 多目标规划模型及其解的概念,多目标规划模型的向量表达形式,记：,则模型为：,或,2 多目标规划模型及其解的概念,一、多目标规划举例二、多目标规划的模型三、多目标规划解的概念,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解。其全体记为。,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 多目标决策简介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),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)越接近理想点越好。理想点：一般指由各单目标最优值组成的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，试用理想点法求解。,解：先分别求解两个单目标问题,3 多目标规划的解法,一、评价函数法 1.线性加权和法（-法确定权系数）2.理想点法 3.目标规划法二、目标排序法,3 目标规划法（Goal Programming）,是求解多目标规划的一种常用方法。该方法不考虑对各个目标进行极小化或极大化，而是希望在约束条件的限制下，每一目标尽可能地接近于事先给定的目的值。,（一）目标规划的思想,例：某工厂生产、两种产品，有关数据如下表：,决策者在原材料供应受严格限制的基础上，考虑尽量满足如下条件：（1）首先，产品的产量不低于产品 的产量；（2）其次，充分利用设备有效台时，不加班；（3）再次，利润额不小于56元。,（二）目标规划的数学模型,（1）在每个目标fi(X)上预先确定一个希望达到的目标值，得一目标值向量,分析：,（2）构造评价函数,（3）多目标决策问题,单目标问题,（其中R为问题的可行域）,（4）为了求解(3)，引入类偏差变量,负偏差,正偏差,可以证明（3）等价于,实际问题中：各目标可赋于不同的优先因子Pj；相同优先因子的两个目标的差别，可分别赋于它们不同的权系数ij,于是得到目标规划模型：,目标规划模型的特点：（1）目标函数都是最小化，只有偏差变量和优先因子（不含一般决策变量）；（2）约束条件中既可包含目标约束，还可包含绝对约束；（3）目标约束均为等式；且一般在一个约束中同时含有正、负偏差变量；,另外，根据决策者的不同要求，目标函数有三种基本形式：,（2）要求超过目标值，评价函数为,（1）要求恰好达到目标值，评价函数为,（3）要求不超过目标值，评价函数为,（三）目标规划建模举例,例1：某工厂生产、两种产品，有关数据如下表：,决策者在原材料供应受严格限制的基础上，考虑尽量满足如下条件：（1）首先，产品的产量不低于产品 的产量；（2）其次，充分利用设备有效台时，不加班；（3）再次，利润额不小于56元。,例1：某工厂生产、两种产品，有关数据如下表：,决策者在原材料供应受严格限制的基础上考虑：（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+,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）确定进基变量时，其在所有更高级目标函数下的检验数为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.理想点法 3.目标规划法二、目标排序法,3 多目标规划的解法,二、目标排序法（简介）,思想：把目标按其重要性排序，设给出的重要性序列为f1(X),f2(X),，fp(X)，然后按这种排序逐步进行一系列单目标优化，最后求出满意解。,3 多目标规划的解法,1.序列最优化法,最优解集Rp-1,缺点：由于某一步最优解唯一时，以后的目标的优化就不能进行下去了。,3 多目标规划的解法,2宽容意义下的序列优化方法,预先给定10，20，p-10作为宽容值,则Xp为多目标问题的最优解。,
