数学建模路线优化问题
选路的优化模型
摘要:
本题是一个有深刻背景的NPC问题，文章分析了分组回路的拓扑结构，并构造了多个模型，从多个侧面对具体问题进行求解。最短树结构模型给出了局部寻优的准则算法模型体现了由简到繁，确保较优的思想而三个层次分明的表述模型证明了这一类问题共有的性质。在此基础上我们的结果也是比较令人满意的。如对第一题给出了总长为599.9，单项长为216的分组，第二题给出了至少分四组的证明。最后，我们还谈到了模型的优缺点及推广思想。
一、问题描述
“水大无情，人命关天”为考察灾情，县领导决定派人及早将各乡（镇），村巡视一遍。巡视路线为从县政府所在地出发，走遍各乡（镇），村又回到县政府所在地的路线。
1.若分三组巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
2.假定巡视人员在各乡（镇）停留时间为T=2小时，在各村停留时间为t =1 小时，
汽车行驶速度为V=35公里/时，要在24小时内巡视完，至少分成几组；给出这
种分组下你认为最佳的巡视路线。
3.上述关于T，t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多
少？给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。
4.巡视组数已定（如三组）要求尽快完成巡视，讨论T，t和V改变时最佳路线的
影响（图见附录）。
二、问题假设
1、乡（镇）村只考察一次，多次经过时只计算一次停留时间。
2、非本县村不限制通过。
3、汽车的行驶速度始终一致。
三、符号说明
第i 人走的回路Ti=vv i(i) v2(i)v n(i)
Ti=00表示第i人在0点没移动
四、模型建立
在这一节里，我们将提出若干个模型及其特点分析，不涉及对题目的求解。
最简树结构模型
在这个模型中我们依靠利用最短树的特殊结构所给出的准则，进行局部寻优，在一个不大的图里，我们较易得到较优解。
(a)分片
准则1利用最短树的长度可大致的估算出路程长，在具体操作中，各片中
的最短路程长度不宜相差太大。
准则 2 尽可能将最短树连成一个回路，这可保证局部上路程是较短的。
(b)片内调整
a2 a3 a4 a5 a6假设a3 a4有路相连
细准1对于右图的最短树结构，最好的走法是a
若a3 a4 进去重复走的话，它与上述的走法路程差w(a3, a2)+w(a2 ,a5)+w(a4, a5)—w(a3, a4)。由两点间最小原则上式是大于0的优劣可见
细准2若有如图所示结构，一般思想是：将中间树枝上的点串到两旁树枝，以便连成回路。
五、模型求解
问题一该问题完全可以用均衡模型表述
用算法模型 1 经过局部优化手工多次比较我们能够给出的最佳结果为第一组路径为
0—P—28—27—26—N—24—23—22-17—16—1—15—1—18—K—21—20—25—
M--0 长191.1 经5 镇6 村
第二组路径为
0—2—5—6—L—19—J—11--G—13—14—H—12—F—10—F—9—E—8—E—7—6—5—2—0 长216.5 经6 镇11 村第三组路径为O—2—3—D—4—D—3—C—B—1—A—34—35—33—31—32—30—Q—29
—R 长192.3 经6 镇11 村总长S=599.9 公里
由算法2 给出的为
1组0—P—29—R—31—33—A—34—35—32—30—Q—28—27—26—N—24—33—22—23—N—2
6—P—0 5 乡13 村长215.2 公里
2组0—M—25—21—K—17—16—I—15—I—18—K—21—25—20—L—19—J—11—G—13—14
—O 5 乡11 村长256.2 公里
3组
O—2—5—6—7—E—9--F—12--H--—12—F—10—F—9—E-8—4—0—7—6—M—5-2—3—L
—13—1—0 8 乡11 村长256.3 公里
总长727.7 公里
问题二
利用最小时模型所给结论 应分组 n
当分 4
组时 1 算
法模型 1 给出的解为
公里小时2
注 以上每一路径是含 0 的回路 如果两点之间没有公共边 则走连接两点之间的最短路径因篇幅有限不能将途径的所有点都罗列
问题三
可以这样认为 往每个点都派一个巡视组去访问 并且都走最短路径 这时所花时间最少由于点的个数有限 时间是容易求的 从地图上看 H 是最短路径最长的点 且停留时间最长它所花的时间即为所求:E=77.1 2/35 +2=6.43(小时)
我们认为在这个时间限制下 最佳路线指派出人数最少路线 依靠最小时模型结论 可以给出估计 n ≥[t*/t]+1=[83.29/6.43]=1=13 但上限为 17+35=52 不能确定 n 的取值 现我们用计算机结合算法模型 2 进行搜索 得到 n 的最优值为 35
参考文献
[1] 《图论及其算法》航空工业出版社.肖住枢主编
[ ≥ t t * ]+1=[ 24
29 . 83 ]+1=4
数学建模路线优化问题
选路的优化模型 摘要: 本题是一个有深刻背景的NPC问题，文章分析了分组回路的拓扑结构，并构造了多个模型，从多个侧面对具体问题进行求解。最短树结构模型给出了局部寻优的准则算法模型体现了由简到繁，确保较优的思想而三个层次分明的表述模型证明了这一类问题共有的性质。在此基础上我们的结果也是比较令人满意的。如对第一题给出了总长为599.9，单项长为216的分组，第二题给出了至少分四组的证明。最后，我们还谈到了模型的优缺点及推广思想。 一、问题描述 “水大无情，人命关天”为考察灾情，县领导决定派人及早将各乡（镇），村巡视一遍。巡视路线为从县政府所在地出发，走遍各乡（镇），村又回到县政府所在地的路线。 1.若分三组巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 2.假定巡视人员在各乡（镇）停留时间为T=2小时，在各村停留时间为t =1 小时， 汽车行驶速度为V=35公里/时，要在24小时内巡视完，至少分成几组；给出这 种分组下你认为最佳的巡视路线。 3.上述关于T，t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多 少？给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 4.巡视组数已定（如三组）要求尽快完成巡视，讨论T，t和V改变时最佳路线的 影响（图见附录）。 二、问题假设 1、乡（镇）村只考察一次，多次经过时只计算一次停留时间。 2、非本县村不限制通过。 3、汽车的行驶速度始终一致。 三、符号说明 第i 人走的回路Ti=vv i(i) v2(i)v n(i) Ti=00表示第i人在0点没移动 四、模型建立
在这一节里，我们将提出若干个模型及其特点分析，不涉及对题目的求解。 最简树结构模型 在这个模型中我们依靠利用最短树的特殊结构所给出的准则，进行局部寻优，在一个不大的图里，我们较易得到较优解。 (a)分片 准则1利用最短树的长度可大致的估算出路程长，在具体操作中，各片中 的最短路程长度不宜相差太大。 准则 2 尽可能将最短树连成一个回路，这可保证局部上路程是较短的。 (b)片内调整 a2 a3 a4 a5 a6假设a3 a4有路相连 细准1对于右图的最短树结构，最好的走法是a 若a3 a4 进去重复走的话，它与上述的走法路程差w(a3, a2)+w(a2 ,a5)+w(a4, a5)—w(a3, a4)。由两点间最小原则上式是大于0的优劣可见 细准2若有如图所示结构，一般思想是：将中间树枝上的点串到两旁树枝，以便连成回路。 五、模型求解 问题一该问题完全可以用均衡模型表述 用算法模型 1 经过局部优化手工多次比较我们能够给出的最佳结果为第一组路径为 0—P—28—27—26—N—24—23—22-17—16—1—15—1—18—K—21—20—25— M--0 长191.1 经5 镇6 村 第二组路径为 0—2—5—6—L—19—J—11--G—13—14—H—12—F—10—F—9—E—8—E—7—6—5—2—0 长216.5 经6 镇11 村第三组路径为O—2—3—D—4—D—3—C—B—1—A—34—35—33—31—32—30—Q—29 —R 长192.3 经6 镇11 村总长S=599.9 公里 由算法2 给出的为 1组0—P—29—R—31—33—A—34—35—32—30—Q—28—27—26—N—24—33—22—23—N—2 6—P—0 5 乡13 村长215.2 公里 2组0—M—25—21—K—17—16—I—15—I—18—K—21—25—20—L—19—J—11—G—13—14 —O 5 乡11 村长256.2 公里 3组 O—2—5—6—7—E—9--F—12--H--—12—F—10—F—9—E-8—4—0—7—6—M—5-2—3—L —13—1—0 8 乡11 村长256.3 公里 总长727.7 公里
快递员配送路线优化模型
快递员配送路线优化模型 摘要 如今，随着网上购物的流行，快递物流行业在面临机遇的同时也需要不断迎接新的挑战。如何能够提高物流公司的配送效率并降低配送过程中的成本，已成为急需我们解决的一个问题。下面，本文将针对某公司的一名配送员在配送货物过程中遇到的三个问题进行讨论及解答。 对于问题一，由于快递员的平均速度及在各配送点停留的时间已知，故可将最短时间转换为最短路程。在此首先通过Floyd求最短路的算法，利用Matlab 程序将仓库点和所有配送点间两两的最短距离求解出来，将出发点与配送点结合起来构造完备加权图，由完备加权图确定初始H圈，列出该初始H圈加点序的距离矩阵，然后使用二边逐次修正法对矩阵进行翻转，可以求得近似最优解的距离矩阵，从而确定近似的最佳哈密尔顿圈，即最佳配送方案。 对于问题二，依旧可以将时间问题转化为距离问题。利用问题一中所建立的模型，加入一个新的时间限制条件，即可求解出满足条件的最佳路线。 对于问题三，送货员因为快件载重和体积的限制，至少需要三次才能将快件送达。所以需要对100件快件分区，即将50个配送点分成三组。利用距离矩阵寻找两两之间的最短距离是50个配送点中最大的三组最短距离的三个点，以此三点为基点按照准则划分配送点。 关键字：Floyd算法距离矩阵哈密尔顿圈二边逐次修正法矩阵翻转
问题重述 某公司现有一配送员，，从配送仓库出发，要将100件快件送到其负责的50个配送点。现在各配送点及仓库坐标已知，货物信息、配送员所承载重物的最大体积和重量、配送员行驶的平均速度已知。 问题一：配送员将前30号快件送到并返回，设计最佳的配送方案，使得路程最短。 问题二：该派送员从上午8：00开始配送，要求前30号快件在指定时间前送到，设计最佳的配送方案。 问题三：不考虑所有快件送达的时间限制，现将100件快件全部送到并返回。设计最佳的配送方案。配送员受快件重量和体积的限制，需中途返回取快件，不考虑休息时间。 符号说明 D：n个矩阵 n V：各个顶点的集合 E：各边的集合 e：每一条边 ij w:边的权 ()e G：加权无向图 , v v：定点 i j C：哈密尔顿圈 () f V：最佳哈密尔顿圈 i
优化问题的数学模型及基本要素
第1章 优化设计 Chapter 1 Optimization Design 1-1 优化设计 1-1-1 最优化 (optimize, optimization ) 所谓最优化，通俗地说就是在一定条件下，在所有可能的计划、设计、安排中找出最好的一个来。换句话说，也就是在一定的条件下，人们如何以最好的方式来做一件事情。(Optimization deals with how to do things in the best possible manner) 结论的唯一性是最优化的特点，即公认最好。(It is the best of all possibilities) 最优化的思想体现在自然科学、工程技术及社会活动的各个领域，最优化的方法在这些领域也得到了广泛地应用。(P1) 1-1-2 最优化方法 (Arithmetic ) 要从所有可能的方案中找出最优的一个，用“试”（try ）的办法是不可行的，需要采用一定的数学手段。二十世纪五十年代以前，用于解决最优化问题的数学方法仅限于古典的微分和变分(differential and variation)。数学规划法在五十年代末被首次用于解决最优化问题，并成为现代优化方法的理论基础。线性规划和非线性规划是数学规划的主要内容，它还包括整数规划、动态规划、二次规划等等。(Linear programming or Nonlinear programming, Integer, Dynamic, Quadratic ) 数学规划法与电子计算机的密切结合,改变了最优化方法多有理论研究价值,而少有实际应用的局面,使得解决工程中的优化问题成为可能。因此,我们现在所说的最优化方法，实际上包括了最优化理论和计算机程序二方面的内容。(Optimization theory plus computer program) 1-1-3 优化设计 下面以一个简单的问题为例来说明传统设计与优化设计这二个不同的设计过程。 例1-1 设计一个体积为5cm 3的薄板包装箱，其中一边的长度不小于4m 。要求使薄板耗 材最少，试确定包装箱的尺寸参数，即长a ，宽b 和高h 。 分析 包装箱的表面积s 与它的长a ，宽b 和高h 尺寸有关。因此，耗板最少的问题可以转化为表面积最小问题，故取表面积s 为设计目标。 传统设计方法: 首先固定包装箱一边的长度如)(4m a =。要满足包装箱体积为3 5m 的设计要求，则有以下多种设计方案: 如果包装箱的长度a 再取)(4m a >的其他值，则包装箱的宽度和高度还会有很多其他结果… 。 最后，从上面众多的可行方案中选择出包装箱表面积最小的方案来，这就是相对最好的设计方案。但由于不可能列出所有可能的设计方案，最终方案就不一定是最优的。 机械产品的传统设计通常需要经过：提出课题、调查分析、技术设计、结构设计、绘图
优化设计数学建模
一、问题重述 1、利用优化设计相关理论计算法，对某设计问题做优化设计。要求如下： ①列出优化数学模型; ②选择所用优化算法； ③画出程序框图； ④程序编写； ⑤程序调试运算结果。 现根据以上条件，结合生活实际，准备以铁板为材料设计一鱼缸，为了能使鱼儿有更大的生存空间，要求鱼缸容积最大。 现有边长为5米长的方形铁板，预备在四个角减去四个相等的方形面积，用以制成方形鱼缸，如何减能使鱼缸的容积最大。 二、问题分析 2.1、对于此问题，我采用的数学模型包括三部分，即设计变量、目标函数和约束条件。 模型如下： 其中，设裁去铁块的边长为：x(0 四、程序编写及函数图像 4.1求极值所用程序如下： function q=line_s(a,b) N=10000;r=0.01; a=0;b=1.5; for k=1:N; v=a+0.382*(b-a); u=a+0.618*(b-a); fv=-25*v+20*v^2-4*v^3; fu=-25*u+20*u^2-4*u^3; if fv>fu if b-v<=r u fu break; else a=v;v=u; u=a+0.618*(b-a); end else if u-a<=r v -fv break; else b=u;u=v; v=a+0.382*(b-a); end k=k+1 end end 4.2 函数曲线图程序如下: 如下曲线所得y值为负，前面（1*）已作解释。 x=0:0.1:2.5; y=-25*x+20*x.^2-4*x.^3; plot(x,y); 五、程序调试运行结果 5.1 如图所示： 当k执行5或7或10或12次时，均有x=0.8329时，有最大y=9.2593（函数中已做处理，变负为正，可以对照曲线图）。 1、高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳 万元，可使用的金属板有500t，劳动力有300人/月，机器有100台/月，此外，不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号为100万元，中号为150万元，大号为200万元，现在要制定一个生产计划，使获得的利润为最大， max=4*x1+5*x2+6*x3-100*y1-150*y2-200*y3; 2*x1+4*x2+8*x3<=500; 2*x1+3*x2+4*x3<=300; 1*x1+2*x2+3*x3<=100; @bin(y1); @bin(y2); @bin(y3); y1+y2+y3>=1; Global optimal solution found. Objective value: 300.0000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost X1 100.0000 0.000000 X2 0.000000 3.000000 X3 0.000000 6.000000 Y1 1.000000 100.0000 Y2 0.000000 150.0000 Y3 0.000000 200.0000 Row Slack or Surplus Dual Price 1 300.0000 1.000000 2 300.0000 0.000000 3 100.0000 0.000000 4 0.000000 4.000000 5 0.000000 0.000000 铺路问题的最优化模型 摘要 本文采用了两种方法，一种是非线性规划从而得出最优解，另一种是将连续问题离散化利用计算机穷举取最优的方法。 根据A地与B地之间的不同地质有不同造价的特点，建立了非线性规划模型和穷举取最优解的模型，解决了管线铺设路线花费最小的难题。 问题一：在本问题中，我们首先利用非线性规划模型求解，我们用迭代法求出极小值（用Matlab实现），计算结果为总费用最小为748.6244万元，管线在各土层中在东西方向上的投影长度分别为15.6786km，3.1827 km，2.1839 km，5.8887km，13.0661km。然后，我们又用穷举法另外建立了一个模型，采用C语言实现，所得最优解为最小花费为748.625602万元，管线在各土层中在东西方向上的投影长度分别为15.70km,3.20km,2.20km,5.90km,13.00km。 问题二：本问题加进了一个非线性的约束条件来使转弯处的角度至少为160度，模型二也是如此。非线性规划模型所得计算结果为最小花费为750.6084万元，管线在各土层中在东西方向上的投影长度分别为14.4566km,4.3591km,2.5984km,6.5387km,12.0472km。遍历模型所得最优解为最小花费为750.821154万元，管线在各土层中在东西方向上的投影长度分别为14.10km,4.30km, 2.70km,6.70km,12.20km。 问题三：因为管线一定要经过一确定点P，我们将整个区域依据P点位置分成两部分，即以A点正东30km处为界，将沙土层分成两部分。非线性规划模型最小花费为752.6432万元，管线在各土层中在东西方向上的投影长度分别为21.2613km,3.3459km,2.2639km,3.1288km,2.4102km,7.5898km。遍历模型最小花费为752.649007万元，管线在各土层中在东西方向上的投影长度分别为21.30km,3.30km,2.30km,3.10km,2.40km,7.60km。 关键词：非线性规划逐点遍历穷举法 数学建模路线优化问题 选路的优化模型 摘要: 本题是一个有深刻背景的NPC问题，文章分析了分组回路的拓扑结构，并构造了多个模型，从多个侧面对具体问题进行求解。最短树结构模型给出了局部寻优的准则算法模型体现了由简到繁，确保较优的思想而三个层次分明的表述模型证明了这一类问题共有的性质。在此基础上我们的结果也是比较令人满意的。如对第一题给出了总长为599.9，单项长为216的分组，第二题给出了至少分四组的证明。最后，我们还谈到了模型的优缺点及推广思想。 一、问题描述 “水大无情，人命关天”为考察灾情，县领导决定派人及早将各乡（镇），村巡视一遍。巡视路线为从县政府所在地出发，走遍各乡（镇），村又回到县政府所在地的路线。 1.若分三组巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 2.假定巡视人员在各乡（镇）停留时间为T=2小时，在各村停留时间为t =1 小 时，汽车行驶速度为V=35公里/时，要在24小时内巡视完，至少分成几组； 给出这种分组下你认为最佳的巡视路线。 3.上述关于T，t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多 少？给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 4.巡视组数已定（如三组）要求尽快完成巡视，讨论T，t和V改变时最佳路线 的影响（图见附录）。 二、问题假设 1、乡（镇）村只考察一次，多次经过时只计算一次停留时间。 2、非本县村不限制通过。 3、汽车的行驶速度始终一致。 三、符号说明 符号表示意义 Ti 第i 人走的回路Ti=vv i(i) v2(i)v n(i) Ti=00表示第i人在0点没移动 Vi Ti的点集Si Ti的长度 Hi(v) 在V上定义的特殊函数仅当V被第i 人走过且停留时 Hi(v)=1,否则为0 一. 管理科学的定义 管理科学是对与定量因素有关的管理问题通过应用科学的方法进行辅助管理决策制定的一门学科. (1) 定量因素(2) 科学的方法(3) 辅助决策制定 二.用管理科学的方法解决问题的基本步骤. （1） 提出问题，并根据需要收录有关数据信息。管理科学工作者向管理者咨询、鉴别所 要考虑的问题以确定合理的目标，然后根据要求收集一些关键数据，并对数据作相应的分析。 （2） 建立模型，引入决策变量，确定目标函数（约束条件）。建模过程是一项创造性的 工作，在处理实际问题时，一般没有一个唯一正确的模型，而是有多种不同的方案。建模是一个演进过程，从一个初始模型往往需要不断的完善渐渐演化成一个完整的数学模型。 （3） 从模型中形成一个对问题求解的算法。要在计算机上运行数学程序对模型进行求 解，一般情况下能找到对模型求解的标准软件。例如，对线性规划问题已有Excel 、Cplex 、Lingo 等标准软件求解。有时要自己编写程序。 （4） 测试模型并在必要时修正。在模型求解后，需要对模型进行检验，以保证该模型能 准确反映实际问题，需要检验模型提供的解是否合理，所有主要相关因素是否已考虑，当有些条件变化时，解如何变化等。 （5） 应用模型分析问题以及提出管理建议。对模型求解并分析后，将相应的最优方案提 交给管理者，由管理者做出决策。管理科学工作者并不作管理决策，其研究只是对涉及的问题进行分析并向管理者提出建议。管理者还要考虑管理科学以外的众多因素才能做出决策。 （6） 帮助实施管理决策。建议被管理者采纳以后，一旦做出管理决策一般要求帮助监督 决策方案的实施。 新问题, 新模型, 新算法, 新应用. 三.优化问题的数学模型 1212max(min)(,, ,) (,,)0..1,2,n j n Z f x x x g x x x s t j m =≤?? =? 由于,j f g 是非线性函数时，此问题是非线性优化问题, 求解较复杂。我们主要讨论线性优化问题，常见的形式：混合整数规划 （1） max 0 0 Z CX hY AX GY b X Y =++≤≥≥取整数 其中111,,,,m n m p m n p A G b C h ?????，不失一般性，我们假定,,,,C h A G b 都是整数矩阵。 当0p =时，（1）为纯整数规划，当0n =时，（1）为线性规划。 投资的收益与风险问题 摘要 对市场上的多种风险资产和一种无风险资产（存银行）进行组合投资策略的设计需要考虑两个目标：总体收益尽可能大和总体风险尽可能小，而这两个目标在一定意义上是对立的。 本文我们建立了投资收益与风险的双目标优化模型，并通过“最大化策略”，即控制风险使收益最大，将原模型简化为单目标的线性规划模型一；在保证一定收益水平下，以风险最小为目标，将原模型简化为了极小极大规划模型二；以及引入收益——风险偏好系数，将两目标加权，化原模型为单目标非线性模型模型三。然后分别使用Matlab的内部函数linprog，fminmax，fmincon对不同的风险水平，收益水平，以及偏好系数求解三个模型。 关键词：组合投资，两目标优化模型，风险偏好 2.问题重述与分析 3.市场上有种资产（如股票、债券、…）()供投资者选择，某公司有数额为的 一笔相当大的资金可用作一个时期的投资。公司财务分析人员对这种资产进行了评估，估算出在这一时期内购买的平均收益率为，并预测出购买的风险损失率为。考虑到投资越分散，总的风险越小，公司确定，当用这笔资金购买若干种资产时，总体风险可用所投资的中最大的一个风险来度量。 购买要付交易费，费率为，并且当购买额不超过给定值时，交易费按购买计算（不买当然无须付费）。另外，假定同期银行存款利率是, 且既无交易费又无风险。（） 1、已知时的相关数据如下： 试给该公司设计一种投资组合方案，即用给定的资金，有选择地购买若干种资产或存银行生息，使净收益尽可能大，而总体风险尽可能小。 2、试就一般情况对以上问题进行讨论，并利用以下数据进行计算。 本题需要我们设计一种投资组合方案，使收益尽可能大，而风险尽可能小。并给出对应的盈亏数据，以及一般情况的讨论。 这是一个优化问题，要决策的是每种资产的投资额，要达到目标包括两方面的要求:净收益最大和总风险最低，即本题是一个双优化的问题，一般情况下，这两个目标是矛盾的，因为净收益越大则风险也会随着增加，反之也是一样的，所以，我们很难或者不可能提出同时满足这两个目标的决策方案，我们只能做到的是：在收益一定的情况下，使得风险最小的决策，或者在风险一定的情况下，使得净收益最大，或者在收益和风险按确定好的偏好比例的情况下设计出最好的决策方案，这 工业中截断切割的优化设计 一摘要 本文讨论了加工业中截断切割的优化排序策略我们对于不同的切割 方式总数用穷举法得到720 种所可行解及其费用并对于原问题建立了决策 并对所给出的算法进行了分析和检验 1.当e=0时我归纳出解决问题的最优法则, 从而提出了将面间距统一成判断权重来作为排 序准则的算法,同时证明 了e = 0 的情况下根据这种最优准则能够实现题目所要求的优化目标 2.对于e 1 0 时我们提出了实用准则 最后我结合实际问题将本问题进行了拓展讨论了当最终产品(成品) 在毛坯(待加工长方体)中位置不预定时应如何实施加工方案以达到节省费用 和节约资源的目的,使我们的方案适用于更为广阔的领域 二问题的重述、 在工业生产中，常需要采取将物理一分为二的截断切割方式从一块长方体材料中切出一个小长方体，其加工费用取决于水平切割和垂直切割的截面面积，以及调整刀具时的额外费用。对本题所给出的问题我们首先面临的对加工次序的排序策略然后我们考虑当毛坯和产品位置不预定的时候如何采取策略以达到我们的优化目的 问题： 1> 需考虑的不同切割方式的总数。 2> 给出上述问题的数学模型和求解方法。 3> 试对某部门用的如下准则做出评价，每次选择一个加工费用最少的切割面进行切割。 4> 对于e=0 的情况有无简明的优化准则。 5> 用以下实例验证你的方法： 待加工长方体和成品长方体的长，宽，高分别为10，14.5,19 和3,2,4,两者左侧面，正面，底面之间的距离分别为6,7,5(单位为厘米，垂直切割费用为每平方厘米1 元，r 和e 的数据有 4 组： 1) r=1,e=0; 2) r=1.5,e=0; 3) r=8,e=0; 4) r=1.5, 2 ￡ e ￡15 ; 三模型的假设和符号说明 1 切割刀具为两个一个水平放置一个为垂直放置 2 目标长方体所在位置不与毛坯任一表面重合 3 水平方向只需平行移动水平刀具垂直方向只平行移动或调整后再平行 移动刀具因此调整费用e 是否付出仅取决于先后两次垂直切割是否平行而 不记是否穿插着水平切割 4毛坯与工作台接触的底面是事先指定的 §3.6 优化问题与规划模型 与最大、最小、最长、最短等等有关的问题都是优化问题。 解决优化问题形成管理科学的数学方法：运筹学。运筹学主要分支：（非）线性规划、动态规划、图与网络分析、存贮学、排队伦、对策论、决策论。 6.1 线性规划 1939年苏联数学家康托洛维奇发表《生产组织与计划中的数学问题》 1947年美国数学家乔治.丹契克、冯.诺伊曼提出线性规划的一般模型及理论. 1. 问题 例1 作物种植安排 一个农场有50亩土地, 20个劳动力, 计划种蔬菜,棉花和水稻. 种植这三种农作物每亩地分别需要劳动力 1/2 1/3 1/4, 预计每亩产值分别为 110元, 75元, 60元. 如何规划经营使经济效益最大. 分析：以取得最高的产值的方式达到收益最大的目标. 1. 求什么？分别安排多少亩地种蔬菜、棉花、水稻？ x 1亩、 x 2 亩、 x 3 亩 2. 优化什么？产值最大 max f=10x 1+75x 2 +60x 3 3. 限制条件？田地总量 x 1+x 2 +x 3 ≤ 50 劳力总数 1/2x 1 +1/3x 2 +1/4x 3 ≤ 20 模型 I : 设决策变量：种植蔬菜 x 1亩, 棉花 x 2 亩, 水稻 x 3 亩， 求目标函数 f=110x 1+75x 2 +60x 3 在约束条件x 1+x 2 +x 3 ≤ 50 1/2x 1 +1/3x 2 +1/4x 3 ≤20 下的最大值 规划问题：求目标函数在约束条件下的最值, 规划问题包含3个组成要素: 决策变量、目标函数、约束条件。 当目标函数和约束条件都是决策变量的线性函数时，称为线性规划问题, 否则称为非线性规划问题。 2. 线性规划问题求解方法 称满足约束条件的向量为可行解,称可行解的集合为可行域, 称使目标函数达最值的可行解为最优解. 命题 1 线性规划问题的可行解集是凸集. 因为可行解集由线性不等式组的解构成。两个变量的线性规划问题的可行解集是平面上的凸多边形。 命题2 线性规划问题的最优解一定在可行解集的某个极点上达到. 图解法：解两个变量的线性规划问题，在平面上画出可行域，计算目标函数在各极点处的值，经比较后，取最值点为最优解。 命题3 当两个变量的线性规划问题的目标函数取不同的目标值时，构成一族平行直线,目标值的大小描述了直线离原点的远近。 于是穿过可行域的目标直线组中最远离(或接近)原点的直线所穿过的凸多边形的顶点即为取的极值的极点—最优解。 单纯形法 : 通过确定约束方程组的基本解, 并计算相应目标函数值, 在可行解 案例16 停车场的优化设计 随着城市车辆的增加，停车位的需求量也越来越大，停车困难已逐渐成为市民们头疼的问题。要解决停车难问题，除了尽可能的增加停车场以外，对停车场进行优化设计也能在一定程度上缓解这一供需矛盾。停车场的优化设计就是在停车场大小确定的情况下，对停车区域进行优化设计，以便容纳更多的车辆。本文的目的就是希望分析一下这一情况，找出缓解停车困难的有效办法。 假设某公共场所附近有一块空地，如果不考虑建设地下或多层结构，我们该如何有效的设计停车位置呢？一般来说，想尽可能的把车塞进停车场，最好的办法就是以垂直停靠的方式将车一辆挤一辆地排成行，但是这样停放的后果就是车辆不能自由出入，只有后进入的车辆全部先出去了，先进入的车才可以离开停车场，显然不符合实际的需求。因而，为了使汽车能够自由地出入停车场，必须设立一定数量具有足够宽度的通道，并且每个通道都应该有足够大的“转弯半径”， 而通道越宽越多，就会使得容纳的车辆数越少。所以我们的问题就是要确定在满足车辆能够自由进出的实际需求下，如何进行停车位置和车行通道的设计，才能够停放更多的车辆，从而做到既方便停车又能获得最大的经济效益。 我们先来看看生活中非货运车辆大小的种类。根据实际调查和经验数据，这类车辆一般可分为小轿车，中型客车和大型客车三类。其中小轿车约占九成，大型客车约占一成，而中型客车一般不多于1%。根据这样的情况，我们可以免去对中型客车的车位设计，即便有中型客车停车的需要，可以使用大型车的车位，这也符合现实生活中绝大多数停车场的车位设计情况。我们设小轿车所占的比例为0.9α=,大型客车所占的比例为10.1α-=，当然现实中也有不少全为小轿车设计的停车场，例如小区的地下车库。 再来看看车位的大小。根据实际的调查，城市内比较普通的小轿车长度一般不超过4.7米，宽度一般不超过1.7米，而一般大型客车长度不超过12米，宽度不超过2.2米。另外，经实际考察可知，停车场中标志线的宽度大约为0.1米，所以我们可以假设停车场中停放轿车需要的车位长5L C =米，宽 2.5W C =米，这其中包括了0.1米的标志线宽度和至少0.3米的汽车间的横向间距。设停放大客车需要长12.5L B =米，宽3W B =米，其中包括0.1米的标志线宽度和必要的汽 与最大、最小、最长、最短等等有关的问题都是优化问题。 解决优化问题形成管理科学的数学方法：运筹学。运筹学主要分支：（非）线性规划、动态规划、图与网络分析、存贮学、排队伦、对策论、决策论。 6.1 线性规划 1939年苏联数学家康托洛维奇发表《生产组织与计划中的数学问题》 1947年美国数学家乔治.丹契克、冯.诺伊曼提出线性规划的一般模型及理论. 1. 问题 例1 作物种植安排 一个农场有50亩土地, 20个劳动力, 计划种蔬菜,棉花和水稻. 种植这三种农作物每亩地分别需要劳动力1/2 1/3 1/4, 预计每亩产值分别为110元, 75元, 60元. 如何规划经营使经济效益最大. 分析：以取得最高的产值的方式达到收益最大的目标. 1. 求什么？分别安排多少亩地种蔬菜、棉花、水稻？ x 1亩、 x 2 亩、 x 3 亩 2. 优化什么？产值最大 max f=10x 1+75x 2 +60x 3 3. 限制条件？田地总量 x 1+x 2 +x 3 ≤ 50 劳力总数 1/2x 1 +1/3x 2 +1/4x 3 ≤ 20 模型I : 设决策变量：种植蔬菜x1亩, 棉花x2亩, 水稻x3亩， 求目标函数f=110x1+75x2+60x3 在约束条件x1+x2+x3≤ 50 1/2x1+1/3x2+1/4x3 ≤20 下的最大值 规划问题：求目标函数在约束条件下的最值, 规划问题包含3个组成要素: 决策变量、目标函数、约束条件。 当目标函数和约束条件都是决策变量的线性函数时，称为线性规划问题, 否则称为非线性规划问题。 2. 线性规划问题求解方法 称满足约束条件的向量为可行解,称可行解的集合为可行域, 称使目标函数达最值的可行解为最优解. 命题 1 线性规划问题的可行解集是凸集. 因为可行解集由线性不等式组的解构成。两个变量的线性规划问题的可行解集是平面上的凸多边形。 命题2 线性规划问题的最优解一定在可行解集的某个极点上达到. 图解法：解两个变量的线性规划问题，在平面上画出可行域，计算目标函数在各极点处的值，经比较后，取最值点为最优解。 命题 3 当两个变量的线性规划问题的目标函数取不同的目标值时，构成一族平行直线,目标值的大小描述了直线离原点的远近。 于是穿过可行域的目标直线组中最远离(或接近)原点的直线所穿过的凸多边形的顶点即为取的极值的极点—最优解。 单纯形法: 通过确定约束方程组的基本解, 并计算相应目标函数值, 在可行解集的极点中搜寻最优解. 正则模型: 决策变量: x 1,x 2 ,…,x n . 目标函数: Z=c 1 x 1 +c 2 x 2 +…+c n x n . 约束条件: a 11 x1+…+a1n x n≤b1, ……a m1x1+…+a mn x n≤b m, 模型的标准化 10. 引入松弛变量将不等式约束变为等式约束. 若有 a i1x 1 +…+a in x n ≤b i , 则引入 x n+i ≥ 0, 使得 a i1 x 1 +…+a in x n + x n+i =b i 若有 a j1x 1 +…+a jn x n ≥b j , 则引入 x n+j ≥ 0, 使得 a j1 x 1 +…+a jn x n - x n+j =b j . 楚雄师范学院 2011年数学建模培训第二次测试论文 题目玩转云南之旅游路线优化模型 姓名李雯刘正权叶万颂 系（院）数学系 专业信息与计算科学 2011年5月15日 一、摘要 云南风光旖旎，四季如春，是旅游的天堂。本论文就是以到云南旅游的交通方式以及路线选择为背景，通过构建模型。实现以经济的方式玩转云南的各大旅游景点。 旅游的交通方式一般有自驾游览和乘坐公共交通工具两种方式。本论文通过比较用公共交通出行方式下所有旅游路线的费用，得出最佳的旅游路线。 为了方便进行进行比较，文中引入了带权图和最小生成树的模型，为比较提供了可以参考的标准，模型中既要考虑路线最短，又要在规定的时间范围完成旅程,且通过预订旅游近点数最多，费用较少。 该模型以云南各大旅游景点为带权图的点，以采用交通方式来进行旅游过程中在具体的两个旅游景点的途中花去的费用为权值，这样，在该种旅游方式下的花费就是各对应的权值之和。当然，选择了公共交通的旅游方式，可能走的旅游路线也不尽相同。这样就产生了同一个旅游方式下的多条路线费用的比较，通过比较大小，就得到了较为经济的相应旅游方式下的最佳路线了。 本文作者充分调查了云南省目前的各种交通方式的收费情况，并查找了相关的旅游路线，有利地确保了论文的真实性和可靠性。 关键字：最小生成树、最佳路线、时间、路程。 二、问题 某旅客携带着家人想到云南旅游观光，并且想玩遍云南的各大旅游景点。请为这一行旅客设计旅游路线，并为他们提供一个合理的旅游交通方式的建议。 三、符号说明 把各景点用数据代替如下： 昆明市⑴楚雄市⑵大理市⑶丽江市⑷香格里拉⑸怒江⑹保山⑺德宏⑻临沧⑼ 普洱市⑽西双版纳⑾玉溪市⑿红河⒀文山市⒁石林⒂曲靖⒃昭通⒄ 权值表示景点之间的车票价 在手机普遍流行的今天，建设基站的问题分析对于运营商来说很有必要。本文针对现有的条件和题目的要求进行讨论。在建设此模型中，核心运用到了0-1整数规划模型，且运用lingo 软件求解。 对于问题一： 我们引入0-1变量，建立目标函数：覆盖人口最大数=所有被覆盖的社区人口之和，即max=15 1j j j p y =∑，根据题目要求建立约束条件，并用数学软件LINGO 对其模型求解，得到最优解。 对于问题二： 同样运用0-1整数规划模型，建立目标函数时，此处假设每个用户的正常资费相同，所以68%可以用减少人口来求最优值，故问题二的目标函数为：max=∑=15 1j j j k p 上述模型得到最优解结果如下： 关键字：基站; 0-1整数规划；lingo 软件 1 问题的重述．．．．．．．．．．．．．．．．．．．．．．．．．3 2 问题的分析．．．．．．．．．．．．．．．．．．．．．．．．．4 3 模型的假设与符号的说明．．．．．．．．．．．．．．．．．．．5 3.1模型的假设．．．．．．．．．．．．．．．．．．．．．． 5 3.2符号的说明．．．．．．．．．．．．．．．．．．．．．． 5 4 模型的建立及求解．．．．．．．．．．．．．．．．．．．．．. 5 4.1模型的建立．．．．．．．．．．．．．．．．．．．．．． 5 4.2 模型的求解．．．．．．．．．．．．．．．．．．．．．． 6 5 模型结果的分析．．．．．．．．．．．．．．．．．．．．．．．7 6 优化方向．．．．．．．．．．．．．．．．．．．．．．．．．．7 7 参考文献．．．．．．．．．．．．．．．．．．．．．．．．．．8 8、附录．．．．．．．．．．．．．．．．．．．．．．．．．．． 9 送货路线设计问题 现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。 现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见表3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1，50个位置点的坐标见表2。 假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。 现在送货员要将100件货物送到50个地点。请完成以下问题。 1. 若将1~30号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。 2. 假定该送货员从早上8点上班开始送货，要将1~30号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。 3. 若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可不考虑中午休息时间。 以上各问尽可能给出模型与算法。 图1 快递公司送货地点示意图 O点为快递公司地点，O点坐标(11000,8250),单位：米 货物号送达地点重量(公斤) 体积(立方米) 不超过时间 1 13 2.500.03169：00 2 18 0.500.03549：00 3 31 1.180.02409：30 4 26 1.560.035012：00 5 21 2.150.030512：00 6 14 1.720.010012：00 7 17 1.380.010912：00 8 23 1.400.042612：00 9 32 0.700.048112：00 10 38 1.330.021910：15 11 45 1.100.02879：30 盈利最大化的产品生产方案 摘 要：本问题是一个优化问题，它解决了大多数企业所面临的在生产设备有限的情况下要实现利润最大化的问题。根据盈利产品生产利润i b *生产数量i x ，我们建立目 标函数3 1i i i Z x b ==∑，又因为i 产品的生产数量i x 又受有限生产设备的限制，所以得到约束 条件：3 1(1,2,3)i ij j i x Y W j =≤=∑。用软件，建立模型求解，我们得到：当生产产品Ⅰ、Ⅱ、 Ⅲ的件数分别为22.5、23.2、7.3时，利润可实现最大化为135.2667千元。 在此基础上，我们做灵敏性分析得到借用设备B 每月60台时是不合算的这一结论；对于问题（3）、（4）可以建立相类似模型，得到对于新产品Ⅳ，Ⅴ的投产在经济上是合算的；当对产品工艺重新进行设计，改进结构，相应的生产产品Ⅰ、Ⅱ、Ⅲ的件数分别为22.8、25.3、0时，利润可实现最大化为153.1618千元；我们对此问题做了引申，当该厂生产的产品Ⅰ、Ⅱ、Ⅲ为汽车、手机等必须以整件计数的产品时，即1x 、2x 、3x 只能取整数，我们在问题一建立的函数模型基础上，加上限制条件，用求解得到了新的生产方案。 问题二回答：对问题一做灵敏性分析：租用设备B 一台时花费是300元，由上面灵敏性分析表可得一个台时的B 设备的影子价格约为267元，也就是说租用B 设备一个台时其能制造的利润为267元。很显然成本高于利润，商家无利可图而且还会造成亏损。 问题五回答：当该厂生产的产品Ⅰ、Ⅱ、Ⅲ为汽车、手机等必须以整件计数的产品时，即1x 、2x 、3x 只能取整数，我们在问题一建立的函数模型基础上，加上限制条件， 关键词：利润最大化；优化问题；生产方案；灵敏性分析 一、问题的提出 知某工厂计划生产Ⅰ、Ⅱ、Ⅲ三种产品，各产品需要在A 、B 、C 设备上加工，有 第2章 优化设计的数学模型及基本要素 Chapter 2 Mathematical Modeling for Optimization 2-1 数学模型的建立 (mathematical modeling) 建立数学模型，就是把实际问题按照一定的格式转换成数学表达式的过程。数学模型建立的合适、正确与否，直接影响到优化设计的最终结果。 建立数学模型，通常是根据设计要求，应用相关基础和专业知识，建立若干个相应的数学表达式。如机械结构的优化设计，主要是根据力学、机械设计基础等专业基础知识及机械设备等专业知识来建立数学模型的。 当然，要建立能够反映客观实际的、比较准确的数学模型并非容易之事。数学模型建的过于复杂，涉及的因素太多，数学求解时可能会遇到困难；而建的太简单，又不接近实际情况，解出来也无多大意义。因此，建立数学模型的原则：抓主要矛盾，尽量使问题合理简化。Principle ：The problem is simplified as much as possible. 由于设计对象千变万化，即使对同一个问题，由于看问题的角度不同，数学模型建的可能也不一样。建立数学模型不可能遵循一个不变的规则，本课也不准备把大量的时间花在数学模型的建立上。仅想以几个例子来演示一下数学模型的建立过程，使学生从中得到一些启发。 Exp. 2-1 例2-1 用宽度为cm 24，长度cm 100的薄 铁皮做成cm 100长的梯形槽，确定折边的尺寸 x 和折角θ（如图 2-1所示） ，使槽的容积最大。 解: 由于槽的长度就是板的长度，槽的梯形 截面积最大就意味着其容积最大。因此，该问题 就由，求体积最大变成求截面积最大。槽的梯形 截面积为： 图 2-1 ?= 2 1S 高 ?（上底边+下底边） 其中，上底边=x 224-；下底边=θcos 2224x x +-；高=θsin x 定义：该优化设计问题的目标函数是槽的梯形截面积S ，设计变量为θ,x 。问题可以简单地归结为：选择适当的设计变量θ,x ，在一定的限制条件下，使目标函数S 达到最大，限制条件为: 120,20<<< 最优化问题的数学模型及其分类 例1.1.1 产品组合问题 某公司现有三条生产线用来生产两种新产品，其主要数据如表1-1所示。请问如何生产可以让公司每周利润最大？ 表1-1 设每周生产的产品一和产品二 的产量分别为1x 和2x ，则每周的生产利润为：2153x x z +=。由于每周的产品生产受到三条生产线的可用时间的限制，因此1x ，2x 应满足以下条件： ?????? ?≥≤+≤≤0, 18231224212121 x x x x x x 故上述问题的数学模型为 2153max x x z += . .t s ?????? ?≥≤+≤≤0, 18231224212121 x x x x x x 其中max 是最大化（maximize ）的英文简称，??t s 是受约束于（subject to ）的简写。 例1.1.2 把一个半径为１的实心金属球熔化后，铸成一个 实心圆柱体，问圆柱体取什么尺寸才能使它的表面积最小？ 设圆柱体的底面半径为r ，高为h ，则该问题的数学模型为： ??? ??=? ?+=ππππ3 422min 22 h r t s r rh S 其中min 是最小化（minimize ）的简写。 通过以上二例，可以看出最优化问题的数学模型具有如下结构： （１） 决策变量（decision variable ）：即所考虑问题 可归结为优选若干个被称为参数或变量的量 n x x x ,,,21 ，它们都取实数值，它们的一组值构 成了一个方案。 （２） 约束条件（constraint condition ）：即对决策 变量n x x x ,,,21 所加的限制条件，通常用不等式或等式表示为： ()(),,,2,1, 0,,,,,2,1, 0,,,2121l j x x x h m i x x x g n j n i ===≥ （３） 目标函数（objective function ）和目标：如使 利润达到最大或使面积达到最小，通常刻划为极大化（maximize ）或极小化（minimize ）一个实值函数()n x x x f ,,21 因此，最优化问题可理解为确定一组决策变量在满足约束条件下，寻求目标函数的最优。 注意到极大化目标函数()n x x x f ,,21相当于极小化 ()n x x x f ,,21-，因此，约束最优化问题的数学模型一般可 表示为： () ()()()?? ? ??===≥??l j x x x h m i x x x g t s x x x f n j n i n ,,2,1,0,,,1.1.1,,2,1,0,,,,,min 212121 若记()T n x x x x ,,21=，则（1.1.1）又可写成：数学建模优化问题经典练习
数学建模铺路问题的最优化模型
数学建模路线
优化问题的数学模型
数学建模：投资问题
数学建模截断切割的优化设计
优化问题与规划模型
数学建模案例_停车场的优化设计(1)
数学建模中的优化问题与规划模型
旅游路线的优化模型
数学建模课程设计——优化问题
送货路线设计问题数学建模优化
数学建模-利润最大优化
优化设计的数学模型及基本要素
最优化问题的数学模型及其分类