单纯形法及其应用

1、单纯形法及其应用摘要单纯形法是一种主要的解决线性规划问题的方法，它在生活的成本问题、交通选择或规划学术问题等方面得到广泛应用.本文系统的研究了单纯形法的相关概念以及原理并阐述了用单纯形法解决线性规划问题的步骤与方法及不同方法的特殊性.正确的应用单纯形法解决问题能够提高准确率，从而进行合理的规划安排，使得效果或收益达到期待化或最优化.关键词：单纯形法；单纯形表；最优性TheSimplexMethodanditsApplicationAbstract:Simplexmethodisamaintosolvelinearprogrammingproblems,itinlifecost,thechoic

2、eoftrafficoracademicplanningproblemsarewidelyused.Thispaperstudythesimplexmethodoftherelatedconceptsandprinciples.Itdescribesthestepsandmethodstousesimplexmethodtosolvelinearprogrammingproblems,andthedifferentmethod.Correctapplicationofthesimplexmethodproblemsolvingisabletoimprovetheaccuracy,inorder

3、tocarryoutreasonableplanningarrangements,makestheeffectorincomereachedexpectationsoroptimization.Keywords:simplexmethod;simplextableau;optimality1 引言12 文献综述12.1 国内外研究现状12.2 国内外研究现状评价22.3 提出问题23 单纯形法的相关概念及原理23.1 线性规划问题解的相关概念23.2 初始基可行解的确定43.3 最优性检验与解的判定44 单纯形法的计算54.1 单纯形表的计算步骤54.1.1 单纯形表54.1.2 计算步骤74

4、.2 人工变量94.2.1 大M法104.2.2 两阶段法124.3 单纯形法的改进一一对偶单纯形法155 单纯形法在实际问题中的应用176 结论196.1 主要发现196.2 启示196.3 局限性196.4 努力方向20参考文献211引言线性规划问题算运筹学中比较早开始研究，在研究过程中发展比较快，在现实生活和学术领域应用比较广泛，研究、解决方法比较成熟的一个不可缺少的分支，随着社会的发展，线性规划也成了人们在解决问题时应用的一种数学方法，它主要应用于数学管理问题的解决中.例如社会经济、交通选择、工业、农业生产等活动中.人们为了提高回报或收益从而对已有的人力、资源、物力等进行合理的的规划安

5、排，使得效果或收益达到期待化或最优化.在解决线性规划问题时，通常应用的方法有图像法和单纯形法等.而应用最多、最有效的方法为单纯形法.单纯形法是一种解决线性规划问题的有效方法，它的应用原理方法为：把线性规划问题的解的可实施部分看做一个n维向量空间Rn中的凸集，由此可得线性规划问题存在最优值那么此最优值只能在凸集的顶点处.既然最优值在顶点处，我们就把所有顶点看做一个集合，先在这个集合里面挑选出一个顶点的值，对它进行判别，判别是否为最优值；如果判别结果不是最优值，那么就用一些方法把这个顶点的值转换为另外一个更可能为最优值的顶点值，依次进行判别，因为顶点有限，所以都可以转换出最终的结果，从而达到解决问

6、题的要求，线性规划问题中没有最优的解也可以利用单纯形法进行计算判别.因此，单纯形法对于解决线性规划有非常重要的地位.单纯形法是一种解决线性规划的方法，只有在线性规划问题中才能更好展现，在本文中，我首先就单纯形法所涉及到的一些线性规划的基本概念、解的定义、专业名词等做出简要说明，然后在典型的线性规划中充分揭示单纯形法的步骤、方法及应用，旨在开阔人们分析线性规划问题的思路，加强人们实施实际问题的能力.2文献综述2.1 国内外研究现状现查阅到的参考文献中，分别就单纯形法的综述及其在解决线性规划问题中的应用做出说明.敖特根、章学仁在1-2中强调单纯形法在线性规划中的产生与发展的重要性燕子宗等在3中给出

