《国家集训队论文集6.李宇骞浅谈地的信息学》由会员分享，可在线阅读，更多相关《国家集训队论文集6.李宇骞浅谈地的信息学（18页珍藏版）》请在金锄头文库上搜索。
1、word 线性规划的简单应用和实现某某省某某二中李宇骞摘要线性规划在实际生活中应用非常广泛，已经创造了无数的财富。但是它在竞赛中的应用很少。然而，我相信它的潜力很大，所以在这里向大家简单地介绍了线性规划的一些应用，以与如何实现解线性规划，以抛砖引玉，希望线性规划能够在竞赛中如同网络流一样熠熠生辉。本文主要分三局部，第一局部简单地介绍了线性规划，给出了其定义；第二局部给出了一些简单的应用，以与一个线性规划的经典应用多物网络流；第三局部是用单纯形Simplex算法实现解线性规划。由于对大多数竞赛选手而言，写一个线性规划的程序比构造一个模型更为恐怖虽然难度可能不与，并且单纯形法不是多项式级别的，不实
2、践很难知道它的速度到底怎么样，所以本文着重于第三局部，较详细地描述了一些实现的细节，以与简单的证明，并且对单纯形法的运行速度做了一些实验，还与专业的数学软件MATLAB和LINDO做了比照，从一定程度上说明了单纯形法的速度是卓越的。同时，200行左右的程序可以让大家不必那么担心编程的复杂度，某些情况下，100行左右的程序就足够了。关键字线性规划Linear programming单纯形法Simplex多物网络流Multimodity flow引言“随著强有力的算法的开展与应用,线性规划能解决的问题也越来越来多。在历史上，没有哪种数学方法可以像线性规划那样，直接为人类创造如此巨额的财富，并对历史
3、的进程发生如此直接的影响。孙捷，这位曾经执教于清华大学的美国华盛顿大学博士如此评价线性规划。他还举了这样一个实例：在波斯湾战争期间，美国军方利用线性规划，有效地解决了部队给养和武器调运问题，对促进战争的胜利，起了关键的作用。难怪人们说，因为使用炸药，第一次世界大战可说是化学的战争；因为使用原子弹，第二次世界大战可说是物理的战争；因为使用线性规划，波斯湾战争可称为数学的战争。 线性规划在实际生活当中的威力已毋庸质疑，但是在信息学竞赛中，他的光芒还没有闪耀在我们的眼前，让我们通过学习和了解，去渐渐感受它的光彩。正文第一局部简介与定义我们会遇到很多这样的问题：他们需要使目标最大化或者最小化；他们通常
4、面临资源或者其它方面上的限制，或者必须在某些方面进展取舍而不能兼顾。如果这些问题的目标可以表示成一个线性的函数，它们的限制或者取舍可以表示成一些线性的等式或者不等式，那么我们就可以将这些问题描述成线性规划的问题。首先来看一个实例：假设你要竞选市长。要当上市长，你必须有5万的城市居民的投票、10万郊区居民的投票以与2.5万农村居民的投票。你有以下四种方案使你获得更多的投票：农村郊区城市2010减免油税1000农业津贴528枪支管制352建设道路并且，你对上述四种方案进展了评估，得到了在某一方案上开支的钱和某一区域内选民票数的变化的关系，如下表。表格中的某一项表示在对应方案上每开支1万元，对应区域
5、中选票增加的数量，以千X为单位。比如第一行第一列-2代表在建设道路上每增加1万元的支出，会减少2千人的城市居民选票；第一行第二列5表示在建设道路上每增加1万元支出，会增加5千人的郊区居民选票；第二行第三列表示在枪支管制上每增加1万元支出，会减少5千人的农村居民选票。你要用最少的支出来获得足够的选票当上市长，假设初始时，你的投票数都为0。这个问题的目标是要求开支最小，它的限制是选票必须达到最低限制，取舍关系是为了增加一个区域的居民投票而在一个项目上投资，可能会造成其它区域的居民投票减少。当然，这个问题还有一些潜在的限制，比如支出不能为负。下面，我们把它描述成一个线性规划问题：假设4种项目的支出分
6、别为x1、x2、x3、x4万元，目标：最小化x1+x2+x3+x4总支出最小限制：-2x1+8x2+0x3+10x4 = 50城市居民5x1+2x2+0x3+0x4 = 100郊区居民3x1-5x2+10x3-2x4 = 25农村居民x1, x2, x3, x4 = 0开支不可能为负那么到底什么是线性规划呢？我们来看定义。线性规划：在满足一些线性等式或者不等式的条件下，最优化一个线性函数。线性函数：给定一些实数：a1, a2, , an和一些变量x1, x2, , xn，这些变量的线性函数f是f(x1, x2, , xn) = a1x1+a2x2+anxn=线性等式或者不等式：如果f(x1,
7、x2, , xn) 是一个线性函数，那么f(x1, x2, , xn) = b 是一个线性等式，f(x1, x2, , xn) = b 是一个线性不等式。这些东西统称为线性约束。线性规划的解：一个向量y1, y2, , yn，使得当xi=yi时目标函数最优且满足条件。线性规划的可行解：一个向量y1, y2, , yn，使得当xi=yi时满足条件，但目标函数不一定最优。线性规划的最优值：在满足条件的前提下目标函数的最优值。一般情况下，我们可以把一个线性规划的问题写成如下形式：最小化或者最大化f(x1, x2, , xn) 满足：pi(x1, x2, , xn) = ci其中f是目标函数，pi是限
8、制中所有的小于等于的线性不等式，qi是限制中所有的线性等式，ri是限制中所有的大于等于的线性不等式。比如：最大化2x1-3x2+3x3满足：x1+x2-x3 = 7x1-2x2+2x3 = 3x3 = -1都是线性规划。注意，线性规划中的系数不要求是整数或者有理数，可以是任何实数，并且线性规划的最优解(y1, y2, , yn)中的y也不一定要是整数或者有理数。如果y限定成整数，那么问题是NPC的，也就是现在为止还没有有效(多项式)解法。第二局部简单的应用下面主要讲了三个简单的应用，前两个分别是相比照拟简单的资源优化配置和最优物资供应，最后一个是相对复杂的多物网络流。一、 资源优化配置有m种资
9、源和n个项目，每个资源都是有限的，设它们的上限为bj(1 = j = m)。假设第i个项目做出xi的成果量，可以获得ci*xi的收益，同时会消耗第j种资源aij*xi。求最大收益。比如下面的这个问题就是一个资源优化配置问题：某工厂现在分别有钢材、木材、塑料b1、b2、b3吨，工厂可以生产4种产品，第i种产品每生产一吨可以获得ci万的收益，但是要消耗ai1吨钢材，ai2吨木材以与ai3吨塑料。求工厂的最大收益。我们将上述问题描述成线性规划的问题：假设4种产品产量分别为x1、x2、x3、x4吨最大化c1x1+c2x2+c3x3+c4x4满足:a11x1+a21x2+a31x3 +a41x4= b1
10、a12x1+a22x2+a32x3 +a42x4= b2a13x1+a23x2+a33x3 +a43x4= 0上述式子可以简写成：最大化满足： xi = 0(1 = i = 0(1 = i = b1a12x1+a22x2+a32x3 = b2a13x1+a23x2+a33x3 = b3a14x1+a24x2+a34x3 = b4x1, x2, x3, x4 = 0一般的最优物资供应问题可以描述为如下的线性规划问题：最小化满足： xi = 0(1 = i = n)三、 多物网络流看到这个标题，很多人都会联想到一般的网络流：有着简单、高效的解法，并且用途广泛。一些经典的网络流模型常常巧妙得令人瞠目
11、结舌。多物网络流虽然和网络流有很多的一样之处，但是它至今为止唯一的有效解法只有线性规划。然而，我相信它的用途绝不比网络流逊色，应该更强大，并且它的一些模型的构造将会比普通的网络流更令人吃惊，因为它不仅包含了只有一个源点和汇点的网络流，还可以应对有多个源点和汇点的网络流。那么到底什么是多物网络流呢？其实上面已经略有提与。多物网络流根本上和一般的网络流一致，唯一的区别就是多物网络流有k个源点和汇点，k可能大于1。假设第i个源点为si，第i个汇点为ti 1 = i = k。多物网络流的问题就是要求一个满足si到ti的流量都为fi的可行流。下面是具体的定义：多物网络流：有一个V个点、E条边的有向图，假
12、设第e条边从ue到ve，并且拥有非负的流量限制ce。给出k个物品，第i个物品用(si, ti, di)表示。这里，si是第i个物品的源点，ti是第i个物品的汇点，di是该物品要求的从si到ti的流量。我们定义一个函数fi，fi(ue,ve)表示物品i在边e上的流量。这个函数满足流量守恒定律除了源点si和汇点ti之外，流进一个点的流量等于流出一个点的流量。最后，n个物品在一条边上的流量和不超过这条边的容量。我们需要确定一组满足这些条件的函数fi。如果上面的定义不够直观，我们来看下面的这个实例：某公司要用铁路运送k种物品，分别从城市si到ti，每个物品每天要送出di。给出城市之间每天铁路的流量限制
13、。假设物品可以任意地成假设干份，从而可以分别从不同的线路走。求一个可行的运送方案。用线性规划来描述多物网络流：最小化：0满足：这里最小化0的意思就是只求一个满足条件的可行解，也就是目标函数中所有的系数都是0。注：这里的描述和算法导论上不一样，主要考虑到可能有重边的情况在一般的多物网络流根底上，如果每条边还有一个花费，假设第e条边的单位花费为Coste，那么在这条边上的花费就等于这条边上的流量和乘以Coste，整个网络流的费用就是所有边的费用和。我们现在的问题不仅是要求一个可行流，还要求一个费用最小的可行流。上述问题就是一个最小费用的多物网络流问题。它的条件和多物网络流完全一样，只是目标函数不同：多物网络流最小化0，多物最小费用流最小化。接下来有一道改编自NWERC2006-D的多物最小费用流的例题： 在一个地图上，某铁路公司有4项目。第i个项目要建造一条从城市si到ti的铁路。现在有一些铁路段可以供公司选择建造，每一段都
