当前位置：文档库 › 最优化单纯形法例题讲解

最优化单纯形法例题讲解

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

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

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

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

22x 2

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

42)24,110(

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

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

123

1234123123min 2..210,248,244,0,1,,4.j x x x s t x x x x x x x x x x x j -++-+=-+≤-+-≤≥= 123123412351236max 2..210,248,244,

0,1,,6.

j x x x s t x x x x x x x x x x x x x j -+-+-+=-++=-+-+=≥=

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

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

解：T

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

值为-19

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

123

1231231

3min 3..211,

243,21,

0,1,,3.

j x x x s t x x x x x x x x x j +--+≤+-≥-=≥=

解引进松弛变量x 4、、剩余变量x 5和人工变量x 6、x 7，解下列问题：

12345671234

12356

37min 300()..211243

0,1,2,,7

j x x x x x M x x s t x x x x x x x x x x x x x j +-++++-++=+--+=-+=≥=

用单纯形法计算如下：

由于σ1<σ2< 0，说明表中基可行解不是最优解，所以确定x 1为换入非基变量；以x 1的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。

11)11,23,111(

min ===θ

因此确定1为主元素（表1中以防括号[]括起），意味着将以非基变量x 1去置换基变量x 7，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将x 1的系数列(1, 2, 1)T 变换成x 7的系数列(0, 0, 1)T ，变换之后重新计算检验数。变换结果见表2。

由于σ2<σ3< 0，说明表中当前基可行解仍不是最优解，所以确定x 2为换入非基变量；以x 2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。因此确定1为主元素，意味着将以非基变量x 2去置换基变量x 6，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将x 2的系数列(-2, 1, 0)T 变换成x 6的系数列(0, 1, 0)T ，变换之后重新计算检验数。变换结果见表3。

由于只有σ3< 0，表中当前基可行解仍不是最优解，所以确定x 3为换入非基变量；又由于x 3的系数列的正分量只有3，所以确定3为主元素，意味着将以非基变量x 3去置换基变量x 4，对约束方程组的系数增广矩阵实施初等行变换，将x 3的系数列(3, 0, -2)T 变换成x 4的系数列(1, 0, 0)T ，变换之后重新计算检验数。变换结果见表4。

表4

至此，无负的检验数且基变量中不含人工变量（即人工变量在基可行解中取0值），求得

原问题的最优解：9*1=x ，1*

=x ，4*

3=x ，最小目标函数值为-2。

例3 用两阶段法求解下列问题：

1212121

12max 2..2,

1,3,,0.

x x s t x x x x x x x -+≥-≥≤≥

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

12123

124

5125max 2..213

,,0

x x s t x x x x x x x x x x x -+-=--=+=≥

第一阶段用单纯形法求解第一阶段的线性规划问题：

67123

124

127min ..21

,,0

x x s t x x x x x x x x x x x x x ω=++-+=--+=+=≥

求解过程见表1。

表1

因此，第一阶段求得最优解为12345313(,,,)(,,0,0,)222

T x x x x x =，，基变量为x 1、x 2和

x 5，不包含人工变量。

第二阶段以第一阶段的最终单纯形表为基础，除去人工变量x 6、x 7及其系数列，恢复目标价值向量为C =（2, -1, 0, 0, 0）T ，重新计算检验数，继续迭代，见表2。

表2

因此，求得原问题的最优解为12345(,,,)(3,0,1,2,0)T

x x x x x =，，最大目标函

数值为6。

例4 用K —T 条件求下列问题

221212121

12min (,)(1)(2)..2000

f x x x x s t x x x x x x =-+-+-≤-≤-≤-+-=

解该问题的Lagrange 函数是

2212112213212(,,)(1)(2)2

(1)L X x x x x x x x x λμλλλμ=-+---+-+-+-（-）- 由于

μλλ--+-=??2111)1(2x x L

μλλ+-+-=??3122

)2(2x x L

故该问题的K —T 条件是

11122

311221321232(1)02(2)0

(2)0

00,,0

x x x x x x λλμλλμλλλλλλ-+--=??-+-+=??--+=??

?=?≥?? 作为K —T 点，除满足上述条件，自然还应满足可行性条件

???

??≥≥=-+-≤-+0

,0010221

2121x x x x x x 为使求解易于进行，从互补松紧条件入手讨论：

1° 设01≠x ，02≠x ，01=λ

由互补松紧条件知023==λλ，由K —T 条件知

0)2(2,

0)1(221=+-=--μμx x

再由可行性条件0121=-+-x x 得到0,2,121===μx x ，但是显然不满足可行性

0221≤-+x x ，故此解舍弃。

2° 设01≠λ

由互补松紧条件知0221=-+x x ，再加上可行性条件0121=-+-x x 知

,2121==

x x ，从而由互补松紧条件知032==λλ，将已知值代入易得1λ=1，0=μ，易知这时K —T 条件和可行性条件满足，因而T X )2

