单纯形法表的解题步骤

《单纯形法表的解题步骤》由会员分享，可在线阅读，更多相关《单纯形法表的解题步骤（8页珍藏版）》请在金锄头文库上搜索。

1、Made By Haowei Song 单纯形法表的解题步骤单纯形法表的解题步骤 单纯形法表结构如下： jc 对应变量的价值系数 i BC bX b 1x 2x 3x ? jx 基变量的价值系数 基变量 资源列 规则求的值 j 检验数 一般形式一般形式 若线性规划问题标准形式如下： 123451231425max2300028416 412 0,1,2,5jzxxxxxxxxxx xx xj=+= +=+= =?取松弛变量345,x x x为基变量，它对应的单位矩阵为基。这样就得到初始可行基解：( )()00,0,8,16,12TX=。将有关数字填入表中，得到初始单纯形表，如表1-1所示： 表

2、表 1-1 ( )()00,0,8,16,12TX= jc 2 3 0 0 0 i BC bX b 1x 2x 3x 4x 5x 0 3x 8 1 2 1 0 0 4 0 4x 16 4 0 0 1 0 - Made By Haowei Song 0 5x 12 0 4 0 0 1 3 j 2 3 0 0 0 若检验数均未达到小于等于0，则对上表进行调整。选择上表中检验数最大的列，该列对应的非变量为入基变量；再应用规则该列对应的各基变量对应的值，选出其中最小的一行，该行对应的基变量为出基变量。修改单纯形表，对各行进行初等变换，确保基变量组成的矩阵为单为矩阵。修改后的单纯形表如表1-2所示： 表

3、表 1-2 ( )()10,3,2,16,0TX= jc 2 3 0 0 0 i BC bX b 1x 2x 3x 4x 5x 0 3x 2 1 0 1 0 1 2 2 0 4x 16 4 0 0 1 0 4 3 2x 3 0 1 0 0 1 4- j 2 1 0 0 3 4 检验数12,0 ，则进行继续调整，调整后的单纯形法表如表1-3所示： 表表 1-3 ( )()22,3,0,8,0TX= jc 2 3 0 0 0 i BC bX b 1x 2x 3x 4x 5x 2 1x 2 1 0 1 0 1 2 - 0 4x 8 0 0 -4 1 2 4 3 2x 3 0 1 0 0 1 412

4、j 0 0 -2 0 1 4Made By Haowei Song 表1-3中， 50，则继续进行调整，调整结果如表1-4所示： 表表 1-4 ( )()34,2,0,0,4TX= jc 2 3 0 0 0 i BC bX b 1x 2x 3x 4x 5x 2 1x 4 1 0 0 1 40 0 5x 4 0 0 -2 1 21 3 2x 2 0 1 1 21 8 0 j -2 0 3 2 1 8 0 检验数0j，这表示目标函数值已不可能再增大，于是得到最优解： ( )()3*4,2,0,0,4TXX= *14z = 带人工变量带人工变量 现有线性规划问题： 12312312313123min

5、321142321,0zxxxxxxxxxxxx x x= + += 将上述线性规划问题用大M法求解，在约束条件中加入松弛变量4x，剩余变量5x，人工变量6x，7x得到： 1234567123412356137min300211423 21 0,1,2,7jzxxxxxMxMxxxxx xxxxx xxx xj= += +=+= =?Made By Haowei Song 其中，M是一个任意大的正数。用单纯形法表进行计算，由于是求MIN，所以用所有0j来判别目标函数是否实现了最小化。初始单纯行表如表2-1所示： jc -3 1 1 0 0 M M i BC bX b 1x 2x 3x 4x 5

6、x 6x 7x 0 4x 11 1 -2 1 1 0 0 0 11 M 6x 3 -4 1 2 0 -1 1 0 3 2M 7x 1 -2 0 1 0 0 0 1 1 j -3+6M 1-M1-3M0 M 0 0 jc -3 1 1 0 0 M M i BC bX b 1x 2x 3x 4x 5x 6x 7x 0 4x 10 3 -2 0 1 0 0 -1 - M 6x 1 0 1 0 0 -1 1 -2 1 1 3x 1 -2 0 1 0 0 0 1 - j -1 1-M 0 0 M 0 3M-1 jc -3 1 1 0 0 M M i BC bX b 1x 2x 3x 4x 5x 6x 7

