单纯形法求解全过程详解共9页

单纯形法例题：某工厂生产I、II两种商品,已知生产单位商品所需的设备台时、A、B两种原材料的消耗、设备使用台时限额以及原材料的限额如下表所示。该工厂每生产一件商品I可获利3元，每生产一件商品II可获利4元。写出使该工厂所获利润最大的线性规划模型,

解：设生产产品I的数量为x1，生产产品II的数量为x2，所获利润为z，相应的模型为：

maxz

=3x1+4x2⎧2x1+x2≤40⎪

⎨x1+3x2≤30⎪x,x≥0⎩12

maxz=3x1+4x2⎧2x1+x2+x3=40⎪

⎨x1+3x2+x4=30⎪x,x,x,x≥0⎩1234

用单纯形法求解。

3,x4]T。（3）将初始基B1=[P3,P4]对应的基变量按顺序填入单纯形表中的XB一列。

3

4

XB

b

4030

x1

21

x2

13

x3

10

x4

01

x3x4

这时，我们可以得到初始基B1=[P3,P4]对应的基可行解。

即令非基变量x1=0,x2=0，根据表中的约束条件可得x3=40,x4=30（这两个值正好是表中基变量对应的资源向量b对应的分量，为什么？）第一个基可行解为X1=[0,0,40,30]T。

（4）找到了第一个基可行解，接下来的任务就是判断该基可行解是否为最优解，检验其是否为最优解的标准是：非基变量xj对应的检验数σj=cj−CB⋅B−1⋅Pj是否≤0。如果所有

非基变量的检验数σj均≤0，那么该基可行解为最优解，如果有一个或若干个非基变量的检验数σj>0，那么该基可行解不是最优解，需要继续找另一个基可行解。因为我们选择的初始基B1=I，所以其逆矩阵B1−1=I。相应的，检验数σj=cj−CB⋅B−1⋅Pj，⇒σj=cj−CB⋅Pj。

在计算检验数时需用到CB（基变量在目标函数中的系数向量），将CB填入表格最左一列中。

3

4

CB

00

XB

b

4030

x1

21

x2

13

x3

10

x4

01

x3x4

接下来就是计算非基变量的检验数（基变量的检验数均等于0，为什么?）

3

4

CB

00

XB

b

4030

x1

21

x2

13

x3

100

x4

010

x3x4

σj(1)=cj−CB⋅Pj

这时，非基变量的检验数：

⎛2⎞⎛1⎞

⎟⎜，()均>0，σ1=c1−CB⋅P1=3−(0,0)⋅⎜=3σ=c−C⋅P=4−0,0⋅22B2⎜1⎟⎜3⎟⎟=4；⎝⎠⎝⎠

所以该基可行解还不是最优解。接下来，我们的任务就是找另一个基可行解。当然，我们希望接下来的这第二个基可行解X2对应的目标函数值比第一个基可行解X1对应的目标函数值更接近max值。

（5）找另一个基可行解。

由非基变量→基变量的决策变量，我们称之为进基变量，挑选原则：maxσjσj>0=σk，那么xk进基（即由非基变量变为基变量）。

由基变量→非基变量的决策变量，我们称之为出基变量，挑选原则：

{}

⎧b⎫b

。min⎨iaik>0⎬=l，那么原来的第l个基变量出基（即由基变量变为非基变量）

aalk⎩ik⎭

我们称alk为主元素，简称主元，在单纯形表中用[]表示。题中，进基变量：

max{σ1=3,σ2=4}=σk=σ2，即x2进基成为基变量。

⎧b⎫⎧bb⎫30⎧40⎫b

出基变量：min⎨iaik>0⎬=min⎨1,2=min=40,=10⎬=2，即第2个

3⎩1⎭a22⎩a12a22⎭⎩aik⎭

基变量出基，第2个基变量是x4，所以是x4出基成为非基变量。主元为a22。

总结：x2进基成为基变量，x4出基成为非基变量。也就是说x2代替x4成为基变量，即：

3

4

CBXB

b

x1x2x3x4

bi

aik

40

=401

x3x4

402110

03013

[3]4

00

10

30=103

σj(1)=cj−CB⋅Pj

04

x3x2

这时的基变矢XB2=[x3,x2]T。这两个基变量对应的系数列向量组成的矩阵即为B2。因为在计算非基变量的检验数的计算过程中会用到B2−1,计算逆矩阵是一件麻烦事，我们当然不想干，怎么办呢？为了计算简便，我们期待B2=[P3,P2]=I，目前我们只是期待而已。下面先把我们的“期待”填入单纯形表中。

3400

CBXB

b

x1x2x3x4

biaik

40

=401

x3x4

402110

03013

[3]401

0010

10

30=103

σj(1)=cj−CB⋅Pj

04

x3x2

σj(2)=cj−CB⋅Pj

先来看X1对应的主元a22所在的行。行的系数表示的是约束条件：30=x1+3x2+x4②。对应于X2，我们期待的是：在这个约束条件中，x2的系数＝1，x3的系数＝0。要做到这一点，只需在等式左右同除以3（主元a22本身），得10=②等价。

接着看另一行。即第一行，该行的系数表示的是约束条件：40=2x1+x2+x3①。对应于X2，我们期待的是：在这个约束条件中，x2的系数＝0，x3的系数＝1。要做到这一点，需要将①－1×②’⇒30=

11

x1+x2+x4②’，式②’与式33

