《运筹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