数学建模之运筹学

数学建模之运筹学第1页，共68页，2023年，2月20日，星期六数学建模简介第2页，共68页，2023年，2月20日，星期六一般地，数学模型可以描述为，对于现实世界的一个特定对象，为了一个特定目的，根据特有的内在规律，作出一些必要的简化假设，运用适当的数学工具，得到的一个数学结构。把现实世界中的实际问题加以提炼，抽象为数学模型，求出模型的解，验证模型的合理性，并用该数学模型所提供的解答来解释现实问题，我们把数学知识的这一应用过程称为数学建模。数学模型或者能解释特定现象的现实状态，或者能预测到对象的未来状况，或者能提供处理对象的最优决策或控制。

第3页，共68页，2023年，2月20日，星期六数学模型的分类1、按模型的应用领域分类：生物数学模型医学数学模型地质数学模型数量经济学模型数学社会学模型2、按是否考虑随机因素分类：确定性模型随机性模型3、按是否考虑模型的变化分类：静态模型动态模型第4页，共68页，2023年，2月20日，星期六4、按应用离散方法或连续方法分类：离散模型连续模型5、按建立模型的数学方法分类：几何模型微分方程模型图论模型规划论模型马氏链模型第5页，共68页，2023年，2月20日，星期六6、按人们对是物发展过程的了解程度分类：（1）白箱模型：指那些内部规律比较清楚的模型。如力学、热学、电学以及相关的工程技术问题。（2）灰箱模型：指那些内部规律尚不十分清楚，在建立和改善模型方面都还不同程度地有许多工作要做的问题。如气象学、生态学经济学等领域的模型。（3）黑箱模型：指一些其内部规律还很少为人们所知的现象。如生命科学、社会科学等方面的问题。但由于因素众多、关系复杂，也可简化为灰箱模型来研究。

第6页，共68页，2023年，2月20日，星期六数学建模的几个过程

1、模型准备

2、模型假设

3、模型建立

4、模型构成

5、模型求解

6、模型分析

7、模型检验8、模型应用

第7页，共68页，2023年，2月20日，星期六模型准备了解实际背景明确建模目的搜集有关信息掌握对象特征形成一个比较清晰的‘问题’模型假设针对问题特点和建模目的作出合理的、简化的假设在合理与简化之间作出折中第8页，共68页，2023年，2月20日，星期六模型建立用数学的语言、符号描述问题发挥想像力使用类比法尽量采用简单的数学工具各种数学方法、软件和计算机技术如结果的误差分析、统计分析、模型对数据的稳定性分析模型求解模型分析第9页，共68页，2023年，2月20日，星期六模型检验

