多目标规划及案例

多目标优化模型、多目标优化简介优化(Optimization):从若干可能的方案中寻求某 种意义下的最优方案多目标规戈(Multiple Objectives Programming) 是数学规划的一个分支，研究多于一个目标函数在给 定区域上的最优化，又称多目标最优化，通常记为 VMPO求解算法 转化为单目标实例1:投资的收益和风险市场上有11种资产（如股票、债券、）Si （ i=l,口） 供投资者选择，某公司有数额为M的一笔相当大的资金可用 作一个时期的投资。公司财务分析人员对这n种资产进行了 评估，估算出在这一时期内购买Si的平均收益率，并预测出 购买Si的风险损失率。考虑到投资越分散，总的风险越小， 公司确定，当用这笔资金购买若干种资产时，总体风险可用 所投资的Si中最大的一个风险来度量。购买Si要付交易费，费率已知，并且当购买额不超过最低限 额时，交易费按购买最低限额计算（不买当然无须付费）。 另外，假定同期银行存款年利率是1 %,且既无交易费又无风 险。试给该公司设计一种投资组合方案目标一：使净收益尽可能大；目标二：而总体风险尽可能小。实例2：旅游路线设计今年暑假，我校要召开“xx学术会议”，届时来自国内外的许多著名学者都会相聚成都。在会议结束后，主办方希望能 安排这些远道而来的贵宾参观四川省境内的著名自然和人文景 观，初步设想有如下线路可供选择： 一号线：九寨沟、黄龙;二号线：乐山、峨嵋;三号线：四姑娘山、丹巴；四号线：都江堰、青城山；五号线：海螺沟、康定；每条线路中的景点可以全部参观，也可以参观其中之一。不仅如此，一起参观景点的人数越多，每人承担的费用也会越 小。车费与车型、乘客人数、路程种类及公里数有关。主办方在会议开始前对所有参会的100位代表旅游意向进行了调查，充分考虑这些代表的意为主办方设计代表们合适的旅游路线，使他们在会 议结束后的10天时间内花最少的钱游尽可能多的地方。目标一:目标二:目标三:宾客参观意愿满意度尽可能高 宾客所花费用尽可能少宾客游尽可能多的景点转化为单目标的具体方法介绍:1.主要目标法在多目标优化问题中，根据问题的实际 情况，确定一个目标为主要目标，而把其余目 标作为次要目标，并且根据决策者的经验，选 取一定的界限值。这样就可以把次要目标也作 为约束来处理，于是就将原多目标问题转化为 在新的约束下，求主要目标的单目标优化问 题。转fk单目标法2.线性加权和法：按照加个目标乞的重要 程度，分别乘以一组权系数，然后相加作为目标函数。mZ=1亍人iZ=1转fk单目标法3. 极大极小点法min w(/(x) = min max/(x)imxeX i0双目标规划模型aF(X) = MX0max R(X) st Q(X)0。为目标权重或偏好系数。a,b,p均可看成参数，对不同的参数值求出 最优解，然后加以讨论，选出满意解。课号课名学分所属类别先修课要求1微积分5数学23456789线性代数最优化方法数据结构应用统计计算机模拟计算机编程预测理论数学实验44343223数学数学；运筹学数学；计算机数学；运筹学微积分；线性代数计算机编程微积分；线性代数运筹学计算机运筹学运筹学；计算机计算机编程应用统计微积分；线性代数例选课策略要求至少选两门数学课、三门运筹学课和两门计算机课为了选修课程门数最少，应学习哪些课程？ 选修课程最少，且学分尽量多，应学习哪些课程？01规划模型决策变量课号123456789课名微积分线性代数最优化方法数据结构应用统计计算机模拟计算机编程预测理论数学实验所属类别数学数学数学；运筹学数学；计算机数学；运筹学计算机；运筹学七二1选修课号i的课程（七二0不选）目标函数选修课程总数最少计算机运筹学运筹学；计算机9Min Z二工兀Z=1最少2门数学课, 约束条件3门运筹学课，2门计算机课。兀3 +尤5 +兀6 +兀8 +尤9有+兀6 + *7 +兀9 2（M规划模型课号课名先修课要求* 1微积分* 2线性代数* 3最优化方法微积分；线性代数4数据结构计算机编程5应用统计微积分；线性代数* 6计算机模拟计算机编程* 7计算机编程8预测理论应用统计* 9数学实验微积分；线性代数约束条件先修课程要求工3=1必有工1 =工2 =1x3 x3 x22x3 - x - x2 Q 兀4 兀7 口 x4 -x7 00模型求解（LINDO）x6 -x7 0最优解:兀8% 5=1,其它为0; 6门课程，总学分212x9 -xl-x2 0学分最多9Min Z二工兀i=讨论：选修课程最少，学分尽量多，应学习哪些课程?课程最少Max W=5xj +4x2 +4% +3x4 +4x5+ 3x6 +2Xy +2无 +3Xg两目标（多目标）规划旳加乙-W多目标优化的处理方法：化成单目标优化。以课程最少为目标，最优解如上，6门课不管学分多少。H程，总学分21。以学分最多为目标，卄最优解显然是选修所 不管课程多少。9有9门课程。9多目标规划增加约束以学分最多为目标求解。课号课名学分* 1 *微积分5* 2 *线性代数4* 3 *最优化方法44数据结构35 *应用统计4* 6计算机模拟3* 7 *计算机编程28预测理论2* 9 *数学实验3解:工=工2 =兀3 =兀5 =x7 = x9 =1,其它为0；总学分由21增至22。注意：最优解不唯一! 可将兀9 =1易为兀6 =1 LINDO无法告诉优化 问题的解是否唯一。在课程最少的前提下 以学分最多为目标。多目标规划对学分数和课程数加权形成一个目标，如三七开。Min Y = Z- 22W = 0.7Z - 0.3W课号课名学分1 *微积分52 *线性代数43 *最优化方法44 *数据结构35 *应用统计46 *计算机模拟37 *计算机编程28预测理论29 *数学实验39Z = 0,1=1W=5x +4x2 +4花 +3嘉 +4兀5+3兀6 +2%y +2 九 +3xg伪兀=兀2 =兀3 =兀4MHBMHHi| 人5 人6 人7 人9 夏,其它为0;总学分28。求解算法之一:转化为单目标求解算法之二:二 目标规划法二多目标优fl!目标規划济线性规划通常考虑一个目标函数（问题简单）目标规划考虑多个目标函数（问题复杂）O例生产安排问题某企业生产甲、乙两种产品，需要用到A,B,C 三种设备，关于产品的盈利与使用设备的工时及限 制如下表所示。甲乙设备的生产能力/hA/（h/件）2212B/（h/件）4016C/（h/件）0515赢利/（元/件）200300问该企业应如何安排生产，使得在计划期内 总利润最大？1.线性规划建模该例是一个线性规划问题，直接考虑它的线性规划模型 设甲、乙产品的产量分别为坷，丕,建立线性规划模型:Max z = 200 %, + 300 x2;s. t.2x1 +2x2 12,4X 0.用Lindo或Lingo软件求解，得到最优Xj = 3,=3,z = 1500.2.目标规划建模Max z = 200 x + 300 x 2;s. t. 2xl + 2x2 12,4壬 16,5兀2 0.若在上例中，企业的经营目标不仅要考 虑利润，还需要考虑多个方面，因此增加下列因素（目标）:力求使利润指标不低于1500元考虑到市场需求，甲、乙两种产品的产量比应尽量保持1：2设备A为贵重设备，严格禁止超时使用设备C可以适当加班，但要控制；设备B既要求充分利用，又 尽可能不加班，在重要性上，设备B是设备C的3倍从上述问题可以看出，仅用线性规划方法是不够的，需要借助于目标规划的方法进行建模求解目标规划的数学模型目标规划的基本概念为了克服线性规划的局限性,目标规划采用如下手段:1. 设置偏差变量;2. 统一处理目标与约束;目标的优先级与权系数。1设置偏差变量用偏差变量(Deviational variables)来表示实际值与目标值超出目标的差值，称为正偏差变量d+ 旷之间的差异，令未达到目标的差值，称为负偏差变量 其中 +与一至少有一个为o约定如下：当实际值超过目标值时，有=0,+0; 当头际值未达到目标值时，有+=0,-0; 当实际值与目标值一致时，有-=0,+=02.统一处理目标与约束在目标规划中，约束可分两类，一类是对资源有严格限制 的，称为刚性约束(Hard Constraint);例如在用目标规划 求解生产安排问题中设备A禁止超时使用，则有刚性约束2xj + 2兀2 12 .另一类是可以不严格限制的，连同原线性规划的目标，构 成柔性约束(Soft Constraint).例如在求解生产安排中，我 们希望利润不低于1500元，则目标可表示为200%! + 300x2 += 1500.甲乙设备的生产能力/hA/（h/件）2212B/（h/件）4016C/（h/件）0515赢利/（元/件）200300力求使利润指标不低于1500元考虑到市场需求，甲、乙两种产品的产量比应尽量保持1：2设备A为贵重设备，严格禁止超时使用 设备C可以适当加班，但要控制；设备B既要求充分利用，又 尽可能不加班，在重要性上，设备B是设备C的3倍设甲、乙产品的产量分别为坷，丕,建立模型:设备C可以适当加班，但要控制, 则目标可表示为mind+;5x9 + d d+ =15.JminJ+ +d_;+ d _ + = 0.设备B既要求充分利用，又尽可能不加班，则目标可表示为mind+ +d ；4兀1 +d_-d+ =16.甲、乙两种产品的产量尽量保 持1:2的比例，则目标可表示为从上面的分析可以看到：如果希望不等式保持大于等于，则极小化负偏差; 如果希望不等式保持小于等于，则极小化正偏差; 如果希望保持等式，则同时极小化正、负偏差3目标的优先级与权系数目标规划模型中，目标的优先分为两个层次，第一个层次是目标分成不同的优先级，在计 后再优化低优先级的目标。通常以P, P2,.表示 不同的因子,并规定pkpk+1,第二个层次是目标 处于同一优先级，但两个目标的权重不一样， 此两目标同时优化，用权系数的大小来表示目标 重要性的差别。标规划时，必须先优化高优先级的目标，用目标规划方法求解解：在生产安排问题中设备A是刚性约束，其余 是柔性约束.首先，最重要的指标是企业的利 润，将它的优先级列为第一级；其次，甲、乙两 种产品的产量保持1:2的比例，列为第二级；再 次，设备B和C的工作时间要有所控制，列为第三 级，设备B的重要性是设备C的三倍，因此它们的 权重不一样。由此可以得到相应的目标规划模 型。min z =+ 匕（d； +d；） +马（3d； +3d； + d；）;5.t. 2x1+2x212,20QX +30Qx*? + - 150Q2兀兀 + 2 d； 0,4尤+ 3 d； 16,5x? +4 d； =15, x“X2“；S； 0J = 123,4.作业3、计算机公司生产管理问题某计算机公司生产三种型号的笔记本电脑A,B,C。 这三种笔记本电脑需要在复杂的装配线上生产，生 产1台A,B,C型号的笔记本电脑分别需要5,8,12小时。 公司装配线正常的生产时间是每月1700小时。公司 营业部门估计A,B,C三种笔记本电脑的利润分别是 每台1000,1440,2520元，而公司预测这个月生产的笔 记本电脑能够全部售出。例计算机公司生产管理问题公司经理考虑以下目标：第一目标：充分利用正常的生产能力，避免开工不足； 第二目标：优先满足老客户的需求，A,B,C三种型号的电脑 50,50,80台，同时根据三种电脑的纯利润分配不同的权因子; 第三目标：限制装配线加班时间，不允许超过200小时； 第四目标：满足各种型号电脑的销售目标,A,B,C型号分别为 100,120,100台，再根据三种电脑的纯利润分配不同的权因子； 第五目标：装配线的加班时间尽可能少。通过适当的假设及变量设置建立模型，不用计算。