数学规划数学建模与大学生数学建模竞赛课件.ppt

《数学规划数学建模与大学生数学建模竞赛课件.ppt》由会员分享，可在线阅读，更多相关《数学规划数学建模与大学生数学建模竞赛课件.ppt（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章 建立数学模型1.1从现实对象到数学模型1.2数学建模的重要意义1.3数学建模示例1.4数学建模的方法和步骤1.5数学模型的特点和分类1.6怎样学习数学建模玩具、照片、飞机、火箭模型实物模型水箱中的舰艇、风洞中的飞机物理模型地图、电路图、分子结构图 符号模型模型是为了一定目的，对客观事物的一部分进行简缩、抽象、提炼出来的原型的替代物模型集中反映了原型中人们需要的那一部分特征1.1 从现实对象到数学模型我们常见的模型你碰到过的数学模型“航行问题”用 x 表示船速，y 表示水速，列出方程：答：船速每小时20千米/小时.甲乙两地相距750千米，船从甲到乙顺水航行需30小时，从乙到甲逆水航行需5

2、0小时，问船的速度是多少?x=20y=5求解航行问题建立数学模型的基本步骤作出简化假设（船速、水速为常数）；用符号表示有关量（x,y表示船速和水速）；用物理定律（匀速运动的距离等于速度乘以时间）列出数学式子（二元一次方程）；求解得到数学解答（x=20,y=5）；回答原问题（船速每小时20千米/小时）。数学模型(MathematicalModel)和数学建模（MathematicalModeling)对于一个现实对象，为了一个特定目的，根据其内在规律，作出必要的简化假设，运用适当的数学工具，得到的一个数学结构。建立数学模型的全过程（包括表述、求解、解释、检验等）数学模型数学建模1.2 数学建模的

3、重要意义电子计算机的出现及飞速发展；数学以空前的广度和深度向一切领域渗透。数学建模作为用数学方法解决实际问题的第一步，越来越受到人们的重视。在一般工程技术领域数学建模仍然大有用武之地；在高新技术领域数学建模几乎是必不可少的工具；数学进入一些新领域，为数学建模开辟了许多处女地。数学建模的具体应用分析与设计预报与决策控制与优化 规划与管理数学建模 计算机技术知识经济如虎添翼1.3 数学建模示例1.3.1 椅子能在不平的地面上放稳吗问题分析模型假设通常三只脚着地 放稳四只脚着地四条腿一样长，椅脚与地面点接触，四脚连线呈正方形;地面高度连续变化，可视为数学上的连续曲面;地面相对平坦，使椅子在任意位置至

4、少三只脚同时着地。模型构成用数学语言把椅子位置和四只脚着地的关系表示出来椅子位置 利用正方形(椅脚连线)的对称性xBADCODCBA用(对角线与x轴的夹角)表示椅子位置四只脚着地距离是的函数四个距离(四只脚)A,C两脚与地面距离之和f()B,D两脚与地面距离之和g()两个距离椅脚与地面距离为零正方形ABCD绕O点旋转正方形对称性用数学语言把椅子位置和四只脚着地的关系表示出来f(),g()是连续函数对任意,f(),g()至少一个为0数学问题已知：f(),g()是连续函数;对任意，f()g()=0;且g(0)=0，f(0)0.证明：存在0，使f(0)=g(0)=0.模型构成地面为连续曲面椅子在任意

5、位置至少三只脚着地模型求解给出一种简单、粗糙的证明方法将椅子旋转900，对角线AC和BD互换。由g(0)=0，f(0)0，知f(/2)=0,g(/2)0.令h()=f()g(),则h(0)0和h(/2)0.由f,g的连续性知h为连续函数,据连续函数的基本性质,必存在0,使h(0)=0,即f(0)=g(0).因为f()g()=0,所以f(0)=g(0)=0.评注和思考 建模的关键假设条件的本质与非本质 考察四脚呈长方形的椅子和f(),g()的确定1.3.2 商人们怎样安全过河问题(智力游戏)3名商人3名随从随从们密约,在河的任一岸,一旦随从的人数比商人多,就杀人越货.但是乘船渡河的方案由商人决定

