运筹学模型与数学建模竞赛1、引言一般来说，大学生数学建模竞赛所涉及到的运筹学模型包括数学规划(线性规划和非线性规划)，网络优化(含网络计划技术)，排队模型，动态规划等，请看下表注：从年起，全国大学生数学建模竞赛开始设置专供大专院校学生做的题。

下而重点介绍运筹学模型的数学规划。

二、数学规划的一般形式nin f(x) (ornnx f(x))/l, (x) = 0, i = 1,2,…丿s.t.<0, ) = 12…，加lb<x< uh线性规划:整数规划:非线性规划:三、数学规划问题举例1下料问题现要用100X50厘米的板料裁剪出规格分别为40X40厘米与50X20厘米的零件, 前者需要25件，后者需要30件。

问如何裁剪，才能最省料？解：题意即要确立从i 号仓库运到j 号工厂的原棉数量。

故设X”表示从i 号仓运到j 号工厂的原棉数量（吨）f 表示总运费•则运输模型为：min f = 2x H +X|2 +3^13 + 2x 2| + 2x 22 + 4x 23 ■x H +x [2 +X13 S 50x 21 + x 22 + x 23 < 30X 11+X 2I =40's 』：X [2+X 22 =15需求量约束+ AS j =25列no 仃= 1,2；丿• = 123丿运输量非负约束一般地，对于有m 个发点和门个收点的运输模型为n工® 5q(7 = h2,3,・・m)m/=iXq nO(j = 12・・〃;J = 12・・n)其中q 为i 号发点的运出量，bj 为j 号收点的需求咼，5为从i 号发点到j 号收点的单位运 价。

m n n特别当工％ =工耳时，存货必须全部运走.故上述约朿条件中的工耳可改为等式: r-1j-1n工七=£（，= 1,2,...w ）3选址问题某地区有m 座煤矿，尸矿每年产量为q 吨，现有火力发电厂一个，每年需用煤b 。

吨, 每年运行的固左费用（包括折旧费，但不包括煤的运费）为ho 元。

现规划新建一个发电厂, m 座煤矿每年开采的原煤将全部供给这两个电厂发电用。

现有门个备选的厂址。

若在尸备 选厂址建电厂，每年运行的固左费用为％元，每吨原煤从严矿运送到严备选厂址的运费为 5元（口j=1,2 -n ）o 每吨原煤从厂矿运送到原有电厂的运费为细（i=1,2,...m ）。

试问：[1] 应把新电厂厂址选在何处？[2] m 座煤矿开采的原煤应如何分配给两个电厂？才能使每年的总费用（电厂运行的固左费用与原煤运费之和）为最小？运岀量受存量约束min m n f = H C u XU模型的建立(1)变量的设置为了解决问题[1],我们使用0・1变量[1选电/#备选厂址.“y； =< — , / = 1,2< -n70否则目标函数的表达m n总运费工工勺勺(对不被选中的备选厂址运费x场将由约束条件限制为0)・r-l每年总费用SW6jXij + 22h jy J +仏z-l J—O y-1(3)约束条件的表达(i)煤矿产量约束n工© = q i = 12…加m(ii)旧电厂用煤量约束2>,。

=九(iii)新电厂用煤疑约束m m记b =工山_叽,当严签选厂址被选中时工切=〃，当r-l r-ltn m严备选厂址没被选中时工切=0,综合表达为工勺=b y） j = 1,2..../?>-1 J-I（iv）选址约束由于只选一个厂址，所以丈=17-1x.j > 0 i = 1,2,…m j = 0丄2, - n（V）非负及整数约束y} =0或1 j = 12综合得数学规划模型:min乙=为为°护j +为山儿+心/=! >=() ./=!艺©=曲=1,…，加7=0m工ho =6z=lm工心=by j J = \,....nZ = 1s.t.<b = 丁 6— Z?()/=!4布点问题某市有6个区，每个区都可建消防站，为了肖省开支，市政府希望设置的消防站最少, 但必须保证在该市任何地区发生火警时，消防车能在15分钟内赶到现场。

假定各区的消防站要建的话，就建在区的中心，根据实地测量,1区2区3区4区5区6区1区410162827202区105243217103区162441227214区283212515255区271727153146区20102125146请你为该市制左一个设置消防站的最省的讣划。

建模并求解。

解：本题实际上是要确泄各个区是否要建立消防站，使其既满足要求，又最卩省。

这自然可 引入0・1变量，故设1,当在第/区建消防站时 （・=]2 6）0,当不在第/区建消防站时若1区发生火警，按照“消防车要在15分钟内赶到现场”的要求，贝IJ I 区和2区至少 应有一个消防站，即為+£»1。

