《纯形法进一步讨论.ppt》由会员分享，可在线阅读，更多相关《纯形法进一步讨论.ppt（28页珍藏版）》请在三一办公上搜索。
1、线性规划和单纯形法,单纯形法的进一步讨论,单纯形法的进一步讨论人工变量法,人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。,单纯形法的进一步讨论人工变量法,单纯形法的进一步讨论人工变量法,单纯形法的进一步讨论人工变量法,单纯形法的进一步讨论人工变量法,原问题的可行解新问题的可行解目标值,结论：新问题的最优解中，如果人工变量均
2、为零，则得到的解也是原问题的最优解，否则原问题无可行解,例6 大M法,最优解:X=(0,5/2,3/2,0,0,0,0)最优值：Z=3/2,例8 线性规划问题,-3 1 1 0 0 M M,cj,cj,-3 1 1 0 0 M M,线性规划问题达到最优,最优解及最优值为:,单纯形法进一步讨论,第一阶段,第一阶段最优解中:如果Z0,则原问题没有基本可行解;如果Z=0,则若人工变量全为非基变量,则得到原问题的基本可行解.否则基本可行解退化,继续迭代就可以得到基本可行解.,单纯形法进一步讨论,第二阶段,以第一阶段最优基作为初始基本可行解,继续迭代.,第一阶段,例 6 两阶段法,第一阶段：,请注意:第
3、一阶段的最优解不是唯一的,第二阶段,大M法举例,大M法举例,所有检验数0 已经是最优解，x5=2 人工变量不为零,表示原问题无可行解(参照图解法结果),例9 线性规划问题,解：加入人工变量，给出第一阶段的线性规划模型:,人工变量已经换出，则=0，得到基可行解，将第一阶段的人工变量取消，填入原问题的目标函数的系数，进行第二阶段运算。,cj,0 0 0 0 0 1 1,人工变量已经换出，则=0，得到基可行解，将第一阶段的人工变量取消，即上表中划去人工变量所在列，填入原问题的目标函数的系数，进行第二阶段运算。,cj-31 1 0 0,最优解为：x 1,=4,x 2,=1,x 3=9,最优值z=-2.,
