1、2023-8-171运筹学运筹学OPERATIONS RESEARCH2023-8-172第五章第五章 目标规划目标规划n目标规划的数学模型目标规划的数学模型 n目标规划的图解法目标规划的图解法n目标规划的单纯形解法目标规划的单纯形解法n目标规划的层次算法目标规划的层次算法n目标规划的应用目标规划的应用2023-8-1731 1 目标规划的提出与数学模型目标规划的提出与数学模型 一、一、引例引例例例1、生产计划问题、生产计划问题 能力能力 设备设备A 2 2 12 设备设备B 4 0 16 设备设备C 0 5 15 利润利润 2 3，各生产多少各生产多少,可获最大利润可获最大利润?2023-8
2、-174 2x1+2x2 12 12 4x1 16 5x2 15 x1，x2 0max Z=2x1+3x2解解:设产品设产品,产量分别为变量产量分别为变量x x1 1 ，x x2 2最优解最优解：15,3,321zxx2023-8-175有时目标不只一个，例如考虑下列要求：有时目标不只一个，例如考虑下列要求：1 1、力求利润指标不低于、力求利润指标不低于1515元；元；2 2、两种产品的产量保持两种产品的产量保持1 1：2 2；3 3、A A为贵重设备，严格禁止超时使用；为贵重设备，严格禁止超时使用；4 4、设备、设备C C可适当加班，但要控制；可适当加班，但要控制；5 5、设备、设备B B既
3、要充分利用，又要尽量不加班，在重要性既要充分利用，又要尽量不加班，在重要性上，设备上，设备B B是设备是设备C C的的3 3倍。倍。要解决这样的问题，将上述的要求都加以考虑，就要解决这样的问题，将上述的要求都加以考虑，就要用目标规划的方法解决。要用目标规划的方法解决。2023-8-176n目标规划是在线性规划的基础上，为适应目标规划是在线性规划的基础上，为适应企业经营管理中多目标决策的需要而逐步企业经营管理中多目标决策的需要而逐步发展起来的。目标规划是一种数学方法。发展起来的。目标规划是一种数学方法。n基本含义：在一定约束条件下，要求多个基本含义：在一定约束条件下，要求多个目标达到或尽可能接近
4、于给定的对应目标目标达到或尽可能接近于给定的对应目标值。值。n特点：既保持了线性规划易于计算的特点，特点：既保持了线性规划易于计算的特点，又克服了线性规划只能解决单一目标优化又克服了线性规划只能解决单一目标优化问题的局限性。问题的局限性。2023-8-177目标规划产生与发展n目标规划的有关概念和数学模型是在目标规划的有关概念和数学模型是在19611961年由美国学者查年由美国学者查恩斯恩斯(A.CharnesA.Charnes)和库伯和库伯(W.W.CooperW.W.Cooper)首次在管理模型首次在管理模型及线性规划的工业应用一书中提出。当时是作为解一个及线性规划的工业应用一书中提出。当
5、时是作为解一个没有可行解的线性规划而引入的一种方法。这种方法把规没有可行解的线性规划而引入的一种方法。这种方法把规划问题表达为尽可能地接近预期的目标。划问题表达为尽可能地接近预期的目标。n19651965年，尤吉年，尤吉艾吉里艾吉里(Yuji Yuji IjiriIjiri)在处理多目标问题，在处理多目标问题，分析各类目标的重要性时，引入了赋予各目标一个优先因分析各类目标的重要性时，引入了赋予各目标一个优先因子及加权系数的概念；并进一步完善了目标规划的数学模子及加权系数的概念；并进一步完善了目标规划的数学模型。型。n表达和求解目标规划问题的方法是由杰斯基莱恩表达和求解目标规划问题的方法是由杰斯
6、基莱恩(JashekilaineuJashekilaineu)和桑和桑李李(SangSangLiLi)给出并加以改进的。给出并加以改进的。2023-8-178二、二、目标规划的有关概念目标规划的有关概念1 1、正、负偏差变量、正、负偏差变量 ：等是决策变量；等是决策变量；是正偏差变量，表决策值超过目标值的部分；是正偏差变量，表决策值超过目标值的部分；是负偏差变量，表决策值未达目标值的部分。是负偏差变量，表决策值未达目标值的部分。且有且有 。dd,21,xxdd0dd2 2、绝对约束和目标约束、绝对约束和目标约束 ：绝对约束绝对约束：必须满足的等式约束或不等式约束。：必须满足的等式约束或不等式约
7、束。如如A A设备严格禁止超时使用，则设备严格禁止超时使用，则 122221 xx2023-8-179目标约束：目标约束：对于不严格限定的约束，在达到此目标时允对于不严格限定的约束，在达到此目标时允许发生正或负的偏差，可在这些约束中加入正负偏差变许发生正或负的偏差，可在这些约束中加入正负偏差变量，成为目标约束。量，成为目标约束。如如：（1 1）“、两种产品的产量保持两种产品的产量保持1 1：2”2”可表示为可表示为当允许此比例当允许此比例 时，即时，即 ，则引入负偏差，则引入负偏差 则该条件可表示为：则该条件可表示为：类似地有类似地有 ，表示允许此比例，表示允许此比例 。表示表示“力求力求、两
8、种产品两种产品 的产量的产量比例不比例不 ”0221 xx2/1212xx d0221dxx0221dxx2/1 02min21ddxxd2/12023-8-1710（2 2）目标函数也可转化为目标约束：）目标函数也可转化为目标约束：如如：“力求利润指标不低于力求利润指标不低于1515元元”可表示为可表示为 1532min21ddxxd（3 3）“设备设备C C可适当加班，但要控制可适当加班，但要控制”可表示为可表示为 155min2ddxd（4 4）“设备设备B B既要充分利用，又要尽量不加班既要充分利用，又要尽量不加班”可表示可表示为为164min1ddxdd2023-8-17113 3、
9、目标的优先级和权系数、目标的优先级和权系数 不同的目标重要程度不同，不同的目标重要程度不同，优先级优先级不同；不同；同一层次优先级的不同目标，重要程度不同，同一层次优先级的不同目标，重要程度不同，权重权重不同不同优先级因子优先级因子：，且，且权重系数权重系数：，数值的大小决定目标的重要程度。，数值的大小决定目标的重要程度。,.,321PPP1kkPP,.,321假设假设 第一优先级：利润不低于第一优先级：利润不低于1515元；元；第二优先级：第二优先级：、产品的数量尽量保持产品的数量尽量保持1 1：2 2；第三优先级：第三优先级：C C、B B的工作时间控制，且的工作时间控制，且B B的重要性
10、是的重要性是C C的的3 3倍。倍。4 4、目标规划的目标函数、目标规划的目标函数 目标函数是要尽量缩小偏离目标值目标函数是要尽量缩小偏离目标值2023-8-1712于是按照上例中的有关要求，该目标规划的于是按照上例中的有关要求，该目标规划的目标函数目标函数构成：构成：4333322211)(3)(mindPddPddPdPz约束条件：约束条件：0,1551640215321222214423312221112121iiddxxddxddxddxxddxxxx2023-8-1713目标规划特点：目标规划特点：可以同时考虑多个目标；可以同时考虑多个目标；可以区分不同目标的优先程度及重要程度；可以
11、区分不同目标的优先程度及重要程度；更加切合实际，更加灵活更加切合实际，更加灵活目标规划中的目标规划中的优先级及权重系数的确定往往需要靠人的主优先级及权重系数的确定往往需要靠人的主观判断，是定性的，常常是模糊的，不是一个确定的数观判断，是定性的，常常是模糊的，不是一个确定的数值，但现在也有很多将其定量化的方法，如层次分析法等值，但现在也有很多将其定量化的方法，如层次分析法等这是处理目标规划时的一个难点。这是处理目标规划时的一个难点。2023-8-1714一般的一般的目标规划数学模型目标规划数学模型)(min11 lklKkLllklkddPzLjmiddxLlgddxcmibxallinjlll
12、jljnjijij,.1;,.,1,0,0,.2,1,.2,1,11刚性约束刚性约束柔性约束柔性约束2023-8-17155.2 5.2 目标规划的图解分析法目标规划的图解分析法求解目标规划的思路：求解目标规划的思路：刚性约束必须严格满足；刚性约束必须严格满足；按优先级次序，从高层到低层逐层优化；按优先级次序，从高层到低层逐层优化；在不增加高层偏差值的情况下，使本层的偏差达到最小。在不增加高层偏差值的情况下，使本层的偏差达到最小。只有两个决策变量的目标规划可用图解法分析。只有两个决策变量的目标规划可用图解法分析。以上例为例，图解分析如下。以上例为例，图解分析如下。2023-8-17161d1d
13、2d2d3d3d4d4d122221 xx153221 xx0221 xx1641x1552xO1x2x4333322211dP)dd(P3)dd(PdPzminFE)75.3,875.1(E)4,2(F25.029)(3433ddd满意解满意解2023-8-17175.3 5.3 目标规划的单纯形解法目标规划的单纯形解法单纯形法求解目标规划的思路：单纯形法求解目标规划的思路：求解步骤与一般线性规划问题的单纯形法基本相同；求解步骤与一般线性规划问题的单纯形法基本相同；根据目标函数中的优先级次序，从高层到低层逐层优化；根据目标函数中的优先级次序，从高层到低层逐层优化；单纯形表中，检验数按优先级次
14、序分行表示。单纯形表中，检验数按优先级次序分行表示。例：例：32211)(mindPddPz0,10023402102133212221111iiddxxddxxddxxddx2023-8-171800P100P1P20CBXBbx1X2d1-d1+d2-d2+d3-d3+P1d1-10101-10d2-40211-1P2d3-100 321-1P1-111P2-3-21第一步：第一步：列初始单纯形表列初始单纯形表j2023-8-1719第二步：第二步：确定进基变量。确定进基变量。按照优先级次序，检查按照优先级次序，检查P P1 1，P P2 2，,P Pk k行检验数是否仍有负值行检验数是否
15、仍有负值（00）若有，找优先级最高一行的负值最小检验数对应变量）若有，找优先级最高一行的负值最小检验数对应变量作为进基变量。此例中选作为进基变量。此例中选x1第三步：第三步：确定出基变量。确定出基变量。按照最小比值规则按照最小比值规则确定出基变量确定出基变量，此例中选此例中选d d1 1-第四步：第四步：迭代运算，得到新的基可行解，判断是否最优。迭代运算，得到新的基可行解，判断是否最优。本例中，本例中，P P2 2行仍有负检验数，转到第二步。行仍有负检验数，转到第二步。2023-8-172000P100P1P20CBXBbx1X2d1-d1+d2-d2+d3-d3+0 x110101-10d2
16、-2001-221-1P2d3-7002-331-1P111P2-23-3100P100P1P20CBXBbx1X2d1-d1+d2-d2+d3-d3+0 x12011/2001/2-1/20d1+1001/2-111/2-1/2P2d3-4001/200-3/23/21-1P111P2-1/23/2-3/21jj2023-8-172100P100P1P20CBXBbx1X2d1-d1+d2-d2+d3-d3+0 x110101-1 000X22001-221-1P2d3-30001-1-221-1P111P2-112-21注意：注意：此时，此时，P P2 2行仍有负检验数，要选行仍有负检验数
17、，要选X X2 2进基，因为进基，因为d d2 2+的的检验数是检验数是 。02321pp此时，此时，已达最优。已达最优。2023-8-1722说明：说明：1 1、进行优化是按照优先级进行的，当高一级的目标行的检进行优化是按照优先级进行的，当高一级的目标行的检验数全部非负时，可进行下一级的优化；验数全部非负时，可进行下一级的优化；2 2、判别迭代终止的准则：、判别迭代终止的准则：（1 1）所有级别）所有级别 的检验数行均非负，迭的检验数行均非负，迭代终止；代终止；（2 2）若）若 行检验数均非负，而行检验数均非负，而 行有行有负检验数，但这些负检验数对应的上面行中有正检验数，负检验数，但这些负
18、检验数对应的上面行中有正检验数，迭代终止。迭代终止。iPPP,.,211iPkPPP,.,212023-8-17235.4 5.4 目标规划的层次算法目标规划的层次算法（思想同前）（思想同前）第一步：第一步：先对目标函数中的先对目标函数中的 层次进行优化。层次进行优化。建立第一层次的线性规划模型，记为建立第一层次的线性规划模型，记为LPLP1.1.目标函数：目标函数：由第一优先级的偏差变量构成由第一优先级的偏差变量构成约束条件：约束条件：由原约束构成。由原约束构成。设第一级优化的最优目标值是设第一级优化的最优目标值是1PLlllllddz1111)(min1z2023-8-1724第二步：第二
19、步：对目标函数中的对目标函数中的 层次进行优化。层次进行优化。建立第二层次的线性规划模型，记为建立第二层次的线性规划模型，记为LPLP2.2.目标函数：目标函数：由第二优先级的偏差变量构成由第二优先级的偏差变量构成约束条件：约束条件：在在原约束原约束基础上增加基础上增加新约束新约束：设第二级优化的最优目标值是设第二级优化的最优目标值是 。以此类推。以此类推。2PLlllllddz1222)(min1111)(zddLlllll2z2023-8-17255.5 5.5 目标规划应用举例目标规划应用举例例例1 1：某电子厂生产录音机和电视机两种产品，分别经由甲、乙两个车间某电子厂生产录音机和电视机
20、两种产品，分别经由甲、乙两个车间生产。生产。已知除外构件外，已知除外构件外，生产一台录音机需甲车间加工生产一台录音机需甲车间加工2h2h，以车间装配，以车间装配1h1h；生产一台电视机需甲车间加工生产一台电视机需甲车间加工1h1h，以车间装配，以车间装配3h3h；检验销售环节：检验销售环节：一台录音机检验销售费用一台录音机检验销售费用5050元；元；一台电视机检验销售费用一台电视机检验销售费用3030元；元；工时及管理费用：工时及管理费用：甲车间每月可用生产工时甲车间每月可用生产工时120h120h，车间管理费用，车间管理费用8080元元/h;/h;乙车间每月可用生产工时乙车间每月可用生产工时
21、150h150h，车间管理费用，车间管理费用2020元元/h;/h;利润及销量：利润及销量：每台录音机利润每台录音机利润100100元，平均每月可销售元，平均每月可销售5050台；台；每台电视机利润每台电视机利润7575元，平均每月可销售元，平均每月可销售8080台；台；2023-8-1726月度计划的目标如下：月度计划的目标如下：1 1、第一优先级：检验和销售费用每月不超过、第一优先级：检验和销售费用每月不超过46004600元；元；2 2、第二优先级：每月销售录音机不少于、第二优先级：每月销售录音机不少于5050台；台；3 3、第三优先级：两车间的工时得到充分利用（重要性权系数、第三优先级
22、：两车间的工时得到充分利用（重要性权系数按每小时的管理费用比）；按每小时的管理费用比）；4 4、第四优先级：甲车间加班不超过、第四优先级：甲车间加班不超过2020小时；小时；5 5、第五优先级：每月销售电视机不少于、第五优先级：每月销售电视机不少于8080台；台；6 6、第六优先级：两车间的加班总时间要控制（权系数分配如、第六优先级：两车间的加班总时间要控制（权系数分配如3 3）试确定该厂为达到上述目标的最优月度生产计划。试确定该厂为达到上述目标的最优月度生产计划。2023-8-17271x2x解：解：假设每月生产录音机假设每月生产录音机 台，电视机台，电视机 台。台。约束：约束：1 1、两车
23、间可用工时、两车间可用工时:1503120222211121ddxxddxx2 2、检验和销售费用检验和销售费用:460030503321ddxx3 3、每月销售量每月销售量:8050552441ddxddx4 4、加班限制加班限制:于是目标函数：于是目标函数：20661ddd)4()4(min21655642134231ddPdPdPddPdPdPz2023-8-1728约束：约束：1503120222211121ddxxddxx460030503321ddxx8050552441ddxddx10661ddd0,21iiddxx2023-8-1729例例2 2：书书P143 P143 例例5
24、 5解：解：设设 是是i i工厂调配给工厂调配给j j用户的产品数量。约束如下用户的产品数量。约束如下1 1、供应量约束、供应量约束:ijx400200300343332312423222114131211xxxxxxxxxxxx2 2、需求量约束、需求量约束:2504501002004342414333231323222121312111dxxxdxxxdxxxdxxx3 3、用户、用户1 1需要量中工厂需要量中工厂3 3的产品数量不少于的产品数量不少于100:100:1005531ddx2023-8-17304 4、各用户满足率不低于、各用户满足率不低于80%80%：20036080160
25、99342414883323137732221266312111ddxxxddxxxddxxxddxxx5 5、运费限制：、运费限制：324510103141ddxcijijij6 6、道路通过限制：、道路通过限制：01124dx7 7、用户、用户1 1和和3 3的满足率保持平衡：的满足率保持平衡：0)(450200)(1212332313312111ddxxxxxx2023-8-17318 8、力求总运费减小：、力求总运费减小：295013133141ddxcijijij目标函数：目标函数：13712126115104987635241)()(mindPddPdPdPddddPdPdPz20
26、23-8-1732例例3 3：某单位领导在考虑本单位职工的升级调资方案时，依次某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定：遵守以下规定：1 1、年工资总额不超过、年工资总额不超过120120万元；万元；2 2、每级的人数不超过定编规定的人数；、每级的人数不超过定编规定的人数；3 3、级的升级面尽可能达到现有人数的级的升级面尽可能达到现有人数的20%20%；4 4、级不足编制的人数可录用新职工，又级不足编制的人数可录用新职工，又级的职工中有级的职工中有 10%10%要退休。要退休。有关资料汇总于下表，请为该单位领导制定一个满意的方案。有关资料汇总于下表，请为该单位领导制定一个满
27、意的方案。等级工资额（元/年）现有人数编制人数400001012300001215200001515合计37422023-8-1733解：解：设设 分别表示提升到分别表示提升到、级和录用到级和录用到级的级的 职工人数。职工人数。确定优先级：确定优先级：321,xxx确定各目标约束：确定各目标约束：（1 1）年工资总额不超过）年工资总额不超过120120万元；万元；（2 2）每级的人数不超过编制规定的人数；）每级的人数不超过编制规定的人数；120)15(2)12(3)1.01010(41132211ddxxxxx121.01010221ddx15123321ddxx15154432ddxx2023-8-1734（3 3）、级的升级面尽可能达到现有人数的级的升级面尽可能达到现有人数的20%20%；0152.00122.0662551ddxddx目标函数：目标函数：)()(min653432211ddPdddPdPz
