单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 目标规划,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