运筹学 单纯形法的计算步骤

关于运筹学单纯形法的计算步骤4．1 单纯形表

用表格法求解LP，规范的表格——单纯形表如下：第2页,共25页，2024年2月25日，星期天计算步骤(1).找出初始可行基，确定初始基可行解，建立初始单纯形表。(2).检验各非基变量xj的检验数，若

j

0，j=m+1，…，n；则已得到最优解，可停止计算，否则转入下一步。(3).在

j

>0，j=m+1，…，n中，若有某个

k对应xk的系数列向量Pk

0，则此问题是无界解，停止计算。否则，转入下一步。(4).根据max(

j>0)=

k，确定xk为换入变量，按

规则计算

=min{bi/aik\aik>0}可确定第l行的基变量为换出变量。转入下一步。第3页,共25页，2024年2月25日，星期天

23000

12

10040

01004

001

02300000081612x3x4x54-3

23000

2

1

0

10-1/2

-92000-3/4003x3x4x224-()

3

0

1001/4

16

4

0010X(0)=(0，0，8，16，12)T，z0=0第4页,共25页，2024年2月25日，星期天

23000

2

1

010-1/2-1300-201/4203x1x4x2-412

3

0

100

1/4

8

0

0-41

2

23000

2

1

0

10-1/2

-92000-3/4003x3x4x224-

3

0

1001/4

16

4

0010()

X(1)=(0，3，2，16，0)T，z1=9第5页,共25页，2024年2月25日，星期天

23000

2

1

010-1/2-1300-201/4203x1x4x2-412

3

0

100

1/4

8

0

0-41

2()

23000

4

1

00

1/40-1400-1.5-1/8

0203x1x5x2

2

0

11/2

-1/8

0

4

0

0-2

1/21

X(2)=(2，3，0，8，0)T，z2=13

X(3)=(4，2，0，4，0)T，z3=14第6页,共25页，2024年2月25日，星期天§5单纯形法的进一步讨论5．1 人工变量法

解决初始基可行解的问题。当某个约束方程中没有明显的基变量时，在该方程中加上人工变量。第7页,共25页，2024年2月25日，星期天其中第2、3个约束方程中无明显基变量，分别加上人工变x6,x7第8页,共25页，2024年2月25日，星期天这时，初始基和初始基可行解很明显。X(0)=(0，0，0，11，0，3，1)T不满足原来的约束条件。如何使得可从X(0)开始，经迭代逐步得到x6=0，x7=0的基可行解，从而求得问题的最优解，有两种方法：第9页,共25页，2024年2月25日，星期天反之，若加了人工变量的问题解后最优解中仍含人工变量为基变量，便说明原问题无可行解。例3的单纯形表格为：

只要原问题有可行解，随着目标函数向最大化方向的改善，人工变量一定会逐步换出基，从而得到原问题的基可行解，进而得到基最优解。3.大M法在目标函数中加上惩罚项

max=3x1-x2-x3-Mx6-Mx7其中M为充分大的正数。第10页,共25页，2024年2月25日，星期天3-6M M-1 3M-1 0

-M 0 0

0x4

103-20100-1-Mx610[1]00-11-21-1x31-2010001

1 -1+M 0 0

-M 0-3M+1

0x4

12[3]001-2-1x210100-14-1x31-20100

1 0 0 0

-1

3x1

41001/3-2/3-1x210100-1-1x390012/3-4/3

000-1/3-1/3

X*=(4，1，9，0，0),z*=2第11页,共25页，2024年2月25日，星期天2.两阶段法第一阶段：以人工变量之和最小化为目标函数 min

=x6+x7

第二阶段：以第一阶段的最优解(不含人工变量)为初始解，以原目标函数为目标函数。第12页,共25页，2024年2月25日，星期天第13页,共25页，2024年2月25日，星期天第14页,共25页，2024年2月25日，星期天第15页,共25页，2024年2月25日，星期天5.2线性规划问题解的讨论一、无可行解

maxz=2x1+4x2

x1+x210

2x1+x2

40

x1,x20人工变量不能从基底换出，此时原线性规划无可行解x1x2

CBXBbX3

x5

0-1

0000-1

x1x2x3x4x540210-1110[1]1100cj

1040/2x1

x5

0-1

200-1-2-111011100

cj-zj0-1-2-10cj-zj210-10Z0=-40Z1=-20第16页,共25页，2024年2月25日，星期天第17页,共25页，2024年2月25日，星期天

例:maxz=3x1+4x2

x1+x240

2x1+x260

x1-x2=0

x1,x20

此题初始解是退化的。最优解也是退化解。退化解迭代中，当换入变量取零值时目标函数值没有改进，x1x20x340111000x4602101-1-Mx50[1]-10010x3400[2]100x46003013x101-1003+M4-M000zj-cj

000-7/3

zj-cj

0x30001-1/3

4x2200101/33x1201001/3cj→3400-M

CB

XBbx5

θx1x2x3

x4

0700zj-cj00-3.50zj-cj4x220011/200x4000-3/213x120101/20第18页,共25页，2024年2月25日，星期天第19页,共25页，2024年2月25日，星期天

例maxz=3x1+5x2

3x1+5x215

2x1+x25

2x1+2x211

x1,x20

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

CBXBbx3

x4x5

00035000

x1x2x3x4x5521010153[5]1003511/5x2

x4x5

50033/511/50027/50-1/51054/50-2/501

cj-zj