单纯形法和应用

..MACROBUTTONMTEditEquationSection2SEQMTEqn\r\hSEQMTSec\r1\hSEQMTChap\r1\h单纯形法及其应用摘要单纯形法是一种主要的解决线性规划问题的方法,它在生活的成本问题、交通选择或规划学术问题等方面得到广泛应用.本文系统的研究了单纯形法的相关概念以及原理.并阐述了用单纯形法解决线性规划问题的步骤与方法及不同方法的特殊性.正确的应用单纯形法解决问题能够提高准确率,从而进行合理的规划安排,使得效果或收益达到期待化或最优化.关键词：单纯形法；单纯形表；最优性TheSimplexMethodanditsApplicationAbstract:Simplexmethodisamaintosolvelinearprogrammingproblems,itinlifecost,thechoiceoftrafficoracademicplanningproblemsarewidelyused.Thispaperstudythesimplexmethodoftherelatedconceptsandprinciples.Itdescribesthestepsandmethodstousesimplexmethodtosolvelinearprogrammingproblems,andthedifferentmethod.Correctapplicationofthesimplexmethodproblemsolvingisabletoimprovetheaccuracy,inordertocarryoutreasonableplanningarrangements,makestheeffectorincomereachedexpectationsoroptimization.Keywords:simplexmethod;simplextableau;optimality目录1引言12文献综述12.1国内外研究现状12.2国内外研究现状评价22.3提出问题23单纯形法的相关概念及原理23.1线性规划问题解的相关概念23.2初始基可行解的确定43.3最优性检验与解的判定44单纯形法的计算54.1单纯形表的计算步骤5单纯形表5计算步骤74.2人工变量9大M法10两阶段法124.3单纯形法的改进——对偶单纯形法155单纯形法在实际问题中的应用176结论196.1主要发现196.2启示196.3局限性196.4努力方向20参考文献21..1引言线性规划问题算运筹学中比较早开始研究,在研究过程中发展比较快,在现实生活和学术领域应用比较广泛,研究、解决方法比较成熟的一个不可缺少的分支,随着社会的发展,线性规划也成了人们在解决问题时应用的一种数学方法,它主要应用于数学管理问题的解决中.例如社会经济、交通选择、工业、农业生产等活动中.人们为了提高回报或收益从而对已有的人力、资源、物力等进行合理的的规划安排,使得效果或收益达到期待化或最优化.在解决线性规划问题时,通常应用的方法有图像法和单纯形法等.而应用最多、最有效的方法为单纯形法.单纯形法是一种解决线性规划问题的有效方法,它的应用原理方法为：把线性规划问题的解的可实施部分看做一个维向量空间中的凸集,由此可得线性规划问题存在最优值那么此最优值只能在凸集的顶点处.既然最优值在顶点处,我们就把所有顶点看做一个集合,先在这个集合里面挑选出一个顶点的值,对它进行判别,判别是否为最优值；如果判别结果不是最优值,那么就用一些方法把这个顶点的值转换为另外一个更可能为最优值的顶点值,依次进行判别,因为顶点有限,所以都可以转换出最终的结果,从而达到解决问题的要求,线性规划问题中没有最优的解也可以利用单纯形法进行计算判别.因此,单纯形法对于解决线性规划有非常重要的地位.单纯形法是一种解决线性规划的方法,只有在线性规划问题中才能更好展现,在本文中,我首先就单纯形法所涉及到的一些线性规划的基本概念、解的定义、专业名词等做出简要说明,然后在典型的线性规划中充分揭示单纯形法的步骤、方法及应用,旨在开阔人们分析线性规划问题的思路,加强人们实施实际问题的能力.2文献综述2.1国内外研究现状现查阅到的参考文献中,分别就单纯形法的综述及其在解决线性规划问题中的应用做出说明.敖特根、章学仁在[1-2]中强调单纯形法在线性规划中的产生与发展的重要性.燕子宗等在[3]中给出了一种新的原对偶单纯形法.郭照庄等在[4-5]中详细阐述单纯形法的基本原理.赵娜、唐帅等在[6-7]中针对如何使用大M法和两阶段法实现某一线性目标最优化问题作出详细说明.胡运权在文献[8]中针对单纯形法的基本知识和应用做出阐述．文献[9]中,马振华举例说明单纯形法在解决不同线性规划问题中的应用及规律.文献[10]中刘红英等对单纯形法的计算机算法进行了说明．邓成梁等在[11-15]中对单纯形法的迭代步骤与解的讨论进行研究,而且也对单纯形法的具体求解做出的研究.2.2国内外研究现状评价文献[1-15]分别就单纯形法的解题步骤及单纯形法在线性规划问题解题中的意义举例作了说明,文献中主要阐述一种或几种单纯形法在线性规划解题中的应用,没有全面地介绍常用单纯形法在不同线性规划问题的应用及解题步骤,而且文献中对怎样应用单纯形法解决线性规划问题提及甚少,对应用中存在的问题也未给出详细深入的说明,以及遇到现实问题时,单纯形法的具体用法及计算机应用方法未有太多涉及.2.3提出问题单纯形法的在线性规划中有广泛的应用,但是大部分书本只介绍了一些基础知识或讲解线性规划时一带而过.因此,除对解决线性规划问题过程中被一带而过单纯形法作出介绍外,还需要对应用单纯形法解决问题过程中可能遇到的困难、不理解及解决办法作出探讨,包括对使用不同单纯形法的目的、作用、要求作阐述．体会在不同题中单纯形法的不同应用,总结概括以指导方便快捷地解决问题．3单纯形法的相关概念及原理3.1线性规划问题解的相关概念线性规划问题是需要用单纯形法解决的一类问题,所以我们在研究讨论单纯形法时是基于线性规划的基础之上,利用单纯形法使线性规划问题简单、清楚的得出结果是我们的最终目的.一般线性规划问题化为标准式是利用单纯形法求解线性规划问题的基本步骤,对于单纯形法能否顺利得出结果,也有很大联系,在解题过程中,应该谨记变量,目标函数,约束条件的相关要求.：目标函数约束条件我们不难看出上式的三个特点：〔1有决策变量：.〔2有目标函数,：,一般多用.两者可以互换,即.〔3有约束条件,通常为等式,对于""或""型的约束条件,可以添加变量转换成等式约束条件,添加的变量称为松弛变量,在目标函数中,松弛变量相对应的系数为0.例如:在利用单纯形法进行计算时,对于线性规划的解的相关概念也需要牢记,在接下来的单纯形法格式中,是以基本概念的求解为基础.线性规划解的概念对于不同元素的换入、换出等都有影响.下面将介绍线性规划问题解的概念:1、可行解:,称为线性规划问题的可行解.可行解的集合,称为可行域.2、最优解:最符合题目要求的解,在可行域中,能够使目标函数取得最大值的可行解称为最优解.最优解一定是可行解.3、基:设A阶系数矩阵〔设,基为A的满秩子矩阵矩阵.4、基可行解:,最优解一定是基可行解.5、可行基:对应于基可行解的基称为可行基.3.2初始基可行解的确定我们说单纯形法是一种迭代算法.所以我们在迭代时需要确定每一次迭代的对象,特别是在进行第一次迭代前,我们必须确定好对象才能使单纯形法的迭代顺利进行.第一次迭代的对象我们称为初始基可行解.为了确定初始基可行解,首先要找出初始可行基.找出初始可行基的方法为：〔1有的线性规划问题中能直接观察得到一个初始可行基：〔2如果所有约束条件是""的不等式,在化为标准形式后,可以重新对变量和变量系数进行编号,得到一个的单位矩阵此时单位矩阵可作为可行基.再将标准形式下的约束条件移项为在同一边的等式,再令,可得,就此得到一个初始基可行解.〔3如果所有约束条件是""的不等式,及等式约束情况不存在单位矩阵时,就采用人工造基方法.即对不等式约束中减去一个非负的变量后,再加上一个非负的人工变量；对于等式约束一样加上一个非负的人工变量,就可以得到一个单位矩阵.3.3最优性检验与解的判定线性规划问题解的结果有以下四种情况：唯一最优解、无穷多最优解、无界解和无可行解.在用单纯形对线性规划进行迭代的过程中,对于什么样的情况使得线性规划有解或无解、什么样的情况线性规划达到最优,这就需要进行最优性检验与解的判定.所以对于线性规划的解需要建立判定准则.〔1最优解的判定设为一个基可行解,并且对于一切都有检验数,则可以判定在该线性规划问题中为最优解.〔2无穷多最优解的判定设为一个基可行解,并且对于一切都有检验数,同时又存在某个非基变量的检验数,则可以判定该线性规划问题有无穷多最优解.〔3无界解的判定设为一个基可行解,有检验数,并且对于有则判定该线性规划问题有无界解也称之为无最优解.4单纯形法的计算利用单纯形表时,我们首先要了解什么是单纯形表,它有什么样的特点、规则等,其次,因为线性规划问题的多样性,我们针对不同类型的问题给出不同方法的单纯形法帮助我们更快的解决问题,例如人工变量法,对偶单纯形法等.4.1单纯形表的计算步骤用单纯形法求解线性规划问题时,正确、熟练的应用单纯形表能给我们带来更多的便捷计算.下面将介绍单纯形表的计算使用方法以及进一步的讨论单纯形法的其他方法应用.4.1.1单纯形表单纯形表是为了便于展现单纯形法中各种计算关系、使计算过程规范简单不杂乱所设计出的一种计算表格.它的功能、表达方式与增广矩阵类似,接下来,将为大家详细介绍单纯形法中的重要步骤单纯形表.为了在下面的运算中便于观察进行迭代,我们可以先将上述的线性规划问题的形式改写成增广矩阵的形式已知,所以它与的系数构成一个基,换将变换为零,即基此表为初始单纯形表,在基列填入基变量,例如；在列中填入基变量的价值系数,例如,它们与基变量相对应；列中填入约束方程组右端的常数；行中填入基变量的价值系数；最后一行为检验数行,对应各非基变量的检验数.每迭代一次可构成一个新的单纯形表.4.1.2计算步骤对于单纯形法,我们已经对其中的重点,单纯形表做出了基本说明,在我们了解了单纯形表的规格、用法等,现在我们对单纯形表的计算步骤加以说明整理.〔1根据目标方程,约束条件建立初始单纯形表.〔2找出初始可行基,确定初始基可行解.〔3算出非基变量的检验数是否大于零.〔4若检验数全部小于等于零,则可停止计算,若检验数有大于零,取最大的检验数所对应的为换入变量,以为换出变量,重新列出单纯形法,进行迭代.下面用一个例题对单纯形表的应用做进一步说明.例1用单纯形表解下面线性规划问题.解：先将此线性规划问题化为标准式：列初始单纯形表25000基从上表,我们可以看到检验数存在大于零的数,且最大检验数为5,同时计算换出变量为,我们可以列出第二张单纯形表：25000基类似的,可以得出第三张单纯形表：25000基从上表中可看到,得到一组新的基本可行解,此时在最后的检验数行中已无正值,说明已求出最优解.评注：在本例题中,我们可以清楚看到单纯形表的计算步骤的呈现.计算时经过了以上的四个步骤.4.2人工变量当线性规划问题的约束条件中本身构造不出单位矩阵时,我们就需要加入人工变量,使其线性规划问题能用单纯形法进行运算.现在,我们主要对人工变量的应用具体探讨.若线性规划问题中的约束条件为现在给每一个约束条件加入一个人工变量,设加入的人工变量分别为可以得到,其中为初始基变量,通过单纯形表可以得到一个初始基可行解,还需要特别注意人工变量是后加入到原来的约束条件中的,所以人工变量是虚拟变量,在计算中应该经过基的变换将人工变量替换出来,在求解结果中,基变量如果不含有非零的人工变量,就表示原线性规划问题有解；基变量中如果含有某个非零人工变量,就表示原线性规划问题无可行解.4.2.1大M法大M法属于人工变量法,针对线性规划问题中约束条件是大于等于形式的情况,不能直接找到初始基可行解〔单位矩阵,采用人造基的方法.在线性规划问题的约束条件中加入了人工变量,我们为了使人工变量对目标函数没有影响,可以给人工变量附加一个极大或极小的系数对人工变量进行控制,使人工变量从基变量中换出.例2用大M法求解下面线性规划问题解：先将原问题化为标准式为：〔这里的M是一个任意大的正数下面用单纯形表进行计算：基基基基由最终单纯形表可得最优解为最优目标函数值.评注：在本例题中添加了人工变量使得线性规划可以顺利转换为标准形式,使单纯形法更加简化.在一些看似复杂的线性规划问题中,适当的利用大法,可以简化运算方法,使思维更加开阔.4.2.2两阶段法用单纯形法求解线性规划问题时,如果线性规划问题的约束矩阵中有一个单位矩阵,并且,看似可以得出基本可行解.但是实际操作后却不能得出,因此还需要另外一种寻找初始可行解的方法即两阶段法.第一阶段引入人工变量,构造辅助线性规划问题,求初始可行解；第二阶段从初始基本可行解开始,去除人工变量,用单纯形法求解原问题.例3用两阶段法求解下面线性规划问题解：第一阶段先引入松弛变量还需引入人工变量,可以构造出辅助问题先用单纯形法求解出辅助问题的解基基基求得辅助线性规划问题的最优解现在人工变量全部换出,第一阶段运算结束,进入第二阶段,用单纯形表求解原问题基基第二阶段结束,从单纯形表中可以得出原线性规划问题的最优解为可以算出目标函数的最优值为.评注：两阶段的方法在解决比较难的、利用一次变换无法求出结果的线性规划问题中非常实用.但是,通过上题,可以发现两阶段法的构造运算也需要大家对单纯形法有很深了解才不容易出错.4.3单纯形法的改进——对偶单纯形法在前面一章中介绍的单纯形法是从一个欠优化的基本可行解开始,在求解过程中保持解的可行性并且逐渐完善解的优化性的方法.对偶单纯形法却是从一个超优的不可行解开始,在求解过程中保持解的优化性并且逐渐完善解的可行性的方法.本节主要以例题分析的形式了解对偶单纯形法的应用步骤.例4给出线性规划的数学模型以上线性规划问题的对偶标准化模型可以写为比较上面线性规划问题及它的对偶问题的特征,可以发现：原问题〔对偶对偶〔原问题约束条件变量=无约束变量约束条件无约束=在对偶单纯形法中,现行解超优但是不可行,所以先选择最不可行的基变量换出,也就是说换出变量是取负值且绝对值最大的基变量,可以列出基基基从表格中可以看出用对偶单纯形法求解时,当约束条件为大于等于时,可以不必引入人工变量,使计算得到简化.评注：本题完整、充分的展示了对偶单纯形法的优点,在原问题利用单纯形法困难时,可以利用对偶单纯形法使计算简便.5单纯形法在实际问题中的应用利用数学计算工具来求解单纯形法中的问题,其价值和推广是可观的,不仅可以提高计算速度还可以保证计算的准确性.用计算机辅助运算单纯形法的方法有利用Excel软件或利用MATLAB实现.案例分析：一个食堂经理Jick想降低食堂成本,他发现在原材料中蚕豆和红薯为主要配料。他每周购买蚕豆的成本是每磅,红薯的成本是1美元.这两种原材料中又必须<1磅相当于454克,1克等于1000毫克.为了简化计划,假设这道炖菜中只有蚕豆和红薯提供了营养.它们的营养成分信息如下表所示：蚕豆红薯蛋白质1.5g/100g6.22g/l0盎司铁0.3mg/100g3.732mg/10盎司维生素C12mg/100g31.1mg/10盎司<1盎司相当于31.1克食堂要求蚕豆和红薯的总量比至少应当是.每周这样的菜至少为10公斤,假设只有蚕豆和红薯决定菜的数量.需要准备的菜没有上限,因为所有剩下的菜可以供应好几天,或者创造性的作为其他主菜的原料.根据以上资料,试回答以下问题：利用计算机表格公式计算可得目标函数值目标函数系数0.882.216.6974359约束条件条件11520194.8718>=180条件231280>=80条件31201001251.282>=1050条件45-60>=0条件51111.28205>=106.1538465.128205决策变量x1x2运算结果报告为目标单元格<最小值>单元格名字初值终值$G$2目标函数系数目标函数值16.697435916.6974359可变单元格单元格名字初值终值$B$116.1538461546.153846154约束单元格名字单元格值公式状态型数值$F$5条件1194.8717949$F$5>=$H$5未到限制值14.87179487$F$6条件280$F$6>=$H$6到达限制值0$F$7条件31251.282051$F$7>=$H$7未到限制值201.2820513$F$8条件40$F$8>=$H$8到达限制值0$F$9条件511.28205128$F$9>=$H$9未到限制值1.282051282从上述表格运算中,我们可以发现,单纯形法可以让实际问题简单化、清楚化.但是,应用计算机、利用Excel软件或利用MATLAB可以很大程度的降低单纯形法的繁琐程度,使计算过程准确化,检验清楚化.所以在实际问题的应用中,因为实际问题中数字的任意性和繁琐程度,我们在使用单纯形法时,更多的使用计算机算法.6结论6.1主要发现从论文中,我们可以发现随着线性规划问题被人们越来越多的应用,单纯形法的重视程度也逐渐提高.单纯形法计算步骤需要细心处理,用单纯形法解决问题时方法灵活多变,单纯形法在线性规划中应用广泛,使用单纯形法能使解题过程清晰、陌生问题熟悉化、抽象问题具体化等.6.2启示使用单纯形法时应该多加练习基本步骤方法,当应用熟练时,遇到新的线性规划问题时,就可以很好的分辨出在本题中能不能把单纯形法简化,用哪种具体的单纯形法解题,这样,我们所遇到的问题也就迎刃而解了.与此同时也能让我们在解决问题时思路清晰、步骤明了,尤其是单纯形法中的人工变量法在解决实际问题和填空题较复杂的问题时作用很大.但是具体的单纯形法在不同线性规划中的应用有所不同,方法很多,应用时要注意灵活地选择,不能生搬硬套.6.3局限性本文主要就单纯形法及其应用做出研究说明,其主要是揭示单纯形法的方法步骤及特殊性,还有诸多知识需待补充,对于单纯形法的计算机编程算法未能详细写出.本文介绍的重点在于单纯形法的常规算法及应用,其余的还有待进一步探讨.单纯形法并不是线性规划的"万能方法",在应用单纯形法时,要合理有效地结合其它方法,灵活选择应用.6.4努力方向单纯形法在解决线性规划问题时的应用非常灵活多变,合理选择适合的单纯形法能让我们的解题事半功倍,但单纯形法并不是短时间内就可以学习掌握的.学好基础知识、理解步骤方法才是熟练应用单纯形法的关键,只有熟练掌握单纯形法的基础知识,积累学习经验,我们才能够更深入的了解、研究单纯形法,提高解决数学问题的能力.参考文献[1]敖特根．单纯形法的产生与发展探析[J]．西北大学学报,2012,<8>:46-48．[2]章学仁．线性规划[M］．上海:上海交通大学出版社,1