经管学院运筹学教案4单纯形法改

§4单纯形法的计算步骤本节重点：单纯形表（特别是检验数行）单纯形法的计算步骤大M法两阶段法解的存在情况判别cjfic1…cmcm+1…cnqICBXBbx1…xmxm+1…xnc1c2x1x2b1b210………00a1,m+1a2,m+1…………a1na2nq1

q2…cmxmbm0…1am,m+1…amnqm-z-z

值0…0sm+1…snXB

列——基变量，CB

列——基变量的价值系数(目标函数系数)cj

行——价值系数，b

列——方程组右侧常数q

列——确定换入变量时的比率计算值下面一行——检验数，中间主要部分——约束方程系数4．1

单纯形表用表格法求解LP，规范的表格——单纯形表如下：用单纯形方法求解s.tmax

z=40x1+45x2+24x3.1

2

3x

,

x

,x

‡

03x1+3x2

+2x3

£120

2x1

+3x2

+

x3

£100max

z

=

2x1+

3x2s.t.

x1

+

2

x2

£

84

x1£164

x2

£12x1，x2

‡0例1的初始单纯形表：cjfi23000qCB

XBbx1x2x3x4x5000x3x4x58161214020(

4)1000100014-3-z023000cjfi23000qCB

XBbx1x2x3x4x5003x3x4x22163140001100010-1/201/424--z-

92000-3/4X(0)=(0，0，8，16，12)T，

z0

=0cjfi23000qCB

XBbx1x2x3x4x5203x1x4x22831000011-40010-1/221/4-412-z-1300-201/4cjfi23000qCB

XBbx1x2x3x4x5003x3x4x22163(

1

)40001100010-1/201/424--z-92000-3/4X(1)=(0，3，2，16，0)T，

z1

=9cjfi23000qCB

XBbx1x2x3x4x5203x1x4x22831000011-40010-1/2(2

)1/4-412-z-1300-201/4cjfi23000qCB

XBbx1x2x3x4x5203x1x5x24421000010-21/21/41/2-1/8010-z-1400-1.5-1/80X(2)=(2，3，0，8，0)T，

z2

=13X(3)=(4，2，0，0,

4)T，

z3

=14单纯形法的计算步骤第一步：将线性规划模型标准化；第二步：选择单位矩阵的基为初始可行基（必要时要加人工变量），对应的变量为初始基变量，建立初始单纯形表；第三步：进行最优解的判别，即计算非基变量的检验数，若所有的检验数均£0，则目前的解为最优解；

计算结束，否则转步骤四。第四步：在单纯形表中选检验数最大的列为主元列，主元列对应的变量为入基变量用主元列，用主元列中的正元素去除对应的常数项，选最小者所对应的行为主元行，主元行对应的基变量为出基变量，主元行与主元列相交的元素为主元素。第五步：通过方程的初等变换将主元列中的主元素变为1，其它元素变为零，在基变量栏中，在原来出基变量的位置，改写成入基变量，得到新的单纯形表，转步骤三。max

z

=

6x1+

4x2s.t.2x1

+

x2

£

10x1

+

x2

£

8x2

£7x1，x2

‡0练习§5

单纯形法的进一步讨论几种情况一、目标函数为Min的情形三种处理方法：令Z’=

-Z

===> Max

Z’=

-CX

；求Min

Z，当所有检验数cj-zj>=0

时为最优，否则要迭代，换入检验数最小的那个变量，确定换出变量的方法和前面Max的情形一样；规定检验数为zj-cj，其余过程和前面Max的情形一样。例8min

z

=-3x1+x2+x3s.t.

311

2

3

x1

,

x2

,x3

‡

0+

x

=

1-

2

x-

4

x

+

x

+

2

x

‡

3x1

-

2

x2

+

x3

£

11标准型：max z’

=3x1-x2-x3s.t.=

131531

2+

x-

2

x-

x

=

3-

4

x

+

x

+

2

xx1

-

2

x2

+

x3

+

x4

=

11

x1

,

,

x5

‡

0其中第2、3个约束方程中无明显基变量，分别加上人工变x6,x7,二、约束方程为“>=”或“=”的情形（加人工变量）=

1171

361

2

3

5+

x

=

1x-

2

x

+-

4

x

+

x

+

2

x

-

x

+

x

=

3x1

-

2

x2

+

x3

+

x4

x1

,

,

x7

‡

0这时，初始基和初始基可行解很明显。X(0)=(0，0，0，11，0，3，1)T不满足原来的约束条件。如何使得可从

X(0)开始，经迭代逐步得到x6=0，x7=0的基可行解，从而求得问题的最优解，有两种方法：=

1161

2

3

5+

x7

=

1x3-

4

x

+

x

+

2

x

-

x

+

x

=

3x1

-

2

x2

+

x3

+

x4-

2

x1

+

x1

,

,

x7

‡

0只要原问题有可行解，随着目标函数向最大化方向的改善，人工变量一定会逐步换出基，从而得到原问题的基可行解，进而得到基最优解。反之，若加了人工变量的问题解后最优解中仍含人工变量为基变量，便说明原问题无可行解。例8的单纯形表格为：5.2

大M法在目标函数中加上惩罚项。max=3x1-x2-x3-Mx6-Mx7其中M为充分大的正数。X*

=

(4，1，9，0，0)T,

z*

=

2Cj3-1-100-M-MqCBXBbx1x2x3x4x5x6x70-M-Mx4x6x7111311-4-2-21012〔1〕1000-10010001113/21sj3-6MM-13M-10-M000-M-1x4x6x3101130-2-2[

1]00011000-10010-1-2111-1+M00-M0-3M+10-1-1x4x2x31211[

3]0-2010001100-2-1041000-13-1-1x1x2x34191000100011/302/3-2/3-1-4/3-2000-1/3-1/35.3

