线性规划整数规划01规划

一、引言我们从2005年“高教社杯”全国大学生数模竞谈起.其中第二个问题是一个如何来分配有限资源，从而达到人们期望目标的优化分配数学模型.这类问题一般可以归结为数学规划模型.赛的B题“DVD在线租赁”问题的第二问和第三问规划模型的应用极其广泛，其作用已为越来来越急速地渗透于工农业生产、商业活动、军事行为核科学研究的各个方面，为社会节省的财富、创造的价值无法估量.特别是在数模竞赛过程中，规划模型是最常见的一类数学模型.从历年全国大学生数模竞赛越多的人所重视.随着计算机的逐渐普及，它越试题的解题方法统计结果来看，每年至少有一道题涉及到利用规划理论来分析、求解.二、线性规划模型线性规划模型是所有规划模型中最基本、最例1.（食谱问题）设有n种食物，各含m种营养素，第j种食物中第i中营养素的含量为aij,n种食物价格分别为c1,c2,…,cn，请确定食谱中n种食物的数量x1,x2,…,xn，要求在食谱中m种营养素简单的一种.2.1线性规划模型的标准形式的含量分别不低于b1,b2,…,bm的情况下，使得总总的费用最低.首先根据食物数量及价格可写出食谱费用为其次食谱中第i种营养素的含量为因此上述问题可表述为：1122,nncxcxcx1122.iiinnaxaxax11221111221121122222112212min..0,0,0nnnnnnmmmnnmncxcxcxaxaxaxbaxaxaxbstaxaxaxbxxx解上述食谱问题就是一个典型的线性规划问题，寻求以线性函数的最大（小）值为目标的数学模型.它是指在一组线性的等式或不等式的约束条件下，线性规划模型的三种形式⑴一般形式目标函数价值向量价值系数决策变量Tnccc),,(1njcj,,2,1,njxj,,2,1,nqjxqjxmsibxaxaxaspibxaxaxapibxaxaxatsxcxczjjininiiininiiininiinn,1,0,,1,0,,1,,,1,,,1,..min(max)22112211221111右端向量mbbb1系数矩阵mnmmnnaaaaaaaaaA212222111211非负约束自由变量TiAjA⑵规范形式⑶标准形式0..minxbAxtsxcT0..minxbAxtsxcT三种形式的LP问题全都是等价的，即一种形式的LP可以简单的变换为另一种形式的LP，且它们有相同的解.以下我们仅将一般形式化成规范形式和标准形式.目标函数的转化xoz-z)(minmaxzz约束条件和变量的转化①．为了把一般形式的LP问题变换为规范形式，我们必须消除等式约束和符号无限制变量.在一般形式的LP中，一个等式约束可用下述两个不等式约束去替代njijijbxa1njijijbxa1njijijbxa1)()(jjjxxx这样就把一般形式的LP变换为规范形式.对于一个无符号限制变量，引进两个非负变量和，并设jx0jx0jx②．为了把一般形式的LP问题变换为标准形式，必须消除其不等式约束和符号无限制变量.对于一个不等式约束njijijbxa1njiiijijsbsxa10,代替上述的不等式约束.对符号无限制变量的处理可按上述方法进行.可引入一个剩余变量，is用对于不等式约束njijijbxa1njiiijijrbrxa10,代替上述的不等式约束这样就把一般形式的LP变换为标准形式.可引入一个松弛变量ir，用针对标准形式的线性规划问题，其解的理论分析已经很完备，在此基础上也提出了很好的算单纯形方法是线性规划问题的最为基础、也法——单纯形方法及其相应的变化形式（两阶段2.2线性规划模型的求解法，对偶单纯形法等）.是最核心的算法。它是一个迭代算法，先从一个特殊的可行解（极点）出发，通过判别条件去判断该可行解是否为最优解（或问题无界），若不是最优解，则根据相应规则，迭代到下一个更好的可行解（极点），直到最优解（或问题无界）.关于线性规划问题解的理论和单纯形法具体的求解过程可参见文献[1].在实际应用中，特别是数学建模过程中，遇到线性规划问题的求解，我们一般都是利用现有的软件进行求解，此时通常并不要求线性规划问题是标准形式.比较常用的求解线性规划模型的软件包有LINGO和LINDO.运输问题例2.设要从甲地调出物资2000吨，从乙地调出物资1100吨，分别供给A地1700吨、B地1100吨、C假定运费与运量成正比.在这种情况下，采用不地200吨、D地100吨.已知每吨运费如表1.1所示.同的调拨计划，运费就可能不一样.现在问：怎样才能找出一个运费最省的调拨计划？1572521甲15375151乙DCBA表1.1销地运费产地乙11x12x13x14x21x22x23x24x2000411jix1100412jix1700211iix1100212iix200213iix100214iix甲DCBA2423222114131211153751511572521minxxxxxxxxf)4,3,2,1;2,1(0jixij解1112131421222324min212571551513715fxxxxxxxxs.t.11121314212223241121122213231424..20001100170011002001000,1,2;1,2,3,4ijstxxxxxxxxxxxxxxxxxij一般的运输问题可以表述如下：要把某种物资从m个发点miAi,,2,1,，调运给需要这种物资的n个收点njBj,,2,1,.已知nijmiiba11，从iA运一个单位的产品到jB的运价为ijc.现在需要确定一个调运方案，即确定由iA到jB的运输量njmixij,,2,1;,,2,1,，在满足供需要求的条件下，使总运输费用最省.数学模型：njmixnjbxmiaxtsxczijmijijnjiijminjijij,,2,1;,,2,1,0,,2,1,,,2,1,..min1111若其中各产地的总产量等于各销地的总销量，即类似与将一般的线性规划问题转化为其标准nijmiiba11否则，称为不平衡的运输问题，包括：，则称该问题为平衡的运输问题.总产量总销量和总产量总销量.形式，我们总可以通过引入假想的销地或产地，将不平衡的运输问题转化为平衡的运输问题.从而，我们的重点就是解决平衡运输问题的求解.产销不平衡问题的处理在实际中遇到的运输问题常常不是产销平衡的，而是下列的一般运输问题模型mnminf=cijxij（1）i=1j=1ns.t.xijaii=1,2,…,m（2）j=1mxij(=,)bjj=1,2,…,n(3）i=1xij0(i=1,2,…,m;j=1,2,…,n)（4）我们可以通过增加虚设产地或销地（加、减松弛变量）把问题转换成产销平衡问题，下面分别来讨论。1.产量大于销量的情况mn考虑aibj的运输问题，得到的数学模i=1j=1型为mnminf=cijxiji=1j=1ns.t.xijaii=1,2,…,mj=1mxij=bjj=1,2,…,ni=1xij≥0(i=1,2,…,m;j=1,2,…,n)只要在模型中的产量限制约束（前m个不等式约束）中引入m个松弛变量xi,n+1i=1,2,…,m即可，变为：nxij+xin+1=aii=1,2,…mj=1然后，需设一个销地Bn+1,它的销量为：mnbn+1=ai-bji=1j=1这里，松弛变量xin+1可以视为从产地Ai运往销地Bn+1的运输量，由于实际并不运送，它们的运费为cin+1=0i=1,2,…,m。于是，这个运输问题就转化成了一个产销平衡的问题。2.销量大于产量的情况mn考虑aibj的运输问题，得到的数学模型为i=1j=1mnMinf=cijxiji=1j=1ns.t.xij=aii=1,2,…,mj=1mxijbjj=1,2,…,ni=1xij≥0(i=1,2,…,m;j=1,2,…,n)只要在模型中的产量限制约束（后n个不等式约束）中引入n个松弛变量xm+1jj=1,2,…,n即可，变为：mxij+xm+1j=bjj=1,2,…mi=1然后，需设一个产地Am+1,它的销量为：nmam+1=bj-aij=1i=1这里，松弛变量xm+1,j可以视为从产地Am+1运往销地Bj的运输量，由于实际并不运送，它们的运费为cm+1,j=0j=1,2,…,n。于是，这个运输问题就转化成了一个产销平衡的问题。显然，运输问题是一个标准的线性规划问题，因而当然可以运用单纯形方法求解.但由于平衡的运输问题的特殊性质，它还可以用其它的一些特殊方法求解，其中最常用的就是表上作业法，该方法将单纯形法与平衡的运输问题的特殊性质结合起来，很方便地实行了运输问题的求解.关于运输问题及其解法的进一步介绍参考文献[2].对于线性规划问题，如果要求其决策变量取整数值，则称该问题为整数线性规划问题.平面法和分支定界法是两种常用的求解整数线性对于整数线性规划问题的求解，其难度和运三、整数线性规划模型算量远大于同规模的线性规划问题.Gomory割规划问题的方法（见文献[1]）.此外，同线性规划模型一样，我们也可以运用LINGO和LINDO软件包来求解整数线性规划模型.以1988年美国大学生数学建模竞赛B题为例，说明整数线性规划模型的建立及用LINGO软件包如何求解整数线性规划模型。例3.有七种规格的包装箱要装到两节铁路平板车上去。包装箱的宽和高是一样的，但厚度（t，以cm计）及重量（w，以kg计）是不同的.表1给出了每种包装箱的厚度、重量以及数量。每节平板车有10.2m长的地方可用来装包装箱（像面包片那样），载重为40t.由于当地货运的限制，对于C5,C6,C7类包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过302.7cm.试把包装箱装到平板车上，使得浪费的空间最小.种类C1C2C3C4C5C6C7t/cm48.753.061.372.048.752.064.0w/kg200030001000500400020001000n/件8796648为在第节车上装载第件包装箱的,ijxji解令数量（1,2,7;1,2ij）；in为第i种包装箱需要装的件数；iw为第i种包装箱的重量；it为第i种包装箱的厚度；jcl为第j节车的长度（1020jcl）；jcw为第j节车的载重量；s为特殊限制（302.7s）。下面我们建立该问题的整数线性规划模型。1)约束条件两节车的装箱数不能超过需要装的件数，即：每节车可装的长度不能超过车能提供的长度：12,1,2,,7iiixxni71,1,2iijjitxclj每节车可装的重量不超过车能够承受的重量：71,1,2iijjiwxcwj对于C5,C6,C7类包装箱的总数的特别限制：2)目标函数7125()iiiitxxs浪费的空间最小，即包装箱的总厚度最大：7121max()()iiiifxtxx3)整数线性规划模型7121max()iiiitxx12717171251,2,71,21,2..()01,2,7;1,2iiiiijjiiijjiiiiiijxxnitxcljwxcwjsttxxsxij取整数由上一步中的求解结果可以看出，*x4)模型求解运用LINGO软件求解得到：**4191