单纯形法在线性规划中与应用.docVIP

单纯形法在线性规划中的应用 0引言 20世纪30年代末，苏联数学家康特罗维奇研究交通运输及机械加工等部门的生产管理工作，于1939年写了《生产组织与计划中的数学方法》一书初稿，为线性规划建立数学模型及解法奠定基础,自此开始，线性规划经过不断的应用和发展，在工业、农业生产管理，交通运输的指挥调度，资源开发，商业和银行等领域得到广泛应用，显著提高了企业的经济效益。随着生产规模的扩大和经济事务变得日益繁杂，对线性规划提出了更多的理论要求，又促使这门学科迅速发展和完善。线性规划不断发展，适用领域不断拓宽，从解决技术问题的最优化设计，到工业、农业、商业、交通运输业、军事、经济计划及管理等领域都发生着作用，已成为现代科学管理的重要基础理论。 例如，在生产管理和经济活动中，经常遇到这些问题，如生产计划问题，即如何合理利用有限的人、财、物等资源，以便得到最好的经济效果；材料利用问题，即如何下料使用材最少；配料问题，即在原料供应量的限制下如何获取最大利润；劳动力安排问题，即如何用最少的劳动力来满足工作的需要；运输问题，即如何制定调运方案，使总运费最小；投资问题，即从投资项目中选取方案，使投资回报最大等等。对于这些问题，都能建立相应的线性规划模型。事实上，线性规划就是利用数学为工具，来研究在一定条件下，如何实现目标最优化。 解线性规划问题目前最常见的方法有两种，图解法和单纯形法。单纯形法是求解线性规划问题的通用方法。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。单纯形法的一般解题步骤可归纳如下：把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。若基本可行解不存在，即约束条件有矛盾，则问题无解。若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。若迭代过程中发现问题的目标函数值无界，则终止迭代。 当实际模型非标准形式时，可以通过以下变换化为标准形式： ①当目标函数为时，可令Z′=-Z，而将其写成为 求得最终解时，再求逆变换Z=-Z′即可。 ②当s·t·中存在形式的约束条件时，可引进变量 便写原条件成为 其中的xn+1称为松驰变量，其作用是化不等式约束为等式约束。 同理，若该约束不是用“≤”号连接，而是用“≥”连接，则可引进松驰变量 使原条件写成 2 单纯形法 2.1 单纯形法的基本原理 单纯形法迭代原理： 确定初始可行解 当线性规划问题的所有约束条件均为≤号时，松弛变量对应的系数矩阵即为单位矩阵，以松弛变量为基变量可确定基可行解。 对约束条件含≥号或=号时，可构造人工基，人为产生一个m×m单位矩阵用大M法或两阶段法获得初始基可行解。 最优性检验与解的判别（目标函数极大型） 当所有变量对应的检验数均非正时，现有的基可行解即为最优解。若存在某个非基变量的检验数为零时，线性规划问题有无穷多最优解；当所有非基变量的检验数均严格小于零时，线性规划问题具有唯一最优解。 若存在某个非基变量的检验数大于零，而该非基变量对应的系数均非正，则该线性规划问题具有无界解（无最优解）。 当存在某些非基变量的检验数大于零，需要找一个新的基可行解，基要进行基变换。 2.1 确定初始可行解 确定初始的基本可行解等价于确定初始的可行基，一旦初始的可行基确定了，那么对应的初始基本可行解也就唯一确定，为了讨论方便，不妨假设在标准型线性规划中，系数矩阵Ａ中前m个系数列向量恰好构成一个可行基，即Ａ=（ＢＮ），其中Ｂ=（Ｐ1，Ｐ2，…Ｐm）为基变量x1，x2，…xm的系数列向量构成的可行基，Ｎ=(Ｐm+1，Pm+2， …Pn)为非基变量xm+1，xm+2， …xn的系数列向量构成的矩阵。 所以约束方程就可以表示为 用可行基Ｂ的逆阵Ｂ-1左乘等式两端，再通过移项可推得： 若令所有非基变量，则基变量 由此可得初始的基本可行解 2.2 最优性检验 假如已求得一个基本可行解，将这一基本可行解代入目标函数，可求得相应的目标函数值 其中分别表示基变量和非基变量所对应的价值系数子向量。 要判定是否已经达到最大值，只需将代入目标函数，使目标函数用非基变量表示，即： 其中称为非基变量ＸN的检验向量，它的各个分量称为检验数。若σN的每一个检验数均小于