算法大全matlab全国大学生数学建模材料.pdf

发布时间：2022-06-05 发布人：admin 分类：说明书资料大小：4.21M 资料格式：pdf 举报版权申诉

songtzu-4098121-4744302543286530680.pdf-第1页.png

第1页 / 共738页

songtzu-4098121-4744302543286530680.pdf-第2页.png

第2页 / 共738页

songtzu-4098121-4744302543286530680.pdf-第3页.png

第3页 / 共738页

songtzu-4098121-4744302543286530680.pdf-第4页.png

第4页 / 共738页

songtzu-4098121-4744302543286530680.pdf-第5页.png

第5页 / 共738页

songtzu-4098121-4744302543286530680.pdf-第6页.png

第6页 / 共738页

songtzu-4098121-4744302543286530680.pdf-第7页.png

第7页 / 共738页

songtzu-4098121-4744302543286530680.pdf-第8页.png

第8页 / 共738页

算法大章全1到19.pdf

算法大全1到12章.pdf

第一章线性规划

第二章整数规划

第三章非线性规划

第四章动态规划

第五章图与网络

第六章排队论.pdf

第七章对策论

第八章层次分析法

第九章插值与拟合

第十章数据的统计描述和分析

第十一章方差分析

第十二章回归分析

第十三章微分方程建模

第十四章稳定状态模型

第十五章常微分方程的解法

第十六章差分方程模型

第十七章马氏链模型

第十八章变分法模型

第十九章神经网络模型

第二十章偏微分方程的数值解

第二十一章目标规划

第二十二章模糊数学模型

第二十三章现代优化算法

第二十四章时间序列模型

第二十五章存贮论

第二十六章经济与金融中的优化问题

第二十七章生产与服务运作管理中的优化问题

第二十八章灰色系统理论及其应用

第二十九章多元分析

§1 聚类分析

§2 聚类分析案例

§3 主成分分析

§4 主成分分析案例

§5 因子分析

第三十章偏最小二乘回归

目录第一章线性规划第二章整数规划第三章非线性规划第四章动态规划第五章图与网络模型及方法第六章排队论模型第七章对策论第八章层次分析法第九章插值与拟合第十章数据的统计描述和分析第十一章方差分析第十二章回归分析第十三章微分方程建模第十四章稳定状态模型第十五章常微分方程的解法第十六章差分方程模型第十七章马氏链模型第十八章动态优化模型第十九章神经网络模型第二十章偏微分方程的数值解第二十一章目标规划第二十二章模糊数学模型第二十三章现代优化算法第二十四章时间序列模型第二十五章存贮论第二十六章经济与金融中的优化问题第二十七章生产与服务运作管理中的优化问题第二十八章灰色系统理论及其应用第二十九章多元分析第三十章偏最小二乘回归

§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-

分享到：

赞收藏

资料库

算法大全matlab全国大学生数学建模材料.pdf

相关推荐

考试认证

热门标签

最新资料