大学精品课件：运筹学（四）.ppt

1、第四章第四章目目 标标 规规 划划（Goal Programming)主要内容：主要内容：第一节第一节 目标规划问题及其数学模型目标规划问题及其数学模型第二节第二节 目标规划的图解法目标规划的图解法第三节第三节 目标规划的单纯形法目标规划的单纯形法第四节第四节 目标规划的灵敏度分析目标规划的灵敏度分析第五节第五节 目标规划的应用举例目标规划的应用举例第一节第一节目标规划问题及其数学模型目标规划问题及其数学模型一、引例一、引例 例例1 1：某企业利用某种原材料和现有设备可生产甲、乙两种某企业利用某种原材料和现有设备可生产甲、乙两种产品，其中，甲、乙两种产品的单价分别为产品，其中，甲、乙两种产品的

2、单价分别为3535元和元和6060元；生元；生产单位甲、乙两种产品需要消耗的原材料分别为产单位甲、乙两种产品需要消耗的原材料分别为2 2个单位和个单位和3 3个单位，需要占用的设备分别为个单位，需要占用的设备分别为1 1台时和台时和2 2台时；原材料拥有台时；原材料拥有量为量为1616个单位；可利用的设备总台时为个单位；可利用的设备总台时为1010台时。台时。试问：若使得总产值最大，如何确定其生产方案？试问：若使得总产值最大，如何确定其生产方案？0,1021632212121xxxxxx216035maxxxZ元310Z4 ,2*2*1xx 在实际决策时，企业领导者必须考虑市场等一系列其在实际

3、决策时，企业领导者必须考虑市场等一系列其它条件，如：它条件，如：（1 1）根据市场信息，乙种产品的需求量有下降的趋势，因）根据市场信息，乙种产品的需求量有下降的趋势，因此乙种产品的产量不应大于甲种产品的产量；此乙种产品的产量不应大于甲种产品的产量；（2 2）超过计划供应的原材料，需用高价采购，这就会使生）超过计划供应的原材料，需用高价采购，这就会使生产成本增加产成本增加,须注意避免超标；须注意避免超标；（3 3）应尽可能地充分利用设备的有效台时，但不希望加班；）应尽可能地充分利用设备的有效台时，但不希望加班；（4 4）应尽可能达到并超过）应尽可能达到并超过260260元的计划产值指标。元的计划

4、产值指标。012 xx163221 xx10221 xx260603521xx这些目标可以表示为如下不等式（等式）：这些目标可以表示为如下不等式（等式）：这是一个多目标决策问题，可以通过建立目标规划模型来解决。这是一个多目标决策问题，可以通过建立目标规划模型来解决。二、目标规划问题的数学模型二、目标规划问题的数学模型（一）目标规划问题数学模型的相关概念（一）目标规划问题数学模型的相关概念 1优先因子和权系数优先因子和权系数 优先因子优先因子 是将决策目标按其重要程度排序并是将决策目标按其重要程度排序并表示出来。表示出来。P1P2 。权系数权系数 区别具有相同优先因子区别具有相同优先因子 的目标

5、的的目标的重要程度的差别，决策者可视具体情况而定。重要程度的差别，决策者可视具体情况而定。lPlP1lPLPlklP对于引例中的四个目标，决策人员经讨论得出各个目标主次对于引例中的四个目标，决策人员经讨论得出各个目标主次轻重的意见：轻重的意见：原材料的使用不得突破限额；原材料的使用不得突破限额；甲种产品的产量必须优先考虑甲种产品的产量必须优先考虑(P1)；设备台时问题其次考虑设备台时问题其次考虑(P2)；最后考虑产值指标最后考虑产值指标(P3)。163221 xx012 xx P1：10221 xx P2：260603521xx P3：2.目标值和偏差变量目标值和偏差变量目标值目标值：是指预先

