一个例子搞懂单纯形法大M法和两阶段法

文章目录

1. 题目2. 添加松弛变量3. 大M法4. 两阶段法

1. 题目

目标函数：

min

⁡

z

=

4

x

1

+

x

2

\min z = 4x_1 + x_2

minz=4x1​+x2​

约束条件：

s.t.

{

3

x

1

+

x

2

=

3

4

x

1

+

3

x

2

≥

6

x

1

+

2

x

2

≤

4

x

1

,

x

2

≥

0

\text{s.t.} \begin{cases} 3x_1 + x_2 = 3 \\ 4x_1 + 3x_2 \geq 6 \\ x_1 + 2x_2 \leq 4 \\ x_1, x_2 \geq 0 \end{cases}

s.t.⎩⎪⎪⎪⎨⎪⎪⎪⎧​3x1​+x2​=34x1​+3x2​≥6x1​+2x2​≤4x1​,x2​≥0​

2. 添加松弛变量

min

⁡

z

=

4

x

1

+

x

2

+

0

x

3

+

0

x

4

\min z = 4x_1 + x_2 + 0x_3 + 0x_4

minz=4x1​+x2​+0x3​+0x4​

s.t.

{

3

x

1

+

x

2

=

3

4

x

1

+

3

x

2

−

x

3

=

6

x

1

+

2

x

2

+

x

4

=

4

x

i

≥

0

,

i

=

1

,

2

,

…

,

4

\text{s.t.} \begin{cases} 3x_1 + x_2 = 3 \\ 4x_1 + 3x_2 - x_3 = 6 \\ x_1 + 2x_2 + x_4 = 4 \\ x_i \geq 0, i = 1,2,\dots, 4 \end{cases}

s.t.⎩⎪⎪⎪⎨⎪⎪⎪⎧​3x1​+x2​=34x1​+3x2​−x3​=6x1​+2x2​+x4​=4xi​≥0,i=1,2,…,4​

3. 大M法

max

⁡

−

z

=

−

4

x

1

−

x

2

+

0

x

3

+

0

x

4

−

M

x

5

−

M

x

6

\max -z = -4x_1 - x_2 + 0x_3 + 0x_4 - Mx_5 - Mx_6

max−z=−4x1​−x2​+0x3​+0x4​−Mx5​−Mx6​

s.t.

{

3

x

1

+

x

2

+

x

5

=

3

4

x

1

+

3

x

2

−

x

3

+

x

6

=

6

x

1

+

2

x

2

+

x

4

=

4

x

i

≥

0

,

i

=

1

,

2

,

…

,

6

\text{s.t.} \begin{cases} 3x_1 + x_2 + x_5 = 3 \\ 4x_1 + 3x_2 - x_3 + x_6 = 6 \\ x_1 + 2x_2 + x_4 = 4 \\ x_i \geq 0, i = 1,2,\dots, 6 \end{cases}

s.t.⎩⎪⎪⎪⎨⎪⎪⎪⎧​3x1​+x2​+x5​=34x1​+3x2​−x3​+x6​=6x1​+2x2​+x4​=4xi​≥0,i=1,2,…,6​

单纯形表

.

C

C

C.-4-100-M-M

C

B

C_B

CB​基

b

b

b

x

1

↓

x_1 \downarrow

x1​↓

x

2

x_2

x2​

x

3

x_3

x3​

x

4

x_4

x4​

x

5

x_5

x5​

x

6

x_6

x6​-M

←

x

5

\leftarrow x_5

←x5​3[3]10010-M

x

6

x_6

x6​643-10010

x

4

x_4

x4​4120100.

σ

\sigma

σ.7M-44M-1-M000

入基变量

x

1

x_1

x1​，出基变量

x

5

x_5

x5​；

.

C

C

C.-4-100-M-M

C

B

C_B

CB​基

b

b

b

x

1

x_1

x1​

x

2

↓

x_2 \downarrow

x2​↓

x

3

x_3

x3​

x

4

x_4

x4​

x

5

x_5

x5​

x

6

x_6

x6​-4

x

1

x_1

x1​11

1

3

\frac{1}{3}

31​00

1

3

\frac{1}{3}

31​0-M

←

x

6

\leftarrow x_6

←x6​20[

5

3

\frac{5}{3}

35​]-10-

4

3

\frac{4}{3}

34​10

x

4

x_4

x4​30

5

3

\frac{5}{3}

35​01-

1

3

\frac{1}{3}

31​0.

σ

\sigma

σ.0

5

3

\frac{5}{3}

35​M+

1

3

\frac{1}{3}

31​-M0-

7

3

\frac{7}{3}

37​M+

4

3

\frac{4}{3}

34​0

入基变量

x

2

x_2

x2​，出基变量

x

6

x_6

x6​；

.

C

C

C.-4-100-M-M

C

B

C_B

CB​基

b

b

b

x

1

x_1

x1​

x

2

x_2

x2​

x

3

↓

x_3 \downarrow

x3​↓

x

4

x_4

x4​

x

5

x_5

x5​

x

6

x_6

x6​-4

x

1

x_1

x1​

3

5

\frac{3}{5}

53​10

1

5

\frac{1}{5}

51​0

1

15

\frac{1}{15}

151​-

1

5

\frac{1}{5}

51​-1

x

2

x_2

x2​

6

5

\frac{6}{5}

56​01

−

3

5

-\frac{3}{5}

−53​0

−

4

5

-\frac{4}{5}

−54​

3

5

\frac{3}{5}

53​0

←

x

4

\leftarrow x_4

←x4​100[1]11-1.

σ

\sigma

σ.00

1

5

\frac{1}{5}

51​0-M-

8

15

\frac{8}{15}

158​-M-

1

5

\frac{1}{5}

51​

入基变量

x

3

x_3

x3​，出基变量

x

4

x_4

x4​；

.

C

C

C.-4-100-M-M

C

B

C_B

CB​基

b

b

b

x

1

x_1

x1​

x

2

x_2

x2​

x

3

x_3

x3​

x

4

x_4

x4​

x

5

x_5

x5​

x

6

x_6

x6​-4

x

1

x_1

x1​

2

5

\frac{2}{5}

52​100-

1

5

\frac{1}{5}

51​-

2

15

\frac{2}{15}

152​0-1

x

2

x_2

x2​

9

5

\frac{9}{5}

59​010

3

5

\frac{3}{5}

53​

−

1

5

-\frac{1}{5}

−51​00

x

3

x_3

x3​100111-1.

σ

\sigma

σ.000

−

1

5

-\frac{1}{5}

−51​-M-

11

15

\frac{11}{15}

1511​-M

所有的

σ

j

≤

0

\sigma_j \leq 0

σj​≤0，且所有的人工变量都是非基变量。 得到最优解：

x

∗

=

(

2

5

,

9

5

,

1

,

0

)

T

，

x^* = (\frac{2}{5}, \frac{9}{5}, 1, 0)^T，

x∗=(52​,59​,1,0)T，

z

∗

=

4

x

1

+

x

2

=

4

∗

2

5

+

9

5

=

17

5

.

z* = 4x_1 + x_2 = 4*\frac{2}{5} + \frac{9}{5} = \frac{17}{5}.

z∗=4x1​+x2​=4∗52​+59​=517​.

4. 两阶段法

第一阶段：

min

⁡

w

=

0

x

1

+

0

x

2

+

0

x

3

+

0

x

4

+

x

5

+

x

6

\min w = 0x_1 + 0x_2 + 0x_3 + 0x_4 + x_5 + x_6

minw=0x1​+0x2​+0x3​+0x4​+x5​+x6​

⇔

\Leftrightarrow

⇔

max

⁡

−

w

=

0

x

1

+

0

x

2

+

0

x

3

+

0

x

4

−

x

5

−

x

6

\max -w = 0x_1 + 0x_2 + 0x_3 + 0x_4 - x_5 - x_6

max−w=0x1​+0x2​+0x3​+0x4​−x5​−x6​

s.t.

{

3

x

1

+

x

2

+

x

5

=

3

4

x

1

+

3

x

2

−

x

3

+

x

6

=

6

x

1

+

2

x

2

+

x

4

=

4

x

i

≥

0

,

i

=

1

,

2

,

…

,

6

\text{s.t.} \begin{cases} 3x_1 + x_2 + x_5 = 3 \\ 4x_1 + 3x_2 - x_3 + x_6 = 6 \\ x_1 + 2x_2 + x_4 = 4 \\ x_i \geq 0, i = 1,2,\dots, 6 \end{cases}

s.t.⎩⎪⎪⎪⎨⎪⎪⎪⎧​3x1​+x2​+x5​=34x1​+3x2​−x3​+x6​=6x1​+2x2​+x4​=4xi​≥0,i=1,2,…,6​

单纯形表

.

C

C

C.0000-1-1

C

B

C_B

CB​基

b

b

b

x

1

↓

x_1 \downarrow

x1​↓

x

2

x_2

x2​

x

3

x_3

x3​

x

4

x_4

x4​

x

5

x_5

x5​

x

6

x_6

x6​-1

←

x

5

\leftarrow x_5

←x5​3[3]10010-1

x

6

x_6

x6​643-10010

x

4

x_4

x4​4120100.

σ

\sigma

σ.74-1000

入基变量

x

1

x_1

x1​，出基变量

x

5

x_5

x5​；

.

C

C

C.0000-1-1

C

B

C_B

CB​基

b

b

b

x

1

x_1

x1​

x

2

↓

x_2 \downarrow

x2​↓

x

3

x_3

x3​

x

4

x_4

x4​

x

5

x_5

x5​

x

6

x_6

x6​0

x

1

x_1

x1​11

1

3

\frac{1}{3}

31​00

1

3

\frac{1}{3}

31​0-1

←

x

6

\leftarrow x_6

←x6​20[

5

3

\frac{5}{3}

35​]-10-

4

3

\frac{4}{3}

34​10

x

4

x_4

x4​30

5

3

\frac{5}{3}

35​01-

1

3

\frac{1}{3}

31​0.

σ

\sigma

σ.0

5

3

\frac{5}{3}

35​-10-

7

3

\frac{7}{3}

37​0

入基变量

x

2

x_2

x2​，出基变量

x

6

x_6

x6​；

.

C

C

C.0000-1-1

C

B

C_B

CB​基

b

b

b

x

1

x_1

x1​

x

2

x_2

x2​

x

3

x_3

x3​

x

4

x_4

x4​

x

5

x_5

x5​

x

6

x_6

x6​0

x

1

x_1

x1​

3

5

\frac{3}{5}

53​10

1

5

\frac{1}{5}

51​0

1

15

\frac{1}{15}

151​-

1

5

\frac{1}{5}

51​0

x

2

x_2

x2​

6

5

\frac{6}{5}

56​01

−

3

5

-\frac{3}{5}

−53​0

−

4

5

-\frac{4}{5}

−54​

3

5

\frac{3}{5}

53​0

x

4

x_4

x4​100111-1.

σ

\sigma

σ.000000

第一阶段结束。

第二阶段

max

⁡

−

z

=

−

4

x

1

−

x

2

+

0

x

3

+

0

x

4

\max -z = -4x_1 - x_2 + 0x_3 + 0x_4

max−z=−4x1​−x2​+0x3​+0x4​

.

C

C

C.-4-100

C

B

C_B

CB​基

b

b

b

x

1

x_1

x1​

x

2

x_2

x2​

x

3

↓

x_3 \downarrow

x3​↓

x

4

x_4

x4​-4

x

1

x_1

x1​

3

5

\frac{3}{5}

53​10

1

5

\frac{1}{5}

51​0-1

x

2

x_2

x2​

6

5

\frac{6}{5}

56​01

−

3

5

-\frac{3}{5}

−53​00

←

x

4

\leftarrow x_4

←x4​100[1]1.

σ

\sigma

σ.00

1

5

\frac{1}{5}

51​0

入基变量

x

3

x_3

x3​，出基变量

x

4

x_4

x4​；

.

C

C

C.-4-100

C

B

C_B

CB​基

b

b

b

x

1

x_1

x1​

x

2

x_2

x2​

x

3

x_3

x3​

x

4

x_4

x4​-4

x

1

x_1

x1​

2

5

\frac{2}{5}

52​100-

1

5

\frac{1}{5}

51​-1

x

2

x_2

x2​

9

5

\frac{9}{5}

59​010

3

5

\frac{3}{5}

53​0

x

3

x_3

x3​10011.

σ

\sigma

σ.000

−

1

5

-\frac{1}{5}

−51​

第二阶段结束。

最优解

x

∗

=

(

2

5

,

9

5

,

1

,

0

)

T

，

x^* = (\frac{2}{5}, \frac{9}{5}, 1, 0)^T，

x∗=(52​,59​,1,0)T，

z

∗

=

4

x

1

+

x

2

=

4

∗

2

5

+

9

5

=

17

5

.

z^* = 4x_1 + x_2 = 4*\frac{2}{5} + \frac{9}{5} = \frac{17}{5}.

z∗=4x1​+x2​=4∗52​+59​=517​.