两阶段法第一阶段：以人工变量之和最小化为目标函数。

minw

=x6+x7只要原问题有可行解，该最小化问题的最优目标函数值就是0，解得的最优解x6=0，x7=0，对应原问题一个基可行解。反之若该问题的最优解目标函数值大于零，则说明原问题无可行解。第二阶段：以第一阶段的最优解(不含人工变量)为初始解，以原目标函数为目标函数。例8

试用两阶段法求解线性规划问题mins.t.11

2

3+

x

=

1-

2

x-

4

x

+

x

+

2

x

‡

3z

=-3x1+x2+x3

x1

-

2

x2

+

x3

£

113

x1

,

x2

,

x3

‡

0解：先在上述线性规划问题的约束方程中加入人工变量，给出第一阶段的数学模型为：min

w

=

x6+x7x1-2x2+x3+x4-4

x1+

x2+2x3

-x5

+

x6=11=3-2x1

+

x3

+

x7

=1x1，…，

x7

‡0第一阶段的单纯形表如下：cj0000011qCBXBbx1x2x3x4x5x6x7011x4x6x711311-4-2-21012[1]1000-10010001113/216-1-30100010x4x6x3101130-2-2[1]00011000-10010-1-21—1—0-100103000x4x2x3121130-2010001100-2-10210-5-204——00000111第一阶段求得的结果是w

=0,最优解是（0,1,1,12,0,0,0）T因人工变量x6=x7=0，所以(0,1,1,12,0)T

是原线性规划问题的基可行解。第二阶段运算:cj-31100qCBXBbx1x2x3x4x5011x4x2x31211[3]0-2010001100-2-104——σj-10001-311x1x2x34191000100011/302/3-2/3-1-4/3σj20001/31/3约束方程为“>=”或“=”的情形（加人工变量）人工变量法（确定初始可行基）：221

1

n

+2amn

xn

+

=

bma2

n

xn

+

xx

+a=

b1=

ba1n

xn

+

xn

+1a11

x1

+am1

x1

+

xn

+m原约束方程：AX=b加入人工变量：xn+1，…，xn+mx1

,,

xn

‡

0,

xn

+1

,,

xn

+m

‡

0人工变量是虚拟变量，加入原方程中是作为临时基变量，经过基的旋转变换，将人工变量均能换成非基变量，所得解是最优解；若在最终表中检验数小于零，而且基变量中还有某个非零的人工变量，原问题无可行解。用两阶段法求下面线性规划问题的解Max Z=2x1+

x

2+

x

3s.t. 4x1+2x2+

2x

3≥42x1+4x2

≤204x1+8x2+

2x

3≤16x1，x2，x

3≥05.4

线性规划问题解的讨论一、无可行解max

z=2x1+4x2x1

+x2

£102x1

+x2

‡

40x1

,x2

‡0人工变量不能从基底换出，此时原线性规划问题无可行解。x1x2-40cjfi0000-1CBXBbx1x2x3x4x5q0X310[1]1100101x540210-1140/2cj-zj210-10Z0=-0x11011100-1x5200-1-2-11cj-zj0-1-2-10Z1=-20两阶段法二、退化问题基可行解的正分量个数小于约束条件个数m。右侧常数中有零时，初始解就是退化解。单纯形法计算中，计算q

值时有两个以上比值同为最小，这样在下一次迭代中就会出现零值的基变量，出现退化解。一般，出现退化情况时，不必特殊处理，一般不会出现由于死循环得不到最优解的情况。勃兰特规则(P35)可避免死循环。例:max

z=3x1+4x2x1

+x2

£402x1+x2£60x1-x2

=0x1

,x2

‡0此题初始解是退化的。最优解也是退化解。退化解迭代中，当换入变量取零值时目标函数值没有改进，x1x2c

j

→3400-MθCBXBbx1x2x3x4x50x340111000x4602101-1-Mx50[1]-1001c

j

-

z

j3+M4-M0000x3400[2]100x46003013x101-100c

j

-

z

j07004x220011/200x4000-3/213x120101/20c

j

-

z

j00-3.500x30001-1/34x2200101/33x1201001/3c

j

-

z

j000-7/3三、有无穷多最优解的情况最优解中有非基变量的检验数等于零的情况。以这种非基变量作为换入变量，迭代可求得另一基最优解。任一最优解可表示为所有基最优解的凸组合。例

max

z=3x1+5x23x1

+5x2

£15如果将x

换入基底，得1另一解，由可行域凸性易知，有两个最优解必有无穷多组最优解当非基底变量的检验数中有取零值，或检验数中零的个数大于基变量个数时，有无穷多解。qCBXB

b0002x1

+ x2

£52x1+2x2

£11x1

,x2

‡03

5

0

0

0x1

x2

x3

x4

x53511/25000Z

=0x3153[5

]100x4521010x51122001cj-zj35000x233/511/500x427/50-1/510x554/50-2/501cj-zj00-100Z1=15x1x2四、无（有）界解max

z=x1+x2-2x1+x2

£4x1-

x2

£2-3x1+x2£3x1

,x2

‡0若检验数有大于0，而对应系数列中元素全部小于或等于零（无换出变量）则原问题有无界解。练习：写出单纯形表,分析检验数与系数关系并画图验证。线性规划解除有唯一最优解的情况外，还有如下几种情况无可行解退化无穷多解无界解人工基可行检验数检验数大变量解中非中零的于零，但不能零元素个数多对应列元从基个数小于基变素小于等底中换