运筹学03单纯形法的进一步讨论：人工变量法VIP免费

1,,1,,1,,(1)(2).00,1,,0,max0,,min(jjiijimjjkkkjkkjmnimccajmnxPx找初始可行基,确定初始基可行解,建表.检验所有非基变量的检验数若所有;则已得最优解;停止计算;否则转(3).(3)在中,若有某对应的系数列向量则为无界解,停止计算;否则转(4).(4)根据()=确定为换入变量根据1:0),(5)(,,,,)(010).(6)(25),isiksikskTkkkskmkTskbbaxaaxPaaaxx确定为换出变量.将对应列向量变换为，，，，并将左侧基变量列中的换为重复直到所有检验数非负获得最优解.复习：单纯形法cj→c1…cm…cj…cnCB基bx1…xm…xj…xnic1x1b11…0…a1j…a1n1c2x2b20…0…a2j…a2n2……………………………cmxmbm0…1…amj…amnmj=cj-zj(检验数)0…0…miijijacc1…miininacc11,,min(:0)isikimikskbbaaa1,,max0jkjmn()=§5单纯形法的进一步讨论:人工变量法人工变量法（确定初始可行基）：原约束方程：AX=b加入人工变量：xn+1，，xn+m人工变量是虚拟变量，加入原方程中是作为临时基变量，经过基变换，将人工变量均能换成非基变量，所得解是最优解；若在最终表中检验数小于零，而且基变量中还有某个非零的人工变量，原问题无可行解。1111112112221111,,0,,,0nnnnnnmmnnnmmnnnmaxaxxbaxaxxbaxaxxbxxxx1、大M法方法：在约束条件中，加入人工变量后，要求目标函数不受影响？目标函数中人工变量的系数取（-M）。理由：目标函数实现最大化，就必须将人工变量从基变量中换出，否则目标函数就不可能取得最大化。例1：用大M法求解如下线性规划问题0,,12324112..3min32131321321321xxxxxxxxxxxtsxxxz0,,,,,,12324112..003min76543217316532143217654321xxxxxxxxxxxxxxxxxxxtsMxMxxxxxxz111-211000113-4120-1103/21-20[1]000110M16xx4x3103-20100-110[1]00-11-211-2010001-3x11x21x341001/3-2/32/3-5/310100-11-2900102/3–4/3-7/3-31100MM-10001M-1M+1zj-cj0001/31/3M-1/3M-2/3zj-cj0x41x21x312[3]001-22-5410100-11-21-2010001cj0MMX4X6X7bCBXBX1X2X3X4X5X6X7i-3+6M1-M1-3M0M00cj-zj-11-M00M03M-1cj-zj最优解是0,9,1,47654321xxxxxxx目标函数为-2。例4：maxz=4x1+3x2-3x1+2x2≤6s.t.-x1+3x2≥3x1,x2≥054354321542132154321:;,:0,,,,33623..0034maxxxxxxxxxxxxxxxxtsMxxxxxz人工变量松弛变量x1x2•无可行解0,124322..23max21212121xxxxxxtsxxzx1x254354321542132154321:;,:0,,,,124322..0023maxxxxxxxxxxxxxxxxtsMxxxxxz人工变量松弛变量2、两阶段法第一阶段：建立一个辅助线性规划并求解，以此判断原线性规划是否存在可行解。辅助线性规划问题：目标函数取成所有的人工变量之和，并对目标函数取极小化，约束条件依然为原问题的以单位矩阵作为可行基的标准型的约束条件。•所有人工变量都变成非基变量，目标函数值为0，原问题存在基可行解。转到第二阶段。•若目标函数值不为0，至少有一个人工变量不能从基变量中转出，原问题没有可行解。停止。第二阶段：从第一阶段最优表格中去掉人工变量，将目标函数系数换成原问题的目标函数系数，用单纯形法计算，直到得到最优解为止。例2：同上第一阶段：求解辅助规划问题0,,,,,,12324112..min765432173165321432176xxxxxxxxxxxxxxxxxxxtsxx0,,12324112..3min32131321321321xxxxxxxxxxxtsxxxz111-211000113-4120-1103/21-20[1]000110106xx4x3103-20100-110[1]00-11-211-201000100000110000011zj-cj0x40x20x312[3]001-22-5410100-11-21-2010000cj011X4X6X7bCBXBX1X2X3X4X5X6X7i6-1-30100cj-zj0-100103cj-zj12[3]001-2410100-11-20100-3112xx1x341001/3-2/3101...