第四章 最优化问题主讲：陈元安 商丘职业技术学院商丘职业技术学院爱因斯坦的一句名言：想象力比知识更重要！因为知识是有限的，而想象力包括世界的一切，是知识的源泉。要 点历年回顾:92A题施肥效果分析 回归分析 数据拟合 92B题实验数据分解 离散模型、组合最优化 93A非线性交调的频率设计 拟合、规划 93B足球队排名 图论、层次分析、整数规划 94A逢山开路 图论、插值、动态规划 94B锁具装箱问题 图论、组合数学 95A飞行管理问题 非线性规划、线性规划 95B天车与冶炼炉的作业调度 动态规划、排队论、图论 96A最优捕鱼策略 微分方程、优化 96B节水洗衣机 非线性规划 97A零件的参数设计 非线性规划 97B截断切割的最优排列 随机模拟、图论 98A一类投资组合问题 多目标优化、非线性规划 98B灾情巡视的最佳路线 图论、组合优化 99A自动化车床管理 随机优化、计算机模拟 99B钻井布局 0-1规划、图论 00A DNA序列分类 模式识别、Fisher判别、人工神经网络 00B钢管订购和运输 组合优化、运输问题 01A血管三维重建 曲线拟合、曲面重建 01B 公交车调度问题 多目标规划 02A车灯线光源的优化 非线性规划 02B彩票问题 单目标决策 03A SARS的传播 微分方程、差分方程 03B 露天矿生产的车辆安排 整数规划、运输问题 04A奥运会临时超市网点设计 统计分析、数据处理、优化 04B电力市场的输电阻塞管理 数据拟合、优化 05A长江水质的评价和预测 预测评价、数据处理 05B DVD在线租赁 随机规划、整数规划 06A出版社书号问题 整数规划、数据处理、优化 06B Hiv病毒问题 线性规划、回归分析 07A 人口问题 微分方程、数据处理、优化 07B 乘公交，看奥运 多目标规划、动态规划、图论0-1规划 08A 照相机问题 非线性方程组、优化 08B 大学学费问题 数据收集和处理、统计分析、 回归分析 09A 制动器试验台的控制方法分析 微元分析法 09B 眼科病床的合理安排 层次分析法 整数规划 动态 规划 排队论 10A 储油罐的变位识别与罐容表标定 非线性规划 多元 拟合 10B 2010年上海世博会影响力的定量评估 数据收集和 处理，层次分析法 时间序列分析解 法规划 问题图 论差微 分方 程数据拟合 模拟处 理优化数据 分析 理论其它 （排 队运 输离 散 ） 相关 赛 题93A,93B 94A,95A 95B,96B 97A,98A 99B,01B 02A,03B 06A,06B 07B,09B 10A93B 94A 94B 95B 97B 98B 99B 07B96A 03A 07A 08A 09A92A,93A 97B,99A 01A,04A 04B,05A 06A,07A 08B,10A 10B92B,96A 98A,98B 99A,00B 02B,04A 04B,06A 07A,08A93B 04A 09A 09B 10B92B 94A 94B 95B 00A 00B合 计1785131266赛题发展的特点： 1. 对选手的计算机能力提出了更高的要求：赛题 的解决依赖计算机，题目的数据较多，手工计算 不能完成，如03B，某些问题需要使用计算机软件 ，01A。问题的数据读取需要计算机技术，如00A （大数据），01A（图象数据，图象处理的方法获 得），04A（数据库数据，数据库方法，统计软件 包）。计算机模拟和以算法形式给出最终结果。 2. 赛题的开放性增大解法的多样性，一 道赛题可用多种解法。开放性还表现在 对模型假设和对数据处理上。 3. 试题向大规模数据处理方向发展 4. 求解算法和各类现代算法的融合， 5.更关注于当年的实事问题eg：04A奥运 会临时超市网点设计，07B 乘公交，看 奥运，10B 2010年上海世博会影响力的 定量评估等； 引言 4.1 线性规划模型 4.2 整数规划模型 4.3 二次规划模型 4.4 非线性规划模型 4.5 应用案例：抢渡长江问题 4.6 应用案例练习 4.7 最优化软件一、引言我们从2005年“高教社杯”全国大学生数模竞谈起.其中第二个问题是一个如何来分配有限资源，从而达到人们期望目标的优化分配数学模型. 它在数学建模中处于中心的地位. 这类问题一般可以归结为 数学规划模型.赛的B题“DVD在线租赁”问题的第二问和第三问 规划模型的应用极其广泛，其作用已为越来越多 的人所重视.随着计算机的逐渐普及，它越来越急 速地渗透于工农业生产、商业活动、军事行为核 科学研究的各个方面，为社会节省的财富、创造 的价值无法估量. 在数模竞赛过程中，规划模型是最常见的一类数 学模型. 从92-2011年全国大学生数模竞赛试题的 解题方法统计结果来看，规划模型共出现了16次 ，占到了近50%，也就是说每两道竞赛题中就有 一道涉及到利用规划理论来分析、求解. 最优化是一门应用十分广泛的学科，它研究在 有限种或无限种可行方案中挑选最优方案，构 造寻求最优解的计算方法。达到最优目标的方 案，称为最优方案，搜索最优方案的方法，称 为最优化方法。这种方法的数学理论，称为最 优化理论。 最优化方法已广泛应用于空间技术、军事科学 、电子工程、通讯工程、自动控制、系统识别 、资源分配、计算数学、经济管理等等领域。 最优化方法包括的内容很广泛，如线性规划、 非线性规划、整数规划、动态规划、多目标规 划、组合优化等等。 在实际生活当中，人们做任何事情，不管是分析问题，还是进行决策，都要用一种标准衡量一下是否达到了最优。 （比如基金人投资） 在各种科学问题、工程问题、生产管理、社会经济问题中，人们总是希望在有限的资源条件下，用尽可能小的代价，获得最大的收获。（比如保险） 运用最优化方法解决最优化问题的一般方法步骤 如下： 前期分析：分析问题，找出要解决的目标，约 束条件，并确立最优化的目标。 定义变量，建立最优化问题的数学模型，列出 目标函数和约束条件。 针对建立的模型，选择合适的求解方法或数学 软件。 编写程序，利用计算机求解。 对结果进行分析，讨论诸如：结果的合理性、 正确性，算法的收敛性，模型的适用性和通用 性，算法效率与误差等。线线 性性 规规 划划某豆腐店用黄豆制作两种不同口感的豆 腐出售。制作口感较鲜嫩的豆腐每千克 需要0.3千克一级黄豆及0.5千克二级黄 豆，售价10元；制作口感较厚实的豆腐 每千克需要0.4千克一级黄豆及0.2千克 二级黄豆，售价5元。现小店购入9千克 一级黄豆和8千克二级黄豆。 问：应如何安排制作计划才能获得最大 收益。一、问题前期分析 该问题是在不超出制作两种不同口感豆腐所需黄豆总量条件下合理安排制 作计划，使得售出各种豆腐能获得最大收益。 二、模型假设 1假设制作的豆腐能全部售出。 2假设豆腐售价无波动。变量假设：设计划制作口感鲜嫩和厚实的豆腐各x1千克和 x2千克，可获得收益R 元。目标函数：获得的总收益最大。 总收益可表示为： 受一级黄豆数量限制： 受二级黄豆数量限制： 综上分析，得到该问题的线性规划模型 s.t. LINGO程序： max=10*x1+5*x2; 0.3*x1+0.4*x22 ;st4x12+x224 ;st5x13+x235 ; end运行结果Global optimal solution found.Objective value: 160.0000Total solver iterations: 5Variable Value Reduced CostX11 2.000000 0.000000X12 0.000000 28.00000X13 2.000000 0.000000X21 0.000000 2.000000X22 4.000000 0.000000X23 3.000000 0.000000Row Slack or Surplus Dual Price1 160.0000 -1.0000002 0.000000 16.000003 1.000000 0.0000004 0.000000 -28.000005 0.000000 -12.000006 0.000000 -24.00000模型标准化 程序编写MODEL: TITLE 调调运大米的运输问题输问题 程序;!定义义集合段;SETS:HANG/15/:B;!定义义矩阵阵的行;LIE/111/:C,X;!定义义矩阵阵的列以及变变量;XISHU(HANG,LIE):A;!定义约义约 束的系数矩阵阵;ENDSETS !定义义数据段;DATA:A= 1 1 1 0 0 0 1 0 0 0 0!系数矩阵赋值阵赋值 ;0 0 0 1 1 1 0 1 0 0 01 0 0 1 0 0 0 0 -1 0 00 1 0 0 1 0 0 0 0 -1 00 0 1 0 0 1 0 0 0 0 -1;C=12 24 8 30 12 0 24 0 0 0 0 0;!目标标函数的系数;B=4 8 2 4 5;!约约束的右端项项;ENDDATA!标标准形式的目标标函数的矩阵阵形式;OBJMIN=SUM(LIE:C*X);FOR(HANG(I):YUESHUSUM(LIE(J):A(I,J)*X(J)=B(I); END程序编写 推荐 模型 M