一、多目标规划问题的提出.ppt

一、多目标规划问题的提出： 多目标问题是现实世界中普遍遇到的一类问题，其中希望（或必须）考虑多个相互矛盾目标的影响。 例如证券投资问题中我们希望利润最大而风险最小，生产销售问题中我们希望费用较少而获利很大，等等。 单目标模型只需简单确定一个目标，而将其余的列为约束； 在构建多目标模型时，则需要对问题有较深的理解，必须考虑更全面——虽然费时较多，却非常有益，更切合实际。 求解多目标决策常用的三种方法（或思想）： 加权或效用系数法 序列或优先级法 有效解（非劣解）法 加权法： 加权法把问题中的所有目标用统一的单位来度量（例如用钱或效用系数） 这种方法的核心是把多目标模型化成单目标模型。 优点：适于计算机求解 （例如模型是线性的时候可用一般的单纯形法求解） 缺点：难处在于如何寻到合理的权系数。 序列或优先级法： 序列或优先级法不是对每个目标加权，而是按照目标的轻重缓急，将其分为不同等级再求解。 优点：避免了权系数的困扰，绝大多数决策者都能采用，事实上他们在许多决策中也正是这样做的。 例如建设高速公路时，既希望减少开支又希望降低交通伤亡事故，此时能否用金钱来衡量一个人的生命价值呢？ 例如决定人员的提升时，许多单位是按其工作态度、工作能力及对单位的有效价值等这样一个先后顺序来进行评定的。 即没有任何其他方案能在各个方面完全胜出这个解 缺点：难处在于如何确切地定出各个目标的优先顺序以获得满意的求解结果。 有效解（或非劣解）法： 有效解（或非劣解）法“不会产生”象加权法或优先级法所具有的局限性，它将找出全部有效解集（即非劣解）以供决策者从中挑选。 缺点：难处在于实际问题中非劣解太多，难于一一推荐给决策者。 某工厂在计划期内要安排生产Ⅰ、 Ⅱ两种产品，已知有关数据如下表所示： 10 8 利润 元/件 10 2 1 设备台时 hr 11 1 2 原材料 kg 拥有量 Ⅱ Ⅰ 解：这是一个单目标规划问题，可用线性规划模型表述为： 试求获利最大的方案。 例1 利润最大化问题： 目标函数 max z = 8x1+10x2 约束条件 2x1 + x2 ≤11 x1 + 2x2 ≤ 10 x1 , x2 ≥ 0 可用图解法求得最优决策方案为： x1*=4, x2*=3, z*=62 x1 + 2x2 ≤ 10 8x1+10x2=c 6 1 2 3 4 5 2 4 6 8 10 2x1 + x2 ≤11 在实际决策时，还应考虑市场等一系列其他条件，如： （1）市场调查发现：Ⅰ的销量有下降趋势，故应考虑适当减少Ⅰ的产量增加Ⅱ的产量，使Ⅰ＜ Ⅱ （2）原材料的价格不断上涨，增加供应会使成本提高。故不考虑再购买原材料。 （3）为提高效率，应充分利用设备，但不希望加班。 （4）市场虽发生变化，但利润应尽可能达到或超过56元。 此时的决策是多目标决策问题——目标规划方法是解决这类决策问题的方法之一。 硬约束 软约束 与建立目标规划模型有关的概念： 1. 正、负偏差变量d+,d- d+ : 决策值超过目标值的部分 d- ：决策值未达到目标值的部分 恒有 d+×d-=0 2 . 绝对约束、目标约束 绝对约束：必须严格满足的等式或不等式约束 目标约束：目标规划所特有的约束，约束右端项看作要追求的目标值，在达到目标值时，允许发生正或负的偏差 3 . 优先因子与权系数 4 .目标规划的目标函数 min z = f ( d＋, d－ ) 三种基本形式： d－＋d＋ fi(x)＋ d－－d＋ ＝ bi fi(x) ＝ bi d－ fi(x)＋ d－－d＋ ＝ bi fi(x) ≥ bi d＋ fi(x)＋ d－－d＋ ＝ bi fi(x) ≤ bi 需要极小化的偏差变量 目标规划格式 目标类型 2.产品Ⅱ的产量不低于产品Ⅰ的产量 1.原材料供应受严格限制 2x1 + x2 ≤11 硬约束 x1－x2 ＋ d1－－d1＋ ＝0 d1＋ x1 ≤ x2 极小化 例2 例1的目标规划模型： 3.充分利用设备有效台时，不加班 x1＋2x2 ＋ d2－－d2＋ ＝10 d2－＋d2＋ x1＋2x2 ＝ 10 极小化 4.利润额不小于56元 8x1＋10x2＋d3－－d3＋ ＝56 d3－ 8x1＋10x2 ≥ 56 极小化 【毕】 建立基础模型 为每一个理想目标确定期望值 对每一个现实目标和约束都加上正负偏差变量 将目标按其重要性划分优先级，第一优先级为硬约束 建立目标规划函数 反映决策者欲望，如“利润最大” 配上期望值的理想目标 建模步骤小结：