第4讲14表格单纯形法的计算步骤

《第4讲14表格单纯形法的计算步骤》由会员分享，可在线阅读，更多相关《第4讲14表格单纯形法的计算步骤（13页珍藏版）》请在装配图网上搜索。

1、第4讲14表格单纯形法的计算步骤1211,1112,122,112101000010000110mmnmnmnm mmnmmmnzxxxxxbaabaabaabccccc 为了便于迭代运算，可将上述方程组写成为了便于迭代运算，可将上述方程组写成增广矩阵形式增广矩阵形式1211,1112,122,11,1,i 1i 1i 10 1 000 0 100 0 011 0 00mmnmnmnmmmnmmmmmi i mni i ni izxxxxxbaabaabaabccaccacbjcnmmcccc11BCBXbmcc 1mxx 1mbb 1nmmxxxx 11im 1mnmmnmaaaa1,11,

2、11001ziibc 0 0 ijijjacc)min(0kjkjiaab 根据增广矩阵设计计算表根据增广矩阵设计计算表 0,12 4 16 4 8 2 21 22000032max6543216251421321654321xxxxxxxxxxxxxxxxxxxxxxZ例例 题：题：cj 2 3 0 0 0 0cBXBb x1 x2 x3 x4 x5 x60000 x3x4x5x61281612 2 2 1 0 0 0 1 2 0 1 0 0 4 0 0 0 1 0 0 4 0 0 0 1-z0 i2 3 0 0 0 012/28/212/4cj 2 3 0 0 0 0cBXBb x1 x2

3、 x3 x4 x5 x6000 x3x4x516 4 0 0 0 1 0 -zi3x23010001/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 i2 0 0 0 0 -3/46/2216/4cj 2 3 0 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

4、 0 -4 1 2 0 1 0 0 0 1/44412-z-13 0 0 0 -2 0 1/4icj 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 0i 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 0 1 0 0 0 1/42283x3 x1x5x20203 x1 x2 x3 x4 x5 x6bXBcB

5、 2 3 0 0 0 0cjicj 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 0i 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 0 1 0 0 0 1/42283x3 x1x5x20203 x1 x2 x3 x4 x5 x6bxBcB 2 3 0 0 0 0cji计算步骤计算步

6、骤对于目标函数求极大情形对于目标函数求极大情形(1)(1)按数学模型确定初始可行基和初始基可行解，按数学模型确定初始可行基和初始基可行解，建立初始单纯形表。建立初始单纯形表。(2)(2)计算各非基变量的检验数，计算各非基变量的检验数，检查检验数，若所有检验数检查检验数，若所有检验数则已得到最优解，可停止计算。否则转入下一步。则已得到最优解，可停止计算。否则转入下一步。miijijjacc1,njj,2,1,0(3)(3)在在j j0,j=m+1,0,j=m+1,n,n中，若有某个中，若有某个k k对应对应x xk k的的系数列向量系数列向量P Pk k00，则此问题是无界，停止计算。，则此问题

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