noi互讲课1线性单纯形算法

1、线性规划：单纯形算法北师大实验中学 徐明宽目录线性规划概述标准型与松弛型单纯形是什么？单纯形算法概述单纯形算法终止性线性规划对偶性与单纯形算法最优性（正确性）例题时间复杂度初始基本可行解线性规划基本定理一些题外话线性规划概述线性规划（Linear programming,简称LP）是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。（百度百科）线性规划问题形如：有n个变量，m个关于这些变量的线性（一次）等式或不严格（带=）不等式，求一组满足这些约束的可行解，使得某个关于这些变量的线性表达式取到最大/最小值。引例引用高中数学必修五中的例子。某

2、工厂计划生产甲、乙两种产品，生产甲(每份)需要A原料3kg和B原料1kg可以获利30元，生产乙(每份)需要A原料2kg和B原料2kg可以获利40元。现有A原料1200kg、B原料800kg，问生产甲、乙各多少份可以使利润最大？最大是多少？引例max 30 x + 40y3x + 2y = 1200 x + 2y = 0标准型已知n个实数c1cn，m个实数b1bm，mn个实数aij（a11amn)，求n个实数x1xn，最大化满足约束cxaxbx0练习1将最短路和最大流问题转化为线性规划。当然我们以后遇到它们时肯定不会转化成线性规划再求解的将线性规划转换为标准型1、如果要最小化目标函数，将其乘上-

3、1即可改为最大化。2、如果某个变量不具有非负性约束，将其改为两个非负变量的差。3、如果存在一个等式约束，改为一个“”和一个“”。4、如果有“”，将其乘以-1改为“”。松弛型在标准型的基础上，对于每一个（不是非负性约束的）约束引入一个新的变量s，并将这个约束重写为称s为松弛变量，因为它衡量了这个约束不等式两边的松弛（差别）。松弛型设初始的m个松弛变量为基本变量，用B来表示基本变量下标的集合；初始的n个变量为非基本变量，用N来表示非基本变量下标的集合。用v表示目标函数中的常数。则一个松弛型线性规划可以表示为：引例max 30 x1 + 40 x2x3 = 1200 - 3x1 - 2x2x4 =

4、800 - x1 - 2x2x1, x2, x3, x4 0单纯形是什么？如果有两个变量，那么每个约束可以看做一个半平面，它们的交是可行区域。如果有三个变量，那么每个约束可以看做一个半空间。如果有n个变量，每个约束可以看做n维空间的一个半空间。这些半空间的交集形成的可行区域称为单纯形（simplex）。目标函数可以看做一个超平面。由于单纯形的凸性，一定有一个最优解在单纯形的一个顶点上取得。单纯形算法概述单纯形算法是求解线性规划问题的通用方法，是美国数学家G.B.丹齐克于1947年首先提出来的。（百度百科）高斯消元法从解未知的一个线性等式开始，在每次迭代中将这个系统重写为一个等价形式。经过若干次

5、迭代后，这个系统的解很容易得到。从某种意义上说，单纯形算法可以看做不等式上的高斯消元法。单纯形算法概述首先我们要把线性规划转化为松弛型。定义“基本解”为所有非基本变量为0的解。一个基本解总是对应于单纯形的一个顶点。一次迭代将一个松弛型转化为一个等价的松弛型，并且v不降，使得若干次迭代后基本解足够好。我们选择一个满足cj0的非基本变量xj，从0开始增加这个变量的值，直到某个基本变量变为0。然后重写松弛型，将这个基本变量和非基本变量xj的角色互换。引例max 30 x1 + 40 x2x3 = 1200 - 3x1 - 2x2x4 = 800 - x1 - 2x2增加x1，最多可增加到400()，

6、此时x3为0。所以我们换出x3，换入x1。x1 = 400 - 1/3x3 - 2/3x2代入，x4 = 400 + 1/3x3 - 4/3x2代入，max 12000 - 10 x3 + 20 x2引例max 12000 - 10 x3 + 20 x2x1 = 400 - 1/3x3 - 2/3x2x4 = 400 + 1/3x3 - 4/3x2增加x2，最多可增加到300()，此时x4为0。x2 = 300 + 1/4x3 - 3/4x4代入，x1 = 200 - 1/2x3 + 1/2x4代入，max 18000 - 5x3 - 15x4中所有系数0，迭代结束。练习2max 3x1 +

