运筹08(第五章目标规划)

《运筹08(第五章目标规划)》由会员分享，可在线阅读，更多相关《运筹08(第五章目标规划)（34页珍藏版）》请在金锄头文库上搜索。

1、运筹学 OPERATIONS RESEARCH*1第五章 目标规划n目标规划的数学模型 n目标规划的图解法n目标规划的单纯形解法n目标规划的层次算法n目标规划的应用Date21 目标规划的提出与数学模型 一、 引例例1、生产计划问题 能力设备A 2 2 12设备B 4 0 16设备C 0 5 15利润 2 3，各生产多少, 可获最大利润?Date32x1+2x2 124x1 16 5x2 15x1，x2 0max Z= 2x1 +3x2解:设产品, 产量分别为变量x1 ， x2最优解：Date4有时目标不只一个，例如考虑下列要求：1、力求利润指标不低于15元；2、两种产品的产量保持1：2；3、

2、A为贵重设备，严格禁止超时使用；4、设备C可适当加班，但要控制；5、设备B既要充分利用，又要尽量不加班，在重要性上 ，设备B是设备C的3倍。要解决这样的问题，将上述的要求都加以考虑，就要用目标规划的方法解决。Date5n目标规划是在线性规划的基础上，为适应 企业经营管理中多目标决策的需要而逐步 发展起来的。目标规划是一种数学方法。n基本含义：在一定约束条件下，要求多个 目标达到或尽可能接近于给定的对应目标 值。n特点：既保持了线性规划易于计算的特点 ，又克服了线性规划只能解决单一目标优 化问题的局限性。Date6目标规划产生与发展n目标规划的有关概念和数学模型是在1961年由美国学者查 恩斯(

3、A.Charnes)和库伯(W.W.Cooper)首次在管理模型 及线性规划的工业应用一书中提出。当时是作为解一个 没有可行解的线性规划而引入的一种方法。这种方法把规 划问题表达为尽可能地接近预期的目标。n1965年，尤吉艾吉里(Yuji Ijiri)在处理多目标问 题，分析各类目标的重要性时，引入了赋予各目标一个优 先因子及加权系数的概念；并进一步完善了目标规划的数 学模型。n表达和求解目标规划问题的方法是由杰斯基莱恩 (Jashekilaineu)和桑李(SangLi)给出并加以改进的 。Date7二、 目标规划的有关概念1、正、负偏差变量 ： 等是决策变量；是正偏差变量，表决策值超过目标

4、值的部分；是负偏差变量，表决策值未达目标值的部分。且有 。2、绝对约束和目标约束 ： 绝对约束：必须满足的等式约束或不等式约束。如A设备严格禁止超时使用，则Date8目标约束：对于不严格限定的约束，在达到此目标时允许发生正或负的偏差，可在这些约束中加入正负偏差变量，成为目标约束。如：（1） “、两种产品的产量保持1：2”可表示为当允许此比例 时，即 ，则引入负偏差 则该条件可表示为：类似地有 ，表示允许此比例 。 表示“力求、两种产品 的产量比例不 ”Date9（2）目标函数也可转化为目标约束：如： “力求利润指标不低于15元”可表示为（3） “设备C可适当加班，但要控制”可表示为（4） “设

5、备B既要充分利用，又要尽量不加班”可表示 为Date103、目标的优先级和权系数不同的目标重要程度不同，优先级不同；同一层次优先级的不同目标，重要程度不同，权重不同优先级因子： ，且权重系数： ，数值的大小决定目标的重要程度。假设 第一优先级：利润不低于15元；第二优先级：、产品的数量尽量保持1：2；第三优先级：C、B的工作时间控制，且B的重要性是C的 3倍。4、目标规划的目标函数 目标函数是要尽量缩小偏离目标值Date11于是按照上例中的有关要求，该目标规划的目标函数构成：约束条件：Date12目标规划特点：可以同时考虑多个目标；可以区分不同目标的优先程度及重要程度；更加切合实际，更加灵活目

6、标规划中的优先级及权重系数的确定往往需要靠人的主观判断，是定性的，常常是模糊的，不是一个确定的数值，但现在也有很多将其定量化的方法，如层次分析法等这是处理目标规划时的一个难点。Date13一般的目标规划数学模型刚性约束柔性约束Date145.2 目标规划的图解分析法求解目标规划的思路：刚性约束必须严格满足；按优先级次序，从高层到低层逐层优化；在不增加高层偏差值的情况下，使本层的偏差达到最小。只有两个决策变量的目标规划可用图解法分析。以上例为例，图解分析如下。Date15满意解Date165.3 目标规划的单纯形解法单纯形法求解目标规划的思路：求解步骤与一般线性规划问题的单纯形法基本相同； 根据

