《运筹学模型与数学建模竞赛.doc》由会员分享，可在线阅读，更多相关《运筹学模型与数学建模竞赛.doc（18页珍藏版）》请在金锄头文库上搜索。
1、运筹学模型与数学建模竞赛一、引言一般来说，大学生数学建模竞赛所涉及到的运筹学模型包括数学规划（线性规划和非线性规划），网络优化（含网络计划技术），排队模型，动态规划等，请看下表年份题号题名模型分类1994A逢山开路网络优化1995A一个飞行管理问题数学规划1995B天车与冶炼炉的作业调度网络计划技术1996A最优捕鱼策略涉及数学规划1996B节水吸引机涉及动态规划1997A零件的参数设计数学规划1997B横断切割涉及数学规划或网络优化1998A投资的收益和风险数学规划1998B灾情巡视路线网络优化1999B钻井布局数学规划2000B钢管的订购和运输数学规划和网络优化2001B公交车调度数学规划
2、2002A车灯线光源的优化设计涉及数学规划2003B露天矿生产的车辆安排数学规划2004A奥运场馆的设计涉及数学规划2004B电力市场的输电阻塞管理涉及数学规划注：从1999年起，全国大学生数学建模竞赛开始设置专供大专院校学生做的C，D题。下面重点介绍运筹学模型的数学规划。二、数学规划的一般形式线性规划：整数规划：非线性规划：三、数学规划问题举例1 下料问题现要用10050厘米的板料裁剪出规格分别为4040 厘米与5020厘米的零件，前者需要25件，后者需要30件。问如何裁剪，才能最省料？解：先设计几个裁剪方案记 A-4040；B-5020方案1AAB/方案2ABBB/方案3BBBBB注：还有
3、别的方案吗？显然，若只用其中一个方案，都不是最省料的方法。最佳方法应是三个方案的优化组合。设方案i使用原材料xi件(i=1,2,3)。共用原材料f件。则根据题意，可用如下数学式子表示：这是一个整数线性规划模型。2 运输问题现要从两个仓库（发点）运送库存原棉来满足三个纺织厂（收点）的需要，数据如下表，试问在保证各纺织厂的需求都得到满足的条件下应采取哪个运输方案，才能使总运费达到最小？（运价（元/吨）如下表）工厂 j仓库i1号2号3号库存量（吨）1号2号2212345030需求量（吨）401525解：题意即要确定从i号仓库运到j号工厂的原棉数量。故设表示从i号仓运到j号工厂的原棉数量（吨）f表示总
4、运费.则运输模型为：一般地，对于有m个发点和n个收点的运输模型为其中ai为i号发点的运出量，bj为j号收点的需求量，cij为从i号发点到j号收点的单位运价。特别当时，存货必须全部运走，故上述约束条件中的可改为等式：3 选址问题某地区有m座煤矿，i# 矿每年产量为ai 吨，现有火力发电厂一个，每年需用煤b0吨，每年运行的固定费用（包括折旧费，但不包括煤的运费）为h0元。现规划新建一个发电厂，m座煤矿每年开采的原煤将全部供给这两个电厂发电用。现有n个备选的厂址。若在j#备选厂址建电厂，每年运行的固定费用为hj元，每吨原煤从i# 矿运送到j#备选厂址的运费为cij元(i=1,2,m, j=1,2n)
5、。每吨原煤从i# 矿运送到原有电厂的运费为ci0 (i=1,2,m)。试问：1 应把新电厂厂址选在何处？2 m座煤矿开采的原煤应如何分配给两个电厂？才能使每年的总费用（电厂运行的固定费用与原煤运费之和）为最小？模型的建立(1) 变量的设置为了解决问题1，我们使用0-1变量为了解决问题2，设从i#煤矿运到j#备选的厂址的运量为xij吨（i=1,2,m，j=0,1,2,n）备选厂址j煤矿i现有电厂 0备 选 厂 址年产量12jn12m年需求量(2)目标函数的表达总运费：（对不被选中的备选厂址运费xij,将由约束条件限制为0）.固定费用 h0+每年总费用 z =(3)约束条件的表达（i）煤矿产量约束
6、 （ii）旧电厂用煤量约束 （iii）新电厂用煤量约束 记 ，当j#备选厂址被选中时，当j#备选厂址没被选中时，综合表达为（iv）选址约束 由于只选一个厂址，所以 (v)非负及整数约束 综合得数学规划模型：4布点问题某市有6个区，每个区都可建消防站，为了节省开支，市政府希望设置的消防站最少，但必须保证在该市任何地区发生火警时，消防车能在15分钟内赶到现场。假定各区的消防站要建的话,就建在区的中心，根据实地测量,各区之间消防车行使的最长时间如下表:(单位:分钟)1区2区3区4区5区6区1区410162827202区105243217103区162441227214区283212515255区27
7、1727153146区20102125146请你为该市制定一个设置消防站的最节省的计划。建模并求解。解：本题实际上是要确定各个区是否要建立消防站，使其既满足要求，又最节省。这自然可引入0-1变量，故设目标是最少。以下考虑约束条件。若1区发生火警，按照“消防车要在15分钟内赶到现场”的要求，则l区和2区至少应有一个消防站，即。同理得：从而得模型为：再仔细观察知，若满足第一、三个约束条件，则必然满足第二、四个约束条件，故后者是多余的，可省略。从而化简得：此模型当然可用软件求解，但由于比较简单,故可直接试算。若要求只有一个，则显然不可行；若要求只有两个，则有唯一可行解，故这就是最优解，即只需在2区和
8、4区建立消防站。附程序：c=1 1 1 1 1 1a=-1 1 0 0 0 0;0 0 1 1 0 0;0 0 0 1 1 1;0 1 0 0 1 1b=-1 1 1 1v=zeros(1,6)u=1 1 1 1 1 1x fval=linprog(c,a,b,v,u)Optimization terminated.x = 0.0000 1.0000 0.0000 1.0000 0.0000 0.0000fval = 2.00005 配套问题设有n个车间要生产m种产品，第j车间每天生产第i种产品至多aij 件（即全天只安排生产产品i而不安排生产其他产品时的最大产量），假设这m种产品每种一件配成
9、一套，问如何安排生产任务才能使生产出的成套产品最多？（i=1,2,.,m； j=1,2,.,n）（1） 建模方法（一）设xij车间j安排用于生产产品i的数量，Z每天生产的成套产品数目，车间j产品i12jn全厂生产产品I的数量12i全厂每天生产产品I的总量m车间j每天生产产品I的总量车间j每天生产产品I的总量原问题可以转化为以下数学模型：模型改进为：模型问题：没有将一天的生产时间约束考虑到！2、建模方法（二）设 xij 车间j安排用于生产产品i的时间（占全天的比例）Z每天生产的成套产品数目则aijxij车间j每天生产产品i的数目。例如：车间2每天至多生产某产品6件，若安排1/3天时间去生产，则可
10、产出2件），而每天全厂产出产品i的总量。车间j产品i12jn全厂生产产品I的数量12i全厂每天生产产品I的总量m车间j每天生产产品I的总量车间j每天生产产品I的总量于是则有模型max Z ( )(*) 其中常数1表示1天。注：(1)此模型着重考虑安排生产的时间；(2)从实际情况考虑，安排生产的时间必须是每件产品耗用生产时间的整数倍才合适。例如，每3分钟生产一件产品，安排5分钟，也只能生产1件，不能认为生产了1.67件。模型（*）没有考虑到这些因素，故是不合适的。（2）建模方法（二）改进（*）显然，车间j生产每件产品i的耗用时间（天）。从以上分析应有 (?是非负整数)从而令 yij=aijxij
11、 , yij是非负整数,表示车间j 每天生产产品i的数目，将它代入（*）后得max Z(*) 这是一个整数线性规划模型。注：此模型着重考虑安排生产产品的数目。四、数学规划在数学建模中的应用举例1 钻井布局勘探部门在某地区找矿。初步勘探时期已零散地在若干位置上钻井，取得了地质资料。进入系统勘探时期后，要在一个区域内按纵横等距的网格点来布置井位，进行“撒网式”全面钻探。由于钻一口井的费用很高，如果新设计的井位与原有井位重合（或相当接近），便可利用旧井的地质资料，不必打这口新井。因此，应该尽量利用旧井，少打新井，以节约钻探费用。比如钻一口新井的费用为500万元，利用旧井资料的费用为10万元，则利用一
12、口旧井就节约费用490万元.设平面上有n个点Pi，其坐标为(ai,bi),i=1,2,n，表示已有的n个井位。新布置的井位是一个正方形网格N的所有结点（所谓“正方形网格”是指每个格子都是正方形的网格；结点是指纵线和横线的交叉点）。假定每个格子的边长（井位的纵横间距）都是1单位（比如100米）。整个网格是可以在平面上任意移动的。若一个已知点Pi与某个网格结点Xi的距离不超过给定误差（=0.05单位），则认为Pi处的旧井资料可以利用，不必在结点Xi处打新井。 为进行辅助决策，勘探部门要求我们研究如下问题： 1)假定网格的横向和纵向是固定的（比如东西向和南北向），并规定两点间的距离为其横向距离（横坐标之差绝对值）及纵向距离（纵坐标之差绝对值）的最大值。在平面上平行移动网格N，使可利用的旧井数尽可能大。试提供数值计算方法，并对下面的数值例子用计算机进行计算。 2)在欧氏距离的误差意义下，考虑网格的横向和纵向不固定（可以旋转）的情形，给出算法及计
