数学建模与数学规划.

第一讲数学建模简介及数学规划模型Page1of68数学建模的几个过程1、模型准备2、模型假设3、模型建立4、模型构成5、模型求解6、模型分析7、模型检验8、模型应用第一讲数学建模简介及数学规划模型Page2of68模型准备了解实际背景明确建模目的搜集有关信息掌握对象特征形成一个比较清晰的‘问题’模型假设针对问题特点和建模目的作出合理的、简化的假设在合理与简化之间作出折中第一讲数学建模简介及数学规划模型Page3of68模型建立用数学的语言、符号描述问题发挥想像力使用类比法尽量采用简单的数学工具各种数学方法、软件和计算机技术如结果的误差分析、统计分析、模型对数据的稳定性分析模型求解模型分析第一讲数学建模简介及数学规划模型Page4of68模型检验与实际现象、数据比较，检验模型的合理性、适用性模型应用第一讲数学建模简介及数学规划模型Page5of68数学规划模型第一讲数学建模简介及数学规划模型Page6of68实际问题中的优化模型mixgtsxxxxfzMaxMiniTn,2,1,0)(..),(),()(1或x~决策变量f(x)~目标函数gi(x)0~约束条件多元函数条件极值决策变量个数n和约束条件个数m较大最优解在可行域的边界上取得重点在模型的建立和结果的分析第一讲数学建模简介及数学规划模型Page7of68•无约束优化•线性规划•非线性规划•整数规划•多目标规划•动态规划等等第一讲数学建模简介及数学规划模型Page8of68线性规划第一讲数学建模简介及数学规划模型Page9of68设每月生产小、中、大型汽车的数量分别为x1,x2,x3321432xxxzMax600535.1..321xxxts60000400250280321xxx0,,321xxx汽车厂生产计划模型建立小型中型大型现有量钢材1.535600时间28025040060000利润234线性规划模型(LP)第一讲数学建模简介及数学规划模型Page10of68模型求解3）模型中增加条件：x1,x2,x3均为整数，重新求解。OBJECTIVEFUNCTIONVALUE1)632.2581VARIABLEVALUEREDUCEDCOSTX164.5161290.000000X2167.7419280.000000X30.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，通过比较可能得到更优的解。•但必须检验它们是否满足约束条件。为什么？结果为小数，怎么办？IP可用LINDO直接求解整数规划(IntegerProgramming,简记IP)“gin3”表示“前3个变量为整数”，等价于：ginx1ginx2ginx3IP的最优解x1=64，x2=168，x3=0，最优值z=632max2x1+3x2+4x3st1.5x1+3x2+5x3600280x1+250x2+400x360000endgin3OBJECTIVEFUNCTIONVALUE1)632.0000VARIABLEVALUEREDUCEDCOSTX164.000000-2.000000X2168.000000-3.000000X30.000000-4.000000321432xxxzMax600535.1..321xxxts60000400250280321xxx为非负整数321,,xxx模型求解IP结果输出其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：80,0,0321xxx0,80,0321xxx80,80,0321xxx0,0,80321xxx0,80,80321xxx80,0,80321xxx80,80,80321xxx0,,321xxx方法1：分解为8个LP子模型汽车厂生产计划•若生产某类汽车，则至少生产80辆，求生产计划。321432xxxzMax600535.1..321xxxts60000400250280321xxxx1,x2,,x3=0或80x1=80，x2=150，x3=0，最优值z=610LINDO中对0-1变量的限定：inty1inty2inty3方法2：引入0-1变量，化为整数规划M为大的正数，可取1000OBJECTIVEFUNCTIONVALUE1)610.0000VARIABLEVALUEREDUCEDCOSTX180.000000-2.000000X2150.000000-3.000000X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000•若生产某类汽车，则至少生产80辆，求生产计划。x1=0或80x2=0或80x3=0或80}1,0{,80,11111yyxMyx}1,0{,80,22222yyxMyx}1,0{,80,33333yyxMyx最优解同前NLP虽然可用现成的数学软件求解(如LINGO,MATLAB)，但是其结果常依赖于初值的选择。方法3：化为非线性规划非线性规划（Non-LinearProgramming，简记NLP）实践表明，本例仅当初值非常接近上面方法算出的最优解时，才能得到正确的结果。•若生产某类汽车，则至少生产80辆，求生产计划。x1=0或80x2=0或80x3=0或800)80(11xx0)80(22xx0)80(33xx第一讲数学建模简介及数学规划模型Page15of68非线性规划第一讲数学建模简介及数学规划模型Page16of68某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a,b表示，距离单位：千米）及水泥用量d（吨）如下：123456abd1.251.2538.750.7550.54.7545.755736.567.257.2511为保障供应，需建两个料场，日储量各为20吨，问应建在何处，使总的吨千米数最小，并试制定每天的供应计划.第一讲数学建模简介及数学规划模型Page17of68•一个有约束条件的非线性规划问题的解法大致分为：•①用线性规划、二次规划来逐步逼近非线性规划的方法；•②对约束非线性规划问题不预先作转换的直接求解方法，如随机试验法等；•③对约束非线性规划问题不预先作转换，直接进行处理的分析方法，如可行方向法、凸单纯形法等；•④把约束非线性规划问题转换为无约束非线性规划来求解的方法，如SUMT外点法、SUMT内点法、乘子法等。第一讲数学建模简介及数学规划模型Page18of68整数规划为了选修课程门数最少，应学习哪些课程？选课策略选修课程最少，且学分尽量多，应学习哪些课程？课号课名学分所属类别先修课要求1微积分5数学2线性代数4数学3最优化方法4数学；运筹学微积分；线性代数4数据结构3数学；计算机计算机编程5应用统计4数学；运筹学微积分；线性代数6计算机模拟3计算机；运筹学计算机编程7计算机编程2计算机8预测理论2运筹学应用统计9数学实验3运筹学；计算机微积分；线性代数0-1规划模型决策变量目标函数xi=1~选修课号i的课程（xi=0~不选）91iixZMin选修课程总数最少约束条件254321xxxxx398653xxxxx29764xxxx课号课名所属类别1微积分数学2线性代数数学3最优化方法数学；运筹学4数据结构数学；计算机5应用统计数学；运筹学6计算机模拟计算机；运筹学7计算机编程计算机8预测理论运筹学9数学实验运筹学；计算机最少2门数学课，3门运筹学课，2门计算机课。先修课程要求74xx02215xxx076xx058xx02219xxx最优解：x1=x2=x3=x6=x7=x9=1,其它为0；6门课程，总学分2102213xxx0-1规划模型约束条件x3=1必有x1=x2=12313,xxxx模型求解（LINDO）课号课名先修课要求1微积分2线性代数3最优化方法微积分；线性代数4数据结构计算机编程5应用统计微积分；线性代数6计算机模拟计算机编程7计算机编程8预测理论应用统计9数学实验微积分；线性代数学分最多多目标优化的处理方法：化成单目标优化。两目标(多目标)规划987654321322343445xxxxxxxxxWMax},{WZMin讨论：选修课程最少，学分尽量多，应学习哪些课程？91iixZMin课程最少•以学分最多为目标，不管课程多少。•以课程最少为目标，不管学分多少。最优解如上，6门课程，总学分21。最优解显然是选修所有9门课程。第一讲数学建模简介及数学规划模型Page23of68多目标规划•在课程最少的前提下以学分最多为目标。注意：最优解不唯一！课号课名学分1微积分52线性代数43最优化方法44数据结构35应用统计46计算机模拟37计算机编程28预测理论29数学实验3LINDO无法告诉优化问题的解是否唯一。可将x9=1易为x6=1增加约束，以学分最多为目标求解。691iix最优解：x1=x2=x3=x5=x7=x9=1,其它为0；总学分由21增至22。第一讲数学建模简介及数学规划模型Page24of68多目标规划•对学分数和课程数加权形成一个目标，如三七开。987654321322343445xxxxxxxxxW91iixZWZWZYMin3.07.021课号课名学分1微积分52线性代数43最优化方法44数据结构35应用统计46计算机模拟37计算机编程28预测理论29数学实验3最优解：x1=x2=x3=x4=x5=x6=x7=x9=1，其它为0；总学分28。第一讲数学建模简介及数学规划模型Page25of68讨论与思考WZYMin213/211,0,12121最优解与1=0，2=1的结果相同——学分最多4/31多目标规划987654321322343445xxxxxxxxxW91iixZ最优解与1=1，2=0的结果相同——课程最少第一讲数学建模简介及数学规划模型Page26of68多目标规划模型第一讲数学建模简介及数学规划模型Page27of68在许多客观实际问题中，要达到的目标往往不止一个。例如，设计导弹时既要使其射程最远，有要燃料最省，还要精度最高。这类含有多个目标的优化问题称为多目标规划问题。第一讲数学建模简介及数学规划模型Page28of68设市场上有香蕉、苹果、葡萄三种水果，其单价分别为4.2元/千克，2.4元/千克，2.2元/千克。现在某单位要筹办一次节日茶话会，要求用于买的水果不少于10千克，香蕉、苹果的总和不少于6千克，问如何确定最好的购买方案。第一讲数学建模简介及数学规划模型Page29of68设1x,2x,3x分别为购买香蕉、苹果、葡萄三种水果的重量（千克）。用于买水果的总钱数为1y,所买的水果的总量为2y，自然，我们希望1y取最小值，2y取最大值。约束条件为0610302.24.22.421321321ixxxxxxxxxi=1,2,3并使min2.24.22.43211xxxymax3212xxxy易见，这是一个包含两个目标),(21yy的LP问题，称为多目标LP问题。求解多目标规划问题的方法有约束法、分层序列法、加权求和法及理想点法等，有兴趣的读者可参考有关书籍。第一讲数学建模简介及数学规划模型Page30of68目标规划模型第一讲数学建模简介及数学规划模型Page31of68目