3,21(*

=为K —T 点。易见

)3,2,1)(,(),,(2121=i x x g x x f i 为凸函数，

且1h 为线性函数，由定理3.1.12知T X )23,21(*

=为全局最优解。（21220(,)02f x x ???=?

???正定，2

1200(,)00i g x x ???=????

半正定）

例5 用0.618法求解问题3

min ()21x f x x x ≥=-+的近似最优解，已知()f x 的单峰区间为]3,0[，

要求最后区间精度5.0=ε。

解 3,0==b a ， 146.1)(382.01=-+=a b a x ，2131.0)(11==x f f ； 1854.1)(618.02=-+=a b a x ，6648.3)(22==x f f ；因为 21f f <，所以向左搜索，则

854.1,02===x b a ， 2131.0,146.11212====f f x x ；

708.0)(382.01=-+=a b a x ，0611.0)(11-==x f f ；因为 21f f <，所以向左搜索，则

146.1,02===x b a ， 0611.0,7086

.01212-====f f x x ； 438.0)(382.01=-+=a b a x ，208.0)(11==x f f ；因为 21f f >，所以向右搜索，则

146.1,438.02===x b a ，0611.0,7086

.02121-====f f x x ； 876.0)(618.02=-+=a b a x ，0798.0)(22-==x f f ；因为 21f f >，所以向右搜索，则 146.1,708.02===x b a ，0798.0,876.02121-====f f x x ；

9787.0)(618.02=-+=a b a x ，0199.0)(22-==x f f ；因为ε=<=-5.0438.0a b ，所以算法停止，得到

927.02

146

.1708.02*=+=+=

b a x 。例 6 用FR 共轭梯度法求解问题()2212min 2f x x x =+，要求选取初始点05,5x ??= ???

610ε-=。

解 ???

??=?2142)(x x x f ，???? ??=20100g ，???? ??--=-=201000g d ， 2

200)205(2)105(205105)(ααααα-+-=???

? ??--=+f d x f ，

令05001800)(00=-=+αααd x f d d ，则1850=α，于是??

????

??-=+=959200001d x x α；

则?

????

? ??-=?=920940)(11x f g ，95201=g ，8140

0110==g g g g T T β，??????

??-=+-=81100814000011d g d β， 2

211)9

201(8150)9201(81400)(ααα+-+-=+d x f ，令

0)(11=+d x f d d αα，则209

1=α，于是???

? ??=+=001112d x x α；则???? ??=?=00)(22x f g ，ε<=02g ，故???

? ??==002*x x 为所求。例7 用外罚函数法求解：

解即

于是

令

)()01.1min 222

21≥-+-=x t s x x x f ()()222

122,(1)min 0,1P x M x x M x =-++-????

()()22122222

222(1),

10,(1)1,10x x x P x M x x M x x ?-+-≥?=?-++--

P x x ?=-?()2222222,1221,1x x P x M x x x ≥??=?

1=??=??x P x P

得：最优值：

当时，，

例8 用内罚函数法求解：

312121

min

(1)12

..10

x x s t x x ++-≥≥ 解定义障碍函数 )1

