logo资料库

数学建模美赛国赛算法全录附matlab代码.pdf

发布时间：2022-06-03 发布人：admin 分类：说明书 资料大小：4.07M 资料格式：pdf 举报 版权申诉
第1页 / 共800页
第2页 / 共800页
第3页 / 共800页
第4页 / 共800页
第5页 / 共800页
第6页 / 共800页
第7页 / 共800页
第8页 / 共800页
资料共800页，剩余部分请下载后查看
    Matlab数学建模算法全收录
    第01章 线性规划
    第02章 整数规划
    第03章 非线性规划
    第04章 动态规划
    第05章 图与网络
    第06章 排队论
    第07章 对策论
    第08章 层次分析法
    第09章 插值与拟合
    第10章 数据的统计描述和分析
    第11章 方差分析
    第12章 回归分析
    第13章 微分方程建模
    第14章 稳定状态模型
    第15章 常微分方程的解法
    第16章 差分方程模型
    第17章 马氏链模型
    第18章 变分法模型
    第19章 神经网络模型
    第20章 偏微分方程的数值解
    第21章 目标规划
    第22章 模糊数学模型
    第23章 现代优化算法
    第24章 时间序列模型
    第25章 存贮论
    第26章 经济与金融中的优化问题
    第27章 生产与服务运作管理中的优化问题
    第28章 灰色系统理论及其应用
    第29章 多元分析
    第30章 偏最小二乘回归
    附录一 Matlab入门
    附录二 Matlab在线性代数中的应用
    附录三 运筹学的LINGO软件
    附录四 判别分析
    参考文献
    数学建模算法全收录 非常赞的一套教程，作者不详。 内容详尽，结合MATLAB具体实现。 欢迎交流学习、covermy@qq.com 算法大全第01章__线性规划.pdf 算法大全第02章 整数规划.pdf 算法大全第03章_非线性规划.pdf 算法大全第04章__动态规划.pdf 算法大全第05章__图与网络.pdf 算法大全第06章_排队论.pdf 算法大全第07章_对策论.pdf 算法大全第08章__层次分析法.pdf 算法大全第09章_插值与拟合.pdf 算法大全第10章_数据的统计描述和分析.pdf 算法大全第11章_方差分析.pdf 算法大全第12章_回归分析.pdf 算法大全第13章_微分方程建模.pdf 算法大全第14章_稳定状态模型.pdf 算法大全第15章_常微分方程的解法.pdf 算法大全第16章_差分方程模型.pdf 算法大全第17章_马氏链模型.pdf 算法大全第18章_变分法模型.pdf 算法大全第19章_神经网络模型.pdf 算法大全第20章_偏微分方程的数值解.pdf 算法大全第21章_目标规划.pdf 算法大全第22章__模糊数学模型.pdf 算法大全第23章__现代优化算法.pdf 算法大全第24章_时间序列模型.pdf 算法大全第25章__存贮论.pdf 算法大全第26章__经济与金融中的优化问题.pdf 算法大全第27章__生产与服务运作管理中的优化问 算法大全第28章__灰色系统理论及其应用.pdf 算法大全第29章_多元分析.pdf 算法大全第30章__偏最小二乘回归.pdf 算法大全附录一__Matlab入门.pdf 算法大全附录二__Matlab在线性代数中的应用.pdf 算法大全参考文献.pdf
    §1 线性规划 第一章 线性规划 在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济 效益的问题。此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(Linear Programming 简记 LP)则是数学规划的一个重要分支。自从 1947 年 G. B. Dantzig 提出 求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深 入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性 规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。 1.1 线性规划的实例与定义 例 1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为 4000 元与 3000 元。 BA、 机器加工，加工时间分别为每台 2 小时和 1 小时；生产乙机床 生产甲机床需用 CBA 、、 需用 三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时 数分别为 A 机器 10 小时、B 机器 8 小时和C 机器 7 小时，问该厂应生产甲、乙机床各 几台，才能使总利润最大？ 上述问题的数学模型：设该厂生产 1x 台甲机床和 2x 乙机床时总利润最大，则 1, xx 2 应满足 （目标函数） max (1) x x 1 3 + 2 x 10 ≤ 2 8 ≤ z 4 = x 2 + 1 x x + 1 2 x 7 ≤ 2 xx , ≥ 1 2 ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 0 s.t.（约束条件） （2） 1, xx 称之为决策变量，（1）式被称为问题的目标函数，（2）中的几个不等式 这里变量 是问题的约束条件，记为 s.t.(即 subject to)。由于上面的目标函数及约束条件均为线性 函数，故被称为线性规划问题。 2 总之，线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最 小的问题。 在解决实际问题时，把问题归结成一个线性规划数学模型是很重要的一步，但往往 也是困难的一步，模型建立得是否恰当，直接影响到求解。而选适当的决策变量，是我 们建立有效模型的关键之一。 1.2 线性规划的 Matlab 标准形式 线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件的不等号可以 是小于号也可以是大于号。为了避免这种形式多样性带来的不便，Matlab 中规定线性 规划的标准形式为 s.t. xc T min x b Ax ≤ ⎧ ⎪ Aeq x =⋅ ⎨ ⎪ lb x ≤≤ ⎩ beq ub 其中 c 和 x 为 n 维列向量， A 、 Aeq 为适当维数的矩阵， b 、beq 为适当维数的列向 量。 -1-
    例如线性规划 的 Matlab 标准型为 xc T s.t. max x Ax ≥ b xc T s.t. − Ax b −≤ min − x 1.3 线性规划问题的解的概念 一般线性规划问题的（数学）标准型为 max z = n ∑ j 1 = j xc j (3) s.t. xa ij j = b i i = ,2,1 , m L (4) 0 ≥ , L 可行解 满足约束条件（4）的解 nx , L 而使目标函数（3）达到最大值的可行解叫最优解。 xx , 1 ,2,1 n x = = ( j , 2 可行域 所有可行解构成的集合称为问题的可行域，记为 R 。 1.4 线性规划的图解法 ) ，称为线性规划问题的可行解， n ∑ j 1 = x j ⎧ ⎪ ⎨ ⎪ ⎩ 1 0 9 8 7 6 5 4 3 2 1 0 2 x 1 + x 2 = 1 0 x 2 = 7 ( 2 , 6 ) x 1 + x 2 = 8 z = 1 2 0 2 4 6 8 1 0 图 1 线性规划的图解示意图 图解法简单直观，有助于了解线性规划问题求解的基本原理。我们先应用图解法来 求解例 1。对于每一固定的值 z ，使目标函数值等于 z 的点构成的直线称为目标函数等 位线，当 z 变动时，我们得到一族平行直线。对于例 1，显然等位线越趋于右上方，其 上的点具有越大的目标函数值。不难看出，本例的最优解为 ，最优目标值 * =z 26 从上面的图解过程可以看出并不难证明以下断言： （1）可行域 R 可能会出现多种情况。R 可能是空集也可能是非空集合，当 R 非空 时，它必定是若干个半平面的交集（除非遇到空间维数的退化）。R 既可能是有界区域， 也可能是无界区域。 x )6,2(* = （2）在 R 非空时，线性规划既可以存在有限最优解，也可以不存在有限最优解（其 。 T 目标函数值无界）。 -2-
    n i 1 = b （3）若线性规划存在有限最优解，则必可找到具有最优目标函数值的可行域 R 的 “顶点”。 上述论断可以推广到一般的线性规划问题，区别只在于空间的维数。在一般的 n 维 空间中，满足一线性等式∑ xa i i = b 的点集被称为一个超平面，而满足一线性不等式 n n i i i 1 = b ≥ ≤ xa i xa i （或∑ ）的点集被称为一个半空间（其中 ∑ a L 为一 n 维行 ( 1 i 1 = 向量， b 为一实数）。若干个半空间的交集被称为多胞形，有界的多胞形又被称为多面 体。易见，线性规划的可行域必为多胞形（为统一起见，空集 Φ 也被视为多胞形）。 在一般 n 维空间中，要直接得出多胞形“顶点”概念还有一些困难。二维空间中的顶点 可以看成为边界直线的交点，但这一几何概念的推广在一般 n 维空间中的几何意义并不 十分直观。为此，我们将采用另一途径来定义它。 na ) , , 2 及 及 2 x R R R ∀ ∈ ∈ 。 x 1 λ xx 1, 定义 1 称 n 维空间中的区域 R 为一凸集，若 ) 1( λ −+ 定义 2 设 R 为 n 维空间中的一个凸集， R 中的点 x 被称为 R 的一个极点，若不 x x 1、 定义 1 说明凸集中任意两点的连线必在此凸集中；而定义 2 说明，若 x 是凸集 R 的一个极点，则 x 不能位于 R 中任意两点的连线上。不难证明，多胞形必为凸集。同 样也不难证明，二维空间中可行域 R 的顶点均为 R 的极点（ R 也没有其它的极点）。 )1,0(∈∀λ )1,0(∈λ −+ ，使得 ∈2 ，有 存在 x λ ) λ 1.5 求解线性规划的 Matlab 解法 单纯形法是求解线性规划问题的最常用、最有效的算法之一。这里我们就不介绍 单纯形法，有兴趣的读者可以参看其它线性规划书籍。下面我们介绍线性规划的 Matlab 解法。 。 1( 2 x x = 1 例 2 求解下列线性规划问题 − 5 x 3 2 = + x z x x max 3 2 + 1 x x x 7 + = 1 2 3 x x 5 2 10 − ≥ + 1 3 2 x x x 3 12 ≤ + + 1 3 ≥xxx , , 0 1 2 3 2 s.t. -3- Matlab 中线性规划的标准型为 xc T min x b Ax ≤ ⎧ ⎪ Aeq x =⋅ ⎨ ⎪ lb x ≤≤ ⎩ beq ub s.t. 基本函数形式为 linprog(c,A,b)，它的返回值是向量 x 的值。还有其它的一些函数调用形 式（在 Matlab 指令窗运行 help linprog 可以看到所有的函数调用形式），如： [x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS) 这里 fval 返回目标函数的值，LB 和 UB 分别是变量 x 的下界和上界， 0x 是 x 的初始值， OPTIONS 是控制参数。
    解 （i）编写 M 文件 c=[2;3;-5]; a=[-2,5,-1;1,3,1]; b=[-10;12]; aeq=[1,1,1]; beq=7; x=linprog(-c,a,b,aeq,beq,zeros(3,1)) value=c'*x z （ii）将M文件存盘，并命名为example1.m。 （iii）在Matlab指令窗运行example1即可得所求结果。 例3 求解线性规划问题 x x min 2 = 1 x x 4 8 + ⎧ 2 1 ⎪ x x 3 2 + ⎨ 1 ⎪ xxx , , ⎩ 1 x 3 + x 2 + 6 ≥ 0 ≥ + ≥ 3 2 3 2 2 3 解 编写Matlab程序如下： c=[2;3;1]; a=[1,4,2;3,2,0]; b=[8;6]; [x,y]=linprog(c,-a,-b,[],[],zeros(3,1)) x 0 = |max yi ε i | ，这样，上面的问题就变换成 2 | | + + min t.s. x [ 1 L 1.6 可以转化为线性规划的问题 很多看起来不是线性规划的问题也可以通过变换变成线性规划的问题来解决。如： 例4 规划问题为 x x | | | + 1 b Ax ≤ ， A 和b 为相应维数的矩阵和向量。 nx T ] x = 要把上面的问题变换成线性规划问题，只要注意到事实：对任意的 ix ，存在 >i 满足 u = 0 x L ， − v x x | | n i i i 其中 i vu , i =| x i v i | + x i i u | + 2 nu i u = u [ 1 L u = ， v i ] T ， v = i | x | − = 2 v [ 1 L x i 就可以满足上面的条件。 nv ] T ，从而我们可以把上面的问题 事实上，我们只要取 这样，记 变成 ) b 例 5 n i i ) ( v u ≤ + t.s. min ∑ i 1 = vuA ( − ⎧ ⎨ vu 0 , ≥ ⎩ {min |} |max ε i x i x − y i y i 。 其中 =ε i 对于这个问题，如果我们取 i -4-
    min t.s. x 0 x 1 − ≤ y 1 , 此即我们通常的线性规划问题。 §2 运输问题(产销平衡) x 0 , x n − y n ≤ x 0 L 例 6 某商品有 m 个产地、 n 个销地，各产地的产量分别为 a ,1 L ，各销地的 b ,1 L 。若该商品由i 产地运到 j 销地的单位运价为 ijc ，问应该如何调 ma , nb 需求量分别为 运才能使总运费最省？ , 解：引入变量 ijx ，其取值为由i 产地运往 j 销地的该商品数量，数学模型为 m n ∑∑ i = 1 j = 1 ijxc ij x ij = a i , i = ,1 , m L x ij = b j , j = ,2,1 , n L ≥ 0 min n ∑ j 1 = m ∑ i 1 = x ij s.t. ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ 显然是一个线性规划问题，当然可以用单纯形法求解。 对产销平衡的运输问题，由于有以下关系式存在： n ∑ j 1 = b j = n m ∑ ∑ i 1 = j 1 = ⎛ ⎜⎜ ⎝ x ij ⎞ =⎟⎟ ⎠ n m ∑ ∑ j 1 = i 1 = ⎛ ⎜ ⎝ x ij ⎞ =⎟ ⎠ m ∑ i 1 = a i 其约束条件的系数矩阵相当特殊，可用比较简单的计算方法，习惯上称为表上作业法（由 康托洛维奇和希奇柯克两人独立地提出，简称康—希表上作业法）。 §3 指派问题 3.1 指派问题的数学模型 例 7 拟分配 n 人去干 n 项工作，每人干且仅干一项工作，若分配第i 人去干第 j 项工作，需花费 ijc 单位时间，问应如何分配工作才能使工人花费的总时间最少？ 容易看出，要给出一个指派问题的实例，只需给出矩阵 C = ( ijc ) ，C 被称为指派 问题的系数矩阵。 引入变量 ijx ，若分配i 干 j 工作，则取 1=ijx ，否则取 0=ijx 。上述指派问题的 数学模型为 min n n ∑∑ i = 1 j = 1 ijxc ij n s.t. ∑ j 1 = ijx = 1 -5-
    n ∑ ijx = 1 i 1 = 0 或=ijx 1 上述指派问题的可行解可以用一个矩阵表示，其每行每列均有且只有一个元素为 1，其余元素均为 0；可以用 ,1 L 中的一个置换表示。 n, 问题中的变量只能取 0 或 1，从而是一个 0-1 规划问题。一般的 0-1 规划问题求解 极为困难。但指派问题并不难解，其约束方程组的系数矩阵十分特殊（被称为全单位模 10或=ijx 矩阵，其各阶非零子式均为 1± ），其非负可行解的分量只能取 0 或 1，故约束 而不改变其解。此时，指派问题被转化为一个特殊的运输问题，其中 可改写为 nm = ， 1= 0≥ijx a b = j i 。 3.2 求解指派问题的匈牙利算法 由于指派问题的特殊性，又存在着由匈牙利数学家 Konig 提出的更为简便的解法 C = 一行（或一列）中每 ，则以C 或 B 为系数矩阵的 ) —匈牙利算法。算法主要依据以下事实：如果系数矩阵 ( ijb 一元素都加上或减去同一个数，得到一个新矩阵 指派问题具有相同的最优指派。 B = ( ijc ) 例 8 求解指派问题，其系数矩阵为 解 将第一行元素减去此行中的最小元素 15，同样，第二行元素减去 17，第三行 元素减去 17，最后一行的元素减去 16，得 C = 16 ⎡ ⎢ 17 ⎢ 24 ⎢ ⎢ 17 ⎣ 15 21 22 19 19 19 18 22 22 18 17 16 ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ 1B = 7401 1240 0157 0631 ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ 再将第 3 列元素各减去 1，得 3 1 0 * 5 1 0 * 7 1 0 * 4 5 3 B 2 = ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ 以 2B 为系数矩阵的指派问题有最优指派 4321 4312 ⎛ ⎜⎜ ⎝ ⎞ ⎟⎟ ⎠ 由等价性，它也是例 7 的最优指派。 有时问题会稍复杂一些。 例 9 求解系数矩阵C 的指派问题 -6- ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ 7 1 0 0 * ⎤ ⎥ ⎥ ⎥ ⎥ ⎦
    7 6 14 6 10 9 6 12 10 6 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ = C 7 9 17 14 10 12 ⎡ ⎢ 8 ⎢ 7 ⎢ ⎢ 15 ⎢ 4 ⎢ ⎣ 9 6 12 6 7 解：先作等价变换如下 12 9 7 − ⎡ ⎢ 9 6 8 − ⎢ 7 17 12 − ⎢ ⎢ 15 14 6 − ⎢ 10 7 4 ⎢ − ⎣ 7 6 7 6 4 → 7 6 14 6 10 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ 9 6 12 10 6 5 ⎡ ⎢ 2 ⎢ *0 ⎢ ⎢ 9 ⎢ 0 ⎢ ⎣ ∨ *0 3 10 8 6 2 0 5 *0 3 0 2 0*0 7 5 0 4 6 2 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ∨ ∨ 容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，但 5=n ， 最优指派还无法看出。此时等价变换还可进行下去。步骤如下： (1) 对未选出 0 元素的行打 ∨ ； (2) 对 ∨ 行中 0 元素所在列打 ∨ ； (3) 对 ∨ 列中选中的 0 元素所在行打 ∨ ； 重复（2）、（3）直到无法再打 ∨ 为止。 可以证明，若用直线划没有打 ∨ 的行与打 ∨ 的列，就得到了能够覆盖住矩阵中所 有零元素的最少条数的直线集合，找出未覆盖的元素中的最小者，令 ∨ 行元素减去此 数， ∨ 列元素加上此数，则原先选中的 0 元素不变，而未覆盖元素中至少有一个已转 变为 0，且新矩阵的指派问题与原问题也等价。上述过程可反复采用，直到能选取出足 够的 0 元素为止。例如，对例 5 变换后的矩阵再变换，第三行、第五行元素减去 2，第 一列元素加上 2，得 7 ⎡ ⎢ 4 ⎢ 0 ⎢ ⎢ 11 ⎢ 0 ⎢ ⎣ 2020 ⎤ ⎥ 0003 ⎥ 3538 ⎥ ⎥ 4008 ⎥ 0414 ⎥ ⎦ 54321 ⎛ ⎜⎜ 53142 ⎝ 。 ⎞ ⎟⎟ ⎠ 现在已可看出，最优指派为 §4 对偶理论与灵敏度分析 4.1 原始问题和对偶问题 考虑下列一对线性规划模型： ≤ s.t. max xcT Ax xb , ≥ 0 (P) 和 min ybT s.t. yAT ≥ yc , ≥ 0 (D) -7-
    分享到：
    赞 收藏

    相关推荐

    资料库

    大数据

    共收录841份资料，累计11个分类，关注成员有19位，主要包括：Matlab,统计分析,数据挖掘,Hbase,Hive,flink,kafka,spark,Storm,算法与数据结构,Hadoop

    热门标签

    Matlab 统计分析 数据挖掘 Hbase Hive flink kafka spark Storm 算法与数据结构 Hadoop

    最新资料