数学建模之优化方法课件

数学建模之优化方法历年回顾:92A题施肥效果分析 回归分析 数据拟合92B题实验数据分解 离散模型、组合最优化93A非线性交调的频率设计 拟合、规划 93B足球队排名 图论、层次分析、整数规划 94A逢山开路 图论、插值、动态规划 94B锁具装箱问题 图论、组合数学 95A飞行管理问题 非线性规划、线性规划 95B天车与冶炼炉的作业调度 动态规划、排队论、图论 96A最优捕鱼策略 微分方程、优化 96B节水洗衣机 非线性规划 07A 人口问题 微分方程、数据处理、优化07B 乘公交，看奥运 多目标规划、动态规划、图论 0-1规划08A 照相机问题 非线性方程组、优化08B 大学学费问题 数据收集和处理、统计分析、回归分析09A 制动器试验台的控制方法分析 微元分析法 09B 眼科病床的合理安排 层次分析法 整数规划 动态规划 排队论10A 储油罐的变位识别与罐容表标定 非线性规划 多元拟合10B 2010年上海世博会影响力的定量评估 数据收集和处理，层次分析法 时间序列分析解法规划问题图论差微分方程数据拟合模拟处理优化数据分析理论其它（排队运输离散）相关赛题93A,93B94A,95A95B,96B97A,98A99B,01B02A,03B06A,06B07B,09B10A93B94A94B95B97B98B99B07B96A03A07A08A09A92A,93A97B,99A01A,04A04B,05A06A,07A08B,10A10B92B,96A98A,98B99A,00B 02B,04A04B,06A07A,08A93B04A09A09B10B92B94A94B95B00A00B合计1785131266赛题发展的特点：赛题发展的特点：1.对选手的计算机能力提出了更高的要求：赛题的解决依赖计算机，题目的数据较多，手工计算不能完成，如03B，某些问题需要使用计算机软件，01A。问题的数据读取需要计算机技术，如00A（大数据），01A（图象数据，图象处理的方法获得），04A（数据库数据，数据库方法，统计软件包）。计算机模拟和以算法形式给出最终结果。2.赛题的开放性增大解法的多样性，一道赛题可用多种解法。开放性还表现在对模型假设和对数据处理上。3.试题向大规模数据处理方向发展 4.求解算法和各类现代算法的融合，5.更关注于当年的实事问题eg：04A奥运会临时超市网点设计，07B 乘公交，看奥运，10B 2010年上海世博会影响力的定量评估等；生产计划问题生产计划问题线性规划模型 2x1+x2 8 s.t.x1 3 x2 4 x1，x2 0 max f=5x1+2x2 求最大利润求最大利润三种材料量的限制三种材料量的限制生产量非负生产量非负线性规划模型运输问题运输问题线性规划模型解：解：设设A A1,1,A A2 2调运到三个粮站的大米分别为调运到三个粮站的大米分别为x x1 1，x x2 2，x x3 3，x x4 4，x x5 5，x x6 6吨。吨。题设量可总到下表：题设量可总到下表：线性规划模型结合存量限制和需量限制得数学模型结合存量限制和需量限制得数学模型：线性规划模型 m个产地个产地A1,Am联合供应联合供应n个销地个销地B1,Bn,各产各产地至各销地单位运价地至各销地单位运价(单位单位:元元/吨吨)为为cij，问如何调运使，问如何调运使总运费最少总运费最少?一般运输问题一般运输问题总运价总运价产量限制产量限制需量限制需量限制运量非负运量非负线性规划模型假设假设产销平衡产销平衡:在很多实际问题中在很多实际问题中,解题思想和运输问题同出一辙解题思想和运输问题同出一辙,也就是说我们可以用运输模型解决其他问题也就是说我们可以用运输模型解决其他问题.线性规划模型 设有设有n件工作件工作B1,B2,Bn,分派给分派给n人人A1,A2,An去去做做,每人只做一件工作且每件工作只派一个人去做每人只做一件工作且每件工作只派一个人去做,设设Ai完成完成Bj的工时为的工时为cij,问应如何分派才能完成全部工作的问应如何分派才能完成全部工作的总工时最少总工时最少.每件工作只派每件工作只派1人人每个人只派做每个人只派做1件件变量变量xi只取只取0和和1,故建立故建立的模型也称的模型也称0-1规划规划.分派问题分派问题线性规划模型选址问题选址问题线性规划模型 现要做现要做100套钢架套钢架,用长为用长为2.9m、2.1m和和1.5m的元的元钢各一根钢各一根,已知原料长已知原料长7.4m,问如何下料问如何下料,使用的原材料使用的原材料最省最省?分析分析:下料方式：下料方式：最省：最省：1.所用刚架根数最少；所用刚架根数最少；2.余料最少余料最少下料问题下料问题线性规划模型原料截成所需原料截成所需长度的根数长度的根数下料方法下料方法所所需需根根长长2.9m211100002.1m021032101.5m10130234剩余料头剩余料头0.10.30.901.10.20.81.4线性规划模型不同方不同方法截得法截得每种根每种根长的总长的总数至少数至少100例例3,4中的此例的变量中的此例的变量xi只取正整数只取正整数,故建立的模型也称故建立的模型也称整数规划整数规划.0-1规划是整数规划的特殊情形规划是整数规划的特殊情形.线性规划模型 某公司生产某产品某公司生产某产品,最大生产能力为最大生产能力为100单位单位,每单位每单位存储费存储费2元元,预定的销售量与单位成本如下预定的销售量与单位成本如下:月份月份单位成本单位成本(元元)销售量销售量1234 70 60 72 70 80 120 76 60求一生产计划求一生产计划,使使 1)满足需求满足需求;2)不超过生产能力不超过生产能力;3)成本成本(生产成本与存储费之和生产成本与存储费之和)最低最低.阶段生产问题阶段生产问题线性规划模型 解解:假定假定1月初无库存月初无库存,4月底卖完月底卖完,当月生产的不库当月生产的不库存存,库存量无限制库存量无限制.第j+1个月的库存量第j+1个月的库存费共共3个月的库存费个月的库存费到本月总生产量到本月总生产量大于等于销售量大于等于销售量4个月总生产量等个月总生产量等于总销售量于总销售量4个月总个月总生产成本生产成本线性规划模型线性规划模型月份月份单位成本单位成本(元元)销售量销售量1234 70 60 72 70 80 120 76 60线性规划模型76827676-80-7472-747270生产月100100100100产量6041207060销量4321321需求月费用费用cij线性规划模型本题本题3个模型为整数规划模型个模型为整数规划模型.线性规划模型线性规划模型特点决策变量：向量(x1 xn)T,决策人要考虑和控制的因素非负；约束条件：线性等式或不等式；目标函数：Z=(x1 xn)线性式，求Z极大或极小；线性规划模型一般形式一般形式目标函数目标函数约约束束条条件件线性规划模型30矩阵形式矩阵形式线性规划模型满足约束条件的变量的值称为满足约束条件的变量的值称为可行解可行解，可行解的集合称为可行解的集合称为可行域可行域。使目标函数达到最大（小）值的可行解使目标函数达到最大（小）值的可行解称为称为最优解最优解，相应的目标函数的值称为相应的目标函数的值称为最优值最优值。线性规划模型线性规划问题的性质:比例性比例性 每个决策变量对目标函数以及右端项每个决策变量对目标函数以及右端项的贡献与该决策变量的取值成正比的贡献与该决策变量的取值成正比.可加性可加性 每个决策变量对目标函数以及右端项的每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关贡献与其他决策变量的取值无关.连续性连续性 每个决策变量的取值都是连续的每个决策变量的取值都是连续的.线性规划模型应 用市场营销市场营销(广告预算和媒介选择，竞争性定价，广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划新产品开发，制定销售计划)生产计划制定生产计划制定(合理下料，配料，合理下料，配料，“生产计划、生产计划、库存、劳力综合库存、劳力综合”)库存管理库存管理(合理物资库存量，停车场大小，设合理物资库存量，停车场大小，设备容量备容量)运输问题运输问题线性规划模型财政、会计财政、会计(预算，贷款，成本分析，投预算，贷款，成本分析，投资，证券管理资，证券管理)人事人事(人员分配，人才评价，工资和奖金人员分配，人才评价，工资和奖金的确定的确定)设备管理设备管理(维修计划，设备更新维修计划，设备更新)城市管理城市管理(供水，污水管理，服务系统设供水，污水管理，服务系统设计、运用计、运用)线性规划问题的基本理论用图解法求解线性规划问题用图解法求解线性规划问题是一簇斜率为是一簇斜率为-5/2的平的平行直线族行直线族斜率为斜率为-2C/2为直线与为直线与y轴的交点轴的交点x10 x28443 求解线性规划的Matlab解法1.Matlab解线性规划的标准形式 x,fval=linprog(c,A1,b1,A2,b2)x,fval=linprog(c,A1,b1,A2,b2,lb,ub)x,fval=linprog(c,A1,b1,A2,b2,lb,ub,x0)没有的加例如x=0;则lb=0,ub用代替求解线性规划问题 编写Matlab程序如下：c=2;3;1;a=-1,-4,-2;-3,-2,-0;b=-8;-6;x,y=linprog(c,a,b,zeros(3,1)例例5.15.1某家具公司制造书桌、餐桌和椅子，所用的资源有三种：木料、木工和漆工。生产数据如下表所示：若要求桌子的生产量不超过5件，如何安排三种产品的生产可使利润最大？每个书桌每个餐桌每个椅子现有资源总数木料8单位6单位1单位48单位漆工4单位2单位1.5单位20单位木工2单位1.5单位0.5单位8单位成品单价60单位30单位20单位max=60*desks+30*tables+20*chairs;8*desks+6*tables+chairs=48;4*desks+2*tables+1.5*chairs=20;2*desks+1.5*tables+.5*chairs=8;tables=5;连续投资连续投资10万元万元A：从第：从第1年年 到第到第4年每年初要投资，次年末回收年每年初要投资，次年末回收本利本利1.15B：第第3年初投资，到第年初投资，到第5年末回收年末回收1.25，最大投资，最大投资4万元万元C：第第2年初投资，到第年初投资，到第5年末回收年末回收1.40，最大投资，最大投资3万元万元D：每年初投资，每年末回收每年初投资，每年末回收1.11。求：求：5年末总资本最大。年末总资本最大。练习练习1 1:连续连续投资投资练习练习2某服务部门一周中每天需要不同数目的雇员，某服务部门一周中每天需要不同数目的雇员，周一到周四每天至少需要周一到周四每天至少需要50人，周五至少需要人，周五至少需要80人，人，周六和周日至少需要周六和周日至少需要90人，现规定应聘者需连续工人，现规定应聘者需连续工作作5天，试确定聘用方案。天，试确定聘用方案。练习练习3某班准备从某班准备从5名游泳员中选择人组成接力队，名游泳员中选择人组成接力队，藏家学校的藏家学校的4100m混合泳接力比赛，混合泳接力比赛，5名队员名队员4种泳种泳姿的百米平均成绩如表，问如何选拔队员。姿的百米平均成绩如表，问如何选拔队员。队员甲乙丙丁戊蝶泳10685721181101074仰泳115610611421142111蛙泳1271064109610961238自由泳586535945721024 线性模型题目1 生产计划问题生产计划问题某工厂计划安排生产，两种产品，已知每种单位产品的利润，生产单位产品所需设备台时及A,B两种原材料的消耗，现有原材料和设备台时的定额如表所示，问：）怎么安排生产使得工厂获利最大？）产品的单位利润降低到1.8万元，要不要改变生产计划，如果降低到1万元呢？）产品的单位利润增大到5万元，要不要改变生产计划？）如果产品，的单位利润同时降低了1万元，要不要改变生产计划？产品产品最大资源量设备128台时原材料A4016kg原材料B0412kg单位产品利润23 线性模型建立 线性模型求解程序编写程序编写model:title 生产计划问题;maxfmax=2*x1+3*x2;Ax1+2*x28;B4*x116;TIME4*x212;END 线性模型求解运行结果运行结果 Model Title:生产计划问题 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2.000000 0.000000 Row Slack or Surplus Dual Price MAXF 14.00000 1.000000 A 0.000000 1.500000 B 0.000000 0.1250000 TIME 4.000000 0.000000 对问题1，安排是生产产品4单位，产品2单位，最大盈利为14万元。线性模型敏感性理论1目标函数的系数变化的敏感性分析目标函数的系数变化的敏感性分析如果目标函数的系数发生变化，将会影响目标函数 f 斜率的变化，但是只要f 的斜率小于等于-1/2（也就是直线l夹在l1与l2之间时），最优解都在(4,2)上取到，最优解不变，从而生产计划不会变.线性模型敏感性分析1要使用敏感性分析要使用敏感性分析必须要在这里选择必须要在这里选择Prices&Ranges然后然后保存保存退出退出路径：路径：LINGOOptionsGeneral Solver(通用求解程序通用求解程序)选项卡选项卡 线性模型敏感性分析1要调出敏感性分析的结果，要调出敏感性分析的结果，必须必须先求解先求解后再后再在程序窗在程序窗口下口下点击点击LINGORange，线性模型敏感性分析1Ranges in which the basis is unchanged:Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 2.000000 INFINITY 0.5000000 X2 3.000000 1.000000 3.000000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease A 8.000000 2.000000 4.000000 B 16.00000 16.00000 8.000000 TIME 12.00000 INFINITY 4.000000 当前变量系数允许增加量允许减少量对问题对问题2，产品，产品的单位利润降低到的单位利润降低到1.8万元，在（万元，在（1.5，）之间，所以不改）之间，所以不改变生产计划。如果降低到变生产计划。如果降低到1万元，不在（万元，不在（1.5，）内，要改变生产计划。在程）内，要改变生产计划。在程序中将目标函数的系数序中将目标函数的系数“2”改为改为“1”，可得新的计划为，可得新的计划为安排是生产产品安排是生产产品2单单位，位，产产品品3单位，最大盈利为单位，最大盈利为11万元万元.对问题对问题3，要改变生产计划，更改程序得新计划为生产产品，要改变生产计划，更改程序得新计划为生产产品2单位，产品单位，产品3单位，最大盈利为单位，最大盈利为19万元万元.对问题对问题4，因为两个系数同时改变了，所以只有更改程序的数据，重新运，因为两个系数同时改变了，所以只有更改程序的数据，重新运行得：不改变生产计划，但是最大利润降低到行得：不改变生产计划，但是最大利润降低到8万元万元.线性模型敏感性理论2 线性模型影子价格理论把y1,y2,y3作为三种原料的定价，定价的目标是在比生产产品获得更多利润的前提下的最小利润.在最优情况下，在最优情况下，y的值就是资的值就是资源的源的影子价格，影子价格，影子价格有意影子价格有意义是有范围的义是有范围的。影子价格经济含义是：在资源得到最优配影子价格经济含义是：在资源得到最优配置，使总效益最大时，该资源投入量每增置，使总效益最大时，该资源投入量每增加一个单位所带来总收益的增加量加一个单位所带来总收益的增加量 线性模型综合讨论Ranges in which the basis is unchanged:Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 2.000000 INFINITY 0.5000000 X2 3.000000 1.000000 3.000000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease A 8.000000 2.000000 4.000000 B 16.00000 16.00000 8.000000 TIME 12.00000 INFINITY 4.000000 运行结果运行结果 Model Title:生产计划问题 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2.000000 0.000000 Row Slack or Surplus Dual Price MAXF 14.00000 1.000000 A 0.000000 1.500000 B 0.000000 0.1250000 TIME 4.000000 0.000000 线性模型题目21桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶 时间时间480小时小时 至多加工至多加工100公斤公斤A1 制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到的获利增加到 30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？每天：每天：加工奶制品的生产计划加工奶制品的生产计划 线性模型建立x1桶牛奶生产桶牛奶生产A1 x2桶牛奶生产桶牛奶生产A2 获利获利 243x1 获利获利 164 x2 原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决策变量决策变量 目标函数目标函数 每天获利每天获利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)线性模型求解Max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100;OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 NO.ITERATIONS=220桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润，利润3360元。元。线性模型影子价格 OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 35元可买到元可买到1桶牛奶，要买吗？桶牛奶，要买吗？35 48,应该买！应该买！聘用临时工人付出的工资最多每小时几元？聘用临时工人付出的工资最多每小时几元？2元！元！线性模型敏感性分析RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000 A1获利增加到获利增加到 30元元/千克，应否改变生产计划？千克，应否改变生产计划？不变！不变！35元可买到元可买到1桶牛奶，每天最多买多少？桶牛奶，每天最多买多少？最多买最多买10桶！桶！2.整数规划 定义规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划 1o 变量全限制为整数时，称纯（完全）整数规划。2o 变量部分限制为整数的，称混合整数规划。3o 变量只能取0或1时，称之为0-1整数规划。（i）分枝定界法可求纯或混合整数线性规划。（ii）割平面法可求纯或混合整数线性规划。（iii）隐枚举法求解“0-1”整数规划：过滤隐枚举法；分枝隐枚举法。（iv）匈牙利法解决指派问题（“0-1”规划特殊情形）。（v）蒙特卡洛法求解各种类型规划(随机取样法)特殊的整数规划指派问题（又称分配问题Assignment Problem）拟分配 人去干 项工作，每人干且仅干一项工作，若分配第 人去干第 项工作，需花费 单位时间，问应如何分配工作才能使工人花费的总时间最少？求解下列指派问题，已知指派矩阵为 编写Matlab程序如下：c=3 8 2 10 3;8 7 2 9 7;6 4 2 7 5；8 4 2 3 5;9 10 6 9 10;c=c(:);a=zeros(10,25);for i=1:5 a(i,(i-1)*5+1:5*i)=1;a(5+i,i:5:25)=1;endb=ones(10,1);x,y=linprog(c,a,b,zeros(25,1),ones(25,1)整数规划的计算机解法整数规划问题的求解可以使用Lingo,Lindo等专用软件.例例5.15.1某家具公司制造书桌、餐桌和椅子，所用的资源有三种：木料、木工和漆工。生产数据如下表所示：若要求桌子的生产量不超过5件，如何安排三种产品的生产可使利润最大？每个书桌每个餐桌每个椅子现有资源总数木料8单位6单位1单位48单位漆工4单位2单位1.5单位20单位木工2单位1.5单位0.5单位8单位成品单价60单位30单位20单位max=60*desks+30*tables+20*chairs;8*desks+6*tables+chairs=48;4*desks+2*tables+1.5*chairs=20;2*desks+1.5*tables+.5*chairs=8;tables0，初始可行点，初始可行点xk,初始步长初始步长k0,在在xk线性化得线性规划问题：线性化得线性规划问题：非线性规划有约束问题 求出此线性规划问题得最优解求出此线性规划问题得最优解xk1，检验，检验是否为原问题的的可行解，若是转是否为原问题的的可行解，若是转，否则缩短，否则缩短步长转步长转；判断精度。判断精度。则取则取最优解最优解x*=xk+1,停，否则令停，否则令k=k+1转转。非线性规划有约束问题（2）罚函数法）罚函数法转化为无约束最优化问题：转化为无约束最优化问题：M为足够大的正数。称为为足够大的正数。称为罚因子罚因子。算法分析：算法分析：设可行域为设可行域为S，构造函数：，构造函数：非线性规划有约束问题 求无约束问题得最优解为求无约束问题得最优解为X(M),直观看出，直观看出，只有当只有当X(M)S才可能真正取得极小值，若才可能真正取得极小值，若就就加大加大罚因子罚因子M，使，使X(M)向向S逼近，逼近，当当M时，点列时，点列非线性规划有约束问题计算步骤计算步骤：（第：（第k次迭代）次迭代）非线性规划有约束问题有约束问题matlab解法x,fval=fmincon(myfun,x0,A,b)x,fval=fmincon(myfun,x0,A,b,Aeq,beq)x,fval=fmincon(myfun,x0,A,b,Aeq,beq,lb,ub)x,fval=fmincon(myfun,x0,A,b,Aeq,beq,lb,ub,comfun)缺省的用代替myfun与confun是M-函数的地址具体如:目标函数：Function f=myfun(x)非线性约束：function c,ceq=confun(x)%Nonlinear inequality constraintsc=c1(x);c2(x);.;%Nonlinear equality constraintsceq=ceq1(x);ceq2(x);.;M-函数1先建立先建立M文件文件 fun4.m,定义目标函数定义目标函数:function f=fun4(x);f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);x1+x2=0 s.t.1.5+x1x2-x1-x2 0 -x1x2 10 0例例32再建立再建立M文件文件mycon.m定义非线性约束：定义非线性约束：function g,ceq=mycon(x)g=x(1)+x(2);1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10;例4 1先建立先建立M-文件文件fun.m定义目标函数定义目标函数:function f=fun(x);f=-2*x(1)-x(2);2再建立再建立M文件文件mycon2.m定义非线性约束：定义非线性约束：function g,ceq=mycon2(x)g=x(1)2+x(2)2-25;x(1)2-x(2)2-7;应用实例：应用实例：供应与选址供应与选址 某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：千米）及水泥日用量d(吨)由下表给出。目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20吨。假设从料场到工地之间均有直线道路相连。（1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多大？（一）、建立模型（一）、建立模型 记工地的位置为记工地的位置为(ai，bi)，水泥日用量为，水泥日用量为di，i=1,6;料场位置料场位置为为(xj，yj)，日储量为，日储量为ej，j=1,2；从料场；从料场j向工地向工地i的运送量为的运送量为Xij。当用临时料场时决策变量为：Xij，当不用临时料场时决策变量为：Xij，xj，yj。（二）使用临时料场的情形（二）使用临时料场的情形 使用两个临时料场A(5,1)，B(2,7).求从料场j向工地i的运送量为Xij，在各工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，这是线性规划问题.线性规划模型为：设X11=X1,X21=X 2,X31=X 3,X41=X 4,X51=X 5,X61=X 6X12=X 7,X22=X 8,X32=X 9,X42=X 10,X52=X 11,X62=X 12 编写程序gying1.mMATLAB（gying1）计算结果为：计算结果为：x=3.0000 5.0000 0.0000 7.0000 0.0000 1.0000 0.0000 0.0000 4.0000 0.0000 6.0000 10.0000fval=136.2275（三）改建两个新料场的情形（三）改建两个新料场的情形 改建两个新料场，要同时确定料场的位置(xj,yj)和运送量Xij，在同样条件下使总吨千米数最小。这是非线性规划问题。非线性规划模型为：设 X11=X1,X21=X 2,X31=X 3,X41=X 4,X51=X 5,X61=X 6 X12=X 7,X22=X 8,X32=X 9,X42=X 10,X52=X 11,X62=X 12 x1=X13,y1=X14,x2=X15,y2=X16 （1）先编写M文件liaoch.m定义目标函数。MATLAB（liaoch）(2)取初值为线性规划的计算结果及临时料场的坐标:x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7;编写主程序gying2.m.MATLAB（gying2）(3)计算结果为：x=3.0000 5.0000 0.0707 7.0000 0 0.9293 0 0 3.9293 0 6.0000 10.0707 6.3875 4.3943 5.7511 7.1867fval=105.4626exitflag=1(4)若修改主程序gying2.m,取初值为上面的计算结果:x0=3.0000 5.0000 0.0707 7.0000 0 0.9293 0 0 3.9293 0 6.0000 10.0707 6.3875 4.3943 5.7511 7.1867得结果为:x=3.0000 5.0000 0.3094 7.0000 0.0108 0.6798 0 0 3.6906 0 5.9892 10.3202 5.5369 4.9194 5.8291 7.2852fval=103.4760exitflag=1总的吨千米数比上面结果略优.(5)若再取刚得出的结果为初值,却计算不出最优解.MATLAB（gying2）MATLAB（gying2）(6)若取初值为:x0=3 5 4 7 1 0 0 0 0 0 5 11 5.6348 4.8687 7.2479 7.7499,则计算结果为:x=3.0000 5.0000 4.0000 7.0000 1.0000 0 0 0 0 0 5.0000 11.0000 5.6959 4.9285 7.2500 7.7500fval=89.8835exitflag=1总的吨千米数89.8835比上面结果更好.通过此例可看出fmincon函数在选取初值上的重要性.MATLAB（gying2）返回返回 露天矿里铲位已分成矿石和岩石露天矿里铲位已分成矿石和岩石:平均铁含量不低于平均铁含量不低于25%的的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多安置一台电平均铁含量（称为品位）都是已知的。每个铲位至多安置一台电铲，电铲平均装车时间铲，电铲平均装车时间5分钟。分钟。卡车在等待时所耗费的能量也是相当可观的，原则上在安卡车在等待时所耗费的能量也是相当可观的，原则上在安排时排时不应发生卡车等待不应发生卡车等待的情况。的情况。矿石卸点需要的铁含量要求都为矿石卸点需要的铁含量要求都为29.5%1%(品位限制），品位限制），搭配量在一个班次（搭配量在一个班次（8小时）内满足品位限制即可。卸点在一个小时）内满足品位限制即可。卸点在一个班次内不变。卡车载重量为班次内不变。卡车载重量为154吨，平均时速吨，平均时速28km,平均卸车时间平均卸车时间为为3分钟。分钟。问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次别在哪些路线上各运输多少次?露天矿生产的车辆安排(CUMCM-2003B)露天矿生产的车辆安排(CUMCM-2003B)距离铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏5.265.194.214.002.952.742.461.900.641.27倒装1.900.991.901.131.272.251.482.043.093.51岩场5.895.615.614.563.513.652.462.461.060.57岩石漏0.641.761.271.832.742.604.213.725.056.10倒装4.423.863.723.162.252.810.781.621.270.50铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石量095105100105110125105130135125岩石量125110135105115135105115135125铁含量30%28%29%32%31%33%32%31%33%31%露天矿生产的车辆安排(CUMCM-2003B)与典型的运输问题明显有以下不同：与典型的运输问题明显有以下不同：1.这是运输矿石与岩石两种物资的问题；这是运输矿石与岩石两种物资的问题；2.属于产量大于销量的不平衡运输问题；属于产量大于销量的不平衡运输问题；3.为了完成品位约束，矿石要搭配运输；为了完成品位约束，矿石要搭配运输；4.产地、销地均有单位时间的流量限制；产地、销地均有单位时间的流量限制；5.运输车辆只有一种，每次满载运输，运输车辆只有一种，每次满载运输，154吨吨/车次；车次；6.铲位数多于铲车数意味着要最优的选择不多于铲位数多于铲车数意味着要最优的选择不多于7个产地作为个产地作为最后结果中的产地；最后结果中的产地；7.最后求出各条路线上的派出车辆数及安排。最后求出各条路线上的派出车辆数及安排。近似处理：近似处理：先求出产位、卸点每条线路上的运输量先求出产位、卸点每条线路上的运输量(MIP模型模型)然后求出各条路线上的派出车辆数及安排然后求出各条路线上的派出车辆数及安排 问题分析卡车在一个班次中不应发生等待或熄火后再启动的情卡车在一个班次中不应发生等待或熄火后再启动的情况；况；在铲位或卸点处由两条路线以上造成的冲突问题面前，在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认为不冲突。我我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论；们不排时地进行讨论；空载与重载的速度都是空载与重载的速度都是28km/h，耗油相差很大；，耗油相差很大；卡车可提前退出系统，等等。卡车可提前退出系统，等等。模型假设(近似近似)xij：从：从i铲位到铲位到j号卸点的石料运量号卸点的石料运量（车）（车）单位：单位：吨；吨；cij：从：从i号铲位到号铲位到j号卸点的距离号卸点的距离 公里；公里；Tij:从从i号铲位到号号铲位到号j卸点路线上运行一个周期平均时间卸点路线上运行一个周期平均时间 分；分；Aij：从号铲位到号卸点最多能同时运行的卡车数：从号铲位到号卸点最多能同时运行的卡车数 辆；辆；Bij：从号铲位到号卸点路线上一辆车最多可运行的次数：从号铲位到号卸点路线上一辆车最多可运行的次数 次；次；pi：i号铲位的矿石铁含量号铲位的矿石铁含量 p=(30,28,29,32,31,33,32,31,33,31)%qj:j号卸点任务需求，号卸点任务需求，q=(1.2,1.3,1.3,1.9,1.3)*10000 吨吨cki：i号铲位的铁矿石储量号铲位的铁矿石储量 万吨万吨cyi：i号铲位的岩石储量号铲位的岩石储量 万吨万吨fi:描述第描述第i号铲位是否使用的号铲位是否使用的0-1变量，取变量，取1为使用；为使用；0为关闭为关闭 符号说明（4）铲位储量约束（1）道路能力(卡车数)约束（2）电铲能力约束（3）卸点能力约束 模型建立优化模型优化模型xij为非负整数fi 为0-1整数（5）产量任务约束（8）整数约束（7）电铲数量约束（6）铁含量约束 模型建立 程序编写model:title CUMCM-2003B-01;sets:cai/1.10/:crate,cnum,cy,ck,flag;xie/1.5/:xsubject,xnum;link(xie,cai):distance,lsubject,number,che,b;endsetsdata:crate=30 28 29 32 31 33 32 31 33 31;xsubject=1.2 1.3 1.3 1.9 1.3;distance=5.26 5.19 4.21 4.00 2.95 2.74 2.46 1.90 0.64 1.27 1.90 0.99 1.90 1.13 1.27 2.25 1.48 2.04 3.09 3.51 5.89 5.61 5.61 4.56 3.51 3.65 2.46 2.46 1.06 0.57 0.64 1.76 1.27 1.83 2.74 2.60 4.21 3.72 5.05 6.10 4.42 3.86 3.72 3.16 2.25 2.81 0.78 1.62 1.27 0.50;cy=1.25 1.10 1.35 1.05 1.15 1.35 1.05 1.15 1.35 1.25;ck=0.95 1.05 1.00 1.05 1.10 1.25 1.05 1.30 1.35 1.25;enddata 程序编写!目标函数目标函数;min=sum(cai(i):sum(xie(j):number(j,i)*154*distance(j,i);!卡车每一条路线上最多可以运行的次数卡车每一条路线上最多可以运行的次数;for(link(i,j):b(i,j)=floor(8*60-(floor(distance(i,j)/28*60*2+3+5)/5)-1)*5)/(distance(i,j)/28*60*2+3+5);!每一条路线上的最大总车次的计算每一条路线上的最大总车次的计算;for(link(i,j):lsubject(i,j)=(floor(distance(i,j)/28*60*2+3+5)/5)*b(i,j);!计算各个铲位的总产量计算各个铲位的总产量;for(cai(j):cnum(j)=sum(xie(i):number(i,j);!计算各个卸点的总产量计算各个卸点的总产量;for(xie(i):xnum(i)=sum(cai(j):number(i,j);程序编写!道路能力约束道路能力约束;for(link(i,j):number(i,j)=lsubject(i,j);!电铲能力约束电铲能力约束;for(cai(j):cnum(j)=flag(j)*8*60/5);!电铲数量约束电铲数量约束 -added by Xie Jinxing,2003-09-07-added by Xie Jinxing,2003-09-07;sum(cai(j):flag(j)=7;!卸点能力约束卸点能力约束;for(xiexie(i):xnum(i)=8*20);!铲位产量约束铲位产量约束;for(cai(i):number(1,i)+number(2,i)+number(5,i)=ck(i)*10000/154);for(cai(i):number(3,i)+number(4,i)=xsubject(i)*10000/154);程序编写!铁含量约束铁含量约束;sum(cai(j):number(1,j)*(crate(j)-30.5)=0;sum(cai(j):number(2,j)*(crate(j)-30.5)=0;sum(cai(j):number(5,j)*(crate(j)-30.5)=0;sum(cai(j):number(2,j)*(crate(j)-28.5)=0;sum(cai(j):number(5,j)*(crate(j)-28.5)=0;!关于车辆的具体分配关于车辆的具体分配;for(link(i,j):che(i,j)=number(i,j)/b(i,j);程序编写!各个路线所需卡车数简单加和各个路线所需卡车数简单加和;hehe=sum(link(i,j):che(i,j);!整数约束整数约束;for(link(i,j):gin(number(i,j);for(cai(j):bin(flag(j);!车辆能力约束车辆能力约束;hehe=20;ccnum=sum(cai(j):cnum(j);end铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿漏131354541111倒42424343岩场70701515岩漏81814343倒13132 27070铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏0.8671.8620.314倒场1.0771.162岩场1.8920.326岩石漏1.8411.229倒场0.6840.11.489 求解结果铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏1(29)倒场1(39)1(37)岩场1(37)岩石漏1(44)1(35)倒场1(47)结论：结论：铲位铲位1、2、3、4、8、9、10处各放置一台电铲。处各放置一台电铲。一共使用了一共使用了13辆卡车；总运量为辆卡车；总运量为85628.62吨公里；吨公里；岩石产量为岩石产量为32186吨；矿石产量为吨；矿石产量为38192吨。吨。求解结果动态规划模型举例产品生产计划安排问题 例1 某工厂生产某种产品的月生产能力为10件，已知今后四个月的产品成本及销售量如表所示。如果本月产量超过销售量时，可以存储起来备以后各月销售，一件产品的月存储费为2元，试安排月生产计划并做到：1、保证满足每月的销售量，并规定计划期初和期末库存为零；2、在生产能力允许范围内，安排每月生产量计划使产品总成本(即生产费用加存储费)最低。例1 产品生产计划安排设xk为第k阶段生产量，则有直接成本 dk(sk,xk)=ck xk+2sk状态转移公式为 sk-1=sk+xk-yk总成本递推公式第一阶段第一阶段：(即第即第4月份月份)由边界条件和状态转移方程由边界条件和状态转移方程 s0=s1+x1 y1=s1+x1 6=0 得得 s1+x1=6 或或 x1=6 s1 0估计第一阶段，即第估计第一阶段，即第4月份初库存的可能状态：月份初库存的可能状态：0 s1 30 6 7 12=5，所以，所以，s1 0,5第一阶段最优决策表第二阶段：最大可能库存量 7 件由状态转移方程：s1=s2+x2 120 及 x210，可知 s22,7，min x2=5由阶段效果递推公式有：f2(2,10)=d2(2,10)+f1*(0,6)=22+8010+456=1260得第二阶段最优决策表，如下第二阶段最优决策表第三阶段：最大可能库存量 4 件由状态转移方程：s2=s3+x3 72 及 x310，可知 s30,4，min x3=5由阶段效果递推公式有：f3(1,10)=d3(1,10)+f2*(4,8)=21+7210+1104=1826得第三阶段最优决策表，如下第三阶段最优决策表第四阶段：初始库存量 s4=0由状态转移方程：s3=s4+x4 60 可知 x46，由阶段效果递推公式有：f4(0,6)=d4(0,6)+f3*(0,10)=706+1902=2322得第四阶段最优决策表，如下回回溯溯得得此此表表三、三、建立动态规划模型的基本步骤建立动态规划模型的基本步骤 （1）将问题的过程恰当地分成若干阶段，一般可按问题所处的时间或空间进行划分，并确定阶段变量。如K=1，2，n。（2）正确选择状态变量 并满足无后效性条件。（3）确定决策变量 及允许决策集合 （4）写出状态转移方程。（5）明确指标函数 或 与阶段指标 之间的关系以及边界条件。（6）写出动态规划方程（数学模型）。注记：注记：（1）动态规划主要是解决多阶段决策问题。有趣的是很多表面上看并不是多阶段的问题，只有恰当地分断就可变成一个多阶段问题。从而可利用动态规划求解。这里的关键是分段和正确地选择上诉变量和指标函数，尤其要注意状态变量的无后效性。（2）在建立动态规划方程时，首先要确定是用逆序法，还是用顺序法。由于这二种方法的边界条件不同，因此在选择方法时，要根据边界条件的难易来。（3）要灵活运用最优化原理，不要四套上诉步骤。资源分配问题项目选择问题 某工厂预计明年有A,B,C,D四个新建项目，每个项目的投资额 wk及其投资后的收益 vk如右表所示。投资总额为30万元，问如何选择项目才能使总收益最大。上述问题的静态规划模型如下：这是一类这是一类0-1规划问题规划问题该问题是经典的该问题是经典的旅行背包问题旅行背包问题(Knapsack)该问题是该问题是 NP-complete 例4 项目选择问题解：设项目选择的顺序为A,B,C,D;1、阶段 k=1,2,3,4 分别对应 D,C,B,A项目的选择过程2、第 k 阶段的状态 sk，代表第 k 阶段初尚未分配的投资额3、第 k 阶段的决策变量 xk,，代表第 k 阶段分配的投资额4、状态转移方程为 sk1=sk wk xk5、直接效益 dk(sk,xk)=vk 或 06、总效益递推公式 该问题的难点在于各阶段的状态的确定，当阶段增加时，状该问题的难点在于各阶段的状态的确定，当阶段增加时，状态数成指数增长。下面利用决策树来确定各阶段的可能状态。态数成指数增长。下面利用决策树来确定各阶段的可能状态。例4 第一阶段(项目D)的选择过程s1损失制排队模型实例损失制排队模型实例S1(M/M/S/S)例例2：某单位电话交换台有一台：某单位电话交换台有一台200门内线门内线的总机，已知在上班的总机，已知在上班8小时内，有小时内，有20%的的内线分机平均每内线分机平均每40min要一次外线电话，要一次外线电话，80%的分机平均间隔的分机平均间隔120min要一次外线。要一次外线。又知外线打入内线的电话平均每分钟又知外线打入内线的电话平均每分钟1次。次。假设与外线通话的时间为平均假设与外线通话的时间为平均3min，并，并且上述时间均服从负指数分布，如果要且上述时间均服从负指数分布，如果要求电话的通话率为求电话的通话率为95%，问该交换台应，问该交换台应设置多少条外线？设置多少条外线？损失制排队模型实例损失制排队模型实例例例2：分析：分析：1)电话交换台的服务分成两类，第一类内电话交换台的服务分成两类，第一类内线打外线，其强度为线打外线，其强度为 1=（0.260/40+0.860/120）200=140第二类是外线打内线，其强度为第二类是外线打内线，其强度为 2=160=60因此总的强度为因此总的强度为 =1+2=140+60=2002)按题目要求，系统损失的概率不能超过按题目要求，系统损失的概率不能超过5%，即，即Plost0.053）外线是整数，在满足条件下，条数越）外线是整数，在满足条件下，条数越少越好少越好Model:R=200;T=3/60;load=R*T;Plost=pel(load,S);Plost=0.05;Q=1-Plost;R_e=Q*R;A=Q*R_e;L_s=R_e*T;eta=L_s/S;Min=S;gin(S);end混合制排队模型混合制排队模型混合制排队模型通常记为：混合制排队模型通常记为：M/M/S/K,即有即有S个服个服务台或服务员，系统空间容量为务台或服务员，系统空间容量为K，当，当K个位置已个位置已被顾客占用时，新到的顾客自动离去，当系统中被顾客占用时，新到的顾客自动离去，当系统中有空位置时，新到的顾客进入系统排队等待。有空位置时，新到的顾客进入系统排队等待。闭合式排队模型闭合式排队模型设系统内有设系统内有M个服务台，顾客到达系统的间隔时间个服务台，顾客到达系统的间隔时间和服务台的服务时间均为负指数分布，而系统的容和服务台的服务时间均为