第9章-目标规划

运筹学1运筹谋划一石多鸟2第九章目标规划•§1目标规划问题举例•§2目标规划的图解法•§3复杂情况下的目标规划•§4加权目标规划3§1目标规划问题举例例1．企业生产•不同企业的生产目标是不同的。多数企业追求最大的经济效益。但随着环境问题的日益突出，可持续发展已经成为全社会所必须考虑的问题。因此，企业生产就不能再如以往那样只考虑企业利润，必须承担起社会责任，要考虑环境污染、社会效益、公众形象等多个方面。兼顾好这几者关系，企业才可能保持长期的发展。4例2．商务活动•企业在进行盈亏平衡预算时，不能只集中在一种产品上，因为某一种产品的投入和产出仅仅是企业所有投入和产出的一部分。因此，需要用多产品的盈亏分析来解决具有多个盈亏平衡点的决策问题（多产品的盈亏平衡点往往是不一致的）。例3．投资•企业投资时不仅仅要考虑收益率，还要考虑风险。一般地，风险大的投资其收益率更高。因此，企业管理者只有在对收益率和风险承受水平有明确的期望值时，才能得到满意的决策。§1目标规划问题举例5例4．裁员•同样的，企业裁员时要考虑很多可能彼此矛盾的因素。裁员的首要目的是压缩人员开支，但在人人自危的同时员工的忠诚度就很难保证，此外，员工的心理压力、工作压力等都会增加，可能产生负面影响。例5．营销•营销方案的策划和执行存在多个目标。既希望能达到立竿见影的效果，又希望营销的成本控制在某一个范围内。此外，营销活动的深入程度也决定了营销效果的好坏和持续时间。§1目标规划问题举例6目标规划是在线性规划的基础上，为适应经济管理中多目标决策的需要而逐步发展起来的一个分支。2、线性规划求最优解；目标规划是找到一个满意解。1、线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题；而目标规划是多个目标决策，可求得更切合实际的解。一、目标规划概述（一）、目标规划与线性规划的比较§1目标规划问题举例74、线性规划的最优解是绝对意义下的最优，但需花去大量的人力、物力、财力才能得到；实际过程中，只要求得满意解，就能满足需要（或更能满足需要）。3、线性规划中的约束条件是同等重要的，是硬约束；而目标规划中有轻重缓急和主次之分，即有优先权。目前，已经在经济计划、生产管理、经营管理、市场分析、财务管理等方面得到了广泛的应用。§1目标规划问题举例例1、某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料如表所示。试制定生产计划，使获得的利润最大？同时，根据市场预测，甲的销路不是太好，应尽可能少生产；乙的销路较好，可以扩大生产。试建立此问题的数学模型。12070单件利润3000103设备台时200054煤炭360049钢材资源限制乙甲单位产品资源消耗设：甲产品x1，乙产品x2一般有：maxZ=70x1+120x29x1+4x2≤36004x1+5x2≤20003x1+10x2≤3000x1，x2≥0同时：maxZ1=70x1+120x2minZ2=x1maxZ3=x29x1+4x2≤36004x1+5x2≤20003x1+10x2≤3000x1，x2≥0显然，这是一个多目标规划问题，用线性规划方法很难找到最优解。12070单件利润3000103设备台时200054煤炭360049钢材资源限制乙甲单位产品资源目标规划通过引入目标值和偏差变量，可以将目标函数转化为目标约束。目标值：是指预先给定的某个目标的一个期望值。实现值或决策值：是指当决策变量xj选定以后，目标函数的对应值。偏差变量（事先无法确定的未知数）：是指实现值和目标值之间的差异,记为d。正偏差变量：表示实现值超过目标值的部分，记为d＋。负偏差变量：表示实现值未达到目标值的部分，记为d－。1、目标值和偏差变量当完成或超额完成规定的指标则表示：d＋≥0,d－＝0当未完成规定的指标则表示：d＋＝0,d－≥0当恰好完成指标时则表示：d＋＝0,d－＝0∴d＋×d－＝0成立。引入了目标值和正、负偏差变量后，就对某一问题有了新的限制，既目标约束。目标约束即可对原目标函数起作用，也可对原约束起作用。目标约束是目标规划中特有的，是软约束。在一次决策中，实现值不可能既超过目标值又未达到目标值，故有d＋×d－＝0,并规定d＋≥0,d－≥02、目标约束和绝对约束12绝对约束（系统约束）是指必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对约束，否则无可行解。所以，绝对约束是硬约束。例如：在例1中，规定Z1的目标值为5000,正、负偏差为d＋、d－,则目标函数可以转换为目标约束，既70x1+120x2＋＝5000，同样，若规定Z2＝200，Z3＝250则有11dd200221ddx250332ddx)3.2.1(0,jddjj若规定3600的钢材尽量用完，原式9x1+4x2≤3600则变为0,360049444421ddddxx§1目标规划问题举例13§1目标规划问题举例目标规划中的目标函数是一个使总偏差量为最小的函数，记为minZ=f（d＋、d－）。一般说来，有以下三种情况，但只能出现其中之一:⑴要求恰好达到规定的目标值，即正、负偏差变量要尽可能小，则minZ=f（d＋＋d－）。⑵要求不超过目标值，即允许达不到目标值，也就是正偏差变量尽可能小，则minZ=f（d＋）。⑶要求超过目标值，即超过量不限，但不低于目标值，也就是负偏差变量尽可能小，则minZ=f（d－）对于由绝对约束转化而来的目标函数，也照上述处理即可。3、目标规划中的目标函数14§1目标规划问题举例优先因子Pk是将决策目标按其重要程度排序并表示出来。P1P2…PkPk+1…Pn，k=1.2…n。权系数ωk区别具有相同优先因子的两个目标的差别，决策者可视具体情况而定。对于这种解来说，前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现。4、优先因子（优先等级）与优先权系数5、满意解（具有层次意义的解）若在例1中提出下列要求：1）完成或超额完成利润指标5000元；2）产品甲不超过200件，产品乙不低于250件，产品甲与产品乙重要程度为7：12；3）现有钢材3600吨尽量用完。试建立目标规划模型。分析：该问题中有三个目标层次，包含四个目标值。第一目标：第二目标：有两个要求即甲，乙，但两个具有相同的优先因子，权系数为7:12。)(11dP32dd)127(322ddP例2、第三目标：)(443ddP1611223344121112223312441212min()(712)()701205000200250943600452000310ZPdPddPddxxddxddxddxxddxxxx-+-+--+-+-+-+=++++++-=+-=+-=++-=+?+1230000,.0(1.2.3.4)jjxddj+--ìïïïïïïíïïï£ïï吵=ïî目标规划模型为：§1目标规划问题举例17•step1•目标函数值为:0•变量解相差值•-----------------------•x100•x241.6670•d1-01•d1+00•d2-2000•d2+00•d3-208.3330•d3+00•d4-3433.3330•d4+00•step2•目标函数值为:0•变量解相差值•-----------------------•x100•x22500•d1-00•d1+250000•d2-2000•d2+07•d3-012•d3+00•d4-26000•d4+00•step3•目标函数值为:1100•变量解相差值•-----------------------•x1166.6670•x22500•d1-00•d1+36666.6670•d2-33.3330•d2+015.167•d3-026•d3+026•d4-11000•d4+02练习：某厂生产Ⅰ、Ⅱ两种产品，有关数据如表所示。试求获利最大的生产方案？ⅠⅡ拥有量原材料2111设备(台时)1210单件利润810在此基础上考虑：1、产品Ⅱ的产量不低于产品Ⅰ的产量；2、充分利用设备有效台时，不加班；3、利润不小于56元。解:分析第一目标：即产品Ⅰ的产量不大于Ⅱ的产量。第二目标：11()Pd+)(222ddP第三目标：33()Pd-11222331211122212331212min()()()0210810562110,,0(1,2,3)jjZPdPddPdxxddxxddxxddxxxddj++---+-+-++--=+++ì-+-=ïï++-=ïï++-=íï+?ïï吵=ïî规划模型(P197E9)：22§1目标规划问题举例23§1目标规划问题举例（一）、模型的一般形式1111min()(1,2)(.)(1,2)0(j1,2n),0(1,2)KLkkllkllklnkjjllljnijjijjllZPddcxddqlLaxbimxddlLww--++==-+==+-=+ì+-==ïïïïï??íïï?ïï?ïî邋åå二、目标规划的数学模型243、对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系wk。（二）、建模的步骤1、根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；2、给各目标赋予相应的优先因子Pk（k=1，2…K）。4、根据决策者的要求，按下列情况之一构造一个由优先因子和权系数相对应的偏差变量组成的，要求实现极小化的目标函数，即达成函数。⑴.恰好达到目标值，取。⑵.允许超过目标值，取。⑶.不允许超过目标值，取。llddldld§1目标规划问题举例25（三）、小结线性规划LP目标规划GP目标函数min,max系数可正负min,偏差变量系数≥0变量xi,xsxaxixsxad约束条件系统约束（绝对约束）目标约束系统约束解最优最满意§1目标规划问题举例26§2目标规划的图解法图解法同样适用两个变量的目标规划问题，但其操作简单，原理一目了然。同时，也有助于理解一般目标规划的求解原理和过程。图解法解题步骤如下：1、确定各约束条件的可行域，即将所有约束条件（包括目标约束和绝对约束，暂不考虑正负偏差变量）在坐标平面上表示出来；2、在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向；3、求满足最高优先等级目标的解；274、转到下一个优先等级的目标，在不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解；5、重复4，直到所有优先等级的目标都已审查完毕为止；6、确定最优解和满意解。例3、用图解法求解目标规划问题11122121112221212min()()101262.5210280,0(1,2)llZPddPdxxddxxddxxxddl+---+-++--=++ì++-=ïï++-=ïí+?ïïï吵=î§2目标规划的图解法012345678123456⑴⑵⑶Ax2x1B1d1d2d2dCB(0.6250,4.6875)C(0,5.2083)，B、C线段上的所有点均是该问题的解（无穷多最优解）。5.62121021xx11122121112221212min()()101262.5210280,0(1,2)llZPddPdxxddxxddxxxddl+---+-++--=++ì++-=ïï++-=ïí+?ïïï吵=î10221xx8221xx29§3复杂情况下的目标规划例4．一工艺品厂商手工生产某两种工艺品A、B，已知生产一件产品A需要耗费人力2工时，生产一件产品B需要耗费人力3工时。A、B产品的单位利润分别为250元和125元。为了最大效率地利用人力资源，确定生产的首要任务是保证人员高负荷生产，要求每周总耗费人力资源不能低于600工时，但也不能超过680工时的极限；次要任务是要求每周的利润超过70000元；在前两个任务的前提下，为了保证库存需要，要求每周产品A和B的产量分别不低于200和120件，因为B产品比A产品更重要，不妨假设B完成最低产量120件的重要性是A完成200件的重要性的2倍。试求如何安