单纯形法及其应用

单纯形法及其应用摘 要单纯形法是一种主要的解决线性规划问题的方法，它在生活的成本问题、交通选择或规划学术问题等方面得到广泛应用.本文系统的研究了单纯形法的相关概念以及原理.并阐述了用单纯形法解决线性规划问题的步骤与方法及不同方法的特殊性.正确的应用单纯形法解决问题能够提高准确率，从而进行合理的规划安排，使得效果或收益达到期待化或最优化.关键词：单纯形法；单纯形表；最优性The Simplex Method and its ApplicationAbstract: Simplex method is a main to solve linear programming problems, it in life cost, the choice of traffic or academic planning problems are widely used. This paper study the simplex method of the related concepts and principles. It describes the steps and methods to use simplex method to solve linear programming problems, and the different method. Correct application of the simplex method problem solving is able to improve the accuracy, in order to carry out reasonable planning arrangements, makes the effect or income reached expectations or optimization.Keywords:simplex method;simplex tableau;optimality目 录1 引言引言 .12 文献综述文献综述 .12.1 国内外研究现状.12.2 国内外研究现状评价.22.3 提出问题.23 单纯形法的相关概念及原理单纯形法的相关概念及原理 .23.1 线性规划问题解的相关概念.23.2 初始基可行解的确定.43.3 最优性检验与解的判定.44 单纯形法的计算单纯形法的计算 .54.1 单纯形表的计算步骤.54.1.1 单纯形表.54.1.2 计算步骤.74.2 人工变量.94.2.1 大 M 法.104.2.2 两阶段法.124.3 单纯形法的改进对偶单纯形法.155 单纯形法在实际问题中的应用单纯形法在实际问题中的应用 .176 结论结论 .196.1 主要发现.196.2 启示.196.3 局限性.196.4 努力方向.20参考文献参考文献 .2111 引言线性规划问题算运筹学中比较早开始研究，在研究过程中发展比较快，在现实生活和学术领域应用比较广泛，研究、解决方法比较成熟的一个不可缺少的分支,随着社会的发展，线性规划也成了人们在解决问题时应用的一种数学方法，它主要应用于数学管理问题的解决中.例如社会经济、交通选择、工业、农业生产等活动中.人们为了提高回报或收益从而对已有的人力、资源、物力等进行合理的的规划安排，使得效果或收益达到期待化或最优化.在解决线性规划问题时，通常应用的方法有图像法和单纯形法等.而应用最多、最有效的方法为单纯形法.单纯形法是一种解决线性规划问题的有效方法，它的应用原理方法为：把线性规划问题的解的可实施部分看做一个维向量空间中的凸集，由此nRn可得线性规划问题存在最优值那么此最优值只能在凸集的顶点处.既然最优值在顶点处，我们就把所有顶点看做一个集合，先在这个集合里面挑选出一个顶点的值，对它进行判别，判别是否为最优值；如果判别结果不是最优值，那么就用一些方法把这个顶点的值转换为另外一个更可能为最优值的顶点值，依次进行判别，因为顶点有限，所以都可以转换出最终的结果，从而达到解决问题的要求，线性规划问题中没有最优的解也可以利用单纯形法进行计算判别.因此，单纯形法对于解决线性规划有非常重要的地位.单纯形法是一种解决线性规划的方法，只有在线性规划问题中才能更好展现，在本文中，我首先就单纯形法所涉及到的一些线性规划的基本概念、解的定义、专业名词等做出简要说明，然后在典型的线性规划中充分揭示单纯形法的步骤、方法及应用，旨在开阔人们分析线性规划问题的思路，加强人们实施实际问题的能力.2 文献综述2.1 国内外研究现状现查阅到的参考文献中，分别就单纯形法的综述及其在解决线性规划问题中的应2用做出说明.敖特根、章学仁在1-2中强调单纯形法在线性规划中的产生与发展的重要性.燕子宗等在3中给出了一种新的原对偶单纯形法.郭照庄等在4-5中详细阐述单纯形法的基本原理.赵娜、唐帅等在 6-7中针对如何使用大 M 法和两阶段法实现某一线性目标最优化问题作出详细说明.胡运权在文献8中针对单纯形法的基本知识和应用做出阐述文献9中，马振华举例说明单纯形法在解决不同线性规划问题中的应用及规律.文献10中刘红英等对单纯形法的计算机算法进行了说明邓成梁等在11-15中对单纯形法的迭代步骤与解的讨论进行研究，而且也对单纯形法的具体求解做出的研究.2.2 国内外研究现状评价文献1-15分别就单纯形法的解题步骤及单纯形法在线性规划问题解题中的意义举例作了说明，文献中主要阐述一种或几种单纯形法在线性规划解题中的应用，没有全面地介绍常用单纯形法在不同线性规划问题的应用及解题步骤，而且文献中对怎样应用单纯形法解决线性规划问题提及甚少，对应用中存在的问题也未给出详细深入的说明，以及遇到现实问题时，单纯形法的具体用法及计算机应用方法未有太多涉及.2.3 提出问题 单纯形法的在线性规划中有广泛的应用，但是大部分书本只介绍了一些基础知识或讲解线性规划时一带而过. 因此，除对解决线性规划问题过程中被一带而过单纯形法作出介绍外，还需要对应用单纯形法解决问题过程中可能遇到的困难、不理解及解决办法作出探讨，包括对使用不同单纯形法的目的、作用、要求作阐述体会在不同题中单纯形法的不同应用，总结概括以指导方便快捷地解决问题3 单纯形法的相关概念及原理3.1 线性规划问题解的相关概念线性规划问题是需要用单纯形法解决的一类问题，所以我们在研究讨论单纯形法3时是基于线性规划的基础之上，利用单纯形法使线性规划问题简单、清楚的得出结果是我们的最终目的.一般线性规划问题化为标准式是利用单纯形法求解线性规划问题的基本步骤，对于单纯形法能否顺利得出结果，也有很大联系，在解题过程中，应该谨记变量，目标函数，约束条件的相关要求.：线性规划问题的标准形式为目标函数 1maxnjjjzc x约束条件 11,. .01,nijjijja xb imstxjn我们不难看出上式的三个特点：（1）有决策变量：.0;1,jxjm （2）有目标函数，：，一般多用.两者可以互换，即. maxmin或maxmaxminzz（3）有约束条件，通常为等式，对于“”或“”型的约束条件，可以添加变量转换成等式约束条件，添加的变量称为松弛变量，在目标函数中，松弛变量相对应的系数为 0.例如:123123445154515xxxxxxx12312352632026320 xxxxxxx在利用单纯形法进行计算时，对于线性规划的解的相关概念也需要牢记，在接下来的单纯形法格式中，是以基本概念的求解为基础.线性规划解的概念对于不同元素的换入、换出等都有影响.下面将介绍线性规划问题解的概念:1、可行解:，称为线性规划问题的可可以满足全部约束条件的解1,TnXxx行解.可行解的集合，称为可行域.2、最优解:最符合题目要求的解，在可行域中，能够使目标函数取得最大值的可行解称为最优解.最优解一定是可行解.3、基:设 A阶系数矩阵（设） ，基为 A 的满秩子矩阵为约束方程组的m nnm4 矩阵.m m4、基可行解:，最优解一定是基可行满足变量非负约束条件的基解叫做基可行解解.5、可行基:对应于基可行解的基称为可行基.3.2 初始基可行解的确定我们说单纯形法是一种迭代算法.所以我们在迭代时需要确定每一次迭代的对象，特别是在进行第一次迭代前，我们必须确定好对象才能使单纯形法的迭代顺利进行.第一次迭代的对象我们称为初始基可行解.为了确定初始基可行解，首先要找出初始可行基.找出初始可行基的方法为：（1）有的线性规划问题中能直接观察得到一个初始可行基： 12100010,.001mBa aa（2）如果所有约束条件是“”的不等式，在化为标准形式后，可以 重新对变量和变量系数进行编号，得到一个的单位矩阵m m12100010,.001mBa aa此时单位矩阵 可作为可行基.再将标准形式下的约束条件移项为 在同一B12,mx xx边的等式，再令 ，可得，就此得到一个初120mmnxxx1,2,iixb im始基可行解. 12,0,0Tmn mXb bb （3）如果所有约束条件是“ ”的不等式，及等式约束情况不存在单位矩阵时，就采用人工造基方法.即对不等式约束中减去一个非负的变量后，再加上一个非负的人工变量；对于等式约束一样加上一个非负的人工变量，就可以得到一个单位矩阵. 53.3 最优性检验与解的判定线性规划问题解的结果有以下四种情况：唯一最优解、无穷多最优解、无界解和无可行解.在用单纯形对线性规划进行迭代的过程中，对于什么样的情况使得线性规划有解或无解、什么样的情况线性规划达到最优，这就需要进行最优性检验与解的判定.所以对于线性规划的解需要建立判定准则.（1）最优解的判定设 为一个基可行解，并且对于一切 都有检 012,0,0TmXb bb1,jmn 验数，则可以判定在该线性规划问题中 max1,2,0jkkjjczzcjn 0X为最优解.（2）无穷多最优解的判定设为一个基可行解，并且对于一切都有检验 012,0,0TmXb bb1,jmn 数，同时又存在某个非基变量的检验数max1,2,0jkkjjczzcjn，则可以判定该线性规划问题有无穷多最优解.0m k（3）无界解的判定设为一个基可行解，有检验数，并且对于 012,0,0TmXb bb0m k有 则判定该线性规划问题有无界解也称之为无最优解.1,2,im,0i m ka4 单纯形法的计算利用单纯形表时，我们首先要了解什么是单纯形表，它有什么样的特点、规则等，其次，因为线性规划问题的多样性，我们针对不同类型的问题给出不同方法的单纯形法帮助我们更快的解决问题，例如人工变量法，对偶单纯形法等.4.1 单纯形表的计算步骤用单纯形法求解线性规划问题时，正确、熟练的应用单纯形表能给我们带来更多的便捷计算.下面将介绍单纯形表的计算使用方法以及进一步的讨论单纯形法的其他方6法应用.4.1.1 单纯形表单纯形表是为了便于展现单纯形法中各种计算关系、使计算过程规范简单不杂乱所设计出的一种计算表格.它的功能、表达方式与增广矩阵类似，接下来，将为大家详细介绍单纯形法中的重要步骤单纯形表.已知线性规划问题的标准形式为1maxnjjjzc x11,. .01,nijjijja xb imstxjn为了在下面的运算中便于观察进行迭代，我们可以先将上述的线性规划问题的形式改写成增广矩阵的形式1211,112,12,112101000010000110mmnmnmnm mmnmmnzxxxxxbaabaabaabccccc已知，所以它与的系数构成一个基，z 不参加基变换12,mx xx换将 变换为零，即即可以采用行初等变12,mc cc，使对应的系数矩阵为单位矩阵1211,112,12,11,11110100001000011000mmnmnmnm mmnmmmmii mniiniiiiizxxxxxbaabaabaabcc acc acb根据上面的增广矩阵设计出以下单纯形表7 jc 1c mc 1mc nc BC基 b 1x mx 1mx nx 12mccc 12mxxx 12mbbb 100 001 1,12,1,1mmm maaa 12nnmnaaa jjcz 0 0 1,11mmii micc a 1mniinicc a此表为初始单纯形表，在基列填入基变量，例如 ；在 列中填入基变量12,mx xxBC的价值系数，例如，它们与基变量相对应；列中填入约束方程组右端的常12,mc ccb数；行中填入基变量的价值系数 ；最后一行为检验数行，对应各非基变jc12,nc cc量 的检验数.每迭代一次可构成一个新的单纯形表.jx4.1.2 计算步骤对于单纯形法，我们已经对其中的重点，单纯形表做出了基本说明，在我们了解了单纯形表的规格、用法等，现在我们对单纯形表的计算步骤加以说明整理.（1）根据目标方程，约束条件建立初始单纯形表.（2）找出初始可行基，确定初始基可行解.（3）算出非基变量 的检验数是否大于零.jx（4）若检验数全部小于等于零，则可停止计算，若检验数有大于零，取最大的检验数所对应的 为换入变量，以 为换出变量，重新列出单纯形法，进行jxmin0iikikbaa迭代.8下面用一个例题对单纯形表的应用做进一步说明.例 1 用单纯形表解下面线性规划问题.12max25zxx12121243. .28,0 xxstxxx x解：先将此线性规划问题化为标准式：12345max25000zxxxxx13141251234543. .28,0 xxxxstxxxx x x x x列初始单纯形表 jc 2 5 000 BC基 b 1x 2x 3x 4x 5x 000 345xxx 438 101 012 100 010 001 jjcz 2 5 0 00从上表，我们可以看到检验数存在大于零的数，且最大检验数为 5，同时计算换出变量为 ，我们可以列出第二张单纯形表：4x jc 2 5 000 BC基 b 1x 2x 3x 4x 5x9类似的，可以得出第三张单纯形表： jc 2 5 000 BC基 b 1x 2x 3x 4x 5x 052 321xxx 232 001 010 100 212 101 jjcz 0 0 0 12从上表中可看到,得到一组新的基本可行解 ，此时 22,3,2,0,0Tx19z 在最后的检验数行中已无正值,说明已求出最优解.评注：在本例题中，我们可以清楚看到单纯形表的计算步骤的呈现.计算时经过了以上的四个步骤.4.2 人工变量当线性规划问题的约束条件中本身构造不出单位矩阵时，我们就需要加入人工变量，使其线性规划问题能用单纯形法进行运算.现在，我们主要对人工变量的应用具体探讨.若线性规划问题中的约束条件为11,. .01,nijjijja xb imstxjn 050 325xxx 432 101 010 100 012 001 jjcz 2 0 0 5010现在给每一个约束条件加入一个人工变量，设加入的人工变量分别为 可以1,nn mxx得到,其中 为初始基变量，通过单纯形11 112211121 12222221 12211,0,0nnnnnnmmmnnn mmnnn ma xa xa xxba xa xa xxba xaxaxxbxxxx1,nn mxx表可以得到一个初始基可行解，还需要特别注意人工变量是后 010,0,Tmxbb加入到原来的约束条件中的，所以人工变量是虚拟变量，在计算中应该经过基的变换将人工变量替换出来，在求解结果中，基变量如果不含有非零的人工变量，就表示原线性规划问题有解；基变量中如果含有某个非零人工变量，就表示原线性规划问题无可行解. 4.2.1 大 M 法大 M 法属于人工变量法,针对线性规划问题中约束条件是大于等于形式的情况,不能直接找到初始基可行解（单位矩阵）,采用人造基的方法.在线性规划问题的约束条件中加入了人工变量，我们为了使人工变量对目标函数没有影响，可以给人工变量附加一个极大或极小的系数对人工变量进行控制，使人工变量从基变量中换出.例 2 用大 M 法求解下面线性规划问题123min3zxxx 12312313123211423. .21,0 xxxxxxstxxx x x解：先将原问题化为标准式为：（这里的 M 是一个任意大的正数）1234567min300zxxxxxMxMx 1234123561371234567211423. .21,0 xxxxxxxxxstxxxx x x x x x x下面用单纯形表进行计算：11 jc 3 1 1 0 0 M M BC基 b 1x 2x 3x 4x 5x 6x 7x 0MM 467xxx 1131 142 210 121 100 010 010 001 jjcz 36M 1M1 3M 0 M 0 0 jc 3 1 1 0 0 M M BC基 b 1x 2x 3x 4x 5x 6x 7x 01M 463xxx 1011 302 210 001 100 010 010 121 jjcz 1 1M0 0 M 031M jc 3 1 1 0 0 M M BC基 b 1x 2x 3x 4x 5x 6x 7x 011 423xxx 1211 302 010 001 100 210 210 521 jjcz 1 00 0 1 1M 1M 12 jc 3 1 1 0 0 M M BC基 b 1x 2x 3x 4x 5x 6x 7x 311 123xxx 419 100 010 001 13023 23143 23143 53273 jjcz 0 00 13 13 13M 23M 由最终单纯形表可得最优解为12345674,1,9,0 xxxxxxx最优目标函数值 .2z 评注：在本例题中添加了人工变量使得线性规划可以顺利转换为标准形式，使单纯形法更加简化.在一些看似复杂的线性规划问题中，适当的利用大法，可以简化M运算方法，使思维更加开阔.4.2.2 两阶段法 用单纯形法求解线性规划问题时，如果线性规划问题的约束矩阵中有一个单位矩阵，并且 ，看似可以得出基本可行解.但是实际操作后却不能得出，因此还需要0b 另外一种寻找初始可行解的方法即两阶段法.第一阶段引入人工变量，构造辅助线性规划问题，求初始可行解；第二阶段从初始基本可行解开始，去除人工变量，用单纯形法求解原问题.例 3 用两阶段法求解下面线性规划问题123max3zxxx1312312313211423. .2101,2,3jxxxxxxstxxxj解：第一阶段先引入松弛变量 还需引入人工变量 ，可以构造出辅助问45,x x67,x x题67max yxx 123412356137211423. .2101,2,7jxxxxxxxxxstxxxxj先用单纯形法求解出辅助问题的解 jc 0 0 0 0 0 1 1 BC基 b 1x 2x 3x 4x 5x 6x 7x 011 467xxx 1131 142 210 121 100 010 010 001 jjcz 6 13 0 1 0 0 jc 0 0 0 0 0 1 1 BC基 b 1x 2x 3x 4x 5x 6x 7x 010 463xxx 1011 302 210 001 100 010 010 12114 jjcz 0 10 0 1 0 3 jc 3 1 1 0 0 M M BC基 b 1x 2x 3x 4x 5x 6x 7x 000 423xxx 1211 302 010 001 100 210 210 521 jjcz 0 00 0 0 1 1求得辅助线性规划问题的最优解 现在人工变量全部换出，0,1,1,12,0,0,0TX第一阶段运算结束，进入第二阶段，用单纯形表求解原问题 jc 3 1 1 0 0 BC基 b 1x 2x 3x 4x 5x 011 423xxx 1211 302 010 001 100 210 jjcz 1 00 0 1 jc 3 1 1 0 0 BC基 b 1x 2x 3x 4x 5x15 311 123xxx 419 100 010 001 13023 23143 jjcz 0 00 13 13第二阶段结束，从单纯形表中可以得出原线性规划问题的最优解为 4,1,9,0,0TTx 可以算出目标函数的最优值为. 2z 评注：两阶段的方法在解决比较难的、利用一次变换无法求出结果的线性规划问题中非常实用.但是，通过上题，可以发现两阶段法的构造运算也需要大家对单纯形法有很深了解才不容易出错.4.3 单纯形法的改进对偶单纯形法在前面一章中介绍的单纯形法是从一个欠优化的基本可行解开始，在求解过程中保持解的可行性并且逐渐完善解的优化性的方法.对偶单纯形法却是从一个超优的不可行解开始，在求解过程中保持解的优化性并且逐渐完善解的可行性的方法.本节主要以例题分析的形式了解对偶单纯形法的应用步骤.例 4 给出线性规划的数学模型123min15245zxxx2312312362. . 521,0 xxstxxxx x x以上线性规划问题的对偶标准化模型可以写为12345max1524500zxxxxx 234123562. .52101,5jxxxstxxxxxj 16比较上面线性规划问题及它的对偶问题的特征，可以发现：原问题（对偶）对偶（原问题）maxmin约束条件变量=无约束变量约束条件无约束=在对偶单纯形法中，现行解超优但是不可行，所以先选择最不可行的基变量换出，也就是说换出变量是取负值且绝对值最大的基变量，可以列出 jc 15 24 5 0 0 BC基 b 1x 2x 3x 4x 5x 00 45xx 21 05 62 11 10 01 jjcz 15 245 0 0 jc 15 24 5 0 0 BC基 b 1x 2x 3x 4x 5x 240 25xx 1313 05 10 1623 1613 01 jjcz 15 01 4 0 jc 15 24 5 0 0 BC基 b 1x 2x 3x 4x 5x17 245 23xx 1412 54152 10 01 1412 1423 jjcz 152 00 72 32从表格中可以看出用对偶单纯形法求解时，当约束条件为大于等于时，可以不必引入人工变量，使计算得到简化.评注：本题完整、充分的展示了对偶单纯形法的优点，在原问题利用单纯形法困难时，可以利用对偶单纯形法使计算简便.5 单纯形法在实际问题中的应用利用数学计算工具来求解单纯形法中的问题，其价值和推广是可观的，不仅可以提高计算速度还可以保证计算的准确性.用计算机辅助运算单纯形法的方法有利用Excel 软件或利用 MATLAB 实现.案例分析：一个食堂经理 Jick 想降低食堂成本，他发现在原材料中蚕豆和红薯为主要配料。他每周购买蚕豆的成本是每磅 ，红薯的成本是 1 美元.这两种原材料中又必须0.4美元 ( 1 磅相当于 454 克，1 克等于 1000180801050C包含克蛋白质、毫克铁、毫克维生素毫克）.为了简化计划， 假设这道炖菜中只有蚕豆和红薯提供了营养.它们的营养成分信息如下表所示：蚕豆红薯蛋白质1.5g/100g6.22 g/l0 盎司铁0.3mg/100g3.732mg/10 盎司维生素 C12mg/100g31.1mg/10 盎司( 1 盎司相当于 31.1 克）食堂要求蚕豆和红薯的总量比至少应当是 .每周这样的菜至少为 10 公斤，假6:518设只有蚕豆和红薯决定菜的数量.需要准备的菜没有上限，因为所有剩下的菜可以供应好几天，或者创造性的作为其他主菜的原料.根据以上资料，试回答以下问题：在满足食堂要求的前提下，使得配料的成本最小.解：了解题目可以发现，问题贴近现实生活，数字多而且复杂，利用普通算法容易 Excel出错，遗漏条件，所以，我们采用软件进行计算： ,kgkg z设需要准备蚕豆红薯为配料的成本12200500min227227zxx1212121212121520180312801201001050.560100,0 xxxxxxstxxxxxx利用计算机表格公式计算可得目标函数值目标函数系数0.882.216.6974359约束条件条件 11520194.8718=180条件 231280=80条件 31201001251.282=1050条件 45-60=0条件 51111.28205=106.153846 5.128205决策变量x1x2运算结果报告为19目标单元格 (最小值)单元格单元格名字名字初值初值终值终值$G$2目标函数系数 目标函数值16.697435916.6974359可变单元格单元格单元格名字名字初值初值终值终值$B$11 6.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 主要发现 从论文中，我们可以发现随着线性规划问题被人们越来越多的应用，单纯形法的重视程度也逐渐提高. 单纯形法计算步骤需要细心处理，用单纯形法解决问题时方法灵活多变，单纯形法在线性规划中应用广泛,使用单纯形法能使解题过程清晰、陌生问题熟悉化、抽象问题具体化等.206.2 启示使用单纯形法时应该多加练习基本步骤方法，当应用熟练时，遇到新的线性规划问题时，就可以很好的分辨出在本题中能不能把单纯形法简化，用哪种具体的单纯形法解题，这样，我们所遇到的问题也就迎刃而解了.与此同时也能让我们在解决问题时思路清晰、步骤明了，尤其是单纯形法中的人工变量法在解决实际问题和填空题较复杂的问题时作用很大. 但是具体的单纯形法在不同线性规划中的应用有所不同，方法很多，应用时要注意灵活地选择，不能生搬硬套.6.3 局限性本文主要就单纯形法及其应用做出研究说明，其主要是揭示单纯形法的方法步骤及特殊性，还有诸多知识需待补充，对于单纯形法的计算机编程算法未能详细写出.本文介绍的重点在于单纯形法的常规算法及应用，其余的还有待进一步探讨.单纯形法并不是线性规划的“万能方法” ，在应用单纯形法时，要合理有效地结合其它方法，灵活选择应用.6.4 努力方向单纯形法在解决线性规划问题时的应用非常灵活多变，合理选择适合的单纯形法能让我们的解题事半功倍，但单纯形法并不是短时间内就可以学习掌握的.学好基础知识、理解步骤方法才是熟练应用单纯形法的关键，只有熟练掌握单纯形法的基础知识，积累学习经验，我们才能够更深入的了解、研究单纯形法，提高解决数学问题的能力.21参考文献1敖特根单纯形法的产生与发展探析J西北大学学报，2012，(8):46-48 2章学仁线性规划M 上海: 上海交通大学出版社，1988: 103 3燕子宗、费浦生、万仲平线性规划的单纯形法及其发展M计算数学，2007，（6）:2-34郭照庄、岳雅璠、孙月芳单纯形法原理及其扩展J北华航天工业学院学报， 2014，(1):20-22 5陈宝林最优化理论与算法M 北京: 清华大学出版社，20056赵娜、唐帅单纯形法解线性规划问题的算法探究J吉林广播电视大学学报，2011，(9):48-497 薛毅,耿美英.运筹学与实验M.电子工业出版社, 2008. 9.8胡运权运筹学教程J清华大学出版社，2007，(3):4-59马振华运筹学与最优化理论卷M清华大学出版社，1998，29(7):33-3410刘红英、夏勇、周水生数学规划基础M北京航空航天大学出版社，2012:215-22011邓成梁运筹学的原理和方法M华中科技大学出版社，2001:1-13212王芳华一种简易的单纯形表J数学的实践与认识，2007，(3):4-52213申卯兴求解线性规划的单纯形法的直接方法M计算机工程与应用，2007，29(7):33-3414孟俊婷求单纯形法中初始基本可行解的新方法外点法M内蒙古科技与经济，2000:215-22015 海燕、 张妍基于单纯形法的线性规划问题改进解法M华中科技大学出版社，2011:1-132致致 谢谢值此论文完成之际，谨在此向四年来给予我关心、帮助的老师、同学和家人表示衷心的感谢！首先，特别感谢我的指导老师程毕陶，在论文的撰写过程中，从选题、编写提纲、资料收集、撰写、修改、最后定稿，他都给予了具体的指导，付出了大量的心血；他循循善诱的教导和不拘一格的思路给予我无尽的启迪这篇论文的每个数据，都离不开他的细心指导其次感谢曲靖师范学院,给我提供了一个很好的学习环境,让我能够顺利完成学业;感谢班主任谢莉桃老师在这四年里对我的帮助；感谢在学习期间给我诸多教诲和帮助的数学与信息科学学院的各位老师；感谢我的朋友和同学，感谢你们在我失意时给我鼓励，在失落时给我支持，感谢你们和我一路走来，让我在此过程中倍感温暖；感谢我的家人，让我可以拥有一个如此温馨的家庭，让我所有的一切都可以在你们这里得到理解与支持，得到谅解和分担。23