6、.商人们怎样才能安全过河?问题分析多步决策过程决策每一步(此岸到彼岸或彼岸到此岸)船上的人员要求在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河.河小船(至多2人)模型构成xk第k次渡河前此岸的商人数yk第k次渡河前此岸的随从数xk,yk=0,1,2,3;k=1,2,sk=(xk,yk)过程的状态S=(x,y)x=0,y=0,1,2,3;x=3,y=0,1,2,3;x=y=1,2S允许状态集合uk第k次渡船上的商人数vk第k次渡船上的随从数dk=(uk,vk)决策D=(u,v)u+v=1,2允许决策集合uk,vk=0,1,2;k=1,2,sk+1=sk dk+(-1)k状态转移

7、律求dkD(k=1,2,n),使skS,并按转移律由s1=(3,3)到达sn+1=(0,0).多步决策问题模型求解xy33 22110穷举法编程上机图解法状态s=(x,y)16个格点10个点允许决策移动1或2格;k奇,左下移;k偶,右上移.s1sn+1d1,，d11给出安全渡河方案d1d11允许状态S=(x,y)x=0,y=0,1,2,3;x=3,y=0,1,2,3;x=y=1,2 数学建模的基本方法机理分析测试分析根据对客观事物特性的认识，找出反映内部机理的数量规律将对象看作“黑箱”,通过对量测数据的统计分析，找出与数据拟合最好的模型机理分析没有统一的方法，主要通过实例研究(CaseStud

8、ies)来学习。以下建模主要指机理分析。二者结合用机理分析建立模型结构,用测试分析确定模型参数1.4 数学建模的方法和步骤 数学建模的一般步骤模型准备模型假设 模型构成模型求解 模型分析模型检验模型应用模型准备了解实际背景 明确建模目的搜集有关信息 掌握对象特征形成一个比较清晰的问题模型假设针对问题特点和建模目的作出合理的、简化的假设在合理与简化之间作出折中模型构成用数学的语言、符号描述问题发挥想像力 使用类比法尽量采用简单的数学工具 数学建模的一般步骤模型求解各种数学方法、软件和计算机技术如结果的误差分析、统计分析、模型对数据的稳定性分析模型分析模型检验与实际现象、数据比较，检验模型的合理性

9、、适用性模型应用 数学建模的一般步骤数学建模的全过程现实对象的信息 数学模型现实对象的解答 数学模型的解答表述求解解释验证(归纳)(演绎)表述求解解释验证根据建模目的和信息将实际问题“翻译”成数学问题选择适当的数学方法求得数学模型的解答将数学语言表述的解答“翻译”回实际对象用现实对象的信息检验得到的解答实践现实世界数学世界理论 实践1.5 数学模型的特点和分类模型的逼真性和可行性模型的渐进性模型的强健性模型的可转移性模型的非预制性模型的条理性模型的技艺性模型的局限性数学模型的特点数学模型的分类应用领域人口、交通、经济、生态数学方法初等数学、微分方程、规划、统计表现特性描述、优化、预报、决策建模

10、目的了解程度 白箱 灰箱 黑箱确定和随机静态和动态线性和非线性离散和连续 1.美国大学生数学建模竞赛的历史 2.我国大学生参加美国大学生数学建模竞赛的历史 3.我国大学生数学建模竞赛的历史 4.我省(我校)参加全国大学生数学建模竞赛和美国大学生数学建模竞赛的情况 1.6关于大学生数学建模竞赛2.1奶制品的生产与销售2.2 自来水输送与货机装运2.3 接力队选拔和选课策略第二章 数学规划模型 y数学规划模型 实际问题中的优化模型x决策变量 f(x)目标函数gi(x)0约束条件多元函数条件极值决策变量个数n和约束条件个数m较大最优解在可行域的边界上取得数学规划线性规划非线性规划整数规划重点在模型的

11、建立和结果的分析企业生产计划2.1奶制品的生产与销售 空间层次工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划。时间层次若短时间内外部需求和内部资源等不随时间变化，可制订单阶段生产计划，否则应制订多阶段生产计划。本节课题例1加工奶制品的生产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶 时间480小时 至多加工100公斤A1制订生产计划，使每天获利最大 35元可买到1桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人