11()1(121),(2

1231x x r x x r x P k k +-+++=

，用解析法求),(min k r x P ，令

0)1()1(41),(21211=--+=??x r x x r x P k

k ，

01),(2

22=-=??x r

x r x P k k ，解得：T k k T r r r x x x k ),21(),(21+==。当0→k r 时，T r x x k )0,1(=→，

故T x )0,1(=是原问题的最优解。例9用内罚函数法求解：

解定义障碍函数 x r x r x P k k ln )1(),(2

-+=，

用解析法求),(min k r x P ，令

0)1(2),(=-+=x

x dx r x dP k k ，解得：2

211k

r r x k ++-=

。

()()1211

x M x M M ==

+()22

1,111M M P x M M M M M -????=+= ? ?+++????M →+∞()()121,1x M x M →→()()()

**1,,11x M x P x M f x ??→=→= ???()()0.1min 2

≥+=x t s x x f

当0

→

k r 时，0

→x

，故0

x是原问题的最优解。

单纯形法步骤例题详解

单纯形法演算 j c 2 1 B C X B b 1x 2x 3x 4x 5x 0 3x 15 0 5 1 0 0 无穷 0 4x 24 6 2 0 1 0 4 0 5x 5 1 1 0 0 1 5 j j z c -（检验数） 2 1 首先列出表格，先确定正检验数最大值所在列为主列，然后用b 除以主列上对应的同行数字。除出来所得值最小的那一行为主行，根据主行和主列可以确定主元（交点）。接着把主元化为1并把X4换成X1. ??? ??? ?≥=++=++=+++++=0,,524261550002max 5152 14213 25 4321x x x x x x x x x x x x x x x z ??????? ≥≤+≤+≤+=0 ,5 24261552max 21212122 1x x x x x x x x x z

j c 2 1 B C X B b 1x 2x 3x 4x 5x 0 3x 15 0 5 1 0 0 2 1x 4 1 2/6 0 1/6 0 0 5x 5 1 1 0 0 1 j j z c - 2 1 这时进行初等行列变换，把主列换单位向量，主元为1。也就是X5所在行减去X1所在行。并且重新计算检验数。 j c 2 1 B C X B b 1x 2x 3x 4x 5x 0 3x 15 0 5 1 0 0 2 1x 4 1 2/6 0 1/6 0 0 5x 5-4 1-1=0 1-2/6 =4/6 0-1/6=-1/6 1 j j z c - 2-2*1-0*0-0*1=0 1-0*5-2*2/6-0*4/6=1/3 0-0*0-2*1/6-0*-1/6=-1/3 再次确定主元。为4/6。然后把X5换成X2。并且把主元化成1。

单纯形法典型例题

科学出版社《运筹学》教材第一章引言第二章线性规划，姜林第三章对偶规划，姜林第四章运输问题，姜林第五章整数规划，姜林第六章非线性规划，姜林第七章动态规划，姜林第八章多目标规划，姜林第九章图与网络分析，熊贵武第十章排队论，熊贵武第十一章库存论，王勇第十二章完全信息博弈，王勇第十三章不完全信息博弈，王勇第十四章决策论与影响图第十五章运筹学模型的计算机求解成年人每天需要从食物中摄取的营养以及四种食品所含营养和价格见下表。问如何选择食品才能在满足营养的前提下使购买食品的费用最小？食品名称热量(kcal) 蛋白质(g) 钙（mg）价格（元）猪肉1000 50 400 14 鸡蛋800 60 200 6

大米900 20 300 3 白菜200 10 500 2 营养需求量 2000 55 800 解：设需猪肉、鸡蛋、大米和白菜各需 x1,x2,x3,x4斤。则热量的需求量为： 2000 20090080010004 3 2 1 x x x x 蛋白质某工厂要做100套钢架，每套有长 3.5米、2.8米和2根2.4米的圆钢组成（如右图）已知原料长12.3米，问应如何下料使需用的原材料最省。解：假设从每根 12.3米的原材料上截取 3.5米、2.8米和2根2.4 米，则每根原材料需浪费 1.2米，做100套需浪费材料 120米，现采用套裁的方法。方案一二三四五六3.5 2.8 2.4 0 0 5 0 4 0 1 2 1 1 3 0 2 0 2 2 1 1 合计剩余 12 0.3 11.2 1.1 11.5 0.8 11.9 0.4 11.8 0.5 12.2 0.1 现在假设每种方案各下料x i （i=1、2、3、4、5、6），则可列出方程： minZ=0.3x 1+1.1x 2+0.8x 3+0.4x 4+0.5x 5+0.1x 6 约束条件： x 3+x 4+2x 5+2x 6=100 4x 2+2x 3+3x 4+x 6=100 5x 1+x 3+2x 5+x 6=200 ,,,800 50030020040055 102060503000 2009008001000. .23614min 4 3214 3 2 1 4 32 14 32 14321x x x x x x x x x x x x x x x x t s x x x x z

(完整word版)单纯形法的解题步骤

三、单纯形法的解题步骤第一步：作单纯形表. ）（1）把原线性规划问题化为标准形式；）（2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵；）（3）目标函数非基化；）（4）作初始单纯形表. 第二步：最优解的判定. (1) 若所有检验数都是非正数，即，则此时线性规划问题已取得最优解. (2) 若存在某个检验数是正数，即，而所对应的列向量无正分量，则线性规划问题无最优解. 如果以上两条都不满足，则进行下一步. 第三步：换基迭代. ，并确定所在列的非基变量为进基变量. （1）找到最大正检验数，设为（2）对最大正检验数所在列实施最小比值法，确定出主元，并把主元加上小括号. 主元是最大正检验数所在列，用常数项与进基变量所对应的列向量中正分量的比值最小者；替换出基变量，从而得到新的基变量.也就是主元所在（3）换基：用进基变量（4）利用矩阵的行初等变换，将主元变为1，其所在列其他元素都变为零，从此得到新的单纯形表；（5）回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得到解决为止. 例3 求.

解（1）化标准型：令，引进松弛变量，其标准型为求（2）作单纯形表：在约束方程组系数矩阵中的系数构成单位矩阵，故取为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）.表 6.8

（3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为目标函数取得最优值. 原线性规划问题的最优解为：.目标函数的最优值为14，即. 例4 用单纯形方法解线性规划问题. 求. 解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（1、2行，3、4列构成），取为基变量，而目标函数没有非基化.从约束方程找出，, 代入目标函数 , 经整理后，目标函数非基化了. 作单纯形表，并进行换基迭代（见表6.9）. 最大检验数，由最小比值法知：为主元，对主元所在列施以行初等变出基，非基变量进基. 换，基变量

单纯形法求最优解问题及一些知识点整理

单纯形法求最优解问题题目（老师布置的那道作业题）：2153m ax x x f +=，其中 ??? ??? ?=≥=++=+=+5,4,3,2,1,0182312245214 231j x x x x x x x x j ，求2153m ax x x f +=的最大值。这张表是根据题目画的，Cj （行向量）为5432100053m ax x x x x x f ++++=中各个变量的系数，Ci （列向量）为与X B （列向量）相对应的各项的系数，X B 称为基变量（3列，由题目中的方程个数决定），起初的基变量由构造的变量x3、x4、x5组成，b 为对应三个方程等式右边的常数，z j 为Ci 各列与xj 各列乘积的和，如z1=0*1+0*0+0*3=0。i θ为判别将哪个基变量换出的依据，根据c j -z j 为正，要先将x2换入XB 中，关键是判断x3、x4、x5哪个跟x2换，这就要根据各列各列除以2x B i X =θ，与所得的最小的i θ对应的XB 换，如上表可知x2跟x4换，换完之后注意原来x4所对应的列向量为[0 1 0]T ,故要将x2所对应的列向量变换为为[0 1 0]T ，注意b 也要跟着变化，于是得下表.

由上表知c 1-z 1=3>0，故仍需将x1换入XB 中，用各列各列除以2x B i X =θ，与所得的最小的i θ对应的XB 换，结合i θ可知，x1跟x5换，于是得下表。由上表可知c j -z j 均非正，故5432100053m ax x x x x x f ++++=取最大值时，????? ?? ?????????=00662x ，对应的最大值36max =f . 系统工程导论知识点整理：系统是由相互作用和相互依赖的若干组成部分(要素)结合的具有特定功能的有机整体。系统的特征：整体性、相关性、目的性、环境适应性。系统的功能是指系统与外部环境相互作用所反映的能力。结构是功能的内在根据，功能是结构的外在表现。系统功能的特性：易变性、相关性。系统工程就是用科学的方法规划和组织人力、物力、财力，通过最优途径的选择，使人们的工作在一定期限内收到最合理、最经济、最有效的效果。科学的方法：从整体观念出发，通盘筹划，合理安排整体中的每一个局部，以求得整体的最优规划、最优管理和最优控制，使每个局部都服从一个整体目标，力求避免资源的损失和浪费。

单纯形法例题(20210121173229)

单纯形法例题 1、例1、目标函数max z=2 * +3 禹+ 2x2 W 8' 4xi W 16 4x2 W 12 k Ki,财鼻0』解：首先要将约束条件化为标准形：由此可以看出我们需要加上三个松弛变量, ；汁Hi吃：弋"審得到的标准形式为： max z=2~ +3-+ 0 勺+g +O 5 'xt + 2xj + x] = 8 1 4?i X4 =16 4x；+ 巧=12 11 巾弓^3j 乂4, ^5 $ ? 2 3 0 0 0 C R b *4 0 8 1 2 1 0 0 4 0 16 4 0 0 1 0 - 0 ◎12 0[E(|00 1 3 k - z) 2 3 0 0 0 引」一弋木日lk(i才I) 熙=') (也就是如果与主元素同行，则用现在的值除以主元素即可得到即将要填入的值, 否则，就用现在的值减去与主元素构成矩形的边角上的值的乘积再除以主元素之后的值。例如：上面的第一行所对应的b值为8-(12*2)/4=2 ,故填入值应该为2。而「则是由我们根据非基变量的检验数的大小，挑选出最大的那个，作为换入变量，然后用b的值除以该换入变量所在的列的所有值，得到约束条件:

由于在检验数中仍然存在大于等于的数，而且, 的坐标中有正分量存在，所以需要继续进行迭代运算。通过观察可以看出主元素为1,换入变量为|勒，换出由于检验数中存在正数，且P5和P3中有正分量存在，所以需要继续迭代（换入变此时可以发现检验数中没有大于的数，表明已经得到了最优解，所以最优解是: (4,2,0,0,4 )，故目标函数值z=2*4+2*3=14 2、合理利用线材问题，现在要做100套钢架，每套用长为，，和的钢各一根,

单纯形法例题讲解

例1 max z=2x1+3x2 （标准形式即所有的变量均为负、所有约束条件为等式、所有的右端项系数非负） a=(2,3) b1=(80,160,120) A2=NULL b2=NULL A3=NULL b3=NULL n.iter=n+2*m maxi=TRUE ● simplex(a=a,A1=A1,b1=b1,maxi=TRUE)： m1=3,m2=0,m3=0 m=3,n=2 a.o=a=(2,3) if(maxi) a=-a(-2,-3) if(m2+m3==0) a=(-2,-3,0,0,0) b=(80,160,120) init=(0,0,0,80,160,120) basic=(3,4,5) eps=1e -10 out1<-simplex1(a=a,A=A,b=b,init=init,basic=basic,eps=eps) ? simplex1(a=a,A=A,b=b,init=init,basic=basic,eps=eps): N=5,M=3 nonbasic=(1,2) if(stage==2) obfun=(-2,-3) it=1 ◆ while(!all(obfun > -eps) && (it <= n.iter))循环 pcol=3 if(stage==2) neg=(1,3) x1+2x2<=80 4x1<=160 4x2<=120 x1，x2>=0 A1= 1 2 4 0 0 4 A= 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 tableau= 80 -1 -2 160 -4 0 120 0 -4 tableau= 80 -1 -2 160 -4 0 120 0 -4 0 -2 -3 转化为标准形式 x1+2x2+x3=80 4x1+x4=160 4x2+x5=120 x1,x2,x3,x4,x5>=0

单纯形法例题

单纯形法例题 1、例1、目标函数 max z=2+3 约束条件：解：首先要将约束条件化为标准形：由此可以看出我们需要加上三个松弛变量， .得到的标准形式为： max z=2+3+ 0+0+0 然后要将其初始的单纯形表画出来： 23000 b 08121004 01640010- 01200013 23000 由初始单纯形表可以看出，为换入变量，而为换出变量；然后根据：= (也就是如果与主元素同行，则用现在的值除以主元素即可得到即将要填入的值，否则，就用现在的值减去与主元素构成矩形的边角上的值的乘积再除以主元素之后的值。例如：上面的第一行所对应的b值为8-(12*2)/4=2,故填入值应该为2。而则是由我们根据非基变量的检验数的大小，挑选出最大的那个，作为换入变量，然后用b的值除以该换入变量所在的列的所有值，得到列的值。 23000 b 02010-1/22 016400104 3301001/4- 2000-3/4由于在检验数中仍然存在大于等于0的数，而且P1，P5的坐标中有正分量存在，所以需要继续进行迭代运算。通过观察可以看出主元素为1，换入变量为，换出变量为，故得到的单纯形表如下：

23000 b 221010-1/2- 0800-414 3301001/412 00-201/4由于检验数中存在正数，且P5和P3中有正分量存在，所以需要继续迭代(换入变 23000 b 241001/40 0400-21/21 32011/2-1/80 00-3/2-1/80 （4,2,0,0,4），故目标函数值z=2*4+2*3=14 2、合理利用线材问题，现在要做100套钢架，每套用长为，，和的钢各一根，已知原料长，问应如何下料，使用的原材料最省；解：首先我们必须要清楚该问题的需要设立的变量是什么。我们分析一下问题，做100套钢架，需要长的钢100根，的钢100根，的钢100根。而一份原料长度是，长度/m 下料根数截取方案 12345 112 212 3132所用长度剩余长度0 方案，使得剩余的总长度最少。由此，我们可以将目标函数和约束条件表述出来：目标函数：min z=+++ 约束条件首先可以写出线性方程组的矩阵形式：发现不存在单位矩阵，所以要采用人造基的方式，也就是要添加人工变量：，那么线性方程组可以

单纯形法的解题步骤

三、单纯形法的解题步骤第一步：作单纯形表. （1）（1）把原线性规划问题化为标准形式；（2）（2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵；（3）（3）目标函数非基化；（4）（4）作初始单纯形表. 第二步：最优解的判定. (1) 若所有检验数都是非正数，即，则此时线性规划问题已取得最优解. (2) 若存在某个检验数是正数，即，而所对应的列向量无正分量，则线性规划问题无最优解. 如果以上两条都不满足，则进行下一步. 第三步：换基迭代. （1）找到最大正检验数，设为，并确定

（2）作单纯形表：在约束方程组系数矩阵中的系数构成单位矩阵，故取为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）. 表 6.8 x1 x2x3x4x5常数 x 3 x 4 x 51 0 1 0 0 1 2 0 1 0 0 （1）0 0 1 5 10 4 S′ 1 3 0 0 0 0 x 3 x 4 x2 1 0 1 0 0 （1）0 0 1 -2 0 1 0 0 1 5 2 4 S′ 1 0 0 0 -3 -12 x 3 x 1 x 20 0 1 -1 2 1 0 0 1 -2 0 1 0 0 1 3 2 4 S′0 0 0 -1 -1 -14