运筹学目标规划课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,目 标 规 划,(Goal programming),目标规划的数学模型,目标规划的图解法,目标规划的单纯形法,目标规划概述,目 标 规 划目标规划的数学模型目标规划的图解法目标规,目标规划是在线性规划的基础上，为适应经济管理中多目标决策的需要而逐步发展起来的一个分支。,2、线性规划求最优解；目标规划是找到一个满意解。,1、线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题；而目标规划是多个目标决策，可求得更切合实际的解。,一、目标规划概述,（一）、目标规划与线性规划的比较,目标规划是在线性规划的基础上，为适应经济管理中多,4、线性规划的最优解是绝对意义下的最优，但需花去大量的人力、物力、财力才能得到；实际过程中，只要求得满意解，就能满足需要（或更能满足需要）。,3、线性规划中的约束条件是同等重要的，是硬约束；而目标规划中有轻重缓急和主次之分，即有优先权。,目前，已经在经济计划、生产管理、经营管理、市场分析、财务管理等方面得到了广泛的应用。,4、线性规划的最优解是绝对意义下的最优，但需花去大量的人,（二）、目标规划的基本概念,例题41,线性规划模型为： maxZ = 8x,1,+ 10 x,2,2x,1,+ x,2,11 ,x,1,+2x,2,10 ,x,1, x,2,0,X*=(4,3),T,Z*=62,目标函数的地位突出，约束条件是必须严格满足的等式或不等式，是绝对化的“硬约束”，此种问题若要求太多时，很容易相互矛盾，得不到可行解。如根据市场情况再加以下要求：,（二）、目标规划的基本概念例题41,产品产量不大于产品。,超过计划供应原材料时，需高价采购，这使成本增加。,应尽可能充分利用设备工时，但不希望加班。,利润不少于56元。,用式子表示：,x,1,- x,2,0,2x,1,+x,2,11,x,1,+2x,2,=10,8x,1,+10x,2,56,左边：决策值（表示实际执行效果）,右边：目标值（表示理想目标）,实际效果与理想目标之间可能有偏差值（不足或者超过），若引入偏差变量，就可变成等式,。,产品产量不大于产品。,目标规划通过引入目标值和偏差变量，可以将目标函数转化为目标约束。,目标值：是指预先给定的某个目标的一个期望值。,实现值或决策值：是指当决策变量,x,j,选定以后，目标函数的对应值。,偏差变量（事先无法确定的未知数）：是指实现值和目标值之间的差异,记为 d 。,正偏差变量：表示实现值超过目标值的部分，记为 d,。,负偏差变量：表示实现值未达到目标值的部分，记为 d,。,1、目标值和偏差变量,1、目标值和偏差变量,当完成或超额完成规定的指标则表示：,d,0,d,0,当未完成规定的指标则表示：,d,0,d,0,当恰好完成指标时则表示：,d,0,d,0,d,d,0 成立。,引入了目标值和正、负偏差变量后，就对某一问题有了新的限制，即目标约束。,目标约束既可对原目标函数起作用，也可对原约束起作用。目标约束是目标规划中特有的，是软约束。,绝对约束（系统约束）是指必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对约束，否则无可行解。所以，绝对约束是硬约束。,在一次决策中，实现值不可能既超过目标值又未达到目标值，故有,d,d,0,并规定d,0,d,0,2、目标约束和绝对约束,当完成或超额完成规定的指标则表示：d0, d0,达成函数是一个使总偏差量为最小的目标函数，记为 minZ =,f,（,d,、d,）。,一般说来，有以下三种情况，但只能出现其中之一：,.要求恰好达到规定的目标值，即正、负偏差变量要尽可能小，则minZ =,f,（,d, d,）。,.要求不超过目标值，即允许达不到目标值，也就是正偏差变量尽可能小，则minZ =,f,（,d,）。,.要求超过目标值，即超过量不限，但不低于目标值，也就是负偏差变量尽可能小，则minZ =,f,（,d,）。,对于由绝对约束转化而来的目标函数，也照上述处理即可。,3、达成函数（即目标规划中的目标函数）,达成函数是一个使总偏差量为最小的目标函数，记为 m,优先因子,P,k,是将决策目标按其重要程度排序并表示出来。,P,1,P,2,P,l,P,l+1,P,L,，l=1.2L。,后面乘任意大的数还是小。必须“满足”第一级才能“满足”第二级，依次类推。,权系数,l,k,：区别具有相同优先因子的两个目标的重要性差别，决策者可视具体情况而定。,（优先因子和权系数的大小具有主观性和模糊性，它不是运筹学本身的问题，主要是决策人自身的经验，可用专家评定法给以量化。）,对于这种解来说，前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现。,4、优先因子（优先等级）与优先权系数,5、满意解（具有层次意义的解）,优先因子Pk 是将决策目标按其重要程度排序并表示,例题42：,解：确定优先因子后得数学模型：,min Z =P,1,d,1,+,+P,2,(d,2,-,+d,2,+,)+P,3,d,3,-,2x,1,+x,2,11,（在绝对约束基础上进行目标规划）,x,1,- x,2,+ d,1,-,- d,1,+,= 0,(要求： d,1,+,尽可能小，最好是0才能满足 ),x,1,+2x,2,+ d,2,-,- d,2,+,=10,（要求：d,2,-,和 d,2,+,都尽可能小，最好等于0）,8x,1,+10x,2,+ d,3,-,- d,3,+,=56,（要求：d,3,-,尽可能小，最好是0才能满足）,x,1, x,2, d,i,-,d,i,+,0,例题42：,规划模型：,规划模型：,（一）、模型的一般形式,二、目标规划的数学模型,（一）、模型的一般形式二、目标规划的数学模型,（二）、建模的步骤,1、根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；,4、对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系数 。,3、给各目标赋予相应的优先因子 P,l,（l=1.2L）。,2、可根据决策者的需要，将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可。,（二）、建模的步骤 1、根据要研究的问题所提出的各目标与,5、根据决策者的要求，按下列情况之一构造一个由,优先因子和权系数相对应的偏差变量组成的，要求实,现极小化的目标函数，即达成函数。,.恰好达到目标值，取 。,.允许超过目标值，取 。,.不允许超过目标值，取 。,5、根据决策者的要求，按下列情况之一构造一个由.恰好达,（三）、小结,线性规划LP,目标规划GP,目标函数,min , max,系数可正负,min ,偏差变量,系数0,变量,x,i,x,s,x,a,x,i,x,s,x,a,d,约束条件,系统约束,（绝对约束）,目标约束,系统约束,解,最优,最满意,（三）、小结线性规划LP目标规划GP目标函数min ,图解法同样适用两个变量的目标规划问题，但其操作简单，原理一目了然。同时，也有助于理解一般目标规划的求解原理和过程。,图解法解题步骤如下：,1、确定各约束条件的可行域，即将所有约束条件（包括目标约束和绝对约束，暂不考虑正负偏差变量）在坐标平面上表示出来；,2、在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向；,三、目标规划的图解法,图解法同样适用两个变量的目标规划问题，但其操作简单,3、求满足最高优先等级目标的解；,4、转到下一个优先等级的目标，在不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解；,5、重复4，直到所有优先等级的目标都已审查完毕为止；,6、确定最优解和满意解。,例一、用图解法求解目标规划问题,min Z =P,1,d,1,+,+P,2,(d,2,-,+d,2,+,)+P,3,d,3,-,2x,1,+x,2,11,x,1,- x,2,+ d,1,-,- d,1,+,= 0,x,1,+2x,2,+ d,2,-,- d,2,+,=10,8x,1,+10x,2,+ d,3,-,- d,3,+,=56,x,1, x,2, d,i,-,d,i,+,0,3、求满足最高优先等级目标的解；例一、用图解法求解,运筹学目标规划课件,例二、已知一个生产计划的线性规划模型为,其中目标函数为总利润，x,1,x,2,为产品,A、B,产量。现有下列目标：,1、要求总利润必须超过 2500 元；,2、考虑产品受市场影响，为避免积压，,A、B的,生产量不超过 60 件和 100 件；,3、由于甲资源供应比较紧张，不要超过现有量140。,试建立目标规划模型，并用图解法求解。,例二、已知一个生产计划的线性规划模型为 其中目标,解：以产品 A、B 的单件利润比 2.5 ：1 为权系数，模型如下：,解：以产品 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)为所求的满意解。,作图：,0x2 0x114020 40 60,检验：将上述结果带入模型，因, ,0,；, ,0,；,0,，,存在；,0,，,存在。所以，有下式：,minZ=,P,3,将,x,1,60，,x,2,58.3,带入约束条件，得,30601258.32499.62500；,260+58.3=178.3 140；,16060,158.358.3 P,2, P,3, P,k,，所以检验数的正负首先取决于P,1,的系数的正负，若P,1,的系数为0，再由P,2,的系数的正负决定检验数的正负，然后依次类推,。,一、特点1目标函数： min,1、建立初始单纯形表。,一般假定初始解在原点，即以约束条件中的所有负偏差变量或松弛变量为初始基变量，按目标优先等级从左至右分别计算出各列的检验数，填入表的下半部 。,2、检验是否为满意解。判别准则如下：,.首先检查,k,(,k,=1.2,K,),是否全部为零？如果全部为零，则表示目标均已全部达到，获得满意解，停止计算转到第6步；否则转入。,（二）、单纯形法的计算步骤,1、建立初始单纯形表。 2、检验是否为满意解。判,.如果某一个,k,0,。说明第k个优先等级的目标尚未达到,必须检查,P,k,这一行的检验数,kj,(j=1.2n+2m).若,P,k,这一行某些负检验数的同列上面（较高优先等级）没有正检验数，说明未得到满意解，应继续改进，转到第3步；若,P,k,这一行全部负检验数的同列上面（较高优先等级）都有正检验数，说明目标虽没达到，但已不能改进，故得满意解，转到第6步。,3、确定进基变量。,在,P,k,行，从那些上面没有正检验数的负检验数中，选绝对值最大者，对应的变量,x,s,就是进基变量。若,P,k,行中有几个相同的绝对值最大者，则依次比较它们各列下部的检验数，取其绝对值最大的负检验数的所在列的,x,s,为进基变量。假如仍无法确定，则选最左边的变量（变量下标小者）为进基变量。,.如果某一个k 0。说明第k个优先等级的目标尚未达,4、确定出基变量,其方法同线性规划，即依据最小比值法则,故确定,x,r,为出基变量，,e,rs,为主元素。若有几个相同的行可供选择时，选最上面那一行所对应得变量为,x,r,。,5、旋转变换（变量迭代）。 以为主元素进行变换，得到新的单纯形表，获得一组新解，返回到第2步。,6、对求得的解进行分析,若计算结果满意，停止运算；若不满意，需修改模型，即调整目标优先等级和权系数，或者改变目标值，重新进行第1步。,4、确定出基变量 5、旋转变换（变量迭代）。,例一、用单纯形法求解下列目标规划问题,例一、用单纯形法求解下列目标规划问题,C,j,0,0,P,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2.5P,2,0,P,2,0,0,0,0,0,P,3,0,0,0,0,C,B,X,B,b,x,1,x,2,P,1,2500,30,12,1,1,0,0,0,0,0,0,0,140,2,1,0,0,1,1,0,0,0,0,0,60,1,0,0,0,0,0,1,1,0,0,0,100,0,1,0,0,0,0,0,0,1,1,kj,P,1,-2500,30,12,0,1,0,0,0,0,0,0,P,2,0,0,0,0,0,0,0,0,2.5,0,1,P,3,0,0,0,0,0,0,1,0,0,0,0,=,min2500/30,140/2,60/1=60,故 为换出变量。,00P1000000000000002.5P20P20000,C,j,0,0,P,1,0,0,P,3,0,2.5P,2,0,P,2,C,B,X,B,b,x,1,x,2,P,1,700,0,12,1,1,0,0,30,30,0,0,0,20,0,1,0,0,1,1,2,2,0,0,0,x,1,60,1,0,0,0,0,0,1,1,0,0,0,100,0,1,0,0,0,0,0,0,1,1,kj,P,1,700,0,12,0,1,0,0,30,30,0,0,P,2,0,0,0,0,0,0,0,0,2.5,0,1,P,3,0,0,0,0,0,0,1,0,0,0,0,=,min700/30,20/2, =10,故 为换出变量。,Cj 00P100P302.5P20P2CBXBbx1x2P,C,j,0,0,P,1,0,0,P,3,0,2.5P,2,0,P,2,C,B,X,B,b,x,1,x,2,P,1,400,0,-3,1,-1,-15,15,0,0,0,0,2.5P,2,10,0,1/2,0,0,1/2,-1/2,-1,1,0,0,0,x,1,70,1,1/2,0,0,1/2,-1/2,0,0,0,0,0,100,0,1,0,0,0,0,0,0,1,-1,kj,P,1,-400,0,3,0,1,15,-15,0,0,0,0,P,2,-25,0,-5/4,0,0,-5/4,5/4,5/2,0,0,1,P,3,0,0,0,0,0,0,1,0,0,0,0,=,min400/15, =10,故 为换出变量。,Cj 00P100P302.5P20P2CBXBbx1x2P,C,j,0,0,P,1,0,0,P,3,0,2.5P,2,0,P,2,C,B,X,B,b,x,1,x,2,P,3,80/3,0,-1/5,1/15,-1/15,-1,1,0,0,0,0,2.5P,2,70/3,0,2/5,1/30,-1/30,0,0,-1,1,0,0,0,x,1,250/3,1,2/5,1/30,-1/30,0,0,0,0,0,0,0,100,0,1,0,0,0,0,0,0,1,1,kj,P,1,0,0,0,1,0,0,0,0,0,0,0,P,2,-175/3,0,-1,-1/12,1/12,0,0,2/5,0,0,1,P,3,-80/3,0,1/5,-1/15,1/15,1,0,0,0,0,0,=,min,350/6,1250/6,100/1=75,故 为换出变量。,Cj 00P100P302.5P20P2CBXBbx1x2P,C,j,0,0,P,1,0,0,P,3,0,2.5P,2,0,P,2,C,B,X,B,b,x,1,x,2,P,3,115/3,0,0,1/12,-1/12,-1,1,-1/2,1/2,0,0,0,x,2,175/3,0,1,1/12,-1/12,0,0,-5/2,5/2,0,0,0,x,1,60,1,0,0,0,0,0,-1,1,0,0,0,125/3,0,0,-1/12,1/12,0,0,5/2,-5/2,1,1,kj,P,1,0,0,0,1,0,0,0,0,0,0,0,P,2,0,0,0,0,0,0,0,0,5/2,0,1,P,3,-115/3,0,0,-1/12,1/12,1,0,1/2,-1/2,0,0,表中,3,115/30，,说明,P,3,优先等级目标没有实现，但已无法改进，得到满意解,x,1,60，,x,2,175/3， 115/3， 125/3。,Cj 00P100P302.5P20P2CBXBbx1x2P,结果分析：计算结果表明，工厂应生产,A,产品,60,件，,B,产品,175/3,件，,2500,元的利润目标刚好达到。 ,125/3,，表明产品比最高限额少,125/3,件，满足要求。 ,115/3,表明甲资源超过库存,115/3,公斤，该目标没有达到。,从表中还可以看到，,P,3,的检验数还有负数，但其高等级的检验数却是正数，要保证,P,1,目标实现，,P,3,等级目标则无法实现。所以，按现有消耗水平和资源库存量，无法实现2500元的利润目标。,可考虑如下措施：降低,A、B,产品对甲资源的消耗量，以满足现有甲资源库存量的目标；或改变,P,3,等级目标的指标值，增加甲资源115/3公斤。,若很难实现上述措施，则需改变现有目标的优先等级，以取得可行的满意结果。,结果分析：计算结果表明，工厂应生产A产品60件,练习：,用单纯形法求解下列目标规划问题,练习：用单纯形法求解下列目标规划问题,C,j,0,0,0,P,1,P,2,P,2,P,3,0,0,C,B,X,B,b,x,1,x,2,x,3,0,0,1,1,1,1,0,0,0,0,0,P,2,10,1,2,0,0,1,1,0,0,0,P,3,56,8,10,0,0,0,0,1,1,0,0,x,3,11,2,1,0,0,0,0,0,0,1,kj,P,1,0,0,0,0,1,0,0,0,0,0,P,2,10,1,2,0,0,0,2,0,0,0,P,3,56,8,10,0,0,0,0,0,1,0,=,min,10/2,56/10,11/1=,5,故 为换出变量。,Cj 000P1 P2 P2P3 00CBXBbx1x2,C,j,0,0,0,P,1,P,2,P,2,P,3,0,0,C,B,X,B,b,x,1,x,2,x,3,0,2,3/2,0,1,1,1/2,-1/2,0,0,0,0,x,2,5,1/2,1,0,0,1/2,-1/2,0,0,0,P,3,6,3,0,0,0,-5,5,1,1,0,0,x,3,6,3/2,0,0,0,-1/2,1/2,0,0,1,kj,P,1,0,0,0,0,1,0,0,0,0,0,P,2,0,0,0,0,0,1,1,0,0,0,P,3,6,3,0,0,0,5,-5,0,1,0,=,min10/3,10,6/3,12/3=,2,故 为换出变量。,Cj 000P1 P2 P2P3 00CBXBbx1x2,C,j,0,0,0,P,1,P,2,P,2,P,3,0,0,C,B,X,B,b,x,1,x,2,x,3,0,2,0,0,1,1,3,-3,-1/2,1/2,0,0,x,2,4,0,1,0,0,4/3,-4/3,-1/6,1/6,0,0,x,1,2,1,0,0,0,-5/3,5/3,1/3,-1/3,0,0,x,3,3,0,0,0,0,2,-2,-1/2,1/2,1,kj,P,1,0,0,0,0,1,0,0,0,0,0,P,2,0,0,0,0,0,1,1,0,0,0,P,3,0,0,0,0,0,0,0,1,0,0,最优解为,x,1,2，,x,2,4。 但非基变量 的检验数为零，故此题有无穷多最优解。,=,min4 , 24 , 6= 4,故 为换出变量。,Cj 000P1 P2 P2P3 00CBXBbx1x2,C,j,0,0,0,P,1,P,2,P,2,P,3,0,0,C,B,X,B,b,x,1,x,2,x,3,0,4,0,0,2,-2,6,-6,-1,1,0,0,x,2,10/3,0,1,-1/3,1/3,1/3,-1/3,0,0,0,0,x,1,10/3,1,0,2/3,-2/3,1/3,-1/3,0,0,0,0,x,3,1,0,0,-1,1,-1,1,0,0,1,kj,P,1,0,0,0,0,1,0,0,0,0,0,P,2,0,0,0,0,0,1,1,0,0,0,P,3,0,0,0,0,0,0,0,1,0,0,最优解为,x,1,10/3,，,x,2,=10/3,。,Cj 000P1 P2 P2P3 00CBXBbx1x2,1、某厂生产,A、B、C,三种产品，装配工作在同一生产线上完成，三种产品时的工时消耗分别为6、8、10小时，生产线每月正常工作时间为200小时；三种产品销售后，每台可获利分别为500、650和800元；每月销售量预计为12、10和6台。,该厂经营目标如下：1、利润指标为每月16000元，争取超额完成；2、充分利用现有生产能力；3、可以适当加班，但加班时间不得超过24小时；4、产量以预计销售量为准。试建立目标规划模型。,作业：,作业：,2、用图解法求解下列目标规划问题：,满意解为由,x,1,=（3， 3）, x,2,=（3.5，1.5） 所连线段。,2、用图解法求解下列目标规划问题：满意解为由x1 =（3，,3、用图解法解下列目标规划模型。,x,1,=400,x,2,=0,Z,=80,p,3,3、用图解法解下列目标规划模型。 x1=400, x,0,100 200 300 400 500,100 200 300 400,x,2,x,1,4,0 100 200,4、用单纯形法求解下列目标规划问题：,x,=（10，20，10）,4、用单纯形法求解下列目标规划问题：x =（10，20，10,5、用目标规划的单纯形方法解以下目标规划模型。,5、,x,1,=12,x,2,=10, =14,Z,=14,p,4,5、用目标规划的单纯形方法解以下目标规划模型。,答案：,答案：,习 题,1.已知条件如表所示,工序,型号,每周最大,加工能力,A,B,（小时/台）,（小时/台）,4,3,6,2,150,70,利润（元/台）,300,450,如果工厂经营目标的期望值和优先等级如下：,p,1,: 每周总利润不得低于10000元；,p,2,: 因合同要求，A型机每周至少生产10台，B型机每周至少 生产15台；,p,3,: 希望工序的每周生产时间正好为150小时，工序的生产时间最好用足，甚至可适当加班。,试建立这个问题的目标规划模型。,习 题型号每周最大AB（小时/台）46150利润（元/台）,运筹学目标规划课件,2.在上题中，如果工序在加班时间内生产出来的产品，每台A型机减少利润10元，每台B型机减少利润25元，并且工序的加班时间每周最多不超过30小时，这是p4级目标，试建立这个问题的目标规划模型。,2.在上题中，如果工序在加班时间内生产出来的产品,设x,1,x,2,分别为在正常时间和加班时间生产A型机台数，x,3,x,4,分别为在正常时间和加班时间生产B型机台数，目标规划数学模型为：,设x1,x2分别为在正常时间和加班时间生产A,3.某纺织厂生产两种布料，一种用来做服装，另一种用来做窗帘。该厂实行两班生产，每周生产时间定为80小时。这两种布料每小时都生产1000米。假定每周窗帘布可销售70000米，每米的利润为2.5元；衣料布可销售45000米，每米的利润为1.5元。,该厂在制定生产计划时有以下各级目标：,p1：每周必须用足80小时的生产时间；,p2：每周加班时数不超过10小时；,p3：每周销售窗帘布70000米，衣料布45000米；,p4：加班时间尽可能减少。,试建立这个问题的目标规划模型。,3.某纺织厂生产两种布料，一种用来做服装，另一种用来,设x,1, x,2,分别为每周生产窗帘布和医疗布的小时数，目标规划数学模型为：,设x1, x2分别为每周生产窗帘布和医疗布的小时数，目标规划,个人观点供参考，欢迎讨论！,个人观点供参考，欢迎讨论！,