7、了一种新的原对偶单纯形法.郭照庄等在4-5中详细阐述单纯形法的基本原理.赵娜、唐帅等在6-7中针对如何使用大M法和两阶段法实现某一线性目标最优化问题作出详细说明.胡运权在文献8中针对单纯形法的基本知识和应用做出阐述.文献9中，马振华举例说明单纯形法在解决不同线性规划问题中的应用及规律.文献10中刘红英等对单纯形法的计算机算法进行了说明.邓成梁等在11-15中对单纯形法的迭代步骤与解的讨论进行研究，而且也对单纯形法的具体求解做出的研究.2.2 国内外研究现状评价文献1-15分别就单纯形法的解题步骤及单纯形法在线性规划问题解题中的意义举例作了说明，文献中主要阐述一种或几种单纯形法在线性规划解题中的

8、应用，没有全面地介绍常用单纯形法在不同线性规划问题的应用及解题步骤，而且文献中对怎样应用单纯形法解决线性规划问题提及甚少，对应用中存在的问题也未给出详细深入的说明，以及遇到现实问题时，单纯形法的具体用法及计算机应用方法未有太多涉及.2.3 提出问题单纯形法的在线性规划中有广泛的应用，但是大部分书本只介绍了一些基础知识或讲解线性规划时一带而过.因此，除对解决线性规划问题过程中被一带而过单纯形法作出介绍外，还需要对应用单纯形法解决问题过程中可能遇到的困难、不理解及解决办法作出探讨，包括对使用不同单纯形法的目的、作用、要求作阐述.体会在不同题中单纯形法的不同应用，总结概括以指导方便快捷地解决问题.3

9、单纯形法的相关概念及原理3.1线性规划问题解的相关概念线性规划问题是需要用单纯形法解决的一类问题，所以我们在研究讨论单纯形法时是基于线性规划的基础之上，利用单纯形法使线性规划问题简单、清楚的得出结果是我们的最终目的.一般线性规划问题化为标准式是利用单纯形法求解线性规划问题的基本步骤，对于单纯形法能否顺利得出结果，也有很大联系，在解题过程中，应该谨记变量,目标函数，约束条件的相关要求.线性规划问题的标准形式为：n目标函数maxz="CjXjj1n11aijXj=bii=1;,m约束条件s.t小jjXj-0j=1;,n我们不难看出上式的三个特点：(1)有决策变量：Xj_0;j=1,-，m

10、.(2)有目标函数，：max或min,一般多用max.两者可以互换，即maxzumin(-z).(3)有约束条件，通常为等式，对于“或“之”型的约束条件，可以添加变量转换成等式约束条件，添加的变量称为松弛变量，在目标函数中，松弛变量相对应的系数为0.例如：4x15x2-x3三15；4x15x2-x3人=152%-6x23x3-20>2x1-6x23x3-x5=20在利用单纯形法进行计算时，对于线性规划的解的相关概念也需要牢记，在接下来的单纯形法格式中，是以基本概念的求解为基础.线性规划解的概念对于不同元素的换入、换出等都有影响.下面将介绍线性规划问题解的概念：1、可行解：可以满足全部约束

