数学建模B题综述课件

数学建模数学建模B题题数学模型的分类数学模型的分类应用领域应用领域人口、交通、经济、生态人口、交通、经济、生态 数学方法数学方法初等数学、微分方程、规划、统计初等数学、微分方程、规划、统计 表现特性表现特性描述、描述、优化优化、预报、决策、预报、决策 建模目的建模目的了解程度了解程度白箱白箱灰箱灰箱黑箱黑箱确定和随机确定和随机静态和动态静态和动态线性和非线性线性和非线性离散离散和连续和连续怎样参加数学建模竞赛怎样参加数学建模竞赛数学建模与其说是一门技术，不如说是一门艺术数学建模与其说是一门技术，不如说是一门艺术技术大致有章可循技术大致有章可循艺术无法归纳成普遍适用的准则艺术无法归纳成普遍适用的准则想像力想像力洞察力洞察力判断力判断力 学习、分析、评价、改进别人作过的模型学习、分析、评价、改进别人作过的模型 亲自动手，认真作几个实际题目亲自动手，认真作几个实际题目n n19921992年年年年:n n()作物生长的施肥效果问题作物生长的施肥效果问题作物生长的施肥效果问题作物生长的施肥效果问题(北理工：叶其孝）北理工：叶其孝）北理工：叶其孝）北理工：叶其孝）n n (B)(B)化学试验室的实验数据分解问题（复旦：谭永基）化学试验室的实验数据分解问题（复旦：谭永基）化学试验室的实验数据分解问题（复旦：谭永基）化学试验室的实验数据分解问题（复旦：谭永基）n n19931993年年年年:n n()通讯中非线性交调的频率设计问题（北大通讯中非线性交调的频率设计问题（北大通讯中非线性交调的频率设计问题（北大通讯中非线性交调的频率设计问题（北大:谢衷洁）谢衷洁）谢衷洁）谢衷洁）n n ()足球甲级联赛排名问题（清华：蔡大用）足球甲级联赛排名问题（清华：蔡大用）足球甲级联赛排名问题（清华：蔡大用）足球甲级联赛排名问题（清华：蔡大用）n n19941994年年年年:n n()山区修建公路的设计造价问题（西电大：何大可）山区修建公路的设计造价问题（西电大：何大可）山区修建公路的设计造价问题（西电大：何大可）山区修建公路的设计造价问题（西电大：何大可）n n ()锁具的制造、销售和装箱问题（复旦锁具的制造、销售和装箱问题（复旦锁具的制造、销售和装箱问题（复旦锁具的制造、销售和装箱问题（复旦:谭永基等）谭永基等）谭永基等）谭永基等）n n19951995年年年年:(:()飞机的安全飞行管理调度问题（复旦飞机的安全飞行管理调度问题（复旦飞机的安全飞行管理调度问题（复旦飞机的安全飞行管理调度问题（复旦:谭永基谭永基谭永基谭永基等）等）等）等）n n ()天车与冶炼炉的作业调度问题（浙大天车与冶炼炉的作业调度问题（浙大天车与冶炼炉的作业调度问题（浙大天车与冶炼炉的作业调度问题（浙大:刘祥官等刘祥官等刘祥官等刘祥官等四、近几年全国大学生数学建模竞赛题四、近几年全国大学生数学建模竞赛题n n19961996年年年年:(A):(A)最优捕鱼策略问题（北师大：刘来福）最优捕鱼策略问题（北师大：刘来福）最优捕鱼策略问题（北师大：刘来福）最优捕鱼策略问题（北师大：刘来福）n n (B)(B)节水洗衣机的程序设计问题（重大：付鹂）节水洗衣机的程序设计问题（重大：付鹂）节水洗衣机的程序设计问题（重大：付鹂）节水洗衣机的程序设计问题（重大：付鹂）n n19971997年年年年:(A):(A)零件参数优化设计问题（清华：姜启源）零件参数优化设计问题（清华：姜启源）零件参数优化设计问题（清华：姜启源）零件参数优化设计问题（清华：姜启源）n n (B)(B)金刚石截断切割问题（复旦：谭永基等）金刚石截断切割问题（复旦：谭永基等）金刚石截断切割问题（复旦：谭永基等）金刚石截断切割问题（复旦：谭永基等）n n19981998年年年年:(A):(A)投资的收益和风险问题（浙大：陈淑平）投资的收益和风险问题（浙大：陈淑平）投资的收益和风险问题（浙大：陈淑平）投资的收益和风险问题（浙大：陈淑平）n n (B)(B)灾情的巡视路线问题（上海海运学院灾情的巡视路线问题（上海海运学院灾情的巡视路线问题（上海海运学院灾情的巡视路线问题（上海海运学院:丁颂康）丁颂康）丁颂康）丁颂康）n n19991999年年年年:(A):(A)自动化机床控制管理问题（北大：孙山泽）自动化机床控制管理问题（北大：孙山泽）自动化机床控制管理问题（北大：孙山泽）自动化机床控制管理问题（北大：孙山泽）n n (B)(B)地质堪探钻井布局问题（郑州大学：林诒勋）地质堪探钻井布局问题（郑州大学：林诒勋）地质堪探钻井布局问题（郑州大学：林诒勋）地质堪探钻井布局问题（郑州大学：林诒勋）n n (C)(C)煤矸石堆积问题（太原理工大学：贾晓峰煤矸石堆积问题（太原理工大学：贾晓峰煤矸石堆积问题（太原理工大学：贾晓峰煤矸石堆积问题（太原理工大学：贾晓峰n n20002000年年年年:(A)DNA:(A)DNA序列的分类问题（北工大：孟大志）序列的分类问题（北工大：孟大志）序列的分类问题（北工大：孟大志）序列的分类问题（北工大：孟大志）n n (B)(B)钢管的订购和运输问题（武大：费甫生）钢管的订购和运输问题（武大：费甫生）钢管的订购和运输问题（武大：费甫生）钢管的订购和运输问题（武大：费甫生）n n (C)(C)飞越北极问题（复旦大学：谭永基）飞越北极问题（复旦大学：谭永基）飞越北极问题（复旦大学：谭永基）飞越北极问题（复旦大学：谭永基）n n (D)(D)空洞探测问题（东北电力学院：关信）空洞探测问题（东北电力学院：关信）空洞探测问题（东北电力学院：关信）空洞探测问题（东北电力学院：关信）n n20012001年年年年:(A):(A)三维血管的重建问题（浙大：汪国昭）三维血管的重建问题（浙大：汪国昭）三维血管的重建问题（浙大：汪国昭）三维血管的重建问题（浙大：汪国昭）n n (B)(B)公交车的优化调度问题（清华：谭泽光）公交车的优化调度问题（清华：谭泽光）公交车的优化调度问题（清华：谭泽光）公交车的优化调度问题（清华：谭泽光）n n (C)(C)基金使用计划问题（东南大学：陈恩水）基金使用计划问题（东南大学：陈恩水）基金使用计划问题（东南大学：陈恩水）基金使用计划问题（东南大学：陈恩水）n n20022002年年年年:(A):(A)汽车车灯的优化设计问题（复旦汽车车灯的优化设计问题（复旦汽车车灯的优化设计问题（复旦汽车车灯的优化设计问题（复旦:谭永基等）谭永基等）谭永基等）谭永基等）n n (B)(B)彩票中的数学问题（信息工程大学：韩中庚）彩票中的数学问题（信息工程大学：韩中庚）彩票中的数学问题（信息工程大学：韩中庚）彩票中的数学问题（信息工程大学：韩中庚）n n (D)(D)球队的赛程安排问题（清华：姜启源球队的赛程安排问题（清华：姜启源球队的赛程安排问题（清华：姜启源球队的赛程安排问题（清华：姜启源n n20032003年年年年:(A)SARS:(A)SARS的传播问题（集体）的传播问题（集体）的传播问题（集体）的传播问题（集体）n n (B)(B)露天矿生产的车辆安排问题（吉林大学：方沛辰）露天矿生产的车辆安排问题（吉林大学：方沛辰）露天矿生产的车辆安排问题（吉林大学：方沛辰）露天矿生产的车辆安排问题（吉林大学：方沛辰）n n (D)(D)抢渡长江问题（华中农业大学：殷建肃）抢渡长江问题（华中农业大学：殷建肃）抢渡长江问题（华中农业大学：殷建肃）抢渡长江问题（华中农业大学：殷建肃）n n20042004年年年年:(A):(A)奥运会临时超市网点设计问题奥运会临时超市网点设计问题奥运会临时超市网点设计问题奥运会临时超市网点设计问题(北工大：孟北工大：孟北工大：孟北工大：孟大志大志大志大志)n n (B)(B)电力市场的输电阻塞管理问题电力市场的输电阻塞管理问题电力市场的输电阻塞管理问题电力市场的输电阻塞管理问题(浙大浙大浙大浙大:刘康生）刘康生）刘康生）刘康生）n n (C)(C)酒后开车问题（清华大学：姜启源）酒后开车问题（清华大学：姜启源）酒后开车问题（清华大学：姜启源）酒后开车问题（清华大学：姜启源）n n (D)(D)公务员的招聘问题（信息工程大学：韩中庚）公务员的招聘问题（信息工程大学：韩中庚）公务员的招聘问题（信息工程大学：韩中庚）公务员的招聘问题（信息工程大学：韩中庚）n n20052005年年年年:(A):(A)长江水质的评价与预测问题（信息工大长江水质的评价与预测问题（信息工大长江水质的评价与预测问题（信息工大长江水质的评价与预测问题（信息工大:韩韩韩韩中庚）中庚）中庚）中庚）n n (B)DVD(B)DVD在线租赁问题（清华大学：谢金星等）在线租赁问题（清华大学：谢金星等）在线租赁问题（清华大学：谢金星等）在线租赁问题（清华大学：谢金星等）n n (C)(C)雨量预报方法的评价问题（复旦大学：谭永基）雨量预报方法的评价问题（复旦大学：谭永基）雨量预报方法的评价问题（复旦大学：谭永基）雨量预报方法的评价问题（复旦大学：谭永基）n n (D)DVD(D)DVD在线租赁问题在线租赁问题在线租赁问题在线租赁问题n n2006A2006A出版社的资源配置出版社的资源配置出版社的资源配置出版社的资源配置 (北京工业大学北京工业大学北京工业大学北京工业大学孟大志孟大志孟大志孟大志)n n2006B 2006B 艾滋病疗法的评价及疗效的预测艾滋病疗法的评价及疗效的预测艾滋病疗法的评价及疗效的预测艾滋病疗法的评价及疗效的预测 (天津大学边馥萍天津大学边馥萍天津大学边馥萍天津大学边馥萍)n n2006C 2006C 易拉罐形状和尺寸最优设计模型的评价易拉罐形状和尺寸最优设计模型的评价易拉罐形状和尺寸最优设计模型的评价易拉罐形状和尺寸最优设计模型的评价 (北京理工大学叶其孝北京理工大学叶其孝北京理工大学叶其孝北京理工大学叶其孝)n n2006D2006D煤矿瓦斯和煤尘的监测与控制煤矿瓦斯和煤尘的监测与控制煤矿瓦斯和煤尘的监测与控制煤矿瓦斯和煤尘的监测与控制 (解放军信息工程大学韩中庚解放军信息工程大学韩中庚解放军信息工程大学韩中庚解放军信息工程大学韩中庚)n n2007A2007A中国人口增长预测中国人口增长预测中国人口增长预测中国人口增长预测 n n2007B2007B乘公交，看奥运乘公交，看奥运乘公交，看奥运乘公交，看奥运n n20082008A A数码相机定位数码相机定位n n2008B2008B高等教育学费标准探讨高等教育学费标准探讨B题题 露天矿生产的车辆安排露天矿生产的车辆安排n n钢铁工业是国家工业的基础之一，铁矿是钢铁工业的主要钢铁工业是国家工业的基础之一，铁矿是钢铁工业的主要原料基地。许多现代化铁矿是露天开采的，它的生产主要原料基地。许多现代化铁矿是露天开采的，它的生产主要是由电动铲车（以下简称电铲）装车、电动轮自卸卡车是由电动铲车（以下简称电铲）装车、电动轮自卸卡车（以下简称卡车）运输来完成。提高这些大型设备的利用（以下简称卡车）运输来完成。提高这些大型设备的利用率是增加露天矿经济效益的首要任务。率是增加露天矿经济效益的首要任务。n n露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，每个铲位已预先根据铁含量将石料分成矿石和岩石。一般每个铲位已预先根据铁含量将石料分成矿石和岩石。一般来说，平均铁含量不低于来说，平均铁含量不低于25%25%的为矿石，否则为岩石。每的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多能安置一台电铲，电铲品位）都是已知的。每个铲位至多能安置一台电铲，电铲的平均装车时间为的平均装车时间为5 5分钟。分钟。n n卸货地点（以下简称卸点）有卸矿石的矿石漏、2个铁路倒装场（以下简称倒装场）和卸岩石的岩石漏、岩场等，每个卸点都有各自的产量要求。从保护国家资源的角度及矿山的经济效益考虑，应该尽量把矿石按矿石卸点需要的铁含量（假设要求都为29.5%1%，称为品位限制）搭配起来送到卸点，搭配的量在一个班次（8小时）内满足品位限制即可。从长远看，卸点可以移动，但一个班次内不变。卡车的平均卸车时间为3分钟。n n所用卡车载重量为所用卡车载重量为154154吨，平均时速吨，平均时速2828。卡车的耗。卡车的耗油量很大，每个班次每台车消耗近油量很大，每个班次每台车消耗近1 1吨柴油。发动吨柴油。发动机点火时需要消耗相当多的电瓶能量，故一个班机点火时需要消耗相当多的电瓶能量，故一个班次中只在开始工作时点火一次。卡车在等待时所次中只在开始工作时点火一次。卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。电铲和卸点都不能同时应发生卡车等待的情况。电铲和卸点都不能同时为两辆及两辆以上卡车服务。卡车每次都是满载为两辆及两辆以上卡车服务。卡车每次都是满载运输。每个铲位到每个卸点的道路都是专用的宽运输。每个铲位到每个卸点的道路都是专用的宽6060的双向车道，不会出现堵车现象，每段道路的的双向车道，不会出现堵车现象，每段道路的里程都是已知的。里程都是已知的。n n一个班次的生产计划应该包含以下内容：出动几台电铲，一个班次的生产计划应该包含以下内容：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次（因为随机因素影响，装卸时间与运输时间都运输多少次（因为随机因素影响，装卸时间与运输时间都不精确，所以排时计划无效，只求出各条路线上的卡车数不精确，所以排时计划无效，只求出各条路线上的卡车数及安排即可）。一个合格的计划要在卡车不等待条件下满及安排即可）。一个合格的计划要在卡车不等待条件下满足产量和质量（品位）要求，而一个好的计划还应该考虑足产量和质量（品位）要求，而一个好的计划还应该考虑下面两条原则之一：下面两条原则之一：n n1.1.总运量（吨公里）最小，同时出动最少的卡车，从而运总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小；输成本最小；n n2.2.利用现有车辆运输，获得最大的产量（岩石产量优先；利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。在产量相同的情况下，取总运量最小的解）。n n请你就两条原则分别建立数学模型，并给出一个请你就两条原则分别建立数学模型，并给出一个班次生产计划的快速算法。针对下面的实例，给班次生产计划的快速算法。针对下面的实例，给出具体的生产计划、相应的总运量及岩石和矿石出具体的生产计划、相应的总运量及岩石和矿石产量。产量。n n某露天矿有铲位某露天矿有铲位1010个，卸点个，卸点5 5个，现有铲车个，现有铲车7 7台，台，卡车卡车2020辆。各卸点一个班次的产量要求：矿石漏辆。各卸点一个班次的产量要求：矿石漏1.21.2万吨、倒装场万吨、倒装场1.31.3万吨、倒装场万吨、倒装场1.31.3万吨、岩万吨、岩石漏石漏1.91.9万吨、岩场万吨、岩场1.31.3万吨。万吨。n n铲位和卸点位置的二维示意图如下，各铲位和各铲位和卸点位置的二维示意图如下，各铲位和各卸点之间的距离（公里）如下表：卸点之间的距离（公里）如下表：问题分析：n n本题目与典型的运输问题明显有以下不同：本题目与典型的运输问题明显有以下不同：n n运输矿石与岩石两种物资；运输矿石与岩石两种物资；n n产量大于销量的不平衡运输；产量大于销量的不平衡运输；n n在品位约束下矿石要搭配运输；在品位约束下矿石要搭配运输；n n产地、销地均有单位时间的流量限制；产地、销地均有单位时间的流量限制；n n运输车辆每次都是满载，运输车辆每次都是满载，154154吨吨/车次；车次；n n铲位数多于铲车数意味着最优的选择不多于铲位数多于铲车数意味着最优的选择不多于7 7个产个产地；地；n n最后求出各条路线上的派出车辆数及安排。最后求出各条路线上的派出车辆数及安排。n n运输问题对应着线性规划，以上第运输问题对应着线性规划，以上第1 1、2 2、3 3、4 4条可通过变条可通过变量设计、调整约束条件实现；第量设计、调整约束条件实现；第5 5条使其变为整数线性规条使其变为整数线性规划；第划；第6 6条用线性模型实现的一种办法，是从个整数规划条用线性模型实现的一种办法，是从个整数规划中取最优的即得到最佳物流；对第中取最优的即得到最佳物流；对第7 7条由最佳物流算出各条由最佳物流算出各条路线上的最少派出车辆数（整数），再给出具体安排即条路线上的最少派出车辆数（整数），再给出具体安排即完成全部计算。完成全部计算。n n对于这个实际问题，要求快速算法，计算含对于这个实际问题，要求快速算法，计算含5050个变量的整个变量的整数规划比较困难。另外，这是一个二层规划，第二层是组数规划比较困难。另外，这是一个二层规划，第二层是组合优化，如果求最优解计算量较大，现成的各种算法都无合优化，如果求最优解计算量较大，现成的各种算法都无能为力。于是问题变为找一个寻求近优解的近似解法，例能为力。于是问题变为找一个寻求近优解的近似解法，例如可用启发式方法求解。如可用启发式方法求解。n n调用调用120120次整数规划可用三种方法避免：（次整数规划可用三种方法避免：（1 1）先）先不考虑电铲数量约束运行整数线性规划，再对解不考虑电铲数量约束运行整数线性规划，再对解中运量最少的几个铲位进行筛选；（中运量最少的几个铲位进行筛选；（2 2）在整数线）在整数线性规划的铲车约束中调用函数来实现；（性规划的铲车约束中调用函数来实现；（3 3）增加）增加1010个个0 01 1变量来标志各个铲位是否有产量。变量来标志各个铲位是否有产量。n n这是一个多目标规划，第一问的目标有两层：第这是一个多目标规划，第一问的目标有两层：第一层是总运量（吨公里）最小，第二层是出动卡一层是总运量（吨公里）最小，第二层是出动卡车数最少，从而实现运输成本最小。第二问的目车数最少，从而实现运输成本最小。第二问的目标有：岩石产量最大；矿石产量最大；运量最小，标有：岩石产量最大；矿石产量最大；运量最小，三者的重要性应按此序。三者的重要性应按此序。n n合理的假设主要有：n n卡车在一个班次中不应发生等待或熄火后再启动的情况；n n在铲位或卸点处因两条路线（及以上）造成的冲突时，只要平均时间能完成任务即可，不进行排时讨论；n n空载与重载的速度都是28km/h，耗油相差却很大，因此总运量只考虑重载运量；n n卡车可提前退出系统。符号 n nxijxij 从从i i号铲位到号铲位到j j号卸点的石料运量号卸点的石料运量 单位单位 吨；吨；n ncijcij 从从i i号铲位到号铲位到j j号卸点的距离号卸点的距离 公里；公里；n nTijTij 从从i i号铲位到号铲位到j j号卸点路线上运行一个周期平均所需时号卸点路线上运行一个周期平均所需时间间 分；分；n nAijAij 从从i i号铲位到号铲位到j j号卸点最多能同时运行的卡车数号卸点最多能同时运行的卡车数 辆；辆；n nBijBij 从从i i号铲位到号铲位到j j号卸点路线上一辆车最多可以运行的次号卸点路线上一辆车最多可以运行的次数数 次；次；n npi ipi i号铲位的矿石铁含量。号铲位的矿石铁含量。%n np p=(30,28,29,32,31,33,32,31,33,31)=(30,28,29,32,31,33,32,31,33,31)n nqj j号卸点任务需求 吨n nq=(1.2,1.3,1.3,1.9,1.3)*10000 n n cki i号铲位的铁矿石储量 万吨n n cyi i号铲位的岩石储量 万吨n nfi:描述第i号铲位是否使用的0-1开关变量，取1为使用；取0为关闭。模型建立、算法设计与模型求解：问题一、求运输成本最小的生产计划n n一以总运量最小为目标函数求解最佳物流一以总运量最小为目标函数求解最佳物流-第第一层规划一层规划n n（1 1）道路能力约束：一个电铲（卸点）不能同时）道路能力约束：一个电铲（卸点）不能同时为两辆卡车服务，一条路线上最多能同时运行的为两辆卡车服务，一条路线上最多能同时运行的卡车数是有限制的。卡车从卡车数是有限制的。卡车从i i号铲位到号铲位到j j号卸点运行号卸点运行一个周期平均所需时间为（分钟）。由于装车时一个周期平均所需时间为（分钟）。由于装车时间间5 5分钟大于卸车时间分钟大于卸车时间3 3分钟，所以这条路线上在分钟，所以这条路线上在卡车不等待条件下最多能同时运行的卡车数为：；卡车不等待条件下最多能同时运行的卡车数为：；其中最后开始发车的一辆卡车一个班次中其中最后开始发车的一辆卡车一个班次中n n在这条路线上最多可以运行的次数为（其他卡车在这条路线上最多可以运行的次数为（其他卡车可能比此数多可能比此数多1 1次），这里是开始装车时最后一辆次），这里是开始装车时最后一辆车的延时时间。一个班次中这条固定路线上最多车的延时时间。一个班次中这条固定路线上最多可能运行的总车次可能运行的总车次大约大约大约大约为：，总吨数。为：，总吨数。n n（2 2）电铲能力约束：一台电铲不能同时为两辆卡）电铲能力约束：一台电铲不能同时为两辆卡车服务，所以一台电铲在一个班次中的最大可能车服务，所以一台电铲在一个班次中的最大可能产量为产量为860/5154860/5154（吨）。（吨）。n n（3 3）卸点能力约束：卸点的最大吞吐量为每小时）卸点能力约束：卸点的最大吞吐量为每小时60/3=2060/3=20车次，于是一个卸点在一个班次中的最大车次，于是一个卸点在一个班次中的最大可能产量为可能产量为820154820154（吨）。（吨）。n n（4 4）铲位储量约束：铲位的矿石和岩石产量都不）铲位储量约束：铲位的矿石和岩石产量都不能超过相应的储藏量。能超过相应的储藏量。n n（5 5）产量任务约束：各卸点的产量不小于该卸点）产量任务约束：各卸点的产量不小于该卸点的任务要求。的任务要求。n n（6 6）铁含量约束：各矿石卸点的平均品位要求都）铁含量约束：各矿石卸点的平均品位要求都在指定的范围内。在指定的范围内。n n （7 7）电铲数量约束：电铲数量约束无法用普通）电铲数量约束：电铲数量约束无法用普通不等式表达，可以引入不等式表达，可以引入1010个个0101变量来标志各个变量来标志各个铲位是否有铲位是否有n n（8）整数约束：当把问题作为整数规划模型时，流量xij除以154为非负整数。n n（9）卡车数量约束：不超过20辆。优化模型优化模型（1）道路能力道路能力(卡车数卡车数)约束约束（2）电铲能力约束（3）卸点能力约束（4）铲位储量约束（5）产量任务约束（6）铁含量约束（7）电铲数量约束（8）整数约束.xij为非负数二对最佳物流的结果进行派车二对最佳物流的结果进行派车-第二层规划第二层规划n n这是组合优化中的一维背包模型，针对快速算法的要求，用启发式方法求近优解。n n先用最佳物流修正Bij,确定卡车一个班次中在这条路线上实际最多可以运行的次数。然后在以目标为出动总卡车数最少的各路线派车中，把各路线需要的卡车数分成整数部分和小数部分，进而可以分配任务让辆车在i到j路线上，每辆往返运输Bij次。为n n了最后实现第二层规划的目标，只需联合处理所有的时把这些小数组合成最少的整数卡车数。所需总卡车数的下界显然是。如果某种派车方案恰好派出Y0辆车实现了所有的xij，则其即为第二层目标意义下近优解的最优方案。但由于有联合派车而总公里数不一定最小,故不一定为全局意义下的最佳方案。n n出动卡车数最少，意味着出动的卡车利用率要最出动卡车数最少，意味着出动的卡车利用率要最大。容易出现的一辆卡车为两个以上路线服务的大。容易出现的一辆卡车为两个以上路线服务的联合派车，可分为两种情况：联合派车，可分为两种情况：有共同铲位（或有共同铲位（或卸点）的联合派车（卸点）的联合派车（V V字形或更复杂）；字形或更复杂）；不同不同铲位且不同卸点之间的联合派车（铲位且不同卸点之间的联合派车（Z Z字形或四边形字形或四边形或更复杂）。派车方案的空载路线应尽量安排在或更复杂）。派车方案的空载路线应尽量安排在第一层规划的最佳物流路线内，即使有的超出也第一层规划的最佳物流路线内，即使有的超出也要保证超出的路程总和最小，这样才能实现重载要保证超出的路程总和最小，这样才能实现重载路程最小且使卡车空载路程也最小。而情况路程最小且使卡车空载路程也最小。而情况的的路路n n线不会超出第一层规划的最佳物流路线。只有情况才会有一部分不在第一层规划的最佳物流路线内。n n问题：各路线都是小数的需车数，如何组合使总卡车数最少且如果出现情况时空载超出部分总和尽量小。n n如果存在情况，则整体考虑情况形路线需要的卡车数相加的和,先确定和的整数部分的车数并对这些车分配任务（任务的形式为在哪条路线上运几趟，再在哪条路线上运几趟，等等）。之后已无情况了，再对各个小数进行组合相加试探，在所有动用卡车数最少的情况中，选择超出第一层最佳物流路线的总和最小的，即为最后派车方案 n n，再对这些车分配任务。由于属情况的为多数，故后面的组合搜索比较简单，常常只有一两个任务属情况。n n根据最后派车方案，回代计算出各车辆在各路线的运输次数。由于整数部分已分配完运输次数,小数乘以对应路线上的Bij取整计算出小数部分对应的具体运输次数.n n进一步计算出实际总运量与矿石和岩石的产量。三、求解过程三、求解过程 n n第一层规划n n求解前面给出的整数规划模型可计算出最优值为总运量85628.62吨公里。n n最佳物流相对应的各个路线上的最佳运输车次：计算结果（LINGO软件）铲铲位位1 1铲铲位位2 2铲铲位位3 3铲铲位位4 4铲铲位位5 5铲铲位位6 6铲铲位位7 7铲铲位位8 8铲铲位位9 9铲铲位位1010矿矿漏漏131313135454545411111111倒倒4242424243434343岩岩场场7070707015151515岩漏岩漏8181818143434343倒倒131313132 2 2 270707070铲铲位位1 1铲铲位位2 2铲铲位位3 3铲铲位位4 4铲铲位位5 5铲铲位位6 6铲铲位位7 7铲铲位位8 8铲铲位位9 9铲铲位位1010矿矿石漏石漏0.8670.8671.8621.8620.3140.314倒倒场场1.0771.0771.1621.162岩岩场场1.8921.8920.3260.326岩石漏岩石漏1.8411.8411.2291.229倒倒场场0.6840.6840.10.11.4891.489cumcm2003b1.lg4计算结果（派车）铲铲位位1 1铲铲位位2 2铲铲位位3 3铲铲位位4 4铲铲位位5 5铲铲位位6 6铲铲位位7 7铲铲位位8 8铲铲位位9 9铲铲位位1010矿矿石漏石漏1 1(2(29)9)倒倒场场1 1(3(39)9)1 1(3(37)7)岩岩场场1 1(3(37)7)岩石漏岩石漏1(44)1(44)1 1(3(35)5)倒倒场场1 1(4(47)7)结论：结论：铲位铲位1、2、3、4、8、9、10处各放置一台电铲。处各放置一台电铲。一共使用了一共使用了13辆卡车；总运量为辆卡车；总运量为85628.62吨公里；吨公里；岩石产量为岩石产量为32186吨；矿石产量为吨；矿石产量为38192吨。吨。此外：此外：6辆联合派车（方案略）辆联合派车（方案略）最大化产量结论：结论：（略）（略）目标函数变化目标函数变化此外：车辆数量（此外：车辆数量（20辆）限制（其实上面的模型也辆）限制（其实上面的模型也应该有）应该有）A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7铁路运价表里程里程300300301301350350351351400400401401450450451451500500 运价运价20202323262629293232 钢管运输问题钢管运输问题（CUMCM-CUMCM-2000B)2000B)n n常用解法常用解法:二次规划二次规划n n先计算最小运费矩阵先计算最小运费矩阵两种运输方式（铁路公路）混合最短路问题两种运输方式（铁路公路）混合最短路问题两种运输方式（铁路公路）混合最短路问题两种运输方式（铁路公路）混合最短路问题是普通最短路问题的变种，需要自己设计算法是普通最短路问题的变种，需要自己设计算法是普通最短路问题的变种，需要自己设计算法是普通最短路问题的变种，需要自己设计算法 钢管运输问题钢管运输问题（CUMCM-CUMCM-2000B)2000B)f fi i表示钢厂表示钢厂表示钢厂表示钢厂i i是否使用；是否使用；是否使用；是否使用；x xij ij是从钢厂是从钢厂是从钢厂是从钢厂i i运到节点运到节点运到节点运到节点j j的钢管量的钢管量的钢管量的钢管量y yj j是从节点是从节点是从节点是从节点j j向左铺设的钢管量；向左铺设的钢管量；向左铺设的钢管量；向左铺设的钢管量；z zj j是向右铺设的钢管量是向右铺设的钢管量是向右铺设的钢管量是向右铺设的钢管量 钢管运输问题钢管运输问题（CUMCM-CUMCM-2000B)2000B)LINDO/LINGO得到的结果比得到的结果比matlab得到的好得到的好cumcm2000b.lg4其他优化赛题飞行管理问题飞行管理问题空洞探测问题空洞探测问题钻井布局问题钻井布局问题抢渡长江问题抢渡长江问题等等等等