目标规划的图解法.ppt

1、第二节 目标规划的图解法,由于目标规划是在线性规划的基础上建立，并弥补了部分不足所以两种规划模型结构没有本质区别，解法也非常类似形式上的区别主要在于：线性规划只能处理一个目标，而目标规划能统筹兼顾地处理多个目标关系，以求得切合实际需求的解；线性规划是求满足所有约束条件的最优解，而目标规划是要在多个目标或约束条件下找到尽量好的满意解；线性规划的约束条件是不分主次地同等对待，而目标规划可根据实际需要给予轻重缓急的考虑,关于最优解：线性规划是在可行解域内寻找某一点，使单个目标达到最优值（最大值或最小值）而目标规划是在可行域内，首先寻找到一个使P1级目标均满足的区域R1，然后再在R1中寻找一个使P2级

2、目标均满足或尽最大可能满足的区域R2（R1），再在R2中寻找一个满足P3的各目标的区域R3（R2R1），,如此下去，直到寻找到一个区域Rk(Rk-1R1)，满足Pk级的各目标，这个Rk即为所求的解域，如果某一个Ri (1 i k)已退化为一点，则计算终止，这一点即为满意解，它只能满足P1,，Pi 级目标，而无法进一步改进，当然，此时或许有低于Pi级目标被满足，这纯属巧合,目标规划图解法的具体演算过程与线性规划图解法类似,第1步：根据决策变量（当然不能多于2个）绘画所有（软、硬）约束条件的直线图形，偏差变量以移动（平移）直线的方法加以考虑,第5步：重复第3、4步过程，直到解区域Ri 减少到一点或

3、满 足了所有k个级别的目标为止，此时，Rk 即为这个目标规划的最优解区域，其中的任何一点均为目标规划的满意解,第2步：对P1级的各目标，确定解区域R1,第3步：对下一个优先级别Pi 级各目标，确定它的最优解空间Ri ，但必须是Ri Ri-1 ( i=2,3,),第4步：在这个过程中，如果某解区域Ri 减小到一点，则 可结束这个过程，因为此时没有进一步改进的可能,例5 求解下面目标规划:,解将约束方程以直线形式画在图上，这里只使用决策变量（即 ），偏差变量在画直线时被去掉，直线画好后，在该直线上标出目标函数中与该直线相关的偏差变量增大时直线的平移方向（用垂直于直线的箭头来反映）如图3-2,l1,

4、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)， 故满意解可表示为：,其中：,这种满足所有目标要求的情况，即： ，在实际中并不多见，很多

5、目标规划问题只能满足前面几级目标要求,例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，则可

6、考虑到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，故先考虑min d3；这时x1、x2的取值范围缩小为ABEF区域。然后考虑

7、d4。在ABEF中无法满足d4=0，因此只能在ABEF中取一点，使d4尽可能小，这就是E点。故E点为满意解。其坐标为(24，26)，,注意：在目标规划中，考虑低级别目标时，不能破坏已经满足的高级别目标，这是基本原则但它并不是说，当某一高级别目标不可能满足时，其后的低级别目标就一定不能满足而是在有些目标规划中，当某一 优先级的目标不能 满足时，其后的某 些低级别目标仍可 能被满足,#,例3.5 用图解法求解目标规划,H,I,D,P1级目标： 线段AB：,P1P2级目标： 线段 HI：,故I点为最优解。,P1P2+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,小 结,第一节 目标规划的基本概念与