运筹学-修正单纯形法(1)(名校讲义)

第九讲第九讲 修正单纯形法（修正单纯形法（ 1） 大约在 1954年， Dantzig和他的同事就发现了更有效的单纯形法。我们知道，在单纯 (扩展 )表格中，共有 3组元素，分别与矢量组 “a1， ， an”， “b”及 “e1 em”相对应，如果说前面讲的习惯用的一般单纯形表格法可只采用左边两组的话，那么，修正单纯形法在运算迭代中只应用右边两组，下面就具体阐述该种方法。仍假设： AX=b， X0， CTX=min (1)且 A、 b、 C已知，属非退化情形，计算过程，将始终用到 A， B， C这些原始数据，故需保存。每一个阶段仍用单纯形表格迭代，只用右边两组，即 m+1列，每个表格与当前基础解集相对应（ j1， ， jm）：第九讲第九讲 修正单纯形法（修正单纯形法（ 2） t10tm0u11 u1mum1 ummz0 y1 ym(2)其中： ti0 给出当前基础解uij 给出当前基础阵之逆z0 给出当前基础解费用yi 给出当前基础阵之联立方程解YTM= (3)第九讲第九讲 修正单纯形法（修正单纯形法（ 3） (5)其中 当前基础解的目标系数。 表格的起步可根据两阶段法的第 1阶段之初始基础解表格开始，即：ti0=bi ， uij = ij ， z0=bi， yi=1 (4)第 1阶段结束后，第 2阶段开始的表格需加以修改，唯一修改处是最末一行，这是由于目标函数发生了变化 z0和 yi计算公式为：第九讲第九讲 修正单纯形法（修正单纯形法（ 4） (6)如果 zj cj，则令 j = s，并作为支点列。如果 zj cj，则去试探其它非基础列 j，假若所有非基础列 j的 zj cj，则已达到最优解，其最优解值为：下面来阐述表格的迭代过程。在一般单纯形表格法中，每次检验元素 zj cj全部算出，然后寻找支点列，而在修正单纯形表格中，不需一次计算全部检验元素，而是逐个计算。设 j属非基础集，则：第九讲第九讲 修正单纯形法（修正单纯形法（ 5） (7)其最小费用为 z0和最优对偶解为 yT。否则，计算 zj(按 6式 )，找出 zj cj，并令 j = s，然后处理如下：首先，计算单纯形表的支点列 s： (8)第九讲第九讲 修正单纯形法（修正单纯形法（ 6） 如果所有 tis0，则最优解不存在，最优目标无限，即，(9)费用若存在 tis0,可求出支点行：(10)第九讲第九讲 修正单纯形法（修正单纯形法（ 7） 求出支点行后，就可进行修正单纯形表格的转换，其表格转换元素的计算只需计算后面 m+1列，即：新行 r = (原行 r)/trs (11)新行 i (i r) = (原行 i) i(原行 r) (12) 其中： 最后，用 as取代旧表格 Vr中表示的基矢量。第九讲第九讲 修正单纯形法（修正单纯形法（ 8） 例 1-23 已知线性规划为：解 1）应用阶段 1，求出初始基础可行解构成新规划： A X = b ， X 0, CTX=min第九讲第九讲 修正单纯形法（修正单纯形法（ 9） 令人工变量作为第 1个基础可行解之基础变量，其对应的表格为： e1e2b e1 e25 1 013 0 118 1 1 第九讲第九讲 修正单纯形法（修正单纯形法（ 10） 检验非基础变量 a1， a2， a3能否进基，可按任何次序检验。先检验 a1：第九讲第九讲 修正单纯形法（修正单纯形法（ 11） e1e2a1 b e1 e21 5 1 04 13 0 15 18 1 1min5/1， 13/4 = 13/4 r = 2。 支点元素为 t21，进行变换使 (t1)列中： t21 =1， t11 =0， z1 c1 = 0，得：将 (t1) 临时放入表格中，以便求出支点行， 第九讲第九讲 修正单纯形法（修正单纯形法（ 12） 当前表格对应的基础矢量为 e1和 a1。再次校验非基础矢量，看是否可进入基础矢量，任意选择 a3检验 。 e1a1a1 b e1 e20 7/4 1 -1/41 13/4 0 1/40 7/4 1 -1/4第九讲第九讲 修正单纯形法（修正单纯形法（ 13） 将 (t3)加入修正单纯形表格中，并求出支点行 r。 e1a1a3 b e1 e23/2 7/4 1 -1/43/2 13/4 0 1/43/2 7/4 1 -1/4第九讲第九讲 修正单纯形法（修正单纯形法（ 14） 即 e1离开基， a3进基，将表格变换得：a3a1a3 b e1 e21 7/6 2/3 -1/60 3/2 -1 1/20 0 0 0从表中看出， 故阶段 1结束，得出初始基础可行解为 x3=7/6， x1=3/2， x2=0。 第九讲第九讲 修正单纯形法（修正单纯形法（ 15） 2）现进行阶段 2，阶段 2的第 1个表格可借用阶段 1的最后表格，仅仅将最后一行加以修改。此时： A， B， C恢复到原问题数值，这时 CT=(7， 1， 1)。其初始表格为：a3a1b e1 e27/6 2/3 -1/63/2 -1 1/235/3 -19/3 10/3 其中， 第九讲第九讲 修正单纯形法（修正单纯形法（ 16） 现判断非基矢量 a2是否应进入基础解集。第九讲第九讲 修正单纯形法（修正单纯形法（ 17） 即支点行 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， z2 c2=0得出新表格为：第九讲第九讲 修正单纯形法（修正单纯形法（ 18） 目前基础矢量为 a2和 a1。再检验非基矢量 a3：a2 b e1 e21 7/3 4/3 -1/30 1/3 -5/3 2/30 14/3 -31/3 13/3a2a1故已得最优解 ： x2 = 7/3， x1 = 1/3y1 = -31/3 ， y2 = 13/3， 且 z = 14/3第九讲第九讲 修正单纯形法（修正单纯形法（ 19） 与此相应的有另一种方法 对偶单纯型法，它的迭代原则是：在保证 “优化 ”前提下，寻找原问题可行解，即在保证对偶可行解基础上，逐步找