表格单纯形法的计算步骤.ppt

《表格单纯形法的计算步骤.ppt》由会员分享，可在线阅读，更多相关《表格单纯形法的计算步骤.ppt（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1.41.4（表格）单纯形法的计算步骤（表格）单纯形法的计算步骤 为了便于理解计算关系，现设计一种计算表，为了便于理解计算关系，现设计一种计算表，称为单纯形表，其功能与增广矩阵相似，下面称为单纯形表，其功能与增广矩阵相似，下面来建立这种计算表。来建立这种计算表。线性规划的方程组线性规划的方程组 为了便于迭代运算，可将上述方程组写成为了便于迭代运算，可将上述方程组写成增广矩阵形式增广矩阵形式根据增广矩阵设计计算表根据增广矩阵设计计算表例例 题：题：cj 2 3 0 0 0 0cBXBb x1 x2 x3 x4 x5 x60000 x3x4x5x61281612 2 2 1 0 0 0 1 2 0

2、 1 0 0 4 0 0 0 1 0 0 4 0 0 0 1-z0 2 3 0 0 0 012/28/212/4cj 2 3 0 0 0 0cBXBb x1 x2 x3 x4 x5 x6000 x3x4x516 4 0 0 0 1 0 -z3x23010001/42620100-1/210010 0-1/2cj 2 3 0 0 0 0cBXBb x1 x2 x3 x4 x5 x60003x3x4x5x262163 2 0 1 0 0 -1/2 1 0 0 1 0 -1/2 4 0 0 0 1 0 0 1 0 0 0 1/4-z-9 2 0 0 0 0 -3/46/2216/4cj 2 3 0

3、0 0 0cBXBb x1 x2 x3 x4 x5 x60203x3 x1x5x22283 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/44412-z-13 0 0 0 -2 0 1/4cj 2 3 0 0 0 0cBXBb x1 x2 x3 x4 x5 x60203x6 x1x5x2 4402 0 0 2 -4 0 1 1 0 1 -1 0 0 0 0 -4 4 1 0 0 1 -1/2 1 0 0-z-14 0 0 -1/2 -1 0 0 0 0 0 -2 0 1/4-13-z4412 0 0 1 -2 0 1/2 1 0

4、0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/42283x3 x1x5x20203 x1 x2 x3 x4 x5 x6bXBcB 2 3 0 0 0 0cjcj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60203x3 x1x6 x2 0442 0 0 1 -1 -1/4 0 1 0 0 0 1/4 0 0 0 0 -2 1/2 1 0 1 0 1/2 -1/8 0-z-14 0 0 0 -3/2 -1/8 0 0 0 0 -2 0 1/4-13-z4412 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2

5、0 1 0 0 0 1/42283x3 x1x5x20203 x1 x2 x3 x4 x5 x6bxBcB 2 3 0 0 0 0cj计算步骤计算步骤对于目标函数求极大情形对于目标函数求极大情形(1)(1)按按数数学学模模型型确确定定初初始始可可行行基基和和初初始始基基可可行行解解，建建立初始单纯形表。立初始单纯形表。(2)(2)计算各非基变量的检验数，计算各非基变量的检验数，检查检验数，若所有检验数检查检验数，若所有检验数则已得到最优解，可停止计算。否则转入下一步。则已得到最优解，可停止计算。否则转入下一步。(3)(3)在在j j0,j=m+1,n0,j=m+1,n中中，若若有有某某个个k

6、k对对应应x xk k的的系数列向量系数列向量P Pk k00，则此问题是无界，停止计算。，则此问题是无界，停止计算。否则，转入下一步。否则，转入下一步。(4)(4)根根据据max(max(j j0)=0)=k k，确确定定x xk k为为换换入入变变量量，按按规则计算规则计算(5)(5)以以alk为为主主元元素素进进行行迭迭代代(即即用用高高斯斯消消去去法法或或称称为为旋旋转运算转运算)，把，把xk所对应的列向量所对应的列向量 将将XB列列中中的的xl换换为为xk，得得到到新新的的单单纯纯形形表表。重重复复(2)(5)，直到终止。，直到终止。练习练习 0 0 -1/12 -7/24-33/4-z x2x112 x1 x2 x3 x4bxBcB 2 1 0 0cj15/43/4011/4-1/810-1/125/24