第10章_目标规划

1、目目 标标 规规 划划(Goal programming)目标规划的数学模型目标规划的数学模型目标规划的图解法目标规划的图解法目标规划的单纯形法目标规划的单纯形法 目标规划是在线性规划的基础上，为适应经济管理目标规划是在线性规划的基础上，为适应经济管理中多目标决策的需要而逐步发展起来的一个分支。中多目标决策的需要而逐步发展起来的一个分支。 例一、某厂计划在下一个生产周期内生产甲、乙两例一、某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料如表所示。试制定生产计划，使获种产品，已知资料如表所示。试制定生产计划，使获得的利润最大？同时，根据市场预测，甲的销路不是得的利润最大？同时，根据市场预测

2、，甲的销路不是太好，应尽可能少生产；乙的销路较好，可以扩大生太好，应尽可能少生产；乙的销路较好，可以扩大生产。试建立此问题的数学模型。产。试建立此问题的数学模型。12070单件利润单件利润3000103设备台时设备台时200054煤炭煤炭360049钢材钢材资源限制资源限制乙乙甲甲 单位单位 产品产品资源资源 消耗消耗一、目标规划模型一、目标规划模型设：甲产品设：甲产品 x1 ，乙产品乙产品 x2 一般有：一般有：maxZ=70 x1 + 120 x2 9 x1 +4 x2 3600 4 x1 +5 x2 2000 3 x1 +10 x2 3000 x1 ， x2 0同时：同时：maxZ1=7

3、0 x1 + 120 x2 minZ2= x1 maxZ3= x2 9 x1 +4 x2 3600 4 x1 +5 x2 2000 3 x1 +10 x2 3000 x1 ， x2 0 显然，这是一个多目标规划问题。显然，这是一个多目标规划问题。 如何将多目标转化为单目标如何将多目标转化为单目标 如何表示不同目标的主次如何表示不同目标的主次 如何求解如何求解若在上例中提出下列要求：若在上例中提出下列要求： 1、完成或超额完成利润指标、完成或超额完成利润指标 50000元；元； 2、产品甲不超过、产品甲不超过 200件，产品乙不低于件，产品乙不低于 250件；件； 3、现有钢材、现有钢材 360

4、0吨必须用完。吨必须用完。50000120701121ddxx：，因此，将上两式合成而建模时却都要考虑到，当然优化前并不知道实际情况只有一种可能）（或：）（：，实现结果有两种可能对于50000120705000012070500001207050000120701112121112121sdxxxxsdxxxx0001111dddd，且有，规定200221ddx250332ddx2、产品甲不超过、产品甲不超过 200件，产品乙不低于件，产品乙不低于 250件；件；200200200200211211dxxdxx，也可能是；，甲产量可能是3 3、36003600吨钢材必须用完吨钢材必须用完 36

5、00494421ddxx360049360049 3600493600494212142121dxxxxdxxxx可能没用完：可能用完：250250250250322322dxxdxx，也可能是；，乙产量可能是 目标值：目标值：预先给定的某个目标的一个期望值预先给定的某个目标的一个期望值e。 实现值或决策值实现值或决策值：当决策变量：当决策变量x xj j 被求出以后，目标被求出以后，目标函数的对应值。函数的对应值。 偏差变量偏差变量（事先无法确定的未知数）：实现值和目（事先无法确定的未知数）：实现值和目标值之间的差异标值之间的差异, ,记为记为 d d。 正偏差变量正偏差变量：实现值超过目标

6、值的部分，记为：实现值超过目标值的部分，记为d。 负偏差变量负偏差变量：实现值未达到目标值的部分，记为：实现值未达到目标值的部分，记为 d。1 1、目标值和偏差变量、目标值和偏差变量 通过引入目标值和偏差变量，使上述三个要求变成通过引入目标值和偏差变量，使上述三个要求变成相应的约束条件，即目标约束。相应的约束条件，即目标约束。 目标约束是目标规划中特有的，是软约束。目标约束是目标规划中特有的，是软约束。 当完成或超额完成规定的指标则表示：当完成或超额完成规定的指标则表示：d d0, d d0 当未完成规定的指标则表示：当未完成规定的指标则表示： d d0, d d0 当恰好完成指标时则表示：当

