单纯形法进一步讨论.pptx

单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法p人工变量法：人工变量法：p前面讨论了在标准型中系数矩阵有单位矩前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问阵，很容易确定一组基可行解。在实际问题中有些模型题中有些模型并不含有单位矩阵并不含有单位矩阵，为了得，为了得到一组基向量和初基可行解，在约束条件到一组基向量和初基可行解，在约束条件的等式左端加一组的等式左端加一组虚拟变量虚拟变量，得到一组基，得到一组基变量。这种人为加的变量称为变量。这种人为加的变量称为人工变量人工变量，构成的可行基称为人工基，用大构成的可行基称为人工基，用大M M法或两阶法或两阶段法求解，这种用人工变量作桥梁的求解段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。方法称为人工变量法。单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法原问题的可行解新问题的可行解目标值结论：新问题的最优解中，如果人工变量均为零，则得到的解也是原问题的最优解，否则原问题无可行解例6 大M法-M0-10 x500010 x6-M00-11-21x6-M0014M-2M-3cj-zj101309x7-M011114x40 x7x4x3x2x1 b -M010-3 cjXBCB表1-100 x400011-1/2-1/2-1/20 x23011/30001/3-3x11102/301/2-1/21/6cj-zj00303/2-M-3/2-M+1/2CBXB cj-30100-M-M b x1x2x3x4x5x6x70 x4330211-100 x21-21-10-110-Mx766040331cj-zj6M-30 4M+103M-4M00 x400001-1/21/2-1/20 x25/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 8 线性规划问题线性规划问题 -3 1 1 0 0 M M cj cj -3 1 1 0 0 M M 线性规划问题达到最优线性规划问题达到最优,最优解最优解及最优值为及最优值为:单单纯纯形形法法进进一一步步讨论第一阶段第一阶段第一阶段最优解中:如果Z0,则原问题没有基本可行解;如果Z=0,则若人工变量全为非基变量,则得到原问题的基本可行解.否则基本可行解退化,继续迭代就可以得到基本可行解.单单纯纯形形法法进进一一步步讨论第二阶段第二阶段以第一阶段最优基作为初始基本可行解,继续迭代.第一阶段第一阶段例 6 两阶段法第一阶段：-10-10 x500010 x6-100-11-21x6-10004-2cj-zj101309x7-1011114x40 x7x4x3x2x1 b -10000 cj XB CB表1-11请注意:第一阶段的最优解不是唯一的33-11x50-4-31-1x6-100-11-21x2000406cj-zj104066x7-1012033x40 x7x4x3x2x1 b -10000 cj XB CB表1-1101/20-1/2x50-1-1/201/2x6-11/301/3103x20-10000cj-zj1/602/3011x10-1/210000 x40 x7x4x3x2x1 b -10000 cj XB CB3/20300cj-zj1/20-1/2x5001/3103x2002/3011x1-312000 x40 x4x3x2x1 b 010-3 cj XB CB表1-12第二阶段-3/43/4-1/4-1/2x50001-1/25/2x20000-9/2cj-zj0103/23/2x3110000 x40 x4x3x2x1 b 0000 cj XB CB大M法举例 CB XBcj1200-Mb x1x2x3x4x50 x4111010-Mx54-12-101cj-zj01-M 2+M000大M法举例CBXBcj-1-200-Mb x1x2x3x4x50 x4111010-Mx54-12-101cj-zj01-M2+M000-2x2111010-Mx52-30-1-21cj-zj21-3M0-M2-2M0所有检验数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.