运筹学第三版第四章目标规划课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第四章 目标规划,Operational Research,( OR ),本章内容,目标规划问题及其数学模型,目标规划的图解法,解目标规划的单纯形法,目标规划的灵敏度分析,目标规划应用举例,目标规划问题的导出,例,4-1,某工厂生产两种产品，受到原材料供应和设备工时的限制。在单件利润等有关数据已知上网条件下，要求制订一个获利最大的生产计划。具体数据如下：,产品,限量,原材料（,kg/,件）,5,10,60,设备工时（,h/,件）,4,4,40,利润（元,/,件）,6,8,解得，最优解,x,1,=8,，,x,2,=2,，,max z=64,（元）,目标规划问题的导出,一般来说，一个计划问题可能要满足多方面得要求。,线性规划有最优解的必要条件是其可行解集非空，即各约束条件彼此相容。但实际问题有时不能满足这样的要求。,线性规划解得可行性和最优性具有十分明确的意义，但那都是针对特定数学模型而言的。实际中，决策者需要计划人员提供的不是严格的数学上的最优解，而是可以帮助作出最优决策的参考性计划，或是提供多种计划方案，供最终决策时选择。,例,4-2,假设计划人员被要求考虑如下意见：,(1),由于产品,销售疲软，故希望产品,的产量不超过产品,的一半；,(2),原材料严重短缺，生产中应避免过量消耗；,(3),最好能节约,4h,设备工时；,(4),计划利润不少于,48,元。,计划人员需要会同有关各方作进一步的协调，最后达成了一致意见： 原材料使用限额不得突破；产品,产量要求必须优先考虑；设备工时问题其次考虑；最后考虑计划利润的要求。,类似这样的多目标决策问题是典型的目标规划问题。,目标规划问题的导出,目标规划的数学模型,基本概念,（,1,）偏差变量,正偏差变量,d,+,表示决策值超过目标值的部分；,负偏差变量,d,-,表示决策值未达到目标值的部分；,d,+,0,，,d,-,0,，,d,+,d,-,=0,（,2,）绝对约束和目标约束,绝对约束就是必须要满足的约束条件，如线性规划中的约束条件。绝对约束是硬约束，对它的满足与否决定了解的可行性。,目标约束是目标规划特有的概念，是一种软约束，目标约束中决策值之间的差异用偏差变量表示。,目标规划的数学模型,基本概念,（,3,）优先因子和权系数,一个规划问题常常有若干目标。但决策者在要求达到这些目标时，是主次或轻重缓急的不同。要求第一位达到的目标赋予优先因子,P,1,，次位的目标赋予优先因子,P,2,，,，并规定,P,k, P,k+1,，,k=1,，,2,，,，,K,。表示,P,k,比,P,k+1,有更大的优先权。即首先保证,P,1,级目标的实现，这时可不考虑次级目标；而,P,2,级目标是在实现,P,1,级目标的基础上考虑的；依此类推。这是绝对差别。,若要区别具有相同优先因子的两个目标的差别，这时可分别赋予他们不同的权系数,w,j,，这种差别是相对的。,目标规划的数学模型,基本概念,（,4,）目标规划的目标函数,目标规划的目标函数由各目标约束的偏差变量及相应的优先因子和权系数构成。当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值。因此目标规划的目标函数只能是极小化,m,inz =f(d,+,，,d,-,),。,三种基本表达式：,要求恰好达到目标值，即正、负偏差变量都要尽可能地小,minf(d,+,+d,-,),或者,m,inz = f(d,+,+d,-,),要求不超过目标值，即允许达不到目标值，就是正偏差变量要尽可能地小,minf(d,+,),或者,m,inz = f(d,+,),要求不低于目标值，但允许超过目标值，即超过量不限，但是必须是负偏差变量要尽可能地小,minf(d,-,),或者,m,inz = f(d,-,),目标规划的数学模型,例,4-1,的目标规划表达式为：,minP,1,d,1,-,P,2,d,2,+,P,3,d,3,-,绝对约束,目标约束,P,1,为两种产品产量要求的优先因子；,P,2,为节约工时要求的优先因子；,P,3,为计划利润要求的优先因子，它们应满足,P,1,P,2,P,3,目标规划的数学模型,目标规划数学模型的一般形式：,g,k,为第,k,个目标约束的预期目标值，,W,lk,-,和,W,lk,+,为,P,l,优先因子对应各目标的权系数。,目标规划的案例,例,1,：,某工厂生产,，,两种产品，已知有关数据见下表。试求获利最大的生产方案。,产品,限量,原材料（,kg/,件）,2,1,11,设备（,hr/,件）,1,2,10,利润（元,/,件）,8,10,解得，最优解,x,1,=4,，,x,2,=3,，,max z=62,（元）,但实际上工厂在做决策时，要考虑市场等一系列其他条件：,(1),根据市场信息，产品,的销售量有下降趋势，故考虑产品,的产量不大于产品,；,(2),超过计划供应的原材料时，需用高价采购，会使成本大幅度增加；,(3),应尽可能充分利用设备台时，但不希望加班；,(4),应尽可能达到并超过计划利润指标,56,元。,在单目标规划问题的基础上，决策者在原材料受严格限制的条件下考虑：首先是产品,的产量不低于产品,的产量；其次是充分利用设备有效台时，不加班；再次是利润额不小于,56,元。求决策方案。,目标规划的案例,目标规划,目标规划问题及其数学模型,目标规划的图解法,解目标规划的单纯形法,目标规划的灵敏度分析,目标规划应用举例,目标规划的图解法,对于只有两个决策变量的目标规划问题，可以用图解方法来求解。,在用图解法解目标规划时，首先必须满足所有绝对约束。在此基础上，再按照优先级从高到低的顺序，逐个地考虑各个目标约束。一般地，若优先因子,P,j,对应的解空间为,R,j,，则优先因子,P,j+1,对应的解空间只能在,R,j,中考虑，即,R,j+1,属于,R,j,。若,R,j,不空，而,R,j+1,为空集，则,R,j,中的解为目标规划的满意解，它只能保证满足,P,1,P,2,P,j,级目标，而不保证满足其后的各级目标。,目标规划的图解法,例,4-3,用图解法解例,4-2,。,R1,R2,OAB,区域是满足绝对约束和非负条件的解空间。对于所有目标约束，去掉偏差变量，画出相应直线，然后标出偏差变量变化时直线平移方向，见图所示。,首先考虑,P,1,，此时要求,min d,-1,，因而解空间,R,1,为,OAC,区域；,再考虑,P,2,，此时要求,min d,2,+,，因而解空间,R,2,为,ODC,区域；,最后考虑,P,3,，此时要求,min d,3,-,，因而解空间,R,3,为四边形,EDCF,区域。,容易求得,E,，,D,，,C,，,F,四点的坐标分别为,(8,0),、,(9,0),、,(6,3),、,(4.8,2.4),，故问题的解可表示为：,1,(8,0)+ ,2,(9,0)+ ,3,(6,3)+ ,4,(4.8,2.4),=(8,1,+9,2,+6,3,+4.8,4, 3,3,+2.4,4,),其中，,1,，,2,，,3,，,4,0,，,1,+ ,2,+ ,3,+ ,4,=1,目标规划的图解法,例,4-3,最后一级目标的解空间非空。这时得到的解能满足所有目标的要求。当解不惟一时,(,如例,4-3,，,R,3,为四边形,EDCF,区域,),，决策者在作实际决策时究竟选择哪一个解，完全取决于决策者自身的考虑。,目标规划的图解法,例,4-4,用图解法解下面的目标规划,minP,1,d,1,-,P,2,d,2,+,P,3,(5d,3,-,+3d,4,-,),P,4,d,1,+,目标规划的图解法,所以满意解为：,x1=6.5,，,x2=1.25,目标规划的图解法,例,4-4,得到的解不能满足所有目标。这时，我们要做的是寻找满意解，使它尽可能满足高级别的目标，同时又使它对那些不能满足的较低级别目标的偏离程度尽可能的小。,必须注意的是，在考虑低级别目标时，不能破坏已经满足的高级别目标，这是目标规划的基本原则。但是，也不能因此而以为，当高级别目标不能满足时，其后的低级别目标也一定不能被满足。事实上，在有些目标规划中，当某一优先级的目标不能满足时，其后的某些低级别目标仍有可能被满足。,目标规划,目标规划问题及其数学模型,目标规划的图解法,解目标规划的单纯形法,目标规划的灵敏度分析,目标规划应用举例,解目标规划的单纯形法,目标规划的数学模型实际上是最小化形的线性规划，可以用单纯形法求解。,在用单纯形法解目标规划时，检验数是各优先因子的线性组合。因此，在判别各检验数的正负及大小时，必须注意,P,1,P,2,P,3,。当所有检验数都已满足最优性条件,(c,j,-z,j,0),时，从最终单纯形表上就可以得到目标规划的解。,解目标规划的单纯形法,例,4-5,用单纯形法解例,4-4,。,引入松弛变量,x3,，,min P,1,d,1,-,P,2,d,2,+,P,3,d,3,-,c,j,0,0,0,P1,0,0,P2,P3,0,C,B,x,B,b,x,1,x,2,x,3,d,1,-,d,1,+,d,2,-,d,2,+,d,3,-,d,3,+,0,x,3,60,5,10,1,0,0,0,0,0,0,P,1,d,1,-,0,1,-2,0,1,-1,0,0,0,0,0,d,2,-,36,4,4,0,0,0,1,-1,0,0,P,3,d,3,-,48,6,8,0,0,0,0,0,1,-1,z,j,-c,j,P,1,-1,2,0,0,1,0,0,0,0,P,2,0,0,0,0,0,0,1,0,0,P,3,-6,-8,0,0,0,0,0,0,1,0,x,3,60,0,20,1,-5,5,0,0,0,0,0,x,1,0,1,-2,0,1,-1,0,0,0,0,0,d,2,-,36,0,12,0,-4,4,1,-1,0,0,P,3,d,3,-,48,0,20,0,-6,6,0,0,1,-1,z,j,-c,j,P,1,0,0,0,1,0,0,0,0,0,P,2,0,0,0,0,0,0,1,0,0,P,3,0,-20,0,6,-6,0,0,0,1,0,x,3,12,0,0,1,1,-1,0,0,-1,1,0,x,1,24/5,1,0,0,2/5,-2/5,0,0,1/10,-1/10,0,d,2,-,36/5,0,0,0,-2/5,2/5,1,-1,-3/5,3/5,P,3,x,2,12/5,0,1,0,-3/10,3/10,0,0,1/20,-1/20,z,j,-c,j,P,1,0,0,0,1,0,0,0,0,0,P,2,0,0,0,0,0,0,1,0,0,P,3,0,0,0,0,0,0,0,1,0,解目标规划的单纯形法,在单纯形表,中，由于非基变量,d,1,+,和,d,3,+,的检验数都是零，故知例,4-4,有多重最优解,(,满意解,),。,以,d,1,+,为换入变量继续迭代，可得如下单纯形表,c,j,0,0,0,P,1,0,0,P,2,P,3,0,C,B,x,B,b,x,1,x,2,x,3,d,1,-,d,1,+,d,2,-,d,2,+,d,3,-,d,3,+,0,x,3,20,0,10/3,1,0,0,0,0,-5/6,5/6,P,1,x1,8,1,4/3,0,0,0,0,0,1/6,-1/6,0,d,2,-,4,0,-4/3,0,0,0,1,-1,-2/3,2/3,P,3,d,1,+,8,0,10/3,0,-1,1,0,0,1/6,-1/6,c,j,-z,j,P,1,0,0,0,1,0,0,0,0,0,P,2,0,0,0,0,0,0,1,0,0,P,3,0,0,0,0,0,0,0,1,0,解目标规划的单纯形法,以,d,3,+,为换入变量继续迭代，可得如下单纯,形表,c,j,0,0,0,P,1,0,0,P,2,P,3,0,C,B,C,B,b,x,1,x,2,x,3,d,1,-,d,1,+,d,2,-,d,2,+,d,3,-,d,3,+,0,d,3,+,12,0,0,1,1,-1,0,0,-1,1,P,1,x,1,6,1,0,1/10,1/2,-1/2,0,0,0,0,0,d,2,-,0,0,0,-3/5,-1,1,1,-1,0,0,P,3,x,2,3,0,1,1/20,-1/4,1/4,0,0,0,0,c,j,-z,j,P,1,0,0,0,1,0,0,0,0,0,P,2,0,0,0,0,0,0,1,0,0,P,3,0,0,0,0,0,0,0,1,0,解目标规划的单纯形法,解目标规划的单纯形法,结论：,例,4-5,的解为以上四个满意解,(,即,C,，,D,，,E,，,F,四点,),的凸组合。而且，从单纯形表,，,，,，,中可知，各非基变量检验数中三个优先因子的系数全部非负，这表示任何一个满意解都能满足所有目标的要求。单纯形法和图解法的解题结果完全一致。,目标规划,目标规划问题及其数学模型,目标规划的图解法,解目标规划的单纯形法,目标规划的灵敏度分析,目标规划应用举例,目标规划的灵敏度分析,在目标规划建模时，目标优先级和权系数的确定往往带有一定的主观性，因此，对它们的灵敏度分析是目标规划灵敏度分析的主要内容。目标规划灵敏度分析的方法、原理同线性规划的灵敏度分析本质上相同。,例,4-6,对例,4-4,的目标规划问题，已求得满意解为,x,1,=13/2,x,2,=5/4,。现决策者想知道，目标函数中各目标的优先因子和权系数对最终解的影响。为此，提出了下面两个灵敏度分析问题，即目标函数分别变为：,(1) minP,1,d,1,-,P,2,d,2,+,P,3,d,1,+,P,4,(5d,3,-,+3d,4,-,),(2) minP,1,d,1,-,P,2,d,2,+,P,3,(W,1,d,3,-,+W,2,d,4,-,),P,4,d,1,+, (W,1,W,2,0),目标规划的灵敏度分析,解 目标函数的变化仅影响原解的最优性，即各变量的检验数。因此，应当先考察检验数的变化，然后再作适当的处理。,1.,当目标函数变为（,1,），就是要了解交换第三和第四优先级目标对原解的影响。此时，单纯形表变为下表：,c,j,0,0,P,1,P,3,0,P,2,5P,4,0,3P,4,0,C,B,x,B,b,x,1,x,2,d,1,-,d,1,+,d,2,-,d,2,+,d,3,-,d,3,+,d,4,-,d,4,+,0,x,1,13/2,1,0,0,0,1/2,-1/2,1/2,-1/2,0,0,P,3,d,1,+,3,0,0,-1,1,1,-1,0,0,0,0,3P,4,d,4,-,3/4,0,0,0,0,-1/4,1/4,1/4,-1/4,1,-1,0,x,2,5/4,0,1,0,0,1/4,-1/4,-1/4,1/4,0,0,c,j,-z,j,P,1,0,0,1,0,0,0,0,0,0,0,P,2,0,0,0,0,0,0,0,0,0,0,P,3,0,0,1,0,-1,1,0,0,0,0,P,4,0,0,0,0,3/4,-3/4,17/4,3/4,0,3,目标规划的灵敏度分析,可见，原解最优性已被破坏,(d,2,-,的检验数,-P,3,+3/4P,4,0,，即,W,1,/W,2,1/4,时，原解不变，仍为,x,1,=13/2,x,2,=5/4,当,W,1,/W,2,1/4,时，原解改变。用单纯形法继续求解，可得新的满意解,x,1,=5,x,2,=2(,此时，,d,3,-,=3,d,4,-,=0),当,W,1,/W,2,=1/4,时，两个解均为满意解。,目标规划的灵敏度分析,第三优先级两目标权系数的改变有可能会影响所得的满意解。解的变化取决于两目标权系数的比值,W,1,/W,2,，其临界点为,1/4,。,事实上，在前两优先级目标均已被满足的条件下，如满足,d,3,-,=0,，则使,d,4,-,=3/4,；如满足,d,4,-,=0,，则使,d,3,-,=3,。,d,4,-,/d,3,-,=1/4,。,如将,W,1,/W,2,看作同一优先级下两目标重要程度的比较，而将,d,4,-,/d,3,-,看作因此而引起的不满足程度的比较，则两者的一致恰好说明了目标规划中权系数的作用和意义。,目标规划,目标规划问题及其数学模型,目标规划的图解法,解目标规划的单纯形法,目标规划的灵敏度分析,目标规划应用举例,目标规划应用举例,例,8,有三个产地向四个销地供应物资。产地,A,i,(i=1,2,3),的供应量,a,i,、销地,B,j,(j=1,2,3,4),的需要量,b,j,、各产销地之间的单位物资运费,c,ij,见表。表中，,a,i,和,b,j,的单位为,t,，,c,ij,的单位为元,t,。编制调运方案时要求按照相应的优先级依次考虑下列,7,项目标：,P,1,: B,4,是重点保证单位，其需要量应尽可能全部满足；,P,2,: A,3,向,B,1,提供的物资不少于,100t,；,P,3,:,每个销地得到的物资数量不少于其需要量的,80%,；,P,4,:,实际的总运费不超过当不考虑,P,1,至,P,6,各目标时的最小总运费的,110%,；,P,5,:,因路况原因，尽量避免安排,A,2,的物资运往,B,4,；,P,6,:,对,B,1,和,B,3,的供应率要尽可能相同；,P,7,:,力求使总运费最省。,试求满意的调运方案。,目标规划应用举例,B,1,B,2,B,3,B,4,a,i,A,1,5,2,6,7,300,A,2,3,5,4,6,200,A,3,4,5,2,3,400,b,j,200,100,450,250,解 用表上作业法可以求得不考虑,P,1,至,P,6,各目标时的最小运费调运方案，相应的最小运费为,2 950,元。现在建立问题的目标规划模型。,设,A,i,运往,B,j,的物资为,x,ij,t(i=1,2,3;j=1,2,3,4),，问题的目标规划模型为：,minP,1,d,4,-,P,2,d,5,-,P,3,(d,6,-,+d,7,-,+d,8,-,+d,9,-,),P,4,d,10,+,P,5,d,11,+,P,6,(d,12,-,+d,12,+,),P,7,d,13,+,目标规划应用举例,设,A,i,运往,B,j,的物资为,x,ij,t(i=1,2,3;j=1,2,3,4),，问题的目标规划模型为：,minP,1,d,4,-,P,2,d,5,-,P,3,(d,6,-,+d,7,-,+d,8,-,+d,9,-,),P,4,d,10,+,P,5,d,11,+,P,6,(d,12,-,+d,12,+,),P,7,d,13,+,需求量约束,供应量约束。考虑到各销地的需要量可以有,20%,的向下浮动，故作为绝对约束条件，且皆取“”号,A,3,向,B,1,的供应量目标约束,向各销地的最低供应量目标约束,实际运费的上限目标约束,A2,尽量不向,B4,调运物资的目标约束,给,B1,和,B3,的供应率尽量相同的目标约束,总运费尽量小的目标约束,解该目标规划，目标规划，可得使各方面尽可能满意的调运方案。相应的总运费为,3 360,元。,目标规划应用举例,B,1,B,2,B,3,B,4,A,1,100,200,300,A,2,90,110,200,A,3,100,250,50,400,190,100,360,250,该调运方案满足,P,1,P,2,P,3,P,5,各优先级目标，但在总运费和对,B,1,及,B,3,的供应率这两方面未能满足目标要求。总运费,3360,元超出运费目标上限,3245,元约,3.5%,。对,B,1,和,B,3,的供应率分别为,95%,和,80%,，差别较大，但这是较低级的目标，对调运方案的满意程度影响不大。,