资源描述：
《国家集训队2007论文集6.李宇骞《浅谈信息学》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、线性规划的简单应用和实现浙江省杭州二中李宇骞摘要线性规划在实际生活中应用非常广泛，已经创造了无数的财富。但是它在竞赛中的应用很少。然而，我相信它的潜力很大，所以在这里向大家简单地介绍了线性规划的一些应用，以及如何实现解线性规划，以抛砖引玉，希望线性规划能够在竞赛中如同网络流一样熠熠生辉。本文主要分三部分，第一部分简单地介绍了线性规划，给出了其定义；第二部分给出了一些简单的应用，以及一个线性规划的经典应用——多物网络流；第三部分是用单纯形（Simplex）算法实现解线性规划。由于对大多数竞赛选手而言，写一个线性规划的程序
2、比构造一个模型更为恐怖（虽然难度可能不及），并且单纯形法不是多项式级别的，不实践很难知道它的速度到底怎么样，所以本文着重于第三部分，较详细地描述了一些实现的细节，以及简单的证明，并且对单纯形法的运行速度做了一些实验，还与专业的数学软件MATLAB和LINDO做了对比，从一定程度上说明了单纯形法的速度是卓越的。同时，200行左右的程序可以让大家不必那么担心编程的复杂度，某些情况下，100行左右的程序就足够了。关键字线性规划（Linearprogramming）单纯形法（Simplex）多物网络流（Multicommodi
3、tyflow）引言“随著强有力的算法的发展与应用,线性规划能解决的问题也越来越来多。在历史上，没有哪种数学方法可以像线性规划那样，直接为人类创造如此巨额的财富，并对历史的进程发生如此直接的影响。”孙捷，这位曾经执教于清华大学的美国华盛顿大学博士如此评价线性规划。他还举了这样一个实例：在波斯湾战争期间，美国军方利用线性规划，有效地解决了部队给养和武器调运问题，对促进战争的胜利，起了关键的作用。难怪人们说，因为使用炸药，第一次世界大战可说是「化学的战争」；因为使用原子弹，第二次世界大战可说是「物理的战争」；因为使用线性规划
4、，波斯湾战争可称为「数学的战争」。线性规划在实际生活当中的威力已毋庸质疑，但是在信息学竞赛中，他的光芒还没有闪耀在我们的眼前，让我们通过学习和了解，去渐渐感受它的光彩。正文第一部分简介与定义我们会遇到很多这样的问题：他们需要使目标最大化或者最小化；他们通常面临资源或者其它方面上的限制，或者必须在某些方面进行取舍而不能兼顾。如果这些问题的目标可以表示成一个线性的函数，它们的限制或者取舍可以表示成一些线性的等式或者不等式，那么我们就可以将这些问题描述成线性规划的问题。首先来看一个实例：假如你要竞选市长。要当上市长，你必须有
5、5万的城市居民的投票、10万郊区居民的投票以及2.5万农村居民的投票。你有以下四种方案使你获得更多的投票：1.建设道路2.加强枪支管制3.发放农业津贴4.减免油税农村郊区城市－2010减免油税1000农业津贴－528枪支管制35－2建设道路并且，你对上述四种方案进行了评估，得到了在某一方案上开支的钱和某一区域内选民票数的变化的关系，如下表。表格中的某一项表示在对应方案上每开支1万元，对应区域中选票增加的数量，以千张为单位。比如第一行第一列-2代表在建设道路上每增加1万元的支出，会减少2千人的城市居民选票；第一行第二列5
6、表示在建设道路上每增加1万元支出，会增加5千人的郊区居民选票；第二行第三列表示在枪支管制上每增加1万元支出，会减少5千人的农村居民选票。你要用最少的支出来获得足够的选票当上市长，假设初始时，你的投票数都为0。这个问题的目标是要求开支最小，它的限制是选票必须达到最低限制，取舍关系是为了增加一个区域的居民投票而在一个项目上投资，可能会造成其它区域的居民投票减少。当然，这个问题还有一些潜在的限制，比如支出不能为负。下面，我们把它描述成一个线性规划问题：假设4种项目的支出分别为x1、x2、x3、x4万元，目标：最小化x1+x2
7、+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=线性等式或者不等式：
8、如果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,y
