数学建模简明教程课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《数学建模简明教程课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 建模 简明 教程 课件
- 资源描述:
-
1、数学建模简明教程国家精品课程国家精品课程第一章第一章 规划理论及模型规划理论及模型 一、一、引言引言 二、线性规划模型二、线性规划模型 三、整数线性规划模型三、整数线性规划模型 四、四、0-10-1整数规划模型整数规划模型 五、五、非线性规划模型非线性规划模型 六、六、多目标规划模型多目标规划模型目录下页返回上页结束 七、动态七、动态规划模型规划模型一、引言一、引言目录下页返回上页结束 我们从我们从2005年年“高教社杯高教社杯”全国大学生数模全国大学生数模竞竞赛的赛的B题题“DVD在线租赁在线租赁”问题的第二问和第三问问题的第二问和第三问 谈起谈起.其中第二个问题是一个如何来分配有限资源,其
2、中第二个问题是一个如何来分配有限资源,从而达到人们期望目标的优化分配数学模型从而达到人们期望目标的优化分配数学模型.它它在运筹学中处于中心的地位在运筹学中处于中心的地位.这类问题一般可以这类问题一般可以归结为归结为数学规划模型数学规划模型.目录下页返回上页结束 规划模型的应用极其广泛,其作用已为越来规划模型的应用极其广泛,其作用已为越来 来越急速地渗透于工农业生产、商业活动、军事来越急速地渗透于工农业生产、商业活动、军事 行为核科学研究的各个方面,为社会节省的财富、行为核科学研究的各个方面,为社会节省的财富、创造的价值无法估量创造的价值无法估量.特别是在数模竞赛过程中,规划模型是最常特别是在数
3、模竞赛过程中,规划模型是最常 见的一类数学模型见的一类数学模型.从从92-06年全国大学生数模竞年全国大学生数模竞 越多的人所重视越多的人所重视.随着计算机的逐渐普及,它越随着计算机的逐渐普及,它越 赛试题的解题方法统计结果来看,规划模型共出赛试题的解题方法统计结果来看,规划模型共出 现了现了15次,占到了次,占到了50%,也就是说每两道竞赛题,也就是说每两道竞赛题 中就有一道涉及到利用规划理论来分析、求解中就有一道涉及到利用规划理论来分析、求解.目录下页返回上页结束二、线性规划模型二、线性规划模型 线性规划模型是所有规划模型中最基本、最线性规划模型是所有规划模型中最基本、最例例1(食谱问题)
4、设有食谱问题)设有 n 种食物,各含种食物,各含 m 种营养种营养素,第素,第 j 种食物中第种食物中第 i 中营养素的含量为中营养素的含量为 aij,n 种种食物价格分别为食物价格分别为c1,c2,cn,请确定食谱中,请确定食谱中n 种食种食物的数量物的数量x1,x2,xn,要求在食谱中,要求在食谱中 m 种营养素种营养素简单的一种简单的一种.2.1 线性规划模型的标准形式线性规划模型的标准形式 的含量分别不低于的含量分别不低于b1,b2,bm 的情况下,使得总的情况下,使得总 的费用最低的费用最低.目录下页返回上页结束 首先根据食物数量及价格可写出食谱费用为首先根据食物数量及价格可写出食谱
5、费用为 1 122,nnc xc xc x1 122.iiinna xa xa x其次食谱中第其次食谱中第 i 种营养素的含量为种营养素的含量为 因此上述问题可表述为:因此上述问题可表述为:11221111221121122222112212min.0,0,0nnnnnnmmmnnmnc xc xc xaxaxaxbaxaxaxbs taxaxaxbxxx 解解目录下页返回上页结束 上述食谱问题就是一个典型的线性规划问题,上述食谱问题就是一个典型的线性规划问题,寻求以线性函数的最大(小)值为目标的数学模型寻求以线性函数的最大(小)值为目标的数学模型.它是指在一组线性的等式或不等式的约束条件下,
6、它是指在一组线性的等式或不等式的约束条件下,目录下页返回上页结束 线性规划模型的三种形式线性规划模型的三种形式 nqjxqjxmsibxaxaxaspibxaxaxapibxaxaxatsxcxczjjininiiininiiininiinn,1,0,1,0,1,1,1,.min(max)22112211221111系系数数矩矩阵阵 mnmmnnaaaaaaaaaA212222111211目标函数目标函数 价值向量价值向量 价值系数价值系数 决策变量决策变量Tnccc),(1 njcj,2,1,njxj,2,1,右端向量右端向量 mbbb1非负约束非负约束自由变量自由变量TiAjA 一般形式一
7、般形式目录下页返回上页结束 规范形式规范形式 标准形式标准形式 0.minxbAxtsxcT 0.minxbAxtsxcT 三种形式的三种形式的LP问题全都是等价的,即一种问题全都是等价的,即一种形式的形式的LP可以简单的变换为另一种形式的可以简单的变换为另一种形式的LP,且它们有相同的解且它们有相同的解.以下我们仅将一般形式化成规范形式和标准以下我们仅将一般形式化成规范形式和标准形式形式.目录下页返回上页结束目标函数的转化目标函数的转化 xoz-z)(minmaxzz 目录下页返回上页结束约束条件和变量的转化约束条件和变量的转化 为了把一般形式的为了把一般形式的LP问题变换为规范形式,问题变
8、换为规范形式,可用下述两个不等式约束去替代可用下述两个不等式约束去替代 njijijbxa1 njijijbxa1 njijijbxa1)()(我们必须消除等式约束和符号无限制变量我们必须消除等式约束和符号无限制变量.在一在一 般形式的般形式的LP中,一个等式约束中,一个等式约束目录下页返回上页结束 jjjxxx这样就把一般形式的这样就把一般形式的LP变换为规范形式变换为规范形式.变量变量 和和 ,并设,并设0 jx0 jx 对于一个无符号限制变量对于一个无符号限制变量 ,引进两个非负,引进两个非负jx目录下页返回上页结束对于一个不等式约束对于一个不等式约束 njijijbxa1 njiiij
9、ijsbsxa10,代替上述的不等式约束代替上述的不等式约束.对符号无限制变量的处理可按上述方法进行对符号无限制变量的处理可按上述方法进行.可引入一个可引入一个剩余变量剩余变量 ,is必须消除其不等式约束和符号无限制变量必须消除其不等式约束和符号无限制变量.为了把一般形式的为了把一般形式的LPLP问题变换为标准形式,问题变换为标准形式,目录下页返回上页结束 对于不等式约束对于不等式约束 njijijbxa1 njiiijijrbrxa10,代替上述的不等式约束代替上述的不等式约束.这样就把一般形式的这样就把一般形式的LP变换为标准形式变换为标准形式.可引入一个可引入一个松弛变量松弛变量ir,用
10、,用目录下页返回上页结束 针对标准形式的线性规划问题,其解的理论针对标准形式的线性规划问题,其解的理论分析已经很完备,在此基础上也提出了很好的算分析已经很完备,在此基础上也提出了很好的算 单纯形方法是线性规划问题的最为基础、也单纯形方法是线性规划问题的最为基础、也法法单纯形方法及其相应的变化形式(两阶段单纯形方法及其相应的变化形式(两阶段2.2 线性规划模型的求解线性规划模型的求解 法,对偶单纯形法等)法,对偶单纯形法等).是最核心的算法是最核心的算法.它是一个迭代算法,先从一个它是一个迭代算法,先从一个特殊的可行解(极点)出发,通过判别条件去判特殊的可行解(极点)出发,通过判别条件去判 断该
11、可行解是否为最优解(或问题无界),若不断该可行解是否为最优解(或问题无界),若不 目录下页返回上页结束是最优解,则根据相应规则,迭代到下一个更好是最优解,则根据相应规则,迭代到下一个更好的软件包的软件包有有LINGO和和LINDO.的可行解(极点),直到最优解(或问题无界)的可行解(极点),直到最优解(或问题无界).关于线性规划问题解的理论和单纯形法具体的求关于线性规划问题解的理论和单纯形法具体的求解过程可参见文献解过程可参见文献1.然后在实际应用中,特别是数学建模过程中,然后在实际应用中,特别是数学建模过程中,遇到线性规划问题的求解,我们一般都是利用现遇到线性规划问题的求解,我们一般都是利用
12、现 有的软件进行求解,此时通常并不要求线性规划有的软件进行求解,此时通常并不要求线性规划 问题问题是标准形式是标准形式.比较常用的求解线性规划模型比较常用的求解线性规划模型 目录下页返回上页结束运输问题运输问题例例2 2 设要从甲地调出物资设要从甲地调出物资20002000吨,从乙地调出物吨,从乙地调出物 资资1100吨,分别供给吨,分别供给A地地1700吨、吨、B地地1100吨、吨、C假定运费与运量成正比假定运费与运量成正比.在这种情况下,采用不在这种情况下,采用不地地200吨、吨、D地地100吨吨.已知每吨运费如表已知每吨运费如表1.1所示所示.同的调拨计划,运费就可能不一样同的调拨计划,
13、运费就可能不一样.现在问:怎现在问:怎样才能找出一个运费最省的调拨计划?样才能找出一个运费最省的调拨计划?目录下页返回上页结束1572521甲甲15375151乙乙DCBA表表 1.1销销地地运运费费产产地地目录下页返回上页结束2423222114131211153751511572521minxxxxxxxxf 解解乙乙11x21x22x23x24x2000411 jix1100412 jix1700211 iix1100212 iix200213 iix100214 iix甲甲DCBA)4,3,2,1;2,1(0 jixij12x13x14x目录下页返回上页结束s.t.1112131421
14、222324112112221323142420001100170011002001000,1,2;1,2,3,4ijxxxxxxxxxxxxxxxxxij 1112131421222324min212571551513715fxxxxxxxx目录下页返回上页结束一般的运输问题可以表述如下:一般的运输问题可以表述如下:,1,2,;1,2,ijximjn jB运一个单位的产品到运一个单位的产品到 nijmiiba11iA已知已知,从,从在满足供需要求的条件下,使总运输费用最省在满足供需要求的条件下,使总运输费用最省.个发点个发点mmiAi,2,1,要把某种物资从要把某种物资从 ,调运给需要这种物
15、资的调运给需要这种物资的 个收点个收点nnjBj,2,1,.的运价为的运价为ijc现在需要确定一个调运方案,即确现在需要确定一个调运方案,即确到到的运输量的运输量iAjB定由定由目录下页返回上页结束数学模型:数学模型:1111min,1,2,s.t.,1,2,0,1,2,;1,2,mnijijijnijijmijjiijzc xxa imxbjnxim jn 目录下页返回上页结束 类似与将一般的线性规划问题转化为其标准类似与将一般的线性规划问题转化为其标准否则,称为不平衡的运输问题,包括:否则,称为不平衡的运输问题,包括:即即 nijmiiba11,则称该问题为平衡的运输问题,则称该问题为平衡
16、的运输问题.总产量总产量总销量和总产量总销量和总产量总销量总销量.形式,我们总可以通过引入假想的销地或产地,形式,我们总可以通过引入假想的销地或产地,将不平衡的运输问题转化为平衡的运输问题将不平衡的运输问题转化为平衡的运输问题.从从而,我们的重点就是解决平衡运输问题的求解而,我们的重点就是解决平衡运输问题的求解.若其中各产地的总产量等于各销地的总销量,若其中各产地的总产量等于各销地的总销量,目录下页返回上页结束该方法将单纯形法与平衡的运输问题的特殊性质该方法将单纯形法与平衡的运输问题的特殊性质运输问题及其解法的进一步介绍参加文献运输问题及其解法的进一步介绍参加文献2.显然,运输问题是一个标准的
17、线性规划问题,显然,运输问题是一个标准的线性规划问题,因而当然可以运用单纯形方法求解因而当然可以运用单纯形方法求解.但由于平衡但由于平衡的运输问题的特殊性质,它还可以用其它的一些的运输问题的特殊性质,它还可以用其它的一些特殊方法求解,其中最常用的就是表上作业法,特殊方法求解,其中最常用的就是表上作业法,结合起来,很方便地实行了运输问题的求解结合起来,很方便地实行了运输问题的求解.关于关于目录下页返回上页结束 对于线性规划问题,如果要求其决策变量取对于线性规划问题,如果要求其决策变量取整数值,则称该问题为整数线性规划问题整数值,则称该问题为整数线性规划问题.平面法和分支定界法是两种常用的求解整数
18、线性平面法和分支定界法是两种常用的求解整数线性 对于整数线性规划问题的求解,其难度和运对于整数线性规划问题的求解,其难度和运三、整数线性规划模型三、整数线性规划模型算量远大于同规模的线性规划问题算量远大于同规模的线性规划问题.Gomory割割规划问题的方法(见文献规划问题的方法(见文献1).此外,同线性规此外,同线性规划模型一样,我们也可以运用划模型一样,我们也可以运用LINGO和和LINDO软软件包来求解整数线性规划模型件包来求解整数线性规划模型.目录下页返回上页结束如何求解整数线性规划模型如何求解整数线性规划模型.以以1988年美国大学生数学建模竞赛年美国大学生数学建模竞赛B题为例,题为例
19、,说明整数线性规划模型的建立及用说明整数线性规划模型的建立及用LINGO软件包软件包例例3 有七种规格的包装箱要装到两节铁路平板车有七种规格的包装箱要装到两节铁路平板车上去上去.包装箱的宽和高是一样的,但厚度(包装箱的宽和高是一样的,但厚度(t,以,以cm 计)及重量(计)及重量(w,以,以kg计)是不同的计)是不同的.表表1给出给出了每种包装箱的厚度、重量以及数量了每种包装箱的厚度、重量以及数量.每节平板每节平板车有车有10.2 m 长的地方可用来装包装箱(像面包片长的地方可用来装包装箱(像面包片那样),载重为那样),载重为40t.由于当地货运的限制,对于由于当地货运的限制,对于目录下页返回
20、上页结束C5,C6,C7 类包装箱的总数有一个特别的限制:这类包装箱的总数有一个特别的限制:这类箱子所占的空间(厚度)不能超过类箱子所占的空间(厚度)不能超过302.7cm.试试把包装箱装到平板车上,使得浪费的空间最小把包装箱装到平板车上,使得浪费的空间最小.种类种类C1C2C3C4C5C6 C7t/cm48.753.061.372.048.752.064.0w/kg2000 3000 10005004000 2000 1000n/件件8796648目录下页返回上页结束 为在第为在第 节车上装载第节车上装载第 件包装箱的件包装箱的,i jxji解解 令令种包装箱需要种包装箱需要);1,2,7;
21、1,2ij ini数量数量(为第为第 下面我们建立该问题的整数线性规划模型下面我们建立该问题的整数线性规划模型.节车的载重量;节车的载重量;jcwjs为第为第302.7s 为特殊限制为特殊限制().).装的件数;装的件数;iwi为第为第种包装箱的重量;种包装箱的重量;it为第为第i种种jclj包装箱的厚度;包装箱的厚度;为第为第 节车的长度节车的长度(1020jcl );目录下页返回上页结束1)约束条件约束条件两节车的装箱数不能超过需要装的件数,即:两节车的装箱数不能超过需要装的件数,即:每节车可装的长度不能超过车能提供的长度:每节车可装的长度不能超过车能提供的长度:12,1,2,7iiixx
22、ni 71,1,2iijjit xclj 每节车可装的重量不超过车能够承受的重量:每节车可装的重量不超过车能够承受的重量:71,1,2iijjiw xcwj 目录下页返回上页结束对于对于C5,C6,C7类包装箱的总数的特别限制:类包装箱的总数的特别限制:2)目标函数目标函数7125()iiiit xxs 浪费的空间最小,即包装箱的总厚度最大:浪费的空间最小,即包装箱的总厚度最大:7121max()()iiiif xtxx 目录下页返回上页结束3)整数线性规划模型整数线性规划模型 7121max()iiiitxx 1271717125 1,2,7 1,2 1,2s.t.()0 1,2,7;1,2
23、iiiiijjiiijjiiiiiijxxnit xcljw xcwjtxxsxij 取取 整整 数数目录下页返回上页结束4)模型求解模型求解运用运用LINGO软件求解得到:软件求解得到:*4191210,2039.44605120 xf5)最优解的分析说明最优解的分析说明优的装车方案,此时装箱的总长度为优的装车方案,此时装箱的总长度为1019.7cm,两节车共装箱的总长度为两节车共装箱的总长度为2039.4cm.由上一步中的求解结果可以看出,由上一步中的求解结果可以看出,*x即为最即为最 但是,上述求解结果只是其中一种最优的装但是,上述求解结果只是其中一种最优的装车方案,即此答案并不唯一车方
24、案,即此答案并不唯一.目录下页返回上页结束 0-1整数规划是整数规划的特殊情形,它要求整数规划是整数规划的特殊情形,它要求线性规划模型中的决策变量线性规划模型中的决策变量 xij 只能取值为只能取值为0或或1.单隐枚举法,该方法是一种基于判断条件(过滤单隐枚举法,该方法是一种基于判断条件(过滤 0-1整数规划模型的求解目前并没有非常好的整数规划模型的求解目前并没有非常好的四、四、0-10-1整数规划模型整数规划模型 算法,对于变量比较少的情形,我们可以采取简算法,对于变量比较少的情形,我们可以采取简条件)的穷举法条件)的穷举法.我们也可以利用我们也可以利用LINGO和和LINDO软件包来求软件
25、包来求解解0-1整数规划模型整数规划模型.目录下页返回上页结束例例4 4 有有 n 个物品,编号为个物品,编号为 1,2,n,第,第 i 件物品件物品重重 ai 千克,价值为千克,价值为 ci 元,现有一个载重量不超过元,现有一个载重量不超过大,应如何装载这些物品?大,应如何装载这些物品?a 千克的背包,为了使装入背包的物品总价值最千克的背包,为了使装入背包的物品总价值最用变量用变量 xi 表示物品表示物品 i 是否装包,是否装包,i=1,2,n,并令:并令:解解目录下页返回上页结束可得到背包问题的规划模型为:可得到背包问题的规划模型为:11maxs.t.011,2,niiiniiiifc x
展开阅读全文