与实际现象、数据比较，检验模型的合理性、适用性模型应用第10页，共68页，2023年，2月20日，星期六数学建模有助于培养以下几个方面的素质和能力：数学素质和能力计算机应用能力论文写作能力团队合作精神和进行协调的组织能力培养想象能力发展观察力，形成洞察力勇于参与的竞争意识和不怕困难、奋力攻关的顽强意志第11页，共68页，2023年，2月20日，星期六为培养和选拔优秀的数学人才，世界各国有各种不同形式不同层次的数学竞赛.传统的数学竞赛只局限于演绎、推理等纯数学形式，它不能培养和发展学生运用数学知识解决实际问题的能力，不能满足科学技术飞速发展的时代需要.从1983年起，在美国就有一些有识之士开始探讨组织一项应用数学方面的竞赛的可能性.第12页，共68页，2023年，2月20日，星期六1985年美国第一届大学生数学建模竞赛（mathematicalcompetitioninmodeling）1988年改为mathematicalcontestinmodeling简称MCM.由美国工业与应用数学会和美国运筹学会联合举办.1985年起每年举行一届，一般在每年的二月下旬或三月初的某个星期五或星期日举行.美国竞赛评出Outstanding,Meritorious,HonorableMention及SuccessfulParticipation等级别.第13页，共68页，2023年，2月20日，星期六1989年北京的三所大学组队参加美国的MCM竞赛,此后我国的参赛队伍越来越多.1992－1993年中国工业与应用数学学会（CSIAM）举办了两次中国大学生数学建模竞赛.1994年起，由国家教委（教育部）高教司和中国工业与应用数学学会共同于每年9月举办，1999年开始设立大专组的竞赛.第14页，共68页，2023年，2月20日，星期六无论是美国还是我国大学本科组数学建模竞赛题每年都是两道，参赛队从中任选一道题目.一般来说其中一道是连续型，另一道是离散型；或者一道是开放型的，另一道是严谨型的.竞赛内容或题目是由工程技术、管理科学中的实际问题简化而成，留有充分余地供参赛者发挥其聪明才智和创造精神.竞赛形式为三名学生组成一队，可以自由地收集资料、调查研究，使用计算机、因特网和任何软件，在三天时间内分工合作完成一篇论文.评奖标准为模型假设的合理性、建模的创造性、结果的准确性和文字表述的清晰程度.第15页，共68页，2023年，2月20日，星期六初等模型第16页，共68页，2023年，2月20日，星期六一辆汽车在拐弯时急刹车，结果冲到路边的沟里（见下图），交通警察立即赶到了事故现场。司机申辩说，当他进入弯道时刹车失灵，他还一口咬定，进入弯道其车速为每小时４０英里（这是该路的速度上限，约合每秒１７.９２米）。警察验车时证实该车的制动器在事故发生时确实失灵，然而，司机所说的车速是否真实可信呢？第17页，共68页，2023年，2月20日，星期六

现在，让我们帮警察计算一下司机所报速度的真实性。连接刹车痕迹的初始点和终点，用x表示沿连线汽车横向所走出的距离，用y表示竖直的距离，如下图第18页，共68页，2023年，2月20日，星期六

上面的表中，我们给出了外侧刹车痕迹的有关值，而且，经过测量还发现，该车并没有偏离它所行驶的转弯路线，也就是说，它的车头一直指向切线方向。可以假设，该车的重心是沿一个半径为r的圆做圆周运动。假设磨擦力作用在该车速度的法线方向上，并设汽车的速度v是一个常数。显然，磨擦力提供了向心力，设磨擦系数为μ,则其中m为汽车质量.由上式易得

如何计算圆周半径r？假设已知弦的长度为c，弓形的高度为h，其图如下所示，由勾股定理知第19页，共68页，2023年，2月20日，星期六

由前面的表中代入近似数据c=33.27,h=3.55后，得r=40.75米根据实际路面与汽车轮胎的情况，可以测量出磨擦系数，经过实际测试得到g=8.175米／秒２

将此结果代入我们上面利用第二定律所得到的式子中，得v≈18.25米／秒此结果比司机所报速度（17.92米／秒）略大。但是，我们不得不考虑计算半径r及测试时的误差。如果误差允许在１０％以内，无疑，此计算结果对司机是相当有利的。

第20页，共68页，2023年，2月20日，星期六椅子能在不平的地面上放稳吗？

把四只脚的椅子往不平的地面上一放，通常只有三只脚着地，放不稳，然而有人认为只要稍挪动几次，就可以四脚着地，放稳了，对吗？第21页，共68页，2023年，2月20日，星期六问题分析

通常三只脚着地

放稳的标准:四只脚着地

四条腿一样长，椅脚与地面点接触，四脚连线呈正方形;

地面高度连续变化，可视为数学上的连续曲面;

地面相对平坦，使椅子在任意位置至少三只脚同时着地。模型假设第22页，共68页，2023年，2月20日，星期六建立模型用数学语言把椅子位置和四只脚着地的关系表示出来.

椅子位置利用正方形(椅脚连线)的对称性用(对角线与x轴的夹角)表示椅子位置

