当前位置：文档之家 › 单纯形法之单纯形表

单纯形法之单纯形表

  • 格式：ppt
  • 大小：133.00 KB
  • 文档页数：3

下载文档原格式

  / 3

合集下载

单纯形法新版

单纯形法新版

1 2
2 1
1 0
10，A 中的2阶可逆子阵有
1
B 1
0
10，其相应的基向量为P3
,
P 4
,
基变量为x
3
,
x
，X
4
B1
x 3 ; x 4
1
B 2
2
2 1
,
其相应的基向量为P 1
,
P 2
,
基变量为x
1
,
x
2
,
X
B2
x 1 。 x 2
问题：本例旳A中一共有几种基？ —— 6个。
一般地，m×n 阶矩阵A中基旳个数最多有多少个？ — —C m 个。 n
p 1
7
(0 0
0) 4
7;
3
360 90
3
4
[ ] 中表达进基列与出基行旳交叉元，下一张表将实 施以它为主元旳初等行变换（称高斯消去）。措施是： 先将主元消成1，再用此1将其所在列旳其他元消成0。
C X B b1
B
B
0
x 3
360
0
x 4
200
0
x 5
300
0
x 3
240
0
x 4
50
（1）先将模型化为原则型
Maxz 7 x1 12x2
9x 1 4x 2 x 3
5x 2 10 x
2
x 4
200
x 300 5
x
1, x
2, x , x , x
3
4
5
0
(2) 拟定初始基可行解、检验
1
B 0
1
,
B
b1

第四节 单纯形法的计算步骤

第四节 单纯形法的计算步骤

上表中由于所有σ 上表中由于所有 j>0 ，表明已求得最优解 x1=4， x2=2， x3=0， x4=0， x5=0， x6=4， ， ， ， ， ， ， Z=14。 。 当确定x 为换入变量计算θ值时 值时， ◆当确定 6为换入变量计算 值时，有两个相 同的最小值： 同的最小值：2/0.5=4，8/2=4。任选其中一 ， 。 个作为换出变量时， 个作为换出变量时，则下面表中另一基变 量的值将等于0，这种现象称为退化 退化。 量的值将等于 ，这种现象称为退化。含有 一个或多个基变量为0的基可行解称为 的基可行解称为退化 一个或多个基变量为 的基可行解称为退化 的基可行解。 的基可行解。
18
迭代
xB
次数
cB
x1
x2
x3
x4
x5 bi
θi
50
x1
100
0
0
0
50 0 100
1 0 0
0
0 0 1
0
1 -2 0
- 50
0 1 0
0
-1 1 1
- 50
50 50 250 -27500
2
x4 x2
σj
2010年8月
管理工程学院
18
《运筹学》 运筹学》
19
所有的检验数 σ j ≤ 0, 此基本可行解： 此基本可行解：
2010年8月
管理工程学院
5
《运筹学》 运筹学》
6
c1 … cl b b1´
⋮
c j→ cB c1
⋮
… cm … xm …0 …⋮ 0 …1 …
⋮
…cj …xj …a1j´ …⋮ a2j´ …⋮ amj´
… ck … cn … xk …xn …0 …⋮ 1 …0

运筹学单纯形法的计算步骤

运筹学单纯形法的计算步骤

b2
0… 0
a2,m+1
…
a2n
2
…
…
…
…
cm xm
bm
0… 1
am,m+1
…
amn
m
-z -z 值 0 … 0
m+1
…
n
XB 列——基变量， CB 列——基变量的价值系数(目标函数系数) cj 行——价值系数，b 列——方程组右侧常数 列——确定换入变量时的比率计算值
下面一行——检验数， 中间主要部分——约束方程系数
(4).根据max(j > 0) =k，拟定xk为换入变量，按 规则计算 =min{bi/aik\aik>0}
可拟定第l行旳基变量为换出变量。转入下一步。
(5).以 alk 为主元素进行迭代(即用高斯消去法或称为旋转变 换)，把 xk 所对应的列向量变换为(0，0，…，1，…，0)T，将
XB 列中的第 l 个基变量换为 xk，得到新的单纯形表，返回(2)。
b
x1
x2
x3
x4
x5
2 x1 2 0 x4 8 3 x2 3
1
0
1
0 -1/2 -
0 0 -4 1 (2 ) 4
0 1 0 0 1/4 12
-z
-13
0
0 -2
0 1/4
X(2)=(2，3，0，8，0)T， z2 =13
cj
2 30 0 0
CB XB
b
x1
x2
x3
x4
x5
2 x1 4 0 x5 4 3 x2 2
量，给出第一阶段的数学模型为：
min = x6+x7
x1-2x2+x3+x4

