目标规划PPT课件

1、 目标规划是在线性规划的基础上，为适应经济管理中多目标决策的需要而逐步发展起来的一个分支。 2 2、线性规划求最优解；目标规划是找到一个满意解。 1 1、线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题；而目标规划是多个目标决策，可求得更切合实际的解。一、目标规划概述一、目标规划概述（一）、目标规划与线性规划的比较（一）、目标规划与线性规划的比较第1页/共36页 4 4、线性规划的最优解是绝对意义下的最优，但需花去大量的人力、物力、财力才能得到；实际过程中，只要求得满意解，就能满足需要（或更能满足需要）。 3 3、线性规划中的约束条件是同等重要的，是硬约束；而目标规划中有轻重缓急和

2、主次之分，即有优先权。目前，已经在经济计划、生产管理、经营管理、市场分析、财务管理等方面得到了广泛的应用。第2页/共36页 例一、某兵工厂计划生产甲乙两种产品，这些产品占用设备如下表？同时，考虑如下几个方面：1 力求使利润指标不低于15元。2考虑到市场要求，甲乙两种产品的生产量需保持1：2的比例。3 A为贵重设备，严格禁止超时使用。4 设备C可以适当加班，但要控制；设备B既要充分利用，又尽可能不加班，又在重要性上设备B是C的三倍。试建立此问题的数学模型。32单件利润1550C 1604B1222A资源限制乙甲 单位 产品资源 消耗（二）、目标规划的基本概念（二）、目标规划的基本概念第3页/共3

3、6页设：甲产品 x1 ，乙产品 x2 一般有：maxZ=2 x1 + 3 x2 2 x1 +2 x2 12 4 x1 +0 x2 16 0 x1 +5 x2 15 x1 ， x2 0对此问题我们可求得最优解为（3，3）最优值为15若考虑上述四个方面，则问题就不再是单纯的线型规划问题了。 显然，这是一个多目标规划问题，用线性规划方法很难找到最优解。第4页/共36页 目标规划通过引入目标值和偏差变量，可以将目标函数转化为目标约束。 目标值：是指预先给定的某个目标的一个期望值。 实现值或决策值：是指当决策变量x xj j 选定以后，目标函数的对应值。 偏差变量（事先无法确定的未知数）：是指实现值和目

4、标值之间的差异, ,记为 d d 。 正偏差变量：表示实现值超过目标值的部分，记为 d d。 负偏差变量：表示实现值未达到目标值的部分，记为 d d。1 1、目标值和偏差变量、目标值和偏差变量第5页/共36页 当完成或超额完成规定的指标则表示：d d0, d d0 当未完成规定的指标则表示： d d0, d d0 当恰好完成指标时则表示： d d0, d d0 d d d d 0 0 成立。 引入了目标值和正、负偏差变量后，就对某一问题有了新的限制，即目标约束。 目标约束既可对原目标函数起作用，也可对原约束起作用。目标约束是目标规划中特有的，是软约束。在一次决策中，实现值不可能既超过目标值又未

5、达到目标值，故有 d d d d 0,0,并规定d d0, d d02 2、目标约束和绝对约束、目标约束和绝对约束第6页/共36页 绝对约束（系统约束）是指必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对约束，否则无可行解。所以，绝对约束是硬约束。 例如：在例一中，规定Z1 的目标值为 15,正、负偏差为d、d ,则目标函数可以转换为目标约束，既2 x1 + 3 x2 15， 同样，若规定甲的产品和乙的产品保持1：2的比例允许有偏差 则有 11dd155442ddx 若C C可以适当加班，但要控制，则0, 02222221ddddxx第7页/共36页 达成函数是一个使总偏差量

6、为最小的目标函数，记为 minZ = f（d、d）。 一般说来，有以下三种情况，但只能出现其中之一： .要求恰好达到规定的目标值，即正、负偏差变量要尽可能小，则minZ = f（d d）。 .要求不超过目标值，即允许达不到目标值，也就是正偏差变量尽可能小，则minZ = f（d）。 .要求超过目标值，即超过量不限，但不低于目标值，也就是负偏差变量尽可能小，则minZ = f（d）。 对于由绝对约束转化而来的目标函数，也照上述处理即可。3 3、达成函数（即目标规划中的目标函数）、达成函数（即目标规划中的目标函数）第8页/共36页 优先因子Pk 是将决策目标按其重要程度排序并表示出来。P1P2Pk

7、Pk+1PK ，k=1.2K。 权系数k 区别具有相同优先因子的两个目标的差别，决策者可视具体情况而定。 对于这种解来说，前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现。4 4、优先因子（优先等级）与优先权系数、优先因子（优先等级）与优先权系数 5 5、满意解（具有层次意义的解）、满意解（具有层次意义的解）第9页/共36页 若在例一中有如下要求： 1、最重要目标是利润，列为第一优先级； 2、其次目标是甲乙产品的产量尽可能的保持1：2的比例，列为第二优先级； 3、设备C、B的工作时间所控制，列为第三优先级，且在此优先级中设备B的重要性比设备C大三倍