12、，付出的工资最多是每小时几元?A1的获利增加到30元/公斤，应否改变生产计划？每天：1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产A1 x2桶牛奶生产A2获利243x1 获利164 x2原料供应 劳动时间 加工能力 决策变量 目标函数 每天获利约束条件非负约束 线性规划模型(LP)时间480小时 至多加工100公斤A1 50桶牛奶每天模型分析与假设 比例性可加性连续性xi对目标函数的“贡献”与xi取值成正比xi对约束条件的“贡献”与xi取值成正比xi对目标函数的“贡献”与xj取值无关xi对约束条件的“贡献”与xj取值无关xi取值连续A1

13、,A2每公斤的获利是与各自产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数A1,A2每公斤的获利是与相互产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数加工A1,A2的牛奶桶数是实数线性规划模型模型求解 图解法 x1x20ABCDl1l2l3l4l5约束条件目标函数 Z=0Z=2400Z=3600z=c(常数)等值线c在B(20,30)点得到最优解目标函数和约束条件是线性函数可行域为直线段围成的凸多边形目标函数的等值线为直线最优解一定在凸多边形的某个顶点取得。模型求解 软件实现 LINDO6.1max72x1+64x2st2）x1+x2503）1

14、2x1+8x24804）3x1100endOBJECTIVEFUNCTIONV ALUE1)3360.000V ARIABLEV ALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产A1,30桶生产A2，利润3360元。结果解释 OBJECTIVEFUNCTIONV ALU

15、E1)3360.000V ARIABLEV ALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2原料无剩余时间无剩余加工能力剩余40max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三种资源“资源”剩余为零的约束为紧约束（有效约束）结果解释 OBJECTIVEFUNCTIONV ALUE1)3360.00

16、0V ARIABLEV ALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2最优解下“资源”增加1单位时“效益”的增量原料增加1单位,利润增长48时间增加1单位,利润增长2加工能力增长不影响利润影子价格35元可买到1桶牛奶，要买吗？3548,应该买！聘用临时工人付出的工资最多每小时几元？2元！RANGESINWHICHTHEBASISISUNCHA

17、NGED:OBJCOEFFICIENTRANGESV ARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最优解不变时目标函数系数允许变

18、化范围DORANGE(SENSITIVITY)ANALYSIS?Yesx1系数范围(64,96)x2系数范围(48,72)A1获利增加到30元/千克，应否改变生产计划x1系数由243=72增加为303=90，在允许范围内不变！(约束条件不变)结果解释 RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESV ARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSI

19、DERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子价格有意义时约束右端的允许变化范围原料最多增加10时间最多增加5335元可买到1桶牛奶，每天最多买多少？最多买10桶!(目标函数不变)2.2 自来水输送与货机装运生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大；运输问题各种类型的货物装箱，由于受体积、重量等限制，如何搭配装载，使获利

20、最高，或装箱数量最少。其他费用:450元/千吨 应如何分配水库供水量，公司才能获利最多？若水库供水量都提高一倍，公司利润可增加到多少？元/千吨甲 乙 丙 丁A 160 130 220 170B 140 130 190 150C 190 200 230/引水管理费例1 自来水输送收入：900元/千吨支出A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：10；40水库供水量(千吨)小区基本用水量(千吨)小区额外用水量(千吨)（以天计）总供水量：160确定送水方案使利润最大问题分析A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：10；40总需求量：120+1

21、80=300总收入900160=144,000(元)收入：900元/千吨其他费用:450元/千吨支出 引水管理费其他支出450160=72,000(元)使引水管理费最小供应限制约束条件需求限制线性规划模型(LP)目标函数 水库i 向j 区的日供水量为 xij（x34=0）决策变量 模型建立 确定3个水库向4个小区的供水量模型求解 OBJECTIVEFUNCTIONV ALUE1)24400.00V ARIABLEV ALUEREDUCEDCOSTX110.00000030.000000X1250.0000000.000000X130.00000050.000000X140.00000020.0

