数学1108徐祖仪(线性规划求解算法研究)

1、摘要 线性规划是运筹学中应用最广泛的一个分支本文主要是针对线性规划问题的相关算法进行了综述和原理的讲解分别阐述了线性规划的发展历程和线性规划的数学模型,详细研究了单纯形法和内点法的主要原理和算法,并为后续研究提供了一个借鉴方向最后给出了线性规划问题的原-对偶内点算法,通过数值实验表明该算法具有很好的收敛性与稳定性关键词:线性规划,单纯形法,内点法，原-对偶内点法Abstract Linear programming is widely applied in all branches of Operation ResearchThis paper mainly describes the rel

2、evant algorithm of linear programming problem and explains their principleThe development of linear programming and the mathematical model of linear programming algorithm are described respectivelyThe main principles of simplex method and interior point methods are analyzed in detail which provide a

3、 reference direction for the follow-up study Finally,we give numerical examples about the primal- dual interior point algorithm for linear programming,the numerical experiment results show that the algorithm has perfect convergence and stabilityKey words：Linear programming,simplex method, Interior p

4、oint methods, Primal-dual interior point method 目录1. 引言11.1 课题背景11.2 发展状况11.3 课题内容22. 线性规划问题和数学模型22.1 线性规划问题及其表示22.2 线性规划基本定理32.3 约束标准型线性规划问题42.4 将一般问题转化为约束标准型4241 目标函数是求最小值4242 约束方程为不等式4243模型中的某些变量没有非负限制53. 单纯形法63.1 单纯形法的基本原理63.2 单纯形算法计算步骤73.3 MATLAB中求解线性规划问题83.4 应用实例93.5 单纯形法的进一步讨论123.5.1 一般线性规划问题

5、的2阶段单纯形算法123.5.2 退化情形的处理124. 内点法134.1 内点法的基本原理135. 原-对偶内点算法155.1 基本原理155.2 算法的具体步骤155.3 应用实例16参考文献191. 引言1.1 课题背景 线性规划是运筹学中应用广泛的一个重要分支，是合理利用、调配资源的一种应用数学方法在日常的生产实践中，如何取得最大的经济效益是我们十分重视的问题要提高经济效益一般可以通过两种途径：一是改进技术，例如改善生产工艺，使用新设备和新型原材料二是改进生产组织与计划，即合理安排人力物力资源而线性规划的基本思路就是在满足一定的约束条件下，使预定的目标达到最优它研究的内容可大致分为两个

6、方面：一是在一定的资源条件下，如何分配能使任务完成得最好如最高产量、最大利润等问题；二是任务量一定时，如何统筹安排，以最少的资源完成这项任务如最低成本、最短距离等问题前者和后者分别是求极大值和极小值问题总之, 线性规划就是在一定限制条下, 求目标函数极值的问题自1947年丹捷格研究出线性规划问题的求解算法单纯形法之后，线性规划在理论上趋向成熟，在实用中日益广泛与深入特别是随着计算机技术的发展，线性规划的适用领域更为广泛，它已成为人们为合理利用有限资源制定最佳决策的重要工具 1.2 发展状况 线性规划求解算法的研究和发展经历了3个重要时期，每一个时期的发展都受到极大的关注自1947年丹捷格提出了

7、单纯形法，凭着成熟的算法理论和完善的算法，它统治线性规划长达30多年单纯形法的基本原理是从一个初始解出发，通过反复迭代改进现有的解，直到得到需要的最优解单纯形法以它简单、实用的特点成为目前常用的方法 然而，在1972年有数学家揭示了单纯形算法的时间复杂度可能是指数型的问题从计算复杂性来看，单纯形算法不是一种好算法于是很多计算机科学家和数学家对线性规划是否存在多项式算法十分感兴趣 1979年前苏联数学家哈奇扬提出了计算复杂性为的椭球算法，它是第1个理论上优于单纯形法的所谓多项式时间算法，但遗憾的是广泛的数值试验表明椭球算法的计算比单纯形方法差 1984年，印度数学家卡玛卡尔提出了另一个计算复杂性