四只脚着地椅脚与地面距离为零距离是的函数xBADCOD´C´B´A´四个距离(四只脚)两个距离正方形对称性正方形ABCD绕O点旋转A,C两脚与地面距离之和记为f()B,D两脚与地面距离之和记为g()第23页，共68页，2023年，2月20日，星期六用数学语言把椅子位置和四只脚着地的关系表示出来.f(),g()是连续函数对任意,f(),g()至少一个为0数学问题已知：f(),g()是连续函数;对任意，f()•g()=0;且g(0)=0，f(0)>0.证明：存在0，使f(0)=g(0)=0.地面为连续曲面

椅子在任意位置至少三只脚着地第24页，共68页，2023年，2月20日，星期六模型求解

将椅子旋转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()的确定.

模型假设中四脚呈正方形不是本质的,读者可考虑长方形的情形.第25页，共68页，2023年，2月20日，星期六数学规划模型第26页，共68页，2023年，2月20日，星期六实际问题中的优化模型x~决策变量f(x)~目标函数gi(x)0~约束条件多元函数条件极值

决策变量个数n和约束条件个数m较大

最优解在可行域的边界上取得

重点在模型的建立和结果的分析第27页，共68页，2023年，2月20日，星期六无约束优化线性规划非线性规划整数规划多目标规划动态规划等等第28页，共68页，2023年，2月20日，星期六线性规划第29页，共68页，2023年，2月20日，星期六设每月生产小、中、大型汽车的数量分别为x1,x2,x3汽车厂生产计划

模型建立

小型中型大型现有量钢材1.535600时间28025040060000利润234线性规划模型(LP)第30页，共68页，2023年，2月20日，星期六模型求解

3）

模型中增加条件：x1,x2,x3

均为整数，重新求解。

OBJECTIVEFUNCTIONVALUE1)632.2581VARIABLEVALUEREDUCEDCOST

X164.516129

0.000000

X2167.741928

0.000000

X30.0000000.946237ROWSLACKORSURPLUSDUALPRICES2)0.0000000.7311833)0.0000000.0032261）舍去小数：取x1=64，x2=167，算出目标函数值z=629，与LP最优值632.2581相差不大。2）试探：如取x1=65，x2=167；x1=64，x2=168等，计算函数值z，通过比较可能得到更优的解。但必须检验它们是否满足约束条件。为什么？结果为小数，怎么办？第31页，共68页，2023年，2月20日，星期六IP可用LINDO直接求解整数规划(IntegerProgramming,简记IP)“gin3”表示“前3个变量为整数”，等价于：ginx1ginx2ginx3IP的最优解x1=64，x2=168，x3=0，最优值z=632

max2x1+3x2+4x3st1.5x1+3x2+5x3<600280x1+250x2+400x3<60000endgin3OBJECTIVEFUNCTIONVALUE1)632.0000VARIABLEVALUEREDUCEDCOSTX164.000000-2.000000X2168.000000-3.000000X30.000000-4.000000

模型求解

IP结果输出第32页，共68页，2023年，2月20日，星期六其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：方法1：分解为8个LP子模型

汽车厂生产计划若生产某类汽车，则至少生产80辆，求生产计划。x1,x2,,x3=0或80x1=80，x2=150，x3=0，最优值z=610第33页，共68页，2023年，2月20日，星期六LINDO中对0-1变量的限定：inty1inty2inty3方法2：引入0-1变量，化为整数规划

M为大的正数，可取1000OBJECTIVEFUNCTIONVALUE1)610.0000VARIABLEVALUEREDUCEDCOST

X180.000000

-2.000000

X2150.000000-3.000000

X30.000000

-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000

若生产某类汽车，则至少生产80辆，求生产计划。x1=0或

80x2=0或

80x3=0或

80最优解同前

第34页，共68页，2023年，2月20日，星期六NLP虽然可用现成的数学软件求解(如LINGO,MATLAB)，但是其结果常依赖于初值的选择。

方法3：化为非线性规划

非线性规划（Non-LinearProgramming，简记NLP）

