运筹学课件第6章 目标规划.ppt

1、第6章 目标规划,重庆三峡学院 关文忠 ,管理运筹学课件,2020年7月8日星期三,教学目标与要求,【教学目标】 通过本章学习，理解目标规划的特点，会建立目标规划的数学模型；至少掌握一种软件求解目标规划的满意解。 【教学要求】,管理运筹学课件,2020年7月8日星期三,导入案例产品组合问题,现增加如下考虑： （1）力求使利润指标不低于15元； （2）据市场预测，I、II两种产品需求量的比例大致是1:2； （3）A为贵重设备，严格禁止超时使用； （4）设备C可以适当加班，但要控制；设备B既要求充分利用，又尽可能不加班，在重要性上设备B是C的3倍。 综合考虑上述因素，企业应如何决策？这里本章所要讨

2、论的问题。,最优解： x1=3 x2=3 z=15,若仅考虑利润目标，其LP模型为：,管理运筹学课件,2020年7月8日星期三,目标规划的正式提出,多目标最优化问题最早是由意大利经济学家L.帕雷托在1896年提出来的，他把许多本质上是不可比较的目标化成一个单一的最优化目标1944年J.von诺伊曼和O.莫根施特恩又从对策论角度提出具有多个决策者并相互矛盾的多目标决策问题。1951年T.C.考普曼从生产和分配活动分析中提出多目标最优化问题，并引入了帕雷托优化的概念。1961年美国学者查纳斯（A.Charnes）和库伯（W.W.Cooper）在他们合著的管理模型和线性规划的工业应用一书中正式提出目

3、标规划，以后这种模型经U杰斯基莱恩和Sang李不断完善改进，并给出了求解目标规划的一般方法单纯形法。,A查纳斯,管理运筹学课件,2020年7月8日星期三,本章主要内容,6.1 目标规划数学模型 6.1.1 基本概念 6.1.2 目标规划的数学模型 6.2 目标规划的基本解法 6.2.1 图解法 6.2.2 单纯形法 6.2.3 序贯算法 6.3 目标规划应用举例 6.3.1 Burnit公司广告策划 6.2.2 产品决策问题 6.2.3 Fruit公司芯片购买决策 本章小结 ,管理运筹学课件,2020年7月8日星期三,目标规划,目标规划（Goal Programming）是针对线性规划目标单一

4、的局限性而提出的，是线性规划的应用拓展，是解决实际问题的一种方法。线性规划是研究资源有效分配和利用，其特点是在满足一组约束条件的情况下，寻求某一个目标的最大值或最小值。而在现实社会中，经常遇到需要考虑多个目标的优化问题。目标规划与传统方法不同，它强调了系统性，其方法在于寻找一个“尽可能”满足所有目标的解，而不是绝对满足这些目标的值。 目标规划有着极大的灵活性，表现在它可以模拟系统的约束和目标优先等级变化的各种模型，为管理决策提供众多的信息。解决目标规划问题首先要根据目标的重要性分清主次先后、轻重缓急，引入偏差变量，将目标按等级转化为目标约束，最终形成可用线性规划方法解决的问题。,管理运筹学课件

5、,2020年7月8日星期三,6.1.1 基本概念,1. 偏差变量：用以表明实际值与超出或未达到目标值的差距，用下列符号表示： d+超出目标的差距，称正偏差变量 d-未达到目标的差距，称负偏差变量 与两者必有一个为零，有三种情况： 第一，当实际值超出规定目标时 ； 第二，当实际值未达到规定目标时 ； 第三，实际值与目标值刚好一致时 。 故恒有 ； 2系统约束： 系统约束指某种资源的使用上受到严格限制。这种限制如同在线性规划中的约束一样，不允许有丝毫超差，故称为刚性约束。如【导入案例】中设备A不允许有超差，称为系统约束，即：,管理运筹学课件,2020年7月8日星期三,6.1.1 基本概念,3目标约

