最优化单纯形法例题讲解.docx

例1 用单纯形法解下列问题：

minx

1

2x?x

2 3

s.t.

x?x

1 2

2x?x

3 4

?10,

2x?x

1 2

4x

3

?8,

x?2x

1 2

4x

3

?4,

x ?0,j?1, ,4.

j

解：将原问题化成标准形：

max?x

1

2x?x

2 3

s.t.

x?x

1 2

2x?x

3 4

?10,

2x?x

1 2

4x

3

?x ?8,

5

x?2x

1 2

4x

3

?x ?4,

6

x ?0,j?1, ,6.

j

5 6x4与添加的松弛变量x，x在约束方程组中其系数列正好构成一个3阶单位阵，它们可以作为初始基变量，初始基可行解为X=（0,0,0,10,8,4）

5 6

列出初始单纯形表，见表1。

表1

c

cj→

基

-1

2

-1

0

0

0

CB

0

b

x1

1

x2

1

x3

-2

x4

1

x5

0

x6

0

0

x4

x5x6

10

8

2

-1

4

0

1

0

0

4

-1

[2]

-4

0

0

1

cj-zj

0

-1

2

-1

0

0

0

由于只有σ20，说明表中基可行解不是最优解，所以确定x2为换入非基变量；以x2

的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。

??min(10,4)?2?4

1 2 2

因此确定2为主元素（表1中以防括号[]括起），意味着将以非基变量x2去置换基变量x6，

采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将x2的系数列(1,-1,2)T变换成x6的系数列(0,0,1)T，变换之后重新计算检验数。变换结果见表2。

表2

cj→

-1

2

-1

0

0

0

CB

基

b

x1

x2

x3

x4

x5

x6

0

x4

8

3/2

0

0

1

0

-1/2

0

x5

10

3/2

0

[2]

0

1

1/2

2

x2

2

-1/2

1

-2

0

0

1/2

cj-zj

4

0

0

3

0

0

-1

5检验数σ3=30，当前基可行解仍然不是最优解。继续“换基”，确定2为主元素，即以非基变量x3置换基变量x。变换结果见表3。

5

表3

cj→

-1

2

-1

0

0

0

CB

基

b

x1

x2

x3

x4

x5

x6

0

x4

8

3/2

0

0

1

0

-1/2

-1

x3

5

3/4

0

1

0

1/2

1/4

2

x2

12

1

1

0

0

1

1

cj-zj

19

-9/4

0

0

0

-3/2

-7/4

此时，3个非基变量的检验数都小于0，σ1=-9/4，σ5=-3/2，σ5=-7/4，表明已求得最优

解：X*

值为-19

?(0,12,5,8,0,0)T。去除添加的松弛变量，原问题的最优解为：X*?(0,12,5,8)T,最小

例2 用大M法求解下列问题：

minx?x

1 2

3x

3

s.t.

x?2x?x

1 2 3

?11,

2x?x

1 2

x

1

4x

3

2x

3

?3,

?1,

x ?0,j?1,

j

解 引进松弛变量x4、剩余变量x5和人工变量x6、x

,3.

，解下列问题：

、

minx?x

1 2

3x

3

0x

4

0x

5

7

M(x

6

x)

7

s.t.

x?2x

1 2

x?x

3 4

?11

2x?x

1 2

x

1

4x

3

2x

3

?x?x ?3

5 6

?x ?1

,77

,7

x ?0,j?1,2,

j

用单纯形法计算如下：

表1

cj→

1

1

-3

0

0

M

M

基

b

x1

x2

x3

x4

x5

x6

x7

x4

11

1

-2

1

1

0

0

0

x6

3

2

1

-4

0

-1

1

0

x7

1

[1]

0

-2

0

0

0

1

cj-zj

4M

1-3M

1-M

-3+6M

0

M

0

0

CB0MM由于σ1σ20，说明表中基可行解不是最优解，所以确定x1为换入非基变量；以

CB

0

MM

??min(11,3,1)?1?1

1 21 1

7因此确定1为主元素（表1中以防括号[]括起），意味着将以非基变量x1去置换基变量x，

7

采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将x1的系数列(1,2,1)T变换成

x7的系数列(0,0,1)T，变换之后重新计算检验数