8、为的多项式时间算法，这个算法从理论和数值上都优于椭球算法，因而受到学术界的高度重视此后，许多学者致力于改进和完善这一算法，得到了许多改进算法这些算法运用不同的思想方法均获得通过可行区域内部的迭代点列，因此统称为解线性规划问题的内点算法虽然内点算法的理论比较成熟，但因为初始内点难以找到，所以应用起来还是有难度，内点算法的研究也始终停留在理论上1989年，Renato D.C.Monteiro和I.Adler给出了求解线性规划一个原-对偶内点法其迭代次数为,计算复杂性为,这是目前理论上最好的求解线性规划的多项式算法由于该算法对初始点的要求很严格这就给数值实验带来更大的困难 为了克服内点算法的不足，

9、从20世纪年90代开始学者着重于线性规划的不可行内点算法的研究不可行内点算法又称之为外点算法， 1.3 课题内容近十年来, 随着计算机和算法理论的发展, 准确快速地解决大规模线性规划问题已成为可能提到线性规划算法，人们最先想到的是单纯形法和内点法单纯形法是实际应用中使用最普遍的一种线性规划算法，而研究者们已证明在最坏的情况下单纯形法的计算复杂度是指数级的，内点算法的计算复杂度是多项式时间的把两种算法相提并论，要么是这两种算法都已经非常完备，要么都有需改进之处显然不属于前者，即两者都有需要改进之处本文分析了线性规划问题，给出了求解线性规划问题的单纯形法和内点法最后给出了线性规划问题的原-对偶内点

10、算法, 数值实验表明该算法具有很好的收敛性与稳定性2. 线性规划问题和数学模型2.1 线性规划问题及其表示 线性规划问题可表示为如下形式： s.t. 上面各式中，是个独立变量 式（2.1）是线性规划问题的目标函数目标函数极小值的线性规划问题也可以转换为与之等价的求目标函数极大值的线性规划问题 式（2.2)式（2.5)是线性规划问题的约束条件式（2.2)有个不等式约束；式（2.3)有个不式约束；式（2.4)有个不等式约束约束的总个数为所有约束的右端参数规定为非负数，即，式（2.5)是线性规划问题的变量非负性约束条件 目标函数和约束条件都为线性函数，所以称为线性规划问题线性规划问题是在一组线性规划

11、条件的限制下，求一线性目标函数最大或最小值的问题 变量满足约束条件式（2.2)式（2.5)的一组值称为线性规划问题的一个可行解所有可行解构成的集合称为线性规划问题的可行区域使目标函数取得极值的可行解称为最优解在最优解处目标函数的值称为最优值有些情况下可能不存在最优解通常有两种情况： (1)根本没有可行解，即给定的约束条件之间是相互排斥的，可行区域为空集； (2)目标函数没有极值，也就是说在维空间中的某个方向上，目标函数值可以无限增大，而仍满足约束条件，此时目标函数值无界 下面给出线性规划问题的一个具体例子 （2.6） s.t （2.7） 例子中，这个问题的解为 ；最优值为16下面将详细讨论如火

12、如何求解2.2 线性规划基本定理 使约束条件式（2.2)式（2.5)中的某n个约束以等号满足的可行解称为线性规划问题的基本可行解若，则基本可行解中至少有个分量为0，也就是说，基本可行解中最多有个分量非零线性规划基本定理：如果线性规划问题有最优解，则必有一基本可行最优解上述定理的重要意义在于，它把一个最优化问题转化为一个组合问题，即在式（22)式（2.5)式的个约束条件中，确定最优解应满足其中哪个约束条件的问题由此可知，只要对各种不同的组合进行测试，并比较每种情况下的目标函数值，就能找到最优解 2.3 约束标准型线性规划问题当线性规划问题中没有不等式约束式(2.2)和式(2.4)，而只有等式约束