6、束与目标要求 目标规划处理问题的方法是将多目标转化为多个目标约束。如目标利润的约束：甲产品单位利润2元，乙产品单位利润3元，目标要求利润不小于15元，即有目标约束不等式： 添加正负偏差变量，将其变为等式： 当 时，表明 ，达到了目标； 当 时，表明 ，未达到目标，此种情况一但发生，希望越小越好，即目标要求为：,管理运筹学课件,2020年7月8日星期三,6.1.1 基本概念,同理有其他目标约束： 产品比例 设备B利用与加班 设备C的加班,管理运筹学课件,2020年7月8日星期三,【知识要点提醒】,目标规划在处理多目标时所采取的办法是： 第一，列出目标约束不等式； 第二，添加正、负偏差变量，将目标

7、约束不等式变成等式约束； 第三，确定每个目标的目标要求： 当目标约束不等式的约束符为“”时， 当目标约束不等式的约束符为“”时， 当目标约束不等式的约束符为“”时,管理运筹学课件,2020年7月8日星期三,6.1.1 基本概念,4. 目标规划中的目标函数 将目标转换为目标约束后，目标要求仍然是多个，而优化时要求必须合并成一个目标。其方法是按轻重缓急划分优先级和冠以不同的权系数。对两个不同目标，如果其重要程度相差悬殊，为达到一个目标甚至可牺牲另一目标，可将它们划分属不同优先级。优先级是一个定性概念，规定PkPk+1。 在同一优先级内，根据重要程度不同，用权系数确定其优先顺序。权系数是一个具体的数

8、字，通常以“罚款额”、“损失额”作为权系数，对重大的战略性问题，应采取“专家意见法”进行综合评价. 设：P1:目标利润；P2:产品比例；P3:设备B的利用与加班，设备C的加班。在P3中设备B的重要性为C的3倍，则目标函数为：,管理运筹学课件,2020年7月8日星期三,6.1.2 目标规划的数学模型,将上述目标规划的目标约束、目标函数再加上系统约束和变量非负约束，即构成了引例中的目标规划数学模型如下：,管理运筹学课件,2020年7月8日星期三,6.1.2 目标规划的数学模型,目标规划数学模型的一般形式：,优先因子,正偏差权系数,负偏差权系数,目标约束,系统约束,变量非负,管理运筹学课件,2020

9、年7月8日星期三,【知识要点提醒】,其建模步骤： （1）列出全部约束条件（约束不等式） （2）把目标约束不等式左端加上负偏差变量，减去正偏差变量后，化为目标约束等式； （3）对目标赋予相应的优先因子； （4）对同一组优先因子中的各偏差变量，根据重要程度不同，赋予不同的权系数； （5）构造一个按优先因子及权系数和对应的目标偏差量所要实现最小化的目标函数。,管理运筹学课件,2020年7月8日星期三,例6-1,已知某实际问题的线性规划模型为： 假定重新确定这个问题的目标为： P1：z的值应不低于1900； P2：资源1尽可能全部利用。 将此问题转换为目标规划问题，列出数学模型。,管理运筹学课件,20

10、20年7月8日星期三,例6-2,P1：第4用户需求量全部满足； P2：每用户满足率80%； P3：总运费原方案的110%； P4：从工厂2到用户4的路线应尽量避免分配运输任务,设：xij产地i到销地j运送量，原方案最优值：2950,管理运筹学课件,2020年7月8日星期三,例6-2,管理运筹学课件,2020年7月8日星期三,6.2 目标规划的基本解法,用目标规划处理问题的难点在于构造模型时需要事先确定优先级和权系数。而这些信息往往来自人们的主观判断，很难给出一个绝对的数值。通常根据求解结果的各项目标满意程度来修改优先级和权系数，直至满意为止。其流程如下图。 我们将介绍3种方法：图解法、单纯形法

11、和序贯算法。,管理运筹学课件,2020年7月8日星期三,6.2.1 图解法,（1）绘出直角坐标 （2）图示系统约束，确定可行域 （3）按优先级高低，依次图示目标约束，缩小满意解范围。,管理运筹学课件,2020年7月8日星期三,6.2.2 单纯形法,单纯形法步骤： 第1步 列出初始单纯形表 （1）由于目标函数均为负值，为方便起见，不转换为极大； （2）以系统约束的松驰变量、人工变量、目标约束的负偏差变量为初始基变量； （3）检验数行按优先因子分别列出。 第2步 计算检验数，确定换入变量 （1）从第一级优级开始，若检验数存在负数，最小检验数所对应的变量为换入变量。当高级优先级得到优化，转向下一级；

