多目标规划2.ppt

第五章多目标规划 1 问题的提出与目标规划的数学模型 2 目标规划的图解分析法 3 用单纯形法求解目标规划 4 求解目标规划的层次算法 5 应用举例 1 问题的提出与目标规划的数学模型 线性规划 整数规划和后面将要学习的动态规划都是解决单个目标函数在一组约束条件下的极值问题 但在许多实际问题中 在一组约束条件下 往往要求实现多个目标 例如 在企业安排生产问题中 既要利润高 又要消耗低 还要考虑市场需求 等等 这些目标的重要性各不相同 目标规划正是为了解决这类多目标规划问题而产生的 它能把决策者的意愿反映到数学模型中去 线性规划问题的局限性 1 要求问题的解必须满足全部约束条件 但实际问题中并非所有约束都需严格满足 2 只能处理单目标的优化问题 因此线性规划模型认为地将一些次要目标转为约束 而实际问题中 目标和约束可以互相转化 处理时不一定严格区分 3 线性规划中各个约束条件都处于同等重要的地位 但实际问题中 各目标的重要性是有差别的 4 线性规划寻求最优解 但很多实际问题中只需找出满意解就可以了 最佳生产计划问题 某工厂计划生产甲 乙两种产品 这两种产品的有关数据如下表所示 一 问题的提出 目标2 超过计划供应的原料时 需要高价采购 使成本增加 因而只采购计划供应的原料 目标3 应尽可能利用现有设备 但不希望加班 目标4 应尽可能达到并超过计划利润指标 56元 这样 在考虑产品生产决策时 不再是单纯追求利润最大 而是同时要考虑多个目标 这样的问题一般的线性规划方法已无法解决 需引入一种新的数学模型 目标规划 二 目标规划模型的建立 1 偏差变量 用来表示实际值与目标值之间的差异 d 超出目标的差值 称为正偏差变量 d 未达到目标的差值 称为负偏差变量 因实际决策值不可能既超过目标值又低于目标值 故最终结果中恒有d d 0 即两者至少有一个为0 目标规划中 一般有多个目标值 每个目标值都相应有一对偏差变量 2 绝对约束和目标约束 绝对约束是指必须严格满足的等式约束或不等式约束 如线性规划问题的所有约束条件 不能满足这些条件的解称为非可行解 所以绝对约束是硬约束 目标约束是目标规划所特有的一种约束 它把要追求的目标值作为右端常数项 在追求此目标值时允许发生正偏差和负偏差 因此 目标约束是由决策变量 正 负偏差变量和要追求的目标值组成的软约束 目标约束不会不满足 但可能偏差过大 绝对约束 问题中的目标2 在原料供应受严格限制的基础上考虑 可写成绝对约束为 假设问题中甲 乙两产品的产量分别为x1和x2 目标约束 问题中的目标4可写成目标约束为 化为标准形式是 线性目标约束的一般形式是 其中 3 优先因子和权系数 目标规划中 当决策者要求实现多个目标时 这些目标之间是有主次区别的 凡要求第一位达到的目标 赋于优先因子p1 要求第二位达到的目标 赋于优先因子p2 并规定pk 1 pk 表示pk比pk 1有绝对优先权 因此 不同的优先因子代表着不同的优先等级 若要区别具有相同优先因子的多个目标 可分别赋予它们不同的权系数 k 越重要的目标 其权系数的值越大 在实现多个目标时 首先保证p1级目标的实现 这时可不考虑其它级目标 而p2级目标是在保证p1级目标值不变的前提下考虑的 以此类推 4 目标函数 目标规划的目标函数是由各目标约束的正 负偏差变量及相应的优先因子 权系数构成的 其中不含决策变量 因为决策者的愿望总是尽可能缩小偏差 实现目标 故总是将目标函数极小化 其基本形式有三种 对于第i个目标 1 若要求决策值超过目标值 则相应的负偏差变量要尽可能地小 而对正偏差变量不加限制 目标函数的形式为 2 允许达不到目标值 就是相应的正偏差变量要尽可能地小 目标函数的形式为 3 恰好达到目标 则相应的正 负偏差变量都要尽可能地小 目标函数的形式为 加入优先因子和权系数后 建立目标函数 其一般形式为 前述问题的目标规划模型可以写为 目标规划的一般数学模型 见教材135 136页 2 目标规划的图解分析法 对于只有两个决策变量的线性目标规划的数学模型 可以用图解法来分析求解 传统的线性规划一般只是寻求一个点 在这个点上得到单目标的最优值 目标规划一般是寻求一个区域 这个区域提供了相互矛盾的目标集的折衷方案 步骤1建立直角坐标系 令各偏差变量为0 作出所有的约束直线 满足所有绝对约束条件的区域 用阴影标出 步骤2作图表示差变量增减对约束直线的影响 在所有目标约束直线旁标上d d 如图所示 这表明目标约束直线可以沿d d 所示的方向平移 步骤3根据目标函数中的优先因子次序 逐步分析求解 根据目标函数中的优先因子次序 首先考虑具有优先因子p1的目标的实现 目标函数要求实现mind1 从图中可见 可以满足d1 0 这时 只能在三角形OBC的区域上取值 考察具有优先因子p2的目标 此时可在线段ED上取值 考察优先因子p3的目标 这就使取值范围缩小到线段GD上 该线段上所有点的坐标 都是问题的解 多目标规划问题的另一类表示方法 解 设购买甲 乙 丙三种糖果的斤数分别为x1 x2 x3 用于买糖所花的钱数为y1 所买糖的总斤数为y2 我们希望y1取最小值 y2取最大值 约束条件可以写为 这是含有两个目标的线性规划问题 这里可以将求y2的最大值转化为求 y2 的最小值 这时目标函数可以写为 其中 3 用单纯形法求解目标规划 目标规划的数学模型与线性规划的数学模型基本相同 因此利用单纯形法求解步骤也基本相同 但是需要尤其注意它们之间的区别 线性规划的单纯形法求解过程 1 建立初始单纯形表 计算出所有变量的检验数 2 在非基变量检验数中找到最大的正数 j 它所对应的变量xj作为换入基的变量 3 对于所有aij 0计算bi aij 其中最小的元素 所对应的基变量xi作为换出基的变量 4 建立新单纯形表 重复上述步骤2 3 直到所有检验数都小于等于零 由于目标规划的目标函数都是求极小化问题 而线性规划问题的标准型中目标函数都是求极大化问题 因此在用单纯形法求解时要注意一些重要的的差别 用单纯形法求解下述目标规划问题 第一步 列出初始单纯形表 并计算检验数 将表格中最后一行检验数按优先级改写为 这是与线性规划单纯形法的第一个差别 对两行检验数需分别进行处理 第二步 确定换入基的变量 在负检验数中 选择最小的一个 j所对应的变量xj作为换入基的变量 在这个问题中第一优先级P1所的检验数中 1是最小的 因此x1为换入基的变量 这是与线性规划单纯形法的第二个差别 在线性规划中是将大于零的检验数中较大的一个对应的变量换入基 这是仅仅因为目标函数取值有极大和极小的差别 对于目标函数取极小的线性规划问题也可以同样进行处理 第三步 确定换出基的变量 对于所有aij 0计算bi aij 其中最小的元素 所对应的基变量xi作为换出基的变量 这与线性规划相同 在这个问题中min bi aij 10 因此d1 为换出变量 换入 换出基的变量确定过程如下表 第四步 用换入变量替换换出变量 进行单纯形法迭代运算 直至优先级P1所对应的检验数全为非负 本例中 第一优先级计算后得 由于优先级P2的检验数仍然有负值 因此可以继续优化 重复上述步骤2 4 确定换入 换出变量 第二点说明 从考察P2行检验数开始 注意应包括更高级别的优先因子在内 如上述问题的进一步单纯形表如下 对应的检验数为P1 3 2 P2 0 对应的检验数为P1 P2 0 对应的检验数为P1 2P2 0 因此上述三种情况都不能选为换入基的变量 这其实与线性规划相同 判别迭代计算停止的准则 1 检验数P1 P2 Pk行的所有值均为非负 2 若P1 P2 Pi行的所有检验数为非负 而Pi 1行存在负检验数 但在负检验数所在列的上面行中有正检验数 不一定是相邻行 只要在起上方即可 4 求解目标规划的层次算法 求解目标规划是从高优先级到低优先级逐层优化的 求解目标规划的层次算法就是根据这样的思想构造的 层次算法步骤 第一步 对目标函数中的P1层次进行优化 建立第一层次的线性规划模型LP1并求解 LP1的目标函数为 LP1的约束条件含原目标规划的所有约束 第二步 对P2层次进行优化 由于下一层次的优化应在前面各层次优化的基础上进行 若第一层次目标函数最优值为z1 则构建的P2层次的线性规划模型LP2 其目标函数为 约束条件除含有原目标规划的所有约束条件之外 由于这一步优化是在前一步优化的基础上进行的 所以前一步优化的结果应成为一个新的约束条件 即约束条件增加了一个式子 小于等于使得上一步的最优值在计算后不会发生改变 第三步 依此类推得到第Ps s 2 层次进行优化时建立的线性规划模型LPs为 当进行到s K时 对Pk层次建立的线性规划模型LPk的最优解即为目标规划问题的满意解 K是某一步 例 用层次算法求解下述目标规划 解 第一层次的优化模型LP1为 利用线性规划的单纯形法对其求解 得 因为z1 0 因此在