目标规划的图解法.ppt

第二节目标规划的图解法 由于目标规划是在线性规划的基础上建立 并弥补了部分不足 所以两种规划模型结构没有本质区别 解法也非常类似 形式上的区别主要在于 线性规划只能处理一个目标 而目标规划能统筹兼顾地处理多个目标关系 以求得切合实际需求的解 线性规划是求满足所有约束条件的最优解 而目标规划是要在多个目标或约束条件下找到尽量好的满意解 线性规划的约束条件是不分主次地同等对待 而目标规划可根据实际需要给予轻重缓急的考虑 关于最优解 线性规划是在可行解域内寻找某一点 使单个目标达到最优值 最大值或最小值 而目标规划是在可行域内 首先寻找到一个使P1级目标均满足的区域R1 然后再在R1中寻找一个使P2级目标均满足或尽最大可能满足的区域R2 R1 再在R2中寻找一个满足P3的各目标的区域R3 R2 R1 如此下去 直到寻找到一个区域Rk Rk 1 R1 满足Pk级的各目标 这个Rk即为所求的解域 如果某一个Ri 1ik 已退化为一点 则计算终止 这一点即为满意解 它只能满足P1 Pi级目标 而无法进一步改进 当然 此时或许有低于Pi级目标被满足 这纯属巧合 目标规划图解法的具体演算过程与线性规划图解法类似 第1步 根据决策变量 当然不能多于2个 绘画所有 软 硬 约束条件的直线图形 偏差变量以移动 平移 直线的方法加以考虑 第5步 重复第3 4步过程 直到解区域Ri减少到一点或满足了所有k个级别的目标为止 此时 Rk即为这个目标规划的最优解区域 其中的任何一点均为目标规划的满意解 第2步 对P1级的各目标 确定解区域R1 第3步 对下一个优先级别Pi级各目标 确定它的最优解空间Ri 但必须是Ri Ri 1 i 2 3 第4步 在这个过程中 如果某解区域Ri减小到一点 则可结束这个过程 因为此时没有进一步改进的可能 例5求解下面目标规划 解将约束方程以直线形式画在图上 这里只使用决策变量 即 偏差变量在画直线时被去掉 直线画好后 在该直线上标出目标函数中与该直线相关的偏差变量增大时直线的平移方向 用垂直于直线的箭头来反映 如图3 2 l1 l2 l3 l4 o A B C D E F x1 x2 R3 图3 2图解法示意图 再考虑P2级目标 要求目标越小越好 因而解空间R2为 OCD区域 按优先级高低 首先考虑P1级目标 要求目标越小越好 就在绝约束的可行解域 OAB中进一步缩小为 OAC 记作R1 R1 R2 最后考虑P3级 此时要求目标越小越好 由图3 2可知R3为四边形CDEF区域 这个区域内的任一点均是该问题的满意解 可使目标函数 由于C D E F坐标分别为 6 3 9 0 8 0 4 8 2 4 故满意解可表示为 其中 这种满足所有目标要求的情况 即 在实际中并不多见 很多目标规划问题只能满足前面几级目标要求 例6用图解法求解下面目标规划问题 解作图3 3 R1 10 0 图3 3图解法示意图 A B 考虑P2级目标 由于直线l2与R1不相交 所以在R1内无法使因此在不退化P1级目标时 不可能使P2级目标完全满足 这样R2就缩为一点 因为在R1中 使达到最小的为A点 所以 x 10 0 由于R2仅含有一个点 所以对P3级目标 我们已经无法进一步的选择与考虑 可求得 即目标函数为 此例中 之所以产生解域R2退缩为一个点 从而无法使P2 P3级目标达成 是因为P2级目标的期望值定得过高 如果将它的目标值从26降到14 则可考虑到P3级目标 见图3 4 满足P1 P2级目标的可行解域为R2 R1 R2 R3 使P1 P2 P3级目标完全满足 这时问题的满意解不唯一 一般地 目标要求确定得越低 可供选择的解越多 目标定得太高 满意解的选择余地也越小 甚至一些低级别的目标无法实现 进一步考察P3级目 标可得最优解区域R3 对该区域中任意一点 均同时能 图3 4 例6求解下面目标规划 用图解法求解 见图4 2 从图4 2中看到 在考虑具有P1 P2的目标实现后 x1 x2的取值范围为ABCD 考虑P3的目标要求时 因d3 的权系数大于d4 故先考虑mind3 这时x1 x2的取值范围缩小为ABEF区域 然后考虑d4 在ABEF中无法满足d4 0 因此只能在ABEF中取一点 使d4 尽可能小 这就是E点 故E点为满意解 其坐标为 24 26 注意 在目标规划中 考虑低级别目标时 不能破坏已经满足的高级别目标 这是基本原则 但它并不是说 当某一高级别目标不可能满足时 其后的低级别目标就一定不能满足 而是在有些目标规划中 当某一优先级的目标不能满足时 其后的某些低级别目标仍可能被满足 例3 5用图解法求解目标规划 H I D P1级目标 线段AB P1 P2级目标 线段HI 故I点为最优解 P1 P2 P3级目标 H点 25 15 I点 37 5 7 5 I x1 x2 l1 l2 O C B A l3 D l4 1 l1与l2形成的可行域OABC 2 先满足P1 OD线段 E 3 再满足P2 ED线段 满意解 E 500 11 500 11 D 360 7 360 7 150 50 100 50 100 150 小结 第一节目标规划的基本概念与数学模型 一 问题的提出 二 目标规划的基本概念 1 决策变量与偏