实践表明，本例仅当初值非常接近上面方法算出的最优解时，才能得到正确的结果。

若生产某类汽车，则至少生产80辆，求生产计划。x1=0或

80x2=0或

80x3=0或

80第35页，共68页，2023年，2月20日，星期六非线性规划第36页，共68页，2023年，2月20日，星期六

某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a,b表示，距离单位：千米）及水泥用量d（吨）如下：123456abd1.251.2538.750.7550.54.7545.755736.567.257.2511

为保障供应，需建两个料场，日储量各为20吨，问应建在何处，使总的吨千米数最小，并试制定每天的供应计划.第37页，共68页，2023年，2月20日，星期六一个有约束条件的非线性规划问题的解法大致分为：①

用线性规划、二次规划来逐步逼近非线性规划的方法；②

对约束非线性规划问题不预先作转换的直接求解方法，如随机试验法等；③

对约束非线性规划问题不预先作转换，直接进行处理的分析方法，如可行方向法、凸单纯形法等；④

把约束非线性规划问题转换为无约束非线性规划来求解的方法，如SUMT外点法、SUMT内点法、乘子法等。第38页，共68页，2023年，2月20日，星期六整数规划第39页，共68页，2023年，2月20日，星期六为了选修课程门数最少，应学习哪些课程？

选课策略选修课程最少，且学分尽量多，应学习哪些课程？

课号课名学分所属类别先修课要求1微积分5数学

2线性代数4数学

3最优化方法4数学；运筹学微积分；线性代数4数据结构3数学；计算机计算机编程5应用统计4数学；运筹学微积分；线性代数6计算机模拟3计算机；运筹学计算机编程7计算机编程2计算机

8预测理论2运筹学应用统计9数学实验3运筹学；计算机微积分；线性代数第40页，共68页，2023年，2月20日，星期六0-1规划模型

决策变量

目标函数

xi=1~选修课号i的课程（xi=0~不选）

选修课程总数最少

约束条件课号课名所属类别1微积分数学2线性代数数学3最优化方法数学；运筹学4数据结构数学；计算机5应用统计数学；运筹学6计算机模拟计算机；运筹学7计算机编程计算机8预测理论运筹学9数学实验运筹学；计算机最少2门数学课，3门运筹学课，2门计算机课。

第41页，共68页，2023年，2月20日，星期六先修课程要求最优解：

x1=x2=x3=x6=x7=x9=1,其它为0；6门课程，总学分210-1规划模型

约束条件x3=1必有x1=x2=1模型求解（LINDO）课号课名先修课要求1微积分

2线性代数

3最优化方法微积分；线性代数4数据结构计算机编程5应用统计微积分；线性代数6计算机模拟计算机编程7计算机编程

8预测理论应用统计9数学实验微积分；线性代数第42页，共68页，2023年，2月20日，星期六学分最多多目标优化的处理方法：化成单目标优化。两目标(多目标)规划

讨论：选修课程最少，学分尽量多，应学习哪些课程？

课程最少

以学分最多为目标，不管课程多少。

以课程最少为目标，不管学分多少。最优解如上，6门课程，总学分21。最优解显然是选修所有9门课程。第43页，共68页，2023年，2月20日，星期六多目标规划

在课程最少的前提下以学分最多为目标。注意：最优解不唯一！课号课名学分1微积分52线性代数43最优化方法44数据结构35应用统计46计算机模拟37计算机编程28预测理论29数学实验3LINDO无法告诉优化问题的解是否唯一。可将x9=1易为x6=1增加约束，以学分最多为目标求解。最优解：

x1=x2=x3=x5=x7=x9=1,

其它为0；总学分由21增至22。第44页，共68页，2023年，2月20日，星期六多目标规划

对学分数和课程数加权形成一个目标，如三七开。课号课名学分1微积分52线性代数43最优化方法44数据结构35应用统计46计算机模拟37计算机编程28预测理论29数学实验3最优解：

x1=x2=x3=x4=x5=x6=x7=x9=1，其它为0