数学建模目标规划方法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,三 目标规划方法,通过前面的介绍和讨论，我们知道，目标规划方法是解决多目标规划问题的重要技术之一。,这一方法是美国学者查恩斯（,A.Charnes,）,和库伯（,W.W.Cooper,）,于,1961,年在线性规划的基础上提出来的。后来，查斯基莱恩（,U.Jaashelainen,）,和李（,Sang.Lee,）,等人，进一步给出了求解目标规划问题的一般性方法,单纯形方法。,目标规划模型,目标规划的图解法,求解目标规划的单纯形方法,目标规划模型,给定若干目标以及实现这些目标的优先顺序，在有限的资源条件下，使总的偏离目标值的偏差最小。,1.,基本思想,：,2.,目标规划的有关概念,例,1,：某一个企业利用某种原材料和现有设备可生产甲、乙两种产品，其中，甲、乙两种产品的单价分别为,8,万元和,10,万元；生产单位甲、乙两种产品需要消耗的原材料分别为,2,个单位和,1,个单位，需要占用的设备分别为,1,单位台时和,2,单位台时；原材料拥有量为,11,个单位；可利用的设备总台时为,10,单位台时。试问：如何确定其生产方案使得企业获利最大？,由于决策者所追求的唯一目标是使总产值达到最大，这个企业的生产方案可以由如下线性规划模型给出：求,x,1,，,x,2,，使,将上述问题化为标准后，用单纯形方法求解可得最佳决策方案为,:,（万元）。,甲,乙,拥有量,原材料,2,1,11,设备,(,台时,),1,2,10,单件利润,8,10,生产,甲、乙两种产品，有关数据如表所示。试求获利最大的生产方案？,但是，在实际决策时，企业领导者必须考虑市场等一系列其它条件，如：,超过计划供应的,原材料,，需用高价采购，这就会使生产,成本增加。,应尽可能地,充分利用设备的有效台时,，但,不希望加班,。,应尽可能,达到并超过计划产值指标,56,万元,。,这样，该企业生产方案的确定，便成为一个多目标决策问题，这一问题可以运用目标规划方法进行求解。,根据市场信息，甲种产品的需求量有下降的趋势，因,此,甲种产品的产量不应大于乙种产品的产量,。,假定有,L,个目标，,K,个优先级,(,K,L,),，,n,个变量。在同一优先级,p,k,中不同目标的正、负偏差变量的权系数分别为,kl,+,、,kl,-,，则多目标规划问题可以表示为：,目标规划模型的一般形式,目标函数,目标约束,绝对约束,非负约束,在以上各式中，,kl,+,、,kl,-,、分别为赋予,p,l,优先因子的第,k,个目标的正、负偏差变量的权系数，,g,k,为第,k,个目标的预期值，,x,j,为决策变量，,d,k,+,、,d,k,-,、分别为第,k,个目标的正、负偏差变量，,目标函数,目标约束,绝对约束,非负约束,目标规划数学模型中的有关概念。,(1),偏差变量,在目标规划模型中，除了决策变量外，还需要引入,正、负偏差变量,d,+,、,d,-,。其中，正偏差变量表示决策值超过目标值的部分，负偏差变量表示决策值未达到目标值的部分。,因为决策值不可能既超过目标值同时又未达到目标值，故有,d,+,d,-,=0,成立。,(2),绝对约束和目标约束,绝对约束,，,必须严格满足的等式约束和不等式约束，譬如，线性规划问题的所有约束条件都是绝对约束，不能满足这些约束条件的解称为非可行解，所以它们是,硬约束,。,目标约束,，,目标规划所特有的，可以将约束方程右端项看作是追求的目标值，在达到此目标值时允许发生正的或负的偏差，可加入正负偏差变量，是,软约束,。,线性规划问题的目标函数，在给定目标值和加入正、负偏差变量后可以转化为目标约束，也可以根据问题的需要将绝对约束转化为目标约束。,(3),优先因子（优先等级）与权系数,一个规划问题,常常有若干个目标，决策者对各个目标的考虑,往往是有主次的。凡要求第一位达到的目标赋予优先因子,p,1,，次位的目标赋予优先因子,p,2,，,，并规定,p,l,p,l,+1,(,l,=1,2,.),表示,p,l,比,p,l,+1,有更大的优先权。,即,:,首先保证,p,1,级目标的实现，这时可以不考虑次级目标；而,p,2,级目标是在实现,p,1,级目标的基础上考虑的；依此类推。,若要区别具有相同优先因子,p,l,的目标的差别就可以分别赋予它们不同的权系数,i,*,(,i,=1,2,k,),。这些优先因子和权系数都由决策者按照具体情况而定。,(3),优先因子（优先等级）与权系数,一个规划问题,常常有若干个目标，决策者对各个目标的考虑,往往是有主次的。凡要求第一位达到的目标赋予优先因子,p,1,，次位的目标赋予优先因子,p,2,，,，并规定,p,l,p,l,+1,(,l,=1,2,.),表示,p,l,比,p,l,+1,有更大的优先权。,即,:,首先保证,p,1,级目标的实现，这时可以不考虑次级目标；而,p,2,级目标是在实现,p,1,级目标的基础上考虑的；依此类推。,(4),目标函数,目标规划的目标函数（准则函数）是,按照各目标约束的正、负偏差变量和赋予相应的优先因子而构造,的。当每一目标确定后，尽可能缩小与目标值的偏离。因此，目标规划的目标函数只能是：,a),要求,恰好达到目标值,，就是正、负偏差变量都要尽可能小,即,b),要求不超过目标值，即允许,达不到目标值,，就是正偏差变量要尽可能小，即,c),要求,超过目标值,，也就是超过量不限，但负偏差变量要尽可能小，即,基本形式有三种：,例,2,：,在例,1,中，如果决策者在原材料供应受严格控制的基础上考虑：首先是甲种产品的产量不超过乙种产品的产量；其次是充分利用设备的有限台时，不加班；再次是产值不小于,56,万元。并分别赋予这三个目标优先因子,p,1,p2,p,3,。试建立该问题的目标规划模型。,分析,:,题目有三个目标层次，包含三个目标值。,第一目标：,p,1,d,1,+,;,即产品,甲,的产量,不大于,乙,的产量。,第二目标：,p,2,(,d,2,+,+,d,2,-,);,即,充分利用设备的有限台时，不加班,；,第三目标：,p,3,d,3,-,;,即产值,不小于,56,万元；,例,2,：在例,1,中，如果,决策者在原材料供应受严格控制的基础上考虑,：首先是甲种产品的产量不超过乙种产品的产量；其次是充分利用设备的有限台时，不加班；再次是产值不小于,56,万元。并分别赋予这三个目标优先因子,p,1,p,2,p,3,。试建立该问题的目标规划模型。,解：,根据题意，这一决策问题的目标规划模型是,例,3,、,某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料如表所示。,(1),试制定生产计划，使获得的利润最大？,120,70,单件利润,3000,10,3,设备台时,2000,5,4,煤炭,3600,4,9,钢材,资源限制,乙,甲,单位 产品,资源 消耗,解,:,设生产甲产品,:,x,1,，,乙产品,:,x,2,(1),若在例,3,中提出下列要求：,1,、完成或超额完成利润指标,50000,元；,2,、产品甲不超过,200,件，产品乙不低于,250,件；,3,、现有钢材,3600,吨必须用完。,试建立目标规划模型。,分析,：,题目有三个目标层次，包含四个目标值。,第一目标：,p,1,d,1,-,第二目标：有两个要求即甲,d,2,+,，乙,d,3,-,，但两个具有相同的优先因子，因此需要确定权系数。本题可用单件利润比作为权系数即,70:120,，化简为,7:12,。,第三目标：,所以目标规划模型为：,图解法同样适用两个变量的目标规划问题，但其操作简单，原理一目了然。同时，也有助于理解一般目标规划的求解原理和过程。,图解法解题步骤如下,：,1,、,确定,各约束条件的,可行域,。即将所有约束条件（包括目标约束和绝对约束，,暂不考虑正负偏差变量,）在坐标平面上表示出来；,2,、在目标约束所代表的边界线上，用箭头,标出正、负偏差变量值增大的方向,；,目标规划的图解法,3,、求满足,最高优先等级目标的解,；,4,、转到,下一个优先等级,的目标，再不破坏所有较高优先等级目标的前提下，求出该优先等级,目标的解,；,5,、重复,4,，直到所有优先等级的目标都已,审查完毕,为止；,6,、确定,最优解,和,满意解,。,例,4,、用图解法求解目标,规划问题,0,1 2 3 4 5 6 7 8,1 2 3 4 5 6,A,x,2,x,1,B,C,由于,d,2,-,取最小，所以，（,2,）线可向上移动，故,B,，,C,线段上的点是该问题的最优解。,例,5,、,已知一个生产,计划的线性规划模型为,其中目标函数为总利润，,x,1,x,2,为产品,A,、,B,产量。,现有下列目标：,1,、要求总利润必须,超过,2500,元；,2,、考虑产品受市场影响，为避免积压，,A,、,B,的生产量不超过,60,件和,100,件,；,3,、由于甲资源供应比较紧张，不要,超过现有量,140,。,试建立目标规划模型，并用图解法求解。,解：,以产品,A,、,B,的单件利润比,2.5:1,为权系数，模型如下：,0,x,2,0,x,1,140,120,100,80,60,40,20,20 40 60 80 100,A,B,C,D,结论：,C(60,58.3),为所求的满意解。,检验：将上述结果带入模型，因,d,1,+,d,1,-,0,；,d,3,+,d,3,-,0,；,d,2,-,=0,，,d,2,+,存在；,d,4,+,0,，,d,4,-,存在。所以，有下式：,minZ,=,将,x,1,60,，,x,2,58.3,带入约束条件，得,3060,1258.3,2499.62500,；,260+58.3=178.3,140,；,160,60,158.3,58.3 100,由上可知：若,A,、,B,的计划产量为,60,件和,58.3,件时，所需甲资源数量将超过现有库存。在现有条件下，此解为非可行解。为此，企业必须采取措施降低,A,、,B,产品对甲资源的消耗量，由原来的,100,降至,78.5,（,140178.3,0.785,），才能使生产方案（,60,，,58.3,）成为可行方案。,求解目标规则的单纯形方法,目标规划模型仍可以用单纯形方法求解，在求解时作以下规定：,因为目标函数都是求最小值，所以，最优判别检验数为：,因为非基变量的检验数中含有不同等级的优先因子，,所以检验数的正、负首先决定于,P,1,的系数,1,j,的正负，若,1,j,=0,，则检验数的正、负就决定于,p,2,的系数,2,j,的正负，,所以检验数的正、负首先决定于,p,1,的系数,1,j,的正、负，若,1,j,=0,，则检验数的正、负就决定于,p,2,的系数,2,j,的正、负，下面可依此类推。,据此，我们可以总结出求解目标规划问题的单纯形方法的计算步骤如下：,建立初始单纯形表，在表中将检验数行按优先因子个数分别排成,L,行，置,l,=1,。,检查该行中是否存在负数，且对应的前,L,-1,行的系数是零。若有，取其中最小者对应的变量为换入变量，转,。若无负数，则转,。,建立初始单纯形表，在表中将检验数行按优先因子个数分别排成,L,行，置,l,=1,。,检查该行中是否存在负数，且对应的前,L,-1,行的系数是零。若有，取其中最小者对应的变量为换入变量，转,。若无负数，则转,。,按最小比值规则（,规则）确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量。,按单纯形法进行基变换运算，建立新的计算表，返回,。,当,l,=,L,时，计算结束，表中的解即为满意解。否则置,l,=,l,+1,，,返回,。,例,4,：,试用,单纯形法,求解例,2,所描述的目标规划问题,.,解,：首先将这一问题化为如下,标准形式,：,取 为初始基变量，列出初始单纯形表。,取,l,=1,，检查检验数的,p,1,行，因该行无负检验数，故转,。,因为,l,=1,L,=3,，置,l,=,l,+1=2,，返回,。,检查发现检验数,p,2,行中有,-1,，,-2,，因为有,min-1,-2=-2,，所以,x,2,为换入变量，转入,。,按,规则计算：，所以,d,2,-,为换出变量，转入,。,进行换基运算，得表,3,。以此类推，直至得到最终单纯形表,4,为止。,表,2,表,3,由表,3,可知，,x,1,*,=2,，,x,2,*,=4,，为满意解。检查检验数行，发现,非基变量,d,3,+,的检验数为,0,，这表明该问题存在多重解。,表,4,在表,3,中，以非基变量,d,3,+,为换入变量，,d,1,-,为换出变量，经迭代得到表,4,。,从表,4,可以看出，,x,1,*,=10/3,，,x,2,*,=10/3,也是该问题的满意解。,