数学建模与大学生数学建模竞赛市公开课一等奖百校联赛特等奖课件.pptx

数学建模数学建模与与大学生数学建模竞赛大学生数学建模竞赛第1页一、数学建模一、数学建模 数学建模是一门新兴学科，数学建模是一门新兴学科，2020世纪世纪7070年代年代初诞生于英、美等当代工业国家。因为新技术尤初诞生于英、美等当代工业国家。因为新技术尤其是计算机技术飞速发展，大量实际问题需要用其是计算机技术飞速发展，大量实际问题需要用计算机来处理，而计算机与实际问题之间需要数计算机来处理，而计算机与实际问题之间需要数学模型来沟通，所以这门学科在短短几十年时间学模型来沟通，所以这门学科在短短几十年时间快速辐射至全球大部分国家和地域。快速辐射至全球大部分国家和地域。8080年代初，年代初，我国高等院校也陆续开设了数学建模课程，伴随我国高等院校也陆续开设了数学建模课程，伴随数学建模教学活动（包含数学建模课程、数学建数学建模教学活动（包含数学建模课程、数学建模竞赛和数学建模试验课程等）开展，这门学科模竞赛和数学建模试验课程等）开展，这门学科越来越得到重视，也深受广大师生喜爱。越来越得到重视，也深受广大师生喜爱。第2页什么是数学模型呢？数学模型（Mathematical Model）是指对于现实世界某一特定对象，为了某个特定目标，做出一些必要简化和假设，利用适当数学工具得到一个数学结构。数学结构是指数学符号、数学关系式、数学命题、图形图表等，这些基于数学思想与方法数学问题。总之，数学模型是对实际问题一个抽象，基于数学理论和方法，用数学符号、数学关系式、数学命题、图形图表等来刻画客观事物本质属性与其内在联络。第3页什么是数学建模呢？数学建模（Mathematical Modeling）就是建立数学模型，建立数学模型过程就是数学建模过程。数学建模是一个数学思索方法，是利用数学语言和方法，经过抽象、简化建立能近似刻画并处理实际问题一个强有力数学伎俩。第4页二、数学建模采取主要方法二、数学建模采取主要方法（一）、机理分析法：依据对客观事物特征认识从基本（一）、机理分析法：依据对客观事物特征认识从基本物理定律以及系统结构数据来推导出模型。物理定律以及系统结构数据来推导出模型。1 1、百分比分析法：建立变量之间函数关系最基本最惯用方、百分比分析法：建立变量之间函数关系最基本最惯用方法。法。2 2、代数方法：求解离散问题（离散数据、符号、图形）主、代数方法：求解离散问题（离散数据、符号、图形）主要方法。要方法。3 3、逻辑方法：是数学理论研究主要方法，对社会学和经济、逻辑方法：是数学理论研究主要方法，对社会学和经济学等领域实际问题，在决议，对策等学科中得到广泛应学等领域实际问题，在决议，对策等学科中得到广泛应用。用。4 4、常微分方程：处理两个变量之间改变规律，关键是建立、常微分方程：处理两个变量之间改变规律，关键是建立“瞬时改变率瞬时改变率”表示式。表示式。5 5、偏微分方程：处理因变量与两个以上自变量之间改变规、偏微分方程：处理因变量与两个以上自变量之间改变规律。律。第5页（二）、数据分析法：经过对量测数据统计分析，找（二）、数据分析法：经过对量测数据统计分析，找出与数据拟合最好模型出与数据拟合最好模型1 1、回归分析法：用于对函数、回归分析法：用于对函数f f（x x）一组观察值）一组观察值（xi,fixi,fi）i=1,2,ni=1,2,n，确定函数表示式，因为处理是静态独，确定函数表示式，因为处理是静态独立数据，故称为数理统计方法。立数据，故称为数理统计方法。2 2、时序分析法：处理是动态相关数据，又称为过程统计方、时序分析法：处理是动态相关数据，又称为过程统计方法。法。二、数学建模采取主要方法二、数学建模采取主要方法 第6页（三）、仿真和其它方法（三）、仿真和其它方法1 1、计算机仿真（模拟）：实质上是统计预计方法，等效于抽、计算机仿真（模拟）：实质上是统计预计方法，等效于抽样试验。样试验。离散系统仿真，有一组状态变量。离散系统仿真，有一组状态变量。连续系统仿连续系统仿真，有解析表示式或系统结构图。真，有解析表示式或系统结构图。2 2、因子试验法：在系统上作局部试验，再依据试验结果进行、因子试验法：在系统上作局部试验，再依据试验结果进行不停分析修改，求得所需模型结构。不停分析修改，求得所需模型结构。3 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 1、只有过程、规则等定性假设，无详细定量数据；、只有过程、规则等定性假设，无详细定量数据；2 2、给出若干实测或统计数据；、给出若干实测或统计数据；3 3、给出若干参数或图形；、给出若干参数或图形；4 4、蕴涵着一些机动、可发挥补充假设条件，或参赛者、蕴涵着一些机动、可发挥补充假设条件，或参赛者能够依据自己搜集或模拟产生数据。能够依据自己搜集或模拟产生数据。第13页四、赛题题型结构形式组成部分四、赛题题型结构形式组成部分（三）、要求回答问题，往往有几个问题（普通不（三）、要求回答问题，往往有几个问题（普通不是唯一答案）是唯一答案）1 1、比较确定性答案（基本答案）；、比较确定性答案（基本答案）；2 2、更细致或更高层次讨论结果（往往是讨论最优方案、更细致或更高层次讨论结果（往往是讨论最优方案提法和结果）。提法和结果）。第14页（一）、标题、摘要部分（一）、标题、摘要部分1 1、题目：写出较确切题目（不能只写、题目：写出较确切题目（不能只写A A题、题、B B题）。题）。2 2、摘要：、摘要：200-300200-300字，包含模型主要特点、建模方法字，包含模型主要特点、建模方法和主要结果。和主要结果。3 3、内容较多时最好有个目录。、内容较多时最好有个目录。五、五、竞赛答卷（三大部分）竞赛答卷（三大部分）第15页（二）、中心部分1 1、问题提出，问题分析。、问题提出，问题分析。2 2、模型建立：、模型建立：补充假设条件，明确概念，引进参数；补充假设条件，明确概念，引进参数；模型形式（可有多个形式模型）；模型形式（可有多个形式模型）；模型求解；模型求解；模型性质；模型性质；3 3、计算方法设计和计算机实现。、计算方法设计和计算机实现。4 4、结果分析与检验。、结果分析与检验。5 5、讨论：模型优缺点，改进方向，推广新思想。、讨论：模型优缺点，改进方向，推广新思想。6 6、参考文件：注意格式。、参考文件：注意格式。五、五、竞赛答卷（三大部分）竞赛答卷（三大部分）第16页（三）、附录部分（三）、附录部分1 1、计算程序、框图。、计算程序、框图。2 2、各种求解演算过程，计算中间结果。、各种求解演算过程，计算中间结果。3 3、各种图形、表格。、各种图形、表格。五、五、竞赛答卷（三大部分）竞赛答卷（三大部分）第17页中国大学生数学建模竞赛题目聚集中国大学生数学建模竞赛题目聚集（注：（注：A A、B B是大学组赛题，是大学组赛题，C C、DD题是大专组赛题，任选其一。）题是大专组赛题，任选其一。）第18页19921992A A、施肥效果分析；、施肥效果分析；B B、试验数据分析。、试验数据分析。19931993A A、非线性交调频率设计；、非线性交调频率设计；B B、足球队排名、足球队排名次。次。19941994A A、逢山开路；、逢山开路；B B、锁具装箱。、锁具装箱。19951995A A、一个飞行管理问题；、一个飞行管理问题；B B、天车与冶炼炉、天车与冶炼炉作业调度。作业调度。19961996A A、最优打鱼策略；、最优打鱼策略；B B、节水洗衣机。、节水洗衣机。19971997A A、零件参数设计；、零件参数设计；B B、截断切割。、截断切割。19981998A A、投资收益与风险；、投资收益与风险；B B、灾情巡视路线。、灾情巡视路线。19991999A A、自动化车床管理；、自动化车床管理；B B、钻井布局；、钻井布局；C C、煤矸石堆积；煤矸石堆积；D D、钻井布局（注、钻井布局（注:比比B B稍易）稍易）第19页A A、DNADNA序列分类；序列分类；B B、钢管订购和运输；、钢管订购和运输；C C、飞越北极；飞越北极；D D、空洞探测。、空洞探测。A A、血管三维重建；、血管三维重建；B B、公交车调度；、公交车调度；C C、基金、基金使用计划；使用计划；D D、公交车调度。、公交车调度。A A、车灯线光源优化设计；、车灯线光源优化设计；B B、彩票中数学；、彩票中数学；C C、车灯线光源计算；车灯线光源计算；D D、赛程安排。、赛程安排。A A、SARSSARS传输；传输；B B、露天矿生产车辆安排；、露天矿生产车辆安排；C C、SARSSARS传输；传输；D D、抢渡长江。、抢渡长江。A A、奥运会暂时超市网点设计；、奥运会暂时超市网点设计；B B、电力市场输、电力市场输电阻塞管理；电阻塞管理；C C、饮酒驾车；、饮酒驾车；D D、公务员招聘。、公务员招聘。A A、长江水质评价和预测；长江水质评价和预测；B B、DVD DVD在线租赁；在线租赁；C C、雨量预报方法评价；雨量预报方法评价；D D、DVD DVD在线租赁。在线租赁。第20页线性规划（概论）线性规划（概论）线性规划（线性规划（线性规划（线性规划（Linear Programming)Linear Programming)Linear Programming)Linear Programming)创始人：创始人：创始人：创始人：1947194719471947年美国人年美国人年美国人年美国人G.B.G.B.G.B.G.B.丹齐克（丹齐克（丹齐克（丹齐克（DantzingDantzingDantzingDantzing）1951195119511951年提出单纯形算法（年提出单纯形算法（年提出单纯形算法（年提出单纯形算法（SimplerSimplerSimplerSimpler）1963196319631963年年年年DantzingDantzingDantzingDantzing写成写成写成写成“Linear Programming and“Linear Programming and“Linear Programming and“Linear Programming and Extension”Extension”Extension”Extension”1979197919791979年苏联年苏联年苏联年苏联KhachianKhachianKhachianKhachian提出提出提出提出“椭球法椭球法椭球法椭球法”1984198419841984年印度年印度年印度年印度KarmarkarKarmarkarKarmarkarKarmarkar提出提出提出提出“投影梯度法投影梯度法投影梯度法投影梯度法”线性规划是研究线性不等式组理论，或者说线性规划是研究线性不等式组理论，或者说线性规划是研究线性不等式组理论，或者说线性规划是研究线性不等式组理论，或者说是研究（高维空间中）凸多面体理论，是线性代是研究（高维空间中）凸多面体理论，是线性代是研究（高维空间中）凸多面体理论，是线性代是研究（高维空间中）凸多面体理论，是线性代数应用和发展。数应用和发展。数应用和发展。数应用和发展。第21页1-1 1-1 线性规划基本概念线性规划基本概念生产计划问题生产计划问题怎怎样样合合理理使使用用有有限限人人力力，物物力力和和资金，使得收到最好经济效益。资金，使得收到最好经济效益。怎怎样样合合理理使使用用有有限限人人力力，物物力力和和资资金金，以以到到达达最最经经济济方方式式，完完成成生生产计划要求。产计划要求。第22页例例1.1 生产计划问题（资源利用问题）生产计划问题（资源利用问题）胜胜利利家家俱俱厂厂生生产产桌桌子子和和椅椅子子两两种种家家俱俱。桌桌子子售售价价50元元/个个，椅椅子子销销售售价价格格30元元/个个，生生产产桌桌子子和和椅椅子子要要求求需需要要木木工工和和油油漆漆工工两两种种工工种种。生生产产一一个个桌桌子子需需要要木木工工4小小时时，油油漆漆工工2小小时时。生生产产一一个个椅椅子子需需要要木木工工3小小时时，油油漆漆工工1小小时时。该该厂厂每每个个月月可可用用木木工工工工时时为为120小小时时，油油漆漆工工工工时时为为50小小时时。问问该该厂厂怎怎样样组组织织生生产产才才能能使每个月销售收入最大？使每个月销售收入最大？第23页解解：将将一一个个实实际际问问题题转转化化为为线线性性规规划划模模型型有有以以下下几个步骤：几个步骤：1确定决议变量确定决议变量：x1=生产桌子数量生产桌子数量 x2=生产椅子数量生产椅子数量2确定目标函数确定目标函数：家俱厂目标是销售收入最大家俱厂目标是销售收入最大 max z=50 x1+30 x23确定约束条件确定约束条件：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=c1x1+c2x2+.+cnxns.t.a11x1+a12x2+.+a1nxn (=,)b1 a21x1+a22x2+.+a2nxn (=,)b2 .am1x1+am2x2+.+amnxn (=,)bm x1,x2.xn 0第31页线性规划问题隐含假定：线性规划问题隐含假定：百分比性假定百分比性假定：决议变量改变引发目标：决议变量改变引发目标函数改变量和决议变量改变量成百分比，函数改变量和决议变量改变量成百分比，一样，每个决议变量改变引发约束方程一样，每个决议变量改变引发约束方程左端值改变量和该变量改变量成百分比。左端值改变量和该变量改变量成百分比。可加性假定可加性假定：每个决议变量对目标函数：每个决议变量对目标函数和约束方程影响是独立于其它变量，目和约束方程影响是独立于其它变量，目标函数值是每个决议变量对目标函数贡标函数值是每个决议变量对目标函数贡献总和。献总和。第32页线性规划问题隐含假定：线性规划问题隐含假定：连续性假定连续性假定：线性规划问题中决议：线性规划问题中决议变量应取连续值。变量应取连续值。确定性假定确定性假定：线性规划问题中全部：线性规划问题中全部参数都是确定参数。线性规划问题参数都是确定参数。线性规划问题不包含随机原因。不包含随机原因。第33页线性规划问题隐含假定：线性规划问题隐含假定：百分比性假定百分比性假定可加性假定可加性假定连续性假定连续性假定确定性假定确定性假定第34页线性规划问题标准形式线性规划问题标准形式(1)：Max S=c1x1+c2x2+.+cnxns.t.a11x1+a12x2+.+a1nxn=b1 a21x1+a22x2+.+a2nxn=b2 .am1x1+am2x2+.+amnxn=bm x1,x2.xn 0其中：其中：bi 0(i=1,2,.m)第35页线性规划问题标准形式线性规划问题标准形式(2)：n Max S =cjxj j=1 n s.t.aijxj=bi (i=1,2,.n)j=1 xj 0(j=1,2,.m)第36页线性规划标准型矩阵形式线性规划标准型矩阵形式(3)：Max S =CX s.t.AX=b X 0第37页 a11 a12 .a1n b1 A=a21 a22 .a2n b =b2 .am1 am2 .amn bn c c1 1 x x1 1 0 0 c c2 2 x x2 2 0 0C=X=0=C=X=0=.c cn n x xn n 0 0第38页怎样将普通问题化为标准型：怎样将普通问题化为标准型：若目标函数是求最小值若目标函数是求最小值 Min S=CX 令令 S=-S,则则 Max S=-CX若约束条件是不等式若约束条件是不等式若约束条件是若约束条件是“”不等式不等式 n aijxj+yi=bi j=1 yi 0是非负是非负松驰变量松驰变量第39页怎样将普通问题化为标准型：怎样将普通问题化为标准型：若约束条件是若约束条件是“”不等式不等式 n aijxj-zi =bi j=1 zi 0是非负松驰变量是非负松驰变量第40页怎样将普通问题化为标准型：怎样将普通问题化为标准型：若约束条件右面某一常数项若约束条件右面某一常数项 bi=0 令令xj=xj-xj”（可正可负）（可正可负）任何形式线性规划总能够化成标准型任何形式线性规划总能够化成标准型第41页例例1.3 将以下问题化成标准型将以下问题化成标准型:Min S =-x1+2x2-3x3s.t.x1+x2+x3 7 x1-x2+x3 2 -3x1+x2+2x3=5 x1,x2 0 x3 无非负限制无非负限制第42页Max S =x1-2x2+3x3-3x3”s.t.x1+x2+x3-x3”+x4 =7 x1-x2+x3-x3”-x5=2 -3x1+x2+2x3-2x3”=5 x1,x2,x3,x3”,x4,x5 0第43页1-3 1-3 线性规划问题线性规划问题解概念解概念第44页（二维）线性规划问题图解法：（二维）线性规划问题图解法：（1）满足约束条件变量值，称为可行解。）满足约束条件变量值，称为可行解。（2）使目标函数取得最优值可行解，称）使目标函数取得最优值可行解，称为最优解。为最优解。例例1.1数学模型数学模型 max S=50 x1+30 x2 s.t.4x1+3x2 120 2x1+x2 50 x1,x2 0第45页x2504030201010203040 x14x1+3x2 120由由 4x1+3x2 120 x1 0 x2 0围成区域围成区域第46页x2504030201010203040 x12x1+x2 50由由 2x1+x2 50 x1 0 x2 0围成区域围成区域第47页x2504030201010203040 x12x1+x2 504x1+3x2 120可行域可行域可行域可行域同时满足：同时满足：2x1+x2 504x1+3x2 120 x1 0 x2 0区域区域可行域可行域第48页x2504030201010203040 x1可行域可行域可行域可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）可行域是由约束条件围成可行域是由约束条件围成区域，该区域内每一点都区域，该区域内每一点都是可行解，它全体组成问是可行解，它全体组成问题解集合。题解集合。该问题可行域是由该问题可行域是由O，Q1，Q2，Q3作为顶点作为顶点凸多凸多边形边形第49页x2504030201010203040 x1可行域可行域可行域可行域目标函数是以目标函数是以S作为作为参数一组平行线参数一组平行线x2=S/30-（5/3）x1第50页x2504030201010203040 x1可行域可行域可行域可行域当当S值不停增加时，该直线值不停增加时，该直线x2=S/30-（5/3）x1沿着其法线方向向右上方移沿着其法线方向向右上方移动。动。第51页x2504030201010203040 x1可行域可行域可行域可行域当该直线移到当该直线移到当该直线移到当该直线移到QQ2 2点时，点时，点时，点时，S S（目标函（目标函（目标函（目标函数）值到达最大：数）值到达最大：数）值到达最大：数）值到达最大：Max S=50*15+30*20=1350此时最优解此时最优解=（15，20）Q2（15，20）第52页二个主要结论：二个主要结论：满足约束条件可行域普通都组满足约束条件可行域普通都组成凸多边形。这一事实能够推成凸多边形。这一事实能够推广到更多变量场所。广到更多变量场所。最优解必定能在凸多边形某一最优解必定能在凸多边形某一个顶点上取得，这一事实也能个顶点上取得，这一事实也能够推广到更多变量场所。够推广到更多变量场所。第53页解讨论：解讨论：最优解是唯一解最优解是唯一解；无穷多组最优解：无穷多组最优解：例例1.1目标函数由目标函数由 max S=50 x1+30 x2变成：变成：max S=40 x1+30 x2 s.t.4x1+3x2 120 2x1+x2 50 x1,x2 0第54页x2504030201010203040 x1可行域可行域可行域可行域目标函数是同约束目标函数是同约束条件：条件：4x1+3x2 120平行直线平行直线x2=S/30-（4/3）x1第55页x2504030201010203040 x1可行域可行域可行域可行域当当S值增加时，目标值增加时，目标函数同约束条件：函数同约束条件：4x1+3x2 120重合，重合，Q1与与Q2之间之间都是最优解。都是最优解。Q1（25，0）Q2（15，20）第56页解讨论：解讨论：无界解：无界解：例：例：max S=x1+x2 s.t.-2x1+x2 40 x1-x2 20 x1,x2 0第57页x2504030201010203040 x1该可行域无界，目标函该可行域无界，目标函数值可增加到无穷大，数值可增加到无穷大，称这种情况为无界解或称这种情况为无界解或无最优解。无最优解。第58页解讨论：解讨论：无可行解：无可行解：例：例：max S=2x1+3x2 s.t.x1+2x2 8 x1 4 x2 3 -2x1+x2 4 x1,x2 0该问题可行域为该问题可行域为空集，即无可行空集，即无可行解，也不存在最解，也不存在最优解。优解。第59页解情况：解情况：有可行解有可行解 有唯一最优解有唯一最优解 有没有穷最优解有没有穷最优解 无最优解无最优解无可行解无可行解第60页1-2 实例分析1全国大学生数模竞赛B题第61页B B 钢管订购和运输钢管订购和运输由钢管厂订购钢管，经铁由钢管厂订购钢管，经铁路、公路运输，铺设一条路、公路运输，铺设一条钢管管道钢管管道A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道铁路公路S1S7 钢管厂火车站450 里程（km）（沿管道建有公路）第62页钢厂产量和销价（1单位钢管=1km管道钢管）钢厂产量下限：500单位钢管1单位钢管铁路运价1000km以上每增加1至100km运价增加5万元1单位钢管公路运价：0.1万元/km（不足整公里部分按整公里计）第63页（1）制订钢管订购和运输计划，使总费用最小）制订钢管订购和运输计划，使总费用最小.（2）分析对购运计划和总费用影响：哪个钢厂钢管销价改）分析对购运计划和总费用影响：哪个钢厂钢管销价改变影响最大；哪个钢厂钢管产量上限改变影响最大？变影响最大；哪个钢厂钢管产量上限改变影响最大？A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16130A17A18A19A20A21190260100（3）讨论管道为树形图情形）讨论管道为树形图情形第64页问题问题1基本模型和解法基本模型和解法总费用最小优化问题总费用：订购，运输（由各厂Si经铁路、公路至各点Aj,i=1,7;j=1,15），铺设管道Aj Aj+1（j=1,14)由Si至Aj最小购运费用路线及最小费用cij 由Si至Aj最优运量xij由Aj向Aj Aj-1段铺设长度zj及向Aj Aj+1段铺设长度yj最优购运计划最优购运计划约束条件约束条件钢厂产量约束：上限和下限（假如生产话）运量约束：xij对i求和等于zj 加yj；yj与 zj+1之和等于Aj Aj+1段长度lj第65页基本模型基本模型由Aj向Aj Aj-1段铺设运量为 1+zj=zj(zj+1)/2由Aj向Aj Aj+1段铺设运量为 1+yj=yj(yj+1)/2二次规划第66页求解步骤求解步骤1）求由Si至Aj最小购运费用路线及最小费用cij 难点：公路运费是里程线性函数，而铁路运费是里程分段阶跃函数，故总运费不具可加性。因而计算最短路惯用Dijkstra算法、Floyd算法失效。A17010881070627030202030300220210420500170690462160320160110290A10A11A12A13A14A15S4S5S6S7需要对铁路网和公路网进行预处理，才能使用惯用需要对铁路网和公路网进行预处理，才能使用惯用算法，得到最小购运费用路线。算法，得到最小购运费用路线。如S7至A10最小费用路线先铁路1130km，再公路70km,运费为77（万元）先公路（经A15）40km,再铁路1100km，再公路70km,运费为76（万元）第67页实际上只有S4和S7需要分解成子问题求解 3)每个子问题是标准二次规划，决议变量为xij,yj,zj,不超出135个。第68页问题问题1其它模型和解法其它模型和解法1）运输问题0-1规划模型将全长5171km管道按公里分段，共5171个需求点，钢厂为7个供给点，组成以下运输问题 cij为从供给点i到需求点j最小购运费xij=1表示从点i到点j购运1单位钢管求解时要针对规模问题寻求改进算法第69页2）最小费用网络流模型）最小费用网络流模型SourceS1S2S7A1A2A15P11P1l1P21Sink(si,pi)(+,cij)(1,1),(1,li)(1,0)SourceS1S2S7A1A2A15P1P2Sink(si,pi)(+,cij)(li,f(f+1)/2)(li,0)线性费用网络线性费用网络(只有产量上限只有产量上限)非线性费用网络非线性费用网络(只有产量上限只有产量上限)边标识（流量上限，单位费用）用标准算法(如最小费用路算法)求解无单位费用概念(f(f+1)/2),需修改最小费用路算法第70页2）最小费用网络流模型）最小费用网络流模型产量有下限ri时修正SourceSiSi(si-ri,pi)(ri,0)(+,0)得到结果应加上 才是最小费用第71页S1S2S3S6S5S1S2S2S3S3S5S5S63)最小面积模型A1A2A3A4A5A6A7A8A9A10A11A12A13A14A15cx作图：Si到管道x单位钢管最小购运费用c由各条Si首尾相连(横坐标)组成一条折线对应一个购运方案，折线下面面积对应方案费用在产量约束下找面积最小折线第72页论文中发觉主要问题论文中发觉主要问题1）针对题目给数据用凑方法算出结果，没有处理这类问题普通模型2）局部最优，如将管道分为左右两段，分别寻求方案；如将问题分为购运和铺设两部分，分别寻优（会造成每段管道都从两端铺到中点）4）由Si至Aj最小购运费用路线及最小费用cij 不对5）数字结果相差较大(如最小费用应127.5至128.2亿元)第73页问题问题2：分析对购运计划和总费用影响（哪个钢厂销价：分析对购运计划和总费用影响（哪个钢厂销价改变影响最大；哪个钢厂产量上限改变影响最大）改变影响最大；哪个钢厂产量上限改变影响最大）规划问题灵敏度分析问题问题3：管道为树形图：管道为树形图701088107062300220210170690462160320160A10A11A12S4S5S6130A17A18A19A20190260100(jk)是连接Aj,Ak边，E是树形图边集，ljk是(jk)长度，yjk是由Aj沿(jk)铺设钢管数量第74页1-3 实例分析实例分析21998年全国大学生数模竞赛年全国大学生数模竞赛A题题第75页投资效益和风险投资效益和风险(1998年全国大学生数学建模竞赛年全国大学生数学建模竞赛A题题)第76页原题还有一组 n=25数据，现略去。第77页问题分析问题分析优化问题决议决议每种资产投资额（投资组合）目标目标净收益最大整体风险最小 在一定风险下收益最大决议 在一定收益下风险最小决议 收益和风险按一定百分比组合最优决议一组解(如在一系列风险值下收益最大决议)二者矛盾 冒险型投资者从中选择高风险下收益最大决议 保守型投资者则可从低风险下决议中选取第78页模型建立模型建立用数学符号和式子表述决议变量、结构目标函数、确定约束条件。xi i对Si(i=0,1,n)投资,S0表示存入银行.目标函数目标函数 总收益投资Si净收益减去交易费，对i求和 总体风险投资Si风险，对i求最大值对Si投资xi i加交易费，对i求和，不超出给定资金M.决议变量决议变量约束条件约束条件第79页0uixicipiui1）投资Si交易费、净收益、风险、资金表示式交易费净收益(收益率ri)风险资金(风险损失率qi)第80页2）投资方案总收益、总体风险、资金表示式投资方案总收益总体风险资金3）两目标（总收益、总体风险）优化模型第81页4）单目标优化模型第82页模型简化模型简化交易费ui很小M很大资金约束设M=1投资Si百分比第83页设M=1线性规划模型线性规划模型LP1模型模型M1简化简化M1第84页模型模型M2简化简化M2极大极小规划模型线性规划模型线性规划模型LP2引入人工变量引入人工变量 xn+1第85页模型模型M3简化简化M3线性规划线性规划模型模型LP3模型求解模型求解LP1,LP2,LP3都很轻易用MATLAB,MATHEMATICA或其它数学软件求解第86页线性规划模型线性规划模型LP1第87页LP1结果结果风险水平取风险水平取k=02.5%,得投资百分比得投资百分比y0y4第88页LP1结果结果第89页LP3结果结果与LP1相同第90页1-4 实例分析实例分析1 灵敏度分析又称为后优化分析第91页1.4 1.4 线性规划灵敏度分析线性规划灵敏度分析线性规划灵敏度分析线性规划灵敏度分析 线性规划是静态模型线性规划是静态模型 参数发生改变，原问题最优解还是不是最优参数发生改变，原问题最优解还是不是最优 哪些参数轻易发生改变哪些参数轻易发生改变 C C,b b,A A 每个参数发生多大改变不会破坏最优解每个参数发生多大改变不会破坏最优解 灵敏度越小，解稳定性越好灵敏度越小，解稳定性越好