数学建模竞赛中的部分优化问题

1、数学建模竞赛中的部分优化问题最短路问题定义 是由 点出发至终点 的最短路程，由最优化原理可得这是一个函数方程，用LINGO可以方便的解决。最短路问题最短路问题LINGO源程序(shorttest.lg4) 计算的部分结果为： Feasible solution found at iteration: 0 Variable Value N 10.00000 F( 1) 17.00000 F( 2) 11.00000 F( 3) 15.00000 F( 4) 8.000000 F( 5) 13.00000 F( 6) 11.00000 F( 7) 5.000000 F( 8) 7.000000 F

2、( 9) 9.000000 F( 10) 0.000000 P( 1, 2) 1.000000 P( 1, 3) 0.000000 P( 2, 4) 1.000000 P( 2, 5) 0.000000 P( 2, 6) 0.000000 P( 3, 4) 1.000000 P( 3, 5) 0.000000 P( 3, 6) 0.000000 P( 4, 7) 0.000000 P( 4, 8) 1.000000 P( 5, 7) 1.000000 P( 5, 8) 0.000000 P( 5, 9) 0.000000 P( 6, 8) 1.000000 P( 6, 9) 0.000000

3、P( 7, 10) 1.000000 P( 8, 10) 1.000000 P( 9, 10) 1.000000在约10,000米高空的某边长160公里的正方形区域内, 经常有若干架飞机作水平飞行。区域内每架飞机的位置和速度均由计算机记录其数据，以便进行飞行管理。当一架欲进入该区域的飞机到达区域边缘, 记录其数据后，要立即计算并判断是否会与区域内的飞机发生碰撞。如果会碰撞，则应计算如何调整各架(包括新进入的)飞机飞行方向角，以避免碰撞。现假定条件如下: 1)不碰撞的标准为任意两架飞机的距离大于8公里; 2) 飞机飞行方向角调整的幅度不应超过30度; 3) 所有飞机飞行速度均为每小时800公里;

4、 4) 进入该区域的飞机在到达区域边缘时, 与区域内飞机的距离应在60公里以上; 5) 最多需考虑6架飞机; 6) 不必考虑飞机离开此区域后的状况。请你对这个避免碰撞的飞行管理问题建立数学模型，列出计算步骤，对以下数据进行计算(方向角误差不超过0.01度)，要求飞机飞行方向角调整的幅度尽量小。设该区域4个顶点的座标为(0,0)，(160,0)，(160,160)，(0,160)。记录数据为:飞行管理问题飞机编号横座标x纵座标y方向角(度) 1150140243285852363150155220.54145501595130150230新进入0 052 注: 方向角指飞行方向与x轴正向的夹角。

5、试根据实际应用背景对你的模型进行评价与推广。 飞行管理问题模型及求解模型的建立飞行管理问题飞行管理问题飞行管理问题飞行管理问题模型求解ij=max，这实际上强化了问题的要求，即考虑了有些飞机可能已经飞出区域，但仍不允许两架飞机的距离小于Km这个简化的模型可以输入LINGO软件演示：CUMCM-1995Aa.lg4 结果：CUMCM-1995A-a.txt飞行管理问题问题1. 如何下料最节省 ? 钢管下料 问题2. 客户增加需求：原料钢管:每根19米 4米50根 6米20根 8米15根 客户需求节省的标准是什么？由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过3种。如何下料最

6、节省？5米10根 按照客户需要在一根原料钢管上安排切割的一种组合。 切割模式余料1米 4米1根 6米1根 8米1根 余料3米 4米1根 6米1根 6米1根 合理切割模式的余料应小于客户需要钢管的最小尺寸余料3米 8米1根 8米1根 钢管下料 为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？合理切割模式2. 所用原料钢管总根数最少 模式4米钢管根数6米钢管根数8米钢管根数余料(米)14003231013201341203511116030170023钢管下料问题1 两种标准1. 原料钢管剩余总余量最小xi 按第i 种模式切割的原料钢管根数(i=1,2,7) 约束满足需求

7、 决策变量 目标1（总余量）按模式2切割12根,按模式5切割15根，余料27米 模式4米根数6米根数8米根数余料14003231013201341203511116030170023需求502015最优解：x2=12, x5=15, 其余为0；最优值：27整数约束： xi 为整数当余料没有用处时，通常以总根数最少为目标 目标2（总根数）钢管下料问题1 约束条件不变 最优解：x2=15, x5=5, x7=5, 其余为0；最优值：25。xi 为整数按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米 虽余料增加8米，但减少了2根 与目标1的结果“共切割27根，余料27米”

8、 相比 钢管下料问题2对大规模问题，用模型的约束条件界定合理模式增加一种需求：5米10根；切割模式不超过3种。现有4种需求：4米50根，5米10根，6米20根，8米15根，用枚举法确定合理切割模式，过于复杂。决策变量 xi 按第i 种模式切割的原料钢管根数(i=1,2,3) r1i, r2i, r3i, r4i 第i 种切割模式下，每根原料钢管生产4米、5米、6米和8米长的钢管的数量满足需求模式合理：每根余料不超过3米整数非线性规划模型钢管下料问题2目标函数（总根数）约束条件整数约束： xi ,r1i, r2i, r3i, r4i (i=1,2,3)为整数增加约束，缩小可行域，便于求解原料钢管

