1、数学建模数学建模 优化专题优化专题第1页专题板块系列专题板块系列概率统计专题概率统计专题1优化专题优化专题2含糊方法及微分方程专题含糊方法及微分方程专题3图论方法专题图论方法专题4第2页华中农业大学数学建模基地华中农业大学数学建模基地优化专题一一线性规划模型线性规划模型二二二二非线性规划模型非线性规划模型三三三三动态规划动态规划第3页华中农业大学数学建模基地华中农业大学数学建模基地生产计划问题生产计划问题线性规划模型线性规划模型第4页华中农业大学数学建模基地华中农业大学数学建模基地 2x1+x2 8 s.t.x1 3 x2 4 x1，x2 0 max f=5x1+2x2 求最大利润求最大利润三
2、种材料量限制三种材料量限制生产量非负生产量非负线性规划模型线性规划模型第5页华中农业大学数学建模基地华中农业大学数学建模基地运输问题运输问题线性规划模型线性规划模型第6页华中农业大学数学建模基地华中农业大学数学建模基地解：解：设设A A1,1,A A2 2调运到三个粮站大米分别为调运到三个粮站大米分别为x x1 1，x x2 2，x x3 3，x x4 4，x x5 5，x x6 6吨。吨。题设量可总到下表：题设量可总到下表：线性规划模型线性规划模型第7页华中农业大学数学建模基地华中农业大学数学建模基地结合存量限制和需量限制得数学模型结合存量限制和需量限制得数学模型：线性规划模型线性规划模型第
3、8页华中农业大学数学建模基地华中农业大学数学建模基地 m个产地个产地A1,Am联合供给联合供给n个销地个销地B1,Bn,各产各产地至各销地单位运价地至各销地单位运价(单位单位:元元/吨吨)为为cij，问怎样调运使，问怎样调运使总运费最少总运费最少?普通运输问题普通运输问题总运价总运价产量限制产量限制需量限制需量限制运量非负运量非负线性规划模型线性规划模型第9页华中农业大学数学建模基地华中农业大学数学建模基地假设假设产销平衡产销平衡:在很多实际问题中在很多实际问题中,解题思想和运输问题同出一辙解题思想和运输问题同出一辙,也就是说我们能够用运输模型处理其它问题也就是说我们能够用运输模型处理其它问题
4、.线性规划模型线性规划模型第10页华中农业大学数学建模基地华中农业大学数学建模基地 设有设有n件工作件工作B1,B2,Bn,分配给分配给n人人A1,A2,An去去做做,每人只做一件工作且每件工作只派一个人去做每人只做一件工作且每件工作只派一个人去做,设设Ai完成完成Bj工时为工时为cij,问应怎样分配才能完成全部工作问应怎样分配才能完成全部工作总工时最少总工时最少.每件工作只派每件工作只派1人人每个人只派做每个人只派做1件件变量变量xi只取只取0和和1,故建立故建立模型也称模型也称0-1规规划划.分配问题分配问题线性规划模型线性规划模型第11页华中农业大学数学建模基地华中农业大学数学建模基地选
5、址问题选址问题线性规划模型线性规划模型第12页华中农业大学数学建模基地华中农业大学数学建模基地 现要做现要做100套钢架套钢架,用长为用长为2.9m、2.1m和和1.5m元元钢各一根钢各一根,已知原料长已知原料长7.4m,问怎样下料问怎样下料,使用原材料使用原材料最省最省?分析分析:下料方式：下料方式：最省：最省：1.所用刚架根数最少；所用刚架根数最少；2.余料最少余料最少下料问题下料问题线性规划模型线性规划模型第13页华中农业大学数学建模基地华中农业大学数学建模基地v原料截成原料截成所需所需长度度根数根数下料方法所需根长2.9m211100002.1m021032101.5m10130234
6、v剩下料剩下料头 0.1 0.3 0.901.1 0.2 0.8 1.4线性规划模型线性规划模型第14页华中农业大学数学建模基地华中农业大学数学建模基地不一样不一样方法截方法截得每种得每种根长总根长总数最少数最少100例例3,4中此例变量中此例变量xi只取正整数只取正整数,故建立模型也称故建立模型也称整数规划整数规划.0-1规划是整数规划特殊情形规划是整数规划特殊情形.线性规划模型线性规划模型第15页华中农业大学数学建模基地华中农业大学数学建模基地 某企业生产某产品某企业生产某产品,最大生产能力为最大生产能力为100单位单位,每单位每单位存放费存放费2元元,预定销售量与单位成本以下预定销售量与
7、单位成本以下:月份单位成本(元)销售量1234 70 60 72 70 80 120 76 60求一生产计划求一生产计划,使使 1)满足需求满足需求;2)不超出生产能力不超出生产能力;3)成本成本(生产成本与存放费之和生产成本与存放费之和)最低最低.阶段生产问题阶段生产问题线性规划模型线性规划模型第16页华中农业大学数学建模基地华中农业大学数学建模基地 解解:假定假定1月初无库存月初无库存,4月底买完月底买完,当月生产不库当月生产不库存存,库存量无限制库存量无限制.第j+1个月库存量第j+1个月库存费共共3个月库存费个月库存费到本月总生产量到本月总生产量大于等于销售量大于等于销售量4个月总生产
8、量等个月总生产量等于总销售量于总销售量4个月总个月总生产成本生产成本线性规划模型线性规划模型第17页华中农业大学数学建模基地华中农业大学数学建模基地线性规划模型线性规划模型第18页华中农业大学数学建模基地华中农业大学数学建模基地月份单位成本(元)销售量1234 70 60 72 70 80 120 76 60线性规划模型线性规划模型第19页华中农业大学数学建模基地华中农业大学数学建模基地76827676-80-7472-747270生产月100100100100产量产量6041207060销量销量4321321需求月费用费用cij线性规划模型线性规划模型第20页华中农业大学数学建模基地华中农业
9、大学数学建模基地本题本题3个模型为整数规划模型个模型为整数规划模型.线性规划模型线性规划模型第21页华中农业大学数学建模基地华中农业大学数学建模基地线性规划模型特点线性规划模型特点v决议变量：向量决议变量：向量(x1 xn)T,决议人要考虑和控制原决议人要考虑和控制原因非负；因非负；v约束条件：线性等式或不等式；约束条件：线性等式或不等式；v目标函数：目标函数：Z=(x1 xn)线性式，求线性式，求Z极大或极小；极大或极小；线性规划模型线性规划模型第22页华中农业大学数学建模基地华中农业大学数学建模基地普通形式普通形式目标函数目标函数约约束束条条件件线性规划模型线性规划模型第23页23矩阵形式
10、矩阵形式线性规划模型线性规划模型第24页华中农业大学数学建模基地华中农业大学数学建模基地满足约束条件变量值称为满足约束条件变量值称为可行解可行解，可行解集合称为可行解集合称为可行域可行域。使目标函数到达最大（小）值可行解称使目标函数到达最大（小）值可行解称为为最优解最优解，对应目标函数值称为对应目标函数值称为最优值最优值。线性规划模型线性规划模型第25页华中农业大学数学建模基地华中农业大学数学建模基地线性规划问题性质线性规划问题性质:v百分比性 每个决议变量对目标函数以及右端项贡献与该决议变量取值成正比.v可加性 每个决议变量对目标函数以及右端项贡献与其它决议变量取值无关.v连续性 每个决议变
11、量取值都是连续.线性规划模型线性规划模型第26页华中农业大学数学建模基地华中农业大学数学建模基地应应 用用v市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制订销售计划)v生产计划制订(合理下料，配料，“生产计划、库存、劳力综合”)v库存管理(合理物资库存量，停车场大小，设备容量)v运输问题v财政、会计(预算，贷款，成本分析，投资，证券管理)v人事(人员分配，人才评价，工资和奖金确实定)v设备管理(维修计划，设备更新)v城市管理(供水，污水管理，服务系统设计、利用)线性规划模型线性规划模型第27页华中农业大学数学建模基地华中农业大学数学建模基地线性规划问题基本理论线性规划问题基本理论用图
12、解法求解线性规划问题用图解法求解线性规划问题是一簇斜率为是一簇斜率为-5/2平行平行直线族直线族斜率为斜率为-2C/2为直线与为直线与y轴交点轴交点x10 x28443第28页华中农业大学数学建模基地华中农业大学数学建模基地x240 x1834如图所表示如图所表示:显然直线向右上移动时，显然直线向右上移动时，与与y轴交点越高，从而轴交点越高，从而c/2越越大，使得目标函数值大，使得目标函数值c 越大。越大。线性规划问题基本理论线性规划问题基本理论第29页华中农业大学数学建模基地华中农业大学数学建模基地从上述几何直观可看出：从上述几何直观可看出：线性规划问题任意两个可行解线性规划问题任意两个可行
13、解联线上联线上点点都是可行解都是可行解；线性规划问题任意两个最优解线性规划问题任意两个最优解联线上联线上点点都是最优解；都是最优解；线性规划问题最优值若存在，则一定线性规划问题最优值若存在，则一定在某个顶点到达在某个顶点到达。线性规划问题基本理论线性规划问题基本理论第30页华中农业大学数学建模基地华中农业大学数学建模基地任何一个线性规划问题都能够化为标准形式，任何一个线性规划问题都能够化为标准形式，我们求解方法都是针对标准形式。我们求解方法都是针对标准形式。线性规划问题基本理论线性规划问题基本理论标准形式标准形式:第31页华中农业大学数学建模基地华中农业大学数学建模基地假如给定假如给定LP问题
14、是极大化问题问题是极大化问题,即即可化为极小化问题可化为极小化问题约束条件不变约束条件不变,其最优解是其最优解是一致一致,但目标函数值符号但目标函数值符号相反相反.则:结论结论:假如问题是求目标函数最大值假如问题是求目标函数最大值,则化为求则化为求 f 最小值最小值;1.关于目标函数线性规划问题基本理论线性规划问题基本理论第32页华中农业大学数学建模基地华中农业大学数学建模基地2.关于约束条件(1)假如给定假如给定LP有约束不等式有约束不等式线性规划问题基本理论线性规划问题基本理论第33页华中农业大学数学建模基地华中农业大学数学建模基地注意注意:新引入变量在目标函数和约束条件中系数均新引入变量
15、在目标函数和约束条件中系数均为为0.(2)假如给定假如给定LP有约束不等式有约束不等式线性规划问题基本理论线性规划问题基本理论第34页华中农业大学数学建模基地华中农业大学数学建模基地3.3.关于变量关于变量 在标准形式中在标准形式中,全部变量都有非负限制全部变量都有非负限制,假如一些假如一些变量没有非负限制变量没有非负限制,则称这些变量为则称这些变量为自由自由.两种处理方法两种处理方法:线性规划问题基本理论线性规划问题基本理论第35页华中农业大学数学建模基地华中农业大学数学建模基地线性规划问题基本理论线性规划问题基本理论第36页华中农业大学数学建模基地华中农业大学数学建模基地线性规划问题基本理
16、论线性规划问题基本理论第37页华中农业大学数学建模基地华中农业大学数学建模基地对应典式以下对应典式以下:最优值为最优值为5.非基可行解非基可行解是最优解，是最优解，线性规划问题基本理论线性规划问题基本理论第38页华中农业大学数学建模基地华中农业大学数学建模基地 1 2 3 4 5 6 7 8 96 5 4 3 2 1（2.25，3.75）1 2 3 4 5 6 7 8 96 5 4 3 2 1分枝定界法分枝定界法线性规划问题基本理论线性规划问题基本理论第39页华中农业大学数学建模基地华中农业大学数学建模基地隐枚举法过滤条件检验可行目标值可行检验过滤检验(0,0,0)0(0,0,1)55(0,1
17、,0)-2(0,1,1)3(1,0,0)3(1,0,1)88（最优）(1,1,0)1(1,1,1)6线性规划问题基本理论线性规划问题基本理论第40页华中农业大学数学建模基地华中农业大学数学建模基地连续投资连续投资10万元万元A：从第：从第1年年 到第到第4年每年初要投资，第二年末回年每年初要投资，第二年末回收本利收本利1.15B：第第3年初投资，到第年初投资，到第5年末回收年末回收1.25，最大投资，最大投资4万元万元C：第第2年初投资，到第年初投资，到第5年末回收年末回收1.40，最大投资，最大投资3万元万元D：每年初投资，每年末回收每年初投资，每年末回收1.11。求：求：5年末总资本最大。
18、年末总资本最大。练习1:连续投资第41页华中农业大学数学建模基地华中农业大学数学建模基地练习练习2某服务部门一周中天天需要不一样数目标雇员，某服务部门一周中天天需要不一样数目标雇员，周一到周四天天最少需要周一到周四天天最少需要50人，周五最少需要人，周五最少需要80人，人，周六和周日最少需要周六和周日最少需要90人，现要求应聘者需连续工人，现要求应聘者需连续工作作5天，试确定聘用方案。天，试确定聘用方案。第42页华中农业大学数学建模基地华中农业大学数学建模基地练习练习3某班准备从某班准备从5名游泳员中选择人组成接力队，名游泳员中选择人组成接力队，藏家学校藏家学校4100m混合泳接力比赛，混合泳
19、接力比赛，5名队员名队员4种泳种泳姿百米平均成绩如表，问怎样选拔队员。姿百米平均成绩如表，问怎样选拔队员。队员队员甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳10685721181101074仰泳仰泳115610611421142111蛙泳蛙泳1271064109610961238自由泳自由泳586535945721024第43页华中农业大学数学建模基地华中农业大学数学建模基地 线性模型题目线性模型题目1 生产计划问题生产计划问题某工厂计划安排生产，两种产品，已知每种单位产品利润，生产单位产品所需设备台时及A,B两种原材料消耗，现有原材料和设备台时定额如表所表示，问：）怎么安排生产使得工厂赢利最大？）产品单位
20、利润降低到1.8万元，要不要改变生产计划，假如降低到1万元呢？）产品单位利润增大到5万元，要不要改变生产计划？）假如产品，单位利润同时降低了1万元，要不要改变生产计划？产品产品产品产品最大资源量最大资源量设备设备128台时台时原材料原材料A4016kg原材料原材料B0412kg单位产品利润单位产品利润23第44页华中农业大学数学建模基地华中农业大学数学建模基地 线性模型建立线性模型建立第45页华中农业大学数学建模基地华中农业大学数学建模基地 线性模型求解线性模型求解程序编写程序编写model:title 生产计划问题;maxfmax=2*x1+3*x2;Ax1+2*x28;B4*x116;TI
21、ME4*x212;END第46页华中农业大学数学建模基地华中农业大学数学建模基地 线性模型求解线性模型求解运行结果运行结果 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万
22、元。第47页华中农业大学数学建模基地华中农业大学数学建模基地 线性模型敏感性理论线性模型敏感性理论1目标函数系数改变敏感性分析目标函数系数改变敏感性分析假如目标函数系数发生改变，将会影响目标函数 f 斜率改变，不过只要f 斜率小于等于-1/2（也就是直线l夹在l1与l2之间时），最优解都在(4,2)上取到，最优解不变，从而生产计划不会变.第48页华中农业大学数学建模基地华中农业大学数学建模基地 线性模型线性模型敏感性分析敏感性分析1要使用敏感性分析要使用敏感性分析必须要在这里选择必须要在这里选择Prices&Ranges然后然后保留保留退出退出路径：路径：LINGOOptionsGeneral
23、 Solver(通用求解程序通用求解程序)选项卡选项卡第49页华中农业大学数学建模基地华中农业大学数学建模基地 线性模型线性模型敏感性分析敏感性分析1要调出敏感性分析结果，要调出敏感性分析结果，必须必须先求解先求解后再后再在程序窗在程序窗口下口下点击点击LINGORange，第50页华中农业大学数学建模基地华中农业大学数学建模基地 线性模型线性模型敏感性分析敏感性分析1Ranges in which the basis is unchanged:Objective Coefficient Ranges Current Allowable Allowable Variable Coefficie
24、nt 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万元，在（万
25、元，在（1.5，）之间，所以不改变）之间，所以不改变生产计划。假如降低到生产计划。假如降低到1万元，不在（万元，不在（1.5，）内，要改变生产计划。在程序）内，要改变生产计划。在程序中将目标函数系数中将目标函数系数“2”改为改为“1”，可得新计划为，可得新计划为安排是生产产品安排是生产产品2单位，单位，产品产品3单位，最大盈利为单位，最大盈利为11万元万元.对问题对问题3，要改变生产计划，更改程序得新计划为生产产品，要改变生产计划，更改程序得新计划为生产产品2单位，产品单位，产品3单位，最大盈利为单位，最大盈利为19万元万元.对问题对问题4，因为两个系数同时改变了，所以只有更改程序数据，重新运
26、行，因为两个系数同时改变了，所以只有更改程序数据，重新运行得：不改变生产计划，不过最大利润降低到得：不改变生产计划，不过最大利润降低到8万元万元.第51页华中农业大学数学建模基地华中农业大学数学建模基地 线性模型敏感性理论线性模型敏感性理论2第52页华中农业大学数学建模基地华中农业大学数学建模基地 线性模型影子价格理论线性模型影子价格理论把y1,y2,y3作为三种原料定价，定价目标是在比生产产品取得更多利润前提下最小利润.在最优情况下，在最优情况下，y值就是资源值就是资源影子价格，影子价格，影子价格有意义是影子价格有意义是有范围有范围。影子价格经济含义是：在资源得到最优配影子价格经济含义是：在
27、资源得到最优配置，使总效益最大时，该资源投入量每增置，使总效益最大时，该资源投入量每增加一个单位所带来总收益增加量加一个单位所带来总收益增加量 第53页华中农业大学数学建模基地华中农业大学数学建模基地 线性模型综合讨论线性模型综合讨论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.000
28、000 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 Du
29、al Price MAXF 14.00000 1.000000 A 0.000000 1.500000 B 0.000000 0.1250000 TIME 4.000000 0.000000 第54页华中农业大学数学建模基地华中农业大学数学建模基地 线性模型题目线性模型题目21桶牛奶 3千克A1 12小时 8小时 4千克A2 或赢利24元/千克 赢利16元/千克 50桶牛奶桶牛奶 时间时间480小时小时 至多加工至多加工100千克千克A1 制订生产计划，使天天赢利最大制订生产计划，使天天赢利最大 35元可买到元可买到1桶牛奶，买吗？若买，天天最多买多少桶牛奶，买吗？若买，天天最多买多少?可聘用
30、暂时工人，付出工资最多是每小时几元可聘用暂时工人，付出工资最多是每小时几元?A1赢利增加到赢利增加到 30元元/千克，应否改变生产计划？千克，应否改变生产计划？天天：天天：加工奶制品生产计划加工奶制品生产计划第55页华中农业大学数学建模基地华中农业大学数学建模基地 线性模型建立线性模型建立x1桶牛奶生产桶牛奶生产A1 x2桶牛奶生产桶牛奶生产A2 赢利赢利 243x1 赢利赢利 164 x2 原料供给原料供给 劳动时间劳动时间 加工能力加工能力 决议变量决议变量 目标函数目标函数 天天赢利天天赢利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)第56页华中农业大学数学建模基地
31、华中农业大学数学建模基地 线性模型求解线性模型求解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桶牛奶生产桶牛奶生
32、产A1,30桶生产桶生产A2，利润，利润3360元。元。第57页华中农业大学数学建模基地华中农业大学数学建模基地 线性模型影子价格线性模型影子价格 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桶牛奶，要买吗？桶牛奶，
33、要买吗？35 0，初始可行点，初始可行点xk,初始步长初始步长k0,在在xk线性化得线性规划问题：线性化得线性规划问题：非线性规划有约束问题非线性规划有约束问题第71页华中农业大学数学建模基地华中农业大学数学建模基地 求出此线性规划问题得最优解求出此线性规划问题得最优解xk1，检验，检验是否为原问题可行解，若是转是否为原问题可行解，若是转，不然缩短，不然缩短步长转步长转；判断精度。判断精度。则取则取最优解最优解x*=xk+1,停，不然令停，不然令k=k+1转转。非线性规划有约束问题非线性规划有约束问题第72页华中农业大学数学建模基地华中农业大学数学建模基地（2）罚函数法）罚函数法转化为无约束最
34、优化问题：转化为无约束最优化问题：M为足够大正数。称为为足够大正数。称为罚因子罚因子。算法分析：算法分析：设可行域为设可行域为S，结构函数：，结构函数：非线性规划有约束问题非线性规划有约束问题第73页华中农业大学数学建模基地华中农业大学数学建模基地 求无约束问题得最优解为求无约束问题得最优解为X(M),直观看出，直观看出，只有当只有当X(M)S才可能真正取得极小值，若才可能真正取得极小值，若就就加大加大罚因子罚因子M，使，使X(M)向向S迫近，迫近，当当M时，点列时，点列非线性规划有约束问题非线性规划有约束问题第74页华中农业大学数学建模基地华中农业大学数学建模基地计算步骤计算步骤：（第：（第
35、k次迭代）次迭代）非线性规划有约束问题非线性规划有约束问题第75页华中农业大学数学建模基地华中农业大学数学建模基地 露天矿里铲位已分成矿石和岩石露天矿里铲位已分成矿石和岩石:平均铁含量不低于平均铁含量不低于25%为为矿石，不然为岩石。每个铲位矿石、岩石数量，以及矿石平均铁矿石，不然为岩石。每个铲位矿石、岩石数量，以及矿石平均铁含量（称为品位）都是已知。每个铲位至多安置一台电铲，电铲含量（称为品位）都是已知。每个铲位至多安置一台电铲，电铲平均装车时间平均装车时间5分钟。分钟。卡车在等候时所花费能量也是相当可观，标准上在安排时卡车在等候时所花费能量也是相当可观，标准上在安排时不应发生卡车等候不应发
36、生卡车等候情况。情况。矿石卸点需要铁含量要求都为矿石卸点需要铁含量要求都为29.5%1%(品位限制），搭品位限制），搭配量在一个班次（配量在一个班次（8小时）内满足品位限制即可。卸点在一个班小时）内满足品位限制即可。卸点在一个班次内不变。卡车载重量为次内不变。卡车载重量为154吨，平均时速吨，平均时速28km,平均卸车时间为平均卸车时间为3分钟。分钟。问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次别在哪些路线上各运输多少次?露天矿生产车辆安排露天矿生产车辆安排(CUMCM-B)第76页华中农业大学数学建模基
37、地华中农业大学数学建模基地 露天矿生产车辆安排露天矿生产车辆安排(CUMCM-B)第77页华中农业大学数学建模基地华中农业大学数学建模基地距离距离铲位铲位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.05
38、6.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-B)第78页华中农业大学数学建模基地华中农业大学数学建模基地与经典运输问题显著有以下不一样：与经典运输问题显著有以下不一样：1.这是运输
39、矿石与岩石两种物资问题；这是运输矿石与岩石两种物资问题；2.属于产量大于销量不平衡运输问题；属于产量大于销量不平衡运输问题；3.为了完成品位约束，矿石要搭配运输；为了完成品位约束，矿石要搭配运输；4.产地、销地都有单位时间流量限制；产地、销地都有单位时间流量限制；5.运输车辆只有一个，每次满载运输，运输车辆只有一个，每次满载运输，154吨吨/车次；车次；6.铲位数多于铲车数意味着要最优选择不多于铲位数多于铲车数意味着要最优选择不多于7个产地作为最个产地作为最终结果中产地；终结果中产地；7.最终求出各条路线上派出车辆数及安排。最终求出各条路线上派出车辆数及安排。近似处理：近似处理：先求出产位、卸
40、点每条线路上运输量先求出产位、卸点每条线路上运输量(MIP模型模型)然后求出各条路线上派出车辆数及安排然后求出各条路线上派出车辆数及安排 问题分析问题分析第79页华中农业大学数学建模基地华中农业大学数学建模基地卡车在一个班次中不应发生等候或熄火后再开启情况；卡车在一个班次中不应发生等候或熄火后再开启情况；在铲位或卸点处由两条路线以上造成冲突问题面前，在铲位或卸点处由两条路线以上造成冲突问题面前，我们认为只要平均时间能完成任务，就认为不冲突。我我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论；们不排时地进行讨论；空载与重载速度都是空载与重载速度都是28km/h，耗油相差很大；，
41、耗油相差很大；卡车可提前退出系统，等等。卡车可提前退出系统，等等。模型假设模型假设第80页华中农业大学数学建模基地华中农业大学数学建模基地(近似近似)xij：从：从i铲位到铲位到j号卸点石料运量号卸点石料运量（车）（车）单位：单位：吨；吨；cij：从：从i号铲位到号铲位到j号卸点距离号卸点距离 公里；公里；Tij:从从i号铲位到号号铲位到号j卸点路线上运行一个周期平均时间卸点路线上运行一个周期平均时间 分；分；Aij：从号铲位到号卸点最多能同时运行卡车数：从号铲位到号卸点最多能同时运行卡车数 辆；辆；Bij：从号铲位到号卸点路线上一辆车最多可运行次数：从号铲位到号卸点路线上一辆车最多可运行次数
42、 次；次；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为关闭为关闭 符号说明符号说明第81页华中农业大学数学建模基地华中农业大学数学建模基地（4）铲位储量约束（1）道路能力(卡车数)约束（2）电铲能力约束（3）卸点能力约束 模型建立模型建立
43、优化模型优化模型第82页华中农业大学数学建模基地华中农业大学数学建模基地xij为非负整数fi 为0-1整数（5）产量任务约束（8）整数约束（7）电铲数量约束（6）铁含量约束 模型建立模型建立第83页华中农业大学数学建模基地华中农业大学数学建模基地 程序编写程序编写model:title CUMCM-B-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 3
44、1 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
45、.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第84页华中农业大学数学建模基地华中农业大学数学建模基地 程序编写程序编写!目标函数目标函数;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)/2
46、8*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);第85页华中农业大学数学建模基地华中农业大学数学建模基
47、地 程序编写程序编写!道路能力约束道路能力约束;for(link(i,j):number(i,j)=lsubject(i,j);!电铲能力约束电铲能力约束;for(cai(j):cnum(j)=flag(j)*8*60/5);!电铲数量约束电铲数量约束 -added by Xie Jinxing,-09-07-added by Xie Jinxing,-09-07;sum(cai(j):flag(j)=7;!卸点能力约束卸点能力约束;for(xiexie(i):xnum(i)=8*20);!铲位产量约束铲位产量约束;for(cai(i):number(1,i)+number(2,i)+numb
48、er(5,i)=ck(i)*10000/154);for(cai(i):number(3,i)+number(4,i)=xsubject(i)*10000/154);第86页华中农业大学数学建模基地华中农业大学数学建模基地 程序编写程序编写!铁含量约束铁含量约束;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(
49、cai(j):number(5,j)*(crate(j)-28.5)=0;!关于车辆详细分配关于车辆详细分配;for(link(i,j):che(i,j)=number(i,j)/b(i,j);第87页华中农业大学数学建模基地华中农业大学数学建模基地 程序编写程序编写!各个路线所需卡车数简单加和各个路线所需卡车数简单加和;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);
50、end第88页华中农业大学数学建模基地华中农业大学数学建模基地铲位铲位1 1铲位铲位2 2铲位铲位3 3铲位铲位4 4铲位铲位5 5铲位铲位6 6铲位铲位7 7铲位铲位8 8铲位铲位9 9铲位铲位1010矿漏矿漏135411倒倒4243岩场岩场7015岩漏岩漏8143倒倒13270铲位铲位1 1铲位铲位2 2铲位铲位3 3铲位铲位4 4铲位铲位5 5铲位铲位6 6铲位铲位7 7铲位铲位8 8铲位铲位9 9铲位铲位1010矿石漏矿石漏0.8671.8620.314倒场倒场1.0771.162岩场岩场1.8920.326岩石漏岩石漏1.8411.229倒场倒场0.6840.11.489 求解结果求