同理得：x x +x 2 +x 6 > 1,从而得模型为：7=1X, +x 2 >1 x l + x 2 +x 6>\ x 3+x 4>\ S ・f S x 3+x 4+x 5>\x 4 + x 5 +x 6 > 1x 2 + x 5 +x 6 > 1 Xj =0,1,（ J = 1,2,…,6 丿若满足第一、三个约束条件，则必然满足第二、四个约朿条件，故后者 从而化简得：tninf = X X j/-IXj +x 2 > 1 x 3 +x 4 > 1s.t.< x 4 + x 5 + x 6 > 1x 2 + x 5 + x 6 > 1Xj =0,1,( j = 1,2,…,6 丿此模型当然可用软件求解，但由于比较简单，故可直接试算。

若要求只有一个厂=1,则显 然不可行；若要求只有两个Xj =1 f 则有唯一可行解x 2 =x 4 = 1, Xj = = x 5 = x 6 = 0 ,故这就是最优解，即只需在2区和4区建立消防站。

附程序：c=[1 11111]a=-[1 1 OOOOjOO 1 1 0 O;O 0 0 1 1 1;O 1 00 1 1] b=-[1 1 1 1] v=zeros(1,6) u=[1 11111]X ：=6目标是f = X X J 最少。

以下考虑约束条件。

x 3+x 4> 1, x 3+x 4 +x 5 > 1, x 4+x 5+x 6 > 1, x 2 + x 5 + x 6 >\再仔细观察知, 是多余的，可省略。

[x fval]=linprog(c,a,b,[],[],v,u)Optimization terminated・x =0.00001.00000.00001.00000.00000.0000 fval =2.00005配套问题设有门个车间要生产m种产品，第j车间每天生产第i种产品至多Gj件（即全天只安排生产产品，而不安排生产其他产品时的最大产量），假设这m种产品每种一件配成一套, 问如何安排生产任务才能使生产出的成套产品最多？设Xij车间j安排用于生产产品i的数量，Z——每天生产的成套产品数目,/1max f = z = min V x.i<i<m 々tJf>Zs X.. < fl..x.. > o a = i,…,〃2；/・=i,…,）模型改进为：max f = z（i = h…"）j"Xjj 5 ©A；y > 0 （； = 1,・・・,〃叮=1,・・・/）模型问题：没有将一天的生产时间约束考虑到!设Xfj ——车间八安排用于生产产品f的时间（占全天的比例）z—一每天生产的成套产品数目则夠X"——车间/每天生产产品j的数目。

例如：车间2每天至多生产某产品6件，若安排1/3天时间去生产，则可产出2件），而工cgxq一一每天全厂产出产品了的总量。

y-i12■ ■ ■j■ ■ ■n全厂生产产品1的数址1■ ■ ■■ ■ ■■ ■ ■X\n a\n■ ■ ■2■ ■ ■■ ■ ■X2j a2j■ ■ ■X2n a2n■ ■ ■■ ■ ■■ ■ ■■ ■ ■■ ■ ■■ ■ ■■ ■ ■■ ■ ■•1■ ■ ■■ ■ ■■ ■ ■X A n为/j全厂毎天生产产品1的总/•Ifit■ ■ ■■ ■ ■■ ■ ■■ ■ ■■ ■ ■■ ■ ■■ ■ ■■ ■ ■m■ ■ ■■ ■ ■■ ■ ■■ ■ ■车剛毎天生产产品I的总扯nt2＞曲车间ji-i每天生产产品i的总max Z ( z = min V )土ClijXijNZ =Hls*龙如兰1（丿=12…力丿/-Ix y > O (i = 1,2,・・・冲,・丿=1,2,.../?丿Z>0 整数其中常数1表示1天。

注：（H此模型着重考虑安排生产的时间：（2）从实际情况考虑,安排生产的时间必须是每件产品耗用生产时间的整数倍才合适。

例如,每3分钟生产一件产品，安排5分钟,也只能生产、件,不能认为生产了\.67件。

模型（*）没有考虑到这些因素,故是不合适的。

（2）建模方法（二）一一改进严）显然，—一一车间/生产每件产品i的耗用时间（天九从以上分析应有a：：（?是非负整数）从而令WjfjXij , Wj是非负整数，表示车间J每天生产产品i的数目，将它代入（°）后得max Z工y nZ仃=12・・・川丿冃tJ/ 、" 122 —* 1 (j=1,2,…〃丿/=1偽丿1y…>0 整数(,=1,2,…川;j = 1,2,.../?丿" Z>0整数这是一个整数线性规划模型。

注:此模型着重考虑安排生产产品的数目。

四、数学规划在数学建模中的应用举例1.钻井布局勘探部门在某地区找矿。

初步勘探时期已零散地在若干位苣上钻井，取得了地质资料。

进入系统勘探时期后，要在一个区域内按纵横等距的网格点来布宜井位，进行“撒网式”全而钻探。

由于钻一口井的费用很髙，如果新设讣的井位与原有井位重合（或相当接近），便可利用旧井的地质资料，不必打这口新井。

因此，应该尽量利用旧井，少打新井，以丹约钻探费用。

比如钻一口新井的费用为500万元，利用旧井资料的费用为10万元，则利用一口旧井就节约费用490万元.设平面上有n个点R,其坐标为（a f,b,）,j=1,2,...,n,表示已有的n个井位。

新布置的井位是一个正方形网格N的所有结点（所谓“正方形网格”是指每个格子都是正方形的网格：结点是指纵线和横线的交叉点）。

假左每个格子的边长（井位的纵横间距）都是1单位（比如100米）。

整个网格是可以在平而上任意移动的。

若一个已知点Pi与某个网格结点Xi的距离不超过给左误差£（=0.05单位），则认为Pi处的旧井资料可以利用，不必在结点X’ 处打新井。