12、 （2）在第k优先级优化过程中，如果破坏了上级优化结果，则迭代停止，k-1以上级目标得到优化，k级以下未得到优化，所得结果为满意解； （3）若所有检验数均非负，所有目标均得到优化，所得结果可称为最优解。 第3步 用最小比值原则确定换出变量 第4步 用换入变量替换换出变量，用行初等变换方法列出新的单纯形表，返回第2步。,管理运筹学课件,2020年7月8日星期三,6.2.2 单纯形法,【例6.4】用单纯形法求目标规划满意解,管理运筹学课件,2020年7月8日星期三,6.2.2 单纯形法,管理运筹学课件,2020年7月8日星期三,6.2.3 序贯算法,若模型的目标函数中含有优先因子，则称为有层次差异

13、的模型。优先因子是个定性的概念，求解一般线性规划的单纯表法不能直接求解，但可以将多目标规划问题分解为若干个单目标的LP，通过序贯式算法进行求解。序贯是数理统计学的一个分支，源于A瓦尔德在1947年发表的一本同名著作，研究的对象是所谓“序贯抽样方案”，其基本思想是：先抽少量样本，根据结果再决定继续抽样，直到决定停止为止。 依据这一思想，先考虑只有系统约束和最高优先级的目标约束，目标函数中的优先因子取“1”，求得其目标要求的偏差变量的值，将其固定，再按优先次序逐级添加目标约束并进行优化，直到全部目标优化完毕为止。,管理运筹学课件,2020年7月8日星期三,【例6.3】用序贯算法求解目标规划问题,管

14、理运筹学课件,2020年7月8日星期三,6.3.1 Burnit公司广告策划,解 设：x1:足球期间插播广告时间 x2:肥皂剧插播广告时间,HIM目标约束,LIP目标约束,HIW目标约束,预算限制,管理运筹学课件,2020年7月8日星期三,6.3.1 Burnit公司广告策划,综上所述：,管理运筹学课件,2020年7月8日星期三,6.3.2 产品决策问题,解 设：x1:产品I产量；x2:产品II产量；x3:产品III产量,长期利润,雇用水平,资本投资,管理运筹学课件,2020年7月8日星期三,6.3.2 产品决策问题,综上所述：,用LINGO求得结果如右。产品I生产8.33，产品III生产1.

15、67，目标1和目标3均得到满足，但目标2超出833人。对此人事部门认为：超员是短期行为，将产生严重后果；财务部门认为：5500万投资也不能突破，故采取带优先权的目标规划，对员工雇用和投资给一个高优先权。,管理运筹学课件,2020年7月8日星期三,6.3.2 产品决策问题,综上所述：,用LINGO解：,d2=d3=0,决策建议：产品I大量生产，III小批量生产，II进一步考察。,管理运筹学课件,2020年7月8日星期三,6.3.3 Fruit公司芯片购买决策,问题： 1.超预算1美元，1美元罚款； 2.预算、优等、良好级、中等分属4个优先级。,设：x1,x2,x3为从供应商1、2、3购买的套数；

16、 x4,x5,x6单独购买优、良、中芯片的个数,问题1：,系统约束,目标约束,约束转换,管理运筹学课件,2020年7月8日星期三,6.3.3 Fruit公司芯片购买决策,数学模型：,优化结果：,管理运筹学课件,2020年7月8日星期三,6.3.3 Fruit公司芯片购买决策,问题2：预算、优等、良好级、中等分属4个优先级。,优化结果： x2=93 x4=10 d2_=340 d3=255 d4=395 其余=0,管理运筹学课件,2020年7月8日星期三,本章小结,本章介绍了目标规划的概念。目标规划是线性规划的应用拓展，它强调了系统性，是解决实际问题的一种有效方法。 目标规划建模是目标规划应用的关键环节，其步骤： 第一步：根据背景材料列出所有约束不等式（包括系统约束和目标约束）； 第二步：对目标约束