数学建模培训规划理论及模型课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《数学建模培训规划理论及模型课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 建模 培训 规划 理论 模型 课件
- 资源描述:
-
1、下下回回停停一、引言一、引言 二、线性规划模型二、线性规划模型三、整数线性规划模型三、整数线性规划模型第一讲第一讲 规划理论及模型规划理论及模型 四、四、0-1整数规划模型整数规划模型 五、非线性规划模型五、非线性规划模型 六、多目标规划模型六、多目标规划模型 七、动态规划模型七、动态规划模型一、引言一、引言 我们从我们从2005年年“高教社杯高教社杯”全国大学生数模全国大学生数模竞竞谈起谈起.其中第二个问题是一个如何来分配有限资源,其中第二个问题是一个如何来分配有限资源,从而达到人们期望目标的优化分配数学模型从而达到人们期望目标的优化分配数学模型.它它在运筹学中处于中心的地位在运筹学中处于中
2、心的地位.这类问题一般可以这类问题一般可以归结为归结为 数学规划模型数学规划模型.赛的赛的B题题“DVD在线租赁在线租赁”问题的第二问和第三问问题的第二问和第三问 规划模型的应用极其广泛,其作用已为越来规划模型的应用极其广泛,其作用已为越来来越急速地渗透于工农业生产、商业活动、军事来越急速地渗透于工农业生产、商业活动、军事行为核科学研究的各个方面,为社会节省的财富、行为核科学研究的各个方面,为社会节省的财富、创造的价值无法估量创造的价值无法估量.特别是在数模竞赛过程中,规划模型是最常特别是在数模竞赛过程中,规划模型是最常见的一类数学模型见的一类数学模型.从从92-06年全国大学生数模竞年全国大
3、学生数模竞越多的人所重视越多的人所重视.随着计算机的逐渐普及,它越随着计算机的逐渐普及,它越赛试题的解题方法统计结果来看,规划模型共出赛试题的解题方法统计结果来看,规划模型共出现了现了15次,占到了次,占到了50%,也就是说每两道竞赛题,也就是说每两道竞赛题中就有一道涉及到利用规划理论来分析、求解中就有一道涉及到利用规划理论来分析、求解.二、线性规划模型二、线性规划模型 线性规划模型是所有规划模型中最基本、最线性规划模型是所有规划模型中最基本、最例例1.(食谱问题)设有食谱问题)设有 n 种食物,各含种食物,各含 m 种营养种营养素,第素,第 j 种食物中第种食物中第 i 中营养素的含量为中营
4、养素的含量为 aij,n 种种食物价格分别为食物价格分别为c1,c2,cn,请确定食谱中,请确定食谱中n 种食种食物的数量物的数量x1,x2,xn,要求在食谱中,要求在食谱中 m 种营养素种营养素简单的一种简单的一种.2.1 2.1 线性规划模型的标准形式线性规划模型的标准形式 的含量分别不低于的含量分别不低于b1,b2,bm 的情况下,使得总的情况下,使得总总的费用最低总的费用最低.首先根据食物数量及价格可写出食谱费用为首先根据食物数量及价格可写出食谱费用为 其次食谱中第其次食谱中第 i 种营养素的含量为种营养素的含量为 因此上述问题可表述为:因此上述问题可表述为:1 122,nnc xc
5、xc x1 122.iiinna xa xa x 1 12211 11221121 1222221 12212min.0,0,0nnnnnnmmmnnmnc xc xc xaxaxaxbaxaxaxbs taxaxaxbxxx 解解 上述食谱问题就是一个典型的线性规划问题,上述食谱问题就是一个典型的线性规划问题,寻求以线性函数的最大(小)值为目标的数学模寻求以线性函数的最大(小)值为目标的数学模型型.它是指在一组线性的等式或不等式的约束条件下,它是指在一组线性的等式或不等式的约束条件下,线性规划模型的三种形式线性规划模型的三种形式 一般形式一般形式 目标函数目标函数 价值向量价值向量 价值系数
6、价值系数 决策变量决策变量Tnccc),(1 njcj,2,1,njxj,2,1,nqjxqjxmsibxaxaxaspibxaxaxapibxaxaxatsxcxczjjininiiininiiininiinn,1,0,1,0,1,1,1,.min(max)22112211221111右端向量右端向量 mbbb1系系数数矩矩阵阵 mnmmnnaaaaaaaaaA212222111211非负约束非负约束自由变量自由变量TiAjA 规范形式规范形式 标准形式标准形式 0.minxbAxtsxcT 0.minxbAxtsxcT 三种形式的三种形式的LP问题全都是等价的,即一种问题全都是等价的,即一
7、种形式的形式的LP可以简单的变换为另一种形式的可以简单的变换为另一种形式的LP,且它们有相同的解且它们有相同的解.以下我们仅将一般形式化成规范形式和标准以下我们仅将一般形式化成规范形式和标准形式形式.目标函数的转化目标函数的转化 xoz-z)(minmaxzz 约束条件和变量的转化约束条件和变量的转化 为了把一般形式的为了把一般形式的LP问题变换为规范形式,问题变换为规范形式,我们必须消除等式约束和符号无限制变量我们必须消除等式约束和符号无限制变量.在一在一般形式的般形式的LP中,一个等式约束中,一个等式约束可用下述两个不等式约束去替代可用下述两个不等式约束去替代 njijijbxa1 nji
8、jijbxa1 njijijbxa1)()(jjjxxx这样就把一般形式的这样就把一般形式的LP变换为规范形式变换为规范形式.对于一个无符号限制变量对于一个无符号限制变量 ,引进两个非负,引进两个非负变量变量 和和 ,并设,并设jx0 jx0 jx为了把一般形式的为了把一般形式的LPLP问题变换为标准形式,问题变换为标准形式,必须消除其不等式约束和符号无限制变量必须消除其不等式约束和符号无限制变量.对于一个不等式约束对于一个不等式约束 njijijbxa1 njiiijijsbsxa10,代替上述的不等式约束代替上述的不等式约束.对符号无限制变量的处理可按上述方法进行对符号无限制变量的处理可按
9、上述方法进行.可引入一个可引入一个剩余变量剩余变量 ,is用用 对于不等式约束对于不等式约束 njijijbxa1 njiiijijrbrxa10,代替上述的不等式约束代替上述的不等式约束 这样就把一般形式的这样就把一般形式的LP变换为标准形式变换为标准形式.可引入一个可引入一个松弛变量松弛变量ir,用,用 针对标准形式的线性规划问题,其解的理论针对标准形式的线性规划问题,其解的理论分析已经很完备,在此基础上也提出了很好的算分析已经很完备,在此基础上也提出了很好的算 单纯形方法是线性规划问题的最为基础、也单纯形方法是线性规划问题的最为基础、也法法单纯形方法及其相应的变化形式(两阶段单纯形方法及
10、其相应的变化形式(两阶段2.2 2.2 线性规划模型的求解线性规划模型的求解 法,对偶单纯形法等)法,对偶单纯形法等).是最核心的算法。它是一个迭代算法,先从一个是最核心的算法。它是一个迭代算法,先从一个特殊的可行解(极点)出发,通过判别条件去判特殊的可行解(极点)出发,通过判别条件去判断该可行解是否为最优解(或问题无界),若不断该可行解是否为最优解(或问题无界),若不是最优解,则根据相应规则,迭代到下一个更好是最优解,则根据相应规则,迭代到下一个更好的可行解(极点),直到最优解(或问题无界)的可行解(极点),直到最优解(或问题无界).关于线性规划问题解的理论和单纯形法具体的求关于线性规划问题
11、解的理论和单纯形法具体的求解过程可参见文献解过程可参见文献1.然后在实际应用中,特别是数学建模过程中,然后在实际应用中,特别是数学建模过程中,遇到线性规划问题的求解,我们一般都是利用现遇到线性规划问题的求解,我们一般都是利用现有的软件进行求解,此时通常并不要求线性规划有的软件进行求解,此时通常并不要求线性规划问题是标准形式问题是标准形式.比较常用的求解线性规划模型比较常用的求解线性规划模型的软件包有的软件包有LINGO和和LINDO.运输问题运输问题例例2.2.设要从甲地调出物资设要从甲地调出物资2000吨,从乙地调出物吨,从乙地调出物 资资1100吨,分别供给吨,分别供给A地地1700吨、吨
12、、B地地1100吨、吨、C假定运费与运量成正比假定运费与运量成正比.在这种情况下,采用不在这种情况下,采用不地地200吨、吨、D地地100吨吨.已知每吨运费如表已知每吨运费如表1.1所示所示.同的调拨计划,运费就可能不一样同的调拨计划,运费就可能不一样.现在问:怎现在问:怎样才能找出一个运费最省的调拨计划?样才能找出一个运费最省的调拨计划?1572521甲甲15375151乙乙DCBA表表 1.1销销地地运运费费产产地地乙乙11x12x13x14x21x22x23x24x2000411 jix1100412 jix1700211 iix1100212 iix200213 iix100214 i
13、ix甲甲DCBA2423222114131211153751511572521minxxxxxxxxf )4,3,2,1;2,1(0 jixij解解1112131421222324min212571551513715fxxxxxxxx s.t.11121314212223241121122213231424.20001100170011002001000,1,2;1,2,3,4ijs t xxxxxxxxxxxxxxxxxij 一般的运输问题可以表述如下:一般的运输问题可以表述如下:数学模型:数学模型:njmixnjbxmiaxtsxczijmijijnjiijminjijij,2,1;,2,
14、1,0,2,1,2,1,.min1111 若其中各产地的总产量等于各销地的总销量,若其中各产地的总产量等于各销地的总销量,即即 类似与将一般的线性规划问题转化为其标准类似与将一般的线性规划问题转化为其标准 nijmiiba11否则,称为不平衡的运输问题,包括:否则,称为不平衡的运输问题,包括:,则称该问题为平衡的运输问题,则称该问题为平衡的运输问题.总产量总产量总销量和总产量总销量和总产量总销量总销量.形式,我们总可以通过引入假想的销地或产地,形式,我们总可以通过引入假想的销地或产地,将不平衡的运输问题转化为平衡的运输问题将不平衡的运输问题转化为平衡的运输问题.从从而,我们的重点就是解决平衡运
15、输问题的求解而,我们的重点就是解决平衡运输问题的求解.显然,运输问题是一个标准的线性规划问题,显然,运输问题是一个标准的线性规划问题,因而当然可以运用单纯形方法求解因而当然可以运用单纯形方法求解.但由于平衡的但由于平衡的运输问题的特殊性质,它还可以用其它的一些特殊运输问题的特殊性质,它还可以用其它的一些特殊方法求解,其中最常用的就是表上作业法,该方法方法求解,其中最常用的就是表上作业法,该方法将单纯形法与平衡的运输问题的特殊性质结合起来,将单纯形法与平衡的运输问题的特殊性质结合起来,很方便地实行了运输问题的求解很方便地实行了运输问题的求解.关于运输问题及关于运输问题及其解法的进一步介绍参加文献
展开阅读全文