下载文档原格式
数学建模的主要建模方法数学建模是指运用数学方法和技巧对复杂的实际问题进行抽象、建模、分析和求解的过程。
它是解决实际问题的一个重要工具，在科学研究、工程技术和决策管理等领域都有广泛的应用。
数学建模的主要建模方法包括数理统计法、最优化方法、方程模型法、概率论方法、图论方法等。
下面将分别介绍这些主要建模方法。
1.数理统计法：数理统计法是基于现有的数据进行概率分布的估计和参数的推断，以及对未知数据的预测。
它适用于对大量数据进行分析和归纳，提取有用的信息。
数理统计法可以通过描述统计和推断统计两种方式实现。
描述统计主要是对数据进行可视化和总结，如通过绘制直方图、散点图等图形来展示数据的分布特征；推断统计则采用统计模型对数据进行拟合，进行参数估计和假设检验等。
2.最优化方法：最优化方法是研究如何在给定的约束条件下找到一个最优解或近似最优解的方法。
它可以用来寻找最大值、最小值、使一些目标函数最优等问题。
最优化方法包括线性规划、非线性规划、整数规划、动态规划等方法。
这些方法可以通过建立数学模型来描述问题，并通过优化算法进行求解。
3.方程模型法：方程模型法是通过建立数学方程或函数来描述问题，并利用方程求解的方法进行求解。
这种方法适用于可以用一些基本的方程来描述的问题。
方程模型法可以采用微分方程、代数方程、差分方程等不同类型的方程进行建模。
通过求解这些方程，可以得到问题的解析解或数值解。
4.概率论方法：概率论方法是通过概率模型来描述和分析不确定性问题。
它可以用来处理随机变量、随机过程和随机事件等问题。
概率论方法主要包括概率分布、随机变量、概率计算、条件概率和贝叶斯推理等内容。
利用概率论的方法，可以对问题进行建模和分析，从而得到相应的结论和决策。
5.图论方法：图论方法是研究图结构的数学理论和应用方法。
它通过把问题抽象成图，利用图的性质和算法来分析和求解问题。
图论方法主要包括图的遍历、最短路径、最小生成树、网络流等内容。
数学建模案例之多变量无约束最优化多变量无约束最优化问题是指在变量间没有限制条件的情况下，求解目标函数的最优值。
这类问题在数学建模中非常常见，实际应用非常广泛。
下面以一个实际案例说明多变量无约束最优化的建模过程。
假设地有几个旅游景点，现在需要制定一个旅游路线，使得游客的游玩时间最长，同时经济成本最低。
已知每个旅游景点之间的距离和游玩时间，以及游客每次游玩每公里所需的成本。
目标是找到一条旅游路线，使得游客在游览所有景点后，花费的经济成本最少。
首先，我们需要定义问题的数学模型。
假设有n个旅游景点，用x1, x2, ..., xn表示每个景点的游玩时间（单位：小时），用dij表示第i个景点和第j个景点之间的距离（单位：公里），用c表示游客游玩每公里所需的成本。
为了定义问题的数学模型，我们需要明确如下几个关键部分：1. 决策变量：定义一个n维向量X，其中每一个分量xi表示游客在第i个景点的游玩时间。
2. 目标函数：定义一个目标函数f(X)，表示游客花费的经济成本。
在本例中，目标函数可以定义为：f(X) = ∑dij * xi * c。
3.约束条件：由于是无约束最优化问题，这里没有额外的约束条件。
有了以上几个关键部分，我们可以将问题的数学模型表达为如下形式：最小化：f(X) = ∑dij * xi * c其中，i=1,2,...,n下一步是求解这个最优化问题。
可以使用各种数值优化算法，比如梯度下降法、牛顿法、遗传算法等。
具体的求解过程会涉及到算法的具体细节，这里不再详述。
最后，根据求解结果，我们可以得到游玩时间最长且经济成本最低的旅游路线。
这条路线就是我们需要制定的旅游路线。
总结起来，多变量无约束最优化问题在数学建模中的应用非常广泛。
通过定义合适的决策变量、目标函数和约束条件，可以将实际问题转化为数学模型，并通过数值优化算法求解这个模型，得到最优解。
在实际应用中，对于复杂的问题，可能需要结合多种算法和技巧来求解。
习题六1、某工厂生产四种不同型号的产品，而每件产品的生产要经过三个车间进行加工，根据该厂现有的设备和劳动力等生产条件，可以确定各车间每日的生产能力（折合成有效工时来表示）。
现将各车间每日可利用的有效工时数，每个产品在各车间加工所花费的工时数及每件产品可获得利润列成下表：试确定四种型号的产品每日生产件数,,,,4321x x x x 使工厂获利润最大。
2、在车辆拥挤的交叉路口，需要合理地调节各车道安置的红绿灯时间，使车辆能顺利、有效地通过。
在下图所示的十字路口共有6条车道，其中d c b a ,,,是4条直行道，f e ,是两条左转弯道，每条车道都设有红绿灯。
按要求制定这6组红绿灯的调节方案。
首先应使各车道的车辆互不冲突地顺利驶过路口，其次希望方案的效能尽量地高。
即各车道总的绿灯时间最长，使尽可能多的车辆通过。
da bc 提示：将一分钟时间间隔划分为4321,,,d d d d 共4个时段，()()()f J b J a J ,,, 为相应车道的绿灯时间。
()d J3、某两个煤厂A 和B 每月进煤量分别为60吨和100吨，联合供应三个居民区C 、D 、E 。
这三个居民区每月对煤的需求量依次分别是50吨、70吨、40吨。
煤厂A 与三个居民区C 、D 、E 的距离分别为10公里、5公里和6公里。
煤厂B 与三个居民区C 、D 、E 的距离分别为4公里、8公里和12公里。
问如何分配供煤量可使运输总量达到最小？4、某工厂制造甲、乙两种产品，每种产品消耗煤、电、工作日及获利润如下表所示。
现有煤360吨，电力200KW.h ，工作日300个。
请制定一个使总利润最大的生产计划。
5、棉纺厂的主要原料是棉花，一般要占总成本的70%左右。
所谓配棉问题，就是要根据棉纱的质量指标，采用各种价格不同的棉花，按一定的比例配制成纱，使其既达到质量指标，又使总成本最低。
棉纱的质量指标一般由棉结和品质指标来决定。
这两项指标都可用数量形式来表示。
数学建模分配问题模型数学建模是一种通过数学方法解决实际问题的方法。
在实际生活中，我们经常会遇到分配问题，即将一定数量的资源分配给不同的需求方。
这些资源可以是金钱、人力、材料等，需求方可以是个人、企业、机构等。
为了合理地分配资源，我们可以使用数学建模的方法进行分析和优化。
一般来说，分配问题可以分为两类：最优化问题和约束问题。
最优化问题的目标是使得某个指标达到最大或最小值，比如最大化利润、最小化成本等。
约束问题则是在一定的条件下寻找满足需求的最优解。
下面我们将分别介绍这两类问题的数学建模方法。
对于最优化问题，我们首先需要确定一个目标函数。
目标函数描述了我们希望优化的指标，可以是一个或多个变量之间的函数关系。
然后，我们需要确定一组约束条件。
约束条件反映了资源的限制以及需求方的限制，可以是等式或不等式。
最后，我们需要确定决策变量，即需要分配的资源量或决策方案。
通过求解目标函数在约束条件下的最优解，就可以得到最佳的分配方案。
以货物运输为例，假设有一批货物需要从仓库分配给不同的销售点，我们希望通过最优化分配来降低运输成本。
我们可以将每个销售点的需求量作为约束条件，将货物的运输成本作为目标函数。
然后，我们需要确定每个销售点的分配量作为决策变量，通过求解目标函数在约束条件下的最优解，就可以得到最佳的分配方案，从而降低运输成本。
对于约束问题，我们需要确定一组约束条件，这些条件可能是资源的限制、需求方的限制或其他限制。
然后，我们需要确定决策变量，即需要分配的资源量或决策方案。
通过在约束条件下寻找满足需求的最优解，就可以得到合理的分配方案。
以人力资源分配为例，假设有一定数量的员工需要分配到不同的项目中，每个项目对员工的技能要求不同。
我们希望通过合理的分配来最大化项目的效益。
我们可以将每个项目的效益作为约束条件，将员工的技能水平作为决策变量。
通过在约束条件下寻找满足需求的最优解，就可以得到最佳的分配方案，从而最大化项目的效益。
输油管布置的优化模型摘要本文建立了输油管线布置的优化问题.为了使两家炼油厂到铁路线上增建的车站的管线铺设费用最省，依据题目提供的有关数据及相关信息，设计出了总费用最少的输油管布置方案以及增建车站的具体位置，最终在讨论分析后，对模型做出了评价和推广.模型Ⅰ：对问题1,根据两炼油厂到铁路线距离和两炼油厂间的不同距离以及共用管线与非共用管线的两种不同情况，给出了四种处理方案，并从图形上加以说明.模型Ⅱ：对问题2,建立了最优模型.在单目标非线性规划模型中，将输油管道铺设分为两个过程.先将输油管道从城区铺设到城郊区域边界线上一点，再从该点铺设到铁路线上.这样，总的费用就化为这两个过程的管道费用之和.本模型兼顾到管线的铺设费用，在城区铺设管线需增加的拆迁和工程补偿等附加费用，运用Lingo9.0数学软件得到新增车站的建设位置、管线的具体布置方案及管线费用最小值281.6893万元.模型Ⅲ：根据炼油厂的实际能力，借助题目提供的输送A、B两厂原油的管线铺设费用，在模型Ⅱ的基础上建立最优模型，给出管线最佳布置方案及相应的最省管线铺设费用为250.9581万元.关键词：输油管共用管线非共用管线 Lingo9.0 非线性规划一、问题重述某油田计划在铁路线一侧建造两家炼油厂，同时在铁路线上增建一个车站，用来运送成品油。
由于这种模式具有一定的普遍性，油田设计院希望建立管线建设费用最省的一般数学模型和方法。
现欲解决下列问题：问题1：针对炼油厂到铁路线距离和两炼油厂间距离的各种不同情形，提出设计方案。
在方案设计时，若有共用管线，考虑共用管线与非共用管线相同或不同的情形。
问题2：设计院目前需对一更为复杂的情形(两炼油厂的具体位置)进行具体的设计。
两炼油厂的具体位置如下图：若所有管线的费用均为7.2万元/千米。
铺设在城区的管线还需增加迁拆和工程补偿等附加费用，为对此附加费用进行估计，聘请三家工程咨询公司(其中一具有甲级资质，公司二和公司三具有乙级资质)进行了估算。
数学建模案例之单变量最优化生猪的最佳销售时间问题1：一头猪重200磅（1磅=0.454公斤），每天增重5磅，饲养每天需花费45美分。
猪的市场价格为每磅65美分，但每天下降0.01美元，求出售猪的最佳时间。
1．问题分析与假设、符号说明涉及的变量：猪的重量w（磅），饲养时间t≥０（天），t天内饲养猪的化费Q（美元），猪的市场价格p（美元/磅），售出生猪所获得的总收益R（美元），我们最终获得的净收益C（美元）。
涉及的常量：猪的初始重量200（磅），饲养每天的花费0.45（美元），生猪每天的增加重量s（磅），当前的市场价格0.65（美元），生猪价格每天的下降比例系数r。
变量之间的联系：假设1：猪的重量从初始的200（磅）按每天s=5（磅）增加，于是有关系：w（磅）=200（磅）+s（磅/天）×t（天）假设2：当前的市场价格0.65（美元/磅），生猪价格每天的下降比例系数r=0.01，那么出售时生猪的价格为：p（美元/磅）=0.65（美元/磅）- r（美元/磅.天）×t（天）因此，我们有如下关系式：饲养生猪的总的费用为：Q（美元）＝0.45（美元／天）×t（天）售出生猪时获得的总收益为：Ｒ（美元）＝ｐ（美元／磅）×ｗ（磅）最终获得的净收益为：C（美元）＝Ｒ（美元）－Q（美元）当生猪卖出时获得最大净收益的时间即为最佳出售时间，因此原问题转换成数学表述就是求Ｐ达到最大时的时间t≥0，其中P的表达式为：=-=⨯-⨯=-+-C t R t Q t p w t rt st t()()()0.45(0.65)(200)0.452．建立数学模型根据前面的分析，原问题的数学模型如下：max ()..()(0.65)(200)0.45,0C t s t C t rt st t t =-+-≥ （1.1）其中，r ，s 为模型参数，此处取值为s=5，r=0.01。
3．模型求解当s=5，r=0.01时，这是一个单变量t 的函数的最优化问题，而且()C t 是一个连续可微的函数。
数学建模动态优化模型数学建模是一种通过建立数学模型来解决实际问题的方法。
动态优化模型则是指在一定的时间尺度内，通过调整决策变量，使系统在约束条件下达到最优效果的数学模型。
本文将介绍数学建模中动态优化模型的基本原理、方法和应用。
动态优化模型是一种考虑时间因素的优化模型。
在解决实际问题时，往往需要考虑到系统随时间变化的特性，因此单纯的静态优化模型可能无法满足需求。
动态优化模型对系统的演化过程进行建模，通过引入时间因素，能够更准确地描述系统的行为，并找到最优的策略。
动态优化模型的核心是建立一个数学模型来描述系统的演化过程。
在建模过程中，需要确定决策变量、目标函数、约束条件和系统的动态特性。
决策变量是指在不同时间点上的决策变量值，目标函数是指目标的数量指标，约束条件是系统必须满足的条件，系统的动态特性是指系统状态随时间的变化规律。
动态优化模型的建模方法有很多种，常见的方法包括状态空间建模、差分方程建模和优化控制建模等。
其中，状态空间建模是一种通过描述系统状态和系统状态之间的关系来建立模型的方法；差分方程建模是一种通过描述离散时间点上系统的状态之间的关系来建立模型的方法；优化控制建模则是一种将优化方法和控制方法相结合的建模方法。
动态优化模型在实际问题中有广泛的应用。
例如，在生产调度问题中，我们需要根据不同时间的产销情况来安排生产任务，以使得产能得到充分利用并满足市场需求；在交通控制问题中，我们需要根据交通流量的变化来调整信号灯的配时方案，以最大程度地减少交通拥堵；在能源管理问题中，我们需要根据电网的负荷变化来调整发电机组的出力，以实现能源的有效利用。
在建立动态优化模型时，需要考虑到模型的复杂性和求解的难度。
一方面，动态优化模型往往比静态优化模型复杂，需要考虑到系统的动态特性和约束条件的演化；另一方面，求解动态优化模型需要考虑到系统的运行时间和求解算法的效率。
因此，在建立动态优化模型时，需要合理选择模型和算法，以保证模型的可行性和求解的可行性。
数学建模案例之单变量最优化在现实生活中，我们经常需要对一些变量进行优化，以获得最佳的结果。
这个过程就被称为单变量最优化。
在数学建模中，单变量最优化是一个非常常见的问题。
下面以公司海外销售业绩最大化为例，介绍单变量最优化的数学建模方法。
假设公司想要通过调整价格来提高其在海外市场的销售额。
现在，该公司销售一种产品，定价为P（单位：美元），该产品的销售量是一个衰减函数，即随着价格的上升，销售量逐渐减少。
为了简化问题，我们假设销售量Q（单位：件）与价格P之间的关系可以用一个二次函数来近似表示。
那么，我们可以将该问题建模为一个单变量最优化问题。
首先，我们需要找到销售量与价格之间的函数关系。
假设销售量与价格之间的关系可以用以下二次函数来表示：Q=aP^2+bP+c其中，a、b、c是待定系数。
接下来，我们需要根据已知的数据来确定这些系数的值。
假设我们已经知道了两个数据点，即在价格P1下销售量为Q1，价格P2下销售量为Q2、我们可以将这两个点代入上式，得到以下两个方程：Q1=aP1^2+bP1+cQ2=aP2^2+bP2+c通过解这个方程组，我们可以确定a、b、c的值。
具体的解法可以使用最小二乘法，即通过最小化误差平方和的方法，求得最佳的a、b、c的估计值。
接下来，我们需要确定如何调整价格来使销售额最大化。
为了简化问题，我们假设该公司的成本是固定的，并且每一件产品的利润是固定的。
那么，该公司的总利润可以表示为：Profit = (P - Cost) * Q其中，Cost是单位产品的成本，P是产品的价格，Q是销售量。
我们的目标是使总利润最大化。
通过将Profit表达式代入销售量与价格之间的函数关系，可以得到总利润关于价格的函数。
我们可以使用微分法来求解这个问题，即通过求导数来找到函数的驻点。
驻点处的导数为0，表示函数取得极值。
我们可以找到极值点来确定价格的最佳取值。
最后，我们可以使用数值方法，如牛顿法或二分法，来求得函数的极值点。
3 最优化方法许多生产计划与管理问题都可以归纳为最优化问题, 最优化模型是数学建模中应用最广泛的模型之一, 其内容包括线性规划、整数线性规划、非线性规划、动态规划、变分法、最优控制等.最优化问题简单来说就是我们在微积分中学过的求极值(包括条件极值)问题, 此类问题的一般形式为：(P)这里.是英文subject to (满足于)的缩写, x = (x 1 , x 2 , … , x n )T, 称为决策变量, f (x )是n 元实值函数, 称为目标函数, x ∈称为约束条件, 为可行解域. 如果 = E n(n 维欧氏空间), 则称(P)为无约束优化问题；如果f (x )是线性函数, 由若干个线性等式或不等式确定, 则称(P)为线性规划问题(LP). 这类优化问题(P)统称为静态规划问题, 它包括线性规划和非线性规划.本章将对线性规划、动态规划和非线性规划问题一一作简要地介绍.线性规划线性规划是最优化方法中理论完整、方法成熟、应用广泛的一个重要分支, 可以应用于生产计划, 物资调运, 资源优化配置, 地区经济规划等问题.线性规划问题的数学模型 例1 (生产计划问题) 某工厂生产甲、乙两种产品, 甲产品每生产一件需消耗黄铜2kg, 3个工日, 两个外协件, 每件可获利润60元；乙产品每生产一件需消耗黄铜4kg, 1个工作日, 不需外协件, 每件可获利润30元. 该厂每月可供生产用的黄铜320kg, 总工日180个, 外协件100个. 问应怎样安排生产才能使工厂的利润最高下面我们来分析问题, 建立数学模型.问题是：怎样安排生产, 即甲、乙两种产品各生产多少才能使工厂的利润最高用x 1, x 2分别表示甲、乙两种产品生产的件数, 该厂追求的目标是获取最高利润, 用数学表达式表示为：max f = 60x 1 + 30x 2.由于生产甲、乙产品的件数要受到生产能力的约束, 即 黄铜约束 2x 1 + 4x 2 ≤320, 工日约束 3x 1 + x 2 ≤180, 外协件约束 2x 1≤100, 非负约束 x 1, x 2 ≥0.这样, 该厂生产计划问题就归结为如下数学模型max f =60x 1 + 30x 2, 2x 1 + 4x 2 ≤320, 3x 1 + x 2 ≤180, 2x 1≤100, x 1, x 2 ≥0.例2 (运输问题) 计划由三个粮站A 1, A 2, A 3运输某种粮食至三个加工厂B 1, B 2, B 3, 三min f (x ), . x ∈.个粮站的供应量和三个加工厂的需求量以及各供应地至需求地的单位运输价(元/吨)如表3-1所示, 试作出运费最省的调运计划方案.表3-1加工厂粮站B 1 B 2 B 3 供应量(吨)A 1 A 2 A 3120 80 90 70 40 30 60 50 20 20 30 50 需求量(吨)25 50 25100现在的问题：如何调运, 才能使运费最省设ij 表示第个粮站运到第个加工厂的粮食数量(单位：吨, i , j =1, 2, 3 ), 则总运费f = 120x 11 + 80x 12 + 90x 13 + 70x 21 + 40x 22 + 30x 23 + 60x 31 + 50x 32 + 20x 33 . 从各粮站运出的粮食数量不能超过供应量x 11 + x 12 + x 13 = 20, x 21 + x 22 + x 23 = 30, x 31 + x 32 + x 33 = 50,同时还要保证各加工厂的需要x 11 + x 21 + x 31 = 25, x 12 + x 22 + x 32 = 50, x 13 + x 23 + x 33 = 25,而运输量应满足 x ij ≥0.于是上述运输问题的数学模型为min f = 120x 11 + 80x 12 + 90x 13 + 70x 21 + 40x 22 + 30x 23 + 60x 31 + 50x 32 + 20x 33 , x 11 + x 12 + x 13 = 20, x 21 + x 22 + x 23 = 30, x 31 + x 32 + x 33 = 50, x 11 + x 21 + x 31 = 25, x 12 + x 22 + x 32 = 50, x 13 + x 23 + x 33 = 25, x ij ≥0.从上述两个例子可以看出, 虽然两个问题的具体内容和性质不同, 但它们都属于优化问题, 它们的数学模型都有相同的数学形式, 即在一定的线性等式或不等式的条件下, 使某一线性函数达到最大(或最小).所谓线性规划问题的数学模型是将实际问题转化为一组线性不等式或等式约束下求线性目标函数的最小(大)值问题, 它都可以化为如下标准形式：(LP) min f = c 1x 1 + c 2x 2 + … + c n x n ,a 11x 1 + a 12x 2 + … + a 1n x n =b 1 , a 21x 1 + a 22x 2 + … + a 2n x n = b 2 , … … …a m 1x 1 + a m 2x 2 + … + a mn x n =b m , x 1 , x 2 , …, x n ≥0.记c = (c 1 , c 2 , … , c n ), A = (a ij )m ×n , x = (x 1 , x 2 , …, x n )T, b = (b 1 , b 2 , …, b m )T , 可将(LP)写成矩阵形式： (LP)其中x ≥0意指x 中的每一个分量x j ≥0.min f = cx ,.Ax = b ,x ≥0.再记A = (a 1 , a 2 , …, a n ), 并且假设A 的秩为m . 我们把A 中任意m 个线性无关列向量m j j j a a a ,,,21 组成矩阵B 称为线性规划问题(LP)基矩阵, 简称基；对应变量m j j j x x x ,,,21 称为基变量, 其它变量称为非基变量.由于m j j j a a a ,,,21 线性无关, 因此B = (m j j j a a a ,,,21 )可逆, 用B 1左乘Ax = b 的两边得B 1Ax = B 1b 3-1 记 B 1A = (p ij )m ×n = ( p 1 , p 2 , …, p n ), B 1b = ( 1 , 2 , …, m )T, 不难看出m j j j p p p ,,,21 都是基本单位向量, 即 (m j j j p p p ,,,21 ) = I . 用D 表示非基变量下标的集合, 即D ={1, 2, … , n } { j 1 , j 2 , … , j m }, 由3-1式得到用非基变量表示基变量如下：⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧-=-=-=∑∑∑∈∈∈D j j mj m j D j j j j D j j j j x p x x p x x p x m βββ ,,221121 3-2 记c B = (m j j j c c c ,,,21 ), 用c B 左乘3-1式的两边得c B B 1Ax = c B B 1b 3-3由f = cx 和3-3式得f = c B B 1b (c B B 1A c )x3-4再记= c B B 1b , c B B 1A c = (1,2, … ,n), 由3-4式得到用非基变量表示的目标函数：f=∑∈Dj jj x α3-53-5式和3-2式合称为 (LP) 对应于基B 的典式.由3-2式知, 当所有的非基变量x j = 0 ( j ∈D ) 时, 基变量 i j x =i( i = 1, 2, … ,m ) 是Ax = b 的解, 此解称为 (LP) 的基解.1, 2 , …, m 通常称为基变量值. 当某个基解为可行解, 即所有的基变量值非负时, 此基解称为基可行解, 相应的基B 称为可行基.假设B 为可行基, 由3-5式和3-2式可得如下两个最优判别准则：最优判别准则Ⅰ 当所有的检验数 1 , 2 , … , n ≤0时, f = 为(LP)的最优值.此时的基B 称为最优基, 相应的基可行解称为基最优解.最优判别准则Ⅱ 若有某个检验数 s ＞0, 且p s ≤0, 则(LP)无最优解. 读者可以自行证明最优判别准则Ⅰ和Ⅱ. 单纯形解法设B 是(LP)的一个基, 其典式的矩阵表现形式是)1()1(1111+⨯+----⎪⎪⎭⎫ ⎝⎛-n m A B b B c A B c b B c B B , 上述矩阵称为对应于基B 的单纯形表, 记作T (B ), 它通常写成如下形式(表3-2)：表3-2x 1 x 2 … x nf12…n1j x 2j x…m j x12…mp 11 p 12 … p 1n p 21 p 22 … p 2n… … …p m 1 p m 2 … p mn如果p rs ≠0 (s ∈D ), 那么利用初等行变换可将T (B )的第r 行( p rs 所在的行)除以p rs , 然后将第0行(目标函数行)减去第r 行的s 倍, 再将第i 行减去第r 行的p is 倍, 即使p rs 所在的列中其它各项都变为0. 这种变换相当于将其典式的第r 式中的非基变量x s 解出, 再代入其它各式得到一个新基对应的典式, 称这种变换为换基迭代, 称p rs 为轴心项, x s 为进基变量, r j x 为离基变量.下面给出(LP)已有一个可行基B 的单纯性解法迭代步骤 ① 计算T (B ), 转向②.② 根据最优判别准则, 若B 是最优基或(LP)无最优解, 停；否则转向③. ③ 寻找轴心项, 假设正检验数中下标最小的是s , 则取满足r /p rs = min{i /p is | p is >0, 1≤i ≤m }的p rs 为轴心项, 转向④.④ 以p rs 为轴心项换基迭代, 得新基B 1, 用B 1代替B , 转向①. 1976年, Bland 证明了在已有一个可行基的单纯性解法中, 按照③选取轴心项换基迭代, 迭代次数是有限的.读者也可以自行证明每次迭代后得到的新基是可行基, 且目标函数值是递减的. 例3 用单纯形法解本节例1中的线性规划问题. 解 原模型为：max f = 60x 1 + 30x 2, 2x 1 + 4x 2 ≤320, 3x 1 + x 2 ≤180, 2x 1≤100, x 1, x 2 ≥0.引入松弛变量x 3, x 4, x 5, 化原问题为标准形式min g = max f = 60x 1 30x 2, 2x 1 + 4x 2 + x 3 =320, 3x 1 + x 2 + x 4 =180, 2x 1 + x 5 =100,x1, x2 , x3, x4, x5≥0.在约束条件中, 变量x1, x2 , x3, x4, x5对应的列向量为a1 = (2, 3, 2)T, a2 = (4, 1, 0)T, a3 = (1, 0, 0)T, a4 = (0, 1, 0)T, a5 = (0, 0, 1)T.令B0 = (a3 , a4 , a5 ), 则B0为单位矩阵, 是一个现成可行基, 对应的单纯形表为表3-3.表3-3x1x2 x3 x4 x5g060 30 0 0 0x3 x4 x53201801002 4 1 0 03 1 0 1 03 0 0 0 1由于检验系数中 1 =60, 2 =30皆为正数, 且p1, p2中有正分量.选取左边第一个检验数 1 = 60对应的变量x1为进基变量.由min{320/2, 180/3, 100/2} = 100/2, 知x5为离基变量, 以p31为轴心项(表3-3中带下划线项)换基迭代得新基B1 = (a3 , a4 , a1 )对应的单纯形表(表3-4).表3-4x1x2x3x4x5g30000 30 0 0 30x3 x4 x122030500 4 1 0 10 1 0 1 3/21 0 0 0 1/2检验系数中 2 =30为正数, 且p2中有正分量, 故x2为进基变量.因min{220/4,30/1}=30/1,故x4为离基变量, 以p22为轴心项换基迭代得新基B2 = (a3 , a2 , a1 )对应的单纯形表(表3-5).表3-5x1x2x3x4x5g39000 0 0 30 15x3 x2 x110030500 0 1 4 50 1 0 1 3/21 0 0 0 1/2检验系数中 5 =15为正数, 且p5中有正分量, 故x5为进基变量.因min{100/5,50/(1/2)} =100/5, 故x3为离基变量, 以p15为轴心项换基迭代得新基B3 = (a5 , a2 , a1 )对应的单纯形表(表3-6).x1x2x3x4x5g42000 0 3 18 0x5 x2 x12060400 0 1/5 4/5 10 1 3/10 1/5 01 0 1/10 2/5 0表3-6中的检验数全部非正, 故B3 = (a5 , a2 , a1 )为最优基, 最优解为x1 = 40, x2 = 60, x3 =0, x4 =0, x5 =20.最优值f = g = 4200元.大M 单纯形解法在中, 我们要求(LP)有一个初始(现成的)可行基, 一般的(LP)没有现成的可行基, 不仅如此, 而且可能根本没有可行基, 或者A 的秩小于m . 为此, 我们给(LP)制造一个人造可行基. 不难将一般的线性规划问题化成如下标准形式： (LP)大M 单纯形解法是引入m 个人工变量x n +1 , … , x n +m 将(LP)变为( M-LP)其中M 为足够大的正数, 起“惩罚”作用, 以便排除人工变量.现在, (M-LP)有一个现成可行基B = (a n +1 , a n +2 , a n +m ), 可以用单纯形方法求解. 引入人工变量的目的是使系数矩阵中包含一个单位矩阵, 以便能列出初始单纯形表. 所以, 一方面能少引入一个人工变量, 就尽量少引入；另一方面, 当某个人工变量一旦作为非基变量后, 它的任务就完成了, 我们就可以把它所在的列从单纯形表中删除.例4 用大M 单纯形法解线性规划问题：min f = 3x 1 + x 2 + x 3, x 1 2x 2 + x 3 ≤11, 4x 1 + x 2 + 2x 3 =3, 2x 1+ x 3 =1, x 1, x 2 , x 3 ≥0.解 引入松弛变量x 4, 人工变量x 5 , x 6 ,并取M =10, 将上述问题改写为新线性规划问题：min f = 3x 1 + x 2 + x 3 + 10x 5 + 10x 6 , x 1 2x 2 + x 3 + x 4 =11, 4x 1 + x 2 + 2x 3 + x 5 =3, 2x 1+ x 3 + x 6 =1, x 1, … , x 6 ≥0.用单纯形方法求解, 计算过程见表3-7. 表3-7x 1 x 2 x 3 x 4 x 5 x 6f 40 57 9 29 0 0 0 x 4 x 5 x 6 11 3 1 1 2 1 1 0 0 4 1 2 0 1 0 2 0 1 0 0 1 f 13 21 0 11 0 0 x 4 x 2 x 6 17 3 1 7 0 5 1 0 4 1 2 0 0 2 0 1 0 1 f21 0 0 0min f = cx ,.Ax = b ≥0, x ≥0.min f = c 1x 1 + c 2x 2 + … + c n x n + M (x n +1 + … + x n +m ), .a i 1x 1 + a i 2x 2 + … + a in x n + x n +i =b i , i = 1, 2, … , m ,x , x , …, x , x , … , x ≥0.x 4 x 2 x 3 12 1 1 3 0 0 1 0 1 0 0 2 0 1 0 f 2 0 0 01/3x 1 x 2 x 34 1 91 0 0 1/3 0 1 0 0 0 0 1 2/3原问题的最优解为x 1 = 4, x 2 = 1, x 3 = 9, 最优值f = 2.最后, 我们不加证明(读者可以自行证明)地给出以下两个结论： ① 如果(M-LP)无最优解, 则(LP)或者无可行解或者无最优解.② 如果(M-LP)有最优解, 且最优解中人工变量的值非0, 则(LP)无可行解；当(M-LP)的最优解中人工变量的值都为0时, 去掉人工变量后, 为(LP)的最优解, 此时它们的最优值相同.一般的(LP)问题除了大M 单纯形解法外, 还有两阶段法, 它与大M 单纯形解法大同小异, 这里不作介绍.整数线性规划在前面我们讨论的线性规划问题中, 对决策变量没有整数要求, 但对于某些具体问题, 常常要求决策变量必须是整数的情形.我们把要求所有变量都只取整数值的线性规划问题称为整数线性规划, 部分变量只取整数值的线性规划问题称为混合整数规划.在生活中经常遇到这样的问题：有n 项任务要完成, 恰好有n 个人可分别去完成其中的每一项, 但由于各人的专长不同, 各人完成不同任务的效率 (或所花费时间等) 也不同.于是产生下述问题：应指派哪个人去完成哪项任务, 使完成n 项任务的总效率最高 (或花费的总时间最少). 这类问题称为指派问题(Assignment Problem).用c ij ＞0 (i , j =1, 2, … , n )表示指派第i 个人去完成第j 项任务时的效率(时间或成本等), (c ij )n ×n 称为效率矩阵.如果设x ij = 1表示指派第i 个人去完成第j 项任务, x ij = 0表示指派第i 个人去完成第j 项任务, 注意到每项任务只能指派一人去完成, 每人只能完成一项任务, 则指派问题的数学模型为min f =∑∑==n i nj ji j i x c11,.⎪⎪⎩⎪⎪⎨⎧====∑∑==,,,2,1,1,,,2,1,111n i x n j x n j ij ni ij x ij ∈{0,1}. 象这种所有变量都只取0或1的整数线性规划称为0-1规划.求解整数线性规划问题的方法很多, 简单的有穷举法, 即穷举变量的所有可行的整数组合, 从中找出最优整数解.穷举法在可行解域有界的小型问题中是可行的, 在大型问题中可行的组合数非常大时是不可取的.一般解法是根据其特点, 增加约束条件加以限制, 仅检查可行整数组合的一部分, 从中找出最优整数解.分枝定界法就是其中的一种, 分枝定界法的基本思想可叙述如下.首先不考虑变量的整数约束, 求解相应的线性规划问题 min f = cx ,Ax = b,x≥0.若最优解中所有的变量都取整数, 则已得到整数规划的最优解.如果其中某一个变量x r的值不是整数, 设N r ＜x r ＜N r +1 ( N r是x r的整数部分), 那么分别求解下面两个子问题：(Sub1)min f = cx , (Sub2)min f = cx ,Ax= b, Ax= b,x r ≤N r , x r ≥N r +1,x≥0. x≥0.这样做, 实际上是将原约束区域中不含整数解的区域N r ＜x r ＜N r +1去掉, 在剩下的约束区域寻找最优解.如果两个子问题中的任何一个最优解仍不是整数解, 则可以继续选择一个非整数变量, 将这个子问题再次分解为两个更下一级的子问题.这个过程称为“分枝”.如某一个子问题的最优解已满足变量的整数要求, 则将这个子问题的目标函数值记录下来, 作为原整数规划最优值的上界.如果其它子问题在分枝过程中, 最优值已超过这个上界, 则这个子问题无需再分枝.这个过程称为“定界”.如果在分枝过程中得到新的最优整数解的最优值小于已记录的上界, 则用这个最优值取代原来的上界.因为上界越小, 就可能删除更多不必要的分枝.例5求解min f = x1 + 3x2,2x1 + 3x2 ≥26,4x2 ≥13,x1, x2 为非负整数.解①先不考虑变量x1和x2的整数约束, 求得最优解为x1 = , x2 = , min f = .这不是整数解, 因此将原问题分枝为(Sub1) min f = x1 + 3x2, (Sub2) min f = x1 + 3x2,2x1 + 3x2 ≥26, 2x1 + 3x2 ≥26,4x2 ≥13, 4x2 ≥13,x1 ≤8. x1 ≥9.②分别求得两个子问题的最优解为(Sub1) x1 = 8, x2 = , min f = 18.(Sub2) x1 = 9, x2 = , min f = .③子问题中的任何一个最优解仍不是整数解, 一般先选择最优值较小的一个子问题(Sub1)继续分枝为(Sub11) min f = x1 + 3x2, (Sub12) min f = x1 + 3x2,2x1 + 3x2 ≥26, 2x1 + 3x2 ≥26,4x2 ≥13, 4x2 ≥13,x1 ≤8, x1 ≤8,x2 ≤3. x2 ≥4.④子问题(Sub11)没有可行解, 不再继续分枝. 子问题(Sub12)的最优解为x1 = 7, x2 = 4, min f = 19.这已是整数解, 记录最优值的上界为19后, 不再继续分枝.⑤再将子问题(Sub2)继续分枝为(Sub21) min f = x1 + 3x2, (Sub22) min f = x1 + 3x2,2x 1 + 3x 2 ≥26, 2x 1 + 3x 2 ≥26, 4x 2 ≥13, 4x 2 ≥13, x 1 ≥9, x 1 ≥9, x 2 ≤3. x 2 ≥4.⑥ 子问题(Sub21)没有可行解, 不再继续分枝.子问题(Sub22)的最优解为x 1 = 9, x 2 = 4, min f = 21.其最优值21大于已记录最优值的上界19, 不管它是否为整数解, 都不再继续分枝.所以原问题的最优解为x 1 = 7, x 2 = 4, min f = 19.需要指出的是, 分枝定解法并不能保证用最少的迭代次数达到最优解, 不同的搜索策略会导致不同的迭代次数.一般来说, 对于同一层的两个子问题, 最优值小的一个先搜索可能有利, 因为这样做有可能得到数值比较小的上界, 而上界值越小, 可能被删除的分枝就越多, 搜索到最优解的速度就越快.分枝定解法对于解混合整数规划特别有效, 因为对没有整数约束的变量就不必分枝, 这将大大减少分枝的数量.动态规划动态规划是解决多阶段决策过程最优化的一种数学方法, 它在工程技术、企业管理、工农业生产及军事等部门都有广泛的应用.动态规划是求解某类问题的一种方法, 是考察问题的一种途径, 许多问题用动态规划的思想来处理, 会收到良好的效果.多阶段决策过程与动态规划在作最优决策时, 决策过程常分为若干个阶段, 每个阶段又有多种方法供选择, 这种决策过程称为多阶段决策过程. 动态规划是解决多阶段决策过程问题的一种方法. 我们先从一个例子来说明动态规划的方法.例1 (最短路线问题) 如图3-1, 给出一个线路网络, 两点间连线上的数字表示两点间的距离, 试求一条由A 到F 的铺管线路, 使总距离为最短.这是一个多阶段决策问题. 我们把从A 到E 分成四个阶段, 从A 站铺到B 为第一阶段.此时有两种选择方法：B 1, B 2, 若选择B 1, 则B 1站就是第一阶段决策的结果, B 1既是第一阶段的终点, 又是第二阶段铺路的始点.在第二阶段, 再B 1站开始, 对应于B 1点就有一个可供选择的终点的集合{C 1, C 2, C 3}. 若选择由B 1铺到C 2为第二阶段, 则C 2就是第二阶段的终点, 同时又是第三阶段的始点.依此类推, 直到终点E .由此我们看到：各个阶段的决策不同, 铺管线路也就不同.现在要求：在各个阶段中如何选一个恰当的决策, 才能使由这些决策所决B 1 B 2 AC 1 C 2C 3C 4D 1D 2 D 3E 5 4 1 3 6 8 7 668 4 53 3 845 34 图 3-1定的铺管线路最短.现在, 我们结合解决最短路问题来介绍动态规划方法的基本思想.最短路线问题有一个重要特性：如果从起点A经过P点和Q点而到终点E是一条最短路线, 则由点P出发经过Q点到达终点E的这条子路线, 对于从点P出发到达终点的所有可能选择的不同路线来说, 必定也是最短的.根据最短路线这一特性, 寻找最短路线的方法, 可以从最后一段开始, 由后向前逐步递推, 求出各点到E点的最短路线, 最后就求得由A点到E点的最短路线. 这种从终点逐段向始点寻找最短路线的一种方法, 就是动态规划的方法, 是一种逆序算法.同样还有一种顺序算法, 我们主要介绍逆序算法.下面我们根据动态规划的方法, 求例1的最短路线问题.首先把A到E的整个过程分成4个阶段, 即A→B, B→C, C→D, D→E.记s k：第k阶段道路的起点；S k：第k阶段所有起点的集合；x k：第k阶段道路的终点；X k (s k )：第k阶段所有以s k为起点, 道路终点的集合, 简记为X k ；d k (s k , x k)：第k阶段由点s k到点x k 的距离；P k：第k阶段的起点到E的路线；V k (s k , P k)：以s k为第k阶段的起点, P k为路线, s k到E的距离；f k (s k )：从s k到E的最短距离.由此可知,V k (s k , P k ) = d k (s k , x k ) + V k+1(s k+1, P k+1),f k (s k ) = min { d k (s k , x k ) + f k+1(s k+1) | x k∈X k.},s k+1= x k , k = 4, 3, 2, 1.这就是该问题的动态规划的数学模型.求A到E的最短距离,就是求f 1 (A), A到E的最短路线为A→x1→x2→x3→E. 具体计算如下.当k = 5时, f 5 (E ) = 0 (虚设第5阶段为E→E).当k = 4时, S4 = {D1 , D2 , D3 }, x4 = E.s4 = D1 , f 4 (D1 ) = d4 (D1 , E ) + f 5 (E ) = 5, V4 (D1 , E ) = 5;s4 = D2 , f 4 (D2 ) = d4 (D2 , E ) + f 5 (E ) = 4, V4 (D2, E ) = 4;s4 = D3 , f 4 (D3 ) = d4 (D3 , E ) + f 5 (E ) = 3, V4 (D3 , E ) = 3.当k = 3时, S3 = {C1 , C2 , C3 , C4},s3 = C1 , X3 = X3 (C1 ) = {D1 , D2 },f 3(C1 ) = min {d3(C1 , D1) + f 4 (D1) ,d3(C1 , D2) + f 4 (D2)} = min {6+5,8+4}=11,V3 (C1 , D1 , E ) = 11;s3 = C2 , X3 = X3 (C2 ) = {D1 , D3 },f 3(C2 ) = min {d3(C2 , D1) + f 4 (D1) ,d3(C2 , D3) + f 4 (D3)} = min {4+5,5+3}= 8;V3 (C2 , D3 , E ) = 8;s3 = C3 , X3 = X3 (C3 ) = {D2 , D3 },f 3(C3 ) = min {d3(C3 , D2) + f 4 (D2) ,d3(C3 , D3) + f 4 (D3)} = min {3+4,3+3}= 6;V3 (C3 , D3 , E ) = 6;s3 = C4 , X3 = X3 (C4 ) = {D2 , D3 },f 3(C4 ) = min {d3(C4 , D2) + f 4 (D2) ,d3(C4 , D3) + f 4 (D3)} = min {8+4,4+3}= 7.V3 (C4 , D3 , E ) = 7;当k = 2时, S2 = {B1 , B2 },s2 = B1 , X2 = X2 (B1 ) = {C1 , C2 , C3 },f 2 (B1 ) = min {d2 (B1 ,C1) + f 3 (C1) , d2 (B1 ,C2) + f 3 (C2) , d2 (B1 ,C3) + f 3 (C3)}= min {1 + 11, 3 + 8, 6 + 6 } = 11;V2 (B1 , C2 , D3 , E ) = 11;s2 = B2 , X2 = X2 (B2 ) = {C2 , C3 , C4},f 2 (B2 ) = min {d2 (B2 ,C2) + f 3 (C2) , d2 (B2 ,C3) + f 3 (C3) , d2 (B2 ,C4) + f 3 (C4)}= min {8 + 8 , 7 + 6 , 6 + 7 } = 13.V2 (B2 , C3 , D3 , E ) = 13, V2 (B2 , C4 , D3 , E ) = 13;当k = 1时, S1 = A, X1 = {B1 , B2 },f 1 (A) = min {d1(A, B1) + f 2 (B1) , d1 (A, B2) + f 2 (B2)} = min {5 +11,4 +13}= 16.V1 (A , B1 , C2 , D3 , E ) = 16;至此, 求得的最短距离为16, 相应的最短路线为A→B1→C2→D3→E .动态规划的基本概念和基本方程⑴基本概念①阶段把所给问题的过程, 恰当地划分为若干个相互联系的阶段, 以便能按一定的次序求解.通常用k表示阶段变量, 阶段总数记为n. 如在例1中可分为4个阶段来求解.②状态状态是指过程在该阶段所处的各种可能情况. 通常一个阶段有若干个状态, 描述状态的变量称为状态变量. 第k阶段的状态变量记为s k , 通常用一个数或一个向量表示, 所有第k阶段状态的集合为S k , s k∈S k .③决策当过程处于某个阶段的某个状态时,常常可以作出不同的决定(或选择), 从而可以确定下一阶段的状态变量,这种决定称为决策.描述决策的变量称为决策变量, 第k 阶段当状态为s k 时的决策变量记为x k (s k ), 它是状态s k的函数.决策变量的变化范围称为允许决策集合,用X k表示第k阶段状态为s k 时的允许决策集合, x k∈X k.④策略由过程的第k阶段开始到终点为止的过程, 称为问题的后部子过程, 由每段的决策组成的决策函数序列{x k, x k+1 , … , x n}就称为子策略. 记P k= {x k, x k+1 , … , x n}.当k = 1时, 则此决策函数序列称为一个策略.如例1中, {A, B1 , C2 , D1 , E }就是一个策略, 即铺管线路为A→B1→C2→D1→E, 而{C2 →D1→E }为一个子策略.⑤状态转移方程第k + 1阶段的状态变量s k+1与第k 阶段的状态变量s k和决策变量x k之间的对应关系可用s k+1 = T k(s k , x k )表示, 它表示k阶段与k +1阶段状态的变化规律.如例1中, 状态转移方程为：s k+1 = x k .⑥阶段效益函数它是衡量该阶段决策效果的数量指标, 用d k(s k , x k )表示第k阶段在状态s k时, 决策x k所得的收益.⑦目标函数V k (s k ,P k )是定义在第k阶段开始至终点为止的子过程上的函数, 它表示从第k阶段状态s k 开始, 以P k 为子策略的目标值.V k (s k ,x k )必须具有递推关系, 一般有两种形式：V k (s k , P k ) = d k (s k , x k ) + V k+1(s k+1, P k+1),或V k (s k , P k ) = d k (s k , x k ) V k+1(s k+1, P k+1).⑧最优目标函数f k (s k )是定义在第k阶段开始至终点为止的子过程上的函数, 它表示从第k阶段状态s k 开始, 逐阶段演变至最终状态的最优目标值. 即f k (s k ) = opt {V k (s k , P k )}.这里的opt表示最优化(optimization), 具体地可以写成min或max.在不同的问题中, 目标的含义是不同的, 它可能是距离、利润、产品的产量或资源消耗等.如在最短路线问题中, V k (s k ,P k ) 表示第k阶段的点s k 以P k为路线至终点E的距离, f k (s k)表示由s k 至终点E的最短距离, d k (s k , x k ) 表示第k的点s k 到点s k+1 = x k(s k )的距离.⑵最优原理作为整个过程的最优策略具有这样的性质：无论过去的状态和策略如何, 对前面的决策所形成的状态而言, 余下的诸决策必须构成最优策略.简言之, 一个最优策略的子策略总是最优的.⑶基本方程从最短路线问题例子的计算过程中可以看出, 用动态规划方法求解问题的关键, 在于正确的写出k阶段与k + 1阶段之间的递推关系：V k (s k , P k ) = d k (s k , x k ) + V k+1(s k+1, P k+1),f k (s k ) = min { d k (s k , x k ) + f k+1(s k+1) | x k∈X k.},s k+1= x k , k = 4, 3, 2, 1.和初值条件f 5 (E ) = 0.一般地, 动态规划方法的数学模型可归纳为一个递推方程：V k (s k , P k ) = d k (s k , x k ) + V k+1(s k+1, P k+1),f k (s k ) = opt { d k (s k , x k ) + f k+1(s k+1) | x k∈X k.},s k+1= T k(s k , x k ), k = n, n 1, … , 1.称为基本方程. 初值条件一般取f n+1(s n+1) = 0. 另一种形式为V k (s k , P k ) = d k (s k , x k )V k+1(s k+1, P k+1),f k (s k ) = opt { d k (s k , x k ) f k+1(s k+1) | x k∈X k.},s k+1= T k(s k , x k ), k = n, n 1, … , 1.初值条件一般取f n+1(s n+1) = 1.综上所述, 建立动态规划数学模型的方法步骤如下：①把所给问题恰当地划分阶段, 并确定阶段的状态变量；②确定决策变量、阶段效益函数以及最优值函数；③建立状态转移方程；④根据动态规划的最优化原理建立基本方程.动态规划模型举例⑴一种资源分配问题设有某种原料, 总数量为a, 用于生产n种产品. 若分配数量x i用于生产第i种产品, 其收益为g i (x i ).问应如何分配, 才能使生产的总收益最大此问题可写成静态规划问题：max f = g1(x1) + g2(x2) + … + g n(x n ) ,x1 + x2 + … + x n = a,x1 , x2 , … , x n ≥0.在应用动态规划方法处理这类“静态规划”问题时, 通常以把资源分配给一个或几个使用者的过程作为一个阶段, 把问题中的变量x i 作为决策变量, 将累计的量或随递推过程变化的量选为状态变量.状态变量s k表示分配用于生产第k种产品至第n种产品的原料数量.决策变量x k表示分配给生产第k种产品的原料数量.状态转移方程为：s k+1= s k x k .允许决策集合为：X k = {x k| 0≤x k ≤s k }.令f k (s k ) 表示以数量为s k的原料分配给第k种至第n种产品所得到的最大收入. 因而可写出动态规划的递推关系式为：f k (s k ) = max {g k (x k ) + f k+1(s k+1) |0≤x k ≤s k }, k = n 1, n 2, … , 1.f n (s n ) =g n (x n ).或f k (s k ) = max {g k (x k ) + f k+1(s k x k) |0≤x k ≤s k },k =n 1, n 2, …, 1.f n (s n ) =g n (x n ).例2 某公司拟将某种高效率的4台加工设备, 分配给所属的甲、乙、丙三个分公司, 各公司若获得这种设备之后, 可以为总公司提供的盈利如下表3-8所示. 问这4台设备如何分配给各分公司, 才能使总公司得到的盈利最大.表3-8 单位：万元分公司设备台数甲乙丙0 1 2 3 40 0 0 3 5 4 7 10 6 9 11 11 12 11 12解将问题按公司分为三个阶段, 甲、乙、丙三个公司分别编号为1、2、3.s k 表示为分配给第k个公司至第3个公司的设备台数.x k 表示分配给第k个公司的设备台数.状态转移方程为：s k+1= s k x k .g k (x k ) 表示x k台设备分配到第k个公司所得的盈利值.f k (s k ) 表示为s k台设备分配给第k个公司至第3个公司时所得到的最大盈利值.因而该问题的动态规划的数学模型为s.f k (s k ) = max {g k (x k ) + f k+1(s k x k) |0≤x k ≤s k }, k =2 , 1.f 3(s3 ) = g3(x3 ).具体计算如下.第二阶段：k = 2 , S2 = {0,1,2,3,4}.因为给乙公司x2台, 其盈利为g2(x2 ), 余下的s 2x2台就给丙公司, 则它的盈利最大值为f 3(s 2x2 ) . 现要选择x2值, 使g2(x2 ) + f 3(s 2x2 )取最大值. 即有f 2(s2 ) = max { g2(x2 ) + f 3(s 2x2 ) | 0≤x2≤s2}.其数值计算如下表3-9所示.表3-9x2 s2g2(x2 ) + f 3(s2x2 )f 2(s 2 )x2*0 1 2 3 40 1 2 3 40 + 4 5 + 00 + 6 5 + 4 10 + 00 + 11 5 + 6 10 + 4 11 + 00 + 12 5 + 11 10 + 6 11 + 4 11 +51014161221, 2表中x2*表示使f 2(s2 )为最大值时的最优决策.第一阶段：k = 1 , S2 = {4}, s1 = 4.因为给甲公司x1台, 其盈利为g1(x1 ), 剩下的4x1台就分给乙和丙两个公司, 则它的盈利最大值为f 2(4x1 ). 现要选择x1值, 使取最大值g1(x1 ) + f 2(4x1 ). 即有f 1(4) = max { g1(x1 ) + f 2(4x1 )| 0≤x1≤4},它就是所求得总盈利最大值, 其数值计算如表3-10所示.表3-10x1 s1g1(x1 ) + f 2(4x1 )f 1(4)x1*0 1 2 3 44 0 +16 3 +14 7 +10 9 +5 12 + 0171, 2然后按表格的顺序反推算, 可知最优分配方案有两个：①x1*= 1, 根据s2= s1x1*= 4 1 = 3, 查表3-9知, x2*= 2, 由s3= s2x2*= 32 = 1, 故x3*= 1. 即甲公司分配1台, 乙公司分配2台, 丙公司分配1台.②x1*= 2, 根据s2= s1x1*= 4 2 = 2, 查表3-9知, x2*= 2, 由s3= s2x2*= 22 = 0, 故x3*= 0. 即甲公司分配2台, 乙公司分配2台, 丙公司分配0台.以上两分配方案所得到得总盈利均为17万元.⑵系统可靠性问题例3 某电子仪器由3个串联的组件( j = 1, 2, 3 )构成, 因而有一个组件失效, 仪器即无法工作. 为提高该仪器可靠性, 每个组件中可增加并联不同的备用元件数. 用R j代表各组件的可靠性, k j代表第j个组件中并联的元件数, C j代表并联不同数目的元件时第j个组件的相应费用, 有关数据见表3-11.若限定用于仪器中组件的总费用不超过1000元. 试确定使该仪器可靠性为最高的设计方案.表3-11组件k jj = 1j = 2j = 3R1C1R2C2R3C3110030020022005004003300600500解对第k个组件确定并联元件数作为第k个阶段的决策.s k 表示对第k个组件至第3个组件确定并联元件数时可用的费用, s1 = 1000, s2∈{700, 800, 900}, s3∈{200, 300, 400, 500, 600}.x k 表示第k个组件并联不同数目的元件时的费用, 允许决策集合为：X1 = {x1| 100, 200, 300, x1≤s1}, X2 = {x2| 300, 500, 600, x2≤s2}, X3 = {x3| 100, 200, 300, x3≤s3}.状态转移方程为：s k+1= s k x k ,阶段效益函数R k (x k ) = R k ,最优目标函数f k (s k ) 表示第k个阶段至第3个阶段用s k元购置组件时所得到该仪器的最大可靠性.从而该问题的动态规划的数学模型为f k (s k ) = max {R k (x k ) f k+1(s k+1) | x k ∈X k },s k+1= s k x k , k = 3,2 , 1,f 4(s4 ) = 1.具体计算如下.k = 3时, f 3(s3 ) = max { R3(x3 ) | x3∈X3 }, 得表3-12.表3-12x3 s3R3(x3 )f 3(s3)x3* 200 400 500200 300 400 500 600200 200 400 500 500k = 2时, f 2(s2 ) = max { g2(x2 ) f 3(s3 ) | x2∈X2 }, 得表3-13.x2 s2R2(x2 ) f 3(s3 )f 2(s2 )x2* 300 500 600700 800 900××××××××300300300 = 1时, 1( 1 ) = max { 1( 1 ) 2( 2 ) |1∈ 1 }, 得表3-14.表3-14x1 s1R1(x1 ) f 2(s2 )f 1(s1 )x1* 100 200 3001000×××200最优策略为1= 200, 2= 300, 2= 500, 即第1、2、3个组件应分别并联2个、1个、3个元件, 才能使该仪器可靠性达到最高, 此值为.非线性规划非线性规划问题的解法相当复杂, 本节主要介绍无约束最优化问题的数学模型min{ f (x )| x ∈E n}的解法：最速下降法、牛顿法、拟牛顿法, 及有约束最优化问题的解法：线性逼近法和罚函数法.预备知识定义1 设f (x )是定义在E n上的可微函数, 则我们称n 维向量Tn x f x f x f ⎪⎪⎭⎫⎝⎛∂∂∂∂∂∂,,,21为函数f (x )在点x 处的梯度, 记作f ∇(x ) 或g (x ). 满足g (x ) = 0的点称为f (x )的驻点.定义2 设f (x )是定义在E n上的二阶可微函数, 则我们称n 阶方阵⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂2222122222212212212212nn n nn x f x x f x x f x x f x fx x f x x f x x f x f为函数f (x )在点x 处的Hesse 矩阵, 记作G (x ). 当f (x )的二阶偏微商连续时, G (x )为对称矩阵.定理1 (一阶必要条件)若x * 为f (x )的局部极小点, 且在x *的某邻域内f (x )具有一阶连续偏微商, 则g (x ) = 0.此定理的证明可由一元函数极值存在的必要条件得到.定理2 (二阶充分条件)若在x *的某邻域内f (x )具有二阶连续偏微商, 且g (x ) = 0, G (x * )正定, 则x * 为f (x )的局部极小点.证 由于G (x * )正定,故对 p ∈E n 有p T G (x * ) p ≥|| p || 2, 其中＞0是G (x * )的最小特征值.现将f (x )在x * 点用泰勒(Taylor)公式展开, 并注意到g (x ) = 0, 有f (x ) = f (x *) +21(x x *)T G (x * ) (x x *) + o (|| x x *|| 2).于是f (x ) f (x *) ≥[ /2 + o (1)]|| x x *|| 2,所以当x 充分接近于x * 时, f (x ) f (x *)＞0, 即x *为f (x )的局部极小点.一维搜索算法求解无约束最优化问题(UP)的基本方法是给定一个初始点x 0, 由这个初始点出发, 依次产生一个点列x 1 , x 2 , … , x k , … , 记为{x k }, 使得或者某个x k 恰好是问题的一个最优解, 或者点列{x k }收敛到问题的一个最优解x *, 这就是我们平时所说的迭代算法.在迭代算法中由点x k 迭代到x k +1时, 要求f (x k +1) ≥ f (x k ), 称这种算法为下降算法.点列{x k }的产生, 通常采取两步来完成.首先在x k 点处求一个方向p k , 使得f (x )沿方向p k 移动时函数值有所下降, 一般称这个方向为下降方向或搜索方向. 其次以x k 为出发点, 以p k 为方向作射线x k + p k , 其中＞0,在此射线上求一点x k +1, x k +1 = x k + k p k , 使得f (x k +1)＜ f (x k ), 其中k 称为步长. 由x k 出发沿方向p k 求步长k 的过程叫一维搜索或线性搜索, 它是求解最优化问题的基本步骤之一.当搜索方向确定之后, 一维搜索的优劣便成为求解最。
数学建模常用算法模型数学建模是将实际问题抽象为数学模型，并利用数学方法求解问题的过程。
在数学建模中，算法模型是解决问题的关键。
下面介绍一些常用的数学建模算法模型。
1.线性规划模型：线性规划是一种用于求解线性约束下的最优化问题的数学方法。
线性规划模型的目标函数和约束条件均为线性函数。
线性规划广泛应用于供需平衡、生产调度、资源配置等领域。
2.非线性规划模型：非线性规划是一种用于求解非线性目标函数和约束条件的最优化问题的方法。
非线性规划模型在能源优化调度、金融风险管理、工程设计等方面有广泛应用。
3.整数规划模型：整数规划是一种在决策变量取离散值时求解最优化问题的方法。
整数规划模型在网络设计、物流调度、制造安排等领域有广泛应用。
4.动态规划模型：动态规划是一种通过将问题分解为多个阶段来求解最优化问题的方法。
动态规划模型在资源分配、投资决策、路径规划等方面有广泛应用。
5.随机规划模型：随机规划是一种在目标函数和约束条件存在不确定性时求解最优化问题的方法。
随机规划模型在风险管理、投资决策、资源调度等方面有广泛应用。
6.进化算法模型：进化算法是一种通过模拟生物进化过程来求解最优化问题的方法。
进化算法模型包括遗传算法、粒子群算法、蚁群算法等，被广泛应用于参数优化、数据挖掘、机器学习等领域。
7.神经网络模型：神经网络是一种模仿人脑神经元连接和传递信息过程的数学模型。
神经网络模型在模式识别、数据分类、信号处理等领域有广泛应用。
8.模糊数学模型：模糊数学是一种用于处理不确定性和模糊信息的数学模型。
模糊数学模型在风险评估、决策分析、控制系统等方面有广泛应用。
除了以上常用的数学建模算法模型，还有许多其他的算法模型，如图论模型、动力系统模型、马尔科夫链模型等。
不同的问题需要选择合适的算法模型进行建模和求解。
数学建模算法模型的选择和应用需要根据具体的问题和要求进行。
§3 分派与装载生活和工作中经常碰到任务分派问题，如由5个人承担5项任务，由于各人的专长不同，他们完成各项任务的时间（或代价）不同，那么派谁去完成哪项任务使总的效率最高呢？类似的问题很多。
例4 车间有n 项加工任务，分派给n 个工人完成，每人完成其中一项。
已知每个人完成各项任务的时间（其中有若干人不能完成某几项任务），问如何进行任务分派，使所需总时间最少？将工人编号为n i ,,2,1 =，任务编号为n j ,,2,1 =，第i 人完成第j 项任务的时间记为ij c （若第i 人不能完成任务j ，则记M c ij =，M 是充分大的正数），任务分派用如下的0——1变量表述：⎩⎨⎧=，否则人完成任务若分派第0,1ji x ij 问题的目标函数——总时间为 ∑∑===n i nj ij ij x c Z 11（1）约束条件为∑===nj ijn i x1,,2,1,1 （2）∑===ni ijn j x1,,2,1,1 （3） n j i x ij ,,2,1,,1,0 == （4）其中（2）说明第i 人只能完成一项任务，（3）说明任务j 只能由一人完成。
这里决策变量ij x 只能取值0和1，称为0—1整数规划。
满足（2）~（4）的可行解ij x 可表为矩阵形式，其中每一行和每一列都必须有且只能有一个1，其余元素均为0。
引入0—1变量解决任务分配问题还可以有其他方式，如例5 工厂用k 种不同工艺生产n 种产品，每种产品的利润已知。
在各种工艺条件下每种产品所消耗的资源（如原料）是确定的，并且工厂的总资源有一定的限制。
问应选择哪种工艺，每种产品各生产多少，使总利润最高。
用k A A A ,,,21 表示k 种工艺，n B B B ,,,21 表示n 种产品。
已知单件i B 的利润为),,2,1(,n i p i =，设在工艺),,2,1(,k j A j =下单件i B 的资源消耗为ij c ，资源限制为j Q 。
数学建模常用算法模型在数学建模中，常用的算法模型包括线性规划、整数规划、非线性规划、动态规划、图论算法以及遗传算法等。
下面将对这些算法模型进行详细介绍。
1.线性规划：线性规划是一种用于求解最优化问题的数学模型和解法。
它的目标是找到一组线性约束条件下使目标函数取得最大（小）值的变量取值。
线性规划的常用求解方法有单纯形法、内点法和对偶理论等。
2.整数规划：整数规划是一种求解含有整数变量的优化问题的方法。
在实际问题中，有时变量只能取整数值，例如物流路径问题中的仓库位置、设备配置问题中的设备数量等。
整数规划常用的求解方法有分支界定法和割平面法等。
3.非线性规划：非线性规划是一种求解非线性函数优化问题的方法，它在实际问题中非常常见。
与线性规划不同，非线性规划的目标函数和约束函数可以是非线性的。
非线性规划的求解方法包括牛顿法、拟牛顿法和全局优化方法等。
4.动态规划：动态规划是一种用于解决决策过程的优化方法。
它的特点是将问题划分为一系列阶段，然后依次求解每个阶段的最优决策。
动态规划常用于具有重叠子问题和最优子结构性质的问题，例如背包问题和旅行商问题等。
5.图论算法：图论算法是一类用于解决图相关问题的算法。
图论算法包括最短路径算法、最小生成树算法、网络流算法等。
最短路径算法主要用于求解两点之间的最短路径，常用的算法有Dijkstra算法和Floyd-Warshall算法。
最小生成树算法用于求解一张图中连接所有节点的最小代价树，常用的算法有Prim算法和Kruskal算法。
网络流算法主要用于流量分配和问题匹配，例如最大流算法和最小费用最大流算法。
6.遗传算法：遗传算法是一种借鉴生物进化原理的优化算法。
它通过模拟生物的遗传、变异和选择过程，不断优化问题的解空间。
遗传算法适用于对问题解空间有一定了解但难以确定最优解的情况，常用于求解复杂的组合优化问题。
总结起来，数学建模中常用的算法模型包括线性规划、整数规划、非线性规划、动态规划、图论算法以及遗传算法等。
初中数学建模30种经典模型初中数学建模是培养学生综合运用数学知识解决实际问题的一种教学方法和手段。
以下是初中数学建模中的30种经典模型，并对每种模型进行简要介绍：1.线性规划模型：通过建立线性目标函数和线性约束条件，优化解决线性规划问题。
2.排队论模型：研究排队系统中的等待时间、服务能力等问题，以优化系统效率。
3.图论模型：利用图的概念和算法解决实际问题，如最短路径、网络流等。
4.组合数学模型：应用组合数学的方法解决实际问题，如排列组合、集合等。
5.概率模型：利用概率理论分析和预测事件发生的可能性和规律。
6.统计模型：收集、整理和分析数据，通过统计方法得出结论和推断。
7.几何模型：运用几何知识解决实际问题，如图形的面积、体积等。
8.算术平均模型：利用算术平均数来描述和分析数据的集中趋势。
9.加权平均模型：利用加权平均数考虑不同数据的重要性来得出综合结论。
10.正态分布模型：应用正态分布来描述和分析数据的分布情况。
11.投影模型：通过投影的方法解决几何体在平面上的投影问题。
12.比例模型：利用比例关系解决实际问题，如物体的放大缩小比例等。
13.数据拟合模型：根据已知数据点，通过曲线或函数拟合来推测未知数据点。
14.最优化模型：寻找最大值或最小值，优化某种指标或目标函数。
15.路径分析模型：研究在网络或图中找到最优路径的问题。
16.树状图模型：通过树状图的结构来描述和解决问题，如决策树等。
17.随机模型：基于随机事件和概率进行建模和分析。
18.多项式拟合模型：利用多项式函数对数据进行拟合和预测。
19.逻辑回归模型：通过逻辑回归分析，预测和分类离散型数据。
20.回归分析模型：分析自变量和因变量之间的关系，并进行预测和推断。
21.梯度下降模型：通过梯度下降算法来求解最优解的问题。
22.贪心算法模型：基于贪心策略解决最优化问题，每次选择当前最优解。
23.线性回归模型：通过线性关系对数据进行建模和预测。
24.模拟模型：通过构建模拟实验来模拟和分析实际情况。
一、数学建模的理解例子：二、经典最优化方法1、微分与极值2、无约束极值问题3、约束极值问题三、无约束优化问题数值解法（向量）1、最优梯度法（梯度下降法）2、牛顿法3、共轭梯度法4、阻尼牛顿法5、变尺度法1.1 无约束优化的一般形式无约束非线性规划问题为其最优解通常都是局部最优解，寻找全局最优解需要对局部最优解进行比较以后得到（如果能够求出所有局部最优解的话）。
1.2 最优性条件是最优解的必要条件为；充分条件为，且正定。
1.3 下降法的基本思想在迭代的第k步，确定一个搜索方向和一个步长，使沿此方向、按此步长走一步到达下一点时，函数值下降。
其基本步骤为1）选初始解；2）对于第次迭代解，确定搜索方向并在此方向确定搜索步长令，使<；3）若符合给定的迭代终止原则，停止迭代，最优解；否则，转2。
搜索方向的选择（不同方向产生不同的算法）：1）最速下降法（梯度法）2）牛顿法3）拟牛顿法：利用第和步得到的，用BFGS公式，DFP公式，GM公式等迭代公式构造正定矩阵近似代替，或直接构造近似代替，从而由，或得到下降方向d k+1。
搜索步长的确定——线性搜索：用二分法、黄金分割法（即0.618法）、Fibonacci 法，牛顿切线法和割线法，插值方法等近似方法求一维优化问题：来确定步长。
2.1 非线性最小二乘拟合问题有一组数据要拟合一个已知函数y=f(x, t), x=(x1,x2,…,xm),, x为待定系数。
记误差，，拟合误差定义为的平方和，于是问题表示为如下的优化模型：当对（的某些分量）是非线性函数时，称非线性最小二乘拟合。
四线性规划1、线性规划的数学模型某工厂安排生产1、2两种产品，2、线性规划的图解法单纯形及其求解法1.1 线性规划的图解法线性规划的图解法只能用于求解两个决策变量（2维）的情形。
由于线性规划的约束条件和目标函数均为线性函数，所以对于2维情形，可以在平面坐标系下画出可行域和目标函数的等值线。
一、概述数学建模是数学与实际问题相结合的产物，通过建立数学模型来解决现实生活中的复杂问题。
Matlab作为一个强大的数学计算工具，在数学建模中具有重要的应用价值。
本文将介绍30种经典的数学建模模型，以及如何利用Matlab对这些模型进行建模和求解。
二、线性规划模型1. 线性规划是数学建模中常用的一种模型，用于寻找最优化的解决方案。
在Matlab中，可以使用linprog函数对线性规划模型进行建模和求解。
2. 举例：假设有一家工厂生产两种产品，分别为A和B，要求最大化利润。
产品A的利润为$5，产品B的利润为$8，而生产每单位产品A 和B分别需要8个单位的原料X和10个单位的原料Y。
此时，可以建立线性规划模型，使用Matlab求解最大化利润。
三、非线性规划模型3. 非线性规划是一类更加复杂的规划问题，其中目标函数或约束条件存在非线性关系。
在Matlab中，可以使用fmincon函数对非线性规划模型进行建模和求解。
4. 举例：考虑一个有约束条件的目标函数，可以使用fmincon函数在Matlab中进行建模和求解。
四、整数规划模型5. 整数规划是一种特殊的线性规划问题，其中决策变量被限制为整数。
在Matlab中，可以使用intlinprog函数对整数规划模型进行建模和求解。
6. 举例：假设有一家工厂需要决定购物哪种机器设备，以最大化利润。
设备的成本、维护费用和每台设备能生产的产品数量均为已知条件。
可以使用Matlab的intlinprog函数对该整数规划模型进行建模和求解。
五、动态规划模型7. 动态规划是一种数学优化方法，常用于多阶段决策问题。
在Matlab 中，可以使用dynamic programming toolbox对动态规划模型进行建模和求解。
8. 举例：考虑一个多阶段生产问题，在每个阶段都需要做出决策以最大化总利润。
可以使用Matlab的dynamic programming toolbox对该动态规划模型进行建模和求解。
