运筹学 单纯形法介绍

《运筹学 单纯形法介绍》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章3.1单纯形法单纯形法求解线性规划的思路：一般线性规划问题具有线性方程组的变量数大于方程个数，这时有不定的解。但可以从线性方程组中找出一个个的单纯形，每个单纯形可以求得一组解，然后再判断该解使目标函数值是增大还是变小，决定下一步选择的单纯形。这就是迭代，直到目标函数实现最大值或者最小值为止。这样问题就得到了最优解。【2】单纯形法的计算步骤如下：第一步：对线性规划数学模型进行标准化，构造一个初始基可行解；第二步：判断当前基本可行解是否是最优解；第三步：若当前解不是最优解，则进行基变换迭代到下一个基本可行解。例：目标函数(3-1)满足约束条件(3-2)【3】在上述问题约

2、束条件中加入松弛变量，，，使不等式变成等式。这时得到标准型：(3-3)(3-4)约束方程(3-4)的系数矩阵从（3-4）式可以看到的系数列向量4，，是线性独立的，这些向量构成一个基对应B的变量为基变量，从（3-4）式中可以得到（3-5）将(3-5)式代入目标函数（3-1）式得到当令非基变量便得到z=0。这时得到一个基可行解将有关数字输入表中，得到初始单纯形表，见表3-6表3-6→230000b000X3X4X58161214020[4]1000100014-323000表3-6中左上角的是表示目标函数中各变量的价值系数。在列填入初始基变量的价值系数，它们都为零，各非基变量

3、的检验数为（1）因检验数都大于零，且有正分量存在，转入下一步；4（1），对应的变量为换入变量，计算它所在行对应的为换出变量。所在列和所在行的交叉处[4]称为主元素或轴元素。（2）以[4]为主元素进行旋转运算，即初等行变换，使变为，在列中将替换，于是得到新表3-7表3-7→230000b003X3X4X22163[1]40001100010-1/201/424-2000-3/4b列的数字是=2，=16，=3。于是得到新的基可行解，目标函数的取值z=9（3）检查表3-7的所有，这时；说明应为换入变量。重复（1）~（4）的计算步骤，得表3-8。表3-8→230000b203X1

4、X5X24421000010-21/21/41/2-1/801000-3/2-1/80(5)表3-8最后一行的所有检验数都已为负或零。这表示目标函数值已不可能再增大，于是得到最优解43.2改进单纯形法当用单纯形表解释线性规划问题时，每行每列的数字都要计算，而有些行列的数字在下一步计算时并不需要。改进单纯形法通过矩阵运算求线性规划问题的关键是计算。3.4工具求解在进行线性规划运算，常用的方法是单纯形法以及单纯形的一些改进方法。但单纯形法求解步骤较为繁琐，需要画对个表来运算。对于一些复杂的线性问题，运算过程就显得很复杂。在日常生活中，人们开始尝试用计算机求解，省去大量繁琐的求

5、解过程。至今已经有很多软件是针对线性规划而设计的，如Excel的规划求解，以及专业的求解工具Lingo和Matlab等。这些软件各有其优点。3.4.1Excel规划求解Microsoftexcel的“规划求解”工具取自得克萨斯大学奥斯汀分学的LeonLasdon和克里夫兰州大学的AllanWaren共同开发的GRG2（GeneralizedReducedGradient）非线性最优化代码。[4]Excel电子表格处理软件，不仅能处理日常工作中的各种表格，同时还可以利用Excel内部提供的大量函数及工具进行数据处理与分析。【5】Excel与专业软件相比，有以下特点：1、Ex

6、cel软件方便易学，大部分人都比较熟悉，容易掌握；2、能用表格简单直观地体现数学模型；3、Excel具有大量的内建函数，通过设置参数，就能进行复杂的计算，建模过程简单；4、Excel软件具有强大的数据分析功能。Excel求解步骤如下：1.创建表格4