单纯形法的综述及其应用 　文献综述.doc

文献综述 单纯形法的综述及其应用 　 前言部分（说明写作的目的，介绍有关概念、综述范围，扼要说明有关主题争论焦点） 1.写作目的 本文主要在于介绍单纯形法的历史背景，基本计算方法，改进的计算方法，以及单纯形法的应用．目的在于对单纯形法的历史背景，计算方法等进行综述，并总结单纯形法在生活各个领域的应用，单纯形法是求解线性规划问题很有效的方法，通过对单纯形法的进一步了解，最后提出一实际问题利用单纯法进行分析求解． 2.有关概念 LP问题的一般形式[1] 线性规划问题的标准型为[2] 其矩阵形式为 其中，，决策向量． 为约束条件中的系数矩阵, 即 本文除了介绍线性规划问题的一般形式、标准形式和矩阵形式以外还列举了一些定义. 定义1[3]：设矩阵的秩为，矩阵是中的一个阶满秩子方阵，则为一个基矩阵．矩阵中剩余元素组成的子阵为,即.把的分量相应地分成两部分，记成和，的分量与的列对应，称为基变量；的分量与中的列对应，称为非基变量．在约束中令所有的非基变量取值为零时，得到解，称为相应于的基本解． 定义2[3]：基本解得基变量都取非负值时，即满足的基本解为基本可行解． 定义3[4]：满足式（1）各约束条件的解称为可行解.全部可行解的集合称为可行域.目标函数达到最大值的可行解称为最优解. 定义4[4]：设为约束方程组的阶系数矩阵，设(),其秩为，为矩阵中的一个阶的满秩子矩阵，称为线性规划问题的一个基.不失一般性，设 中每一个向量称为基向量；与基向量对应的变量称为基变量.基变量以外的的变量称为非基变量. 定义5[4]：在约束方程组中，令所有非基变量 . 此时约束方程组有唯一解.将此解加上非基变量取０的值，有，称为线性规划问题的基本解.基本解总数不超过个. 3.综述范围 通常，求解LP模型时，常用基本单纯形方法、大M法、两阶段法等，所以在文献[5-8]具体介绍了求解线性规划的单纯形法的一些计算方法．根据对模型中是否存在单位基矩阵、存在怎么样的基矩阵等特征的判断来选择方法或判断解的存在与否等情况．这就是说，在求解线性规划的单纯形法中，初始基(矩阵)的确定是一个基本问题．通常使用大M法和两阶段法，通过人工构造，人为地在系数矩阵中形成一个单位矩阵作为初始基，再进行单纯形法的迭代[9]． 由于越来越多的领域借助于线性规划来做出最优决策，完善线性规划理论及其有效解法已成为重要研究课题．单纯形法作为求解线性规划问题较实用而有效的算法已在实际中得到广泛应用．本文在文献[10-11]简述关于单纯形算法的讨论、优化设计与实现，分析了单纯形算法的主要特点． 最后本文例举一些单纯形法在实际问题应用例子来说明单纯形法是处理运筹学模型的一种重要方法． 4.主题的争论 各种资源的最优配置已成为当今节约型社会的研究热点．它广泛应用于国防、科技、工业、农业、交通运输、环境工程、教育、经济及社会科学等领域，是指在一定的人力、物力、财力等资源条件下，如何合理利用这些资源完成最多任务或得到最大效益的方法．线性规划的资源最优配置是研究在一组线性约束之下，目标线性函数的最小值或最大值问题[3]． Dantzig在1947年提出了求解线性规划问题的单纯形算法．单纯形算法是寻找最优基本可行解的一种行之有效的算法[12]. 二、主体部分（阐明有关主题的历史背景、现状和发展方向，以及对这些问题的评述） （一）历史背景 单纯形法是求解线性规划问题的通用方法．它是是美国数学家G.B.丹齐克于1947年首先提出来的．它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到．顶点所对应的可行解称为基本可行解．单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行．因基本可行解的个数有限，故经有限次转换必能得出问题的最优解．如果问题无最优解也可用此法判别． （二）现状 1.基本定理 下面主要介绍一下在单纯形法的综述及其应用中所涉及的一些基本定理. 定理1[3]：若式（1）存在有界最优解，则必从基本可行解中得到． 定理2[9]:若矩阵经过有限次初等行（列）变换变换成矩阵则，的行（列）向量组与的行（列）向量组等价，而的任意个列（行）向量与中对应的个列（行）向量有相同的线性相关性． 定理3[4]:若线性规划问题存在可行解，则问题的可行域为凸集. 定理4[4]:线性规划问题的基本可行解对应线性规划问题可行域的顶点. 定理5[4]:若线性规划问题有最优解，一定存在一个基本可行解是最有解. 2．单纯形法的计算 （1）计算步骤 单纯形表 … … … … … … … … … … 0 … 0 …