单纯形表

单纯形表

xm非基1.变..量. XxNn
a1m1 ...a1n a 2 m 1N...a 2 n ......非基阵
a mm1 ...a mn cm1 N cn
b
b1
b2


bm 0

单纯形表
单纯形表结构
c j
C c12 c21 0
已知 C X
B
B
b
x1
x2

c1 x1 b '1
18
表格单纯形法求解步骤
第一步：将LP化为标准型，并加以整理。
引入适当的松驰变量、剩余变量和人工变量 ，使约束条件化为等式，并且约束方程组的系数 阵中有一个单位阵。
确定初始可行基，写出初始基本可行解
19
第二步：最优性检验
计算检验数，检查： 所有检验数是否≤ 0？
是——结束，写出最优解和目标函数最优值； 还有正检验数——检查相应系数列≤ 0？
是——结束，该LP无“有限最优解”！ 不属于上述两种情况，转入下一步—基变换。
确定是停止迭代还是转入基变换？
20
第三步：基变换
选择（最大）正检验数对应的系数列 为主元列，主元列对应的非基变量为换 入变量；
最小比值对应的行为主元行，主元行 对应的基变量为换出变量。
确定进基变量和出基变量。
21
第四步 换基迭代（旋转运算、枢运算)
12 18
x1, x2 0
补充作业：请用单纯形表求解
minZ = x1-2x2+3x3+2x4
3x1-3x2-3x3+6x4=1
-x1+ x2+
x4 =1
xj>=0
min 单纯形表结构 i

单纯形法表的解题步骤

单纯形法表的解题步骤

单纯形法表的解题步骤单纯形法表结构如下：j c →对应变量的价值系数i θB Cb Xb1x 2x 3x " j x基变量的价值系数基变量 资源列θ规则求的值j σ检验数①一般形式若线性规划问题标准形式如下：123451231425max 23000284164120,1,2,5j z x x x x x x x x x x x x x j =++++++=⎧⎪+=⎪⎨+=⎪⎪≥=⎩"取松弛变量345,,x x x 为基变量，它对应的单位矩阵为基。

这样就得到初始可行基解：()()00,0,8,16,12TX =。

将有关数字填入表中，得到初始单纯形表，如表1-1所示：表 1-1 ()()00,0,8,16,12TX =j c →2 3 0 0 0i θB C b X b1x 2x 3x 4x 5x0 3x 8 1 2 1 0 0 4 04x16 4 0 0 1 0 -5x12 0 [4] 0 0 1 3j σ2 3 0 0 0若检验数均未达到小于等于0，则对上表进行调整。

选择上表中检验数最大的列，该列对应的非变量为入基变量；再应用θ规则该列对应的各基变量对应的θ值，选出其中最小的一行，该行对应的基变量为出基变量。

修改单纯形表，对各行进行初等变换，确保基变量组成的矩阵为单为矩阵。

修改后的单纯形表如表1-2所示：表 1-2 ()()10,3,2,16,0TX =检验数12,0σσ>，则进行继续调整，调整后的单纯形法表如表1-3所示：表 1-3 ()()22,3,0,8,0TX =表1-3中， 50σ>，则继续进行调整，调整结果如表1-4所示：表 1-4 ()()34,2,0,0,4TX =检验数0j σ≤，这表示目标函数值已不可能再增大，于是得到最优解：()()3*4,2,0,0,4TX X ==*14z =②带人工变量现有线性规划问题：12312312313123min 321142321,,0z x x x x x x x x x x x x x x =−++−+≤⎧⎪−++≥⎪⎨−+=⎪⎪≥⎩ 将上述线性规划问题用大M 法求解，在约束条件中加入松弛变量4x ，剩余变量5x ，人工变量6x ，7x 得到：1234567123412356137min 300211423210,1,2,,7j z x x x x x Mx Mx x x x x x x x x x x x x x j =−++++++−++=⎧⎪−++−+=⎪⎨−++=⎪⎪≥=⎩"其中，M 是一个任意大的正数。

运筹学单纯形法

运筹学单纯形法

单纯形表
max z=x1+2x2 s.t. x1+x23 x2 1 x1, x2 0
Cj CB XB b 0 0 Z X3 3 X4 1 0 1 2 0 0
标准化
max z=x1+2x2 s.t. x1+x2+ x3 =3 x2 +x4=1 x1, x2 ,x3, x40
X1 X2 X3 X4 1 0 1 1 1 2 1 0 0 0 1 0
Z=x1+2x2 x1+x2+ x3 =3 x2 +x4=1 单纯形表
Cj
1
2
0
0
单纯形法原理 单纯形表 CB XB b
z=x1+2x2 x3 =3-x1-x2 x4=1 -x2
x2进基，x4离基
X1 X2 X3 X4

