运筹学胡运权第04章.ppt

第四章 目标规划 Operational Research ( OR ) 本章内容 目标规划问题及其数学模型 目标规划的图解法 解目标规划的单纯形法 目标规划的灵敏度分析 目标规划应用举例 目标规划问题的导出 例4-1 某工厂生产两种产品，受到原材料供应和设备工时的限制。在单件利润等有关数据已知上网条件下，要求制订一个获利最大的生产计划。具体数据如下： 目标规划问题的导出 目标规划问题的导出 例4-2 假设计划人员被要求考虑如下意见： (1) 由于产品Ⅱ销售疲软，故希望产品Ⅱ的产量不超过产品Ⅰ的一半； (2) 原材料严重短缺，生产中应避免过量消耗； (3) 最好能节约4h设备工时； (4) 计划利润不少于48元。 计划人员需要会同有关各方作进一步的协调，最后达成了一致意见： 原材料使用限额不得突破；产品Ⅱ产量要求必须优先考虑；设备工时问题其次考虑；最后考虑计划利润的要求。 类似这样的多目标决策问题是典型的目标规划问题。 目标规划的数学模型 基本概念 （1）偏差变量 d+≥0， d- ≥0，d+·d-=0 （2）绝对约束和目标约束 （3）优先因子和权系数 （4）目标规划的目标函数 三种基本表达式： ①要求恰好达到目标值 min{f(d++d-)} ②要求不超过目标值，但允许不足目标值 min{f(d+)} ③要求不低于目标值，但允许超过目标值 min{f(d-)} 目标规划的数学模型 例4-1的目标规划表达式为： min{P1d1-,P2d2+,P3d3-} 目标规划的数学模型 目标规划数学模型的一般形式： 目标规划 目标规划问题及其数学模型 目标规划的图解法 解目标规划的单纯形法 目标规划的灵敏度分析 目标规划应用举例 目标规划的图解法 对于只有两个决策变量的目标规划问题，可以用图解方法来求解。 在用图解法解目标规划时，首先必须满足所有绝对约束。在此基础上，再按照优先级从高到低的顺序，逐个地考虑各个目标约束。一般地，若优先因子Pj对应的解空间为Rj，则优先因子Pj+1对应的解空间只能在Rj中考虑，即Rj+1属于Rj。若Rj不空，而Rj+1为空集，则Rj中的解为目标规划的满意解，它只能保证满足P1,P2,…,Pj级目标，而不保证满足其后的各级目标。 目标规划的图解法 例4-3 用图解法解例4-2。 目标规划的图解法 △OAB区域是满足绝对约束和非负条件的解空间。对于所有目标约束，去掉偏差变量，画出相应直线，然后标出偏差变量变化时直线平移方向，见图所示。 首先考虑P1，此时要求min d-1，因而解空间R1为△OAC区域； 再考虑P2，此时要求min d2+，因而解空间R2为△ODC区域； 最后考虑P3，此时要求min d3-，因而解空间R3为四边形EDCF区域。 容易求得E，D，C，F四点的坐标分别为(8,0)、(9,0)、(6,3)、(4.8,2.4)，故问题的解可表示为： 目标规划的图解法 例4-3最后一级目标的解空间非空。这时得到的解能满足所有目标的要求。当解不惟一时(如例4-3，R3为四边形EDCF区域)，决策者在作实际决策时究竟选择哪一个解，完全取决于决策者自身的考虑。 目标规划的图解法 例4-4 用图解法解下面的目标规划 min{P1d1-,P2d2+,P3(5d3-+3d4-),P4d1+} 目标规划的图解法 所以满意解为：x1=6.5，x2=1.25 目标规划 目标规划问题及其数学模型 目标规划的图解法 解目标规划的单纯形法 目标规划的灵敏度分析 目标规划应用举例 解目标规划的单纯形法 目标规划的数学模型实际上是最小化形的线性规划，可以用单纯形法求解。 在用单纯形法解目标规划时，检验数是各优先因子的线性组合。因此，在判别各检验数的正负及大小时，必须注意P1?P2?P3?…。当所有检验数都已满足最优性条件(cj-zj≥0)时，从最终单纯形表上就可以得到目标规划的解。 解目标规划的单纯形法 例4-5 用单纯形法解例4-4。 解目标规划的单纯形法 解目标规划的单纯形法 以d3+为换入变量继续迭代，可得如下单纯形表Ⅴ 解目标规划的单纯形法 结论： 例4-5的解为以上四个满意解(即C，D，E，F四点)的凸组合。而且，从单纯形表Ⅲ，Ⅳ，Ⅴ，Ⅵ中可知，各非基变量检验数中三个优先因子的系数全部非负，这表示任何一个满意解都能满足所有目标的要求。单纯形法和图解法的解题结果完全一致。 目标规划 目标规划问题及其数学模型 目标规划的图解法 解目标规划的单纯形法 目标规划的灵敏度分析 目标规划应用举例 目标规划的灵敏度分析 在目标规划建模时，目标优先级和权系数的确定往往带有一定的主观性，因此，对它们的灵敏度分析是目标规划灵敏度分析的主