下载文档原格式
数学建模第二讲简单的优化模型数学建模是利用数学方法对实际问题进行建模、分析和求解的过程。
在实际问题中，常常需要针对一些指标进行优化，以达到最优的效果。
本讲将介绍一些简单的优化模型。
一、线性规划模型线性规划是一种重要的数学优化方法，广泛应用于工程、经济、管理等领域。
其数学模型可以表示为：\begin{aligned}&\text{max} \quad c^Tx \\&\text{s.t.} \quad Ax \leq b, \quad x \geq 0\end{aligned}\]其中，$x$为决策变量，$c$为目标函数系数，$A$为约束条件系数矩阵，$b$为约束条件右端向量。
线性规划模型指的是目标函数和约束条件都是线性的情况。
通过线性规划模型，可以求解出使得目标函数取得最大（或最小）值时的决策变量取值。
二、非线性规划模型非线性规划模型指的是目标函数或约束条件中存在非线性部分的情况。
非线性规划模型相对于线性规划模型更为复杂，但在实际问题中更为常见。
对于非线性规划问题，通常采用数值优化方法进行求解，如梯度下降法、牛顿法等。
这些方法通过迭代的方式逐步靠近最优解。
三、整数规划模型整数规划模型是指决策变量必须为整数的规划模型。
整数规划在实际问题中应用广泛，如物流配送问题、工程调度问题等。
整数规划模型通常难以求解，因为整数规划问题是一个NP难问题。
针对整数规划问题，常用的求解方法有枚举法、分支定界法、遗传算法等。
四、动态规划模型动态规划模型是指将问题划分为子问题，并通过求解子问题最优解来求解原问题最优解的方法。
动态规划通常用于求解具有重叠子问题和最优子结构性质的问题。
动态规划模型具有递推性质，通过递归或迭代的方式求解子问题的最优解，并保存中间结果，以提高求解效率。
五、模拟退火模型模拟退火是一种用来求解组合优化问题的随机优化算法。
模拟退火算法基于固体退火过程的模拟，通过温度的控制和随机跳出来避免陷入局部最优解。
优化模型在生活中的应用人类生活在丰富多彩、变化万千的现实世界里，无时无刻不在运用智慧和力量去认识、利用、改造这个世界，从而不断地创造出日新月异、五彩缤纷的物质文明和精神文明。
而在我们认识、利用和改造世界时我们往往离不开数学方法，数学建模则是利用数学方法解决实际问题的一种实践。
通过抽象,简化、假设、引进变量等处理过程后，将实际问题用数学方式表达，建立起数学模型，然后运用先进的数学方法及计算机技术进行求解。
人们生活是离不开数学的，衣食住行等各个方面都需要数学，倘若能在这些实际问题中建立各种各样的比较典型的数学模型，在遇到生活中的这些琐碎小事时，就能更高效、更正确地进行处理了。
必须说明的是，建立数学模型需要用系统的某种特征的本质的数学表达式（或是用数学术语）对部分现实世界的描述即用数学式子（如函数，图形，代数方程，微分方程，积分方程，差分方程等）来描述所研究的客观对象或系统在某一方面的存在规律。
优化模型是生活过程中必须用到的的数学模型，其建立目的就是为了得到最大化的工作效益以及减少投资等一系列最优条件。
一般来说，我们在生活中经常应用这种模型，却没有将其抽象出来，明文对其进行规定。
1.模型类型说明举例在姜启源先生等人主编的《数学模型》一书中提到过这样一个例子：“一饲养场每天投入4元资金用于饲料、设备、人力，估计可使一头80公斤重的生猪每天增加2公斤．目前生猪出售的市场价格为每公斤8元，但是预测每天会降低0．1元，问该场应该什么时候出售这样的生猪。
”在上述描述中，我们将设计到的特征，用数值明确地表示出来，通过构建数学式子便可很快的计算出最佳的出售时机。
建模解答过程如下：模型假设每天投入4元资金使生猪体重每天增加常数r(=2公斤)；生猪出售的市场价格每天降低常数g(=0．1元)．模型建立给出以下记号：t ～时间(天)．w ～生猪体重(公斤)；~p 单价 (元／公斤)；R-出售的收入(元)；C-t 天投入的资金(元)；Q-纯利润(元)．按照假设，)1.0(8),2(80=-==+=g gt p r rt w ．又知道t C pw R 4,==，再考虑到纯利润应扣掉以当前价格(8元／公斤)出售80公斤生猪的收入，有808⨯--=C R Q ，得到目标函数(纯利润)为其中1.0,2==g r ．求)0(≥t 使)(t Q 最大．模型求解这是求二次函数最大值问题，用代数或微分法容易得到当1.0,2==g r 时，20)10(,10==Q t ，即10天后出售，可得最大纯利润20元．2.模型实际应用举例上述实例属于优化模型，在日常生活过程中，我们常常会遇到与之类似的问题，比如购物时如何花最少的钱挑选最合适的商品，外出旅游时如何调节出行费用与参观门票等等，通过这种优化模型，在相关的条件限制下，就可以的到一个最值，是我们得到最大的方便与利益。
04章组合优化模型组合优化模型是指在给定一组有限资源的情况下，通过选择和组合这些资源，以达到其中一种目标的问题。
这一类模型广泛应用于供应链管理、制造业生产优化和物流网络设计等领域。
本文将介绍几种常见的组合优化模型，并分析其应用。
一、背包问题背包问题是最基本的组合优化问题之一、背包问题可以描述为在给定一组物品和一个固定容量的背包的情况下，如何选择物品放入背包中，以使得背包中物品的总价值最大。
背包问题可以有多种变形，如01背包问题、完全背包问题和多重背包问题等。
例如，假设有一个容量为C的背包，和n个物品，每个物品有一个重量wi和一个价值vi。
目标是在背包容量限制下，选择一些物品放入背包中，使得背包中物品的总价值最大。
背包问题可以通过动态规划算法求解。
定义一个二维数组dp，其中dp[i][j]表示在前i个物品中选择一些放入容量为j的背包中所能达到的最大总价值。
背包问题的状态转移方程可以表示为：dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi] + vi)二、旅行商问题旅行商问题是一个经典的组合优化问题，也是一个NP-hard问题。
旅行商问题可以描述为在给定一组城市和每对城市之间的距离，如何找到一条最短的路径，使得每个城市只访问一次，并且最终回到起始城市。
旅行商问题可以通过深度优先、分支定界算法和遗传算法等方法求解。
尽管求解旅行商问题的确切解决方案是困难的，但通过使用近似算法和启发式算法，可以在合理的时间内得到较好的解。
三、作业调度问题作业调度问题是指在给定一组作业和一组机器的情况下，如何安排作业在机器上执行，以最大程度地减少完成所有作业的总时间。
作业调度问题可以通过贪心算法和动态规划算法求解。
贪心算法可以按照一些优先级规则对作业进行排序，并依次将作业分配给空闲的机器，直到所有作业都被分配完为止。
动态规划算法可以定义一个二维数组dp，其中dp[i][j]表示前i个作业在j个机器上执行的最小总时间。
第六讲、系统优化模型1. 在系统工程学科中的地位2. 模转换函数型对象：最优化问题，举例说明1) 食谱问题设市场上可以买到n 种不同的食品，第j 种食品的价格为j c ，每种食品含有m 种营养成份，每单位第j 种食品含第i 种营养成份为ij a 。
假设每人每天对第i 种营养成份的需要量不少于i b ，试确定在保证营养条件下的最经济食谱。
设每人每天对n 种食品的需要量为：n x x x ,,,21⋅⋅⋅，则相应的伙食费为：n n x c x c x c +⋅⋅⋅++2211保证满足营养最小的需求约束方程为：i n in i i b x a x a x a ≥+⋅⋅⋅++2211 m i ,,2,1⋅⋅⋅= 0≥j x n j ,,2,1L =则数学模型为：min n n x c x c x c +⋅⋅⋅++2211t s . 11212111b x a x a x a n n ≥+⋅⋅⋅++ 22222121b x a x a x a n n ≥+⋅⋅⋅++ …………………………m n mn m m b x a x a x a ≥+⋅⋅⋅++2211 0≥j x n j ,,2,1L =如果令 T n x x x x ),,,(21L =),,,(21n c c c c L = n m ij a A ×=)( T m b b b b ),,,(21L =则上面的优化模型可以写成如下矩阵形式：min cxt s . 0,≥≥x b Ax2) 结构设计问题设两杆组成的对称衔架如下图所示，已知衔架的跨度为2L ，高度2x 的上限为H ，承受负荷2P ，钢管的厚度为T ，材料比重ρ，纵向弹性系数为E 且允许应力y σ，试确定钢管的平均厚度1x 和衔架高度2x 并使衔架重量最小。
Y-Y 剖面衔架的重量为：2/12221)(2x L Tx G +=πρ平均内径1x 和高度2x 满足如下约束：z 高度约束： H x ≤2z 钢管压应力约束：在负荷2P 的作用下，钢管承受的压力F 为22/1222)(cos x x L P PF +==θ 钢管的横截面面积S 为 1Tx s π≈ 因此，钢管的压应力为212/122221)(),(x Tx x L P x x πσ+=所以对给定的允许应力y σ，要求y x Tx x L P σπ≤+212/1222)(z 临界应力约束：假设弹性模数为E ，则利用欧拉公式可以算出临界应力l σ为)(8)(2222212x L T x E l ++=πσ 因此，要求)(8)()(2222212212/1222x L T x E x Tx x L P ++≤+ππ 综上所述，衔架设计问题的最优化模型为min 2/12221)(2x L Tx +πρt s . H x ≤2y x Tx x L P σπ≤+212/1222)()(8)()(2222212212/1222x L T x E x Tx x L P ++≤+ππ 0,021≥≥x x3) 水果采购问题某单位举行联欢会要采购香蕉、苹果和葡萄，假设市场上香蕉、苹果和葡萄的价格分别为4.2元/公斤、2.4元/公斤、2.2元/公斤，如果要求采购水果的钱不超过300元、水果总重量不小于10公斤、香蕉和苹果总和不小于6公斤，试确定最好的采购方案。
优化问题建模举例例1：组合投资问题：总金额1000万美圆的资金，用于投资四种债券。
已知债券年收益率期望值/%债券113债券28债券312债券414年收益率最低值/%持续期/年6 38 410 79 9希望年收益率期望值达到最大，并且满足下列要求：1）组合投资的年收益率最低值至少为8%;2）组合投资的平均持续期至多为6年（各债券的投资百分比乘持续期，之和）；3）任一债券的投资百分比至多为40% .怎样投资？解:四种债券的投资金额是待定的决策变量，分别记为为公2山3,& ；目标是年收益率期望值最大；题中的三条要求是约束条件。
得下面优化模型：max 0.13x-i 0.08x2 0.12x3 0.14x4 .s.t. x1 x2 x3 x4 = 1000,2x1 - 2x3 - X4 — 0,-3为一2X2 x3 3x4乞0,0 辽x“ x2, x3, x4咗400 .（在这个模型中，决策变量都是线性的，故称为线性规划）例2：某学校游泳队要从5名队员中选4名参加4乘100米混合泳接力赛。
5名队员4种泳姿的百米成绩（单位：秒）李王张刘赵蝶泳66.857.2787067.4仰泳75.66667.874.271蛙泳8766.484.669.683.8自由泳58.65359.457.262.4如何选拔？（1）请建立“ 0----1规划”模型;（2）用Lin go求解。
解：若第i名队员参加第j种泳姿比赛，则令为=1 ;否则令为=0 ；共有20个决策变量X j。
第i 名队员的第j种泳姿成绩记为q，则5 4目标函数为：mi n C j X ijy 2约束条件有：每名队员顶多能参加一种泳姿比赛4、x— 1, i =1,2,3,4,5 ；j丄5每种泳姿有且仅有一人参加' X ij "j =123,4i丄这样就能建立如下“0----1 规划”模型：5 4min 二二cij Nji 4 j4s.t. ' x ij乞1, i =1,2,3,4,5j」5' X j = 1 , j 二1,2,3,4 .i 4例3：某帆船制造公司要决定下两年八个季度的帆船生产量。