8、。试建立目标规划模型。 分析：题目有三个目标层次，包含四个目标值。 第一目标： 第二目标 第三目标，设备的重要性，此时有设备B和C，因为设备B的重要性比设备C大三倍，因此目标函数中在设备B的偏差变量前冠以权系数311dP22 dd例二、例二、第10页/共36页第三目标：)(3333 ddP)4 . 3 . 2 . 1( 0 ., 03000 10 3 12 2 2 155 164 0 x2- 2 1532)(3)(min212121442331221112133322211jddxxxxxddxddxddxddxxddPddPdPZjj目标规划模型为：)(43dP)(43dP第11页/共36页

9、（一）、模型的一般形式)2 .1( 0 .n)1.2(j 0)2 .1( ).()2 .1( )(min1111LlddxmibxaLlqddxcddPZlljnjijijnjllljkjKkLllkllklk二、目标规划的数学模型二、目标规划的数学模型第12页/共36页（二）、建模的步骤 1 1、根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束； klkl和和 4 4、对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系数 。 3 3、给各目标赋予相应的优先因子 P Pk k（k=1.2k=1.2K K）。 2 2、可根据决策者的需要，将某些或全部

10、绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可。第13页/共36页 5 5、根据决策者的要求，按下列情况之一构造一个由 优先因子和权系数相对应的偏差变量组成的，要求实现极小化的目标函数，即达成函数。llddldld. .恰好达到目标值，取 。. .允许超过目标值，取 。. .不允许超过目标值，取 。第14页/共36页（三）、小结线性规划线性规划LPLP目标规划目标规划GPGP目标函数目标函数min , max系数可正负系数可正负min , 偏差变量偏差变量系数系数0 0变量变量x xi,i, x xs s x xa a x xi i x xs s x xa a

11、d d约束条件约束条件系统约束系统约束（绝对约束）（绝对约束）目标约束目标约束系统约束系统约束解解最优最优最满意最满意第15页/共36页 图解法同样适用两个变量的目标规划问题，但其操作简单，原理一目了然。同时，也有助于理解一般目标规划的求解原理和过程。 图解法解题步骤如下： 1、确定各约束条件的可行域，即将所有约束条件（包括目标约束和绝对约束，暂不考虑正负偏差变量）在坐标平面上表示出来； 2、在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向；三、目标规划的图解法三、目标规划的图解法第16页/共36页 3、求满足最高优先等级目标的解； 4、转到下一个优先等级的目标，再不破坏所有较

12、高优先等级目标的前提下，求出该优先等级目标的解； 5、重复4，直到所有优先等级的目标都已审查完毕为止； 6、确定最优解和满意解。例一、用图解法求解目标规划问题)2 . 1(0, 08 2 102 5 .621210)(min21212221112122111lddxxxddxxddxxdPddPZll第17页/共36页01 2 3 4 5 6 7 8 1 2 3 4 5 6 Ax2 x1B1d1d2d2dC B (0.6250 , 4.6875) C (0 , 5.2083) ， B、C 线段上的所有点均是该问题的解（无穷多最优解）。第18页/共36页Cj c1c2cn+2mCBXBb x1x

13、2 xn+2m cj1xj1 bo1e11e12e1n+2mcj2xj2bo2e21e22e2n+2m cjmxjm bomem1em2emn+2mkjP1 111121n+2mP2 221222n+2mPK K m1m2mn+2m四、目标规划的单纯形法四、目标规划的单纯形法（一）、一般形式：（一）、一般形式：第19页/共36页 1 1、建立初始单纯形表。 一般假定初始解在原点，即以约束条件中的所有负偏差变量或松弛变量为初始基变量，按目标优先等级从左至右分别计算出各列的检验数，填入表的下半部 。 2 2、检验是否为满意解。判别准则如下： . .首先检查k (k=1.2K)是否全部为零？如果全部

14、为零，则表示目标均已全部达到，获得满意解，停止计算转到第6 6步；否则转入。 （二）、单纯形法的计算步骤（二）、单纯形法的计算步骤第20页/共36页 . .如果某一个k 0。说明第k k个优先等级的目标尚未达到, ,必须检查Pk这一的检验数kj(j=1.2(j=1.2n+2m).n+2m).若Pk这一行某些负检验数的同列上面（较高优先等级）没有正检验数，说明未得到满意解，应继续改进，转到第3 3步；若Pk这一行全部负检验数的同列上面（较高优先等级）都有正检验数，说明目标虽没达到，但已不能改进，故得满意解，转到第6 6步。 3 3、确定进基变量。 在Pk行，从那些上面没有正检验数的负检验数中，选

15、绝对值最大者，对应的变量xs就是进基变量。若Pk行中有几个相同的绝对值最大者，则依次比较它们各列下部的检验数，取其绝对值最大的负检验数的所在列的xs为进基变量。假如仍无法确定，则选最左边的变量（变量下标小者）为进基变量。第21页/共36页 4 4、确定出基变量 其方法同线性规划，即依据最小比值法则故确定xr为出基变量，e ersrs为主元素。若有几个相同的行可供选择时，选最上面那一行所对应得变量为xr 。rsorisissiebeeb0/min 5 5、旋转变换（变量迭代）。 以为主元素进行变换，得到新的单纯形表，获得一组新解，返回到第2 2步。 6 6、对求得的解进行分析 若计算结果满意，停

16、止运算；若不满意，需修改模型，即调整目标优先等级和权系数，或者改变目标值，重新进行第1 1步。第22页/共36页)4 . 3 . 2 . 1( 0, 0100 60 140 2 250012305 . 2min214423312221112123423211lddxddxddxddxxddxxdPdPdPdPZll例一、用单纯形法求解下列目标规划问题例一、用单纯形法求解下列目标规划问题第23页/共36页Cj00P1000000000000002.5P20P200000P30000CBXBbx1x2P125003012110000000140210011000006010000011000100

17、0100000011kjP1 -2500301201000000P2 000000002.501P3 000000100001d1d2d2d3d3d4d4d1d2d3d4d= min2500/30,140/2,60/1=60 ,故 为换出变量。3d第24页/共36页Cj 00P100P302.5P20P2CBXBbx1x2P1700012110030300002001001122000 x160100000110001000100000011kjP1 7000120100303000P2 000000002.501P3 000000100001d1d2d2d3d3d4d4d1d2d4d= mi

18、n700/30,20/2, =10 ,故 为换出变量。2d第25页/共36页Cj 00P100P302.5P20P2CBXBbx1x2P14000-31-1-151500002.5P21001/2001/2-1/2-11000 x17011/2001/2-1/200000100010000001-1kjP1 -400030115-150000P2 -250-5/400-5/45/45/2001P3 000000100001d1d2d2d3d3d4d4d1d4d= min400/15, =10 ,故 为换出变量。3d1d第26页/共36页Cj 00P100P302.5P20P2CBXBbx1x2

19、P380/30-1/51/15-1/15-1100002.5P270/302/51/30-1/3000-11000 x1250/312/51/30-1/3000000001000100000011kjP1 00010000000P2 -175/30-1-1/121/12002/5001P3 -80/301/5-1/151/151000001d1d2d2d3d3d4d4d4d= min,350/6,1250/6,100/1=75 ,故 为换出变量。2d3d3d第27页/共36页Cj 00P100P302.5P20P2CBXBbx1x2P3115/3001/12-1/12-11-1/21/2000

20、 x2175/3011/12-1/1200-5/25/2000 x160100000-11000125/300-1/121/12005/2-5/211kjP1 00010000000P2 000000005/201P3 -115/300-1/121/12101/2-1/2001d1d2d2d3d3d4d4d4d2d表中3115/30，说明P3 优先等级目标没有实现，但已无法改进，得到满意解 x1 60， x2 175/3， 115/3， 125/3。4d2d第28页/共36页 结果分析：计算结果表明，工厂应生产A产品60件，B产品175/3件，2500元的利润目标刚好达到。 125/3，表明产

21、品比最高限额少125/3件，满足要求。 115/3 表明甲资源超过库存115/3公斤，该目标没有达到。 从表中还可以看到，P3 的检验数还有负数，但其高等级的检验数却是正数，要保证 P1目标实现，P3等级目标则无法实现。所以，按现有消耗水平和资源库存量，无法实现25002500元的利润目标。 可考虑如下措施：降低A、B产品对甲资源的消耗量，以满足现有甲资源库存量的目标；或改变P3等级目标的指标值，增加甲资源115/3115/3公斤。 若很难实现上述措施，则需改变现有目标的优先等级，以取得可行的满意解果。4d2d第29页/共36页 练习: 某公司分厂用一条生产线生产两种产品A和B ，每周生产线运

22、行时间为60小时，生产一台A产品需要4小时，生产一台B产品需要6小时根据市场预测，A、B产品平均销售量分别为每周9、8台，它们销售利润分别为12、18万元。在制定生产计划时，经理考虑下述4项目标：首先，产量不能超过市场预测的销售量； 其次，工人加班时间最少； 第三，希望总利润最大； 最后，要尽可能满足市场需求, 当不能满足时, 市场认为B产品的重要性是A产品的2倍 试建立这个问题的数学模型第30页/共36页讨论： 若把总利润最大看作目标，而把产量不能超过市场预测的销售量、工人加班时间最少和要尽可能满足市场需求的目标看作约束，则可建立一个单目标线性规划模型 设决策变量 x1，x2 分别为产品A，B的产量 Max Z