运筹学--单纯形法求解-动态演示

单纯形法求解的动态演示

单纯形法求解—动态演示在求解LP问题时,有人给出了图解法,但对 多维变量时,却无能为力,于是 美国数学家G· Dantgig(丹捷格)发明了一 B· 种“单纯形法”的代数算法，尤其是方 便于计算机运算。这是运筹学史上最辉 煌的阶段。

单纯形法求解的动态演示

线性规划的例子max z 4 x1 3 x2 2 x1 2 x2 1600 5 x1 2.5 x2 2500 x1 400 x1 , x2 0

单纯形法求解的动态演示

线性规划--标准化

引入变量：s1,s2,s3

max

z 50 x1 100 x2 0 s1 0 s2 0 s3 300 400 s3 250

x1 x2 s1 2 x1 x2 s2 x2

x1 , x2 , s1 , s2 , s3 0

单纯形法求解的动态演示

提取系数，填入表格：max z 50 x1 100 x 2 0s1 0s 2 0s3 x1 x2 max z 50 100 0 0 0 s1 s2 s3 x1 1 1 1 0 0 x 2 300 2 1 0 1 0 s1 400 0 1 0 0 1 s 2 250 s3

1x1+1 x2+1s1+0s2+0s3 =300 2x1+1 x2+0s1+1s2+0s3 =400 0x1+1x2+0s1+0s2+1s3 =250 x1 ≥0, x2≥0, si≥0

s.t.

单纯形法求解的动态演示

初始单纯形表迭代 基变 次数 量 x1 X2 s1 s2 S3 比值

CB

b

bi aij

1

Zj

j cj z j

单纯形法求解的动态演示

初始单纯形表迭代 基变 次数 量 x1 X2 s1 s2 S3 比值

CB

目标系数区

b右 端 系 数

bi aij

基 变 量 区

1

约束条件 系数区Zj检验系数区

j cj z j

单纯形法求解的动态演示

初始单纯形表迭代 基变 次数 量

x1 CB

x2

s1

s2

s3

比值

b

50 100

0

0

0

bi ai 2

1

Zj

j cj z j

单纯形法求解的动态演示

初始单纯形表迭代 次数 基 变 量

x1 CB 50

X2 100

s1 0

s2 0

S3 0

比值

b

bi ai 2

1 20 Zj

1 11

1 00

0 10

0 01

300 400250

0 j cj z j

单纯形法求解的动态演示

初始单纯形表迭代 次数 基 变 量

x1 CB50

x2100

s10

s20

s30

比值

b

bi ai 2

1 21

1 11

1 00

0 10

0 01

300 400250

0Zj

j cj z j

单纯形法求解的动态演示

初始单纯形表迭代 次数 基 变 量

x1 CB50

x2100

s10

s20

s30

比值

b

bi ai 2

S1 S21

0 00Zj

1 20

1 11

1 00

0 10

0 01

300 400250

S3

j cj z j

单纯形法求解的动态演示

初始单纯形表x1迭代 基变 次数 量

X2 s1 s2 S3 00

比值

CB

50 100 0

b

bi ai 2

S1 S21

0 00Zj

1 20

1 11

1 00

0 10

0 01

300 400250

S3

j cj z j

Z=

0

单纯形法求解的动态演示

初始单纯形表x1迭代 基变 次数 量

X2 s1 s2 S3 00

比值

CB

50 100 0

b

bi ai 2

S1 S21

0 00Zj

1 200 0

1 110 0

1 00

0 10

0 010 0

300 400250

S3

0 0 0 0

j cj z j

Z=

0

单纯形法求解的动态演示

初始单纯形表x1迭代 基变 次数 量

X2 s1 s2 S3 b 0 0 1 000

比值

CB

S1 S21

0 00Zj

50 100 0 1 1 1 2 1 0 00

bi ai 2

0 010

300 400250

S3

10

00

j cj z j

50 100 0

0

0

Z=

0

单纯形法求解的动态演示

初始单纯形表x1迭代 基变 次数 量

X2 s1 s2 S3 00

比值

CB

50 100 0

b

bi ai 2300 1 400 1

S1 S21

0 00Zj

1 200

1 11 ①0

1 000 0

0 100 0

0 010 0

300 40025

0Z=0

S3

250 1

j cj z j

50 100

单纯形法求解的动态演示

初始单纯形表x1迭代 基变 次数 量

X2 s1 s2 S3 00

比值

CB

50 100 0

b

bi ai 2300 1 400 1

S1 S22

0 0Zj

1 20

1 11 ①

1 00

0 10

0 01

300 400250

x2 j cj z j

250 1

单纯形法求解的动态演示

初始单纯形表x1迭代 基变 次数 量

X2 s1 s2 S3 00

比值

CB

50 100 0

b

bi ai 2300 1 400 1

S1 S22

0 0100 Zj

1 20

1 11 ①

1 00

0 10

0 01

300 400250

x2

250 1

j cj z j

单纯形法求解的动态演示

初始单纯形表x1迭代 基变 次数 量

X2 s1 s2 S3 00

比值

CB

50 100 0

b

bi ai 2300 1 400 1

S1 S22

0 0100 Zj

1 20

1 11 ①

1 00

0 10

0 01

300 400250

x2

250 1

j cj z j

单纯形法求解的动态演示

初始单纯形表x1迭代 基变 次数 量

X2 s1 s2 S3 00

比值

CB

50 100 0

b

bi ai 2300 1 400 1

S1 S22

0 0100 Zj

1 20

1 11 ①

1 00

0 10

0 01

300 400250

x2

250 1

j cj z j

单纯形法求解的动态演示

初始单纯形表x1迭代 基变 次数 量

X2 s1 s2 S3 00

比值

CB

50 100 0

b

bi ai 2

S1 S22

0 0Zj

1 20

0 01

1 00

0 10

-1 50 -1 1501 250Z=25000

x2 100 j cj z j

单纯形法求解的动态演示

初始单纯形表x1迭代 基变 次数 量

X2 s1 s2 S3 00

比值

CB

50 100 0

b

bi ai 2

S1 S22

0 0Zj

1 200

0 01100

1 000

0 10

-1 50 -1 1501 250Z=25000

x2 100 j cj z j

0 100

单纯形法求解的动态演示

初始单纯形表迭代 基变 次数 量 x1 X2 s1 s2 S3 比值

CB

50 100 0

0

0

b

bi ai 2

S1 S22

0 0Zj

1 200 50

0 011000

1 000 0

0 100

-1 50 -1 1501-100

x2 100 j cj z j

250Z=25000

0 100

本文来源：https://www.bwwdw.com/article/g6cm.html