运筹学 目标规划

自亚当斯密开始，资产阶级经济学家就认为企业的决策者是“经济人”，他们只以追求经济利益“最大化”为行为准则。西蒙(美国卡内基—梅隆大学,1916-2001年)由于对现代经济管理的决策科学进行了开创性的研究,而荣获了1978年诺贝尔经济学奖。他否定了“最大化”的“经济人”行为准则，提出了“令人满意”的“管理人”行为准则。他认为现代管理决策所追求的不是绝对意义上的最优解，而是相对意义的满意解，追求的目标应是多元的，才能在各方面都“令人满意”。现代管理决策的两个基本假设是：（1）决策者必需考虑决策环境，希望达到一个满意的目标水平；（2）经济组织是一个合作系统，组成它们的各团体也许会有一同的甚至矛盾的目标，但它们必须互相协调、共同对策。因此，管理就是决策，现代管理就是多目标决策。第八章目标规划•线性规划只研究在满足一定条件下，单一目标函数取得最优解，而在企业管理中，经常遇到多目标决策问题，如拟订生产计划时，不仅考虑总产值，同时要考虑利润，产品质量和设备利用率等。这些指标之间的重要程度（即优先顺序）也不相同，有些目标之间往往相互发生矛盾。•求解线性规划问题，首先要求约束条件必须相容，如果约束条件中，由于人力，设备等资源条件的限制，使约束条件之间出现了矛盾，就得不到问题的可行解，但生产还得继续进行，这将给人们进一步应用线性规划方法带来困难。•为了弥补线性规划问题的局限性，解决有限资源和计划指标之间的矛盾，在线性规划基础上，建立目标规划方法，从而使一些线性规划无法解决的问题得到满意的解答。目标规划(goalprogramming)是针对线性规划目标单一的局限性而提出的，是线性规划的应用拓展，是解决实际问题的一种方法。它强调了系统性，其方法在于寻找一个满足所有目标的解，而不是绝对满足这些目标的值。目标规划可用于以下3种类型的决策分析：第一，为了达到一且预定目标，决策系统投入的需要量；第二，对于已给定的有限资源，决策计划目标所能达到的程度；第三，在变化的系统输入和目标体系下，它能提供满意解。多目标规划问题多目标规划问题的提出在实际问题中，可能会同时考虑几个方面都达到最优：产量最高，成本最低，质量最好，利润最大，环境达标，运输满足等。多目标规划能更好地兼顾统筹处理多种目标的关系，求得更切合实际要求的解。目标规划可根据实际情况，分主次地、轻重缓急地考虑问题。引例:在第一章的例1:某工厂生产门窗两种产品，已知的条件如表所示，试制订总利润最大的生产计划。单位产品生产所需时间车间门窗每天可用生产时间（小时）11042021233218单位利润（元）300500模型:求解得:最大利润为36006,221xx12121212max3005004212s.t.3218,0Zxxxxxxxx现在，工厂领导根据市场预测等一系列因素，重新提出如下目标1)窗的销路有下降趋势，故窗的产量应减少,希望不超过门的2倍；2)车间3另有新任务,希望车间3能节省4个工时用于生产新产品;3)每周利润应尽可能达到并超过3000元.若重新建模121212121212max30050042123214s.t.203005003000,0Zxxxxxxxxxxxx该模型无解.怎么办？注意,这里新提的要求有”希望”或”尽可能”,这就表明这样的要求是有弹性的,那么如何去表达这种要求呢?多目标决策问题实际问题决策经常面临的问题：方案优劣并不以单一准则为目标，而是以多重准则为目标约束条件并不完全符合严格的刚性条件，具有一定的弹性可能的弹性约束：最好等于最好不大于最好不小于弹性约束的处理方法实际量＋d－－d+=目标值负偏差变量正偏差变量ddMin最好等于：dMin最好不大于：dMin最好不小于：基本概念1.偏差变量偏差变量：用以表明实际值与超出或未达到目标值的差距，用下列符号表示：d+——超出目标的差距，称为正偏差变量。d-——未达到目标的差距，称为负偏差变量d+与d-两者必有一个为零，有3种情况：第一，当实际值超出规定目标时，d-=0,d+0.第二，当实际值未达到规定目标时，d-0,d+=0.第三，当实际值与目标值相等时，d-=0,d+=0.故恒有：d-·d+=0.2.系统约束系统约束指对某种资源的使用上受到严格限制，不允许有丝毫的超差，故称为刚性约束。3.目标约束是目标规划特有的，我们可以把约束右端项看作要努力追求的目标值，但允许发生正式负偏差，用在约束中加入正、负偏差变量来表示，于是称它们是软约束或弹性约束。4.目标规划中的目标函数——达成函数：达成函数是一个使总偏差量为最小的目标函数。为此对目标赋予相应的优先因子，视目标重要程度相差悬殊来排序,用权系数Pk大小表达其优先顺序。由权系数确定总偏差量为最小的目标函数。系统约束如引例1中的约束x1≦4；2x2≦12；3x1+2x2≦18；目标约束如引例1中的目标,把约束右端项看作要努力追求的目标值，但允许发生正式负偏差，用在约束中加入正、负偏差变量来表示，目标1窗的产量应减少,希望不超过门的2倍：-2x1+x2+d-1-d+1=0;（mind+1）目标2希望车间3能节省4个工时用于生产新产品：3x1+2x2+d-2-d+2=14;（mind-2+d+2）目标3每周利润应尽可能达到并超过3000元:300x1+500x2+d-3-d+3=3000;（mind-3）1122233121212111222123312min()42123218s.t.2032143005003000,0,,0,1,2,3jjZPdPddPdxxxxxxddxxddxxddxxddj目标函数——达成函数：用权系数Pk大小表达以上3个目标的优先顺序。由权系数确定总偏差量为最小的目标函数。1122233()ZPdPddPd用Excel软件求解：目标规划的数学模型一般情形:min()iiiiizPWdWd11(1,,)..()(1,,)0(1,,),,0(1,,)nijjiiijnijjijjiicxddgimstaxbilxjnddim目标约束系统约束变量非负约束建模型步骤:(1)列出全部约束条件;(2)把要达到指标的约束不等式加上正、负偏差变量后，化为目标约束等式；(3)对目标赋予相应的优先因子;(4)对同一组优先因子中的各偏差变量,根据重要程度不同,赋予不同的权系数;(5)构造一个按优先因子及权系数和对应的目标偏差变量所要实现最小化的目标函数.应用案例分析例2轿车生产的目标规划求解某汽车制造厂拟生产A,B,C三种型号轿车,相关数据见下表,设xi表示生产A,B,C三种型号轿车的数量(i=1,2,3),则有求利润最大的数学模型:且为整数工时约束0,,91510)(24012108..45.35.2max321321321321xxxxxxxxxtsxxxZ解之,得最优解为:x*1=2,x*2=14,x*3=7,最优值为Z*max=82根据市场情况调整生产方案,要求:1、车型B的产量应不大于车型C的产量；2、适当降低车型A的产量；3、应尽量充分利用原设备台时，而不要加班；4、利润尽可能达到或超过82。11132min;0dddxx1221min;2dddx3333321min;24012108ddddxxx444321min;8245.35.2dddxxx4,3,2,1,0,,0,,9;;15;10;8245.35.2;24012108;10;0..)(min32132144321333212211132443332211iddxxxxxxddxxxddxxxddxddxxtsdpddpdpdpZii目标规划模型：Excel求解特征向量法(层次分析法）特征向量法是层次分析法中针对上一层次某元素对本层次各元素的相对重要性进行两两比较,给出判断并用数值表示出来(判断矩阵)然后求出其特征向量作为权数的一种方法.步骤：第一步：构造判断矩阵B1B2…BnB1b11b12…b1nB2b21b22…b2n……………Bm.bm1bm2…bmn多目标转化为单目标的方法设有个目标，要比较它们对nnzzzZ,,,21特征向量法：总目标Z的影响程度，可设z1,z2,…zn为其线性组合：Z=w1z1+w2z2+…+wnzn是达成函数。其中w1,w2,…wn是权重系数，其满足：wi0,11niiwijbijnnnnnnnnijbbbbbbbbbbB212222111211用表示第个因素相对于第个因素的比较结果，则称为成对比较矩阵。从z1,z2,…zn中任取zi与zj比较它们对于Z贡献（重要程度）的大小，按照以下标度给zi/zj赋值：zi/zj＝1，认为“zi与zj重要程度相同”zi/zj＝3，认为“zi比zj重要程度略大”zi/zj＝5，认为“zi比zj重要程度大”zi/zj＝7，认为“zi比zj重要程度大很多”zi/zj＝9，认为“zi比zj重要程度绝对大”当比值为2，4，6，8时认为介于前后中间状态。１３５７９尺度第个因素与第个因素的影响相同ij第个因素比第个因素的影响稍强第个因素比第个因素的影响强第个因素比第个因素的影响明强第个因素比第个因素的影响绝对地强iiiijjjj含义比较尺度：（1~9尺度的含义）2,4,6,8表示第个因素相对于第个因素的影响介于上述两个相邻等级之间。当5个等级不够用时，可以使用这几个数。以上不难定义各尺度倒数的含义，而且。ji1,1ijiijibbb一般而言，判断矩阵的数值是根据数据资料、专家意见和分析者的认识，加以平衡后给出的。如果判断矩阵存在“传递”关系：（i，j，k＝1，2，3，…，n）则称它具有完全一致性，或称B为一致矩阵。否则称B不是一致矩阵。由于在复杂的事物面前我们的判断是不可能具有“传递性”，故一般B不是一致矩阵。但为了考察AHP决策分析方法得出的结果是否基本合理，允许B不一致，但要确定不一致的允许范围，即要求B近似一致，故需要对判断矩阵进行一致性检验。ijjkikbbb一致性检验的方法：可证：B的最大特征根n,且=n时为一致阵。1nnCI定义一致性指标:CI越大，不一致越严重RI000.580.901.121.241.321.411.451.491.51n1234567891110为衡量CI的大小，引入随机一致性指标RI——随机模拟得到aij,形成A，计算CI即得RI。定义一致性比率CR=CI/RI当CR0.1时，通过一致性检验Saaty的结果如下因此否则，当CR0.1时，就需要调整判断矩阵，直到满意为止。若判断矩阵B通过一致性检验，那么求它的最大特征值λmax和属于它的最大特征值λmax的特征向量V=，并令即可。而且这样的权系数是唯一的。1;1,2,,jjniivwjnv},,{21nvvv求它的最大特征值λmax和属于它的最大特征值λmax的特征向量V，可用数学软件求，也可用简便算法。(一)方根法计算判断矩阵每一行元素的乘积计算的n次方根njijinibM1),,2,1(),,2,1(niMWniiiM权系数的简便算法将向量＝归一化：则即为所求的特征向量。计算最大特征根表示向量AW的第i个分量。TnW),2,1(1niniiinWAW1max)(TniAW)((二)和积法将判断矩阵每一列归一化：对按列归一化的判断矩阵