教学课件PPT修正单纯形法.ppt

第九讲修正单纯形法 1 大约在1954年 dantzig和他的同事就发现了更有效的单纯形法 我们知道 在单纯 扩展 表格中 共有3组元素 分别与矢量组 a1 an b 及 e1 em 相对应 如果说前面讲的习惯用的一般单纯形表格法可只采用左边两组的话 那么 修正单纯形法在运算迭代中只应用右边两组 下面就具体阐述该种方法 仍假设 ax b x 0 ctx min 1 且a b c已知 属非退化情形 计算过程 将始终用到a b c这些原始数据 故需保存 每一个阶段仍用单纯形表格迭代 只用右边两组 即m 1列 每个表格与当前基础解集相对应 j1 jm 第九讲修正单纯形法 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 如果所有tis 0 则最优解不存在 最优目标无限 即 9 费用 若存在tis 0 可求出支点行 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 c tx min 第九讲修正单纯形法 9 令人工变量作为第1个基础可行解之基础变量 其对应的表格为 第九讲修正单纯形法 10 检验非基础变量a1 a2 a3能否进基 可按任何次序检验 先检验a1 第九讲修正单纯形法 11 min 5 1 13 4 13 4 r 2 支点元素为t 21 进行变换使 t1 列中 t 21 1 t 11 0 z 1 c 1 0 得 将 t1 临时放入表格中 以便求出支点行 第九讲修正单纯形法 12 当前表格对应的基础矢量为e1和a1 再次校验非基础矢量 看是否可进入基础矢量 任意选择a3检验 第九讲修正单纯形法 13 将 t3 加入修正单纯形表格中 并求出支点行r 第九讲修正单纯形法 14 即e1离开基 a3进基 将表格变换得 从表中看出 故阶段1结束 得出初始基础可行解为x3 7 6 x1 3 2 x2 0 第九讲修正单纯形法 15 2 现进行阶段2 阶段2的第1个表格可借用阶段1的最后表格 仅仅将最后一行加以修改 此时 a b c恢复到原问题数值 这时ct 7 1 1 其初始表格为 其中 第九讲修正单纯形法 16 现判断非基矢量a2是否应进入基础解集 第九讲修正单纯形法 17 即支点行r 1 a3离开 支点元素t12 1 2 将a2加入表格并转换 将a2对应的t2列变为t12 1 t22 0 z2 c2 0得出新表格为 第九讲修正单纯形法 18 目前基础矢量为a2和a1 再检验非基矢量a3 故已得最优解 x2 7 3 x1 1 3y1 31 3 y2 13 3 且z 14 3 第九讲修正单纯形法 19 与此相应的有另一种方法 对偶单纯型法 它的迭代原则是 在保证 优化 前提下 寻找原问题可行解 即在保证对偶可行解基础上 逐步找出原规划可行解 这些概念体现在表格上 即使每一步表格的检验行的元素 zj cj