运筹目标规划素材.pptx

2024/4/3 周三1运筹学运筹学OPERATIONS RESEARCH2024/4/3 周三2第五章第五章 目标规划目标规划n目标规划的数学模型目标规划的数学模型 n目标规划的图解法目标规划的图解法n目标规划的单纯形解法目标规划的单纯形解法n目标规划的层次算法目标规划的层次算法n目标规划的应用目标规划的应用2024/4/3 周三31 1 目标规划的提出与数学模型目标规划的提出与数学模型 1 1.1.1 引例引例例例1 1 生产计划问题生产计划问题 能力能力 设备设备A 2 2 12 设备设备B 4 0 16 设备设备C 0 5 15 利润利润 2 3，各生产多少各生产多少,可获最大利润可获最大利润?2024/4/3 周三4解解:设产品设产品,产量分别为变量产量分别为变量最优解最优解：这里的目标只有一个！这里的目标只有一个！2024/4/3 周三5有时目标不只一个，例如考虑下列要求：有时目标不只一个，例如考虑下列要求：1 1、力求利润指标不低于、力求利润指标不低于1515元；元；2 2、两种产品的产量保持两种产品的产量保持1 1：2 2；3 3、A A为贵重设备，严格禁止超时使用；为贵重设备，严格禁止超时使用；4 4、设备、设备C C可适当加班，但要控制；可适当加班，但要控制；5 5、设备、设备B B既要充分利用，又要尽量不加班，在重要既要充分利用，又要尽量不加班，在重要 性上，设备性上，设备B B是设备是设备C C的的3 3倍。倍。要解决这样的问题，将上述的要求都加以考虑，要解决这样的问题，将上述的要求都加以考虑，就要用目标规划的方法解决。就要用目标规划的方法解决。2024/4/3 周三6n目标规划是在线性规划的基础上，为适应企业经目标规划是在线性规划的基础上，为适应企业经 营管理中多目标决策的需要而逐步发展起来的。营管理中多目标决策的需要而逐步发展起来的。目标规划是一种数学方法。目标规划是一种数学方法。n基本含义：在一定约束条件下，要求多个目标达基本含义：在一定约束条件下，要求多个目标达 到或尽可能接近于给定的对应目标值。到或尽可能接近于给定的对应目标值。n特点：既保持了线性规划易于计算的特点，又克特点：既保持了线性规划易于计算的特点，又克 服了线性规划只能解决单一目标优化问题的局限服了线性规划只能解决单一目标优化问题的局限 性。性。2024/4/3 周三7目标规划产生与发展目标规划产生与发展n目标规划的有关概念和数学模型是在目标规划的有关概念和数学模型是在19611961年由美年由美国学者查恩斯国学者查恩斯(A.Charnes)A.Charnes)和库伯和库伯(W.W.Cooper)W.W.Cooper)首首次在管理模型及线性规划的工业应用一书中次在管理模型及线性规划的工业应用一书中提出。当时是作为解一个没有可行解的线性规划提出。当时是作为解一个没有可行解的线性规划而引入的一种方法。这种方法把规划问题表达为而引入的一种方法。这种方法把规划问题表达为尽可能地接近预期的目标。尽可能地接近预期的目标。n19651965年，尤吉年，尤吉艾吉里艾吉里(Yuji Ijiri)Yuji Ijiri)在处理多在处理多目标问题，分析各类目标的重要性时，引入了赋目标问题，分析各类目标的重要性时，引入了赋予各目标一个优先因子及加权系数的概念；并进予各目标一个优先因子及加权系数的概念；并进一步完善了目标规划的数学模型。一步完善了目标规划的数学模型。n表达和求解目标规划问题的方法是由杰斯基莱恩表达和求解目标规划问题的方法是由杰斯基莱恩(Jashekilaineu)Jashekilaineu)和桑和桑李李(SangSangLi)Li)给出并加给出并加以改进的以改进的。2024/4/3 周三81 1.2.2 目标规划的有关概念目标规划的有关概念1 1、正、负偏差变量、正、负偏差变量 ：等是决策变量；等是决策变量；是正偏差变量，表决策值超过目标值的部分；是正偏差变量，表决策值超过目标值的部分；是负偏差变量，表决策值未达目标值的部分。是负偏差变量，表决策值未达目标值的部分。且有且有 。2 2、绝对约束和目标约束、绝对约束和目标约束 ：绝对约束绝对约束：必须满足的等式约束或不等式约束。：必须满足的等式约束或不等式约束。如：如：A A设备严格禁止超时使用，则设备严格禁止超时使用，则 2024/4/3 周三9目标约束：目标约束：对于不严格限定的约束，在达到此目标对于不严格限定的约束，在达到此目标时允许发生正或负的偏差，可在这些约束中加入正时允许发生正或负的偏差，可在这些约束中加入正负偏差变量，成为目标约束。负偏差变量，成为目标约束。如如：（1 1）“、两种产品的产量保持两种产品的产量保持1 1：2”2”可表示为可表示为当允许此比例当允许此比例 时，即时，即 ，则引入负，则引入负偏差偏差 ，则该条件可表示为：，则该条件可表示为：类似地有类似地有 ，表示允许此比例，表示允许此比例 。表示表示“力求力求、两种产品两种产品 的产量比例不的产量比例不 ”2024/4/3 周三10（2 2）目标函数也可转化为目标约束：）目标函数也可转化为目标约束：如：如：“力求利润指标不低于力求利润指标不低于1515元元”可表示为可表示为（3 3）“设备设备C C可适当加班，但要控制可适当加班，但要控制”可表示为可表示为（4 4）“设备设备B B既要充分利用，又要尽量不加班既要充分利用，又要尽量不加班”可可 表示为表示为2024/4/3 周三113 3、目标的优先级和权系数、目标的优先级和权系数 不同的目标重要程度不同，不同的目标重要程度不同，优先级优先级不同；同一层次不同；同一层次优先级的不同目标，重要程度不同，优先级的不同目标，重要程度不同，权重权重不同不同优先级因子优先级因子：，且，且权重系数权重系数：，数值的大小决定目标的重要数值的大小决定目标的重要 程度。程度。假设：第一优先级：利润不低于假设：第一优先级：利润不低于1515元；元；第二优先级：第二优先级：、产品的数量尽量保持产品的数量尽量保持1:21:2；第三优先级：第三优先级：C C、B B的工作时间控制，且的工作时间控制，且B B的重的重 要性是要性是C C的的3 3倍。倍。4 4、目标函数：、目标函数：目标函数是要尽量缩小偏离目标值目标函数是要尽量缩小偏离目标值2024/4/3 周三12于是按照上例中的有关要求，该目标规划的于是按照上例中的有关要求，该目标规划的目标函数目标函数约约束束条条件件：2024/4/3 周三13目标规划特点：目标规划特点：可以同时考虑多个目标；可以同时考虑多个目标；可以区分不同目标的优先程度及重要程度；可以区分不同目标的优先程度及重要程度；更加切合实际，更加灵活更加切合实际，更加灵活目标规划中的目标规划中的优先级及权重系数的确定往往需要靠优先级及权重系数的确定往往需要靠人的主观判断，是定性的，常常是模糊的，不是一人的主观判断，是定性的，常常是模糊的，不是一个确定的数值，但现在也有很多将其定量化的方个确定的数值，但现在也有很多将其定量化的方法，如层次分析法等这是处理目标规划时的一个难法，如层次分析法等这是处理目标规划时的一个难点。点。2024/4/3 周三14一般的目标规划数学模型一般的目标规划数学模型刚性约束刚性约束柔性约束柔性约束2024/4/3 周三152 2 目标规划的图解分析法目标规划的图解分析法求解目标规划的思路：求解目标规划的思路：刚性约束必须严格满足；刚性约束必须严格满足；按优先级次序，从高层到低层逐层优化；按优先级次序，从高层到低层逐层优化；在不增加高层偏差值的情况下，使本层的偏差达在不增加高层偏差值的情况下，使本层的偏差达到最小。到最小。只有两个决策变量的目标规划可用图解法分析。只有两个决策变量的目标规划可用图解法分析。以上例为例，图解分析如下。以上例为例，图解分析如下。2024/4/3 周三16满意解满意解 F2024/4/3 周三173 3 目标规划的单纯形解法目标规划的单纯形解法单纯形法求解目标规划的思路：单纯形法求解目标规划的思路：1.1.求解步骤与一般线性规划问题的单纯形法基本相同；求解步骤与一般线性规划问题的单纯形法基本相同；2.2.根据目标函数中的优先级次序，从高层到低层逐层优根据目标函数中的优先级次序，从高层到低层逐层优 化；化；3.3.单纯形表中，检验数按优先级次序分行表示。单纯形表中，检验数按优先级次序分行表示。例：例：2024/4/3 周三1800P100P1P20CBXBbx1X2d1-d1+d2-d2+d3-d3+P1d1-10101-10d2-40211-1P2d3-100 321-1P1-111P2-3-21第一步：第一步：列初始单纯形表列初始单纯形表2024/4/3 周三19第二步：第二步：确定进基变量。确定进基变量。按照优先级次序，检查按照优先级次序，检查P P1 1，P P2 2，,P,Pk k行检验数是否行检验数是否仍有负值（仍有负值（00）若有，找优先级最高一行的负值最）若有，找优先级最高一行的负值最小检验数对应变量作为进基变量。此例中选小检验数对应变量作为进基变量。此例中选x x1 1第三步：第三步：确定出基变量。确定出基变量。按照最小比值规则确定出基变量，此例中选按照最小比值规则确定出基变量，此例中选d d1 1-第四步：第四步：迭代运算，得到新的基可行解，判断是否迭代运算，得到新的基可行解，判断是否最优。最优。本例中，本例中，P P2 2行仍有负检验数，转到第二步。行仍有负检验数，转到第二步。2024/4/3 周三2000P100P1P20CBXBbx1X2d1-d1+d2-d2+d3-d3+0 x110101-10d2-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/212024/4/3 周三2100P100P1P20CBXBbx1X2d1-d1+d2-d2+d3-d3+0 x110101-1 000X22001-221-1P2d3-30001-1-221-1P111P2-112-21注意：注意：此时，此时，P P2 2行仍有负检验数，要选行仍有负检验数，要选X X2 2进基，进基，因为因为d d2 2+的检验数是的检验数是 。此时，此时，已达最优。已达最优。2024/4/3 周三22说明：说明：1 1、进行优化是按照优先级进行的，当高一级的目进行优化是按照优先级进行的，当高一级的目标行的检验数全部非负时，可进行下一级的优化；标行的检验数全部非负时，可进行下一级的优化；2 2、判别迭代终止的准则：、判别迭代终止的准则：（1 1）所有级别）所有级别 的检验数行均非负，的检验数行均非负，迭代终止；迭代终止；（2 2）若）若 行检验数均非负，而行检验数均非负，而 行有负检验数，但这些负检验数对应的上面行中有行有负检验数，但这些负检验数对应的上面行中有正检验数，迭代终止。正检验数，迭代终止。2024/4/3 周三234 4 目标规划的层次算法目标规划的层次算法（思想同前）（思想同前）第一步：第一步：先对目标函数中的先对目标函数中的 层次进行优化。层次进行优化。建立第一层次的线性规划模型，记为建立第一层次的线性规划模型，记为LPLP1.1.目标函数：目标函数：由第一优先级的偏差变量构成由第一优先级的偏差变量构成约束条件：约束条件：由原约束构成。由原约束构成。设第一级优化的最优目标值是设第一级优化的最优目标值是2024/4/3 周三24第二步：第二步：对目标函数中的对目标函数中的 层次进行优化。层次进行优化。建立第二层次的线性规划模型，记为建立第二层次的线性规划模型，记为LPLP2.2.目标函数：目标函数：由第二优先级的偏差变量构成由第二优先级的偏差变量构成约束条件：约束条件：在原约束基础上增加新约束：在原约束基础上增加新约束：设第二级优化的最优目标值是设第二级优化的最优目标值是 。以此类推。以此类推。2024/4/3 周三255 5 目标规划应用举例目标规划应用举例例例1 1：某电子厂生产录音机和电视机两种产品，分别某电子厂生产录音机和电视机两种产品，分别经由甲、乙两个车间生产。经由甲、乙两个车间生产。已知除外构件外，已知除外构件外，生产一台录音机需甲车间加工生产一台录音机需甲车间加工2h2h，乙车间装配，乙车间装配1h1h；生产一台电视机需甲车间加工生产一台电视机需甲车间加工1h1h，乙车间装配，乙车间装配3h3h；检验销售环节：检验销售环节：一台录音机检验销售费用一台录音机检验销售费用5050元；一台电视机检验销元；一台电视机检验销售费用售费用3030元；元；2024/4/3 周三26工时及管理费用：工时及管理费用：甲车间每月可用生产工时甲车间每月可用生产工时120h120h，车间管理费用，车间管理费用8080元元/h;/h;乙车间每月可用生产工时乙车间每月可用生产工时150h150h，车间管理费用，车间管理费用2020元元/h;/h;利润及销量：利润及销量：每台录音机利润每台录音机利润100100元，平均每月可销售元，平均每月可销售5050台；台；每台电视机利润每台电视机利润7575元，平均每月可销售元，平均每月可销售8080台；台；月度计划的目标如下：月度计划的目标如下：2024/4/3 周三271 1、第一优先级：检验和销售费用每月不超过、第一优先级：检验和销售费用每月不超过46004600元；元；2 2、第二优先级：每月销售录音机不少于、第二优先级：每月销售录音机不少于5050台；台；3 3、第三优先级：两车间的工时得到充分利用（重要、第三优先级：两车间的工时得到充分利用（重要性权系数按每小时的管理费用比）；性权系数按每小时的管理费用比）；4 4、第四优先级：甲车间加班不超过、第四优先级：甲车间加班不超过2020小时；小时；5 5、第五优先级：每月销售电视机不少于、第五优先级：每月销售电视机不少于8080台；台；6 6、第六优先级：两车间的加班总时间要控制（权系、第六优先级：两车间的加班总时间要控制（权系数分配如数分配如3 3）试确定该厂为达到上述目标的最优月度生产计划。试确定该厂为达到上述目标的最优月度生产计划。2024/4/3 周三28解：解：假设每月生产录音机假设每月生产录音机 台，电视机台，电视机 台。台。1 1、两车间可用工时、两车间可用工时:2 2、检验和销售费用、检验和销售费用:3 3、每月销售量、每月销售量:4 4、加班限制、加班限制:于是模型如下于是模型如下 2024/4/3 周三29约束：约束：目标函数目标函数2024/4/3 周三30例例2 2：书书P143 P143 例例5 5解：解：设设 是是i i工厂调配给工厂调配给j j用户的产品数量。约束如用户的产品数量。约束如下下1 1、供应量约束、供应量约束:2 2、需求量约束、需求量约束:3 3、用户、用户1 1需要量中工厂需要量中工厂3 3的产品数量不少于的产品数量不少于100:100:2024/4/3 周三314 4、各用户满足率不低于、各用户满足率不低于80%80%：5 5、运费限制：、运费限制：6 6、道路通过限制：、道路通过限制：7 7、用户、用户1 1和和3 3的满足率保持平衡：的满足率保持平衡：2024/4/3 周三328 8、力求总运费减小：、力求总运费减小：目标函数：目标函数：2024/4/3 周三33例例3 3：某单位领导在考虑本单位职工的升级调资方案某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定：时，依次遵守以下规定：1 1、年工资总额不超过、年工资总额不超过120120万元；万元；2 2、每级的人数不超过定编规定的人数；、每级的人数不超过定编规定的人数；3 3、级的升级面尽可能达到现有人数的级的升级面尽可能达到现有人数的20%20%；4 4、级不足编制的人数可录用新职工，又级不足编制的人数可录用新职工，又级的职级的职工中有工中有10%10%要退休。要退休。有关资料汇总于下表，请为该单位领导制定一个满有关资料汇总于下表，请为该单位领导制定一个满意的方案。意的方案。2024/4/3 周三34等级等级工资额（元工资额（元/年）年）现有人数现有人数编制人数编制人数400001012300001215200001515合计合计3742解：解：设设 分别表示提升到分别表示提升到、级和录用到级和录用到 级的职工人数。级的职工人数。则模型如下：则模型如下：目标函数目标函数 各目标约束：各目标约束：2024/4/3 周三35（1 1）年工资总额不超过）年工资总额不超过120120万元；万元；（2 2）每级的人数不超过编制规定的人数；）每级的人数不超过编制规定的人数；（3 3）、级的升级面尽可能达到现有人数的级的升级面尽可能达到现有人数的20%20%；例例4 4：某农场有某农场有3 3万亩农田，欲种植玉米、大豆和小万亩农田，欲种植玉米、大豆和小麦。各种作物每亩需施化肥分别为麦。各种作物每亩需施化肥分别为0.12,0.20,0.150.12,0.20,0.15吨。预计秋后玉米每亩可收获吨。预计秋后玉米每亩可收获500500公斤，售价为公斤，售价为0.240.24元元/公斤；大豆每亩可收获公斤；大豆每亩可收获200200公斤，售价为公斤，售价为1.201.20元元/公斤；小麦每亩可收获公斤；小麦每亩可收获300300公斤，售价为公斤，售价为0.700.70元元/公公斤。斤。农场年初规划时需考虑以下几个方面：农场年初规划时需考虑以下几个方面：nP1P1：年终收益不低于：年终收益不低于350350万元；万元；nP2P2：总产量不低于：总产量不低于1.251.25万吨；万吨；nP3P3：小麦产量以：小麦产量以0.50.5万吨为宜；万吨为宜；nP4P4：大豆产量不少于：大豆产量不少于0.20.2万吨；万吨；nP5P5：玉米产量不超过：玉米产量不超过0.60.6万吨；万吨；nP6P6：农场现在能提供：农场现在能提供50005000吨化肥，若不够，可在市吨化肥，若不够，可在市场高价购买，但希望高价采购量愈少愈好。场高价购买，但希望高价采购量愈少愈好。试就该农场生产计划建立数学模型。试就该农场生产计划建立数学模型。人有了知识，就会具备各种分析能力，人有了知识，就会具备各种分析能力，明辨是非的能力。明辨是非的能力。所以我们要勤恳读书，广泛阅读，所以我们要勤恳读书，广泛阅读，古人说古人说“书中自有黄金屋。书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，给我们巨大的精神力量，鼓舞我们前进鼓舞我们前进。