9、总根数下界： 特殊生产计划：对每根原料钢管模式1：切割成4根4米钢管，需13根；模式2：切割成1根5米和2根6米钢管，需10根；模式3：切割成2根8米钢管，需8根。原料钢管总根数上界：31 模式排列顺序可任定 钢管下料问题2需求：4米50根，5米10根，6米20根，8米15根每根原料钢管长19米LINGO求解整数非线性规划模型Local optimal solution found at iteration: 12211 Objective value: 28.00000Variable Value Reduced CostX1 10.00000 0.000000X2 10.00000 2.0

10、00000X3 8.000000 1.000000R11 3.000000 0.000000R12 2.000000 0.000000R13 0.000000 0.000000R21 0.000000 0.000000R22 1.000000 0.000000 R23 0.000000 0.000000 R31 1.000000 0.000000 R32 1.000000 0.000000 R33 0.000000 0.000000 R41 0.000000 0.000000 R42 0.000000 0.000000 R43 2.000000 0.000000 模式1：每根原料钢管切割成2根

11、4米、1根5米和1根6米钢管，共10根；(书上模式1与模式2相反了)模式2：每根原料钢管切割成3根4米和1根6米钢管，共10根；模式3：每根原料钢管切割成2根8米钢管，共8根。原料钢管总根数为28根。演示cut02a.lg4； cut02b.lg4露天矿里铲位已分成矿石和岩石: 平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多安置一台电铲，电铲平均装车时间5分钟卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。 露天矿生产的车辆安排(CUMCM-2003B) 矿石卸点需要的铁含量要求都为2

12、9.5%1%(品位限制），搭配量在一个班次（8小时）内满足品位限制即可。卸点在一个班次内不变。卡车载重量为154吨，平均时速28km,平均卸车时间为3分钟。问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次 ?平面示意图问题数据 距离铲位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.7

13、61.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%问题分析 与典型的运输问题明显有以下不同：这是运输矿石与岩石两种物资的问题；属于产量大于销量的不平衡运输问题；为了完成品位约束，矿石要搭配运输；产地、销地均有单位时间的流量限制；运输车辆只有

14、一种，每次满载运输，154吨/车次；铲位数多于铲车数意味着要最优的选择不多于7个产地作为最后结果中的产地；最后求出各条路线上的派出车辆数及安排。近似处理：先求出产位、卸点每条线路上的运输量(MIP模型)然后求出各条路线上的派出车辆数及安排模型假设卡车在一个班次中不应发生等待或熄火后再启动的情况；在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论；空载与重载的速度都是28km/h，耗油相差很大；卡车可提前退出系统，等等。如理解为严格不等待，难以用数学规划模型来解 个别参数队找到了可行解 （略）符号xij ：从i铲位到j号卸点的石料运

15、量 （车） 单位： 吨；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为关闭。(近似)优化模型（1）道路能力(

16、卡车数)约束（2）电铲能力约束（3）卸点能力约束（4）铲位储量约束（5）产量任务约束（6）铁含量约束（7）电铲数量约束（8）整数约束 .xij为非负整数fi 为0-1整数计算结果（LINGO软件）铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿漏135411倒4243岩场7015岩漏8143倒13270铲位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.489cumcm2003b1.lg4计算结果（派车）铲位1铲位2铲位3铲位4铲位5铲

17、位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吨。此外：6辆联合派车（方案略）最大化产量结论：（略）目标函数变化此外：车辆数量（20辆）限制（其实上面的模型也应该有） 钢管运输问题（CUMCM-2000B) 要铺设一条的输送天然气的主管道, 如图所示(见下页)。经筛选后可以生产这种主管道钢管的钢厂有表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公

18、路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。 为方便计，1km主管道钢管称为1单位钢管。图中粗线表示铁路，单细线A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7铁路运价表里程3003013503514004014

19、50451500运价2023262932 钢管运输问题（CUMCM-2000B) 钢管运输问题（CUMCM-2000B)一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大个单位，钢管出厂销价1单位钢管为万元，如下表：数量为1234567800800100020002000200030001601551551601551501601单位钢管的铁路运价如下表： 钢管运输问题（CUMCM-2000B)里程(km)300301350351400401450451500运价(万元)2023262932里程(km)50160060170070180080190090

20、01000运价(万元)37445055601000km以上每增加1至100km运价增加5万元。 钢管运输问题（CUMCM-2000B)公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。(1)请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。(2)请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。(3)如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。 钢管运输问题（CUMCM-2000B)常用解法: 二次规划先计算最小运费矩阵两种运输方式（铁路公路）混合最短路问题是普通最短路问题的变种，需要自己设计算法 钢管运输问题（CUMCM-2000B) 钢管运输问题（CUMCM-2000B)运输矩阵的计算模型问题分析铁路子网络 钢管运输问题（CU