第1章+线性规划与单纯形法-第4节

《第1章+线性规划与单纯形法-第4节》由会员分享，可在线阅读，更多相关《第1章+线性规划与单纯形法-第4节（22页珍藏版）》请在文档大全上搜索。

1、 运筹学运筹学（第三版）运筹学教材编写组 编清华大学出版社 第1章 线性规划与单纯形法 第4节 单纯型法的计算步骤钱颂迪 制作第1章 线性规划与单纯形法第4节 单纯型法的计算步骤第4节 单纯型法的计算步骤 根据以上讨论的结果，将求解线性规划问题的单纯形法的计算步骤归纳如下 如利用单纯型表，求解线性规划问题。 4.1 单纯型表 为了便于理解计算关系，现设计一种计算表，称为单纯形表，其功能与增广矩阵相似，下面来建立这种计算表。 将(1-22)式与目标函数组成n+1个变量，m+1个方程的方程组。 线性规划的方程组0111111221122111111nnmmmmmnmnmmmmnnmmnnmmxcx

2、cxcxczbxaxaxbxaxaxbxaxax为了便于迭代运算，可将上述方程组写成增广矩阵形式01000001000010211211,21, 211, 1121mnmmmnmmnmnmnmmbbbcccccaaaaaabxxxxxz若将z看作不参与基变换的基变量，它与x1,x2,xm的系数构成一个基，这时可采用行初等变换将c1,c2,cm变换为零，使其对应的系数矩阵为单位矩阵。得到miiimmiininmimiimmnmmnmnmnmmbcbbbaccaccaaaaaabxxxxxz121111,11,21, 211, 11210001000001000010可根据上述增广矩阵设计计算表，

3、表1-2。 miininmimiimmiiimmnmmmmmnmnmnmmBBinmmjaccaccbczaabxcaabxcaabxcxxxxbXCccccc111,111,221, 2222111,1111111100100001表1-2的说明 XB列中填入基变量，这里是x1，x2,，xm； CB列中填入基变量的价值系数，这里是c1,c2,cm；它们是与基变量相对应的； b列中填入约束方程组右端的常数； cj行中填入基变量的价值系数c1,c2,cn； i列的数字是在确定换入变量后，按规则计算后填入； 最后一行称为检验数行，对应各非基变量xj的检验数是miijijnjacc1, 2 , 1,

4、4.2 计算步骤 表1-2称为初始单纯形表，每迭代一步构造一个新单纯形表。 计算步骤： (1) 按数学模型确定初始可行基和初始基可行解，建立初始单纯形表。 (2) 计算各非基变量xj的检验数， 检查检验数，若所有检验数 则已得到最优解，可停止计算。否则转入下一步。 miijijjacc1,njj, 2 , 1, 0 (3) 在j0,j=m+1,n中，若有某个k对应xk的系数列向量Pk0，则此问题是无界，停止计算。 否则，转入下一步。 (4) 根据max(j0)=k，确定xk为换入变量，按规则计算lklikikiabaab0min (5) 以alk为主元素进行迭代(即用高斯消去法或称为旋转运算)