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