纯形法进一步讨论.pptxVIP

线性规划和单纯形法单纯形法的进一步讨论

单击此处添加大标题内容

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

单纯形法的进一步讨论－人工变量法

单击此处添加大标题内容

单纯形法的进一步讨论－人工变量法

单纯形法的进一步讨论－人工变量法

单纯形法的进一步讨论－人工变量法01原问题的可行解新问题的可行解目标值02结论：新问题的最优解中，如果人工变量均为零，则得到的解也是原问题的最优解，否则原问题无可行解03

例6大M法-M0-10x500010x6-M00-11-21x6-M0014M-2M-3cj-zj101309x7-M011114x40x7x4x3x2x1b-M010-3cjXBCB表1-10

0x400011-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-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线性规划问题

-3 1 100MMcj→

cj→-3 1 100MM线性规划问题达到最优,最优解及最优值为:

第一阶段单

纯

形

法

进

一

步

讨

论第一阶段最优解中:如果Z0,则原问题没有基本可行解;如果Z=0,则若人工变量全为非基变量,则得到原问题的基本可行解.否则基本可行解退化,继续迭代就可以得到基本可行解.

第一阶段单

纯

形

法

进

一

步

讨

论第二阶段以第一阶段最优基作为初始基本可行解,继续迭代.

例6两阶段法第一阶段：-10-10x500010x6-100-11-21x6-10004-2cj-zj101309x7-1011114x40x7x4x3x2x1b-10000cjXBCB表1-11

表1-11请注意:第一阶段的最优解不是唯一的33-11x50-4-31-1x6-100-11-21x2000406cj-zj104066x7-1012033x40x7x4x3x2x1b-10000cjXBCB01/20-1/2x50-1-1/201/2x6-11/301/3103x20-10000cj-zj1/602/3011x10-1/210000x40x7x4x3x2x1b-10000cjXBCB

第二阶段3/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+M000

大M法举例CBXBcj-1-200-Mbx1x2x3x4x50x4111010-Mx54-12-101cj-zj01-M2+M000-2x2111010-Mx52-30-1-21cj-zj21-3M0-M2-2M0所有检验数0已经是最优解，x5=2人工变量不为零,表示原问题无可行解(参照图解法结果)

例9线性规划问题01解：加入人工变量，给出第一阶段的线性规划模型:02

人工变量已经换出