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

1运筹学模型与数学建模竞赛一、引言一般来说，大学生数学建模竞赛所涉及到的运筹学模型包括数学规划（线性规划和非线性规划），网络优化（含网络计划技术），排队模型，动态规划等，请看下表年份题号题名模型分类1994A逢山开路网络优化1995A一个飞行管理问题数学规划1995B天车与冶炼炉的作业调度网络计划技术1996A最优捕鱼策略涉及数学规划1996B节水吸引机涉及动态规划1997A零件的参数设计数学规划1997B横断切割涉及数学规划或网络优化1998A投资的收益和风险数学规划1998B灾情巡视路线网络优化1999B钻井布局数学规划2000B钢管的订购和运输数学规划和网络优化2001B公交车调度数学规划2002A车灯线光源的优化设计涉及数学规划2003B露天矿生产的车辆安排数学规划2004A奥运场馆的设计涉及数学规划2004B电力市场的输电阻塞管理涉及数学规划注：从1999年起，全国大学生数学建模竞赛开始设置专供大专院校学生做的C，D题。下面重点介绍运筹学模型的数学规划。二、数学规划的一般形式))(max()(minxforxfubxlbmjxglixhtsji,,2,1,0)(,,2,1,0)(..线性规划：整数规划：非线性规划：三、数学规划问题举例1下料问题现要用100×50厘米的板料裁剪出规格分别为40×40厘米与50×20厘米的零件，前者需要25件，后者需要30件。问如何裁剪，才能最省料？2解：先设计几个裁剪方案记A---------40×40；B-----------50×20AAB//////////////////////////////ABBB//////////////BBBBB注：还有别的方案吗？显然，若只用其中一个方案，都不是最省料的方法。最佳方法应是三个方案的优化组合。设方案i使用原材料xi件(i=1,2,3)。共用原材料f件。则根据题意，可用如下数学式子表示：)3,2,1(03053252..min32121321jxxxxxxtsxxxfj，整数这是一个整数线性规划模型。2运输问题现要从两个仓库（发点）运送库存原棉来满足三个纺织厂（收点）的需要，数据如下表，试问在保证各纺织厂的需求都得到满足的条件下应采取哪个运输方案，才能使总运费达到最小？（运价（元/吨）如下表）工厂j仓库i1号2号3号库存量（吨）1号2号2212345030需求量（吨）401525方案1方案2方案33解：题意即要确定从i号仓库运到j号工厂的原棉数量。故设ijx表示从i号仓运到j号工厂的原棉数量（吨）f表示总运费.则运输模型为：运输量非负约束；需求量约束运出量受存量约束),,j,i(xxxxxxxxxxxxx.t.sxxxxxxfminij321210251540305042232231322122111232221131211232221131211一般地，对于有m个发点和n个收点的运输模型为),...2,1;,...2,1(0)...2,1(),...3,2,1(..min1111njmixnjbxmiaxtsxcfijmijijnjiijminjijij其中ai为i号发点的运出量，bj为j号收点的需求量，cij为从i号发点到j号收点的单位运价。特别当minjjiba11时，存货必须全部运走，故上述约束条件中的njiijax1可改为等式：),...2,1(1miaxinjij3选址问题某地区有m座煤矿，i#矿每年产量为ai吨，现有火力发电厂一个，每年需用煤b0吨，每年运行的固定费用（包括折旧费，但不包括煤的运费）为h0元。现规划新建一个发电厂，m座煤矿每年开采的原煤将全部供给这两个电厂发电用。现有n个备选的厂址。若在j#备选厂址建电厂，每年运行的固定费用为hj元，每吨原煤从i#矿运送到j#备选厂址的运费为cij元(i=1,2,…m,j=1,2…n)。每吨原煤从i#矿运送到原有电厂的运费为ci0(i=1,2,…m)。试问：[1]应把新电厂厂址选在何处？[2]m座煤矿开采的原煤应如何分配给两个电厂？才能使每年的总费用（电厂运行的固定费用与原煤运费之和）为最小？4模型的建立(1)变量的设置为了解决问题[1]，我们使用0-1变量njjyj,2,10#1否则备选厂址选中为了解决问题[2]，设从i#煤矿运到j#备选的厂址的运量为xij吨（i=1,2,…m，j=0,1,2,…,n）备选厂址j煤矿i现有电厂0备选厂址年产量12┄j┄n11010/xc11/jjxc1a22020/xc22/jjxc2a┄┄┄m00/mmxc/mjmjxcma年需求量0b01miibab1miia总供应(2)目标函数的表达总运费：ijminojijxc1（对不被选中的备选厂址运费xij,将由约束条件限制为0）.固定费用h0+njjjyh1每年总费用z=0110hyhxcnjjjminjijij(3)约束条件的表达（i）煤矿产量约束m,,iaxinjij210（ii）旧电厂用煤量约束010bxmii（iii）新电厂用煤量约束记01babmii，当j#备选厂址被选中时miijbx1，当j#备选厂址没被选中时miijx10，综合表达为njybxjmiij,...2,115（iv）选址约束由于只选一个厂址，所以11njjy(v)非负及整数约束njynjmixjij,2,110,2,1,0,2,10或综合得数学规划模型：010100011011min,1,...,,1,...,..10,1,...,;0,...,0,1;1,...,mnnijijjjijjnijijmiimijjimiinjjijjzcxhyhxaimxbxbyjnstbabyximjnyjn4布点问题某市有6个区，每个区都可建消防站，为了节省开支，市政府希望设置的消防站最少，但必须保证在该市任何地区发生火警时，消防车能在15分钟内赶到现场。假定各区的消防站要建的话,就建在区的中心，根据实地测量,各区之间消防车行使的最长时间如下表:(单位:分钟)1区2区3区4区5区6区1区410162827202区105243217103区162441227214区283212515255区271727153146区20102125146请你为该市制定一个设置消防站的最节省的计划。建模并求解。6解：本题实际上是要确定各个区是否要建立消防站，使其既满足要求，又最节省。这自然可引入0-1变量，故设）（区建消防站时当不在第区建消防站时当在第62101,,,jj,j,xj目标是61jjxf最少。以下考虑约束条件。若1区发生火警，按照“消防车要在15分钟内赶到现场”的要求，则l区和2区至少应有一个消防站，即121xx。同理得：1111165265454343621xxx,xxx,xxx,xx,xxx从而得模型为：62110111111652654543436212161),,,j(,,xxxxxxxxxxxxxxxxx.t.sxfminjjj再仔细观察知，若满足第一、三个约束条件，则必然满足第二、四个约束条件，故后者是多余的，可省略。从而化简得：621101111652654432161),,,j(,,xxxxxxxxxxx.t.sxfminjjj此模型当然可用软件求解，但由于比较简单,故可直接试算。若要求只有一个1jx，则显然不可行；若要求只有两个1jx，则有唯一可行解01653142xxxx,xx，故这就是最优解，即只需在2区和4区建立消防站。附程序：c=[111111]a=-[110000;001100;000111;010011]b=-[1111]7v=zeros(1,6)u=[111111][xfval]=linprog(c,a,b,[],[],v,u)Optimizationterminated.x=0.00001.00000.00001.00000.00000.0000fval=2.00005配套问题设有n个车间要生产m种产品，第j车间每天生产第i种产品至多aij件（即全天只安排生产产品i而不安排生产其他产品时的最大产量），假设这m种产品每种一件配成一套，问如何安排生产任务才能使生产出的成套产品最多？（i=1,2,...,m；j=1,2,...,n）8（1）建模方法（一）设xij——车间j安排用于生产产品i的数量，Z——每天生产的成套产品数目，车间j产品i12┄j┄n全厂生产产品I的数量111x┄┄1jx┄1nx┄221x┄┄2jx┄2nx┄┄┄┄┄┄┄┄┄i1ix┄┄ijx┄inx1nijjx全厂每天生产产品I的总量┄┄┄┄┄┄┄┄m1mx┄┄mjx┄mnx┄车间j每天生产产品I的总量1mijix车间j每天生产产品I的总量原问题可以转化为以下数学模型：11maxminnijimjfzx..0(1,,;1,,)ijijijfzstxaximjn模型改进为：maxfz1(1,,)..0(1,,;1,,)nijjijijijxzimstxaximjn模型问题：没有将一天的生产时间约束考虑到！92、建模方法（二）设xij——车间j安排用于生产产品i的时间（占全天的比例）Z——每天生产的成套产品数目则aijxij——车间j每天生产产品i的数目。例如：车间2每天至多生产某产品6件，若安排1/3天时间去生产，则可产出2件），而xaijnjij1——每天全厂产出产品i的总量。车间j产品i12┄j┄n全厂生产产品I的数量11111xa┄┄11jjxa┄11nnxa┄22121xa┄┄22jjxa┄22nnxa┄┄┄┄┄┄┄┄┄i11iixa┄┄ijijxa┄ininxa1nijijjxa全厂每天生产产品I的总量┄┄┄┄┄┄┄┄m11mmxa┄┄mjmjxa┄mnmnxa┄车间j每天生产产品I的总量1mijijixa车间j每天生产产品I的总量于是则有模型maxZ(11minnijimjzx)(*)整数0212102112111Z)n,...,,j;m,...,,i(x)n,...,,j()m,...,,i(Z.t.sijmiijnjijijxxa其中常数1表示1天。10注：(1)此模型着重考虑安排生产的时间；(2)从实际情况考虑，安排生产的时间必须是每件产品耗用生产时间的整数倍才合适。例如，每3分钟生产一件产品，安排5分钟，也只能生产1件，不能认为生产了1.67件。模型（*）没有考虑到这些因素，故是不合适的。（2）建模方法（二）——改进（*）显然，ija1——车间j生产每件产品i的耗用时间（天）。从以上分析应有axijij1?(?是非负整数)从而令yij=aijxij,yij是非负整数,表示车间j每天生产产品i的数目，将它代入（*）后得maxZ(**)整数整数02121021112111Z)n,...,,j;m,...,,i()n,...,,j()m,...,,i(Z.t.syyayijmiijijnjij这是一个整数线性规划模型。注：此模型着重考虑安排生产产品的数目。四、数学规划在数学建模中的应用举例1．钻井布局勘探部门在某地区找矿。初步勘探时期已零散地在若