运筹学模型与数学建模竞赛.doc

《运筹学模型与数学建模竞赛.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、运筹学模型与数学建模竞赛一、引言一般来说，大学生数学建模竞赛所涉及到的运筹学模型包括数学规划（线性规划和非线性规划），网络优化（含网络计划技术），排队模型，动态规划等，请看下表年份题号题名模型分类1994A逢山开路网络优化1995A一个飞行管理问题数学规划1995B天车与冶炼炉的作业调度网络计划技术1996A最优捕鱼策略涉及数学规划1996B节水吸引机涉及动态规划1997A零件的参数设计数学规划1997B横断切割涉及数学规划或网络优化1998A投资的收益和风险数学规划1998B灾情巡视路线网络优化1999B钻井布局数学规划2000B钢管的订购和运输数学规划和网络优化2001B公交车调度

2、数学规划2002A车灯线光源的优化设计涉及数学规划2003B露天矿生产的车辆安排数学规划2004A奥运场馆的设计涉及数学规划2004B电力市场的输电阻塞管理涉及数学规划注：从1999年起，全国大学生数学建模竞赛开始设置专供大专院校学生做的C，D题。下面重点介绍运筹学模型的数学规划。二、数学规划的一般形式线性规划：整数规划：非线性规划：三、数学规划问题举例1下料问题现要用100×50厘米的板料裁剪出规格分别为40×40厘米与50×20厘米的零件，前者需要25件，后者需要30件。问如何裁剪，才能最省料？解：先设计几个裁剪方案记A---------40×40；B-----------50×2

3、0方案1AAB//////////////////////////////方案2ABBB//////////////方案3BBBBB注：还有别的方案吗？显然，若只用其中一个方案，都不是最省料的方法。最佳方法应是三个方案的优化组合。设方案i使用原材料xi件(i=1,2,3)。共用原材料f件。则根据题意，可用如下数学式子表示：这是一个整数线性规划模型。2运输问题现要从两个仓库（发点）运送库存原棉来满足三个纺织厂（收点）的需要，数据如下表，试问在保证各纺织厂的需求都得到满足的条件下应采取哪个运输方案，才能使总运费达到最小？（运价（元/吨）如下表）工厂j仓库i1号2号3号库存量（吨）1号2号2

4、212345030需求量（吨）401525解：题意即要确定从i号仓库运到j号工厂的原棉数量。故设表示从i号仓运到j号工厂的原棉数量（吨）f表示总运费.则运输模型为：一般地，对于有m个发点和n个收点的运输模型为其中ai为i号发点的运出量，bj为j号收点的需求量，cij为从i号发点到j号收点的单位运价。特别当时，存货必须全部运走，故上述约束条件中的可改为等式：3选址问题某地区有m座煤矿，i#矿每年产量为ai吨，现有火力发电厂一个，每年需用煤b0吨，每年运行的固定费用（包括折旧费，但不包括煤的运费）为h0元。现规划新建一个发电厂，m座煤矿每年开采的原煤将全部供给这两个电厂发电用。现有n个备选

5、的厂址。若在j#备选厂址建电厂，每年运行的固定费用为hj元，每吨原煤从i#矿运送到j#备选厂址的运费为cij元(i=1,2,…m,j=1,2…n)。每吨原煤从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备选厂址年产量12┄j┄n12┄┄

6、┄m年需求量(2)目标函数的表达总运费：（对不被选中的备选厂址运费xij,将由约束条件限制为0）.固定费用h0+每年总费用z=(3)约束条件的表达（i）煤矿产量约束（ii）旧电厂用煤量约束（iii）新电厂用煤量约束记，当j#备选厂址被选中时，当j#备选厂址没被选中时，综合表达为（iv）选址约束由于只选一个厂址，所以(v)非负及整数约束综合得数学规划模型：4布点问题某市有6个区，每个区都可建消防站，为了节省开支，市政府希望设置的消防站最少，但必须保证在该市任何地区发生火警时，消防车能在15分钟赶到现场。假定各区的消防站要建的话,就建在区的中心，根据实地测量,各区之间消防车行使的最长时间如

7、下表:(单位:分钟)1区2区3区4区5区6区1区410162827202区105243217103区162441227214区283212515255区271727153146区20102125146请你为该市制定一个设置消防站的最节省的计划。建模并求解。解：本题实际上是要确定各个区是否要建立消防站，使其既满足要求，又最节省。这自然可引入0-1变量，故设目标是最少。以下考虑约束条件。若1区发生火警，按照“消防车要在15分钟赶到现场”的要求，则l