第四讲 单纯型表格算法(运筹学-清华大学,林谦)

t t (a t ijV i ) t ijV i
1 rj rs s ir ir
m
ir j 将a 的两个表达式(21)和(23)的矢量系数加以比较，便可
1 s 1 t rj t rs a (t ij t is t rj t rs )V i
(23)
得出下述关系：
Operations Research
第七、八讲
§1 与基础解对应的单纯型表格（1）
关于单纯形法概念，以前已讲过，本章讲具体计算步骤。该 计算方法在计算机上计算。令A为m×n矩阵，m≤n,行线性 独立，即秩为m。非退化线性规划的标准形式为： AX=b，X≥0，CTX=min (1)
如果b是A的不少于m列的线性组合，则称非退化形式。设从 阶段2开始计算，即设已获得初始可行解X（这需阶段1，而 寻找第1个初始可行解亦需用到阶段2算法）。
各个元素如何根据原表1-3求出呢？
现在就对该问题进行推导。因为当前基础解和新基础 解都假定是可行的非退化解，因此两表中： ti0>0 ，t’i0>0 (i=1,2,…,m) (16)
page 12 25 January 2014
Prof. Wang School of Economics & Management
(18)
由于基础矢量V1,…Vr, …Vm线性无关，因此trs≠0；
page 13 25 January 2014
Prof. Wang School of Economics & Management
Operations Research
第七、八讲
§2 新基础解表格与原表格的关系（5）
否则，从式(18)中说明，as可由Vi(i=1,…,m,i≠r)线性组合， 这说明新基础解不是线性无关的矢量构成，与假设矛盾。 于是，Vr可根据式(18)表达为： Vr=
则扩充表格为：
a1 V1=a3 V2=a1 0 1 a2 1 -1 一
page 8 25 January 2014
a3 1 0
b 1 2 二
e1 3 -7
e2 -2 5 三 (15)
Prof. Wang School of Economics & Management
Operations Research
对于扩充表格右边系数 u’ij 的表达更没问题。可把单位 矢量ej作为扩充矩阵[A，I]的列，就像阶段法1做的那样， 可设： e1=an+1，e2=an+2，…，em=an+m (26)
于是，我们可定义：
uij=ti,，n+j (i,j=1,2, …,m) (27)
在式(24)和(25)中，用n+j代替j可得 ③当i=r时，u’rj=urj/trs ④当i≠r时，u’ij=uij－(tis/trs)urj
---------------------------------------------
因为单位矢量 ej(j=1, …,m)构成一个标准单位矩阵 I，而 Vi是基础矩阵M的列，根据式(10)知，I=MU ∴U=M－1。因此扩充表格中的{uij}是当前基础阵之逆阵。
page 6 25 January 2014
同样，b可写成：b=t10V1+t20V2+…+tm0Vm
这样，便可给出一个单纯形表格 (tij)，i=1,…,m；j=1,2,…,n,0
page 3 25 January 2014
(5)
(6)
Prof. Wang School of Economics & Management
Operations Research
em u’1m u’rm
u’mm
t’11 t’r1 t’m1
┇ (Vm)’
page 11 25 January 2014
Prof. Wang School of Economics & Management
Operations Research
第七、八讲
§2 新基础解表格与原表格的关系（3）
其中原表格是已经给出的与当前基础矢量相对应的单 纯形表格，新基础解是由原非基矢量as代入Vr所致。 其新解所对应的表格形式如表1-4所示，那么新表中
①当i=r时,
②当i≠r时，
page 16 25 January 2014
t’rj=trj/trs
t’ij=tij－(tis/trs)trj
(24)
(25)
Prof. Wang School of Economics & Management
Operations Research
第七、八讲
§2 新基础解表格与原表格的关系（8）
1 t rs (a s t isV i ) i 1 ir m
(19)
从假设知，新基础解基础矢量为：
(V1)’=V1, …,(Vr)’=as, …,(Vm)’=Vm
为获得新表格，系数t’ij应满足：
page 14 25 January 2014
(20)
Prof. Wang School of Economics & Management
第七、八讲
§2 新基础解表格与原表格的关系（1）
设在上述基础解的基础上，将非基矢量as引进基础解集， 即as→B集；而令原基础解集B中的Vr处原基矢量离开。 这两种情况表达形式示于表1-3和表1-4 表1-3 原表格（用当前基础解表达矢量） a1 … as … an b e1 … em V1 ┇ Vr ┇ Vm t11 ┇ t r1 ┇ tm1 … t1s ┇ trs ┇ tms … t1n ┇ trn ┇ tmn t10 ┇ t r0 ┇ tm0 u11 ┇ ur1 ┇ um … … … u1m ┇ urm ┇ umm
page 15 25 January 2014
trjVr+
i t V ij ir(2 Nhomakorabea)Prof. Wang School of Economics & Management
Operations Research
第七、八讲
§2 新基础解表格与原表格的关系（7）
现在，把Vr用式(19)代入，则式(22)变为： aj =
i u V = ij i 1
m
(j=1,2,…,m)
(10)
Prof. Wang School of Economics & Management
Operations Research
第七、八讲
§1 与基础解对应的单纯型表格（5）
于是，扩充的单纯形表格如下 ：
a1 V1 ┇ Vm tm1 t11 … … … an t1n tmn b t10 tm0 e1 u11 um1 … … … em u1m umm
page 17 25 January 2014
(28) (29)
Prof. Wang School of Economics & Management
Operations Research
第七、八讲
§2 新基础解表格与原表格的关系（9）
上述公式的含义如下：如果用 as代替Vr 而形成新基础可 行解，则称 ①原表中的r行为支点行 ②原表中的s列为支点列 ③trs为支点元素 支点行(r)：新表r行＝原表r行/trs
page 2 25 January 2014
Prof. Wang School of Economics & Management
Operations Research
第七、八讲
§1 与基础解对应的单纯型表格（2）
设已有一个基础可行解 X ，只依赖于 m 列 aj(j=1,…,m) ， 则有 xj>0，jB，B={j1，…，jm} (2) 令矢量 Vi=aji (i=1,2,…,m) (3) 则，V1，V2，…，Vm即是当前基础矩阵M的列矢量。 现把A阵每一列都用基础列表达： aj=t1jV1+t2jV2+…tmjVm (j=1,2,…,n) (4)
扩充单纯形表格：前述表格中的元素仅是把A阵矢量和b 表达为基础矢量线性组合时的系数，为方便，现又增加 {uij} ， 其 含 义 是 把 m 个 单 位 矢 量 e1(1,0,0,…) ， e2(0,1,0, …)， …，em(0,0,…,1)表达成基本矢量的线性组 合，即：
ej
page 5 25 January 2014
page 10 25 January 2014
Prof. Wang 1 School of Economics & Management
Operations Research
第七、八讲
§2 新基础解表格与原表格的关系（2）
a1 (V1)’ ┇
as→(Vr)’
表1-4 新表格（用新基础解表达矢量） … as … an b e1 … … t’1s t’rs t’ms … t’1n t’rn t’mn t’10 t’r0 t’m0 u’11 u’r1 u’m1 … … …
非支点行(i):新表i行=原表i行－i（原表r行）
page 18 25 January 2014
Prof. Wang School of Economics & Management
Operations Research
第七、八讲
§2 新基础解表格与原表格的关系 （10）
Operations Research
第七、八讲
§2 新基础解表格与原表格的关系（6）
aj=t’1j(V1)’+ …+t’rj(Vr)’+ … +t’mj(Vm)’ 这表明 aj = t’rj as+
i t ' V ij ir