信息学集训队作业线性

1、线性规划的简单应用与实现浙江省杭州二中李宇骞前言线性规划带来巨额财富方案在历史上，没有哪种数学方法，可以像线性规划那样，直接为人类创造如此巨额的财富，并对历史的进程发生如此直接的影响。孙捷，美国华盛顿大学博士曾执教于北京清华大学 。实例为了要竞选市长，你想以最小的开支拥有5万的城市居民的投票、10万郊区居民的投票以及2.5万农村居民的投票。城市郊区农村建设道路253枪支管制825农业津贴0010减免油税1002实例让x1+x2+x3+x4最小满足： -2x1+8x2+0 x3+10 x4 = 50（城市居民投票不少于5万）5x1+2x2+0 x3+0 x4 = 100（郊区居民）3x1-5x2

2、+10 x3-2x4 = 25（农村居民）x1, x2, x3, x4 = 0（开支不能为负）建设道路的开支枪支管制上的开支定义线性规划：在满足一些线性等式或者不等式的条件下，最优化一个线性函数。x1+x2+x3+x4-2x1+8x2+0 x3+10 x4 = 50 x1 =0 x2=4x1+5=x2应用资源优化配置有一些资源和产品，在资源有限的情况下如何将其分配给这些产品使得获利最大。最佳物资供给有一些需求要满足，如何在保证满足的前提下，提供最少价值的物资。多物网络流有多个源点和汇点的网络流多物网络流源点1源点2汇点1汇点2算法单纯形法(Simplex)椭球法（Ellipsoid)内点法(I

3、nterior-point)多项式级别LindoMatlab单纯形法标准形式(Standard form)最大化x1+x2+x3+x4目标函数要求最大化满足：x1+2x2+3x3 = 3x4 = 0所有的变量都有非负限制单纯形法标准形式(Standard form)mnacb单纯形法标准形式(Standard form)最大化共n+m个约束，除了n个变量的非负限制外，还满足m个约束，第j个约束为单纯形法形象的理解最优值在某一顶点上用调整法，从一个顶点出发，直到到达一个最优值。单纯形法主程序初始化：首先找到一个顶点最优化：不断调整，直到最优化单纯形法顶点松弛形式一个顶点对应一个松弛形式单纯形法n

4、维空间中的一个顶点n个数的坐标n个n元一次方程组的解n个不等式取等号单纯形法松弛形式（Slack form)将n+m个不等式和n+m个变量一一对应x1=0 xn=0 x1=0 xn=0 xn+j=0第i个不等式取等号时就是xi=0单纯形法松弛形式（Slack form）n维空间中的一个顶点n个不等式取等号n个变量取0N单纯形法松弛形式（Slack form）NN点点松弛形式松弛形式单纯形法转轴操作（Pivot）n-1个等式确定一条边调换N中的某一个元素沿着另外n-1个等式所确定的边到达另一个点单纯形法回顾主程序松弛形式转轴操作单纯形法时间复杂度最多有 个松弛形式贪心优化对于所有有可能的边，选一

5、条使v变得最大的边走。实验 变量个数n限制个数m5010050我的程序 小于1秒MATLAB7.0 小于1秒LINDO 小于1秒我的程序 小于1秒MATLAB7.0 17秒LINDO 小于1秒100我的程序 小于1秒MATLAB7.0 17秒LINDO 小于1秒我的程序 小于1秒MATLAB7.0 30秒LINDO 小于1秒实验 变量个数n限制个数m200300200普通程序： 8秒，pivot操作5396次加贪心优化的程序： 1秒，pivot操作336次LINDO： 1秒，迭代次数558普通程序： 11秒，pivot操作5310次加贪心优化的程序： 1秒，pivot操作349次LINDO： 1秒，迭代次数578300普通程序： 28秒，pivot操作7864次加贪心优化的程序： 2秒，pivot操作485次LINDO： 2秒，迭代次数819普通程序： 105秒，pivot操作18243次加贪心优化的程序： 7秒，pivot操作947次LINDO： 7秒，迭代次数1369实验 变量个数n限制个数m400500400加贪心优化的程序： 23秒，pivot操作1368次LINDO： 17秒，迭代次数2487加贪心优化的程序： 22秒，pivot操作1078次LINDO： 11秒，迭代次数1770500加贪心优化的程序： 36秒，pivot操作1521次LINDO： 24秒，迭代次数