6、给定的某个目标的一个期望值。是指预先给定的某个目标的一个期望值。实现值或决策值实现值或决策值：是指当决策变量是指当决策变量xj 选定以后，目标函数的选定以后，目标函数的对应值。对应值。偏差变量偏差变量（事先无法确定的未知数）：是指实现值和目标值（事先无法确定的未知数）：是指实现值和目标值之间的差异之间的差异,记为记为 d。正偏差变量：正偏差变量：表示实现值超过目标值的部分，记为表示实现值超过目标值的部分，记为 d。负偏差变量：负偏差变量：表示实现值未达到目标值的部分，记为表示实现值未达到目标值的部分，记为 d。规定规定d0,d0 当超额完成规定的指标则表示：当超额完成规定的指标则表示：d d0

7、,d d0 当未完成规定的指标则表示：当未完成规定的指标则表示：d d0,d d0 当恰好完成指标时则表示：当恰好完成指标时则表示：d d0,d d0 因此有因此有 d d d d 0 0。163221 xx)3,2,1(00,2606035102021332122211112kddxxddxxddxxddxxkk，对于引例，有：对于引例，有：3.绝对约束和目标约束绝对约束和目标约束绝对约束绝对约束：在约束条件中，必须绝对满足的约束条件称为：在约束条件中，必须绝对满足的约束条件称为绝对约束。绝对约束。目标约束目标约束：对于某些条件，我们提出其目标值，希望它们：对于某些条件，我们提出其目标值，希

8、望它们尽量满足这些目标值，但允许他们能够偏离这个目标值，尽量满足这些目标值，但允许他们能够偏离这个目标值，这样的约束称为目标约束这样的约束称为目标约束。163221 xx)3,2,1(00,2606035102021332122211112kddxxddxxddxxddxxkk，绝对约束绝对约束目标约束目标约束4.达成函数达成函数目标规划的目标函数称为达成函数，由目标规划的目标函数称为达成函数，由各目标约束的偏差各目标约束的偏差变量变量及及相应的优先因子和权系数相应的优先因子和权系数构成。构成。因为目标规划追求的是各目标尽量达到其目标值，也就是因为目标规划追求的是各目标尽量达到其目标值，也就是

9、期望有关偏差变量尽量小。具体而言，通常有三种形式：期望有关偏差变量尽量小。具体而言，通常有三种形式：minf(d+):表示希望某个目标不超过其期望值；表示希望某个目标不超过其期望值；minf(d-):表示希望某个目标不少于其期望值；表示希望某个目标不少于其期望值；minf(d+d-):表示希望某个目标刚好达到其期望值。表示希望某个目标刚好达到其期望值。对于引例，我们首先希望对于引例，我们首先希望x2要尽量小于要尽量小于x1，即希望，即希望d1+尽量小；又希望设备台时尽量用完且不加班，即希望尽量小；又希望设备台时尽量用完且不加班，即希望d2+d2-尽量小；还希望产值尽量超过目标值，即希尽量小；还

10、希望产值尽量超过目标值，即希望望d3-尽量小。再结合它们目标对应的优先因子，列出尽量小。再结合它们目标对应的优先因子，列出达成函数，为：达成函数，为：3322211)(mindPddPdPZ3322211)(mindPddPdPZ)3,2,1(00,2606035102016322133212221111221kddxxddxxddxxddxxxxkk，由此，我们可以得到引例的目标规划模型如下：由此，我们可以得到引例的目标规划模型如下：（二）目标规划问题数学模型的一般形式（二）目标规划问题数学模型的一般形式)2.1(0,n)1,2(j 0)2.1(),()2.1()(min1111Llddxm

11、ibxaKkgddxcddPZlljnjijijnjkkkjkjLlKkklkklkl三、目标规划与线性规划的比较三、目标规划与线性规划的比较 1、线性规划只讨论一个线性目标函数在一组线性约束、线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题；而目标规划是多个目标决策，可求条件下的极值问题；而目标规划是多个目标决策，可求得更切合实际的解。得更切合实际的解。2、线性规划中的约束条件是同等重要的，是硬约束；、线性规划中的约束条件是同等重要的，是硬约束；而目标规划中有轻重缓急和主次之分，即有优先权。而目标规划中有轻重缓急和主次之分，即有优先权。3、线性规划求最优解；目标规划是找到一个满意

12、解、线性规划求最优解；目标规划是找到一个满意解。第二节第二节目标规划的图解法目标规划的图解法 图解法同样适用两个变量的目标规划问题，图解法同样适用两个变量的目标规划问题，但其操作简单，原理一目了然。同时，也有助于但其操作简单，原理一目了然。同时，也有助于理解一般目标规划的求解原理和过程。理解一般目标规划的求解原理和过程。图解法解题步骤如下：图解法解题步骤如下：第第1 1步步：作出绝对约束及决策变量的约束（与一般线性规划：作出绝对约束及决策变量的约束（与一般线性规划作图法相同）。作图法相同）。第第2 2步步：令目标约束中的：令目标约束中的 ，作目标约束直线，标，作目标约束直线，标出达成函数中涉及

13、的偏差变量增大时对应的目标约束直线出达成函数中涉及的偏差变量增大时对应的目标约束直线的移动方向。的移动方向。第第3 3步步：按照优先因子从高到低的顺序，逐级考虑各个目标：按照优先因子从高到低的顺序，逐级考虑各个目标约束。对约束。对 级的各目标，确定最优解空间级的各目标，确定最优解空间 ，对下一个优，对下一个优先级别先级别 级各目标，确定它的最优解空间级各目标，确定它的最优解空间 ，但必须是，但必须是 （=1=1，2 2，3 3，L-1L-1）。）。在此过程中，若遇到在此过程中，若遇到 不为空，而不为空，而 为空，则该目标为空，则该目标规划的满意解在规划的满意解在 内，它（它们）能满足内，它（它

14、们）能满足P1P1，P2P2，级目标，不能但尽量满足级目标，不能但尽量满足 级目标；若能够求得最低优先级目标；若能够求得最低优先级级 对应的解空间不为空，则对应的解空间不为空，则 中的所有点均为该目标规中的所有点均为该目标规划的满意解，且能够满足所有目标要求。划的满意解，且能够满足所有目标要求。0kkddlPlR1lP1lR1lRlRllRmR1mRmRmP1mPLPLR)3.2.1(0,011 256108102 0 min2121332122211121332211jddxxxddxxddxxddxxdPdPdPZjj例例2：用图解法确定以下目标规划的满意解：用图解法确定以下目标规划的满意

15、解区域区域OAB区域区域OAC区域区域ACDE区域区域EFGox2x1ABCDEFGl1l2l3d1d2d3+-(0,5)(0,5.6)(2,4)5544332211mindPdPdPdPdPZ)5,4,3,2,1(00,43649561081020112215521442133212221112121kddxxddxxddxxddxxddxxddxxxxkk，EoFl3DCBl2+d1l1x1x2Ad2-d3+-d4d5Gl4l5例例3：用图解法确定以下目标规划的满意解：用图解法确定以下目标规划的满意解区域区域OAB区域区域OAC区域区域ACDE区域区域EFG点点G（满足前（满足前3级目标，

16、不满足第级目标，不满足第4级目标，但满足第级目标，但满足第5级目标）级目标）第三节第三节目标规划的单纯形法目标规划的单纯形法单纯形法的计算步骤：单纯形法的计算步骤：1 1、建立初始单纯形表；、建立初始单纯形表；2 2、检验是否为满意解；、检验是否为满意解；3 3、确定换入基变量；、确定换入基变量；4 4、确定换出基变量；、确定换出基变量；5 5、迭代，返回到第、迭代，返回到第2 2步；步；6 6、确定满意解并对解进行分析。、确定满意解并对解进行分析。例例4 4：用单纯形法求解例用单纯形法求解例2。)3,2,1(00,561081020112321332122211121321kddxxxddx

17、xddxxddxxxxxkk，解：解：引入松弛变量引入松弛变量x x3 3,将它们化为标准型：将它们化为标准型：=min11/1,10/2,56/10=5,故故 为换出变量。为换出变量。Cj0000P1P200P3CBXBbx1x2x30 x311211000000001-101-10000P210120001-100056810000001-1kjP1 000010000P2-1-20000100P3 0000000011d1d2d2d3d3d1d2d3d2d表表1：Cj0000P1P200P3CBXBbx1x2x30 x363/20100-1/21/200053/2001-11/2-1/2

18、000 x251/210001/2-1/2000630000-551-1kjP1 000010000P2 000001000P3 0000000011d1d2d2d3d3ddd得到满意解得到满意解x1=0,x2=5，满足所有约束。，满足所有约束。表表2：Cj0000P1P200P3CBXBbx1x2x30 x354/106/5010000-1/101/10056/109/5001-1001/10-1/100 x256/104/51000001/10-1/1006/53/50000-111/5-1/5kjP1 000010000P2 000001000P3 0000000011d1d2d2d3d

19、3dd2d的检验数为的检验数为0，把它作为换入变量。把，把它作为换入变量。把 作为换出变量。作为换出变量。3d2d得到另外一个满意解得到另外一个满意解x1=0,x2=5.6，满足所有约束。，满足所有约束。表表2中中，表表2中，中，x1的检验数为的检验数为0，把它作为换入变量。把，把它作为换入变量。把 作为换作为换出变量。出变量。3dCj0000P1P200P3CBXBbx1x2x30 x33001002-2-1/21/2020001-13-3-1/21/20 x24010004/3-4/3-1/61/60 x1210000-5/35/31/3-1/3kjP1 000010000P2 00000

20、1000P3 0000000011d1d2d2d3d3dd得到又一个满意解得到又一个满意解x1=2,x2=4，满足所有约束。，满足所有约束。所以，该问题有无穷多满意解，表示为：所以，该问题有无穷多满意解，表示为：)4,2()6.5,0()5,0(321*aaaX1 0,321321aaaaaa且其中，)46.55 ,2(3213aaaa例例5 5：5544332211mindPdPdPdPdPZ)5,4,3,2,1(00,4364956108102011232155214421332122211121321kddxxxddxxddxxddxxddxxddxxxxxkk，用单纯形法求解例用单纯形

21、法求解例3。解：引入松弛变量解：引入松弛变量x3，化为标准形式如下，化为标准形式如下：cj0000P1P200P3P40P50CBXBbx1x2x30 x3112110000000000001-101-100000000P210120001-1000000056810000001-10000P4369400000001-100P54110000000001-1cj-zjP10000100000000P2-1-200001000000P30000000010000P4-9-400000000100P5-1-100000000001d2d3d5d4d1d1d2d2d3d3d4d5d4d5dcj00

22、00P1P200P3P40P50CBXBbx1x2x30 x3300100-331/2-1/20000020001-13-3-1/2 1/200000200000-1/31/31/6-1/600-110 x1210000-5/35/31/3-1/30000P420000029/3-29/3-7/3 7/31-1000 x24010008/6-8/6-1/6 1/60000cj-zjP10000100000000P20000010000000P30000000010000P400000-29/3 29/37/3-7/30100P50000000000010d5d4d1d1d2d2d3d3d4d5

23、d4d5d经过若干步迭代，得到最终单纯形表：经过若干步迭代，得到最终单纯形表：得到唯一满意解：得到唯一满意解：X=(2,4)=(2,4)第四节第四节灵敏度分析灵敏度分析)4,3,2,1(0,02 4292 62)35(min21442332122211121144332211jddxddxddxxddxxddxxdPddPdPdPZjj例：求解如下目标规划问题例：求解如下目标规划问题当上述问题的目标函数变为当上述问题的目标函数变为 时，最优解是否改变？时，最优解是否改变？)4,3,2,1(0,02 4292 62)35(min21442332122211121144332211jddxddxd

24、dxxddxxddxxdPddPdPdPZjj144332211)3(mindPddPdPdPZ6221 xx22x4221 xx2x1xoDCAB9221 xxFGE1d2d4d3d考虑前两级目标，得到解空间考虑前两级目标，得到解空间ABCD;考虑第三级目标，首先考虑考虑第三级目标，首先考虑min ,得到解空间得到解空间ABEF;3d 然后考虑然后考虑min ,在在E点点得到满意解得到满意解;4d解解：（：（1）用图解法求解）用图解法求解Cj00P1P40P25P303P30CBXBbx1x2P16121-10000000912001-100005P341-200001-1003P32010

25、000001-1kjP1-1-201000000P2 0000010000P3-5700000503P400010000001d1d2d2d3d3d1d2d3d4d4d4d（2）用单纯形法求解）用单纯形法求解Cj00P1P40P25P303P30CBXBbx1x20 x113/210001/2-1/21/2-1/200P4300-111-100003P33/40000-1/41/41/4-1/41-10 x25/401001/4-1/4-1/41/400kjP1 0010000000P2 0000010000P300003/4-3/417/43/403P40010-1100001d1d2d2d

26、3d3d1d4d4d4dX=(13/2,5/4)E点点（3）用图解法求解新问题）用图解法求解新问题6221 xx22x4221 xx2x1xoDCAB9221 xxFGE1d2d4d3d考虑前两级目标，得到解空间考虑前两级目标，得到解空间ABCD;考虑第三级目标，首先考虑考虑第三级目标，首先考虑min ,得到解空间得到解空间CDGH;然后考虑然后考虑min ,在在G点点得到满意解得到满意解;)4,3,2,1(0,02 4292 62)3(min21442332122211121144332211jddxddxddxxddxxddxxdPddPdPdPZjj4dH3d（4）用灵敏度分析考察新问题

27、的最优解）用灵敏度分析考察新问题的最优解Cj00P1P40P2P303P30CBXBbx1x20 x113/210001/2-1/21/2-1/200P4300-111-100003P33/40000-1/41/41/4-1/41-10 x25/401001/4-1/4-1/41/400kjP1 0010000000P2 0000010000P300003/4-3/41/43/403P40010-1100001d1d2d2d3d3d1d4d4d4dX=(13/2,5/4)E点点与图解法矛盾！与图解法矛盾！注意：图解法在处理有权系数的问题时可能会出现错误注意：图解法在处理有权系数的问题时可能会出

28、现错误第五节第五节目标规划的应用举例目标规划的应用举例一、物资调运一、物资调运 某公司下属三个小型煤矿某公司下属三个小型煤矿A1，A2，A3，每天煤炭，每天煤炭的生产量分别为的生产量分别为12t，10t，10t，供应，供应B1，B2，B3，B4四个工厂，需求量分别为四个工厂，需求量分别为6t，8t，6t，10t。公司调运时依次考虑的目标优先级为：。公司调运时依次考虑的目标优先级为：P1：A1产地因库存限制，应尽量全部调出；产地因库存限制，应尽量全部调出；P2：因煤质要求，：因煤质要求，B4需求最好由需求最好由A3供应；供应；P3：满足各需求地需求；：满足各需求地需求；P4：调运总费用尽可能不超

29、过：调运总费用尽可能不超过82元；元；P5：A2至至B2的道路较差，运量尽量减少到最低点。的道路较差，运量尽量减少到最低点。从煤矿到各工厂调运的运价见下表，试建立该问题从煤矿到各工厂调运的运价见下表，试建立该问题的目标规划模型。的目标规划模型。工厂工厂 运价运价煤矿煤矿B1B2B3B4供应量（供应量（t）A1365212A2244110A3436310需求量（需求量（t）686108574654332211)(mindPdPddddPdPdPZ）（）；（）（7,6,5,4,3,2,10,4,3,2,1,3,2,10 0 4,3,2,1,3,2,182 10 6 8 6 10 12 10 10

30、12 8822314776644342414554333231344423222123341312111223411131211333231232221131211kddjixddxjiddxcddxxxxddxxxxddxxxxddxxxxddxddxxxxxxxxxxxxkkijijijij二、工作时间安排二、工作时间安排 某商店由经理、主任、销售员甲和乙以及某商店由经理、主任、销售员甲和乙以及1 1名兼职售货员。根据名兼职售货员。根据以往经验，各类人员每小时工作带来的销售额的分别是：经理：以往经验，各类人员每小时工作带来的销售额的分别是：经理：120120元；主任：元；主任：8080元；

31、销售员甲：元；销售员甲：4545元；销售员乙：元；销售员乙：2525元；兼元；兼职销售员：职销售员：1212元。该单位每投入元。该单位每投入100100元的广告费带来元的广告费带来240240元的销元的销售额。各类人员工作时间规定如下：经理、主任每月各售额。各类人员工作时间规定如下：经理、主任每月各200200小小时；销售员甲时；销售员甲172172小时；销售员乙小时；销售员乙160160小时；兼职销售员小时；兼职销售员100100小小时。主任和两位售货员可得相当于其销售额约时。主任和两位售货员可得相当于其销售额约5.5%5.5%的工资收入，的工资收入，根据以往经验，主任每月可得收入根据以往经

32、验，主任每月可得收入10501050元；售货员元；售货员430430元；销元；销售员乙为售员乙为260260元。加班限制：经理、主任每月不超过元。加班限制：经理、主任每月不超过2424小时；小时；售货员甲不超过售货员甲不超过5252小时；售货员乙不超过小时；售货员乙不超过4242小时；兼职售货员小时；兼职售货员不超过不超过3232小时。小时。试确定该商店各类人员每月的工作时间及广告费用的开支，试确定该商店各类人员每月的工作时间及广告费用的开支，以期保证正常的工作秩序和良好的经济效益。以期保证正常的工作秩序和良好的经济效益。决策的目标及优先等级如下：决策的目标及优先等级如下：P1P1：保证全体人

33、员正常工作时间得到充分的利用；：保证全体人员正常工作时间得到充分的利用；P2P2：销售额每月达到：销售额每月达到5555，000000元。元。P3P3：主任的每月工资不少于：主任的每月工资不少于10501050元；元；P4P4：各类人员每月的加班时间不超过规定限额；：各类人员每月的加班时间不超过规定限额；P5P5：每月的广告费不超过：每月的广告费不超过450450元；元；P6P6：售货员甲每月的工资收入不少于：售货员甲每月的工资收入不少于430430元，销售元，销售员乙每月的工资不少于员乙每月的工资不少于260260元。元。）（）；（15,2,10,6,5,4,3,2,1026025%5.54

34、3045%5.5450132202224224224105080%5.5550004.2825458012010016017220020015152141431313612125111141010399288177266654321555444333222111kddjxddxddxddxddxddxddxddxddxddxddxxxxxxddxddxddxddxddxkkj 解：设解：设x xi i（i=1,2,3,4,5i=1,2,3,4,5）依次表示经理、主任、售货员甲、售货员）依次表示经理、主任、售货员甲、售货员乙、兼职售货员每月的工作小时；乙、兼职售货员每月的工作小时；x x6 6表示每月投入的广告费用。表示每月投入的广告费用。minZ=)()()(151461351211109847362543211ddPdPdddddPdPdPdddddP作业：4.64.7