7、x2 + 2x3x1 + x2 + 3x3 302x1 + 2x2 + 5x3 244x1 + x2 + 2x3 36x1, x2, x3 0终止性我们提到过在每次迭代中v不降。大部分情况下v严格递增，然而v有可能不变。max x2 - x3x4 = 8 - x1 - x3x5 = x1 - x2退化是唯一可以让单纯形算法不终止的方式。如果两次不同迭代中的松弛型相同，则算法出现了循环。总是选择具有最小下标的变量可以避免循环，这个策略叫做Bland规则。证明从略。小结维护矩阵a、向量b、（转置）向量c、实数v，使得对于向量x：max v + cxax = bx = 0现在我们应该已经可以做一部分

8、简单的线性规划题目了。在此之前，我们先来证明单纯形算法的正确性（接下来的证明没有错，但是还是留了个小bug）。练习3max 18x1 + 12.5x2x1 + x2 = 20 x1 = 12x2 = 0对偶性给定一个标准型线性规划定义其对偶线性规划为对于任意可行解x,y有（线性规划弱对偶性）推论如果那么x与y分别是原线性规划和对偶线性规划的最优解。与最大流最小割定理类似。最优性（正确性）设c为simplex后得到的c向量，则对于所有j，cj0。由于最终松弛型等价于初始松弛型，simplex得出的目标函数的值对应到初始松弛型的目标函数的值是相同的，设其为v。设最优对偶解为yi=-cn+i(n+i

9、N)或0(其他情况)练习4min x1 + x2 + x32x1 + 7.5x2 + 3x3 = 1000020 x1 + 5x2 + 10 x3 = 30000 x1, x2, x3 = 0 NOI2008 志愿者招募申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要Ai 个人。 布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用是每人Ci 元。新官上任三把火，为了出色地完成自己的工作，布布希望

10、用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。为了方便起见，我们可以认为每类志愿者的数量都是无限多的。“费用流神题，单纯形裸题”有人愿意把这题的费用流建图过程推一下吗？有人愿意把这题转化成一个线性规划问题吗？（练习5）时间复杂度志愿者招募：N=103，M=104。如果用Dinic的话时间复杂度是O(N2*M)，达到了1010。（网络流管什么时间复杂度）也许你注意到了单纯形算法不循环的话理论上最多迭代C(N + M, M)次（因为只有这么多种状态）不过认为这么大的数并没有什么卵用单纯形算法的时间复杂度现在还不清楚。最高可能为阶乘级(O(N

11、+M)! /(N-1)! /(M-1)!)，在本题的数据范围下约等于103363。最低可能为指数级(O(2n)，1972年有人给出过执行2n-1次迭代的例子。初始基本可行解我们之前定义过“基本解”为所有非基本变量为0的解。然而一个可行的线性规划可能不具有一个可行的初始基本解。max 2x1 - x22x1 - x2 = 2x1 - 5x2 = 0在这种情况下，从一个不可行的解开始迭代是没有意义的。初始基本可行解原线性规划当且仅当辅助线性规划的最优目标值为0时，原线性规划可行。构造辅助线性规划。不过如果原线性规划的初始基本解不可行，显然辅助线性规划的初始基本解也不可行。换入x0，换出xi满足bi

12、 min，则辅助线性规划的基本解一定可行。线性规划基本定理任意一个线性规划，要么有一个有限目标值的最优解，要么不可行，要么无界。练习6多商品流问题有一个有向图，每条边有容量。有k种商品，第i种商品要从源si向汇ti运送di份。这些商品共享同一个网络，即每条边的k种商品的流量和不超过它的容量。求一个可行方案。（*）最小费用多商品流问题一些题外话单纯形算法在之前讲的基础上还有不少可改进的地方。虽然单纯形算法不是多项式时间的，但是线性规划问题是P难度的。椭球法是线性规划的第一个多项式时间算法，于1979年提出，但是极其低效(O(n6*L2)。内点法是另一类线性规划的多项式时间解法，于1984年提出，对于较大的输入规模比单纯形算法更优，一说时间复杂度O(n3.5*L2)。（L是输入规模）一些题外话多商品流问题唯一已知