7、恰好完成指标时则表示： d d0, d d0 d d d d 0 0 成立。成立。 引入了目标值和正、负偏差变量后，就对某一问题引入了目标值和正、负偏差变量后，就对某一问题有了新的限制，即有了新的限制，即目标约束目标约束。在一次决策中，实现值不可能既超过目标值又未达在一次决策中，实现值不可能既超过目标值又未达到目标值，故有到目标值，故有 d d d d 0,0,并规定并规定d d0, d d02 2、目标约束和绝对约束、目标约束和绝对约束 绝对约束绝对约束：必须严格满足的等式或不等式约束。：必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对约束，有一如线性规划中的所有约束条件都

8、是绝对约束，有一个不满足就无可行解。所以，绝对约束是硬约束。个不满足就无可行解。所以，绝对约束是硬约束。)4 . 3 . 2 . 1( 0 ., 03000 10 3 2000 5 4 36004 9 250 200 500001207021212144213322211121jddxxxxxddxxddxddxddxxjj)()127(min44332211ddPddPdPZ目标约束目标约束（软约束）（软约束）绝对约束绝对约束（硬约束）（硬约束） 目标函数是一个使总偏差量为最小的目标函数，记为目标函数是一个使总偏差量为最小的目标函数，记为 minZ = f（d、d）。）。 一般说来，有以下三

9、种情况，但只能出现其中之一：一般说来，有以下三种情况，但只能出现其中之一： 3 3、目标函数、目标函数 要求恰好达到规定的目标值，即正、负偏差变量要求恰好达到规定的目标值，即正、负偏差变量要尽可能小，则要尽可能小，则minZ = f（d d）。）。 要求不超过目标值，即允许达不到目标值，也就是要求不超过目标值，即允许达不到目标值，也就是正偏差变量尽可能小，则正偏差变量尽可能小，则minZ = f（d）。）。 要求不低于目标值，即超过量不限，也就是负偏差要求不低于目标值，即超过量不限，也就是负偏差变量尽可能小，则变量尽可能小，则minZ = f（d）。）。 对于由绝对约束转化而来的目标函数，也照

10、上述处对于由绝对约束转化而来的目标函数，也照上述处理即可。理即可。 优先因子优先因子Pk 是将决策目标按其重要程度排序并表是将决策目标按其重要程度排序并表示出来。示出来。P1P2PkPk+1PK ，k=1.2K。 权系数权系数k 区别具有相同优先因子的两个目标的差区别具有相同优先因子的两个目标的差别，决策者可视具体情况而定。别，决策者可视具体情况而定。 对于这种解来说，前面的目标可以保证实现或部分对于这种解来说，前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现。有些可能就不能实现。4 4、优先因子（优

11、先等级）与优先权系数、优先因子（优先等级）与优先权系数 5 5、满意解（具有层次意义的解）、满意解（具有层次意义的解）36004 9 250 200 500001207044213322211121ddxxddxddxddxx 对于上例中的目标：对于上例中的目标： 1、完成或超额完成利润指标、完成或超额完成利润指标 50000元；元； 2、产品甲不超过、产品甲不超过 200件，产品乙不低于件，产品乙不低于 250件；件； 3、现有钢材、现有钢材 3600吨必须用完。吨必须用完。 若实现值没有达到目标，则存在偏差，希望按目标先若实现值没有达到目标，则存在偏差，希望按目标先后尽可能使偏差最小。后尽

12、可能使偏差最小。 1 d2 d3 d）（44 dd1P偏差偏差2P3P目标目标2有两个要求，且具有相同的优先因子，因此需要确定权系有两个要求，且具有相同的优先因子，因此需要确定权系数。本题可用单件利润比作为权系数即数。本题可用单件利润比作为权系数即 70 :120，化简为，化简为7:12。223 712Pdd （）)4 . 3 . 2 . 1(0, 030001032000543600492502005000012070)()127(min212121442133222112144332211j d dxx x x x x ddx x ddx dd x ddxxddPddPdPZjj1，目标规

13、划模型为：目标规划模型为：例：例：某厂生产某厂生产、两种产两种产品，有关数据如表所示。试品，有关数据如表所示。试求获利最大的生产方案。求获利最大的生产方案。限量限量原材料原材料2111设备设备(台时台时)1210单件利润单件利润810 要求考虑：要求考虑： 1、产品、产品的产量不低于产品的产量不低于产品的产量；的产量； 2、充分利用设备有效台时，不加班；、充分利用设备有效台时，不加班； 3、利润不小于、利润不小于 56 元。元。设：设：I、II产品产量产品产量 分别为分别为x1 ，x2 0112112ddx x xx ）（121222 210 210 xxxxdd （ ）12123381056

14、81056xxxxdd （ ）11221 x x11dP)(222 ddP33dP目标规划模型：目标规划模型：)3 . 2 . 1(0, 0112561081020)(min21213321222111213322211j d dxx x xddxxddx x ddx x dPddPdPZjj，)2 .1(0.0)2 .1).()2 .1()(min1111Ll d dn)1.2(j xmi( bxaLl qddxcddPZlljnjijijnjllljkjKkLllkllklk目标规划模型的一般形式目标规划模型的一般形式目标规划建模步骤目标规划建模步骤 2 2、根据要研究的问题所提出的各目标

15、与条件，确定、根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；目标值，列出目标约束与绝对约束； klkl和和 5 5、对同一优先等级中的各偏差变量，若需要可按其、对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系数重要程度的不同，赋予相应的权系数 。 4 4、给各目标赋予相应的优先因子、给各目标赋予相应的优先因子 P Pk k（k=1.2Kk=1.2K）。）。 3 3、可根据决策者的需要，将某些或全部绝对约束、可根据决策者的需要，将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差转化为目标约束。这时只需要给绝对约束加上负偏差变量和

16、减去正偏差变量即可。变量和减去正偏差变量即可。个子目标优先权个目标中第分别为第、其中，lkklkl 1 1、假设决策变量；、假设决策变量； 6 6、根据决策者的要求，按下列情况之一构造一个由、根据决策者的要求，按下列情况之一构造一个由优先因子和权系数相对应的偏差变量组成的、要求优先因子和权系数相对应的偏差变量组成的、要求实现极小化的目标函数，即达成函数。实现极小化的目标函数，即达成函数。llddldld. .恰好达到目标值，取恰好达到目标值，取 。. .不希望低于目标值，取不希望低于目标值，取 。. .不希望超过目标值，取不希望超过目标值，取 。 图解法同样适用两个变量的目标规划问题，但其操图

17、解法同样适用两个变量的目标规划问题，但其操作简单，原理一目了然。同时，也有助于理解一般目作简单，原理一目了然。同时，也有助于理解一般目标规划的求解原理和过程。标规划的求解原理和过程。 图解法解题步骤如下：图解法解题步骤如下： 1、确定各约束条件的可行域，即将所有约束条件、确定各约束条件的可行域，即将所有约束条件（包括目标约束和绝对约束，暂不考虑正负偏差变量）（包括目标约束和绝对约束，暂不考虑正负偏差变量）在坐标平面上表示出来；在坐标平面上表示出来； 2、在目标约束所代表的边界线上，用箭头标出正、在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向；负偏差变量值增大的方向；目标规划的

18、图解法目标规划的图解法 3、求满足最高优先等级目标的解；、求满足最高优先等级目标的解； 4、转到下一个优先等级的目标，再不破坏所有较高、转到下一个优先等级的目标，再不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解；优先等级目标的前提下，求出该优先等级目标的解； 5、重复、重复4，直到所有优先等级的目标都已审查完毕，直到所有优先等级的目标都已审查完毕为止；为止； 6、确定最优解或满意解。、确定最优解或满意解。例：用图解法求解目标规划问题例：用图解法求解目标规划问题)2 . 1(0, 08 2 102 5 .621210)(min21212221112122111lddxxxddxxdd

19、xxdPddPZll01 2 3 4 5 6 7 8 1 2 3 4 5 6 x2 x11d1d2d2dBC B (0.6250 , 4.6875) C (0 , 5.2083) ， B、C 线段上线段上的所有点均是该问题的解（无穷多最优解）。的所有点均是该问题的解（无穷多最优解）。)2 . 1(0, 08 2 102 5 .621210)(min21212221112122111lddxxxddxxddxxdPddPZll )3 . 2 . 1(0., 0112561081020)(min21213321222111213322211jddxxxddxxddxxddxxdPddPdPZjj

20、练习：用图解法求解下列目标规划问题练习：用图解法求解下列目标规划问题1d1d3d3d2d2d结论：有无穷多最优解。结论：有无穷多最优解。C（2，4）D（10/3，10/3） )3 . 2 . 1(0., 0112561081020)(min21213321222111213322211jddxxxddxxddxxddxxdPddPdPZjj CD 例：已知一个生产计划的线性规划模型为例：已知一个生产计划的线性规划模型为 01006014021230max21212121xxxxxxxZ)( )( )( 丙丙资资源源乙乙资资源源甲甲资资源源 其中目标函数为总利润，其中目标函数为总利润，x1,x2

21、 为产品为产品A、B产量。现产量。现有下列目标：有下列目标： 1、要求总利润必须超过、要求总利润必须超过 2500 元；元； 2、考虑产品受市场影响，为避免积压，、考虑产品受市场影响，为避免积压，A、B的生产生产量不超过量不超过 60 件和件和 100 件；件； 3、由于甲资源供应比较紧张，不要超过现有量、由于甲资源供应比较紧张，不要超过现有量140。试建立目标规划模型，并用单纯形法求解。试建立目标规划模型，并用单纯形法求解。)4 . 3 . 2 . 1(0, 0100601402250012305 . 2min214423312221112123423211l ddxdd x dd x dd

22、 x x ddxxdPdPdPdPZll)5 . 2(432ddPP1P3P2目标规划的单纯形法目标规划的单纯形法Cj00P100P302.5P20P2CBXBbx1x2P1250030121100000001402100110000060100000110001000100000011kjP1 -2500301201000000P2 000000002.501P3 000000100001d1d2d2d3d3d4d4d1d2d3d4d= min2500/30,140/2,60/1=60 ,故故 为换出变量。为换出变量。3d目标函数系数和检验数竖着排列目标函数系数和检验数竖着排列 = 2.5P

23、2-（0*P1+0*0-1*0+0*0）= 2.5P2 , 将2.5填填P2行。行。3dCj 00P100P302.5P20P2CBXBbx1x2P1700012110030300002001001122000 x160100000110001000100000011kjP1 7000120100303000P2 000000002.501P3 000000100001d1d2d2d3d3d4d4d1d2d4d= min700/30,20/2, =10 ,故故 为换出变量。为换出变量。2d = 2.5P2-（30P1+2*0-1*0+0*0）= 2.5P2-30P13dCj 00P100P30

24、2.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 = 0-（-15P1+2.5P2/2+1/2*0+0*0）= 15P1-2.5P2/22dCj 00P100P302.5P20P2CBXBbx1x2P380/3

25、0-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 ,故故 为换出变量。为换出变量。2d3d3dCj 00P100P302.5P20P2CBXBbx1x2P3115/3001/12-1/12-11-1/21/2000 x2175/3

26、011/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表中表中 P3 行行有负检验数，说明有负检验数，说明P3 级目标没有实现，但已无法改进，级目标没有实现，但已无法改进，得到满意解得到满意解 x1 60， x2 175/3， 115/3， 125/3。4d2d234232115 . 2mindPdPdPdPZ 结果分析：计算结果表明，工厂应生产结果分

27、析：计算结果表明，工厂应生产A产品产品60件，件，B产品产品175/3件，件，2500元的利润目标刚好达到。元的利润目标刚好达到。 125/3，表明产，表明产品品B B比最高限额少比最高限额少125/3件，满足要求。件，满足要求。 115/3 表明甲资源表明甲资源超过库存超过库存115/3公斤，该目标没有达到。公斤，该目标没有达到。 即甲资源多即甲资源多消耗消耗115/3公斤，刚好公斤，刚好实现实现25002500元的利润目标。元的利润目标。而按现有消耗水平和资源库存量，无法而按现有消耗水平和资源库存量，无法实现利润目标。实现利润目标。 可考虑如下措施：降低可考虑如下措施：降低A、B产品对甲资

28、源的消耗量，以满产品对甲资源的消耗量，以满足现有甲资源库存量的目标；或改变足现有甲资源库存量的目标；或改变P3级目标值，增加甲资源级目标值，增加甲资源115/3115/3公斤。公斤。 若很难实现上述措施，则需改变现有目标的优先等级，以若很难实现上述措施，则需改变现有目标的优先等级，以取得可行的满意解果。取得可行的满意解果。4d2d1、要求总利润必须超过、要求总利润必须超过 2500 元；元；2、考虑产品受市场影响，为避免积压，、考虑产品受市场影响，为避免积压，A、B的生产量不生产量不超过超过 60 件和件和 100 件；件；3、由于甲资源供应比较紧张，不要超过现有量、由于甲资源供应比较紧张，不

29、要超过现有量140。234232115 . 2dPdPdPdP 1 1、建立初始单纯形表。、建立初始单纯形表。 一般假定初始解在原点，即以约束条件中的所有负一般假定初始解在原点，即以约束条件中的所有负偏差变量或松弛变量为初始基变量，按目标优先等级从偏差变量或松弛变量为初始基变量，按目标优先等级从左至右分别计算出各列的检验数，填入表的下半部左至右分别计算出各列的检验数，填入表的下半部 。 2 2、检验是否为满意解。判别准则如下：、检验是否为满意解。判别准则如下： . .首先检查首先检查b b列中的列中的k (k=1.2K)是否全部为零？是否全部为零？如果全部为零，则表示目标均已全部达到，获得满意

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

31、验数的同列上面（较高优这一行全部负检验数的同列上面（较高优先等级）都有正检验数，说明目标虽没达到，但已不先等级）都有正检验数，说明目标虽没达到，但已不能改进，故得满意解，转到第能改进，故得满意解，转到第6 6步。步。 3 3、确定进基变量。、确定进基变量。 在在Pk行行，从那些上面没有正检验数的负检验数中，从那些上面没有正检验数的负检验数中，选绝对值最大者，对应的变量选绝对值最大者，对应的变量xs就是进基变量。若就是进基变量。若Pk行行中有几个相同的绝对值最大者，则依次比较它们各列中有几个相同的绝对值最大者，则依次比较它们各列下部的检验数，取其绝对值最大的负检验数的所在列下部的检验数，取其绝对

32、值最大的负检验数的所在列的的xs为进基变量。假如仍无法确定，则选最左边的变量为进基变量。假如仍无法确定，则选最左边的变量（变量下标小者）为进基变量。（变量下标小者）为进基变量。 4 4、确定出基变量、确定出基变量 其方法同线性规划，即依据最小比值法则其方法同线性规划，即依据最小比值法则故确定故确定xr为出基变量，为出基变量，e ersrs为主元素。若有几个相同的为主元素。若有几个相同的行可供选择时，选最上面那一行所对应得变量为行可供选择时，选最上面那一行所对应得变量为xr 。rsorisissiebeeb0/min 5 5、旋转变换（变量迭代）。、旋转变换（变量迭代）。 以主元素进行变换，得到

33、新的单纯形表，获得一组新以主元素进行变换，得到新的单纯形表，获得一组新解，返回到第解，返回到第2 2步。步。 6 6、对求得的解进行分析、对求得的解进行分析 若计算结果满意，停止运算；若不满意，需修改模若计算结果满意，停止运算；若不满意，需修改模型，即调整目标优先等级和权系数，或者改变目标值，型，即调整目标优先等级和权系数，或者改变目标值，重新进行第重新进行第1 1步。步。)3 . 2 . 1( 0 ., 011 256108102 0 )(min21213321222111213322211jddxxxddxxddxxddxxdPddPdPZjj练习：练习：用单纯形法求解下列目标规划问题用单

34、纯形法求解下列目标规划问题Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 00111100000P210120011000 P3 5681000001100 x3 11210000001kjP1 0000100000P2 10120002000P3 5681000000101d1d2d2d3d3d1d2d3d= min,10/2,56/10,11/1= 5,故故 为换出变量。为换出变量。2dCj 000P1 P2 P2P3 00CBXBbx1x2 x3 023/20111/2-1/20000 x251/21001/2-1/2000 P3 63000-551100 x3 63/2000-1/21/2001kjP1 0000100000P2 0000011000P3 630005-50101d1d2d2d3d3d1d3d= min4/3,10,6/3,12/3= 2,故故 为换出变量。为换出变量。3dCj 000P1 P2 P2P3 00CBXBbx1x2 x3 0200113-3-1