13、式(2.3)和变量非负约束式(2.5)时，称该线性规划问题具有标准形式为便于讨论，不妨先考察一类更特殊的标准形式线性规划问题这一类线性规划问题中，每一个等式约束中，至少有一个变量的系数为正，且这个变量只在该约束中出现在每一约束方程中选择一个这样的变量，并以它作为变量求解该约束方程这样选出来的变量称为左端变量或基本变量，其总数为个剩下的个变量称为右端变量或非基本变量这一类特殊的标准形式线性规划问题称为约束标准型线性规划问题虽然约束标准型线性规划问题非常特殊，但是对于理解线性规划问题的算法是非常重要的稍后将看到，任意一个线性规划问题可以转换为约束标准型线性规划问题对于任何约束标准型线性规划问题，只

14、要将所有非基本变量都置为0，从约束方程式中解出满足约束的基本变量的值，可求得一个基本可行解2.4 将一般问题转化为约束标准型2.4.1目标函数是求最小值若要求目标函数实现极小化，即这时只需将目标函数最小化变换为求目标函数最大化，即令于是得到必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号2.4.2 约束方程为不等式 需要把(22)或(24)形式的不等式约束转换为等式约束具体做法是引入松弛变量，利用松弛变量的非负性将不等式转化为等式松驰变量记为，共有个在求解过程中，应当将松弛变量与原来变量同样对待求解结束后，抛弃松弛变量注意松弛变量前的符号由相应的原不等式的方向所确

15、定为了进一步构造标准型约束，还需要引入m个人工变量，记为至此，原问题已经变换为等价的约束标准型线性规划问题例2.1 将下列不等式约束转换为标准型约束 解：引入松弛变量 引入人工变量 2.4.3 模型中的某些变量没有非负限制若某个变量可正可负，这时可以令 ，其中，即用两个非负变量之差来表示一个无符号限制的变量，当然的符号取决于和的相对大小，这样就可以满足标准型的要求3. 单纯形法3.1 单纯形法的基本原理单纯形算法的基本思想就是从一个基本可行解出发，进行一系列的基本可行解的变换每次变换将一个非基本变量与一个基本变量互调位置，且保持当前的线性规划问题是一个与原问题完全等价的标准线性规划问题单纯形表

16、：为基本变量， 为非基本变量基本变量下标集为B=1,2,m； 非基本变量下标集为N=m+1,m+2,n；当前基本可行解为（）表格 3-1 当前单纯形表xm+1xm+2xnzc0cm+1cm+2cnx1b1a1m+1a1m+2a1nx2b2a2m+1a2m+2a2nMMxmbmamm+1amm+2amn 单纯形算法的第1步：选出使目标函数增加的非基本变量作为入基变量查看单纯形表的第1行（也称之为z行）中标有非基本变量的各列中的值，依次让每一非基本变量从当前值开始增加，同时保持其余非基本变量仍为0；然后考察变化结果，看目标函数值是增加还是减小考察的目的是选出使目标函数增加的非基本变量作为入基变量容

17、易看出z行中的正系数非基本变量都满足要求单纯形算法的第2步：选取离基变量在单纯形表中考察由第1步选出的入基变量所相应的列在基本变量变为负值之前，查看入基变量可以增到多大如果入基变量所在的列与基本变量所在行交叉处的表元素为负数，那么该元素将不受任何限制，相应的基本变量只会越变越大如果入基变量所在列的所有元素都是负值，则目标函数无界，说明已经得到了问题的无界解如果选出的列中有一个或多个元素为正数，那么就要弄清是哪个数限制了入基变量值的增加显然，这一受限的增加量可以用入基变量所在列的元素（称为主元素）来除主元素所在行的“常数列”（最左边的列）中元素而得到所得到数值越小说明受到限制越多因此，应该选取受

18、到限制最多的基本变量作为离基变量，才能保证将入基变量与离基变量互调位置后，仍满足约束条件 单纯形算法的第3步：转轴变换转轴变换的目的是将入基变量与离基变量互调位置给入基变量一个增值，使之成为基本变量；同时修改离基变量，让入基变量所在列中离基变量所在行的元素值减为零，并使之成为非基本变量单纯形算法的第4步：转回并重复第1步，进一步改进目标函数值不断重复上述过程，直到z行的所有非基本变量系数都变成负值为止这表明目标函数不可能再增加了3.2 单纯形算法计算步骤 单纯形算法的计算过程可以用单纯形表的形式归纳为一系列基本矩阵运算主要运算为转轴变换，该变换类似解线性方程组的高斯消去法中的消元变换 单纯形算

