page 13 25 January 2014
7/4
1
-1/4
Prof. Wang School of Economics & Management
Operations Research
第九讲
修正单纯形法（14）
7 / 4 13 / 4 min , min 7 / 6,13 / 6 7 / 6, r 1 3/ 2 3/ 2
Operations Research
第九讲
修正单纯形法（11）
将(t1)' 临时放入表格中，以便求出支点行， a1 1 4 b 5 13 e1 1 0 e2 0 1
e1 e2
5 18 1 1 min{5/1，13/4} = 13/4 r = 2。支点元素为t’21， 进行变换使(t1)’列中：t’21 =1，t’11 =0，z’1 － c’1 = 0，得：
i tis / trs i r，i 1,, m 0 ( z s cs ) / trs
最后，用as取代旧表格Vr中表示的基矢量。
page 7 25 January 2014
Prof. Wang School of Economics & Management
Operations Research
T 3
t '13 3 / 2 3 1 1 / 4 3 (t )' Ua t 'ห้องสมุดไป่ตู้0 1/4 6 3 / 2 23
3
将(t3)'加入修正单纯形表格中，并求出支点行r。 a3 b e1 e2 1 -1/4 e1 3/2 7/4 0 1/4 a1 3/2 13/4 3/2
Prof. Wang School of Economics & Management
Operations Research
第九讲
修正单纯形法（7）
求出支点行后，就可进行修正单纯形表格的转换，其表 格转换元素的计算只需计算后面m+1列，即： 新行r = (原行r)/trs 新行i (i r) = (原行i) － i(原行r) 其中： (11) (12)
Prof. Wang School of Economics & Management
Operations Research
第九讲
修正单纯形法（4）
下面来阐述表格的迭代过程。在一般单纯形表格法中， 每次检验元素 zj －cj全部算出，然后寻找支点列，而在修 正单纯形表格中，不需一次计算全部检验元素，而是逐 个计算。设j属非基础集，则：
page 12 25 January 2014
Prof. Wang School of Economics & Management
Operations Research
第九讲
修正单纯形法（13）
3 3 z '3 c'3 y ' a c'3 1 1 / 4 0 0 2 6
Prof. Wang School of Economics & Management
Operations Research
第九讲
修正单纯形法（16）
现判断非基矢量a2是否应进入基础解集。
19 10 2 z 2 y a , 4 3 3 5
1 2 3 1 0 5 A' ，b' ， 4 5 6 0 1 13
page 8 25 January 2014
Prof. Wang School of Economics & Management
Operations Research
第九讲
修正单纯形法（9）
Operations Research
第九讲
修正单纯形法（5）
xi x ji ti 0 (i 1， ，m)
其最小费用为z0和最优对偶解为yT。

(7)
否则，计算zj(按6式)，找出zj > cj，并令j = s，然后处理 如下：
首先，计算单纯形表的支点列s：
tis uik aks
第九讲
修正单纯形法（8）
[例1-23] 已知线性规划为：
AX b，x 0， C T X min 1 A 4 2 5 3 5 T ， b ， C 7， 1， 1 6 13
[解] 1）应用阶段1，求出初始基础可行解 构成新规划：A' X ' = b ' ，X '≥0, C'TX'=min
C T C1 , C 2 , C3 , C S1 , C S 2 0 0 0 1 1 X 'T x1 , x2 , x3 , s1 , s 2
令人工变量作为第1个基础可行解之基础变量，其对应的 表格为： b e1 e2 e1 e2 5 13 18 1 0 1 0 1 1
page 9 25 January 2014
Prof. Wang School of Economics & Management
Operations Research
第九讲
修正单纯形法（15）
2 ）现进行阶段 2 ，阶段 2 的第 1 个表格可借用阶段 1 的最 后表格，仅仅将最后一行加以修改。此时：A，B，C恢 复到原问题数值，这时CT=(7，1，1)。其初始表格为： b e1 e2 其中， 7/6 2/3 -1/6 m 1 3/2 -1 1/2 Z 0 ti 0 c i 7 / 6， 3 / 2 7 35 / 3 i 1 35/3 -19/3 10/3
a3 a1
1 y1 ui1 c i 2 / 3， 1 7 19 / 3 i 1 m 1 y2 ui 2 c i 1 / 6， 1 / 2 7 10 / 3 i 1
m
page 15 25 January 2014
3
7/6 3/2
35/3
2/3 -1
-19/3
-1/6 1/2
10/3
将a2对应的t2列变为t12=1，t22=0，z2－c2=0 得出新表格为：
page 17 25 January 2014
z j yi ai j
i 1
m
(6)
如果zj > cj，则令j = s，并作为支点列。 如果zj ≤cj，则去试探其它非基础列j，假若所有非基础 列j的zj ≤cj，则已达到最优解，其最优解值为：
page 4 25 January 2014
Prof. Wang School of Economics & Management
Prof. Wang School of Economics & Management
Operations Research
第九讲
修正单纯形法（10）
检验非基础变量a1，a2，a3能否进基，可按任何次序检验。 先检验a1： 1 T 1 z '1 y ' a 1 1 5 4
25 January 2014
School of Economics & Management
Operations Research
第九讲
修正单纯形法（2）
t10
· · ·
u11
…
u1m
tm0
z0
um1 … umm y1 … y m
(2)
其中：ti0——给出当前基础解 uij——给出当前基础阵之逆 z0——给出当前基础解费用 yi——给出当前基础阵之联立方程解
T 2
z 2 c2 4 1 3 0, 故a 2可进入B, 即s 2 1 2 1 2 t12 3 6 2 又 Ua 2 有非负项 t 22 1 1 5 1 2 2 7/6 3 / 2 min , min 7 / 3,3 7 / 3 r 1, 1/2 1 / 2
z '1 c'1 5 0 , a1可以进基 t '11 1 0 1 1 1 (t )' U ' a 0 1 4 4 t '21
1
page 10 25 January 2014
Prof. Wang School of Economics & Management
m i 1
费用
cos t C T X ( ) C T X (0) ( zs c s )当 , cos t
若存在tis>0,可求出支点行：
(9)
tr 0 / trs min ti 0 / tis：tis 0
(10)
page 6 25 January 2014
Operations Research
第九讲
第五讲 修正单纯形法（1）
大约在1954年，Dantzig和他的同事就发现了更有效的单 纯形法。 我们知道，在单纯(扩展)表格中，共有3组元素，分别 与矢量组“a1，…，an”，“b”及“e1……em”相对应，如 果说 前面讲的习惯用的一般单纯形表格法可只采用左边两组 的话，那么，修正单纯形法在运算迭代中只应用右边两 组，下面就具体阐述该种方法。 仍假设： AX=b， X≥0， CTX=min (1) 且A、b、C已知，属非退化情形，计算过程，将始终 用到A，B，C这些原始数据，故需保存。每一个阶段仍 用单纯形表格迭代，只用右边两组，即m+1列，每个表 page 格与当前基础解集相对应（ 1 j1，…，jm）： Prof. Wang