22、00000X210.00000010.000000X2250.0000000.000000X230.00000020.000000X2410.0000000.000000X3140.0000000.000000X320.00000010.000000X3310.0000000.000000利润=总收入-其它费用-引 水 管 理 费=144000-72000-24400=47600（元）A(50)B(60)C(50)甲(30;50)乙(70;70)丙(10;20)丁(10;40)5050401010引水管理费 24400(元)目标函数 总供水量(320)总需求量(300)每个水库最大供水量都提高

23、一倍利润=收入(900)其它费用(450)引水管理费利润(元/千吨)甲 乙 丙 丁A 290 320 230 280B 310 320 260 300C 260 250 220/供应限制B,C类似处理问题讨论 确定送水方案使利润最大需求约束可以不变求解OBJECTIVEFUNCTIONV ALUE1)88700.00V ARIABLEV ALUEREDUCEDCOSTX110.00000020.000000X12100.0000000.000000X130.00000040.000000X140.00000020.000000X2130.0000000.000000X2240.0000000.

24、000000X230.00000010.000000X2450.0000000.000000X3150.0000000.000000X320.00000020.000000X3330.0000000.000000这类问题一般称为“运输问题”(TransportationProblem)总利润 88700（元）A(100)B(120)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)4010050305030如何装运，使本次飞行获利最大？三个货舱最大载重(吨),最大容积(米3)例2货机装运重量（吨）空间(米3/吨）利润（元/吨）货物1 18 480 3100货物2 15

25、 650 3800货物3 23 580 3500货物4 12 390 2850三个货舱中实际载重必须与其最大载重成比例前仓：10；6800中仓：16；8700后仓：8；5300飞机平衡决策变量 xij-第i 种货物装入第j 个货舱的重量(吨）i=1,2,3,4,j=1,2,3(分别代表前、中、后仓)模型假设 每种货物可以分割到任意小；货机装运每种货物可以在一个或多个货舱中任意分布；多种货物可以混装，并保证不留空隙；模型建立 货舱容积 目标函数(利润)约束条件货机装运模型建立 货舱重量 10；680016；87008；5300 xij-第i 种货物装入第j 个货舱的重量约束条件平衡要求 货物供应

26、 货机装运模型建立 10；680016；87008；5300 xij-第i 种货物装入第j 个货舱的重量OBJECTIVEFUNCTIONV ALUE1)121515.8V ARIABLEV ALUEREDUCEDCOSTX110.000000400.000000X120.00000057.894737X130.000000400.000000X2110.0000000.000000X220.000000239.473679X235.0000000.000000X310.0000000.000000X3212.9473690.000000X333.0000000.000000X410.0000

27、00650.000000X423.0526320.000000X430.000000650.000000货物2：前仓10,后仓5；货物3:中仓13,后仓3；货物4:中仓3。货机装运模型求解 最大利润约121516元货物供应点货舱需求点平衡要求运输问题运输问题的扩展分派问题2.3 接力队选拔和选课策略若干项任务分给一些候选人来完成，每人的专长不同，完成每项任务取得的效益或需要的资源就不同，如何分派任务使获得的总效益最大，或付出的总资源最少。若干种策略供选择，不同的策略得到的收益或付出的成本不同，各个策略之间有相互制约关系，如何在满足一定条件下作出决择，使得收益最大或成本最小。丁的蛙泳成绩退步到1

28、15”2；戊的自由泳成绩进步到57”5,组成接力队的方案是否应该调整？如何选拔队员组成4100米混合泳接力队?例1混合泳接力队的选拔甲 乙 丙 丁 戊蝶泳106”8 57”2 118”110”107”4仰泳115”6 106”107”8 114”2 111”蛙泳127”106”4 124”6 109”6 123”8自由泳58”6 53”59”4 57”2 102”45名候选人的百米成绩穷举法：组成接力队的方案共有5!=120种。目标函数若选择队员i参加泳姿j 的比赛，记xij=1,否则记xij=0 0-1规划模型 cij(秒)队员i 第j 种泳姿的百米成绩约束条件每人最多入选泳姿之一ciji=

29、1 i=2 i=3 i=4 i=5j=1 66.8 57.2 78 70 67.4j=2 75.6 66 67.8 74.2 71j=3 87 66.4 84.6 69.6 83.8j=4 58.6 53 59.4 57.2 62.4每种泳姿有且只有1人 模型求解 最优解：x14=x21=x32=x43=1,其它变量为0;成 绩 为 253.2(秒)=413”2MIN66.8x11+75.6x12+87x13+58.6x14+67.4x51+71x52+83.8x53+62.4x54SUBJECTTOx11+x12+x13+x14=1x41+x42+x43+x44=1x11+x21+x31+x

30、41+x51=1x14+x24+x34+x44+x54=1ENDINT20输入LINDO求解 甲 乙 丙 丁 戊蝶泳106”8 57”2 118”110”107”4仰泳115”6 106”107”8 114”2 111”蛙泳127”106”4 124”6 109”6 123”8自由泳58”6 53”59”4 57”2 102”4甲自由泳、乙蝶泳、丙仰泳、丁蛙泳.丁蛙泳c43=69.675.2，戊自由泳c54=62.457.5,方案是否调整？敏感性分析？乙蝶泳、丙仰泳、丁蛙泳、戊自由泳IP规划一般没有与LP规划相类似的理论，LINDO输出的敏感性分析结果通常是没有意义的。最优解：x21=x32=

31、x43=x51=1,成绩为417”7c43,c54 的新数据重新输入模型，用LINDO求解 指派(Assignment)问题：每项任务有且只有一人承担，每人只能承担一项，效益不同，怎样分派使总效益最大.讨论甲自由泳、乙蝶泳、丙仰泳、丁蛙泳.原方案为了选修课程门数最少，应学习哪些课程？例2选课策略要求至少选两门数学课、三门运筹学课和两门计算机课 课号 课名 学分 所属类别 先修课要求1微积分5数学2线性代数4数学3最优化方法4数学；运筹学 微积分；线性代数4数据结构3数学；计算机 计算机编程5应用统计4数学；运筹学 微积分；线性代数6计算机模拟3计算机；运筹学 计算机编程7计算机编程2计算机8预

32、测理论2运筹学 应用统计9数学实验3运筹学；计算机 微积分；线性代数选修课程最少，且学分尽量多，应学习哪些课程？0-1规划模型 决策变量 目标函数 xi=1选修课号i 的课程（xi=0不选）选修课程总数最少约束条件最少2门数学课，3门运筹学课，2门计算机课。课号 课名 所属类别1微积分 数学2线性代数 数学3最优化方法 数学；运筹学4数据结构 数学；计算机5应用统计 数学；运筹学6计算机模拟 计算机；运筹学7计算机编程 计算机8预测理论 运筹学9数学实验 运筹学；计算机先修课程要求最优解：x1=x2=x3=x6=x7=x9=1,其它为0；6门课程，总学分210-1规划模型 约束条件x3=1必有

33、x1=x2=1模型求解（LINDO）课号 课名 先修课要求1微积分2线性代数3最优化方法 微积分；线性代数4数据结构 计算机编程5应用统计 微积分；线性代数6计算机模拟 计算机编程7计算机编程8预测理论 应用统计9数学实验 微积分；线性代数学分最多多目标优化的处理方法：化成单目标优化。两目标(多目标)规划 讨论：选修课程最少，学分尽量多，应学习哪些课程？课程最少以学分最多为目标，不管课程多少。以课程最少为目标，不管学分多少。最优解如上，6门课程，总学分21。最优解显然是选修所有9门课程。多目标规划 在课程最少的前提下以学分最多为目标。最优解：x1=x2=x3=x5=x7=x9=1,其它为0；总

34、学分由21增至22。注意：最优解不唯一！课号 课名 学分1微积分52线性代数43最优化方法44数据结构35应用统计46计算机模拟37计算机编程28预测理论29数学实验3 LINDO无法告诉优化问题的解是否唯一。可将x9=1易为x6=1增加约束，以学分最多为目标求解。多目标规划 对学分数和课程数加权形成一个目标，如三七开。最优解：x1=x2=x3=x4=x5=x6=x7=x9=1，其它为0；总学分28。课号 课名 学分1微积分52线性代数43最优化方法44数据结构35应用统计46计算机模拟37计算机编程28预测理论29数学实验3 讨论与思考最优解与1=0，2=1的结果相同学分最多多目标规划 最优解与1=1，2=0的结果相同课程最少