数学建模论文--Matlab数学建模算法全收录(数学建模比赛必备参考资料).pdf
《数学建模论文--Matlab数学建模算法全收录(数学建模比赛必备参考资料).pdf》由会员分享,可在线阅读,更多相关《数学建模论文--Matlab数学建模算法全收录(数学建模比赛必备参考资料).pdf(800页珍藏版)》请在文库网上搜索。
1、本人精通MATLAB等编程语言,可以提供以下方向的帮助 1. MATLAB/GUI/SIMULINK/C+/VC+编程问题; 2. 线性与非线性控制、智能控制、模糊控制; 3. 数值计算问题、小波分析算法、有限元问题; 4. 电机控制、电力系统、机器人路径优化、机器人控制; 5. 粒子群算法、神经网络、模拟退火算法等智能优化算法; 6. 图像处理、信号处理、语音信号处理、电子通信等方向; 有问题的朋友,可以将问题直接发到我的邮箱,24小时内给您答复!非 常欢迎大家加我为QQ好友,欢迎访问我的空间! 联系方式: QQ:626815632 邮箱: QQ空间:http:/ 声明:本资料来源于网络,切
2、勿用做商业用途!请您支持正版图书! -1- 第一章 线性规划 1 线性规划 在人们的生产实践中,经常会遇到如何利用现有资源来安排生产,以取得最大经济 效益的问题。此类问题构成了运筹学的一个重要分支数学规划,而线性规划(Linear Programming 简记 LP)则是数学规划的一个重要分支。自从 1947 年 G. B. Dantzig 提出 求解线性规划的单纯形方法以来,线性规划在理论上趋向成熟,在实用中日益广泛与深 入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后,线性 规划的适用领域更为广泛了,已成为现代管理中经常采用的基本方法之一。 1.1 线性规划的实例与定
3、义 例 1 某机床厂生产甲、 乙两种机床, 每台销售后的利润分别为 4000 元与 3000 元。 生产甲机床需用 B A、 机器加工,加工时间分别为每台 2 小时和 1 小时;生产乙机床 需用 C B A 、 、 三种机器加工,加工时间为每台各一小时。若每天可用于加工的机器时 数分别为A机器 10 小时、B机器 8 小时和C 机器 7 小时,问该厂应生产甲、乙机床各 几台,才能使总利润最大? 上述问题的数学模型: 设该厂生产 1 x 台甲机床和 2 x 乙机床时总利润最大, 则 2 1 ,x x 应满足 (目标函数) 2 1 3 4 max x x z + = ( 1) s.t.(约束条件)
4、 + + 0 , 7 8 10 2 2 1 2 2 1 2 1 x x x x x x x(2) 这里变量 2 1 ,x x 称之为决策变量, (1)式被称为问题的目标函数, (2)中的几个不等式 是问题的约束条件,记为 s.t.(即 subject to)。由于上面的目标函数及约束条件均为线性 函数,故被称为线性规划问题。 总之,线性规划问题是在一组线性约束条件的限制下,求一线性目标函数最大或最 小的问题。 在解决实际问题时,把问题归结成一个线性规划数学模型是很重要的一步,但往往 也是困难的一步,模型建立得是否恰当,直接影响到求解。而选适当的决策变量,是我 们建立有效模型的关键之一。 1.2
5、 线性规划的 Matlab 标准形式 线性规划的目标函数可以是求最大值,也可以是求最小值,约束条件的不等号可以 是小于号也可以是大于号。为了避免这种形式多样性带来的不便,Matlab 中规定线性 规划的标准形式为 x c x Tmin s . t. = ub x lb beq x Aeq b Ax其中c和x为n维列向量,A、Aeq为适当维数的矩阵,b、beq为适当维数的列向 量。 -2- 例如线性规划 b Ax x c x T s.t. max 的 Matlab 标准型为 b Ax x c x T s.t. min 1.3 线性规划问题的解的概念 一般线性规划问题的(数学)标准型为 = = n
6、 j j j x c z 1 max ( 3) s.t. = = = = n j x m i b x a j n j i j ij , , 2 , 1 0 , , 2 , 1 1 L L( 4) 可行解 满足约束条件(4)的 解 ) , , , ( 2 1 n x x x x L = ,称为线性规划问题的可行解, 而使目标函数(3)达到最大值的可行解叫最优解。 可行域 所有可行解构成的集合称为问题的可行域,记为R。 1.4 线性规划的图解法 0 2 4 6 8 10 0 1 2 3 4 5 6 7 8 9 10 x2=7 2x1+x2=10 x1+x2=8 z=12 (2,6)图1 线性规划的
7、图解示意图 图解法简单直观,有助于了解线性规划问题求解的基本原理。我们先应用图解法来 求解例 1。对于每一固定的值z,使目标函数值等于z的点构成的直线称为目标函数等 位线,当z变动时,我们得到一族平行直线。对于例 1,显然等位线越趋于右上方,其 上的点具有越大的目标函数值。不难看出,本例的最优解为 T x ) 6 , 2 ( * = ,最优目标值 26 * = z 。 从上面的图解过程可以看出并不难证明以下断言: (1)可行域R可能会出现多种情况。R可能是空集也可能是非空集合,当R非空 时,它必定是若干个半平面的交集(除非遇到空间维数的退化) 。R既可能是有界区域, 也可能是无界区域。 (2)
8、 在R非空时, 线性规划既可以存在有限最优解, 也可以不存在有限最优解 (其 目标函数值无界) 。 -3- (3)若线性规划存在有限最优解,则必可找到具有最优目标函数值的可行域R的 “顶点” 。 上述论断可以推广到一般的线性规划问题, 区别只在于空间的维数。 在一般的n维 空间中,满足一线性等式 = = n i i i b x a 1 的点集被称为一个超平面,而满足一线性不等式 = n i i i b x a 1 (或 = n i i i b x a 1 )的点集被称为一个半空间(其中 ) , , ( 1 n a a L 为一n维行 向量,b为一实数) 。若干个半空间的交集被称为多胞形,有界的
9、多胞形又被称为多面 体。易见,线性规划的可行域必为多胞形(为统一起见,空集 也被视为多胞形) 。 在一般n维空间中,要直接得出多胞形“顶点”概念还有一些困难。二维空间中的顶点 可以看成为边界直线的交点, 但这一几何概念的推广在一般n维空间中的几何意义并不 十分直观。为此,我们将采用另一途径来定义它。 定义 1 称n 维空间中的区域R 为一凸集,若 R x x 2 1 , 及 ) 1 , 0 ( ,有 R x x + 2 1 ) 1 ( 。 定义 2 设R为n维空间中的一个凸集,R中的点x被称为R的一个极点,若不 存在 R x x 2 1 、 及 ) 1 , 0 ( ,使得 2 1 ) 1 (
10、x x x + = 。 定义 1 说明凸集中任意两点的连线必在此凸集中;而定义 2 说明,若x是凸集R 的一个极点,则x不能位于R中任意两点的连线上。不难证明,多胞形必为凸集。同 样也不难证明,二维空间中可行域R的顶点均为R的极点(R也没有其它的极点) 。 1.5 求解线性规划的 Matlab 解法 单纯形法是求解线性规划问题的最常用、最有效的算法之一。这里我们就不介绍 单纯形法, 有兴趣的读者可以参看其它线性规划书籍。 下面我们介绍线性规划的 Matlab 解法。 Matlab 中线性规划的标准型为 x c x Tmin s . t. = ub x lb beq x Aeq b Ax基本函数
11、形式为 linprog(c,A,b),它的返回值是向量x的值。还有其它的一些函数调用形 式(在 Matlab 指令窗运行 help linprog 可以看到所有的函数调用形式) ,如: x,fval=linprog(c,A,b,Aeq,beq,LB,UB,X 0 ,OPTIONS) 这里 fval 返回目标函数的值, LB 和 UB 分别是变量x的下界和上界, 0 x 是x的初始值, OPTIONS 是控制参数。 例 2 求解下列线性规划问题 3 2 1 5 3 2 max x x x z + = s.t. 7 3 2 1 = + + x x x 10 5 2 3 2 1 + x x x 12
12、 3 3 2 1 + + x x x 0 , , 3 2 1 x x x -4- 解 (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 (ii)将M文件存盘,并命名为example1.m。 (iii)在Matlab指令窗运行example1即可得所求结果。 例3 求解线性规划问题 3 2 1 3 2 min x x x z + + = + + + 0 , , 6 2 3 8 2 4 3 2 1 2 1 3 2 1 x x
13、x x x x x x解 编写Matlab程序如下: c=2;3;1; a=1,4,2;3,2,0; b=8;6; x,y=linprog(c,-a,-b,zeros(3,1) 1.6 可以转化为线性规划的问题 很多看起来不是线性规划的问题也可以通过变换变成线性规划的问题来解决。如: 例4 规划问题为 b Ax x x x n + + +t. s. | | | | | | min 2 1 L其中 T n x x x 1 L = ,A和b为相应维数的矩阵和向量。 要把上面的问题变换成线性规划问题,只要注意到事实:对任意的 i x ,存在 0 , i i v u 满足 i i i v u x =
14、, i i i v u x + = | | 事实上,我们只要取 2 | | i i i x x u + = , 2 | | i i i x x v = 就可以满足上面的条件。 这样,记 T n u u u 1 L = , T n v v v 1 L = ,从而我们可以把上面的问题 变成 = + n i i i v u 1 ) ( min 0 , ) (t. s. v u b v u A例 5 | | max min i y x i i 其中 i i i y x = 。 对于这个问题,如果我们取 | | max 0 i y i x = ,这样,上面的问题就变换成 -5- 0 min x 0 0
15、1 1 , , t. s. x y x x y x n n L 此即我们通常的线性规划问题。 2 运输问题(产销平衡) 例 6 某商品有m个产地、n个销地,各产地的产量分别为 m a a , , 1 L ,各销地的 需求量分别为 n b b , , 1 L 。若该商品由i产地运到 j销地的单位运价为 ij c ,问应该如何调 运才能使总运费最省? 解:引入变量 ij x ,其取值为由i产地运往 j销地的该商品数量,数学模型为 = m i n j ij ij x c 11 min s.t. = = = = = = 0 , , 2 , 1 , , , 1 , 1 1 ij m i j ij n j
16、 i ij x n j b x m i a x L L显然是一个线性规划问题,当然可以用单纯形法求解。 对产销平衡的运输问题,由于有以下关系式存在: = = = = = = = m i i n j n j m i ij m i n j ij j a x x b 1 11 1 11其约束条件的系数矩阵相当特殊, 可用比较简单的计算方法, 习惯上称为表上作业法 (由 康托洛维奇和希奇柯克两人独立地提出,简称康希表上作业法) 。 3 指派问题 3.1 指派问题的数学模型 例 7 拟分配n人去干n项工作,每人干且仅干一项工作,若分配第i人去干第 j 项工作,需花费 ij c 单位时间,问应如何分配工作
17、才能使工人花费的总时间最少? 容易看出,要给出一个指派问题的实例,只需给出矩阵 ) ( ij c C = ,C被称为指派 问题的系数矩阵。 引入变量 ij x ,若分配i干 j工作,则取 1 = ij x ,否则取 0 = ij x 。上述指派问题的 数学模型为 = n i n j ij ij x c 11 min s.t. = = n j ij x 1 1 -6- = = n i ij x 1 1 1 0或 = ij x 上述指派问题的可行解可以用一个矩阵表示,其每行每列均有且只有一个元素为 1,其余元素均为 0;可以用 n , , 1 L 中的一个置换表示。 问题中的变量只能取 0或 1,
18、从而是一个 0-1 规划问题。一般的 0-1 规划问题求解 极为困难。但指派问题并不难解,其约束方程组的系数矩阵十分特殊(被称为全单位模 矩阵, 其各阶非零子式均为 1 ) , 其非负可行解的分量只能取 0或 1, 故约束 1 0或 = ij x 可改写为 0 ij x 而不改变其解。此时,指派问题被转化为一个特殊的运输问题,其中 n m = , 1 = = j i b a 。 3.2 求解指派问题的匈牙利算法 由于指派问题的特殊性,又存在着由匈牙利数学家 Konig 提出的更为简便的解法 匈牙利算法。算法主要依据以下事实:如果系数矩阵 ) ( ij c C = 一行(或一列)中每 一元素都加
19、上或减去同一个数,得到一个新矩阵 ) ( ij b B = ,则以C或B为系数矩阵的 指派问题具有相同的最优指派。 例 8 求解指派问题,其系数矩阵为 = 16 22 19 17 17 18 22 24 18 19 21 17 22 19 15 16 C 解 将第一行元素减去此行中的最小元素 15,同样,第二行元素减去 17,第三行 元素减去 17,最后一行的元素减去 16,得 = 0 6 3 1 0 1 5 7 1 2 4 0 7 4 0 1 1 B 再将第 3 列元素各减去 1,得 = * * * * 2 0 5 3 1 0 0 5 7 1 1 4 0 7 3 0 1 B 以 2 B 为系
20、数矩阵的指派问题有最优指派 4 3 1 2 4 3 2 1由等价性,它也是例 7的最优指派。 有时问题会稍复杂一些。 例 9 求解系数矩阵C的指派问题 -7- = 6 10 7 10 4 10 6 6 14 15 12 14 12 17 7 6 6 6 9 8 9 7 9 7 12 C 解:先作等价变换如下 2 6 3 6 0 4 0 * 0 8 9 5 7 5 10 * 0 0 * 0 0 3 2 2 0 2 * 0 5 6 10 7 10 4 10 6 6 14 15 12 14 12 17 7 6 6 6 9 8 9 7 9 7 12 4 6 7 6 7容易看出, 从变换后的矩阵中只能选
21、出四个位于不同行不同列的零元素, 但 5 = n , 最优指派还无法看出。此时等价变换还可进行下去。步骤如下: (1) 对未选出 0元素的行打 ; (2) 对 行中 0 元素所在列打 ; (3) 对 列中选中的 0 元素所在行打 ; 重复(2) 、 (3)直到无法再打 为止。 可以证明,若用直线划没有打 的行与打 的列,就得到了能够覆盖住矩阵中所 有零元素的最少条数的直线集合,找出未覆盖的元素中的最小者,令 行元素减去此 数, 列元素加上此数,则原先选中的 0 元素不变,而未覆盖元素中至少有一个已转 变为 0,且新矩阵的指派问题与原问题也等价。上述过程可反复采用,直到能选取出足 够的 0 元素
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 建模 论文 Matlab 算法 收录 比赛 必备 参考资料