优化建模-研

null最优化最优化 哈尔滨工业大学 尚寿亭建模·原理·算法教材教材[1] Mokhtar S. Bazaraa, C. M. Shetty, Nonlinear Programming theory and Algorithms. John Wiley & Sons, Inc.,1979 [2] M.S.巴扎拉，C.M.希蒂，王化存，张春柏译，非线性规划—理论与算法. 贵阳：贵州人民出版社，1986 [3] Mokhtar S. Bazaraa, C. M. Shetty, Foundations of optimization, lecture Notes in Economics and Mathematical Systems, No. 122, Springer-Verlag, New York,1976null参考 [1] 应玫茜，魏权龄. 非线性规划及其理论. 北京：中国人民大学出版社. 1994.9 [2] 薛嘉庆. 最优化原理与方法（修订版）. 北京：冶金工业出版社，1992.8 [3] 解可新，韩立兴，林友联. 最优化方法. 天津：天津大学出版社，1997.1 [4] 谢金星，薛毅. 优化建模与LINDO/LINGO软件. 北京：清华大学出版社，2005.7 [5] 邢文训，谢金星. 现代优化计算方法. 北京：清华大学出版社，1999.8 参考网站参考网站[1] 全国大学生数学建模竞赛网： http://www.mcm.edu.cn [2] 美国：数学及其应用联合会网站： http://www.comap.com/undergraduate/ [3] 中国数学建模网站： http://www.shumo.com/ [4] “中国电机工程学会杯”全国大学生电工数学建模竞赛网： http://www.cseem.org/ null 最优化方法 实际问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 与建模1.经典极值问题1.经典极值问题例1.车站选址问题 一直线铁路经过钢厂A，矿区 B 位于距铁路最近处 C 为20km，A C 相距150km。计划在铁路上设一站 D，在A D之间筑一条直线公路，若矿石运费铁路为3元/km·t，公路为5元/km·t。 问题：D 站选在何处最好。 y B（150，20） o x 150 x A D Cnull 建模与求解 建立模型： 设：坐标系 xoy，铁路线在 ox- 轴上，点A 位于坐标原点 o，点B位于（150，20）,点C位于（150，0）,站D选在 x 处，运费为 f (x)。 模型： （min--minimize） （1） 其中： 求解：应用导数求极值 令 ，即 （2） 由（2） null移项后两边开方，解得： （3） 由（2）知 x = 165 为增根（ ） x = 135 为唯一驻点 答案：站 D 应设在距钢厂 A 135km处。 问题扩展：考虑筑路、建站、装卸等费用，如何建模？ 数学建模竞赛题：道路改造项目中碎石运输的设计 相关网站： “中国电机工程学会杯”全国大学生电工数学建模竞赛 http://www.cseem.org/ 例2. 罐头盒问题 设计圆柱形罐头盒，使用料最省。 假设：1.不考虑折边及铁皮厚度； 2.底半径 r，高 h； 3.容积为常数V。null建立最优化模型： （4） s.t. --- subject to (满足于): 约束条件 令 模型（4）可写成 与（1）类似的形式 不考虑不等式约束时，模型（4）可用Lagrange乘子法求解null令 求解方程组 由 r > 0,及（6）解得 ，代入（5） 结论：高与直径相等时用料最省。 问题扩展：侧面与底面厚度不同或造价不同，该如何设计？ 作 业 题：建立易拉罐的优化设计模型。null经典优化问题一般模型： a.无约束问题： 其中的 可省去； b.条件极值： 最优化问题一般模型：null2.最优化问题实例： 例4. 生产计划问题 某工厂有 m 种资源 某一时段的数量 分别为： 可用来生产 n 种产品 每生产一单位 消耗 为 利润为 。如何安排 生产可获最大利润？ 设：计划生产 单位 建立线性规划模型 LP（Linear Programming） Max c1x1+ c2x2+ + cnxn s. t. a11 x1+ a12x2+ + a1nxn≤b1 am1 x1+ am2x2+ + amnxn ≤bm x1, x2, , xn 0 null令 x = [x1, x2, ···, xn ]T ; c = [c1, c2, ···, cn ]T ; b = [b1, b2, ···, bm ]T ; A = [ aij ]mxn LP： 问题扩展 a. 若 c1, c2, ···, cn 不是固定的，c 是随机变量， 平均值 ，协方差矩阵 V 。 希望利润期望值最大且方差最小，建立多目标优化模型： null问题扩展 b. 风险投资问题（参考98全国建模赛题） 将前面的产品换成投资项目，考虑投资 Aj 风险损失qj 。 建立多目标优化模型： 化为多目标线性规划模型： null例5. 数据拟合问题 设某系统中变量 x, y 满足： y = f (x) 已获得系统数据： ( xi , yi ) , i = 1, 2 , ··· , m 确定 f (x) 的参数，例如： 最优化模型： （最小二乘） 其中决策变量为f (x) 的参数null例6. 指派问题（0-1规划） null例7. 旅行商问题-TSP（组合优化） 一商人欲到 n 个城市推销， 城市 i 到城市 j 相距 dij , 求走遍所有城市的最短路。 模型： ○○○null计算复杂性概念 n个城市的旅行商问题-TSP，固定一个城市，采用枚举法需 (n-1)! 个枚举。 枚举时城市数与计算时间的关系 可以看出27个城市时枚举法已很费时，27个以上可采用启发式算法(heuristic algrithm)，参见： [5] （邢文训，谢金星. 现代优化计算方法. ） 问题扩展 ：多旅行商问题 98全国建模赛题 ： B. 灾情巡视路线 null2000B题 钢管订购和运输 要铺设一条A1→ A2→··· → A15的输送天然气的主管道, 如图一所示(见下页)。经筛选后可以生产这种主管道钢管的钢厂有S1, S2, ··· S7, 。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。 为方便计，1km主管道钢管称为1单位钢管。 一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂Si在指定期限内能生产该钢管的最大数量为个si单位，钢管出厂销价1单位钢管为pi万元，如下表： null 1单位钢管的铁路运价如下表： 1000km以上每增加1至100km运价增加5万元。 公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。 null钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。 （1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。 （2）请就（1）的模型 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。 （3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。nullnull钢管订购和运输 最优化模型钢管订购和运输 最优化模型钢管订购和运输 最优化模型钢管订购和运输 最优化模型钢管订购和运输 最优化模型钢管订购和运输 最优化模型null1998A题 投资的收益和风险 市场上有n种资产（如股票、债券、…）Si ( i=1,…n) 供投资者选择，某公司有数额为M的一笔相当大的资金可用作一个时期的投资。公司财务分析人员对这n种资产进行了评估，估算出在这一时期内购买Si的平均收益率为ri，并预测出购买Si的风险损失率为qi。考虑到投资越分散，总的风险越小，公司确定，当用这笔资金购买若干种资产时，总体风险可用所投资的Si中最大的一个风险来度量。 购买Si要付交易费，费率为pi，并且当购买额不超过给定值ui时，交易费按购买ui计算（不买当然无须付费）。另外，假定同期银行存款利率是r0, 且既无交易费又无风险。（ r0 =5%）nullnullnull2006东北三省建模联赛赛题2006东北三省建模联赛赛题B题（研究生、本科生）公平的竞赛评卷系统 数学建模竞赛吸引了众多的大学生、研究生甚至中学生的参与，越来越多的人关心竞赛评卷的公平性。现今大多数的评卷工作是这样进行的：先将答卷编成密号，评委由各参赛学校（20-50所）派出，按不同的题目分成几个题组，每个题组由M个评委组成，评阅N份答卷，每份答卷经L个评委评阅，评委对每份答卷给出等级分（A+，A，A-，B+，B，B-，C+ ，C，C-，D），如果L个评委给出的分数基本一致，就给出这份答卷的平均分，否则需讨论以达成一致（其中M = 5-10，N = 60-200，L = 3-5）。现在需要你解决如下问题：null1．有A,B,C,D四个题目，P（P ≥ M）所学校参赛，给出一种答卷编号加密和解密的数学公式方法（其中题号为明号）；要求方法简单易算、可随意变换且保密性能好；对你的方法给出分析。 2．每个题组的M个评委来自不同学校，给出一种评阅答卷分配的数学公式方法，要求回避本校答卷，并且每个评委评阅的答卷尽可能广泛，并满足某些特殊的要求。 3．给出评分一致性或公正性的检验方法，该方法要求对每个评委的公平性给出评价（某评委分数普遍给的偏高或低属于尺度偏差，不应算作不公平，可在下面的问题中调整）。null4．给出最终的分数调整计算公式。该公式要处理那些可能出现的“不公平”，及尺度偏差。对可能出现的“不公平”构造例子，说明你的方法。 5．对评卷中的其他问题（如采用百分制还是等级分，一份答卷由几个评委评阅可以满足既经济又公平，等等）提出你的看法和根据。 6．假定有35所学校298个参赛队参赛，数据如附表。 其中：数字前两位代表学校，甲组选做A，B题；乙组选做C，D题； 25名评委所属的学校编号为：1-17，20，21，22，24，26，28，29，30。null每份试卷经四位评委评阅，编号为15，22的只容许评C，D题，编号为26的只容许评A，B题，编号为1，4，6，12，16的评委要求评A题，编号为2，5，7，10的评委要求评B题；编号为24的评委要求评C题，编号为29的评委要求评D题。其余按所在学校的甲、乙组别及个人的要求安排。 要求对问题1，2给出具体的算法及结果。对问题3，4，5给出模拟数据再进行分析和运算。 数据全国高校研究生数学建模竞赛赛题全国高校研究生数学建模竞赛赛题2006D：学生面试问题 高校自主招生是高考改革中的一项新生事物，现在仍处于探索阶段。某高校拟在全面衡量考生的高中学习成绩及综合表现后再采用专家面试的方式决定录取与否。该校在今年自主招生中，经过初选合格进入面试的考生有N人，拟聘请老师M人。每位学生要分别接受4位老师（简称该学生的“面试组”）的单独面试。面试时，各位老师独立地对考生提问并根据其回答问题的情况给出评分。由于这是一项主观性很强的评价工作，老师的专业可能不同，他们的提问内容、提问方式以及评分习惯也会有较大差异，因此面试同一位考生的“面试组”的具体组成不同会对录取结果产生一定影响。为了保证面试工作的公平性，组织者提出如下要求：nullY1. 每位老师面试的学生数量应尽量均衡； Y2. 面试不同考生的“面试组”成员不能完全相同； Y3. 两个考生的“面试组”中有两位或三位老师相同的情形尽量的少； Y4. 被任意两位老师面试的两个学生集合中出现相同学生的人数尽量的少。 请回答如下问题： 问题一：设考生数N已知，在满足Y2条件下，说明聘请老师数M至少分别应为多大，才能做到任两位学生的“面试组”都没有两位以及三位面试老师相同的情形。null问题二：请根据Y1～Y4的要求建立学生与面试老师之间合理的分配模型，并就N＝379，M＝24的情形给出具体的分配 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 （每位老师面试哪些学生）及该方案满足Y1～Y4这些要求的情况。 问题三：假设面试老师中理科与文科的老师各占一半，并且要求每位学生接受两位文科与两位理科老师的面试，请在此假设下分别回答问题一与问题二。 问题四：请讨论考生与面试老师之间分配的均匀性和面试公平性的关系。为了保证面试的公平性，除了组织者提出的要求外，你们认为还有哪些重要因素需要考虑，试给出新的分配方案或建议。 Matlab优化工具箱 （Optimization toolbox） Matlab优化工具箱 （Optimization toolbox） attgoal： 求解多目标优化问题. constr： 求解约束非线性优化问题. fmin： 求解标量非线性优化问题. fminu,fmins：求解无约束非线性优化问题. lp： 求解线性规划问题. minmax： 求解最小最大问题. qp： 求解二次规划问题. seminf： 求解半无限问题. conls： 求解线性约束最小二乘最优解. curvefit： 非线性数据拟合. leastsq： 求解非线性最小二乘最优问题. nnls： 求解非负约束最小二乘最优解 nullnullnull线性规划MATLAB程序线性规划MATLAB程序模型： Min z = cTx s.t. Ax ≤b v1≤ x ≤v2 x=lp (c,A,b,v1,v2, x0,ne,dis) v1,v2---- x 的下,上界 x0 ---- 初始值 ne ---- 前 ne 个约束为等式约束 dis ---- 给出警告信息，如解无界或无可行解 缺省时 用 [ ] 占据其位置，程序将自动给出无约束非线性规划MATLAB程序无约束非线性规划MATLAB程序模型： Min f（x） x=fminu (‘fun’,x0,opt,’grad’,p1,p2) [x, opt]=fminu (‘fun’,x0,opt,’grad’,p1,p2) ‘fun’ ---- 建立 fun.m 函数文件 x0 ---- 初始值 opt ----控制参数 ’grad’----建立 grad .m 函数文件计算梯度 p1,p2----可传递到 fun 和 grad 中公用的参数 （最多10个） 缺省时 用 [ ] 占据其位置，程序将自动给出约束非线性规划MATLAB程序约束非线性规划MATLAB程序模型： Min f（x） S.t. g（x）≤ 0 x =constr (‘fun’,x0,opt,v1,v2,’grad’,p1,p2) [x, opt]=constr(‘fun’,x0,opt,v1,v2,’grad’,p1,p2) ‘fun’ ---- 建立 fun.m 函数文件: [ f，g ] = fun (x) x0 ---- 初始值 opt ----控制参数 v1,v2----x的下,上界 ’grad’----建立grad .m 函数文件计算梯度 [ df，dg ] = grad (x) p1,p2----可传递到fun和grad中公用的参数（最多10个） 缺省时 用 [ ] 占据其位置，程序将自动给出