单纯形法课程论文

《单纯形法课程论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、最优化方法课程论文题目：单纯形法的发展及其应用系别：理学院专业：信息与计算科学姓名：班级：信息101班单纯形法的发展及其应用一．单纯形法简介：单纯形法，求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因基本可行解的个数有

2、限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。二．单纯形法在线性规划中的应用1.单纯形法解线性规划问题在生产管理和经济活动中，经常遇到这些问题，如生产计划问题，即如何合理利用有限的人、财、物等资源，以便得到最好的经济效果；材料利用问题，即如何下料使用材最少；配料问题，即在原料供应量的限制下如何获取最大利润；劳动力安排问题，即如何用最少的劳动力来满足工作的需要；运输问题，即如何制定调运方案，使总运费最小；投资问题，即从投资项目中选取方案，使投资回报最大等等。对于这些问题，都能建立相应的线性规划模型。事实上，线性规划就是利用数学为工具，来研

3、究在一定条件下，如何实现目标最优化。单纯形法是求解线性规划问题的通用方法。(1)单纯形法解线性规划问题的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。(2)单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。(3)单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约

4、束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。(4)概述根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…xn的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值

5、）的可行解称为最优解。这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可

6、行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有10^6个决策变量和10^4个约束条件的线性规划问题已能在计算机上解得。2.线性规划问题的标准化使用单纯形法求解线性规划时，首先要化问题为标准形式所谓标准形式是指下列形式：当实际模型非标准形式时，可以通过以下

7、变换化为标准形式：①当目标函数为时，可令Z′=-Z，而将其写成为求得最终解时，再求逆变换Z=-Z′即可。②当s·t·中存在形式的约束条件时，可引进变量便写原条件成为其中的xn+1称为松驰变量，其作用是化不等式约束为等式约束。同理，若该约束不是用“≤”号连接，而是用“≥”连接，则可引进松驰变量使原条件写成3.单纯形法迭代原理（1）确定初始可行解①当线性规划问题的所有约束条件均为≤号时，松弛变量对应的系数矩阵即为单位矩阵，以松弛变量为基变量可确定基可行解。②对约束条件含≥号或=号时，可构造人工基，人为产生一个m×m单位矩阵用大M法或两阶段法获得初始基可行解。（2）最

8、优性检验与解的判别（目标