运筹学模型与数学建模竞赛
一、引言
一般来说，大学生数学建模竞赛所涉及到的运筹学模型包括数学规划（线性规划和非线性规划），网络优化（含网络计划技术），排队模型，动态规划等，请看下表 年份 1994 1995 1995 1996 1996 1997 1997 1998 1998 1999 2000 2001 2002 2003 2004 2004 题号 A A B A B A B A B B B B A B A B 题名 逢山开路 一个飞行管理问题 天车与冶炼炉的作业调度 最优捕鱼策略 节水吸引机 零件的参数设计 横断切割 投资的收益和风险 灾情巡视路线 钻井布局 钢管的订购和运输 公交车调度 车灯线光源的优化设计 露天矿生产的车辆安排 奥运场馆的设计 电力市场的输电阻塞管理 模型分类 网络优化 数学规划 网络计划技术 涉及数学规划 涉及动态规划 数学规划 涉及数学规划或网络优化 数学规划 网络优化 数学规划 数学规划和网络优化 数学规划 涉及数学规划 数学规划 涉及数学规划 涉及数学规划 注：从1999年起，全国大学生数学建模竞赛开始设置专供大专院校学生做的C，D题。
下面重点介绍运筹学模型的数学规划。 二、数学规划的一般形式
minf(x)(ormaxf(x))
s.t.线性规划： 整数规划： 非线性规划：
?hi(x)?0,i?1,2,?,l?j?1,2,?,m ?gj(x)?0,?lb?x?ub?三、数学规划问题举例
1 下料问题
现要用100×50厘米的板料裁剪出规格分别为40×40 厘米与50×20厘米的零件，前者需要25件，后者需要30件。问如何裁剪，才能最省料？
1
解：先设计几个裁剪方案
记 A---------40×40；B-----------50×20
方案1
A A B //////////////////////////////
方案2
A ////////////// B B B
方案3
B B B B B 注：还有别的方案吗？
显然，若只用其中一个方案，都不是最省料的方法。最佳方法应是三个方案的优化组合。设方案i使用原材料xi件(i=1,2,3)。共用原材料f件。则根据题意，可用如下数学式子表示：
minf?x1?x2?x3s.t.?2x1?x2?25 ??x1?3x2?5x3?30?x?0，整数(j?1,2,3)?j这是一个整数线性规划模型。
2 运输问题
现要从两个仓库（发点）运送库存原棉来满足三个纺织厂（收点）的需要，数据如下表，试问在保证各纺织厂的需求都得到满足的条件下应采取哪个运输方案，才能使总运费达到最小？（运价（元/吨）如下表）
工厂 j 仓库i 1号 2号 需求量（吨）
1号 2号 3号 库存量（吨） 2 2 40 1 2 15 3 4 25 50 30 2
解：题意即要确定从i号仓库运到j号工厂的原棉数量。故设xij表示从i号仓运到j号工厂的原棉数量（吨）f表示总运费.则运输模型为：
minf?2x11?x12?3x13?2x21?2x22?4x23?x11?x12?x13?50??运出量受存量约束??x21?x22?x23?30??x?x?40?1121? ??s.t.?x12?x22?15?需求量约束?x?x?25???1323?xij?0(i?1,2；j?1,2,3)运输量非负约束???一般地，对于有m个发点和n个收点的运输模型为
minf???cijxiji?1j?1mn?n??xij?ai(i?1,2,3,...m)?j?1 ??ms.t.??xij?bj(j?1,2...n)?i?1?xij?0(i?1,2,...m;j?1,2,...n)???其中ai为i号发点的运出量，bj为j号收点的需求量，cij为从i号发点到j号收点的单位运
价。 特别当
?a??bii?1j?1mnj时，存货必须全部运走，故上述约束条件中的
?xj?1nij?ai可改为等
式：
3 选址问题
?xj?1nij?ai(i?1,2,...m)
某地区有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座煤矿开采的原煤应如何分配给两个电厂？
才能使每年的总费用（电厂运行的固定费用与原煤运费之和）为最小？
3
模型的建立
(1) 变量的设置为了解决问题[1]，我们使用0-1变量
?1yj???0选中j#备选厂址否则j?1,2,?n
为了解决问题[2]，设从i#煤矿运到j#备选的厂址的运量为xij吨（i=1,2,…m，j=0,1,2,…,n）
备选厂址j 现有电厂 0 备 选 厂 址 年产量 煤矿i 1 2 ┄ j ┄ n 1 2 ┄ m 年需求量 x10/c10 x20/c20 ┄ x1j/c1j a1 a2 ┄ x2j/c2j xm0/cm0 xmj/cmj b??ai?b0 i?1mam b0 ?ai?1mi?总供应 (2)目标函数的表达 总运费：
??ci?1j?onmnijxij（对不被选中的备选厂址运费xij,将由约束条件限制为0）.
固定费用 h0+
?hj?1mjyj
n每年总费用 z =
??ci?1j?0ijxij??hjyj?h0
j?1n(3)约束条件的表达 （i）煤矿产量约束
?xj?0mnij?aii?1,2,?m
（ii）旧电厂用煤量约束
?xi?1i0?b0
?b0，当j备选厂址被选中时?xij?b，当
#
（iii）新电厂用煤量约束 记 b??ai?1mmii?1 4
j备选厂址没被选中时
#
?xi?1mij?0，综合表达为?xij?byji?1mj?1,2,...n
（iv）选址约束 由于只选一个厂址，所以
?yj?1nj?1
(v)非负及整数约束
xij?0yj?0或1i?1,2,?mj?1,2,?nj?0,1,2,?n
综合得数学规划模型：
minz???cijxij??hjyj?h0i?1j?0j?1mnn?n??xij?ai,i?1,...,m?j?0?m??xi0?b0?i?1?m??xij?byj,j?1,...,n?i?1m??s.t.?b??ai?b0i?1??n??yj?1?j?1?x?0,i?1,...,m;j?0,...,n?ij?yj?0,1;j?1,...,n?? ??4布点问题
某市有6个区，每个区都可建消防站，为了节省开支，市政府希望设置的消防站最少，但必须保证在该市任何地区发生火警时，消防车能在15分钟内赶到现场。假定各区的消防站要建的话,就建在区的中心，根据实地测量,各区之间消防车行使的最长时间如下表:(单位:分钟)
1区 1区 2区 3区 4区 5区 6区 4 10 5 24 32 17 10 16 24 4 12 27 21 5
28 32 12 5 15 25 27 17 27 15 3 14 20 10 21 25 14 6 2区 10 3区 16 4区 28 5区 27 6区 20