单纯形法的综述及其应用 　　　开题报告

《单纯形法的综述及其应用 　　　开题报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、开题报告单纯形法的综述及其应用　　　一、选题的背景、意义（所选课题的历史背景、国内外研究现状和发展趋势）（一）历史背景单纯形法是求解线性规划问题的通用方法．它是是美国数学家G.B.丹齐克于1947年首先提出来的．它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到．顶点所对应的可行解称为基本可行解．单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行．因基本可行解的个数有限，故经有限次转换必能得出问题的最优解．

2、如果问题无最优解也可用此法判别．（二）现状1.基本定理下面主要介绍一下在单纯形法的综述及其应用中所涉及的一些基本定理.定理1[1]：若式存在有界最优解，则必从基本可行解中得到．定理2[2]:若矩阵经过有限次初等行（列）变换变换成矩阵则，的行（列）向量组与的行（列）向量组等价，而的任意个列（行）向量与中对应的个列（行）向量有相同的线性相关性．定理3[3]:若线性规划问题存在可行解，则问题的可行域为凸集.定理4[3]:线性规划问题的基本可行解对应线性规划问题可行域的顶点.定理5[3]:若线性规划问题有最优解，一定存在一个基本可行解是最有解.2．单纯形法的计算（1）计算步骤单纯形表

3、…………………………0…0…列依次标明各方程的基变量；是基变量相应的价值系数，它们是与基变量相对应的；列是约束方程组右端的常数；行是基变量的价值系数；列的数字是在确定换入变量后，按规则计算后填入；最后一行称为检验数行，对应各非基变量的检验数是．现在把单纯性法的的计算步骤归纳如下：第一步对于一个已知的可行基，写出B对应的典式以及对应的基可行解，第二步检查检验数，如果所有检验数（j=1,2,…,n）则便是最优解，计算结束，否则转下一步．第三步如果有检验数，而，则问题无最优解，计算结束，否则转下一步．第四步如果有检验数，且中有正数，则取为进基变量（若有多个正检验数，可任选一个，一般

4、来说选取最大的检验数有利于提高迭代效率），并求最小比值由此来确定为离基变量（若上述最小比值同时在几个比值上达到，则选取其中下标最小的变量为离基变量），然后用代换得新基，再接下一步．第五步求出新基的典式（计算或直接通过初等行变换来实现）以及对应的基可行解，然后，以取代B，取代，返回第二步[4]．（2）单纯形法的进一步讨论人工变量：大M法和两阶段法为了解线性规划问题需要一个初始基可行解，为此常常借助于大M法或两阶段法．大M法：在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函数取值不受影响，为此假定人工变量在目标函数中的系数为（-M）（M为任意大的正数），这样目标

5、函数要实现最大化时，必须把人工变量从基变量换出．否则目标函数不可能实现最大化．在许多线性规划问题中，引进松弛变量化成标准形式后，约束条件方程组的系数矩阵并不含m阶单位矩阵，这样就给单纯形解法的换基迭代带来了困难，为了很快找到第一个可行基，在利用单纯形法求解时，首先要在线性规划问题中引入人工变量，把问题变为约束方程组的系数矩阵中含有单位阵，用以作为人造基，然后再按照单纯形法进行换基迭代，求得最优解或判定无最优解．这种方法就称为两阶段法．第一阶段：不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化．如然后用单纯形法求解上述模型

6、，若得到，这说明原问题存在基可行解，可以进行第二段计算．否则原问题无可行解，应停止计算．第二阶段：将第一阶段计算得到的最终表，除去人工变量．将目标函数行的系数，换原问题的目标函数系数，作为第二阶段计算的初始表．大法与两阶段法都是从寻求线性规划问题的一个初始可行基引入的．从形式上看，它们是两种不同的方法，但在本质上是一致．3．单纯形法的算法（1）改进单纯形算法通常使用大M法和两阶段法，通过人工构造，人为地在系数矩阵中形成一个单位矩阵作为初始基，再进行单纯形法的迭代．这样，往往无意中扰乱了思想主线，增加了计算量．特别对于人工计算显得运算操作繁杂而偏离了主体，在理解和教学中常常带来

7、不便．通过对单纯形法求解法的实质的分析和认识，提出了基于矩阵初等变换初始可行基的获得方法，进而得到基于单纯形法的求解线性规划模型的直接方法使单纯法的运用简单明白．利用这种确定初始可行基的方法求解线性规划问题时，首先，对线性规划模型的系数增广矩阵进行上述的初等行变换而得到阶的初始可行基，接着，将所得初始可行基安排入单纯形表，然后，进行单纯形表的表上作业程序．这样做的优点不仅在于可以给出初始可行基，而且可以方便地发现不独立的约束，并将其提前剔除，以减少单纯形法的计算量．具体步骤为:步骤1对增广矩阵施行一系列