运筹学单纯形法的进一步讨论

关于运筹学单纯形法的进一步讨论一、LP问题的标准化LP模型的标准形式运筹学第4讲：单纯形法的进一步讨论maxZ=CXs.t.AX=b

X≥0

目标函数为max型

X≥0b≥0!

单纯形法仅适于LP标准模型的求解第2页,共21页，2024年2月25日，星期天非标准型LP模型的标准化（P10）一、若目标函数为：minZ=CX

令Z’=-Z，则原目标函数转化为maxZ’=-CX二、若存在bi<0

将bi所在的约束条件式两边同乘（－1）三、若约束条件不等式为“≤”左式加入松弛变量xj，xj≥0运筹学第4讲：单纯形法的进一步讨论第3页,共21页，2024年2月25日，星期天五、若存在xj无约束可令xj=xj’-xj’’,xj’,xj’’≥0六、若存在xj<0

令xj’=-xj，xj≥0四、若约束条件不等式为“≥”左式减去剩余变量xj，xj≥0运筹学第4讲：单纯形法的进一步讨论第4页,共21页，2024年2月25日，星期天minz=x1+2x2+3x3

s.t. -2x1+x2+x3≤9-3x1+x2+2x3≥4 4x1-2x2-3x3=-6

x1≤0

,x2≥0，x3无约束例1：将下述LP模型转化为标准型运筹学第4讲：单纯形法的进一步讨论第5页,共21页，2024年2月25日，星期天maxz=-3x1+x3

s.t. x1+x2+x3≤4-2x1+x2-x3≥1 3x2+x3=9

x1,

x2,x3≥0例2：求解如下LP模型：运筹学第4讲：单纯形法的进一步讨论第6页,共21页，2024年2月25日，星期天二、人工变量法(大M法)

为使LP标准模型的初始可行基为单位矩阵，填入人工变量！

在目标函数中，令人工变量的系数为任意大的负值，采用“－M”表示。

当所有检验数σj≤0，但基变量中仍含有非零的人工变量，说明该LP模型无可行解。运筹学第4讲：单纯形法的进一步讨论第7页,共21页，2024年2月25日，星期天

退化问题：当存在多个相同的θ最小比值，或存在多个相同的最大σj>0时，说明模型中存在多余的约束，使多个基可行解对应同一顶点。当模型存在退化解时，处理方法如下：

θ最小比值相同时，取下标值最大的变量为换出变量

σj最大值相同时，取下标值最小的变量为换入变量运筹学第4讲：单纯形法的进一步讨论第8页,共21页，2024年2月25日，星期天

大M法的问题在于：采用手工计算求解不会碰到问题，但用计算机求解时，对M只能在计算机中输入一个机器最大字长的数字；显然，如果其他参数值大于或与这个数字相近，便会导致计算结果发生错误！运筹学第4讲：单纯形法的进一步讨论第9页,共21页，2024年2月25日，星期天maxz=-4x1–x2

s.t. 3x1+x2=34x1+3x2-x3=

6

x1+

2x2+x4=4

x1-4≥0例3：P20例2.6运筹学第4讲：单纯形法的进一步讨论第10页,共21页，2024年2月25日，星期天运筹学第4讲：单纯形法的进一步讨论第11页,共21页，2024年2月25日，星期天三、二阶段法

针对大M法存在的问题，我们可以对添加人工变量后的LP模型分为两个阶段来计算，称为二阶段法(P22)。

第一阶段：先求一个目标函数中只包含人工变量的LP模型，也就是说，令目标函数中其他变量的系数为0，人工变量的系数为某个正常数(一般为1)，在原问题约束条件不变的情况下求解。第二阶段：当第一阶段求解结果表明模型有可行解时，在原问题中去除人工变量，从第一阶段的最优解出发，继续求解。例4：采用二阶段法求解P22中LP模型运筹学第4讲：单纯形法的进一步讨论第12页,共21页，2024年2月25日，星期天运筹学第4讲：单纯形法的进一步讨论首先应确定当x5,x6=0时，可行域是否存在！则第一阶段先求解如下的LP模型：显然，若z=0，即x5,x6=0，则问题的可行域存在。第13页,共21页，2024年2月25日，星期天运筹学第4讲：单纯形法的进一步讨论x5,x6=0，则z=0，问题的可行域存在。第14页,共21页，2024年2月25日，星期天运筹学第4讲：单纯形法的进一步讨论去除x5和x6，进一步求解第二阶段的LP模型：得到最优解和最优值。第15页,共21页，2024年2月25日，星期天四、采用单纯形法求解的几种情况

惟一最优解无可行解(P23-例2.7)

所有检验数σj≤0，但基变量中仍含有非零人工变量无界解(例5)

当存在最大的σj>0，但θ值无解多重最优解(例6:习题2-1)

当所有检验数≤0，但存在非基变量σj

=0，该非基变量可以作为换入变量，模型存在多重最优解运筹学第4讲：单纯形法的进一步讨论第16页,共21页，2024年2月25日，星期天maxz=3x1+2x2

s.t. -2x1+x2≤2

x1-3x2≤

3

x1,

x2≥0例5：求解如下LP模型运筹学第4讲：单纯形法的进一步讨论第17页,共21页，2024年2月25日，星期天cj→3200bbi/aikcBXBx1x2x3x50x3-21102/0x4[1]-30133δj(1)3200maxz=3x1+2x2

+0x3+0x4

s.t. -2x1+x2+x3=2

x1-3x2+x4=

3

x1,

x2≥0解：将模型化为标准型，运筹学第4讲：单纯形法的进一步讨论第18页,共21页，2024年2月25日，星期天cj→3200bbi/aikcBXBx1x2x3x50x3-21102/0x4[1]-30133δj(1)32000x30-5128/3x11-3013/δj(2)0110-3

由于max{σj|σj>0}所对应的θ值无解，则该LP问题解无界。运筹学第4讲：单纯形法的进一步