《数学建模与大学生数学建模竞赛.ppt》由会员分享，可在线阅读，更多相关《数学建模与大学生数学建模竞赛.ppt（149页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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、因子试验法：在系统上作局部试验，再根据试验结果进行、因子试验法：在系统上作局部试验，再根据试验结果进行不断分析修改，求得所
7、需的模型结构。不断分析修改，求得所需的模型结构。3 3、人工现实法：基于对系统过去行为的了解和对未来希望达、人工现实法：基于对系统过去行为的了解和对未来希望达到的目标，并考虑到系统有关因素的可能变化，人为地组成到的目标，并考虑到系统有关因素的可能变化，人为地组成一个系统。一个系统。二、数学建模采用的主要方法二、数学建模采用的主要方法 三、大学生数学建模竞赛三、大学生数学建模竞赛 1985年在美国出现了一种叫做MCM的一年一度的大学生数学模型竞赛（Mathematical Contest in Modeling,缩写MCM）。我国自1989年首次参加这一竞赛，历届均取得优异成绩。经过数年参加美国
8、赛表明，中国大学生在数学建模方面是有竞争力和创新联想能力的。为了在国内推广这一活动，1992年由中国工业与应用数学学会（CSIAM）组织了第一次中国大学生数学建模竞赛（简称CMCM），1994年起由教育部高教司和CSIAM共同举办，每年一次（9月），现在已经成为全国高校规模最大的课外科技活动。三、大学生数学建模竞赛三、大学生数学建模竞赛 竞赛题目一般由工程技术、管理科学中的实际问竞赛题目一般由工程技术、管理科学中的实际问题简化而成，没有事先设定的标准答案，但留有题简化而成，没有事先设定的标准答案，但留有充分余地供参赛者发挥其聪明才智和创造精神。充分余地供参赛者发挥其聪明才智和创造精神。竞赛形式
9、：三名大学生组成一队，可以自由地收竞赛形式：三名大学生组成一队，可以自由地收集资料、调查研究，使用计算机、互联网和任何集资料、调查研究，使用计算机、互联网和任何软件，在三天时间内分工合作完成一篇论文。评软件，在三天时间内分工合作完成一篇论文。评奖标准：假设的合理性、建模的创造性、结果的奖标准：假设的合理性、建模的创造性、结果的正确性、文字表述的清晰程度。每年出两道题，正确性、文字表述的清晰程度。每年出两道题，大学：大学：A A、B B题，大专：题，大专：C C、D D题，任选一题。题，任选一题。A A、C C为连续型题目，为连续型题目，B B、D D为离散型题目。优秀论文为离散型题目。优秀论文
10、登在工程数学学报（登在工程数学学报（20012001年后），数学的年后），数学的实践与认识（实践与认识（20012001年前）来年第年前）来年第1 1期上。期上。三、大学生数学建模竞赛三、大学生数学建模竞赛 数学模型竞赛与通常的数学竞赛不同之处在于它数学模型竞赛与通常的数学竞赛不同之处在于它来自实际问题或有明确的实际背景，它的宗旨是来自实际问题或有明确的实际背景，它的宗旨是培养大学生用数学方法解决实际问题的意识和能培养大学生用数学方法解决实际问题的意识和能力，培养创新意识、团队精神，鼓励参与、提倡力，培养创新意识、团队精神，鼓励参与、提倡公平竞争，提高学生综合素质。整个比赛要完成公平竞争，提高
11、学生综合素质。整个比赛要完成一篇包括问题的阐述分析，模型的假设和建立，一篇包括问题的阐述分析，模型的假设和建立，计算结果及讨论的论文。通过训练和比赛，同学计算结果及讨论的论文。通过训练和比赛，同学们不仅用数学方法解决实际问题的意识和能力有们不仅用数学方法解决实际问题的意识和能力有很大提高，而且在团结合作发挥集体力量攻关，很大提高，而且在团结合作发挥集体力量攻关，以及撰写科技论文等方面将都会得到十分有益的以及撰写科技论文等方面将都会得到十分有益的锻炼。锻炼。三、大学生数学建模竞赛三、大学生数学建模竞赛 四、赛题题型结构形式的组成部分四、赛题题型结构形式的组成部分（一）、实际问题背景（一）、实际问
12、题背景、涉及面宽，有社会，经济，管理，生活，环境，自、涉及面宽，有社会，经济，管理，生活，环境，自然现象，工程技术，现代科学中出现的新问题等。然现象，工程技术，现代科学中出现的新问题等。、一般都有一个比较确切的现实问题。、一般都有一个比较确切的现实问题。四、赛题题型结构形式的组成部分四、赛题题型结构形式的组成部分（二）、若干假设条件（二）、若干假设条件1 1、只有过程、规则等定性假设，无具体定量数据；、只有过程、规则等定性假设，无具体定量数据；2 2、给出若干实测或统计数据；、给出若干实测或统计数据；3 3、给出若干参数或图形；、给出若干参数或图形；4 4、蕴涵着某些机动、可发挥的补充假设条件
13、，或参赛、蕴涵着某些机动、可发挥的补充假设条件，或参赛者可以根据自己收集或模拟产生数据。者可以根据自己收集或模拟产生数据。四、赛题题型结构形式的组成部分四、赛题题型结构形式的组成部分（三）、要求回答的问题，往往有几个问题（一般（三）、要求回答的问题，往往有几个问题（一般不是唯一答案）不是唯一答案）1 1、比较确定性的答案（基本答案）；、比较确定性的答案（基本答案）；2 2、更细致或更高层次的讨论结果（往往是讨论最优方、更细致或更高层次的讨论结果（往往是讨论最优方案的提法和结果）。案的提法和结果）。（一）、标题、摘要部分（一）、标题、摘要部分1 1、题目：写出较确切的题目（不能只写、题目：写出较
14、确切的题目（不能只写A A题、题、B B题）。题）。2 2、摘要：、摘要：200-300200-300字，包括模型的主要特点、建模方字，包括模型的主要特点、建模方法和主要结果。法和主要结果。3 3、内容较多时最好有个目录。、内容较多时最好有个目录。五、五、竞赛答卷（三大部分）竞赛答卷（三大部分）（二）、中心部分1 1、问题提出，问题分析。、问题提出，问题分析。2 2、模型建立：、模型建立：补充假设条件，明确概念，引进参数；补充假设条件，明确概念，引进参数；模型形式（可有多个形式的模型）；模型形式（可有多个形式的模型）；模型求解；模型求解；模型性质；模型性质；3 3、计算方法设计和计算机实现。、
15、计算方法设计和计算机实现。4 4、结果分析与检验。、结果分析与检验。5 5、讨论：模型的优缺点，改进方向，推广新思想。、讨论：模型的优缺点，改进方向，推广新思想。6 6、参考文献：注意格式。、参考文献：注意格式。五、五、竞赛答卷（三大部分）竞赛答卷（三大部分）（三）、附录部分（三）、附录部分1 1、计算程序、框图。、计算程序、框图。2 2、各种求解演算过程，计算中间结果。、各种求解演算过程，计算中间结果。3 3、各种图形、表格。、各种图形、表格。五、五、竞赛答卷（三大部分）竞赛答卷（三大部分）中国大学生数学建模竞赛题目汇集中国大学生数学建模竞赛题目汇集（注：（注：A A、B B是大学组赛题，是
16、大学组赛题，C C、DD题是大专组赛题，任选其一。）题是大专组赛题，任选其一。）19921992A A、施肥效果分析；、施肥效果分析；B B、实验数据分析。、实验数据分析。19931993A A、非线性交调的频率设计；、非线性交调的频率设计；B B、足球队排、足球队排名次。名次。19941994A A、逢山开路；、逢山开路；B B、锁具装箱。、锁具装箱。19951995A A、一个飞行管理问题；、一个飞行管理问题；B B、天车与冶炼炉、天车与冶炼炉的作业调度。的作业调度。19961996A A、最优捕鱼策略；、最优捕鱼策略；B B、节水洗衣机。、节水洗衣机。19971997A A、零件的参数设
17、计；、零件的参数设计；B B、截断切割。、截断切割。19981998A A、投资的收益与风险；、投资的收益与风险；B B、灾情巡视路线。、灾情巡视路线。19991999A A、自动化车床管理；、自动化车床管理；B B、钻井布局；、钻井布局；C C、煤矸石堆积；煤矸石堆积；D D、钻井布局（注、钻井布局（注:比比B B稍易）稍易）20002000A A、DNADNA序列分类；序列分类；B B、钢管订购和运输；、钢管订购和运输；C C、飞越北极；、飞越北极；D D、空洞探测。、空洞探测。20012001A A、血管的三维重建；、血管的三维重建；B B、公交车调度；、公交车调度；C C、基金使用计划
18、；基金使用计划；D D、公交车调度。、公交车调度。20022002A A、车灯线光源优化设计；、车灯线光源优化设计；B B、彩票中的数、彩票中的数学；学；C C、车灯线光源计算；、车灯线光源计算；D D、赛程安排。、赛程安排。20032003A A、SARSSARS的传播；的传播；B B、露天矿生产的车、露天矿生产的车辆安排；辆安排；C C、SARSSARS的传播；的传播；D D、抢渡长江。、抢渡长江。20042004A A、奥运会临时超市网点设计；、奥运会临时超市网点设计；B B、电力市、电力市场的输电阻塞管理；场的输电阻塞管理；C C、饮酒驾车；、饮酒驾车；D D、公务员招、公务员招聘。聘
19、。2005 A2005 A、长江水质的评价和预测；长江水质的评价和预测；B B、DVD DVD在线在线租赁；租赁；C C、雨量预报方法的评价；雨量预报方法的评价；D D、DVD DVD在线在线租赁。租赁。线性规划（概论）线性规划（概论）线性规划（线性规划（线性规划（线性规划（Linear Programming)Linear Programming)Linear Programming)Linear Programming)创始人：创始人：创始人：创始人：1947194719471947年美国人年美国人年美国人年美国人G.B.G.B.G.B.G.B.丹齐克（丹齐克（丹齐克（丹齐克（Dantzi
20、ngDantzingDantzingDantzing）1951195119511951年提出单纯形算法（年提出单纯形算法（年提出单纯形算法（年提出单纯形算法（SimplerSimplerSimplerSimpler）1963196319631963年年年年DantzingDantzingDantzingDantzing写成写成写成写成“Linear Programming and“Linear Programming and“Linear Programming and“Linear Programming and Extension”Extension”Extension”Extension
21、”1979197919791979年苏联的年苏联的年苏联的年苏联的KhachianKhachianKhachianKhachian提出提出提出提出“椭球法椭球法椭球法椭球法”1984198419841984年印度的年印度的年印度的年印度的KarmarkarKarmarkarKarmarkarKarmarkar提出提出提出提出“投影梯度法投影梯度法投影梯度法投影梯度法”线性规划是研究线性不等式组的理论，或者线性规划是研究线性不等式组的理论，或者线性规划是研究线性不等式组的理论，或者线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线说是研究（高维空间中）凸多面体的理论
22、，是线说是研究（高维空间中）凸多面体的理论，是线说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。性代数的应用和发展。性代数的应用和发展。性代数的应用和发展。1-1 1-1 线性规划基本概念线性规划基本概念生产计划问题生产计划问题如如何何合合理理使使用用有有限限的的人人力力，物物力力和资金，使得收到最好的经济效益。和资金，使得收到最好的经济效益。如如何何合合理理使使用用有有限限的的人人力力，物物力力和和资资金金，以以达达到到最最经经济济的的方方式式，完完成生产计划的要求。成生产计划的要求。例例1.1 生产计划问题（资源利用问题）生产计划问题（资源利用问题）胜胜利利家家具具厂厂生生产
23、产桌桌子子和和椅椅子子两两种种家家具具。桌桌子子售售价价50元元/个个，椅椅子子销销售售价价格格30元元/个个，生生产产桌桌子子和和椅椅子子要要求求需需要要木木工工和和油油漆漆工工两两种种工工种种。生生产产一一个个桌桌子子需需要要木木工工4小小时时，油油漆漆工工2小小时时。生生产产一一个个椅椅子子需需要要木木工工3小小时时，油油漆漆工工1小小时时。该该厂厂每每个个月月可可用用木木工工工工时时为为120小小时时，油油漆漆工工工工时时为为50小小时时。问问该该厂厂如如何何组组织织生生产产才才能能使每月的销售收入最大？使每月的销售收入最大？解解：将将一一个个实实际际问问题题转转化化为为线线性性规规划
24、划模模型型有有以以下下几个步骤：几个步骤：1确定决策变量确定决策变量：x1=生产桌子的数量生产桌子的数量 x2=生产椅子的数量生产椅子的数量2确定目标函数确定目标函数：家具厂的目标是销售收入最大家具厂的目标是销售收入最大 max z=50 x1+30 x23确定约束条件确定约束条件：4x1+3x2 120（木工工时限制）（木工工时限制）2x1+x2 50 （油漆工工时限制）（油漆工工时限制）4变量取值限制变量取值限制：一般情况，决策变量只取正值（非负值）一般情况，决策变量只取正值（非负值）x1 0,x2 0 1-2 线性规划问题的数学模型例例1.2 营养配餐问题营养配餐问题 假定一个成年人每天
25、需要从食物中假定一个成年人每天需要从食物中获得获得3000千卡的热量、千卡的热量、55克蛋白质和克蛋白质和800毫克的钙。如果市场上只有四种食毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购何选择才能在满足营养的前提下使购买食品的费用最小？买食品的费用最小？各种食物的营养成分表解解：设设xj为为第第j种种食食品品每每天天的的购购入入量量，则配餐问题的线性规划模型为：则配餐问题的线性规划模型为：min S=14x1+6x2+3x3+2x4 s.t.1000
26、 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、的一些基地美国国防部关于如何从现有的一些基地向海湾运送海湾战争所需要的人员和物资向海湾运送海湾战争所需要的人员和物资的决策的决策 Chessie道路系统关于购买和修理价值道路系统关于购买和修理价值40亿美圆货运汽车决策亿美圆货运汽车决策用于成功决策的实例：用于成功决策的实例：魁北克水利部门关于用哪几个水库来满足每魁北克水利部门关于用哪几个水库来满足每天电力需求决策天电力需求决策农场信贷系统联邦土地银行关于如何支付到农场信贷系统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金（每年期债券和应发售多少新债券以获取资金（每年共计共计60亿美圆）来维持发展决策亿美圆）来维持发展决策北美长途
28、运输公司关于每周如何调度数千辆北美长途运输公司关于每周如何调度数千辆货车的决策货车的决策埃克森炼油厂关于调节冶炼能力去适应关于埃克森炼油厂关于调节冶炼能力去适应关于无铅燃料生产的法律更改的决策无铅燃料生产的法律更改的决策线性规划问题的一般形式：线性规划问题的一般形式：Max(Min)S=c1x1+c2x2+.+cnxns.t.a11x1+a12x2+.+a1nxn (=,)b1 a21x1+a22x2+.+a2nxn (=,)b2 .am1x1+am2x2+.+amnxn (=,)bm x1,x2.xn 0线性规划问题隐含的假定：线性规划问题隐含的假定：比例性假定比例性假定：决策变量变化引起的
29、目标：决策变量变化引起的目标函数的改变量和决策变量的改变量成比函数的改变量和决策变量的改变量成比例，同样，每个决策变量的变化引起约例，同样，每个决策变量的变化引起约束方程左端值的改变量和该变量的改变束方程左端值的改变量和该变量的改变量成比例。量成比例。可加性假定可加性假定：每个决策变量对目标函数：每个决策变量对目标函数和约束方程的影响是独立于其他变量的，和约束方程的影响是独立于其他变量的，目标函数值是每个决策变量对目标函数目标函数值是每个决策变量对目标函数贡献的总和。贡献的总和。线性规划问题隐含的假定：线性规划问题隐含的假定：连续性假定连续性假定：线性规划问题中的决：线性规划问题中的决策变量应
30、取连续值。策变量应取连续值。确定性假定确定性假定：线性规划问题中的所：线性规划问题中的所有参数都是确定的参数。线性规划有参数都是确定的参数。线性规划问题不包含随机因素。问题不包含随机因素。线性规划问题隐含的假定：线性规划问题隐含的假定：比例性假定比例性假定可加性假定可加性假定连续性假定连续性假定确定性假定确定性假定线性规划问题的标准形式线性规划问题的标准形式(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
31、(i=1,2,.m)线性规划问题的标准形式线性规划问题的标准形式(2)：n Max S =cjxj j=1 n s.t.aijxj=bi (i=1,2,.n)j=1 xj 0(j=1,2,.m)线性规划标准型的矩阵形式线性规划标准型的矩阵形式(3)：Max S =CX s.t.AX=b X 0 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如何将一般问题化为标准型：如何将一般问题化为标准型：若目标函数是求
32、最小值若目标函数是求最小值 Min S=CX 令令 S=-S,则则 Max S=-CX若约束条件是不等式若约束条件是不等式若约束条件是若约束条件是“”不等式不等式 n aijxj+yi=bi j=1 yi 0是非负的是非负的松驰变量松驰变量如何将一般问题化为标准型：如何将一般问题化为标准型：若约束条件是若约束条件是“”不等式不等式 n aijxj-zi =bi j=1 zi 0是非负的松驰变量是非负的松驰变量如何将一般问题化为标准型：如何将一般问题化为标准型：若约束条件右面的某一常数项若约束条件右面的某一常数项 bi=0 令令xj=xj-xj”（可正可负）可正可负）任何形式的线性规划总可以化成
33、标准型任何形式的线性规划总可以化成标准型例例1.3 将下列问题化成标准型将下列问题化成标准型:Min S =-x1+2x2-3x3s.t.x1+x2+x3 7 x1-x2+x3 2 -3x1+x2+2x3=5 x1,x2 0 x3 无非负限制无非负限制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 01-3 1-3 线性规划问题线性规划问题解的概念解的概念（二维）线性规划问题图解法：（二维）线性规划问题图解法：（1）满足约束条件的变量的值，称
34、为可）满足约束条件的变量的值，称为可行解。行解。（2）使目标函数取得最优值的可行解，）使目标函数取得最优值的可行解，称为最优解。称为最优解。例例1.1的数学模型的数学模型 max S=50 x1+30 x2 s.t.4x1+3x2 120 2x1+x2 50 x1,x2 0 x2504030201010203040 x14x1+3x2 120由由 4x1+3x2 120 x1 0 x2 0围成的区域围成的区域x2504030201010203040 x12x1+x2 50由由 2x1+x2 50 x1 0 x2 0围成的区域围成的区域x2504030201010203040 x12x1+x2
35、504x1+3x2 120可行域可行域可行域可行域同时满足：同时满足：2x1+x2 504x1+3x2 120 x1 0 x2 0的区域的区域可行域可行域x2504030201010203040 x1可行域可行域可行域可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）可行域是由约束条件围成可行域是由约束条件围成的区域，该区域内的每一的区域，该区域内的每一点都是可行解，它的全体点都是可行解，它的全体组成问题的解集合。组成问题的解集合。该问题的可行域是由该问题的可行域是由O，Q1，Q2，Q3作为顶点的作为顶点的凸多边形凸多边形x2504030201010203040 x1可行域可
36、行域可行域可行域目标函数是以目标函数是以S作为作为参数的一组平行线参数的一组平行线x2=S/30-（5/3）x1x2504030201010203040 x1可行域可行域可行域可行域当当S值不断增加时，该直线值不断增加时，该直线x2=S/30-（5/3）x1沿着其法线方向向右上方移沿着其法线方向向右上方移动。动。x2504030201010203040 x1可行域可行域可行域可行域当该直线移到当该直线移到当该直线移到当该直线移到QQ2 2点时，点时，点时，点时，S S（目标函（目标函（目标函（目标函数）值达到最大：数）值达到最大：数）值达到最大：数）值达到最大：Max S=50*15+30*2
37、0=1350此时最优解此时最优解=（15，20）Q2（15，20）二个重要结论：二个重要结论：满足约束条件的可行域一般都满足约束条件的可行域一般都构成凸多边形。这一事实可以构成凸多边形。这一事实可以推广到更多变量的场合。推广到更多变量的场合。最优解必定能在凸多边形的某最优解必定能在凸多边形的某一个顶点上取得，这一事实也一个顶点上取得，这一事实也可以推广到更多变量的场合。可以推广到更多变量的场合。解的讨论：解的讨论：最优解是唯一解最优解是唯一解；无穷多组最优解：无穷多组最优解：例例1.1的目标函数由的目标函数由 max S=50 x1+30 x2变成：变成：max S=40 x1+30 x2 s
38、.t.4x1+3x2 120 2x1+x2 50 x1,x2 0 x2504030201010203040 x1可行域可行域可行域可行域目标函数是同约束目标函数是同约束条件：条件：4x1+3x2 120平行的直线平行的直线x2=S/30-（4/3）x1x2504030201010203040 x1可行域可行域可行域可行域当当S的值增加时，目的值增加时，目标函数同约束条件：标函数同约束条件：4x1+3x2 120重合，重合，Q1与与Q2之间之间都是最优解。都是最优解。Q1（25，0）Q2（15，20）解的讨论：解的讨论：无界解：无界解：例：例：max S=x1+x2 s.t.-2x1+x2 40
39、 x1-x2 20 x1,x2 0 x2504030201010203040 x1该可行域无界，目标函该可行域无界，目标函数值可增加到无穷大，数值可增加到无穷大，称这种情况为无界解或称这种情况为无界解或无最优解。无最优解。解的讨论：解的讨论：无可行解：无可行解：例：例：max S=2x1+3x2 s.t.x1+2x2 8 x1 4 x2 3 -2x1+x2 4 x1,x2 0该问题可行域为该问题可行域为空集，即无可行空集，即无可行解，也不存在最解，也不存在最优解。优解。解的情况：解的情况：有可行解有可行解 有唯一最优解有唯一最优解 有无穷最优解有无穷最优解 无最优解无最优解无可行解无可行解1-
40、2 实例分析实例分析12000年全国大学生数模竞赛年全国大学生数模竞赛B题题2000B 2000B 钢管订购和运输钢管订购和运输由钢管厂订购钢管，经铁由钢管厂订购钢管，经铁路、公路运输，铺设一条路、公路运输，铺设一条钢管管道钢管管道A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S
41、4S5S6S7管道铁路公路S1S7 钢管厂火车站450 里程（km）（沿管道建有公路）钢厂的产量和销价（1单位钢管=1km管道钢管）钢厂产量的下限：500单位钢管1单位钢管的铁路运价1000km以上每增加1至100km运价增加5万元1单位钢管的公路运价：0.1万元/km（不足整公里部分按整公里计）（1）制定钢管的订购和运输计划，使总费用最小）制定钢管的订购和运输计划，使总费用最小.（2）分析对购运计划和总费用影响：哪个钢厂钢管销价的）分析对购运计划和总费用影响：哪个钢厂钢管销价的变化影响最大；哪个钢厂钢管产量上限的变化影响最大？变化影响最大；哪个钢厂钢管产量上限的变化影响最大？A1325801
42、010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16130A17A18A19A20A21190260100（3）讨论管道为树形图的情形）讨论管道为树形图的情形问题问题1的基本模型和解法的基本模型和解法总费用最小的优化问题总费用：订购，运输（由各厂Si经铁路、公路至各点Aj,i=1
43、,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基本模型基本模型由Aj向Aj Aj-1段铺设的运量为 1+zj=zj(zj+1)/2由Aj向Aj Aj+1段铺设的运量为 1+yj=yj(yj+1)/2二次规划求解步骤求解步骤1）求由Si至Aj的最小购运费用路线及最小费
44、用cij 难点：公路运费是里程的线性函数，而铁路运费是里程的分段阶跃函数，故总运费不具可加性。因而计算最短路常用的Dijkstra算法、Floyd算法失效。A17010881070627030202030300220210420500170690462160320160110290A10A11A12A13A14A15S4S5S6S7需要对铁路网和公路网进行预处理，才能使用常用需要对铁路网和公路网进行预处理，才能使用常用算法，得到最小购运费用路线。算法，得到最小购运费用路线。如S7至A10的最小费用路线先铁路1130km，再公路70km,运费为77（万元）先公路（经A15）40km,再铁路110
45、0km，再公路70km,运费为76（万元）实际上只有S4和S7需要分解成子问题求解 3)每个子问题是标准的二次规划，决策变量为xij,yj,zj,不超过135个。问题问题1的其它模型和解法的其它模型和解法1）运输问题的0-1规划模型将全长5171km的管道按公里分段，共5171个需求点，钢厂为7个供应点，构成如下的运输问题 cij为从供应点i到需求点j的最小购运费xij=1表示从点i到点j购运1单位钢管求解时要针对规模问题寻求改进算法2）最小费用网络流模型）最小费用网络流模型SourceS1S2S7A1A2A15P11P1l1P21Sink(si,pi)(+,cij)(1,1),(1,li)(
46、1,0)SourceS1S2S7A1A2A15P1P2Sink(si,pi)(+,cij)(li,f(f+1)/2)(li,0)线性费用网络线性费用网络(只有产量上限只有产量上限)非线性费用网络非线性费用网络(只有产量上限只有产量上限)边的标记（流量上限，单位费用）用标准算法(如最小费用路算法)求解无单位费用概念(f(f+1)/2),需修改最小费用路算法2）最小费用网络流模型）最小费用网络流模型产量有下限ri时的修正SourceSiSi(si-ri,pi)(ri,0)(+,0)得到的结果应加上 才是最小费用S1S2S3S6S5S1S2S2S3S3S5S5S63)最小面积模型A1A2A3A4A5
47、A6A7A8A9A10A11A12A13A14A15cx作图：Si到管道x单位钢管的最小购运费用c由各条Si首尾相连(横坐标)组成的一条折线对应一个购运方案，折线下面的面积对应方案的费用在产量约束下找面积最小的折线论文中发现的主要问题论文中发现的主要问题1）针对题目给的数据用凑的方法算出结果，没有解决这类问题的一般模型2）局部最优，如将管道分为左右两段，分别寻求方案；如将问题分为购运和铺设两部分，分别寻优（会导致每段管道都从两端铺到中点）4）由Si至Aj的最小购运费用路线及最小费用cij 不对5）数字结果相差较大(如最小费用应127.5至128.2亿元)问题问题2：分析对购运计划和总费用影响（
48、哪个钢厂销价：分析对购运计划和总费用影响（哪个钢厂销价的变化影响最大；哪个钢厂产量上限的变化影响最大）的变化影响最大；哪个钢厂产量上限的变化影响最大）规划问题的灵敏度分析问题问题3：管道为树形图：管道为树形图701088107062300220210170690462160320160A10A11A12S4S5S6130A17A18A19A20190260100(jk)是连接Aj,Ak的边，E是树形图的边集，ljk是(jk)的长度，yjk是由Aj沿(jk)铺设的钢管数量1-3 实例分析实例分析21998年全国大学生数模竞赛年全国大学生数模竞赛A题题投资的效益和风险投资的效益和风险(1998年全
49、国大学生数学建模竞赛年全国大学生数学建模竞赛A题题)原题还有一组 n=25的数据，现略去。问题分析问题分析优化问题决策决策每种资产的投资额（投资组合）目标目标净收益最大整体风险最小 在一定风险下收益最大的决策 在一定收益下风险最小的决策 收益和风险按一定比例组合最优的决策一组解(如在一系列风险值下收益最大的决策)二者矛盾 冒险型投资者从中选择高风险下收益最大的决策 保守型投资者则可从低风险下的决策中选取模型建立模型建立用数学符号和式子表述决策变量、构造目标函数、确定约束条件。xi i对Si(i=0,1,n)的投资,S0表示存入银行.目标函数目标函数 总收益投资Si的净收益减去交易费，对i求和
50、总体风险投资Si的风险，对i求最大值对Si的投资xi i加交易费，对i求和，不超过给定资金M.决策变量决策变量约束条件约束条件0uixicipiui1）投资Si的交易费、净收益、风险、资金表达式交易费净收益(收益率ri)风险资金(风险损失率qi)2）投资方案总收益、总体风险、资金表达式投资方案总收益总体风险资金3）两目标（总收益、总体风险）优化模型4）单目标优化模型模型简化模型简化交易费ui很小M很大资金约束设M=1投资Si的比例设M=1线性规划模型线性规划模型LP1模型模型M1的简化的简化M1模型模型M2的简化的简化M2极大极小规划模型线性规划模型线性规划模型LP2引入人工变量引入人工变量