数学建模培训之数学规划模型

《数学建模培训之数学规划模型》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学建模MathematicalModelling第一讲数学规划模型优化问题：现实世界当中经常遇到的一类问题。最优化方法：解决优化问题的数学方法。解决优化问题的基本步骤：1)建立优化模型;2)利用优化方法辅以计算机求解优化模型。优化模型：1)数学规划：线性规划非线性规划整数规划动态规划多目标规划生产与服务业的运作管理：计划问题、调度问题、运输问题、下料问题，…经济与金融领域：经济均衡问题、投资组合问题、市场营销问题，…2)图与网络的优化模型运输问题指派问题最大匹配问题最小覆盖问题最短路问题最小树问题行遍性问题(旅行商问题/中国邮递员问题)网络流问题(最大流/最小费用流)计

2、划网络图优化问题3)对策论（博弈论）4)排队论5)存贮论参考书：▲运筹学(第3版)，《运筹学》教材编写组编，清华大学出版社,2005▲优化建模与LINDO/LINGO软件，谢金星、薛毅编著，清华大学出版社,2006例1某公司的甲、乙两个蔬菜生产基地，产量分别为1200kg和900kg，同时供应A、B、C、D四个大型超市，其需要量分别为800kg、500kg、500kg、300kg，而从各基地到各超市运送蔬菜的费用为：试制定一个调运方案，使总的运费最小.运费(元/kg)ABCD甲基地0.210.250.170.15乙基地0.470.370.160.28例2某食品厂有n种产品

3、A1,A2,…,An，每种产品的单位利润分别为r1,r2,…,rn.而生产每种产品所需设备数分别为a1,a2,…,an，所需原料的消耗分别为b1,b2,…,bn，所需劳动力分别为c1,c2,…,cn.该厂现有的设备、原料和劳动力的总数分别为a,b,c，产品在市场上的需求量分别不超过q1,q2,…,qn.该厂若要获得最大利润，应如何制定生产计划？数学规划(MathematicalProgramming)例3.某加工厂制作一批钢架，需50根4m，20根6m和15根8m的同型号钢管，而从钢管厂购进的该型号的原料钢管长度均为19m.问应如何下料能最节省？例4.某建筑公司有6个工地

4、同时开工，每个工地的位置(用平面坐标系(ai,bi)表示，距离单位:km)及水泥日用量di(单位:t)为i123456aibidi1.258.750.505.753.007.251.250.754.755.006.507.253547611目前位于A(5,1)和B(2,7)处有两个临时料场，日储量各20t.假定从料场到各工地均为直线道路.(1)对A,B两料场，制定每天的供应计划，使总的吨千米数最小；(2)舍弃A,B两料场，修建两个新料场，日储量不变，问应建于何处？总的吨千米数减少了多少？线性规划(LinearProgramming,LP)其中c=(c1,…,cn)T,x=

5、(x1,…,xn)T，b=(b1,…,bm)T.标准形线性规划的求解5x1+4x2=24Q2Q1Q3Q42x1+5x2=15x2-x1=1Ox1x25x1+10x2=z例1线性规划的基本性质（1）若LP存在可行域，则其可行域为凸集（凸多面体）；（2）x为LP的基可行解的充分必要条件是x为其可行域的极点（顶点）；（3）若LP存在最优解，则其最优解一定在其可行域的极点上得到。求解线性规划：（1）求基可行解（可行域的极点）；（2）在基可行解中寻找最优解。单纯形算法从某个基可行解出发，通过迭代法沿目标函数值下降最快的方向求另一个基可行解。经有限次迭代，便可得到LP的最优解。Q2Q

6、1Q3Q45x1+10x2=z5x1+4x2=24Ox1x22x1+5x2=15x2-x1=1••••••••••••，x1,x2为整数整数规划(IntegerProgramming,IP)数学规划其中x=(x1,…,xn)T,g(x)=(g1(x),…,gm(x))T,而S={x

7、g(x)0}Rn为该数学规划的可行域。非线性规划(NonlinearProgramming,NLP)或设x*S，而xS有f(x)f(x*)，则称x*为NLP的全局最优解，f(x*)为NLP的全局最优值(全局极小值)。非线性规划设x*S，若U(x*)使xU(x*)∩S，有f(

8、x)f(x*)，则称x*为NLP的局部最优解，f(x*)为NLP的局部最优值(局部极小值)。设SRn，x*S，f(x)在x*处取得局部极值的必要条件为f(x*)==0；f(x)在x*处取得局部极小值的充分条件为f(x*)=0，且2f(x*)=正定。数值迭代法无约束NLP的求解Step2对于第k次迭代解x(k)，确定一个搜索方向p(k)Rn，并在此方向上确定搜索步长tkR，令x(k+1)=x(k)+tkp(k)，使f(x(k+1))f(x(k))；若可行域S=Rn：无约束NLP；否则SRn：带约束NLP。St