19、法计算步骤如下： 步骤1：选入基变量 如果所有，则当前基本可行解为最优解，计算结束否则，取相应的非基本变量为入基变量 步骤2：选离基变量 对于步骤1选出的入基变量，如果所有，则最优解无界，计算结束否则,计算选取基本变量为离基变量 新的基本变量下标集为新的非基本变量下标集为 步骤3：作转轴变换 新单纯形表中各元素变换如下 （31） （32） （33） （34） 步骤4：转步骤13.3 MATLAB中求解线性规划问题MATLAB解决的线性规划问题的标准形式为：min s.t. 其中f、x、b、beq、lb、ub为向量，A、Aeq为矩阵其它形式的线性规划问题都可经过适当变换化为此标准形式Matlab

20、优化工具箱中有现成函数linprog对的LP问题求解函数 linprog 的调用格式 x = linprog(f,A,b) %求min f ' *x subto 线性规划的最优解 x = linprog(f,A,b,Aeq,beq) %等式约束，若没有不等式约束，则A= ，b= x = linprog(f,A,b,Aeq,beq,lb,ub) %指定x的范围，若没有等式约束 ，则Aeq= ，beq= x,fval = linprog() % 返回目标函数最优值，即fval= f ' *x3.4 应用实例例31 用单纯形法求解以下线性规划问题解： ；基本变量为；非基本变量为； 画

21、出单纯形表，如表3-2表格 3-2 单纯形表z0-13-273-1212-24010-438 该问题的一个明显的基本可行解是 惟一的一个值为正的行元素是3，它所在列中有2个正元素，即4和3由于，应该选取为离基变量；入基变量取值为3 解离基变量所相应的方程将入基变量用离基变量表示为再将其代入其他基本变量和所在的行中消去,得到代入目标函数得到形成新单纯形表如表3-3表格 2 新单纯形表3-3z91/2-3/4-2105/21/423-1/21/401-5/2-3/48在上面的单纯形表中，惟一的值为正的z行元素是非基本变量相应的列，其值因此，选取非基本变量作为入基变量它所在列中有惟一的正元素，即基本

22、变量相应行的元素因此，选取为离基变量再经步骤3的转轴变换得到新单纯形表如表3-4所示表格 3-4 新单纯形表2z11-1/5-4/5-12/542/51/104/551/53/102/5111-1/210新单纯形表z行的所有非基本变量系数都变成负值，求解过程结束整个问题的解可以从最后一张单纯形表的常数列中读出目标函数的最大值为11；最优解为:例32 用MATLAB求解下面线性规划问题 min subt 解：先根据MATLAB中解决的线性规划问题的标准形式，写出相应的f、x、b、beq、lb、ub等向量以及A、Aeq矩阵，若没有以 代替，再调用linprog函数求解在Matlab命令窗口或者M文

23、件中输入以下程序：>>clc>>clear>>f = -5; -4; -6;>>A = 1 -1 1;3 2 4;3 2 0;>>b = 20; 42; 30;>>lb = zeros(3,1);>>x,fval = linprog(f,A,b,lb)结果为：x = %最优解 00000 150000 30000fval = %最优值 -78000035 单纯形法的进一步讨论 351 一般线性规划问题的2阶段单纯形算法引入人工变量后的线性规划问题与原问题并不等价，除非所有都是0 为了解决这个问题，在求解时必须分