3/1 11
0
1 0
1 1
1 1
2 2 0 1 0 2 0 1 0 0 1 0 -1 0
max z=x1+2x2 s.t. x1+x2+x3 =3 x2 +x4=1 x1, x2, x3, x40
x1=0
(x1,x2,x3,x4)= (0,1,2,0), z=2 C (x1,x2,x3,x4)= (2,1,0,0), z=4,最优解
B
x4=0 x3=0
(x1,x2,x3,x4)= (0,0,3,1), z=0
1 0
0 0
0 1
0
CB XB b 0 2 Z Cj CB XB b 1 2 Z X1 2 X2 1 4 X3 2 X2 1 2 1 1 0 0
X1 X2 X3 X4 1 0 1 1 0 0 0 -1 1 -1

单纯形法的表格解法


n
bi aij xj. i 1, 2,L , m
j m1
把以上的表达式带入目标函数，就有
m
n
z c1x1 c2 x2 L cn xn ci xi c j x j
i 1
j m 1
其中：
n
n
z0
c j z j x j z0 j x j
j m 1
j m 1
0 0 1 1 0 0 0 1 0 那么显然所求得的基本解一定是基本可行解，这个单位矩阵或由单位矩阵各列向 量组成的基一定是可行基。实际上这个基本可行解中的各个变量或等于某个bj或等 于零。
.
§1 单纯形法的基本思路和原理
在本例题中我们就找到了一个基是单位矩阵。
1 0 0
B2 0 1 0
0 0 1
m
z0 cibi , j c j z j ;
a1 j
i1 m
z j ciaij c1a1 j c2a2 j L
i 1
cmamj
c1, c2 ,L
, cm
a2
j
M
amj
c1, c2 ,L , cm p j .
§2 单纯形法的表格形式
上面假设x1,x2,…xm是基变量，即第i行约束方程的基变量正好是xi，而 经过迭代后，基将发生变化，计算zj的式子也会发生变化。如果迭代后的 第i行约束方程中的基变量为xBi，与xBi相应的目标函数系数为cBi，系数列
1. 最优性检验的依据——检验数σj 一般来说目标函数中既包括基变量，又包括非基变量。现在我们要求
只用非基变量来表示目标函数，这只要在约束等式中通过移项等处理就可 以用非基变量来表示基变量，然后用非基变量的表示式代替目标函数中基 变量，这样目标函数中只含有非基变量了，或者说目标函数中基变量的系 数都为零了。此时目标函数中所有变量的系数即为各变量的检验数，把变 量xi的检验数记为σi。显然所有基变量的检验数必为零。在本例题中目标 函数为50x1+100x2。由于初始可行解中x1，x2为非基变量，所以此目标函 数已经用非基变量表示了，不需要再代换出基变量了。这样我们可知 σ1=50，σ2=100，σ3=0，σ4=0，σ5=0。

单纯形法

•单纯形计算过程特别说明
1. 如何从单纯形表判断最优解
1)唯一最优解判别：最优表中所有非基变量的检验数大于零,则线性规划具有唯一最优解.
2)多重最优解判别：最优表中存在非基变量的检验数为零,则线性规划具有多重最优解(或无穷多最优解).
<0且a ik≤０（i=1,…,m）则线性规划具有无界解.
3)无界解判别：某个σ
k
4)无可行解的判别：当用大M单纯形法计算得到最优解并且存在Ri>0时，则表明原线性规划无可行解.
5)退化解的判别：
a)存在某个基变量为零的基本可行解;
[此时可能出现循环迭代而永远找不到最优解.该情况是由比值相同造成的.可以证明：当出现比值相同时,按下标最小的基变量作为换出变量可避免出现循环，具体可参阅有关文献];
b)人工变量在最优表的基中,但人工变量的取值为零.
[此种情况是由于存在多余约束(A不行满秩)造成的,可通过消去多余约束加以解决]
3. 计算过程需要特别注意的问题：
在确定了进基变量和出基变量，即确定主元后，单纯形变换的计算方法：
1）主元所在的行所有元素除以主元值，将主元变换成1；
2）用主元行的合适倍数加至其它各行(此时，改变的是其它各行，而主元行不发生变化!)，以将主元列除主元外的其它元素变换成零。

注：采用以上变换方法（而不是任意初等变换）是为了保证：原来在基中并为发生改变的基变量，在变换计算后其对应的基向量不能发生改变。

