数学建模与大学生数学建模竞赛省名师优质课赛课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢您,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢您,数学建模与大学生数学建模竞赛,第1页,一、数学建模,数学建模是一门新兴学科，20世纪70年代初诞生于英、美等当代工业国家。因为新技术尤其是计算机技术飞速发展，大量实际问题需要用计算机来处理，而计算机与实际问题之间需要数学模型来沟通，所以这门学科在短短几十年时间快速辐射至全球大部分国家和地域。80年代初，我国高等院校也陆续开设了数学建模课程，伴随数学建模教学活动（包含数学建模课程、数学建模竞赛和数学建模试验课程等）开展，这门学科越来越得到重视，也深受广大师生喜爱。,第2页,什么是数学模型呢？,数学模型（Mathematical Model）是指对于现实世界某一特定对象，为了某个特定目标，做出一些必要简化和假设，利用适当数学工具得到一个数学结构。数学结构是指数学符号、数学关系式、数学命题、图形图表等，这些基于数学思想与方法数学问题。总之，数学模型是对实际问题一个抽象，基于数学理论和方法，用数学符号、数学关系式、数学命题、图形图表等来刻画客观事物本质属性与其内在联络。,第3页,什么是数学建模呢？,数学建模（Mathematical Modeling）就是建立数学模型，建立数学模型过程就是数学建模过程。数学建模是一个数学思索方法，是利用数学语言和方法，经过抽象、简化建立能近似刻画并处理实际问题一个强有力数学伎俩。,第4页,二、数学建模采取主要方法,（一）、机理分析法：依据对客观事物特征认识从基本物理定律以及系统结构数据来推导出模型。,1、百分比分析法：建立变量之间函数关系最基本最惯用方法。,2、代数方法：求解离散问题（离散数据、符号、图形）主要方法。,3、逻辑方法：是数学理论研究主要方法，对社会学和经济学等领域实际问题，在决议，对策等学科中得到广泛应用。,4、常微分方程：处理两个变量之间改变规律，关键是建立“瞬时改变率”表示式。,5、偏微分方程：处理因变量与两个以上自变量之间改变规律。,第5页,（二）、数据分析法：经过对量测数据统计分析，找出与数据拟合最好模型,1、回归分析法：用于对函数f（x）一组观察值（xi,fi）i=1,2,n，确定函数表示式，因为处理是静态独立数据，故称为数理统计方法。,2、时序分析法：处理是动态相关数据，又称为过程统计方法。,二、数学建模采取主要方法,第6页,（三）、仿真和其它方法,1、计算机仿真（模拟）：实质上是统计预计方法，等效于抽样试验。离散系统仿真，有一组状态变量。连续系统仿真，有解析表示式或系统结构图。,2、因子试验法：在系统上作局部试验，再依据试验结果进行不停分析修改，求得所需模型结构。,3、人工现实法：基于对系统过去行为了解和对未来希望到达目标，并考虑到系统相关原因可能改变，人为地组成一个系统。,二、数学建模采取主要方法,第7页,三、大学生数学建模竞赛,1985年在美国出现了一个叫做MCM一年一度大学生数学模型竞赛（Mathematical Contest in Modeling,缩写MCM）。我国自1989年首次参加这一竞赛，历届均取得优异成绩。经过多年参加美国赛表明，中国大学生在数学建模方面是有竞争力和创新联想能力。,第8页,为了在国内推广这一活动，1992年由中国工业与应用数学学会（CSIAM）组织了第一次中国大学生数学建模竞赛（简称CMCM），1994年起由教育部高教司和CSIAM共同举行，每年一次（9月），现在已经成为全国高校规模最大课外科技活动。,三、大学生数学建模竞赛,第9页,竞赛题目普通由工程技术、管理科学中实际问题简化而成，没有事先设定标准答案，但留有充分余地供参赛者发挥其聪明才智和创造精神。竞赛形式：三名大学生组成一队，能够自由地搜集资料、调查研究，使用计算机、互联网和任何软件，在三天时间内分工合作完成一篇论文。评奖标准：假设合理性、建模创造性、结果正确性、文字表述清楚程度。每年出两道题，大学：A、B题，大专：C、D题，任选一题。A、C为连续型题目B、D为离散型题目。优异论文登在工程数学学报（年后），数学实践与认识（年前）明年第1期上。,三、大学生数学建模竞赛,第10页,数学模型竞赛与通常数学竞赛不一样之处于于它来自实际问题或有明确实际背景，它宗旨是培养大学生用数学方法处理实际问题意识和能力，培养创新意识、团体精神，勉励参加、提倡公平竞争，提升学生综合素质。整个比赛要完成一篇包含问题阐述分析，模型假设和建立，计算结果及讨论论文。经过训练和比赛，同学们不但用数学方法处理实际问题意识和能力有很大提升，而且在团结合作发挥集体力量攻关，以及撰写科技论文等方面将都会得到十分有益锻炼。,三、大学生数学建模竞赛,第11页,四、赛题题型结构形式组成部分,（一）、实际问题背景,、包括面宽，有社会，经济，管理，生活，环境，自然现象，工程技术，当代科学中出现新问题等。,、普通都有一个比较确切现实问题。,第12页,四、赛题题型结构形式组成部分,（二）、若干假设条件,1、只有过程、规则等定性假设，无详细定量数据；,2、给出若干实测或统计数据；,3、给出若干参数或图形；,4、蕴涵着一些机动、可发挥补充假设条件，或参赛者能够依据自己搜集或模拟产生数据。,第13页,四、赛题题型结构形式组成部分,（三）、要求回答问题，往往有几个问题（普通不是唯一答案）,1、比较确定性答案（基本答案）；,2、更细致或更高层次讨论结果（往往是讨论最优方案提法和结果）。,第14页,（一）、标题、摘要部分,1、题目：写出较确切题目（不能只写A题、B题）。,2、摘要：200-300字，包含模型主要特点、建模方法和主要结果。,3、内容较多时最好有个目录。,五、,竞赛答卷（三大部分）,第15页,（二）、中心部分,1、问题提出，问题分析。,2、模型建立：,补充假设条件，明确概念，引进参数；,模型形式（可有多个形式模型）；,模型求解；,模型性质；,3、计算方法设计和计算机实现。,4、结果分析与检验。,5、讨论：模型优缺点，改进方向，推广新思想。,6、参考文件：注意格式。,五、,竞赛答卷（三大部分）,第16页,（三）、附录部分,1、计算程序、框图。,2、各种求解演算过程，计算中间结果。,3、各种图形、表格。,五、,竞赛答卷（三大部分）,第17页,中国大学生数学建模竞赛题目聚集,（注：A、B是大学组赛题，C、D题是大专组赛题，任选其一。）,第18页,1992A、施肥效果分析；B、试验数据分析。,1993A、非线性交调频率设计；B、足球队排名次。,1994A、逢山开路；B、锁具装箱。,1995A、一个飞行管理问题；B、天车与冶炼炉作业调度。,1996A、最优打鱼策略；B、节水洗衣机。,1997A、零件参数设计；B、截断切割。,1998A、投资收益与风险；B、灾情巡视路线。,1999A、自动化车床管理；B、钻井布局；C、煤矸石堆积；D、钻井布局（注:比B稍易）,第19页,ADNA序列分类；B、钢管订购和运输；C、飞越北极；D、空洞探测。,A、血管三维重建；B、公交车调度；C、基金使用计划；D、公交车调度。,A、车灯线光源优化设计；B、彩票中数学；C、车灯线光源计算；D、赛程安排。,A、SARS传输；B、露天矿生产车辆安排；C、SARS传输；D、抢渡长江。,A、奥运会暂时超市网点设计；B、电力市场输电阻塞管理；C、饮酒驾车；D、公务员招聘。,A、长江水质评价和预测；B、DVD在线租赁；C、雨量预报方法评价；D、DVD在线租赁。,第20页,线性规划（概论）,线性规划（Linear Programming)创始人：,1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）,1963年Dantzing写成“Linear Programming and Extension”,1979年苏联Khachian提出“椭球法”,1984年印度Karmarkar提出“投影梯度法”,线性规划是研究线性不等式组理论，或者说是研究（高维空间中）凸多面体理论，是线性代数应用和发展。,第21页,1-1 线性规划基本概念,生产计划问题,怎样合理使用有限人力，物力和资金，使得收到最好经济效益。,怎样合理使用有限人力，物力和资金，以到达最经济方式，完成生产计划要求。,第22页,例1.1 生产计划问题（资源利用问题）,胜利家俱厂生产桌子和椅子两种家俱。桌子售价50元/个，椅子销售价格30元/个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂怎样组织生产才能使每个月销售收入最大？,第23页,解：,将一个实际问题转化为线性规划模型有以下几个步骤：,1,确定决议变量,：x1=生产桌子数量,x2=生产椅子数量,2,确定目标函数,：,家俱厂目标是销售收入最大,max z=50 x1+30 x2,3,确定约束条件,：,4x1+3x2,120（木工工时限制）,2x1+x2,50,（油漆工工时限制）,4,变量取值限制,：,普通情况，决议变量只取正值（非负值）,x1,0,x2,0,第24页,1-2 线性规划问题数学模型,例1.2 营养配餐问题,假定一个成年人天天需要从食物中取得3000千卡热量、55克蛋白质和800毫克钙。假如市场上只有四种食品可供选择，它们每千克所含热量和营养成份和市场价格见下表。问怎样选择才能在满足营养前提下使购置食品费用最小？,第25页,各种食物营养成份表,第26页,解：,设,xj,为第j种食品天天购入量，则配餐问题线性规划模型为：,min S=14x1+6x2+3x3+2x4,s.t.1000 x1+800 x2+900 x3+200 x4,3000,50 x1+60 x2+20 x3+10 x4,55,400 x1+200 x2+300 x3+500 x4,800,x1，x2，x3，x4,0,第27页,其它经典问题：,合理下料问题,运输问题,生产组织与计划问题,投资证券组合问题,分配问题,生产工艺优化问题,第28页,用于成功决议实例：,美国航空企业关于哪架飞机用于哪一航班和哪些机组人员被安排于哪架飞机决议,美国国防部关于怎样从现有一些基地向海湾运输海湾战争所需要人员和物资决议,Chessie,道路系统关于购置和修理价值40亿美圆货运汽车决议,第29页,用于成功决议实例：,魁北克水利部门关于用哪几个水库来满足天天电力需求决议,农场信贷系统联邦土地银行关于怎样支付到期债券和应出售多少新债券以获取资金（每年共计60亿美圆）来维持发展决议,北美长途运输企业关于每七天怎样调度数千辆货车决议,埃克森炼油厂关于调整冶炼能力去适应关于无铅燃料生产法律更改决议,第30页,线性规划问题普通形式：,Max(Min)S=c,1,x,1,+c,2,x,2,+.+c,n,x,n,s.t.a,11,x,1,+a,12,x,2,+.+a,1n,x,n,(=,)b,1,a,21,x,1,+a,22,x,2,+.+a,2n,x,n,(=,)b,2,.,a,m1,x,1,+a,m2,x,2,+.+a,mn,x,n,(=,)b,m,x,1,x,2,.x,n,0,第31页,线性规划问题隐含假定：,百分比性假定,：决议变量改变引发目标函数改变量和决议变量改变量成百分比，一样，每个决议变量改变引发约束方程左端值改变量和该变量改变量成百分比。,可加性假定,：每个决议变量对目标函数和约束方程影响是独立于其它变量，目标函数值是每个决议变量对目标函数贡献总和。,第32页,线性规划问题隐含假定：,连续性假定,：线性规划问题中决议变量应取连续值。,确定性假定,：线性规划问题中全部参数都是确定参数。线性规划问题不包含随机原因。,第33页,线性规划问题隐含假定：,百分比性假定,可加性假定,连续性假定,确定性假定,第34页,线性规划问题标准形式(1)：,Max S=c,1,x,1,+c,2,x,2,+c,n,x,n,s.t.a,11,x,1,+a,12,x,2,+.+a,1n,x,n,=b,1,a,21,x,1,+a,22,x,2,+.+a,2n,x,n,=b,2,.,a,m1,x,1,+a,m2,x,2,+.+a,mn,x,n,=b,m,x,1,x,2,.x,n,0,其中：b,i,0(i=1,2,.m),第35页,线性规划问题标准形式(2)：,n,Max S =,c,j,x,j,j=1,n,s.t.,a,ij,x,j,=b,i,(i=1,2,.n),j=1,x,j,0(j=1,2,.m),第36页,线性规划标准型矩阵形式(3)：,Max,S,=,CX,s.t.,AX=b,X,0,第37页,a,11,a,12,.a,1n,b,1,A=,a,21,a,22,.a,2n,b,=,b,2,.,a,m1,a,m2,.a,mn,b,n,c,1,x,1,0,c,2,x,2,0,C=X=0=,.,c,n,x,n,0,第38页,怎样将普通问题化为标准型：,若目标函数是求最小值 Min S=CX,令 S=-S,则 Max S=-CX,若约束条件是不等式,若约束条件是,“,”不等式,n,a,ij,x,j,+y,i,=b,i,j=1,y,i,0,是非负,松驰变量,第39页,怎样将普通问题化为标准型：,若约束条件是“,”不等式,n,a,ij,x,j,-z,i,=b,i,j=1,z,i,0,是非负松驰变量,第40页,怎样将普通问题化为标准型：,若约束条件右面某一常数项 b,i,=0,令x,j,=,x,j,-x,j,”（可正可负）,任何形式线性规划总能够化成标准型,第41页,例1.3 将以下问题化成标准型,:,Min S =-x,1,+2x,2,-3x,3,s.t.x,1,+x,2,+x,3,7,x,1,-x,2,+x,3,2,-3x,1,+x,2,+2x,3,=5,x,1,x,2,0 x,3,无非负限制,第42页,Max S =x,1,-2x,2,+3x,3,-3x,3,”,s.t.x,1,+x,2,+x,3,-x,3,”+x,4,=7,x,1,-x,2,+x,3,-x,3,”-x,5,2,-3x,1,+x,2,+2x,3,-2x,3,”,=5,x,1,x,2,x,3,x,3,”,x,4,x,5,0,第43页,1-3 线性规划问题,解概念,第44页,（二维）线性规划问题图解法：,（1）满足约束条件变量值，称为可行解。,（2）使目标函数取得最优值可行解，称为最优解。,例1.1数学模型,max S=50 x,1,+30 x,2,s.t.4x,1,+3x,2,120,2x,1,+x,2,50,x,1,x,2,0,第45页,x,2,50,40,30,20,10,10,20,30,40,x,1,4x,1,+3x,2,120,由 4x,1,+3x,2,120,x,1,0 x,2,0,围成区域,第46页,x,2,50,40,30,20,10,10,20,30,40,x,1,2x,1,+x,2,50,由 2x,1,+x,2,50,x,1,0 x,2,0,围成区域,第47页,x,2,50,40,30,20,10,10,20,30,40,x,1,2x,1,+x,2,50,4x,1,+3x,2,120,可行域,同时满足：,2x,1,+x,2,50,4x,1,+3x,2,120,x,1,0 x,2,0,区域,可行域,第48页,x,2,50,40,30,20,10,10,20,30,40,x,1,可行域,O（0，0）,Q,1,（25，0）,Q,2,（15，20）,Q,3,（0，40）,可行域是由约束条件围成区域，该区域内每一点都是可行解，它全体组成问题解集合。,该问题可行域是由O，Q,1,，Q,2,，Q,3,作为顶点,凸多边形,第49页,x,2,50,40,30,20,10,10,20,30,40,x,1,可行域,目标函数是以S作为参数一组平行线,x,2,=,S/30-（5/3）x,1,第50页,x,2,50,40,30,20,10,10,20,30,40,x,1,可行域,当S值不停增加时，该直线,x,2,=,S/30-（5/3）x,1,沿着其法线方向向右上方移动。,第51页,x,2,50,40,30,20,10,10,20,30,40,x,1,可行域,当该直线移到Q,2,点时，S（目标函数）值到达最大：,Max S=50*15+30*20=1350,此时最优解=（15，20）,Q,2,（15，20）,第52页,二个主要结论：,满足约束条件可行域普通都组成凸多边形。这一事实能够推广到更多变量场所。,最优解必定能在凸多边形某一个顶点上取得，这一事实也能够推广到更多变量场所。,第53页,解讨论：,最优解是唯一解,；,无穷多组最优解：,例1.1目标函数由,max S=50 x,1,+30 x,2,变成：max S=40 x,1,+30 x,2,s.t.4x,1,+3x,2,120,2x,1,+x,2,50,x,1,x,2,0,第54页,x,2,50,40,30,20,10,10,20,30,40,x,1,可行域,目标函数是同约束条件：4x,1,+3x,2,120平行直线,x,2,=,S/30-（4/3）x,1,第55页,x,2,50,40,30,20,10,10,20,30,40,x,1,可行域,当S值增加时，目标函数同约束条件：4x,1,+3x,2,120,重合，Q,1,与Q,2,之间都是最优解。,Q,1,（25，0）,Q,2,（15，20）,第56页,解讨论：,无界解：,例：max S=x,1,+x,2,s.t.-2x,1,+x,2,40,x,1,-x,2,20,x,1,x,2,0,第57页,x,2,50,40,30,20,10,10,20,30,40,x,1,该可行域无界，目标函数值可增加到无穷大，称这种情况为无界解或无最优解。,第58页,解讨论：,无可行解：,例：max S=2x,1,+3x,2,s.t.x,1,+2x,2,8,x,1,4,x,2,3,-2x,1,+x,2,4,x,1,x,2,0,该问题可行域为空集，即无可行解，也不存在最优解。,第59页,解情况：,有可行解,有唯一最优解,有没有穷最优解,无最优解,无可行解,第60页,1-2 实例分析1,年全国大学生数模竞赛B题,第61页,B 钢管订购和运输,由钢管厂订购钢管，经铁路、公路运输，铺设一条钢管管道,A,1,3,2,5,80,10,10,31,20,12,42,70,10,8810,70,62,70,30,20,20,30,450,104,301,750,606,194,205,201,680,480,300,220,210,420,500,600,306,195,202,720,690,520,170,690,462,160,320,160,110,290,1150,1100,1200,A,2,A,3,A,4,A,5,A,6,A,7,A,8,A,9,A,10,A,11,A,12,A,13,A,14,A,15,S,1,S,2,S,3,S,4,S,5,S,6,S,7,管道,铁路,公路,S1S7,钢管厂,火车站,450 里程（km）,（沿管道建有公路）,第62页,钢厂产量和销价（1单位钢管=1km管道钢管）,钢厂产量下限：500单位钢管,1单位钢管铁路运价,1000km以上每增加1至100km运价增加5万元,1单位钢管公路运价：0.1万元/km（不足整公里部分按整公里计）,第63页,（1）制订钢管订购和运输计划，使总费用最小.,（2）分析对购运计划和总费用影响：哪个钢厂钢管销价改变影响最大；哪个钢厂钢管产量上限改变影响最大？,A,1,3,2,5,80,10,10,31,20,12,42,70,10,88,10,70,62,70,30,20,20,30,450,104,301,750,606,194,205,201,680,480,300,220,210,420,500,600,306,195,202,720,690,520,170,690,462,160,320,160,110,290,1150,1100,1200,A,2,A,3,A,4,A,5,A,6,A,7,A,8,A,9,A,10,A,11,A,12,A,13,A,14,A,15,S,1,S,2,S,3,S,4,S,5,S,6,S,7,A,16,130,A,17,A,18,A,19,A,20,A,21,190,260,100,（3）讨论管道为树形图情形,第64页,问题1基本模型和解法,总费用最小优化问题,总费用：订购，运输（由各厂S,i,经铁路、公路至各点A,j,i=1,7;j=1,15铺设管道A,j,A,j+1,（j=1,14),由S,i,至A,j,最小购运费用路线及最小费用,c,ij,由S,i,至A,j,最优运量,x,ij,由A,j,向A,j,A,j-1,段铺设长度,z,j,及,向A,j,A,j+1,段铺设长度,y,j,最优购运计划,约束条件,钢厂产量约束：上限和下限（假如生产话）,运量约束：,x,ij,对,i,求和等于,z,j,加,y,j,；,y,j,与,z,j+1,之和等于A,j,A,j+1,段长度,l,j,第65页,基本模型,由A,j,向A,j,A,j-1,段铺设运量为 1+,z,j,=z,j,(,z,j,+1)/2,由A,j,向A,j,A,j+1,段铺设运量为 1+,y,j,=y,j,(,y,j,+1)/2,二次规划,第66页,求解步骤,1）求由S,i,至A,j,最小购运费用路线及最小费用,c,ij,难点：公路运费是里程线性函数，而铁路运费是里程分段阶跃函数，故总运费不具可加性。因而计算最短路惯用Dijkstra算法、Floyd算法失效。,A,1,70,10,88,10,70,62,70,30,20,20,30,300,220,210,420,500,170,690,462,160,320,160,110,290,A,10,A,11,A,12,A,13,A,14,A,15,S,4,S,5,S,6,S,7,需要对铁路网和公路网进行预处理，才能使用惯用算法，得到最小购运费用路线。,如S,7,至A,10,最小费用路线,先铁路1130km，,再公路70km,运费为77（万元）,先公路（经A,15,）40km,再铁路1100km，再公路70km,运费为76（万元）,第67页,实际上只有S,4,和S,7,需要分解成子问题求解,3)每个子问题是标准二次规划，决议变量为,x,ij,y,j,z,j,不超出135个。,第68页,问题1其它模型和解法,1）运输问题0-1规划模型,将全长5171km,管道按公里分段，共5171个需求点，钢厂为7个供给点，组成以下运输问题,c,ij,为从供给点,i,到需求点,j,最小购运费,x,ij,=,1表示从点,i,到点,j,购运1单位钢管,求解时要针对规模问题寻求改进算法,第69页,2）最小费用网络流模型,Source,S1,S2,S7,A1,A2,A15,P11,P1,l,1,P21,Sink,(,s,i,p,i,),(+,c,ij,),(1,1),(1,l,i,),(1,0),Source,S1,S2,S7,A1,A2,A15,P1,P2,Sink,(,s,i,p,i,),(+,c,ij,),(,l,i,f,(,f,+1)/2),(,l,i,0),线性费用网络(只有产量上限),非线性费用网络(只有产量上限),边标识（流量上限，单位费用）,用标准算法(如最小费用路算法)求解,无单位费用概念(,f,(,f,+1)/2,),需修改最小费用路算法,第70页,2）最小费用网络流模型,产量有下限,r,i,时修正,Source,Si,Si,(,s,i,-r,i,p,i,),(,r,i,0),(+,0),得到结果应加上,才是最小费用,第71页,S,1,S,2,S,3,S,6,S,5,S,1,S,2,S,2,S,3,S,3,S,5,S,5,S,6,3)最小面积模型,A,1,A,2,A,3,A,4,A,5,A,6,A,7,A,8,A,9,A,10,A,11,A,12,A,13,A,14,A,15,c,x,作图：,S,i,到管道,x,单位钢管最小购运费用,c,由各条,S,i,首尾相连(横坐标)组成一条折线对应一个购运方案，折线下面面积对应方案费用,在产量约束下找面积最小折线,第72页,论文中发觉主要问题,1）针对题目给数据用凑方法算出结果，没有处理这类问题普通模型,2）局部最优，如将管道分为左右两段，分别寻求方案；如将问题分为购运和铺设两部分，分别寻优（会造成每段管道都从两端铺到中点）,4）由S,i,至A,j,最小购运费用路线及最小费用,c,ij,不对,5）数字结果相差较大(如最小费用应127.5至128.2亿元),第73页,问题2：分析对购运计划和总费用影响（哪个钢厂销价改变影响最大；哪个钢厂产量上限改变影响最大）,规划问题灵敏度分析,问题3：管道为树形图,70,10,88,10,70,62,300,220,210,170,690,462,160,320,160,A,10,A,11,A,12,S,4,S,5,S,6,130,A,17,A,18,A,19,A,20,190,260,100,(,jk,),是连接A,j,A,k,边，E是树形图边集，,l,jk,是(,jk,)长度，,y,jk,是由A,j,沿(,jk,)铺设钢管数量,第74页,1-3 实例分析2,1998年全国大学生数模竞赛A题,第75页,投资效益和风险,(1998年全国大学生数学建模竞赛A题),第76页,原题还有一组,n,=25数据，现略去。,第77页,问题分析,优化问题,决议,每种资产投资额（投资组合）,目标,净收益最大,整体风险最小,在一定风险下收益最大决议,在一定收益下风险最小决议,收益和风险按一定百分比组合最优决议,一组解(如在一系列风险值下收益最大决议),二者矛盾,冒险型投资者从中选择高风险下收益最大决议,保守型投资者则可从低风险下决议中选取,第78页,模型建立,用数学符号和式子表述决议变量、结构目标函数、确定约束条件。,x,i,对S,i,(,i,=0,1,n),投资,S,0,表示存入银行.,目标函数,总收益,投资S,i,净收益减去交易费，对,i,求和,总体风险,投资S,i,风险，对,i,求最大值,对S,i,投资,x,i,加,交易费，对,i,求和，不超出给定资金M.,决议变量,约束条件,第79页,0,u,i,x,i,c,i,p,i,u,i,1）,投资S,i,交易费、净收益、风险、资金表示式,交易费,净收益,(收益率,r,i,),风险,资金,(风险损失率,q,i,),第80页,2）,投资方案总,收益、总体风险、资金表示式,投资方案,总,收益,总体风险,资金,3）两目标（,总,收益、总体风险）优化模型,第81页,4）单目标优化模型,第82页,模型简化,交易费,u,i,很小M很大,资金约束,设M=1,投资S,i,百分比,第83页,设M=1,线性规划模型LP1,模型M1简化,M1,第84页,模型M2简化,M2,极大极小规划模型,线性规划模型LP2,引入人工变量,x,n+1,第85页,模型M3简化,M3,线性规划模型,LP3,模型求解,LP1,LP2,LP3都很轻易用MATLAB,MATHEMATICA或其它数学软件求解,第86页,线性规划模型LP1,第87页,LP1,结果,风险水平取k=02.5%,得投资百分比y,0,y,4,第88页,LP1,结果,第89页,LP3,结果,与LP1相同,第90页,1-4 实例分析1,灵敏度分析又称为后优化分析,第91页,1.4 线性规划灵敏度分析,线性规划是静态模型,参数发生改变，原问题最优解还是不是最优,哪些参数轻易发生改变,C,b,A,每个参数发生多大改变不会破坏最优解,灵敏度越小，解稳定性越好,第92页,1.4.1 边际值(影子价),q,i,以(max,)为例,边际值(影子价),q,i,是指在最优解基础上，当第,i,个约束行右端项,b,i,降低一个单位时，目标函数改变量,第93页,例1.4.1,第94页,关于影子价一些说明,影子价是资源最优配置下资源理想价格，资源影子价与资源紧缺度相关,松弛变量增加一个单位等于资源降低一个单位,剩下变量增加一个单位等于资源增加一个单位,资源有剩下，在最优解中就有对应松弛变量存在，且其影子价为 0,影子价为 0，资源并不一定有剩下,应用，邮电产品影子价格,第95页,1.4.2 价值系数,c,j,灵敏度分析,c,j,变动可能因为市场价格波动，或生产成本变动,c,j,灵敏度分析是在确保最优解基变量不变情况下，分析,c,j,允许变动范围,c,j,c,j,改变会引发检验数改变，有两种情况,非基变量对应价值系数改变，不影响其它检验数,基变量对应价值系数改变，影响全部非基变量检验数,1、非基变量对应价值系数灵敏度分析,第96页,例,1.4.2,第97页,2、,基变量对应价值系数灵敏度分析,因为,基变量对应价值系数在,C,B,中出现，所以它会影响全部非基变量检验数,只有一个基变量,c,j,发生改变，改变量为,c,j,令,c,j,在,C,B,中第,k,行，研究非基变量,x,j,机会成本改变,第98页,设,x,4,价值系数增加,c,4,，对应,k,=2，,有一边为空集怎样处理,为何,a,kj,=0不出现在任何一边集合中,与对偶单纯型法找入变量公式一样,第99页,2.4.3 右端项,b,i,灵敏度分析,设,X,B,=,B,1,b,是最优解，则有,X,B,=,B,1,b,0,b,改变不会影响检验数,b,改变量,b,可能造成原最优解变为非可行解,第100页,1.4.3 右端项,b,i,灵敏度分析,第101页,以,b,2,为例,x,6,是对应初始基变量，所以有,第102页,1.4.4 技术系数,a,ij,灵敏度分析,技术系数,a,ij,改变影响比较复杂,对应基变量,a,ij,，且资源,b,i,已全部用完,对应基变量,a,ij,，但资源,b,i,未用完,对应非基变量,a,ij,，且资源,b,i,全用完或未用完,1、对应基变量,a,ij,，且资源,b,i,已全部用完,a,ij,=0,2、对应基变量,a,ij,，但资源,b,i,未用完,a,ij,x,n+i,/x,j,上述两个公式不充分，为何？,B,1,发生改变，从而引发非基变量检验数,c,j,z,j,改变,3、对应非基变量,a,ij,只影响对应非基变量,x,j,检验数,c,j,z,j,若,a,ij,0，不会破坏最优解,若,a,ij,0,当,X,3,=0,火车,X,3,=1,船,第126页,例2、,a,i1,x,1,+,a,i2,x,2,+,a,in,x,n,b,i,(,i=1,m,),相互排斥m,个约束，只有一个起作用,a,i1,x,1,+,a,in,x,n,b,i,+,y,i,M,(,i=1,m,),y,1,+,y,m,=m-1,y,i,为0或1 M,0,第127页,2.2 整数规划解法,(一)、整数规划解：,可行域为其对应线性规划问题可行域子集,例1、,LP:X=(4.8,0)maxZ=96,ILP:X=(4,1)maxZ=90,x,1,x,2,6,2,O,6.5,(4.8,0),第128页,(1)、四舍五入法,可估近似解，例中,X=(4,0),Z=80,80 Z*,96,0Z*-80,S,0,且解为整数解，令Sc,S0,且解为非整数解，令,(C)，,(D)取代(B)返回(4),(6)、全部枝剪完，停,第138页,优点：,(1)、任何模型均可用；,(2)、思绪简单、灵活；,(3)、速度快；,(4)、适合上机。,第139页,分枝定界法注意事项：,(1)、分枝变量选择标准：,按目标函数系数：选系数绝对值最大者变 量先分。,对目标值升降影响最大。,选与整数值相差最大非整数变量先分枝。,按使用者经验，对各整数变量排定主要性,优先次序。,第140页,(2)、分枝节点选择：,广探法：,选目标函数当前最大值节点，找到整数,解质量高。慢。,深探法(后进先出法)：,最终打开节点最先选，尽快找到整数解。,整数解质量可能不高。,第141页,01问题分枝定界法（背包问题),例：,maxZ=12X,1,+,12X,2,+,9X,3,+,15X,4,+,90X,5,+,26X,6,+,112X,7,(A),3X,1,+,4X,2,+,3X,3,+,3X,4,+,15X,5,+,13X,6,+,16X,7,35,X,j,为0或1，,(j,=17,),松弛问题,(B)为,同于,(A)约束，目标,0,X,j,1,(j,=17,),第142页,解:“单位重量价值大先放”,重量 价值 价/重,1 3 12 4 ,2 4 12 3,3 3 9 3,4 3 15 5 ,5 15 90 6 ,6 13 26 2,7 16 112 7 ,第143页,(0),Z=221,X,7,=,X,5,=,X,4,=1,X,1,=1/3,(9),217,X,1,=,X,4,=X,7,=1,X,5,=13/5,(10),217,X,1,=,X,7,=,X,5,=1,X,2,=1/4,(5),216,X,3,=,X,7,=,X,5,=1,X,4,=1/3,(6),219,X,7,=,X,5,=,X,4,=1,X,6,=1/13,(1),219,X,1,=,X,7,=,X,5,=1,X,4,=1/3,(7),174,X,6,=,X,7,=1,X,5,=6/15,(8),217,X,7,=,X,5,=,X,4,=1,(2),220,X,7,=,X,5,=,X,4,=1,X,2,=1/4,(3),214,X,2,=,X,7,=,X,5,=1,(4),220,X,7,=,X5,=,X,4,=1,X,3,=1/3,X,1,=1,X,1,=0,X,2,=1,X,2,=0,X,3,=1,X,3,=0,X,4,=1,X,4,=0,X,6,=1,X,6,=0,第144页,144,隐枚举法,(一)、基本思想：,对,maxZ=CX,AX=b,X为0,2,n,个可能解，只检验其中一部分,例：,max,Z,=2x,1,+4x,2,+x,3,3x,1,-,8x,2,+5x,3,-,1,x,1,x,2,x,3,为,0,1,第145页,X,1,=1,X,1,=0,1,1,1,0,1,0,1,0,1,X,2,=0,X,3,=0,0,X,2,=0,X,2,=1,X,1,=1,X,3,=10,0,0,1,第146页,(二)、简单隐枚举法(,max,),标准：,(1)、用试探法，求出一个可行解，以它目标值作为当前最好值,Z,0,(2)、增加过滤条件,Z,Z,0,(3)、将,x,i,按,c,i,由小,大排列,第147页,例：,max,Z,=3x,1,-2x,2,+5x,3,x,1,+2x,2,-,x,3,2,x,1,+4x,2,+x,3,4,x,1,+x,2,3,4x,2,+x,3,6,x,1,x,2,x,3,为0或1,解：观察得解,(x,1,x,2,x,3,)=(1,0,0)Z,0,=3,过滤条件,：3x,1,-2x,2,+5x,3,3,将,(x,1,x,2,x,3,),(x,2,x,1,x,3,),第148页,解,(x,2,x,1,x,3,),目标值,Z,0,当前最好值,(0,0,0)0 5,(0,1,0)3 8,(1,0,0)-2 ,(1,0,1)3 ,(1,1,0)1 ,(1,1,1)6 ,最优解,x=(1,0,1),T,Z=8,第149页,