24、2个阶段进行第一阶段用一个辅助目标函数替代原来的目标函数这个线性规划问题称为原线性规划问题所相应的辅助线性规划问题对辅助线性规划问题用单纯形算法求解如果原线性规划问题有可行解，则辅助线性规划问题就有最优解，且其最优值为0，即所有都为0在辅助线性规划问题最后的单纯形表中，所有均为非基本变量划掉所有相应的列，剩下的就是只含和的约束标准型线性规划问题了换句话说，单纯形算法第一阶段的任务就是构造一个初始基本可行解第二阶段的目标是求解由第一阶段导出的问题此时要用原来的目标函数进行求解如果在辅助线性规划问题最后的单纯形表中，不全为0，则原线性规划问题没有可行解从而原线性规划问题无解352 退化情形的处理用

25、单纯形算法解一般的线性规划问题时，可能会遇到退化的情形，即在迭代计算的某一步中，常数列中的某个元素的值变成0，使得相应的基本变量取值为0如果选取退化的基本变量为离基变量，则作转轴变换前后的目标函数值不变在这种情况下，算法不能保证目标函数值严格递增，因此，可能出现无限循环考察下面的由Beale在1955年提出的退化问题的例子按照2阶段单纯形算法求解该问题将出现无限循环Bland提出避免循环的一个简单易行的方法在单纯形算法迭代中，按照下面的2个简单规则就可以避免循环规则1：设，取为入基变量规则2：设取为离基变量算法leave(col)已经按照规则2选取离基变量选取入基变量的算法enter(objr

26、ow) 中只要加一个break语句即可4 内点法 41 内点法的基本原理 内点法中有一个惩罚函数，用于描述凸集与单纯形法不同，它通过遍历内部可行区域来搜索最优解 线性规划问题描述如下： (4.1)与（4.1）对应的对数型惩罚函数为： (4.2)这里是一个小的正参数，常被称作“惩罚因子”当趋近于0时，将趋近于（41）的解 惩罚函数的梯度为： (4.3)是原始函数的梯度，且是的梯度 除了原始变量x，我们还引入了拉格朗日乘子（有时也称松弛变量）： (4.4)（4.4）有时被称为扰动互补条件，类似于KKT条件中的互补松弛我们试图找到那些使得惩罚函数梯度为0的对比（4.3）与（4.4）我们容易得到一个关

27、于梯度的等式： (4.5)其中，是限制条件的雅克比矩阵 （45）式意味着的梯度应该位于限制条件梯度所张成的子空间中对（44）和（45）应用牛顿法我们得到：其中，是的黑塞矩阵，是的的对角矩阵 因为（4.1）和（4.4），所以在每次迭代时都必须满足，所以可以通过选择合适的来计算：5 原-对偶内点算法51 基本原理 考虑如下线性规划问题的标准型（P)及其对偶（DP）这里A是的矩阵，且总假设A为行满秩矩阵，b和c分别是m维和n维向量，z是对偶问题中加入的n维松弛变量对原问题和对偶问题做出下面的假设：集合S、T都是非空，其定义如下：且定义为了给出算法，先考虑初始点的选取 令和恒满足下列式子： (5.1)

28、原对偶内点算法要求初始点满足如下准则： (5.2)这里，是欧式范数52 算法的具体步骤步骤1：选取初始点且满足（5.2）式，其中和同时满足（51）；给定终止误差步骤2：若对偶间隙，则停，为（P）的近似解；否则转步骤3；步骤3：令，计算；步骤4：转步骤253 应用实例例51 考虑如下线性规划（P）及其对偶（DP）（DP)中为引入的松弛变量给出一组初始解运算结果见图1例52 考虑如下线性规划（P）及其对偶（DP）（DP)中为引入的松弛变量给出一组初始解运算结果见图1用MATLAB编程例51与例52详细的计算结果见图1 图1原对偶内点算法数值结果 由运算结果可以看出，例51中x越来越趋于最优解，原问题的目标值也趋于f=5例52中x越来越趋于最优解，原问题的目标值也趋于具体程序如下： clear all clc n=3;delt=05316;wucha=0001; A=1 1 2;2 1 3; c=2;1;4; x0=15;05;05; y0=-4;2; z0=2;3;6; k=1;e=1;1;1;x(:,k)=x0; % 将x 赋值给x 的第k 列