7、x 0 4x 12 3 0 0 1 -2 2 -5 4 1 2x 1 0 1 0 0 -1 1 -2 - 1 3x 1 -2 0 1 0 0 0 1 - j -1 0 0 0 1 M-1 M+1 Made By Haowei Song jc -3 1 1 0 0 M M i BC bX b 1x 2x 3x 4x 5x 6x 7x -3 1x 4 1 0 0 1 32 3 2 35 3 1 2x 1 0 1 0 0 -1 1 -2 1 3x 9 0 0 1 2 34 3 4 37 3 j 0 0 0 1 31 3M-1 3M-2 3上表中得到最优解，12345674,1,9,0,2xxxxxx

8、xz= 两阶段法（含有人工变量的线性规划问题）两阶段法（含有人工变量的线性规划问题） 下面介绍求解加入人工变量的线性规划问题的两阶段法。 第一阶段：第一阶段： 不考虑原问题是否存在基可行解， 给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。如 111111121 12221 112min001,0nn mnnnnnnnmmnnn mmn mxxxxa xa xxb a xa xxba xaxxb x xx+=+= += += ? ? ? ?然后用单纯形法求解上述模型，若得到0=,这说明原问题存在基可行解，可以进行第二阶段计算。否则原问题无可行解，应停止计算。 第二阶

9、段：将第一阶段计算得到的最终表，除去人工变量。将目标函数行的系数，换成原问题的目标函数系数，作为第二阶段计算的初始表。 各阶段计算方法及步骤与第3节单纯形法相同。下面举例说明。 例：线性规划问题 12312312313min3211423211, 2, 30zxxxxxxxxxxxx xx= + += Made By Haowei Song 解：先在上述线性规划问题的约束方程中加入人工变量，给出第一阶段的数学模型为： 671234123561374567min211423211, 2, 3,0xxxxxxxxxxxxxxx xxx x x x=+= +=+= 这里6x，7x是人工变量。用单纯形

10、法求解，如表3-1所示： 表表 3-1 两阶段法求解含人工变量的线性规划问题两阶段法求解含人工变量的线性规划问题 第一阶段第一阶段 jc 0 0 0 0 0 1 1 i BC bX b 1x 2x 3x 4x 5x 6x 7x 0 4x 11 1 -2 1 1 0 0 0 11 1 6x 3 -4 1 2 0 -1 1 0 3 21 7x 1 -2 0 1 0 0 0 1 1 j 6 -1 -3 0 1 0 0 jc 0 0 0 0 0 1 1 i BC bX b 1x 2x 3x 4x 5x 6x 7x 0 4x 10 3 -2 0 1 0 0 -1 - 1 6x 1 0 1 0 0 -1

11、1 -2 1 0 3x 1 -2 0 1 0 0 0 1 - j 0 -1 0 0 1 0 3 jc 0 0 0 0 0 1 1 i BC bX b 1x 2x 3x 4x 5x 6x 7x Made By Haowei Song 0 4x 12 3 0 0 1 -2 2 -5 0 2x 1 0 1 0 0 -1 1 -2 0 3x 1 -2 0 1 0 0 0 1 j 0 0 0 0 0 1 1 第一阶段求得的结果是0=，得到最优解是： 12345670,1.1,12,0xxxxxxx= 因为人工变量670xx=，所以()0,1,1,12,0T是该线性规划问题的基可行解。于是可以进行第二阶段

12、运算。 将第一阶段的最终表中的人工变量取消并填入原问题的目标函数的系数。进行第二阶段的计算，如表3-2所示： 表表 3-2 两阶段法求解含人工变量的线性规划问题两阶段法求解含人工变量的线性规划问题 第二阶段第二阶段 jc -3 1 1 0 0 i BC bX b 1x 2x 3x 4x 5x 0 4x 12 3 0 0 1 -2 4 1 2x 1 0 1 0 0 -1 - 1 3x 1 -2 0 1 0 0 - j -1 0 0 0 1 jc -3 1 1 0 0 i BC bX b 1x 2x 3x 4x 5x -3 1x 4 1 0 0 1 32 3 1 2x 1 0 1 0 0 -1 1 3x 9 0 0 1 2 34 3 j 0 0 0 1 31 3Made By Haowei Song 表3-2中得到最优解为1234,1,9xxx=，目标函数值2z = 。 退化情况退化情况 单纯形法计算中用规则确定换出变量时， 有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。这时换出变量。 尽管计算过程的循环现象极少出现，但还是有可能的。可利用勃兰特规则解决该问题： （1）选取0jjcz中下标最小的非基变量kx为换入基变量，即 ()min|0jjkj cz= （2）当按规则计算存在两个和两个以上最小比值时，选取下标最小的基变量为换出变量。