第五讲修正单纯形法(1)(运筹学-清华大学,林谦)

1、第九讲大约在1954年，Dantzig和他的同事就发现了更有效的单纯形法。 我们知道，在单纯(扩展)表格中，共有3组元素，分别与矢量组“a1，an”，“b”及“e1em”相对应，如果说前面讲的习惯用的一般单纯形表格法可只采用左边两组的话，那么，修正单纯形法在运算迭代中只应用右边两组，下面就具体阐述该种方法。 仍假设： AX=b， X0， CTX=min (1) 且A、b、C已知，属非退化情形，计算过程，将始终用到A，B，C这些原始数据，故需保存。每一个阶段仍用单纯形表格迭代，只用右边两组，即m+1列，每个表格与当前基础解集相对应（j1，jm）：第九讲t10tm0u11 u1m um1 ummz

2、0 y1 ym(2)其中：ti0给出当前基础解 uij给出当前基础阵之逆 z0给出当前基础解费用 yi给出当前基础阵之联立方程解YTM= (3)TC第九讲miiictz100miijijcuy1(5)其中 当前基础解的目标系数。 ic表格的起步可根据两阶段法的第1阶段之初始基础解表格开始，即：ti0=bi ，uij = ij ，z0=bi，yi=1 (4)第1阶段结束后，第2阶段开始的表格需加以修改，唯一修改处是最末一行，这是由于目标函数发生了变化z0和yi计算公式为：第九讲(6) 如果zj cj，则令j = s，并作为支点列。如果zj cj，则去试探其它非基础列j，假若所有非基础列j的zj

3、cj，则已达到最优解，其最优解值为：下面来阐述表格的迭代过程。在一般单纯形表格法中，每次检验元素zjcj全部算出，然后寻找支点列，而在修正单纯形表格中，不需一次计算全部检验元素，而是逐个计算。设j属非基础集，则：mijiijayz1第九讲(7) )1( 0mitxxijii， ) 1( 1miautmkksikis， 其最小费用为z0和最优对偶解为yT。否则，计算zj(按6式)，找出zj cj，并令j = s，然后处理如下：首先，计算单纯形表的支点列s： (8)第九讲如果所有tis0，则最优解不存在，最优目标无限，即，(9)miiisisVttaAX10 )()(费用 cos,)()0()(c

4、ostczXCXCtssTT当若存在tis0,可求出支点行：0/min/00isisirsrttttt：(10)第九讲求出支点行后，就可进行修正单纯形表格的转换，其表格转换元素的计算只需计算后面m+1列，即：新行r = (原行r)/trs (11)新行i (i r) = (原行i) i(原行r) (12) 其中： rsssrsisitczmiritt/ )( ,1, /0，最后，用as取代旧表格Vr中表示的基矢量。第九讲例1-23 已知线性规划为：解 1）应用阶段1，求出初始基础可行解构成新规划：A X = b ，X 0, CTX=min117 135 6 5 43 2 1min0T，CbAX

5、CxbAXT，1351 0 6 5 40 1 3 2 1bA第九讲令人工变量作为第1个基础可行解之基础变量，其对应的表格为： 2132121321,1 1 0 0 0,ssxxxXCCCCCCTSSTe1e2 b e1 e25 1 013 0 118 1 1 第九讲检验非基础变量a1，a2，a3能否进基，可按任何次序检验。先检验a1：41411 00 1)(,055411 112111111111aUtttaczayzT可以进基第九讲e1e2 a1 b e1 e21 5 1 04 13 0 15 18 1 1 min5/1，13/4 = 13/4 r = 2。支点元素为t21，进行变换使(t1

6、)列中：t21 =1，t11 =0，z1 c1 = 0，得：将(t1) 临时放入表格中，以便求出支点行， 第九讲当前表格对应的基础矢量为e1和a1。再次校验非基础矢量，看是否可进入基础矢量，任意选择a3检验。 e1a1 a1 b e1 e20 7/4 1 -1/41 13/4 0 1/40 7/4 1 -1/4第九讲将(t3)加入修正单纯形表格中，并求出支点行r。 2/32/3631/4 04/11)(0230634/113231333333UatttcayczTe1a1 a3 b e1 e23/2 7/4 1 -1/43/2 13/4 0 1/43/2 7/4 1 -1/4第九讲即e1离开基

7、，a3进基，将表格变换得：a3a1 a3 b e1 e21 7/6 2/3 -1/60 3/2 -1 1/20 0 0 01, 6/76/13, 6/7min2/34/13,2/34/7minr从表中看出， 故阶段1结束，得出初始基础可行解为x3=7/6，x1=3/2， x2=0。 ，0min00isz第九讲2）现进行阶段2，阶段2的第1个表格可借用阶段1的最后表格，仅仅将最后一行加以修改。此时：A，B，C恢复到原问题数值，这时CT=(7，1，1)。其初始表格为：a3a1 b e1 e27/6 2/3 -1/63/2 -1 1/235/3 -19/3 10/3 其中， miiimiiimiii

8、cuycuyctZ1221111003/10712/16/13/197113/23/35712/36/7，第九讲现判断非基矢量a2是否应进入基础解集。1,r 3/73 , 3/7min2/12/3,1/27/6min 21215221 161322, 0314452310,3192221222222有非负项又即可进入故UattsBaczayzT第九讲即支点行r = 1，a3离开，支点元素t12=1/2。将a2加入表格并转换 a2 b e1 e21/2 7/6 2/3 -1/61/2 3/2 -1 1/23 35/3 -19/3 10/3将a2对应的t2列变为t12=1，t22=0，z2c2=0得出新表格为：第九讲目前基础矢量为a2和a1。再检验非基矢量a3： a2 b e1 e21 7/3 4/3 -1/30 1/3 -5/3 2/30 14/3 -31/3 13/3a2a106151633/133/313333，cayczT故已得最优解 ：x2 = 7/3， x1 = 1/3y1 = -31/3 ，y2 = 13/3， 且z = 14/3第九讲与此相应的有另一种方法对偶单纯型法，它的迭代原则是：在保证“优化”前提下，寻找原问题可行解，即在保证对偶可