7、目标函数中的优先级次序，从高层到低层逐层优化；单纯形表中，检验数按优先级次序分行表示。例：Date1700P100P1P20 CBXBbx1X2d1-d1+d2-d2+d3-d3+ P1d1-10101-1 0d2-40211-1 P2d3-100 321-1 P1-111 P2-3-21第一步：列初始单纯形表Date18第二步：确定进基变量。按照优先级次序，检查P1，P2，,Pk行检验数是否仍有负值 （0）若有，找优先级最高一行的负值最小检验数对应变量 作为进基变量。此例中选x1第三步：确定出基变量。按照最小比值规则确定出基变量，此例中选d1-第四步：迭代运算，得到新的基可行解，判断是否最优

8、。本例中， P2行仍有负检验数，转到第二步。Date1900P100P1P20CBXBbx1X2d1-d1+d2-d2+d3-d3+0x110101-10d2-2001-221-1P2d3-7002-331-1P111P2-23-3100P100P1P20CBXBbx1X2d1-d1+d2-d2+d3-d3+0x12011/2001/2-1/20d1+1001/2-111/2-1/2P2d3-4001/200-3/23/21-1P111P2-1/23/2-3/21Date2000P100P1P20CBXBbx1X2d1-d1+d2-d2+d3-d3+0x110101-1 000X22001-2

9、21-1P2d3-30001-1-221-1P111P2-112-21注意：此时， P2行仍有负检验数，要选X2进基，因为d2+的检验数是 。此时， 已达最优。Date21说明：1、进行优化是按照优先级进行的，当高一级的目标行的检验数全部非负时，可进行下一级的优化；2、判别迭代终止的准则：（1）所有级别 的检验数行均非负，迭 代终止；（2）若 行检验数均非负，而 行有负检验数，但这些负检验数对应的上面行中有正检验数，迭代终止。Date225.4 目标规划的层次算法（思想同前）第一步：先对目标函数中的 层次进行优化。建立第一层次的线性规划模型，记为LP1.目标函数：由第一优先级的偏差变量构成约束

10、条件：由原约束构成。设第一级优化的最优目标值是Date23第二步：对目标函数中的 层次进行优化。建立第二层次的线性规划模型，记为LP2.目标函数：由第二优先级的偏差变量构成约束条件：在原约束基础上增加新约束：设第二级优化的最优目标值是 。以此类推。Date245.5 目标规划应用举例例1：某电子厂生产录音机和电视机两种产品，分别经由甲、乙两个车间 生产。已知除外构件外，生产一台录音机需甲车间加工2h，以车间装配1h；生产一台电视机需甲车间加工1h，以车间装配3h；检验销售环节：一台录音机检验销售费用50元； 一台电视机检验销售费用30元；工时及管理费用：甲车间每月可用生产工时120h，车间管理

11、费用80元/h; 乙车间每月可用生产工时150h，车间管理费用20元/h;利润及销量： 每台录音机利润100元，平均每月可销售50台； 每台电视机利润75元，平均每月可销售80台；Date25月度计划的目标如下：1、第一优先级：检验和销售费用每月不超过4600元；2、第二优先级：每月销售录音机不少于50台；3、第三优先级：两车间的工时得到充分利用（重要性权系数 按每小时的管理费用比）；4、第四优先级：甲车间加班不超过20小时；5、第五优先级：每月销售电视机不少于80台；6、第六优先级：两车间的加班总时间要控制（权系数分配如 3） 试确定该厂为达到上述目标的最优月度生产计划。Date26解：假设

12、每月生产录音机 台，电视机 台。约束：1、两车间可用工时: 2、检验和销售费用: 3、每月销售量: 4、加班限制:于是目标函数： Date27约束：Date28例2：书P143 例5解：设 是i工厂调配给j用户的产品数量。约束如下1、供应量约束:2、需求量约束:3、用户1需要量中工厂3的产品数量不少于100:Date294、各用户满足率不低于80%：5、运费限制：6、道路通过限制：7、用户1和3的满足率保持平衡：Date308、力求总运费减小：目标函数：Date31例3：某单位领导在考虑本单位职工的升级调资方案时，依次 遵守以下规定：1、年工资总额不超过120万元；2、每级的人数不超过定编规定的人数；3、级的升级面尽可能达到现有人数的20%；4、级不足编制的人数可录用新职工，又级的职工中有 10%要退休。有关资料汇总于下表，请为该单位领导制定一个满意的方案 。等级工资额（元/年 ）现有人数编制人数400001012 300001215 200001515 合计3742Date32解：设 分别表示提升到、级和录用到级的职工人数。确定优先级： 确定各目标约束： （1）年工资总额不超过120万元；（2）每级的人数不超过编制规定的人数；Date33（3） 、级的升级面尽可能达到现有人数的20%；目标函数： Date34