也就是说：在任何时候，单纯形表中的所有基向量构成的矩阵均为单位矩阵！。

第三章3 单纯形法2


第二节 单纯形法
那么纯收入就为 140-240=- （相当于检验数小于零） 140 元， 纯收入就为 140-240=-100 相当于检验数小于零） 那么 ， 说明炒股无利可图。 还有人们常说的炒股打了个平手 没有赚也没有 （ 说明炒股无利可图。 ，实际上已经亏了 亏） 实际上已经亏了 240 元。因为这笔钱不去炒股的话存在银行里 ， 元的收入， 240=还可以有 240 元的收入，所以纯收入为 0-240=-240 元。 上面分析过，既然生产产品甲还有利可图， 上面分析过，既然生产产品甲还有利可图，那么就要把 x1 转化 为基变量， 将有一个被换出成为非基变量。 为基变量，原来是基变量的 x3、x4 将有一个被换出成为非基变量。 min{15/3，6/（3/5）}=5， 将被换出。 因为 min{15/3，6/（3/5）}=5，可知 x4 将被换出。通过行线性
第二节 单纯形法
这时的实际情况是没有生产任何产品，所以每一种产 这时的实际情况是没有生产任何产品， 品的机会费用都为零（关于机会费用的详细说明参考课 品的机会费用都为零（ 本 23 页的内容） 检验数 Cj-Zj=利润-机会成本，它的值 的内容） ，检验数 ， 利润-机会成本， 就是这种生产条件下生产第 j 种产品可能得到的纯利润， 种产品可能得到的纯利润， 从中可以看出，生产丙产品可能获得的最大的利润（因 从中可以看出，生产丙产品可能获得的最大的利润（ 为 max{4，1，5}=5 ） 所以作为一个生产决策者首先应 max{4， ，所以作为一个生产决策者首先应 ， 当想到生产丙产品。 当想到生产丙产品。
第二节 单纯形法
5 3 1 0 -1/3 0 1/3 -1/3 1 1 -1/5 2/5 1 x2 -1/3 1 11/3 -8/3 5 x3 0 1 5 0 0 x4 1/3 -1/5 1/3 -1/3 0 x5 -1/3 2/5 2/3 -2/3

第3章05-单纯形表法

第3章05单纯形表法同学们大家好，前面我们讲了单纯形法的原理，它的整个过程看似很复杂，但实际上，单纯形法的全部计算过程，可以简单地在一张类似增广矩阵的表格上进行，这种表格我们称为单纯形表，所以，今天我们就来学习线性规划模型的单纯形表法。

给定一个可行基，可以画出一张单纯形表。

单纯形表的行标是n个变量以及右端项b，列标是m个基变量以及检验数行σ。

所以，用矩阵的形式把它表示出来，就如下表所示我们注意到，像B，所以，是与原方程组等价的。

最后一行是检验数C-C B B-1A，右下角是-C B B-1b，它恰好是这个基B所对应的可行解的目标函数值的相反数。

用单纯形表法求解线性规划模型时，有下面的步骤：单纯形表法求解线性规划问题的步骤：Step1.转换一般的线形规划模型为标准型，并写出A，b，C。

Step2找初始基本可行解，写出B，B-1，X B，C B。

Step3计算单纯形表中的各矩阵B-1A，B-1b，C-C B B-1A，-C B B-1b，并构造初始单纯形表。

Step4判断基本最优解。

Step5换基迭代，返回Step4。

第一步是将一般的线性规划模型转化为标准形，并写出约束矩阵A，右端项b，以及价值向量C。

第二步，找初始的基本可行解。

根据上一讲单纯形法的原理，你要注意的是，我们总是从约束矩阵A里面选一个单位阵出来作为初始基，在右端项非负的条件下，这样选出来的单位阵一定是可行基，也就是找到了初始的基本可行解。

而如果约束矩阵A中没有单位阵，我们将会通过引入人工变量构造出一个单位阵，这种构造方法我们将在后面进行详细介绍。

初始基选出来之后，我们就能写出B，B-1，以及基变量X B和基变量所对应的价值向量C B。

第三步，计算B-1A，B-1b，C-C B B-1A，-C B B-1b，这样就可以把初始单纯形表写出来。

第四步，判断当前的基本可行解是不是最优解？按照我们上一讲介绍的单纯形法的原理，如果检验数行中所有的检验数都小于等于0，当前的基本解就是最优解；如果有一个非基变量的检验数是正的，而且它所对应A中的列的项都小于等于0,那么这个时候是无界解。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。