数学规划第三章-单纯形法.ppt

《数学规划第三章-单纯形法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章单纯形法本章内容最优基本可行解的判断基本可行解的改进初始基本可行解的确定退化情况与Bland法则单纯形法的基本思想：从标准型线性规划的一个基本可行解出发，在确定它不是线性规划问题的最优解后，能求得另外一个基本可行解并使目标函数值下降。单纯形法的核心：（1）如何判断一个基本可行解为最优解（2）如何从一个非最优基本可行解求得另一个改进了的基本可行解或矩阵形式：minz=cxs.t.Ax=bx≥0式中，A为m×n矩阵，秩为m其约束函数和目标函数可用矩阵表示为：对于线性规划问题：初始表设B是A的一个基，令B由A的前m列组成，则基变量xB=（x1，…，x

2、m）T。则前述系数矩阵可通过初等行变换变作：对应于基B的标准型表基变量与非基变量的关系：基B的基本解：当yi0≥0（i=1，…，m）时，即为基本可行解，此时目标函数值是否为最优解？若对j=m+1，…，n均满足ri≥0，且xj≥0，则有：由此表明：最小值对应的最优解为对于基B的标准型表中，最后一行的rm+1，…，rn，有：任一可行解x对应的目标函数值：基变量与非基变量之间又有：因此，标准型表的求解过程可概括为：标准型表变换注意事项：1、m阶方阵B变成每行每列有且仅有一个元素为1，其余元素为0；2、B中m列对应的表上最后一行元素为0；3、基本变量根据最优

3、性和可行性来选择，并不一定要逐项挨着选择。单纯形法的思路找出一个初始基可行解是否最优转移到另一个基可行解（找出更大的目标函数值）最优解是否循环核心是：变量迭代结束例3.1-2用单纯形法求下列线性规划的最优解解：1）将问题化为标准型，加入松驰变量x3、x4则标准型为:2）求出线性规划的初始基可行解，列出初始单纯形表。cj3400θicB基bx1x2x3x40x34021100x43013013400检验数松驰变量x3、x4系数均为1，若令x1=x2=0，则可求得初始基本可行解x3=40，x4=30。3）进行最优性检验如果表中所有检验数，则表中的基可行解就

4、是问题的最优解，计算停止。否则继续下一步。4）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表确定换入基的变量。选择，对应的变量xj作为换入变量，当有一个以上检验数大于0时，一般选择最大的一个检验数，即：，其对应的xk作为换入变量。确定换出变量。根据下式计算并选择θ，选最小的θ对应基变量作为换出变量。用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。5）重复3）、4）步直到计算结束为止。cj3400θicB基变量bx1x2x3x40x34021100x430130

5、134000x34x23x14x2换入列bi/ai2，ai2>04010换出行将3化为15/311801/301/3101－1/3303005/30－4/3乘以1/3后得到103/5－1/51801－1/5－2/5400－1－1随堂练习1用单纯形法求解