《纯形法进一步讨论》PPT课件

《《纯形法进一步讨论》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性规划和单纯形法单纯形法的进一步讨论单纯形法的进一步讨论－人工变量法人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。单纯形法的进一步讨论－人工变量法单纯形法的进一步讨论－人工变量法单纯形法的进一步讨论－人工变量法单纯形法的进一步讨论－人工变量法原问题的可行解新问题的可行解目标值结论：新问题的最优解中

2、，如果人工变量均为零，则得到的解也是原问题的最优解，否则原问题无可行解例6大M法-M0-10x500010x6-M00-11-21x6-M0014M-2M-3cj-zj101309x7-M011114x40x7x4x3x2x1b-M010-3cjXBCB表1-100x400011-1/2-1/2-1/20x23011/30001/3-3x11102/301/2-1/21/6cj-zj00303/2-M-3/2-M+1/2CBXBcj-30100-M-Mbx1x2x3x4x5x6x70x4330211-100x21-21-10-110-Mx766040331cj-zj6M

3、-304M+103M-4M00x400001-1/21/2-1/20x25/2-1/2100-1/41/41/4-3x33/23/20103/401/4cj-zj-2/9000-3/4-M+3/4-M-1/4最优解:X=(0,5/2,3/2,0,0,0,0)最优值：Z=3/2例8线性规划问题-31100MMcj→cj→-31100MM线性规划问题达到最优,最优解及最优值为:单纯形法进一步讨论第一阶段第一阶段最优解中:如果Z<0,则原问题没有基本可行解;如果Z=0,则若人工变量全为非基变量,则得到原问题的基本可行解.否则基本可行解退化,继续迭代就可以得到基本

4、可行解.单纯形法进一步讨论第二阶段以第一阶段最优基作为初始基本可行解,继续迭代.第一阶段例6两阶段法第一阶段：-10-10x500010x6-100-11-21x6-10004-2cj-zj101309x7-1011114x40x7x4x3x2x1b-10000cjXBCB表1-11请注意:第一阶段的最优解不是唯一的33-11x50-4-31-1x6-100-11-21x2000406cj-zj104066x7-1012033x40x7x4x3x2x1b-10000cjXBCB表1-1101/20-1/2x50-1-1/201/2x6-11/301/310

5、3x20-10000cj-zj1/602/3011x10-1/210000x40x7x4x3x2x1b-10000cjXBCB3/20300cj-zj1/20-1/2x5001/3103x2002/3011x1-312000x40x4x3x2x1b010-3cjXBCB表1-12第二阶段-3/43/4-1/4-1/2x50001-1/25/2x20000-9/2cj-zj0103/23/2x3110000x40x4x3x2x1b0000cjXBCB大M法举例CBXBcj1200-Mbx1x2x3x4x50x4111010-Mx54-12-101cj-zj01-M2+M0

6、00大M法举例CBXBcj-1-200-Mbx1x2x3x4x50x4111010-Mx54-12-101cj-zj01-M2+M000-2x2111010-Mx52-30-1-21cj-zj21-3M0-M2-2M0所有检验数<0已经是最优解，x5=2人工变量不为零,表示原问题无可行解(参照图解法结果)例9线性规划问题解：加入人工变量，给出第一阶段的线性规划模型:人工变量已经换出，则ω=0，得到基可行解，将第一阶段的人工变量取消，填入原问题的目标函数的系数，进行第二阶段运算。cj→0000011人工变量已经换出，则ω=0，得到基可行解，将第一阶段的人工变量取消，即上表

7、中划去人工变量所在列，填入原问题的目标函数的系数，进行第二阶段运算。cj→-31100最优解为：x1,=4,x2,=1,x3=9,最优值z=-2.