算法合集之《浅谈信息学竞赛中的线性规划简洁高效的单纯形法实现与应用》

线性规划的简单应用和实现浙江省杭州二中李宇骞摘要线性规划在实际生活中应用非常广泛，已经创造了无数的财富。但是它在竞赛中的应用很少。然而，我相信它的潜力很大，所以在这里向大家简单地介绍了线性规划的一些应用，以及如何实现解线性规划，以抛砖引玉，希望线性规划能够在竞赛中如同网络流一样熠熠生辉。本文主要分三部分，第一部分简单地介绍了线性规划，给出了其定义；第二部分给出了一些简单的应用，以及一个线性规划的经典应用——多物网络流；第三部分是用单纯形（Simplex）算法实现解线性规划。由于对大多数竞赛选手而言，写一个线性规划的程序比构造一个模型更为恐怖（虽然难度可能不及），并且单纯形法不是多项式级别的，不实践很难知道它的速度到底怎么样，所以本文着重于第三部分，较详细地描述了一些实现的细节，以及简单的证明，并且对单纯形法的运行速度做了一些实验，还与专业的数学软件MATLAB和LINDO做了对比，从一定程度上说明了单纯形法的速度是卓越的。同时，200行左右的程序可以让大家不必那么担心编程的复杂度，某些情况下，100行左右的程序就足够了。关键字线性规划（Linearprogramming）单纯形法（Simplex）多物网络流（Multicommodityflow）引言“随著强有力的算法的发展与应用,线性规划能解决的问题也越来越来多。在历史上，没有哪种数学方法可以像线性规划那样，直接为人类创造如此巨额的财富，并对历史的进程发生如此直接的影响。”孙捷，这位曾经执教于清华大学的美国华盛顿大学博士如此评价线性规划。他还举了这样一个实例：在波斯湾战争期间，美国军方利用线性规划，有效地解决了部队给养和武器调运问题，对促进战争的胜利，起了关键的作用。难怪人们说，因为使用炸药，第一次世界大战可说是「化学的战争」；因为使用原子弹，第二次世界大战可说是「物理的战争」；因为使用线性规划，波斯湾战争可称为「数学的战争」。线性规划在实际生活当中的威力已毋庸质疑，但是在信息学竞赛中，他的光芒还没有闪耀在我们的眼前，让我们通过学习和了解，去渐渐感受它的光彩。正文第一部分简介与定义我们会遇到很多这样的问题：他们需要使目标最大化或者最小化；他们通常面临资源或者其它方面上的限制，或者必须在某些方面进行取舍而不能兼顾。如果这些问题的目标可以表示成一个线性的函数，它们的限制或者取舍可以表示成一些线性的等式或者不等式，那么我们就可以将这些问题描述成线性规划的问题。首先来看一个实例：假如你要竞选市长。要当上市长，你必须有5万的城市居民的投票、10万郊区居民的投票以及2.5万农村居民的投票。你有以下四种方案使你获得更多的投票：1.建设道路2.加强枪支管制3.发放农业津贴4.减免油税并且，你对上述四种方案进行了评估，得到了在某一方案上开支的钱和某一区域内选民票数的变化的关系，如下表。表格中的某一项表示在对应方案上每开支1万元，对应区域中选票增加的数量，以千张为单位。比如第一行第一列-2代表在建设道路上每增加1万元的支出，会减少2千人的城市居民选票；第一行第二列5表示在建设道路上每增加1万元支出，会增加5千人的郊区居民选票；第二行第三列表示在枪支管制上每增加1万元支出，会减少5千人的农村居民选票。你要用最少的支出来获得足够的选票当上市长，假设初始时，你的投票数都为0。这个问题的目标是要求开支最小，它的限制是选票必须达到最低限制，取舍关系是为了增加一个区域的居民投票而在一个项目上投资，可能会造成其它区域的居民投票减少。当然，这个问题还有一些潜在的限制，比如支出不能为负。下面，我们把它描述成一个线性规划问题：假设4种项目的支出分别为x1、x2、x3、x4万元，目标：最小化x1+x2+x3+x4（总支出最小）农村郊区城市－2010减免油税1000农业津贴－528枪支管制35－2建设道路限制：-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=1njjjax线性等式或者不等式：如果f(x1,x2,…,xn)是一个线性函数，那么f(x1,x2,…,xn)=b是一个线性等式，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)=aiqi(x1,x2,…,xn)=biri(x1,x2,…,xn)=ci其中f是目标函数，pi是限制中所有的小于等于的线性不等式，qi是限制中所有的线性等式，ri是限制中所有的大于等于的线性不等式。比如：最大化2x1-3x2+3x3满足：x1+x2-x3=7x1-2x2+2x3=4最小化2x1+7x2满足:x1=73x1+x2=24.5x2=3x3=-1都是线性规划。注意，线性规划中的系数不要求是整数或者有理数，可以是任何实数，并且线性规划的最优解(y1,y2,…,yn)中的y也不一定要是整数或者有理数。如果y限定成整数，那么问题是NPC的，也就是现在为止还没有有效(多项式)解法。第二部分简单的应用下面主要讲了三个简单的应用，前两个分别是相对比较简单的资源优化配置和最佳物资供给，最后一个是相对复杂的多物网络流。一、资源优化配置有m种资源和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=b1a12x1+a22x2+a32x3+a42x4=b2a13x1+a23x2+a33x3+a43x4=b3x1,x2,x3,x4=0上述式子可以简写成：最大化41iiicx满足：41(13)ijijiaxbjxi=0(1=i=4)下面是一般的资源优化配置问题的线性规划描述：最大化1niiicx满足：1(1)nijijiaxbjmxi=0(1=i=n)二、最佳物资供给有m种需求要满足，假设第j种需求至少要bj的量才能满足。现在有n种物资，其中每单位第i种物资会提供给第j种需求aij的量。假设第i种物资供给了xi单位，要支付费用ci*xi。在满足所有需求的前提下，使总费用最小。下面的问题就是一个最佳物资供给问题：一个人一天至少要摄入b1克糖类、b2克脂肪、b3克蛋白质以及b4克维生素。米饭的价格为每克c1元，每克米饭会提供a11克糖类、a12克脂肪、a13克蛋白质以及a14克的维生素；蔬菜每克c2元，每克蔬菜回提供a21克糖类、a22克脂肪、a23克蛋白质以及a24克维生素；肉类每克c3元，每克肉类提供a31克糖类、a32克脂肪、a33克蛋白质以及a34克维生素。请问至少要多少钱才能满足人一天的营养需求？上述问题可以描述为下面的线性规划问题：假设人一天吃米饭x1克、蔬菜x2克、肉类x3克最小化c1x1+c2x2+c3x3满足：a11x1+a21x2+a31x3=b1a12x1+a22x2+a32x3=b2a13x1+a23x2+a33x3=b3a14x1+a24x2+a34x3=b4x1,x2,x3,x4=0一般的最佳物资供给问题可以描述为如下的线性规划问题：最小化1niiicx满足：1(1)nijijiaxbjmxi=0(1=i=n)三、多物网络流看到这个标题，很多人都会联想到一般的网络流：有着简单、高效的解法，并且用途广泛。一些经典的网络流模型常常巧妙得令人瞠目结舌。多物网络流虽然和网络流有很多的相同之处，但是它至今为止唯一的有效解法只有线性规划。然而，我相信它的用途绝不比网络流逊色，应该更强大，并且它的一些模型的构造将会比普通的网络流更令人吃惊，因为它不仅包含了只有一个源点和汇点的网络流，还可以应对有多个源点和汇点的网络流。那么到底什么是多物网络流呢？其实上面已经略有提及。多物网络流基本上和一般的网络流一致，唯一的区别就是多物网络流有k个源点和汇点，k可能大于1。假设第i个源点为si，第i个汇点为ti（1=i=k）。多物网络流的问题就是要求一个满足si到ti的流量都为fi的可行流。下面是具体的定义：多物网络流：有一个V个点、E条边的有向图，假设第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。给出城市之间每天铁路的流量限制。假设物品可以任意地成若干份，从而可以分别从不同的线路走。求一个可行的运送方案。用线性规划来描述多物网络流：最小化：0满足：1(,)(1)kieeeifuvceE::(,)(,)(1,1pqippiqqipvvquvfuvfuvikvVvsi且不等于或t):(,)(1)eiieeieusfuvdik(,)0(1,1)ieefuvikeE这里最小化0的意思就是只求一个满足条件的可行解，也就是目标函数中所有的系数都是0。（注：这里的描述和《算法导论》上不一样，主要考虑到可能有重边的情况）在一般的多物网络流基础上，如果每条边还有一个花费，假设第e条边的单位花费为Coste，那么在这条边上的花费就等于这条边上的流量和乘以Coste，整个网络流的费用就是所有边的费用和。我们现在的问题不仅是要求一个可行流，还要求一个费用最小的可行流。上述问题就是一个最小费用的多物网络流问题。它的条件和多物网络流完全一样，只是目标函数不同：多物网络流最小化0，多物最小费用流最小化11(,)EkeieeeiCostfuv。接下来有一道改编自NWERC2006-D的多物最小费用流的例题：在一个地图上，某铁路公司有4项目。第i个项目要建造一条从城市si到ti的铁路。现在有一些铁路段可以供公司选择建造，每一段都是从一个城市到另一个城市的，且每一段铁路的造价是已知的。由于项目之间是独立的，每一段铁路只能被一个项目所拥有、建造，造好以后也只能被此项目所使用。求完成4个项目的最小费用。我们将城市作为点，铁路段作为边进行构图，每条边的容量都是1，单位费用为建造该铁路段的费用，k等于4，si和ti没有变，di都是1。如果仔细看上面的这个模型，