第6章-目标规划-管理运筹学-.pptx

1、第第6章章 目标规划目标规划目录4目标规划数学模型目标规划数学模型123目标规划基本解法目标规划基本解法目标规划应用举例目标规划应用举例本章小结与作业本章小结与作业管理运筹学 第6章 目标规划6.1 目标规划的数学模型管理运筹学 第6章 目标规划引例与问题的提出引例与问题的提出目标规划的基本概念目标规划的基本概念目标规划的数学模型目标规划的数学模型目标规划的建模步骤目标规划的建模步骤导入案例产品组合问题管理运筹学 第6章 目标规划现增加如下考虑：现增加如下考虑：（1）力求使利润指标不低于）力求使利润指标不低于15元；元；（2）据市场预测，）据市场预测，I、II两种产品两种产品需求量的比例大致是

2、需求量的比例大致是1:2；（3）A为贵重设备，严格禁止超时为贵重设备，严格禁止超时使用；使用；（4）设备）设备C可以适当加班，但要控可以适当加班，但要控制；设备制；设备B既要求充分利用，又尽可既要求充分利用，又尽可能不加班，在重要性上设备能不加班，在重要性上设备B是是C的的3倍。倍。综合考虑上述因素，企业应如何决综合考虑上述因素，企业应如何决策？这里本章所要讨论的问题。策？这里本章所要讨论的问题。产品I 产品II 可用台时可用台时设备A设备B设备C240205121615单位利润2312121212max232212416.512,0zxxxxxstxx x最优解：最优解：x1=3x2=3z=

3、15若仅考虑利润目标，其若仅考虑利润目标，其LP模型为模型为：目标规划的正式提出n目标规划（目标规划（Goal Programming）:是针对线性规划目标单一是针对线性规划目标单一的局限性而提出的，是线性规划的应用拓展，是解决实际问题的局限性而提出的，是线性规划的应用拓展，是解决实际问题的一种方法。线性规划是研究资源有效分配和利用，其特点是的一种方法。线性规划是研究资源有效分配和利用，其特点是在满足一组约束条件的情况下，寻求某一个目标的最大值或最在满足一组约束条件的情况下，寻求某一个目标的最大值或最小值。而在现实社会中，经常遇到需要考虑多个目标的优化问小值。而在现实社会中，经常遇到需要考虑多

4、个目标的优化问题。目标规划与传统方法不同，它强调了系统性，其方法在于题。目标规划与传统方法不同，它强调了系统性，其方法在于寻找一个寻找一个“尽可能尽可能”满足所有目标的解，而不是绝对满足这些满足所有目标的解，而不是绝对满足这些目标的值。目标的值。n目标规划有着极大的灵活性，表现在它可以模拟系统的约束和目标规划有着极大的灵活性，表现在它可以模拟系统的约束和目标优先等级变化的各种模型，为管理决策提供众多的信息。目标优先等级变化的各种模型，为管理决策提供众多的信息。解决目标规划问题首先要根据目标的重要性分清主次先后、轻解决目标规划问题首先要根据目标的重要性分清主次先后、轻重缓急，引入偏差变量，将目标

5、按等级转化为目标约束，最终重缓急，引入偏差变量，将目标按等级转化为目标约束，最终形成可用线性规划方法解决的问题。形成可用线性规划方法解决的问题。管理运筹学 第6章 目标规划目标规划的正式提出多目标最优化问题最早是由意大利经济学家多目标最优化问题最早是由意大利经济学家L.帕雷托在帕雷托在1896年提出来的，他把许多本质上是不可比较的目标化成一个年提出来的，他把许多本质上是不可比较的目标化成一个单一的最优化单一的最优化目标。目标。1944年年J.von诺伊曼和诺伊曼和O.莫根施特恩又莫根施特恩又从对策论角度提出具有多个决策者并相互矛盾的多目标决从对策论角度提出具有多个决策者并相互矛盾的多目标决策问

6、题。策问题。1951年年T.C.考普曼从生产和分配活动分析中提出多考普曼从生产和分配活动分析中提出多目标最优化问题，并引入了帕雷目标最优化问题，并引入了帕雷托最优的托最优的概念。概念。1961年美年美国学者查纳斯（国学者查纳斯（A.Charnes）和库伯（）和库伯（W.W.Cooper）在他）在他们合著的们合著的管理模型和线性规划的工业应用管理模型和线性规划的工业应用一书中正式一书中正式提出目标规划，以后这种模型经提出目标规划，以后这种模型经U杰斯基莱恩和杰斯基莱恩和Sang李不李不断完善改进，并给出了求解目标规划的一般方法断完善改进，并给出了求解目标规划的一般方法单纯单纯形法。形法。管理运筹

