[数学]2优化模型.ppt

全年捕鱼的收获量（捕捞总量） 其中用到了k3=0.42k4 原问题变成一个普通函数极值问题，用软件可以求解。 与并行相关的计算问题 目前大家用的机器一般是多CPU的机器 大计算量的计算问题问题在多CPU下会变成什么样子？ 简单示例： for i=1:102400 A(i) = sin(i*2*pi/10240); end plot(A) Amdahl’s law：加速比的极限 W固定，可以看作是输入数据量或者是总的计算量。Ws和Wp分别为其中的串行分量和可并行分量，W = Ws+Wp 记f = Ws/W，表示串行分量所占比；1-f表示并行分量所占的比例 Speedup(p) ? (Ws+Wp) / (Ws+Wp/p) 其中p是处理器的数量 Speedup(p) ? [f+(1-f)] / [f+(1-f)/p] = 1/[f+(1-f)/p] 1/f 即加速比受限于问题算法的串行分量所占比例 例如，如果问题计算量的5%必须串行，则加速比最多不过20，无论用多少个处理器/执行核 在matlab中怎么办？ 并行计算（Parallel Computing） 1、打开并行开关（matlabpool open） 根据算法，把for改成parfor 然后计算 2、批命令 batch(‘mywave’, ‘matlabpool’, 2） 优化模型 内容 优化模型的分类 各种优化模型的建立和求解（用实例说明） 并行计算问题 优化模型的分类 抽象优化模型: Max f(x) S.t: g(x)0 根据f(x) 和g(x)的类型不同，可以分为： 线性规划（优化）问题 二次规划（优化）问题 非线性规划（优化）问题 多目标规划（优化）问题 其它的优化问题（如离散方案比较） 竞赛题目大部分与优化问题相关 例一飞机飞行管理问题 在约10,000米高空的某边长160公里的正方形区域内, 经常有若干架飞机作水平飞行。区域内每架飞机的位置和速度均由计算机记录其数据，以便进行飞行管理。当一架欲进入该区域的飞机到达区域边缘, 记录其数据后，要立即计算并判断是否会与区域内的飞机发生 碰撞。如果会碰撞，则应计算如何调整各架(包括新进入的)飞机飞行方向角，以避免碰撞。现假定条件如下:?? 1) 不碰撞的标准为任意两架飞机的距离大于8公里; 2) 飞机飞行方向角调整的幅度不应超过30度; 3) 所有飞机飞行速度均为每小时800公里;4) 进入该区域的飞机在到达区域边缘时, 与区域内飞机的距离应在60公里以上;5) 最多需考虑6架飞机;6) 不必考虑飞机离开此区域后的状况。请你对这个避免碰撞的飞行管理问题建立数学模型，列出计算步骤，对以下数据进行计算(方向角误差不超过0.01度)，要求飞机飞行方向角调整的幅度尽量小。设该区域4个顶点的座标为(0,0)，(160,0)，(160,160)，(0,160)。 记录数据为: 飞机编号 横座标x 纵座标y 方向角(度) 1 150 140 243 2 85 85 236 3 150 155 220.5 4 145 50 159 5 130 150 230 新进入 0 0 52 问题链 关键词搭配 避免碰撞 调整 实时 优化问题 方向角 最小距离8km 幅度尽量小 调整方案 优化算法 飞机运行图 两架飞机的情况 什么时间调整？ A C B D E 是否需要多次调整？ A H E C D G B O F 碰撞的表达式 在t时刻两架飞机的位置分别在 和 dij(t)在t时刻两架飞机的距离，则 讨论相撞的条件 令f（t）=dij2 – R2 (R不发生碰撞的最小距离） 则 f(t)=at2+bt+c,判断飞机是否相撞，即判断方程f(t)=0在[0,tij)是否有解。 △=b2-4ac △0 两架飞机不碰撞 △≥0分三种情况：(t1t2) t20或t1tij 不会撞，其他情况必会相撞。 模型 其中Dij( , )两架飞机在[0,tij)的最短距离 Dij( , )的计算参见碰撞分析 化简 这是一个非线性优化问题，没有软件能直接处理，必须做合理的化简。 把优化函数变为 把条件变化为： 线性模型 将每架飞机视为圆片状，半径4km vij 经计算（用复数）可知 模型 引进中间变量后可以把它变成标准的可用线性规划软件处理线性规划问题 例二：最优捕鱼策略 （1996 a)为了保护人类赖以生存的自然环境，可再生资源（如渔业、林业资源）的开发必须适度。一种合理、简化的策略是，在实现可持续收获的前提下，追求最大产量或最佳效益。 ????考虑对某种鱼（鲳鱼）的最优捕捞策略： ????假设这种鱼分４个年龄组：称１龄鱼，……，４龄鱼。各年龄组每条鱼的平均重量分别为5.07,11.55,