多目标规划2.ppt

《多目标规划2.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章多目标规划§1．问题的提出与目标规划的数学模型§2．目标规划的图解分析法§3．用单纯形法求解目标规划§4．求解目标规划的层次算法§5．应用举例§1．问题的提出与目标规划的数学模型线性规划、整数规划和后面将要学习的动态规划都是解决单个目标函数在一组约束条件下的极值问题。但在许多实际问题中，在一组约束条件下，往往要求实现多个目标。例如，在企业安排生产问题中，既要利润高，又要消耗低，还要考虑市场需求，等等。这些目标的重要性各不相同，目标规划正是为了解决这类多目标规划问题而产生的，它能把决策者的意愿反映到数学模型中去。线性

2、规划问题的局限性：1.要求问题的解必须满足全部约束条件，但实际问题中并非所有约束都需严格满足；2.只能处理单目标的优化问题，因此线性规划模型认为地将一些次要目标转为约束。而实际问题中，目标和约束可以互相转化，处理时不一定严格区分；3.线性规划中各个约束条件都处于同等重要的地位，但实际问题中，各目标的重要性是有差别的；4.线性规划寻求最优解，但很多实际问题中只需找出满意解就可以了。最佳生产计划问题某工厂计划生产甲、乙两种产品，这两种产品的有关数据如下表所示。工厂在作决策时，要实现如下的目标：目标1：根据市场信息，产品甲的销售

3、量有下降的趋势，故考虑产品甲的产量不大于产品乙；一、问题的提出目标2：超过计划供应的原料时，需要高价采购，使成本增加，因而只采购计划供应的原料；目标3：应尽可能利用现有设备，但不希望加班；目标4：应尽可能达到并超过计划利润指标(56元)。这样，在考虑产品生产决策时，不再是单纯追求利润最大，而是同时要考虑多个目标，这样的问题一般的线性规划方法已无法解决，需引入一种新的数学模型——目标规划。二、目标规划模型的建立1.偏差变量用来表示实际值与目标值之间的差异。d+——超出目标的差值，称为正偏差变量。d-——未达到目标的差值，称为

4、负偏差变量。因实际决策值不可能既超过目标值又低于目标值，故最终结果中恒有d+·d-=0(即两者至少有一个为0)。目标规划中，一般有多个目标值，每个目标值都相应有一对偏差变量。2.绝对约束和目标约束绝对约束是指必须严格满足的等式约束或不等式约束；如线性规划问题的所有约束条件，不能满足这些条件的解称为非可行解，所以绝对约束是硬约束。目标约束是目标规划所特有的一种约束，它把要追求的目标值作为右端常数项，在追求此目标值时允许发生正偏差和负偏差。因此，目标约束是由决策变量，正、负偏差变量和要追求的目标值组成的软约束。目标约束不会不满

5、足，但可能偏差过大。绝对约束：问题中的目标2，在原料供应受严格限制的基础上考虑，可写成绝对约束为假设问题中甲、乙两产品的产量分别为x1和x2。目标约束：问题中的目标4可写成目标约束为化为标准形式是：线性目标约束的一般形式是：其中：3.优先因子和权系数目标规划中，当决策者要求实现多个目标时，这些目标之间是有主次区别的。凡要求第一位达到的目标，赋于优先因子p1，要求第二位达到的目标，赋于优先因子p2…并规定pk+1∝pk，表示pk比pk+1有绝对优先权。因此，不同的优先因子代表着不同的优先等级。若要区别具有相同优先因子的多个目

6、标，可分别赋予它们不同的权系数k。越重要的目标，其权系数的值越大。在实现多个目标时，首先保证p1级目标的实现，这时可不考虑其它级目标，而p2级目标是在保证p1级目标值不变的前提下考虑的，以此类推。4.目标函数目标规划的目标函数是由各目标约束的正、负偏差变量及相应的优先因子、权系数构成的，其中不含决策变量。因为决策者的愿望总是尽可能缩小偏差，实现目标。故总是将目标函数极小化，其基本形式有三种。对于第i个目标:(1)若要求决策值超过目标值，则相应的负偏差变量要尽可能地小，而对正偏差变量不加限制，目标函数的形式为：(2)允许达

7、不到目标值，就是相应的正偏差变量要尽可能地小，目标函数的形式为：(3)恰好达到目标，则相应的正、负偏差变量都要尽可能地小，目标函数的形式为：加入优先因子和权系数后，建立目标函数，其一般形式为：前述问题的目标规划模型可以写为：目标规划的一般数学模型，见教材135~136页。§2．目标规划的图解分析法对于只有两个决策变量的线性目标规划的数学模型，可以用图解法来分析求解。传统的线性规划一般只是寻求一个点，在这个点上得到单目标的最优值，目标规划一般是寻求一个区域，这个区域提供了相互矛盾的目标集的折衷方案。步骤1建立直角坐标系，令各

8、偏差变量为0，作出所有的约束直线。满足所有绝对约束条件的区域，用阴影标出。步骤2作图表示差变量增减对约束直线的影响在所有目标约束直线旁标上d+，d-，如图所示。这表明目标约束直线可以沿d+，d-，所示的方向平移。步骤3根据目标函数中的优先因子次序，逐步分析求解。根据目标函数中的优先因子次序，首先考虑具有