7、学 第6章 目标规划6.1.1 基本概念管理运筹学 第6章 目标规划d 用以表明实际值与超出或未达到目标值的差距，用下列符号表示：用以表明实际值与超出或未达到目标值的差距，用下列符号表示：d+超出目标的差距，称正偏差变量超出目标的差距，称正偏差变量 d-未达到目标的差距，称负偏差变量未达到目标的差距，称负偏差变量 第一，当实际值超出规定目标时第一，当实际值超出规定目标时d-=0,d+0；第二，当实际值未达到规定目标时第二，当实际值未达到规定目标时d-0,d+=0；第三，实际值与目标值刚好一致时第三，实际值与目标值刚好一致时d-=d+=0。故恒有故恒有d-d+=0；1.偏差变量偏差变量 系统约束

8、指某种资源的使用上受到严格限制。这种限制如同在线性规划系统约束指某种资源的使用上受到严格限制。这种限制如同在线性规划中的约束一样，不允许有丝毫超差，故称为刚性约束。中的约束一样，不允许有丝毫超差，故称为刚性约束。2.系统约束系统约束 目标规划处理问题的方法是将多目标转化为多个目标约束。如目目标规划处理问题的方法是将多目标转化为多个目标约束。如目标利润的约束：甲产品单位利润标利润的约束：甲产品单位利润2元乙产品单位利润元乙产品单位利润3元，目标要元，目标要求利润不小于求利润不小于15元，即有目标约束不等式：元，即有目标约束不等式：2x1+3x215 添加正负偏差变量，将其变为等式：添加正负偏差变

9、量，将其变为等式：2x1+3x2+d-1-d+1=15 当当d-1=0,d+10时，表明时，表明2x1+3x215，达到了目标；，达到了目标；当当d-10,d+1=0时，表明时，表明2x1+3x2Pk+1。4.目标函数中的优先级目标函数中的优先级 在同一优先级内，根据重要程度不同，用权系数确定其优先顺序。权系数是在同一优先级内，根据重要程度不同，用权系数确定其优先顺序。权系数是一个具体的数字，通常以一个具体的数字，通常以“罚款额罚款额”、“损失额损失额”作为权系数，对重大的战作为权系数，对重大的战略性问题，应采取略性问题，应采取“专家意见法专家意见法”进行综合评价进行综合评价.设：设：P1:目