11、条件的解X=(X,，又称为线性规划问题的可行解.可行解的集合，称为可行域.2、最优解：最符合题目要求的解，在可行域中，能够使目标函数取得最大值的可行解称为最优解.最优解一定是可行解.3、基：设A为约束方程组的mn阶系数矩阵(设nam),基为A的满秩子矩阵mxm矩阵.4、基可行解：满足变量非负约束条件的基解叫做基可行解，最优解一定是基可行解.5、可行基：对应于基可行解的基称为可行基3.2初始基可行解的确定我们说单纯形法是一种迭代算法.所以我们在迭代时需要确定每一次迭代的对象，特别是在进行第一次迭代前，我们必须确定好对象才能使单纯形法的迭代顺利进行.第一次迭代的对象我们称为初始基可行解.为了确定初

12、始基可行解，首先要找出初始可行基.找出初始可行基的方法为：(1)有的线性规划问题中能直接观察得到一个初始可行基：100010B=但0，.am：-001_(2)如果所有约束条件是“W”的不等式，在化为标准形式后，可以重新对变量和变量系数进行编号，得到一个mm的单位矩阵100010B=(a1,a2；.am)=;：:-001_此时单位矩阵B可作为可行基.再将标准形式下的名束条件移项为X1,X2，Xm在同一边的等式，再令Xm噌=Xm=-'=%=0,可得为=。(i=1,2，m),就此得到一个初始TT基可行解X=|b,b2,，bm,0,0.n5(3)如果所有约束条件是“之”的不等式，及等式约束情况

13、不存在单位矩阵时，就采用人工造基方法.即对不等式约束中减去一个非负的变量后，再加上一个非负的人工变量；对于等式约束一样加上一个非负的人工变量，就可以得到一个单位矩阵.3.3最优性检验与解的判定线性规划问题解的结果有以下四种情况：唯一最优解、无穷多最优解、无界解和无可行解.在用单纯形对线性规划进行迭代的过程中，对于什么样的情况使得线性规划有解或无解、什么样的情况线性规划达到最优，这就需要进行最优性检验与解的判定.所以对于线性规划的解需要建立判定准则.(1)最优解的判定设xf)=(b；,b2，b'm,0,0T为一个基可行解，并且对于一切j=m+1,，n都有检验数5=ckzk=maxLjCj

14、|j=1,2,，nk0,则可以判定在该线性规戈(J问题中X(°)为最优解.(2)无穷多最优解的判定设xC)=(b'i,b'2,，b'm,0,0T为一个基可行解，并且对于一切j=m+1,，n都有检验数5=Ck-Zk=maxZj-Cj|j=1,2,，n<0,同时又存在某个非基变量的检验数北=0,则可以判定该线性规划问题有无穷多最优解.(3)无界解的判定设xf)=(b1,b2,，b'm,0,，0T为一个基可行解，有检验数仃m*>0,并且对于i=1,2m有a,m衣<0则判定该线性规划问题有无界解也称之为无最优解.4单纯形法的计算利用单纯形表时

15、，我们首先要了解什么是单纯形表，它有什么样的特点、规则等，其次，因为线性规划问题的多样性，我们针对不同类型的问题给出不同方法的单纯形法帮助我们更快的解决问题，例如人工变量法，对偶单纯形法等.4.1 单纯形表的计算步骤用单纯形法求解线性规划问题时，正确、熟练的应用单纯形表能给我们带来更多的便捷计算.下面将介绍单纯形表的计算使用方法以及进一步的讨论单纯形法的其他方法应用.4.1.1 单纯形表单纯形表是为了便于展现单纯形法中各种计算关系、使计算过程规范简单不杂乱所5设计出的一种计算表格.它的功能、表达方式与增广矩阵类似，接下来，将为大家详细介绍单纯形法中的重要步骤单纯形表.已知线性规划问题的标准形式

16、为nmaxz='CjXjjin£aijXj=b（i=1,，m）stjJXj>0（j=1,，n）为了在下面的运算中便于观察进行迭代，我们可以先将上述的线性规划问题的形式改写成增广矩阵的形式zXiX2.XmVa-书Xnb一010-0a1,m+anbl0*031"303a2,m书a2nab000"1am,m书amnbC2"CmCm书Cn0即可以采用行初等变换已知z不参加基变换,所以它与Xi,X2，Xm的系数构成一个基,将GC,，Cm变换为零，使对应的系数矩阵为单位矩阵，即-zX1X2XmXm41Xnb一0100a1,m书&nb100510

17、a2,m书a2nb0001am,m书amnbmmm|11000Cm+一乙Ciai,m+Cn-匕Ciain-IGbii=1iT根据上面的增广矩阵设计出以下单纯形表CjTC1CmCmH1CnCB基bxi一一xmxmH1xnC)Kbi10a1,m书anC2x2b200a2,m书a2nair1-1-*cmxmbm0.1am,m书a"mnCj一Zjmm0,0Cm书一£Cai,m书ih-Cn-ZCiainI此表为初始单纯形表，在基列填入基变量，例如x1,x2，xm;在CB列中填入基变量的价值系数，例如g,C2,，Cm,它们与基变量相对应；b列中填入约束方程组右端的常数；Cj行中填入基变

18、量的价值系数C1,C2,，Cn；最后一行为检验数行，对应各非基变量Xj的检验数.每迭代一次可构成一个新的单纯形表.4.1.2计算步骤对于单纯形法，我们已经对其中的重点，单纯形表做出了基本说明，在我们了解了单纯形表的规格、用法等，现在我们对单纯形表的计算步骤加以说明整理.(1)根据目标方程，约束条件建立初始单纯形表.(2)找出初始可行基，确定初始基可行解.(3)算出非基变量xj的检验数是否大于零.(4)若检验数全部小于等于零，则可停止计算，若检验数有大于零，取最大的检验数所对应的为换入变量，以min且除0为换出变量，重新列出单纯形法，进行迭1aikJ代.下面用一个例题对单纯形表的应用做进一步说明

19、.例1用单纯形表解下面线性规划问题.maxz=245x2X<4x2M3stx1+2x2<8x1,x2>0解：先将此线性规划问题化为标准式：maxz=2x15x20x30x40x5x1+x3=4x1+x4=3s.t14x1+2x2+x5=8Xi,x2,x3,x4,x5>0列初始单纯形表CjT25000CB基bxix2x3x4x50x34101000x43010100x812001Cj-Zj25*000从上表，我们可以看到检验数存在大于零的数，且最大检验数为5,同时计算换出变量为x4,我们可以列出第二张单纯形表：CjT25000CB基bXx2x3儿x0x34101005x2

20、3010100x52100-21Cj-Zj2用00-508类似的，可以得出第三张单纯形表:cjT25000CB基bX1X2X3X4X50X320012-15X23010102X12100-21Cj-Zj000-1-2从上表中可看到将到一组新的基本可行解xf)=(2,3,2,0,0T,此时z=19在最后的检验数行中已无正值，说明已求出最优解.评注：在本例题中，我们可以清楚看到单纯形表的计算步骤的呈现.计算时经过了以上的四个步骤.4.2人工变量当线性规划问题的约束条件中本身构造不出单位矩阵时，我们就需要加入人工变量，使其线性规划问题能用单纯形法进行运算.现在，我们主要对人工变量的应用具体探讨.,n

21、I-aijxj=Ri=1；,m若线性规划问题中的约束条件为stu°Xj之0(j=1,，n)现在给每一个约束条件加入一个人工变量，设加入的人工变量分别为Xn+,，xn.可以11、+a2X2+anXn+Xn+=b1a2iXi822X2a2nXnXn2=4得到，其中Xn+,，Xn.为初始基变量，通过单纯形表am1X1+am2X2+amnXn+XnbmX1；Xn-0,Xn1；Xnm-0可以得到一个初始基可行解x（°）=（0，0,%，bm）T,还需要特别注意人工变量是后加入到原来的约束条件中的，所以人工变量是虚拟变量，在计算中应该经过基的变换将人工变量替换出来，在求解结果中，基变量如

22、果不含有非零的人工变量，就表示原线性规划问题有解；基变量中如果含有某个非零人工变量，就表示原线性规划问题无可行解.4.2.1大M法大M法属于人工变量法，针对线性规划问题中约束条件是大于等于形式的情况，不能直接找到初始基可行解（单位矩阵），采用人造基的方法.在线性规划问题的约束条件中加入了人工变量，我们为了使人工变量对目标函数没有影响，可以给人工变量附加一个极大或极小的系数对人工变量进行控制，使人工变量从基变量中换出例2用大M法求解下面线性规划问题minz-3x1x2%x1-2x2+x3<11-4x1+x2+2x3>3s.t-2x1+x3=1Xi,x2,x3>0解：先将原问题化

23、为标准式为：minz=-3x1+x2+x3+0x4+0x5+Mx6+Mx7（这里的M是一个任意大的正数）x,-2x2+x3+x4=114x1+x2+2x3xs+x6=3s.t-2x1+x3+x7=1、为？2?3?4?5?6,*7>0卜面用单纯形表进行计算：CjT-31100MMCB基bxix2x3x4xx6x7100X4111-211000MX63-4120-110MX71-2010001cj-zj-3+6M1-M1-3M0M00cjT1100MMCB基bXX2X3X4XXX70X4103-20100-1MX610100-11-21X31-20100013M-1cj-zj-11-M00M

24、0CjT41100MMCb基bX1X2X3X4X5X6X70X4123001-22-51X210100-11-21X31-2010001cj-zj-10001M-1M+1cjt-31100MM基bX1X2X3X4X5X6X711CB-3x14100%-%-%11x2x3190010010%-1-%1%-2-%cj-zj000%M-XM-%由最终单纯形表可得最优解为x=4,x2-1,x3-9,X4=X5=x=X7最优目标函数值z=2.评注：在本例题中添加了人工变量使得线性规划可以顺利转换为标准形式，使单纯形法更加简化.在一些看似复杂的线性规划问题中，适当的利用大M法，可以简化运算方法，使思维更加

25、开阔4.2.2两阶段法用单纯形法求解线性规划问题时，如果线性规划问题的约束矩阵中有一个单位矩阵，并且b20，看似可以得出基本可行解.但是实际操作后却不能得出，因此还需要另外一种寻找初始可行解的方法即两阶段法.第一阶段引入人工变量，构造辅助线性规划问题，求初始可行解；第二阶段从初始基本可行解开始，去除人工变量，用单纯形法求解原问题.例3用两阶段法求解下面线性规划问题maxz=3X|-x2-x3x1一2x2+x3M11s.t-4x1x22x3一3-2x1x3=1xj>0(j=1,2,3)解：第一阶段先引入松弛变量x4,x5还需引入人工变量x6,x7,可以构造出辅助问12x1-2x2x3x41

26、11-4x1x22x3-x5x6=3-2x1x3x7=1xj_0j=1,2,7先用单纯形法求解出辅助问题的解cjT00000-1-1CB基bx1x2x3x4x5x6x70x4111-211000-1x63-4120-110-1x71-2010001cj-zj-6130-100CjT00000-1-1CB基bx1x2乂3x4x5xx70x4103-20100-1-1%10100-11-20x31-2010001cj-zj0100-10-3cjT-31100MMCB基b乂2乂3x4x5xx7130X4123001-22-50X210100-11-20X31-2010001cj-zj00000-1-

27、1求得辅助线性规划问题的最优解X*=(0,1,1,12,0,0,0(现在人工变量全部换出，第一阶段运算结束，进入第二阶段，用单纯形表求解原问题CjT3-1-100CB基bX1X2X3X4X50X4123001-2-1X210100-1-1X31-20100cj-zj1000-1CjT-31100CB基bX1X2X3X4X5410%-%3X00-1-1X21010-%-1X39001%Cj-Zj000-%-%第二阶段结束，从单纯形表中可以得出原线性规划问题的最优解为xT=(4,1,9,0,0T可以算出目标函数的最优值为z=2.14评注：两阶段的方法在解决比较难的、利用一次变换无法求出结果的线性规

28、划问题中非常实用.但是，通过上题，可以发现两阶段法的构造运算也需要大家对单纯形法有很深了解才不容易出错.4.3单纯形法的改进一一对偶单纯形法在前面一章中介绍的单纯形法是从一个欠优化的基本可行解开始，在求解过程中保持解的可行性并且逐渐完善解的优化性的方法.对偶单纯形法却是从一个超优的不可行解开始，在求解过程中保持解的优化性并且逐渐完善解的可行性的方法.本节主要以例题分析的形式了解对偶单纯形法的应用步骤.例4给出线性规划的数学模型minz=15xi24x25x36x2x3_2s.t55x1+2x2+x3之1Xi,X2,X3-0以上线性规划问题的对偶标准化模型可以写为maxz-15x1-24x2-5x30x40x5_6x2-x3.M-2s.t-5x1-2x2-x3+%=-1xj之0（j=1-，5）比较上面线性规划问题及它的对偶问题的特征，可以发现:原问题（对偶）对偶（原问题）maxmin约束条件变量之<=无约束变量w约束条件工无约束=15在对偶单纯形法中，现行解超优但是不可行，所以先选择最不可行的基变量换出,也就是说换出变量是取负值且绝对值最大的基变量，可以列出cjT-15-24-500CB基bXiX2X3X4X50X4-201-6-1100x5-1-5-2-101czcjzj-1