51

x1+x3−x4①’，式①’与式①等价。33

51⎧

30=x+x−x413⎪⎧40=2x1+x2+x333为实现我们的期待，将约束条件⎨就等价的代换成⎨

1130=x+3x+x124⎩⎪10=x1+x2+x433⎩

将这两个与原约束条件等价的约束条件填入表格中。

3400

CBXB

b

x1x2x3x4

biaik

40

=401

x3x4

402110

03013

[3]401

0010

10

30=103

σj(1)=cj−CB⋅Pj

04

x3x2

3010

5313

−

1313

σj(2)=cj−CB⋅Pj

这时，我们可以得到基B2=[P3,P2]对应的基可行解。

即令非基变量x1=0,x4=0，根据表中的约束条件可得x3=30,x2=10（这两个值正好是表中基变量对应的资源向量b对应的分量）那么，第2个基可行解为X2=[0,10,30,0]T。

（6）找到了第2个基可行解，接下来的任务就是判断该基可行解是否为最优解，检验其是否为最优解的标准前面已经详细讲述，这里就不啰唆了。即转回到步骤（4）。

3

4

CBXB

b

x1x2x3x4

bi

aik

40

=401

x3x4

402110

03013

[3]40

001

10

30=103

σj(1)=cj−CB⋅Pj

x3

30

53

−

13

4

x2

10

σj(2)=cj−CB⋅Pj

这时，非基变量的检验数σ1=

1353

10

00

134−3

54

,σ4=−，其中σ1>0，所以该基可行解不是最优解。33

（7）接下来，我们的任务就是找另一个基可行解。即转回到步骤（5）。

5⎫⎧

选择进基变量：max⎨σ1=⎬=σk=σ1，即x1进基成为基变量。

3⎭⎩

出基变量：min⎨

⎧b1b2⎫3⎧⎫b1

，即第1个基变量出基，第,⎬=min⎨30×=18,10×3=30⎬=

5⎩⎭a11⎩a11a21⎭

1个基变量是x3，所以是x3出基成为非基变量。主元为a11。

总结：x1进基成为基变量，x3出基成为非基变量。也就是说x1代替x3成为基变量，即：

3

4

CBXB

b

x1x2x3x4

bi

aik

40

=401

x3x4

402110

03013

[3]4

00

10

30=103

σj(1)=cj−CB⋅Pj

x3x2

30

5[]31353

01

1−3134−3

330×=18

5

41010

00

10×3=30

σj(2)=cj−CB⋅Pj

34

x1x2

σj(3)=cj−CB⋅Pj

这时的基变矢XB3=[x1,x2]T。这两个基变量对应的系数列向量组成的矩阵即为B3。

同样的，我们期待B3=[P1,P2]=I。

3400

CBXB

b

x1x2x3x4

biaik

40

=401

x3x4

402110

03013

[3]4

00

10

30=103

σj(1)=cj−CB⋅Pj

x3x2

30

5[]31353

10

01

1−3134−3

330×=18

5

4101001

00

10×3=30

σj(2)=cj−CB⋅Pj

34

x1x2

σj(3)=cj−CB⋅Pj

先来看主元a11所在的行。行的系数表示的是约束条件：30=

51

x1+x3−x4①’。33

我们期待的是：在约束条件中，x1的系数＝1，x2的系数＝0。要做到这一点，只需在等式

531

（主元a11本身），得18=x1+x3−x4①’’，式①’’与式①’等价。353

11

接着看另一行。即第二行，该行的系数表示的是约束条件：10=x1+x2+x4②’。

33

左右同除以

我们期待的是：在约束条件中，x1的系数＝0，x2的系数＝1。

112

要做到这一点，需要将②’－×①’’⇒4=x2−x3+x4②’’，式②’’与式②’

355

等价。

5131⎧⎧30=x+x−x18=x+x−x413413⎪⎪33就等价的代换成55约束条件⎨⎨1112⎪10=x1+x2+x4⎪4=x2−x3+x4

3355⎩⎩

将这些系数填入表格中。

3400

CBXB

b

x1x2x3x4

bi

aik

40

=401

x3x4

402110

03013

[3]4

00

10

30=103

σj(1)=cj−CB⋅Pj

x3x2

30

5[]31353

10

01

1−3134−31−525

330×=18

5

4101001

00

10×3=30

σj(2)=cj−CB⋅Pj

34

x1x2

184

351−5

σj(3)=cj−CB⋅Pj

这时，我们可以得到基B3=[P1,P2]对应的基可行解。

即令非基变量x3=0,x4=0，根据表中的约束条件可得x1=18,x2=4（这两个值正好是表中基变量对应的资源向量b对应的分量）那么，第3个基可行解为X3=[18,4,0,0]T。

（8）找到了第3个基可行解，接下来的任务就是判断该基可行解是否为最优解，检验其是否为最优解的标准前面已经详细讲述，这里就不啰唆了。即转回到步骤（4）。

3400

CBXB

b

x1x2x3x4

biaik

40

=401

x3x4

402110

03013

[3]4

00

10

30=103

σj(1)=cj−CB⋅Pj

x3x2

30

5[]31353

100

01

1−3134−31−525

330×=18

5

41010010

00

10×3=30

σj(2)=cj−CB⋅Pj

34

x1x2

184

351−5−1

σj(3)=cj−CB⋅Pj

−1

这时，非基变量的检验数σ3=−1,σ4=−1，均