下载文档原格式
求解线性规划初始可行基的常规算法摘要：本文通过对求线性规划初始可行基的一些常规方法和近年来的主要研究成果进行归纳，简介和总结，并加以比较，给出各种方法的优势与不足．以便读者在解决具体问题时根据自身的实际情况，找出相应的方法，以使达到方便解决所研究的问题．关键词：线性规划；单纯形法；解法1.求线性规划初始可行基的一些的常规算法[1]单纯形法：单纯形解法最初是在20世纪40年代由George Dantzig研究出来的．它的基本思路是：先求得一个初始基可行解，以这个初始基可行解在可行域中对应的极点为出发点，根据最优准则来判断这个基可行解是否是最优解，如果不是最优解,则转换到相邻的一个极点，即得到一个新的基可行解，并使目标函数值下降，这样重复进行有限次后，可找到最解或判断问题无最优解．单纯形法是求解线性规划最基本，最常用的方法，通常情况下，大多数的线性规划问题都可以得以解决。
但不足之处在于单纯形法必须在己知一个基本可行解(初始点)既线性规划的约束方程为G-J方程组的前提下才能进行求解．然而在大多数情况下，线性规划问题并没有明显的初始基本可行解，于是，很多人就提出了多种新的解决思路，给出了求初始基本可行解的许多算法，这些算法各有所长所短．归纳起来，具有代表性的是下面介绍的几种。
[2]大M法：此方法系在目标函数中，加上人工变元与一个很大很大的正数M的积（此称罚函数），这样，当基本可行解中人工变元非0时，此人工变元项将是一个大数，因它在目标函数中被加上，从而此解不可能最优（注意目标函数求极小）．换言之，在迭代中，人工变元会很快出基．说明：若原来的问题为（Ⅰ），而用大M法构造的新方法为（Ⅱ），则（1）设（Ⅱ）有最优解，其中为人工变元：若，则问题（Ⅰ）有最优解 ;若，则问题无解．（2）设（Ⅱ）有无界解：若，则问题（Ⅰ）也有无界解;若，则问题（Ⅰ）无解．还有一点要说明的是：在实际运算中（计算机程序）大M法里的M需适当赋值，若M赋值过大，则容易引起计算误差：而M赋值过小，则影响求解过程的实施．[3]两阶段法：对一般的线性规划，往往很难找到初始基可行解，甚至连有无可行基都难以判定，这时就需要应用两阶段法来求解线性规划．二阶段法就是把解线性规划问题划分为两个阶段，第一阶段求出原问题的一个基可行解或判断原问题可行域为空：第二阶段在得到的基可行解基础上求解原问题．方法如下：第一阶段：人为地在原约束矩阵中增加一些变量使得到单位矩阵，增加的变量称为人工变量，目标函数是人工变量之和．该线性规划一定有最优解，设为：．则可能有三种情形：1）若：在最优解的基变量中，不存在人工变量，即人工变量都是非基变量．则的前个分量便是（LP）的一个基可行解．可进入第二阶段；2）若：在最优解的基变量中，包括某些人工变量，并且最优值．则（LP）的可行域为空，（LP）无解；3）若在最优解的基变量中，包括某些人工变量，但最优值，此时为基变量的人工变量都取值为0．设是一个人工变量的基变量，其在最优解的单纯形表中对应第行，设是非人工变量中非基变量的下标集．如果单纯形表的第行中，所有的，( )此示原约束中第行为其余行的线性组合，即是个多余的约束，应当删去；如果存在( )，则无论是正还是负，以它为变换轴心，进基，离基．如果新表中的基变量中还有人工变量，重复以上步骤，有限次可得到1）的情形．第二阶段：1）以第一阶段最优解对应的单纯形表为基础，删去人工变量对应的列，并且将原规划（已标准化）的作为检验数，放在第一行，然后用用行变换将基变量对应的检验数消为零；2）以步1结束时建立单纯形表为原线性规划的初始单纯形表，求解原线性规划；通常认为，上述两方法相比较，手算时大M法比两阶段法简单，但在编制计算机程序时，由于大M法的赋值成了制约该方法的障碍（赋值太大，引起大误差，太小起不到惩罚作用）．若把大M法中的M视为参数，另在求解过程中把检验数向量分成两部分（且把M看成一个大数），先来考虑人工变元的影响，则大M法实际上已化为两阶段法了．[4]Khachyian多项式算法：该算法又称椭球算法，它是在原苏联学者肖尔关于非线性规划椭球算法基础上提出来的．Khachyian算法可求解线性不等式方程组：，其中是矩阵，和是列向量．没有任何非负约束，也不存在在任何限定的极大化或极小化目标函数，因此，首要的问题是把线性规划问题转换为等价的与（LP）有相同解的不等式方程组，两者都有相同的解．第一步迭代时，以原点为球心，取一个较大的正数为半径（把所有的可行点包括在内）得到一个超球面围成的可行域，选定的被违反的约束方程．超平面通过当前中心原点，与第一个约束的平面平行，割去初始的左半部分．新的椭球体积变小但包含了留下的右半椭球及可行域．重复迭代，直到椭球中心点收敛于可行域．[1][5]Karmarkar多项式算法：1984年Karmarkar提出了解LP问题的另一个由多项式时间的算法．从理论上讲，Karmarkar算法比Khachyian算法的阶有所降低，实算效果也较好．它的基本思想是：不沿可行域多面体（如单纯形法那样）搜索，而是直接穿过多面体每部的某个点开始（解）．Karmarkar算法每次迭代次数上界是 (nl)，这里l是问题的输入规模（问题转换成数码0，1的个数）：此外算法中变换了系数矩阵，运用矩阵计算技巧，使每步迭代（矩阵求逆）的计算是约为 ( )，从而使总算法时间复杂性为（）．此方法的完善与改进，极为人们所关注，且有许多新的方法派生：．投影方法；．仿射均衡尺度法；．路径跟踪法；．仿射均衡势函数方法等．[3]参考文献[1] 杨富贵,梁邦助.求线性规划初始基本可行解的一种直接方法[J],天津商学学报,2002(03):21-25.[2]吴振奎.运筹学[M].北京:中国人民大学出版社,2005:37-46.[3]于庆年,王晓辉.用预备表法寻找线性规划问题第一可行基[J],丹东师专学报,1995(03):8-10.[4]周誓达.线性规划问题求初始可行基一种新的解法[J],首都师范大学学报,1996(04):11-15.[5]曹细玉.求解线性规划问题的新方法及影子价格[J],华中师范大学学报,2000(01):4-8.[6]孟俊婷.求单纯形法中初始基本可行解的新方法-外点法[J],内蒙古科技与经济,2000(02):39-241.[7]肖蓬.求第一个可行基的一种不同的方法[J],福建师范大学学报,2002(02):20-23.[8]安中华,周树民,安琼.线性规划初始基本可行解的新算法[J],武汉理工大学学报,2004(07):72-74.[9]王章雄,陈耀辉.线性规划初始基可行解的一种直接算法[J],数学杂志,1996(02):217-222.[10]吴延东.求线性规划问题可行基的一种方法[J],运筹与管理,1999(01):41-45.[11]孙可钦.寻求线性规划初始可行基的一种新算法[J],云南师范大学学报,1999(04):17-20.[12]严文利.一类线性规划问题初始可行基产生的新方法[J],运筹与管理,2001(02):79-85.4。
工程优化设计中单纯形法的基本原理张云龙（大连海洋大学土木工程学院辽宁大连116023)摘要：从实例出发提出线性规划的数学模型，给出图解法的基本原理，进而重点讲述它的标准解法——单纯形法。
在此基础上进一步讨论单纯形法的推广，即大M法和两相法。
关键词：线性规划图解法单纯形法大M法THE BASIC PRINCIPLES OF SIMPLEX METHOD TO THE ENGINEERING OPTIMIZE DESIGNZHANG Yun-long(Dalian Ocean University, College of Civil Engineering, Liaoning, Dalian 16023)Abstract: From the instance of the starting linear programming mathematical model of the basic principles of the graphic method, and then focus on the standard solution - simplex method. To promote further discussion on this basis, the simplex method, that is, the big M method and two-phase method.Key Words: Linear programming；Graphic method；Simplex Method; Big M Method1引言在工程优化设计问题中，当约束集由一组线性函数所确定时，其最优化问题的求解已有比较系统的技巧。
如果连目标函数也是线性的，也即线性规划问题，则是目前对规划问题研究最透彻最完善的一类问题，而且有比较成熟的解法。
线性规划在工程实例中的应用已相当广泛。
虽然大多数设计问题是非线性的，但对线性规划的研究仍然占据突出地位。
一线性规划图解法1.线性规划的标准形式：(1)目标函数最大；约束条件等式；决策变量非负（x≥0）；资源限量非负（b≥0）。
(2)图解法两个变量系数C1、C2，斜率k=-(C1/C2)(3)图解法K≥0时，绝对值越大越靠近Y轴；K≤0时，绝对值越大越靠近Y轴。
(4)阴影区：无论斜率为正或负，小于的部分阴影区都在线的下方。
二单纯形法1.大M法（1）加入人工变量-Mx i…，M无穷大。
（2）最后将人工变量x i替换出去，且σ≤0.2.两阶段法（1）第一阶段：目标函数为max z′=−x i…，得到最终表。
（2）第二阶段：目标函数替换为原目标函数，在最终表里继续计算σ，直到都小于等于0。
3.单纯表特殊情况的解判断（1）最优解中人工变量大于0，线性规划无解。
（2）某次迭代过程，表中有一个σ＞0，且该列系数向量都小于等于0，线性规划无界。
（因为比较比值大小时都是负的）。
（3）某个非基变量σ=0，无穷解。
（4）退化问题：相同的比值，选择下标大者离基。
σk相同，任选一个入基。
4.初等行变换✓某一行（列），乘以一个非零倍数。
✓某一行（列），乘以一个非零倍数，加到另一行（列）。
✓某两行（列），互换。
三单纯形法灵敏度分析1.对偶问题原问题：max z=cx对偶问题：min f=b T yAx≤b A T y≥c TX≥0 y≥0（1）原问题统一为以上标准型，再进行下一步。
（2）原问题第i个约束条件等号，对偶问题i个决策变量无约束。
（3）原问题第i个决策变量无约束，对偶问题第i个约束条件等号。
（4）原问题的对偶价格为对偶问题的最优解。
（参考习题册第7、19题）（5）对偶价格：常数项增加1单位，目标函数值改进的数量。
（6）影子价格：常数项增加1单位，目标函数值增加的数量。
2.灵敏度分析（1）目标函数变量系数C k:将C k直接代入最终表，判断σ是否小于0。
（2）约束方程常数项b：利用如下公式计算新的最终表中b值。
判断b是否非负。
运筹学课程讲义第一部分线性规划第一章线性规划的基本性质1.1 线性规划的数学模型一、线性规划问题的特点胜利家具厂生产桌子和椅子两种家具。
桌子售价50 元/个，椅子售价30 元/个。
生产桌子和椅子需木工和油漆工两种工种。
生产一个桌子需要木工4 小时，油漆工2小时。
生产一个椅子需要木工3 小时，油漆工1 小时。
该厂每月可用木工工时为120 小时，油漆工工时为50 小时。
问该厂如何组织生产才能使每月的销售收入最大？max z 50x1 30x24x1 3x2 1202x1 x2 50x1,x2 0 例：某工厂生产某一种型号的机床。
每台机床上需要 2.9m、2.1m、1.5m的轴，分别为1根、2根和1根。
这些轴需用同一种圆钢制作，圆钢的长度为74m。
如果要生产100台机床，问应如何安排下料，才能用料最省？二、数学模型的标准型1. 繁写形式2. 缩写形式3. 向量形式4. 矩阵形式若原模型中变量 x j 有上下界，如何化为非负变量？三、 任一模型如何化为标准型？1. 若原模型要求目标函数实现最大化，如何将其化为最小化问题？2. 若原模型中约束条件为不等式，如何化为等式？3. 若原模型中变量 x k 是自由变量，如何化为非负变量？1. 2 图解法该法简单直观，平面作图适于求解二维问题。
使用该法求解线性规划问题时，不必把原模型化为标准型。
一、 图解法步骤1. 由全部约束条件作图求出可行域2. 作出一条目标函数的等值线3. 平移目标函数等值线，作图求解最优点，再算出最优值 max z 5x 1 6x 2 7x 3x 1 5x 23x 3 15 5x 1 6x 210x 3 20 x 1 x 2 x 3 5x 1 0,x 2 0,x 3无约束令 x 1' x 1,x 3 x 3' x 3'',x 3' ,x 3'' 0, Z 1Z ' 1 1 min z ' 5x 1' 6x 2 7x 3' 7x 3'' 0x 5 Mx 6 1 x 1' 5x 2 1 11 3x 3' 3x 3'' x 4 x 6 15 1 5x 1' 6x 2 10x 3' 10x 3'' x 5 20 1 x ' x 1 ' II '' 54.Mx 7 x 1, x 2 , x 3, x 3, x 4 , x 5 ,x 6, x 7 0从图解法看线性规划问题解的几种情况1. 有唯一最优解2. 有无穷多组最优解3. 无可行解4. 无有限最优解（无界解）min z 6x1 4x?2x〔X2 13 最优解（1,0），最优值33x14x2 22x1, x20直观结论：1）线性规划问题的可行域为凸集，特殊情况下为无界域（但有有限个顶点）或空集；2）线性规划问题若有最优解，一定可以在其可行域的顶点上得到。
两阶段法孙敏 枣庄学院考虑线性规划问题0 s.t.min ≥==x bAx cx Z（1）符号说明与教材一致，唯一的不同之处是不要求假设矩阵A 是行满秩的。
在初始基本可行解未知的情况下，可以采用两阶段法。
这种方法的基本思想是：第一阶段在约束中增加人工变量a x ，修改目标函数为极小化人工变量的和，即下面的问题（2），然后用普通单纯形法消去人工变量（如果可能的话），即把人工变量都变换成非基变量，求出问题（1）的一个基本可行解。
第二阶段就从得到的基本可行解出发，用普通单纯法求解问题（1）。
0,0s.t.min ≥≥=+=a a a T x x bx Ax x e W （2）这样，在极小化目标函数的过程中，由于大M 的存在，将迫使人工变量离基。
由于b x x a ==,0是线性规划（2）一个基本可行解，目标函数在可行域上有下界0，因此问题（2）一定存在最优基本可行解。
用单纯形法求解线性规划（2），设得到的最优基本可行解是⎥⎦⎤⎢⎣⎡**a x x ，此时必有下列三种情形之一。
（a ）0*≠a x 。
这时问题（1）无可行解。
因为如果问题（1）有可行解xˆ，则 ⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡0ˆxx x a是线性规划（2）的可行解。
在此点处，问题（2）的目标函数值⎪⎪⎭⎫ ⎝⎛⎥⎦⎤⎢⎣⎡=<==⎪⎪⎭⎫ ⎝⎛⎥⎦⎤⎢⎣⎡***000ˆa a T T x x W x e e x W这与⎥⎦⎤⎢⎣⎡**a x x 是问题（2）的最优解矛盾。
（b ）0*=a x 且*a x 的分量都是非基变量。
这时，m 个基变量都是问题（1）的变量，又知⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡0***x x x a 是问题（2）的基本可行解，因此*x 是问题（1）的一个基本可行解。
转第二阶段。
（c ）0*=a x 且*a x 的某些分量是基变量。
这时，可用主元素消去法，把原来变量中的某些非基变量引进基，替换基变量中的人工变量，再开始第二阶段。
