目标规划——建模与图解法.ppt

第5章，目标规划，本章内容要点，目标规划的基本特征，基本概念和模型目标规划图解目标规划的简单形式，第5章目标规划，实践中，人们常遇到多目标数学规划问题，目标规划(goalprogramming )，是一种多目标规划方法。 目标规划在实践中的应用十分广泛，其重要特征是各目标的逐步加权和逐步优化，这符合人们分别保证处理问题的优先级和优先级的思路。 提出目标规划问题，例如5.1某公司在一条生产线上生产两个产品a和b，每周生产线运行时间为60小时，一个a产品生产需要4小时，一个b产品生产需要6小时。 据市场预测，a、b产品的平均销售量分别为每周9、8台，它们的销售利润分别为12、18万元。 在制定生产计划时，经理要考虑以下四个目标。 首先，产量不得超过市场预测的需求，其次是工人加班时间最少的第三，希望总利润达到最大，最后为了尽可能满足市场需求，如果不满足，市场认为b产品的重要性是a产品的2倍。 试论该问题的数学模型，问题分析以总收益为最大目标，假设产量不超过市场预测的销售量，工人加班时间最小，尽可能满足市场需求的目标为制约，单目标线性规划模型：决策变量x1， 以x2分别为产品a的b的产量maxz=12 x 118 x2s.t.4 x 16x 260 x 19 x 28 x 1，x20，上述线性规划的最佳解在从(9，4 ) t到(3，8 ) t的线段上，最佳目标值为z*=180，有几个选择。 事实上，这一结果并没有完全满足决策者的要求，只实现了经理的第一至第三个目标，而没有实现最后的目标。 进一步分析，实现总体目标是不可能的。 目标规划建模，首先，例5.1的4个目标表示为不等式。 将x1、x2分别作为产品a、b产量. 第一个目标是：x19，x28，第二个目标是：4x1 6x260。第三个目标是：总收益最大，需要找到目标的上界来表示不等式，在此可以推断为252(=129 188 )。 有12x1 18x2252的第四个目标是：x19，x28。目标规划模型的基本概念，(1)正、负偏差变量d，d-我们表示正偏差变量d中决策值超过目标值的部分，负偏差变量d-决策值小于目标值的部分。 由于决策值即使超过目标值也不能最终达到目标值，因此常常将绝对约束和目标约束分为两部分：绝对约束和目标约束。 绝对约束：是指必须严格满足的等式约束和不等式约束的硬约束。 某原材料的数量有限制，无法从其他途径补充的情况下，构成绝对的制约。 目标制约：目标计划特有，我们可以将制约右端的项目视为应追求的目标值，但允许正式的负偏差，通过在制约上加上正、负偏差变量来表现，称为软制约。 根据分析，我们导入以下目标约束x1d1-d1=9(5-1) x2d2-d2=8(5-2) x1x6x2d3-d3=60 (5-3) 12 x1x 18 x4-d4=252 (5-4)、(3)具有优先级因子和权重系数的优先级因子Pi，I=1，2，l . fL，将请求实现第一位的目标分配给优先因子P1，将第二位的目标分配给优先因子P2，分配给优先因子P2，PiPi 1，I=1，2，L-1 .Pi的含义：保证第一位的实现，并且不必考虑第二位的目标。P2级目标考虑到实现P1级目标，依此类推。 如果需要区分具有相同优先级系数的若干目标之间的差异，则可以给出不同的加权系数wj。(4)目标规划目标函数由各目标制约的正、负偏差变量和相应的优先顺序构筑，决策者的要求是尽可能减小偏离目标的数值. 因此，目标计划的目标函数应该求出minf=f(d，d-)极小，目标函数的基本形式有3种： (1)要求正确地达到目标值，对应的目标制约的正、负偏差变量也必须尽可能小。 此时要求取min (d-d-) (2)不超过目标值，对应的目标约束的正偏差变量尽量小。 此时设为min(d )的(3)要求为目标值以上，对应的目标约束的负的偏差变量尽可能小。 此时取min(d-)，关于例7.1，根据决策者想法得知第一优先级请求min(d1 d2)的第二优先级请求min(d3)第三优先级请求min(d4- )或第四优先级请求min(d1- 2d2- )，在此，在不满足市场需求的情况下，市场是b产品的重要性是a产品的2倍也就是说，因为减少b产品的影响是a产品的2倍，所以导入了2:1的加权系数。 目标计划模型minf=p1(d1d2) p2d3p3d4- p4(d1-2d2- ) s.t.x1d1-d1=9x2d2-d2=84 x 16x3-d3=60 (5-5) 12 x 118 x2d4-d4=252 x 1，x2，di-，di0，I=1，2，34.目标计划5.2目标规划的几何意义和图解法，对于只有两个决策变量的目标规划数学模型，可以用图解法求解。 图解示例包括诸如目标规划中的优先级因子、正、负偏差变量和加权因子等的几何意义。 另外，用图式解法求例5-1时，首先在平面直角坐标系的第一象限内(x0 )，生成与各约束条件对应的直线，然后在这些直线的旁边分别标记为G-i、I=1、2、3、4。 在图6中，x和y的每一个通过-表示表示问题例子5.1中的x-1和x-2的直线移动，并且函数值变大和变小的方向，并且这些值变为正负偏差变量di和di-(图5-1中所示)。 从目标函数的优先因子分析中求解：首先考虑实现一级具有P1优先因子的目标，要求目标函数实现min(d1 d2)，d1=d2=0.图52的阴影部分表示其最优解集合的所有点。 我们在第一等级目标的最佳解集合中寻找满足第二优先级要求min(d3)的最佳解，设d3=0，则得到图5-3的阴影部分满足第一、第二优先级要求的最佳解集合。 此外，如从图5-2、图5-3、以及第三优先级要求min(d4- )可以得到图5-4的两个投影部分的交线(粗线)，其表示满足第一、第二和第三优先级要求的最佳解集合，而d4-不能取0值，而是取d4-最小值72。 第4优先级要求min(d1- 2d2- )在粗线段中找到最佳解. 因为d1-的加权因子小于d2-，所以这里设定d2-=0。 因此，最佳解为a点x1=3、x2=8，d1-=6。 图5-4，5.3目标计划计算机利用软件依次求出目标优先级：第1步骤：将原问题的P1级目标作为目标函数，求出将原约束作为问题的约束求解的第k步骤的解的步骤：第k 1步骤：将原问题的Pk 1级目标作为目标函数，求出上位级别的约束的上位级别的解范例：目标计划模型minf=p1(d1d2) p2d3p3d4- p4(d1-2d2- ) s.t.x1d1-d1=9x2d2-d2=84 x1x6x3-d3=6012 x 118x4-d4=252 x 1，x2，di-，di0，I=1，2， 3 4.在计算机中求解，在第一步中依次线性规划模型minf=d1d2s.t.x1 D1- D1=9x2d2-D2=84 x 16x 2d3-D3=6012 x 118 x 2d4-D4=252 x1，x2，di-，di0，I=1，2，3， 4 .分辨率： d1=d2=0在第二步中，下一线性规划模型minf=d3s.t.x1d1-d1=9x2d2-d2=84 x 16x2d3-d3=6012 x 118 x2d4-d4=252 d1=0，d2=0x1，x2，di-，di0，I=1，2，3， 4 .解： d3=0阶三阶线性规划模型minf=d4- s.t.x1d1-d1=9x2d2-d2=84 x 16x2d3-d3=6012 x 118 x2d4-d4=252 d1=