10、标利润；目标利润；P2:产品比例；产品比例；P3:设备设备B的利用与加班，设备的利用与加班，设备C的加班。的加班。在在P3中设备中设备B的重要性为的重要性为C的的3倍，则目标函数为：倍，则目标函数为：5.权系数权系数4333322211)(3)(mindPddPddPdPz6.1.1 基本概念管理运筹学 第6章 目标规划6.1.2 目标规划的数学模型n将上述目标规划的目标约束、目标函数再加上系统约束将上述目标规划的目标约束、目标函数再加上系统约束和变量非负约束，即构成了引例中的目标规划数学模型和变量非负约束，即构成了引例中的目标规划数学模型如下：如下：管理运筹学 第6章 目标规划4333322

11、211)(3)(mindPddPddPdPz1212111222133244122212231520.416512,0(1,2,3,4)jjxxxxddxxddstxddxddx xddj系统约束目标约束变量非负约束6.1.2 目标规划的数学模型n目标规划数学模型的一般形式：目标规划数学模型的一般形式：管理运筹学 第6章 目标规划min()()iiiiif dP w dw d11(1,).()(1,)0(1,),0(1,)nijjiiijnijjijjiic xddgimsta xbilxjn ddim 优先因子优先因子正偏差权系数正偏差权系数负偏差权系数负偏差权系数目标约束目标约束系统约束系

12、统约束变量非负变量非负目标规划建模步骤根据背根据背景材料景材料列出全列出全部约束部约束不等式不等式目标目标约束约束系统系统约束约束xj 0d0“”mind-“”mind+“=”mind-+d+左端左端+dd+=右端右端确定优先确定优先级和权系级和权系数数,构造目构造目标偏差最标偏差最小的目标小的目标函数函数约束约束条件条件目标目标规划规划数学数学模型模型管理运筹学 第6章 目标规划例6-1管理运筹学 第6章 目标规划已知某实际问题的线性规划模型已知某实际问题的线性规划模型为：为：假定重新确定这个问题的目标为：假定重新确定这个问题的目标为：P1：z的值应不低于的值应不低于1900；P2：资源：资

13、源1尽可能全部利用。尽可能全部利用。将此问题转换为目标规划问题，将此问题转换为目标规划问题，列出数学模型。列出数学模型。12max10050zxx121212121016200.11325,0 xxs txxx x资资源源资资源源112:100501900Pxx12111100501900minxxddd212:1016200Pxx122221016200minxxddd112212121211122212min101620011325.1005019001016200,0(1,2)izPdP dxxxxs txxddxxddxxdiP1：第：第4用户需求量全部满足；用户需求量全部满足；P2：

14、每用户满足率：每用户满足率80%；P3：总运费：总运费原方案的原方案的110%；P4：从工厂：从工厂2到用户到用户4的路线应的路线应尽量尽量避免避免分配运输任务分配运输任务.例6-2管理运筹学 第6章 目标规划1234生产量生产量123534255642763300200400需求量需求量2001004502501142434:250Pxxx142434111250minxxxddd设：设：xij产地产地i到销地到销地j运送量，原方案最优值：运送量，原方案最优值：29501121312122232132333160:80360 xxxPxxxxxx11213122212223233313233

15、3444160min80min360minxxxdddxxxdddxxxddd424:0Px246660minxddd11121314321222324313233345267:354645233245xxxxPxxxxxxxx1112131421222324313233345555267354645233245minxxxxxxxxxxxxddd112234354611121314212223243132333414243411112131221222323313233344:min()30020040025016080.zP dPdddP dP dxxxxxxxxxxxxxxxddxxxd

16、dxxxdds txxxdd综综 上上 所所 述述系系 统统 约约 束束11121314212223243132333455246636052673546452332450,0(1,2,3;1,2,3,4;1.6)ijkxxxxxxxxxxxxddxddxdijk目目 标标 约约 束束例6-2管理运筹学 第6章 目标规划6.2 目标规划的基本解法管理运筹学 第6章 目标规划求解流程求解流程图解法图解法单纯形法单纯形法序贯算法序贯算法目标规划求解流程管理运筹学 第6章 目标规划用目标规划处理问题用目标规划处理问题的难点在于构造模型的难点在于构造模型时需要事先确定优先时需要事先确定优先级和权系数。

17、而这些级和权系数。而这些信息往往来自人们的信息往往来自人们的主观判断，很难给出主观判断，很难给出一个绝对的数值。通一个绝对的数值。通常根据求解结果的各常根据求解结果的各项目标满意程度来修项目标满意程度来修改优先级和权系数，改优先级和权系数，直至满意为止。其流直至满意为止。其流程如右图。程如右图。明确问题，明确问题，列出（或修列出（或修改）目标的改）目标的优先级和权优先级和权系数系数no构造目标构造目标规划模型规划模型求出求出满意解满意解分析各分析各项目标项目标完成情完成情况况据此据此制订制订决策决策方案方案满意否？满意否？yes1122233334121211122213324412min()

18、3()2212231520.416515,0(1,2,3,4)jjzPdP ddP ddPdxxxxddxxdds txddxddx x ddj6.2.1 图解法管理运筹学 第6章 目标规划x1x2o662x1+2x2=1211dd2x1+3x2=157.552x1-x2=022dd4x1=1633dd5x2=1544dd（1）绘出直角坐标）绘出直角坐标（2）图示系统约束，确定可行域）图示系统约束，确定可行域（3）按优先级高低，依次图示目）按优先级高低，依次图示目标约束，缩小满意解范围。标约束，缩小满意解范围。1212206xxxx122,4xx112233440,10,08,00,5dddd

19、dddd6.2.2 单纯形法管理运筹学 第6章 目标规划（1）由于目标函数均为最小，为方便起见，不转换为极大；）由于目标函数均为最小，为方便起见，不转换为极大；（2）以系统约束的松驰变量、人工变量、目标约束的负偏差变量为初始基变）以系统约束的松驰变量、人工变量、目标约束的负偏差变量为初始基变量；量；（3）检验数行按优先因子分别列出。）检验数行按优先因子分别列出。目标规划与线性规划初始单纯形表的不同目标规划与线性规划初始单纯形表的不同（1）从第一级优级开始，若检验数存在负数，最小检验数所对应的变量为换）从第一级优级开始，若检验数存在负数，最小检验数所对应的变量为换入变量。当高级优先级得到优化，转

20、向下一级；入变量。当高级优先级得到优化，转向下一级；（2）在第）在第k优先级优化过程中，如果破坏了上级优化结果，则迭代停止，优先级优化过程中，如果破坏了上级优化结果，则迭代停止，k-1以上级目标得到优化，以上级目标得到优化，k级以下未得到优化，所得结果为满意解；级以下未得到优化，所得结果为满意解；（3）若所有检验数均非负，所有目标均得到优化，所得结果可称为最优解。）若所有检验数均非负，所有目标均得到优化，所得结果可称为最优解。目标规划与线性规划计算检验数的不同目标规划与线性规划计算检验数的不同1122312111222123312min()250240.2280,0(1,2,3)iizP dd

21、P dxxddxxdds txxddx xddi,【例例6.4】用单用单纯形法求目标纯形法求目标规划满意解规划满意解满意解：满意解：x1=0,x2=40目标完成情况：目标目标完成情况：目标1产生产生30个单位的正偏差，其余均无偏差。个单位的正偏差，其余均无偏差。单纯形法例题管理运筹学 第6章 目标规划6.2.3 序贯算法n序贯是数理统计学的一个分支，源于序贯是数理统计学的一个分支，源于AA瓦尔德在瓦尔德在19471947年发表的一本同名著作，研究的对象是所谓年发表的一本同名著作，研究的对象是所谓“序贯抽样方案序贯抽样方案”，其基本思想是：先抽少量样本，其基本思想是：先抽少量样本，根据结果再决定

22、继续抽样，直到决定停止为止。根据结果再决定继续抽样，直到决定停止为止。依依据这一思想，先考虑只有系统约束和最高优先级的据这一思想，先考虑只有系统约束和最高优先级的目标约束，目标函数中的优先因子取目标约束，目标函数中的优先因子取“1”1”，求得其，求得其目标要求的偏差变量的值，将其固定，再按优先次目标要求的偏差变量的值，将其固定，再按优先次序逐级添加目标约束并进行优化，直到全部目标优序逐级添加目标约束并进行优化，直到全部目标优化完毕为止。化完毕为止。管理运筹学 第6章 目标规划【例6.5】用序贯算法求解目标规划问题管理运筹学 第6章 目标规划1:0d解解得得111212111:.min2212.

23、2315Pzdxxs txxdd第第 步步 优优化化1222121211122212:.min22122315.200PPzddxxxxdds txxddd第第 步步 固固定定 最最优优解解,优优化化1122233334121211122213324412min()3()2212231520.416515,0(1,2,3,4)jjzPdP ddP ddPdxxxxddxxdds txddxddx x ddj系系统统约约束束目目标标约约束束233412121112221332441223:min332212231520.4165150PPzdddxxxxddxxdds txddxddddd3 3

24、第第 步步 固固定定最最优优解解,优优化化121342,4:1,8,5xxddd解解得得:目目标标完完成成程程度度22:00dd解解得得6.3 目标规划应用举例管理运筹学 第6章 目标规划Burnit 公司广告策划公司广告策划产品决策问题产品决策问题 Fruit公司芯片购买决策公司芯片购买决策Burnit公司准备通过电视公司准备通过电视媒体做广告媒体做广告,在在“足球足球”和和“肥皂剧肥皂剧”中中插播，插播，相相关关资料如右表。表中：资料如右表。表中：HIM高收入高收入男士男士;LIP低收入低收入人群人群;HIW高收入女士高收入女士6.3.1 Burnit公司广告策划管理运筹学 第6章 目标规

25、划广告广告预期观众数预期观众数(百万百万)费用费用(万美元万美元)HIMLIPHIW足球足球肥皂剧肥皂剧7310554106目标目标40603560单位损失单位损失20105解解 设：设：x1:足球期间插播广告时间足球期间插播广告时间,x2:肥皂剧插播广告时间肥皂剧插播广告时间127340 xx121117340min 20 xxddd1210560 xx1222210560min10 xxddd125435xx123335435min5xxddd1210660 xxHIM目标约束目标约束LIP目标约束目标约束HIW目标约束目标约束预算限制预算限制1231212111222123312min2

26、0105106607340.105605435,0(1,2,3)izdddxxxxdds txxddxxddx xdi综上所述：综上所述：6.3.1 Burnit公司广告策划管理运筹学 第6章 目标规划126,0 xx满满意意解解：13250dd目目标标达达成成情情况况：其其余余6.3.2 产品决策问题 管理运筹学 第6章 目标规划数据数据/万件万件目标目标权数权数IIIIII长期利润（百万元）长期利润（百万元）雇用水平（百人）雇用水平（百人）资本投资（百万元）资本投资（百万元）12559371548125=40555(-)2(+),4(-)3(+)解解 设：设：x1:产品产品I产量；产量；x

27、2:产品产品II产量；产量；x3:产品产品III产量产量12312915125xxx12311112915125min5xxxddd12353440 xxx123222253440min(42)xxxdddd12357855xxx12333357855min3xxxddd长期利润长期利润雇用水平雇用水平资本投资资本投资122312311123221233313min54231291512553440.57855,0(1,2,3)izddddxxxddxxxdds txxxddxdi综上所述：综上所述：优化结果：产品优化结果：产品I生产生产8.33，产品，产品III生产生产1.67，目标，目标1

28、和目标和目标3均得均得到满足，但目标到满足，但目标2超出超出833人。对人。对此人事部门认为：超员是短期行此人事部门认为：超员是短期行为，将产生严重后果；财务部门为，将产生严重后果；财务部门认为：认为：5500万投资也不能突破，万投资也不能突破，故采取带优先权的目标规划，对故采取带优先权的目标规划，对员工雇用和投资给一个高优先权。员工雇用和投资给一个高优先权。12321212311123221233313min(23)(54)1291512553440.57855,0(1,2,3)izPddPddxxxddxxxdds txxxddxdi优化结果：优化结果：x1=5,x3=3.75目标达成情况

29、：目标达成情况：d1_=8.75，其余，其余=06.3.2 产品决策问题 管理运筹学 第6章 目标规划6.3.3 Fruit公司芯片购买决策 管理运筹学 第6章 目标规划供应商供应商一套（一套（100个）芯片个）芯片每套价格（美元）每套价格（美元）优等优等 良好级良好级 中等中等123605040203520201540400300250单个购价单个购价需求量需求量1050006300041000问题：问题：1.超预算超预算1美元，美元，1美元罚款；美元罚款；2.预算、优等、良好级、中等预算、优等、良好级、中等分属分属4个优先级。个优先级。设：设：x1,x2,x3为从供应商为从供应商1、2、3

30、购买的套数；购买的套数；x4,x5,x6单独购买优、良、中芯片的个数单独购买优、良、中芯片的个数123412351236605040500020352030002015401000 xxxxxxxxxxxx优优等等良良好好级级中中等等123456400300250106428000 xxxxxx123456111400300250106428000minxxxxxxddzd问题问题1：系统约束系统约束目标约束目标约束约束转换约束转换112341235123612345611161min60504050002035203000.2015401000400300250106428000,0zdxx

31、xxxxxxstxxxxxxxxxxddxd数学模型：数学模型：优化结果：优化结果：6.3.3 Fruit公司芯片购买决策 管理运筹学 第6章 目标规划1210,1002000 xxd6.3.3 Fruit公司芯片购买决策 管理运筹学 第6章 目标规划供应商供应商一套（一套（100个）芯片个）芯片每套价格（美元）每套价格（美元）优等优等良好级良好级中等中等123605040203520201540400300250单个购价单个购价需求量需求量1050006300041000问题问题2：预算、优等、良好级、中等分属：预算、优等、良好级、中等分属4个优先级。个优先级。1 1223344123456

32、11123422123533123644161min4003002501064280006050405000.20352030002015401000,0zPdPdPdPdxxxxxxddxxxxddstxxxxddxxxxddxd优化结果：优化结果：x2=93x4=10d2_=340d3=255d4=395其余其余=0本章小结1.1.概念：概念：目标规划是对多目标或相互目标规划是对多目标或相互矛盾的多重目标进行择优的一种方法。矛盾的多重目标进行择优的一种方法。它是线性规划的应用拓展，它强调了它是线性规划的应用拓展，它强调了系统性，是解决实际问题的一种有效系统性，是解决实际问题的一种有效方法。

33、方法。2.2.建模步骤建模步骤1)根据背景材料列出所有约束不等式；根据背景材料列出所有约束不等式；2)对目标约束不等式左端加负偏差变对目标约束不等式左端加负偏差变量减正偏差变量，转换为等式约束；量减正偏差变量，转换为等式约束；3)确定每个目标的目标要求：确定每个目标的目标要求：目标约束符为目标约束符为“”，mind-；目标约束符为目标约束符为“”，mind+；目标约束符为目标约束符为“=”，mind-+d+；4)将各目标的目标要求用优先因子将各目标的目标要求用优先因子及权系数组合成一个目标，求其最及权系数组合成一个目标，求其最小值。小值。3.优先级与权系数优先级与权系数确定优先级与权系数。优先级为定确定优先级与权系数。优先级为定性的层次差异因子；权系数的确定，性的层次差异因子；权系数的确定，通常可用通常可用“罚数罚数”作为权系数或用作为权系数或用“专家意见法专家意见法”确定。确定。作业作业:P125-127：1,2,3,7,9管理运筹学 第6章 目标规划