对偶性与对偶算法.ppt

将 的表示式代入目标函数，原问题等价为 变换后的等价问题对应的单纯型表为 该单纯型表的检验数均为非正数，如果右边常数没 有负数，已经得到原问题的最优解 能否在保持检验数非正的前提下消除负的右边数？ ② ① ①× (-0.5) + ② ①× (-2) + ② 或 合格 不合格 选比值小的进基！ 出基变量行非基变 量的系数全为负数 ② ① ①× (-2) + ② 合格 选比值小的变量进基时不用考虑负数！ 出基变量行非基变 量的系数中有正数 出基变量行的变量系数全为正数时原问题无解！ 不可能同时成立 出基变量行非基变 量的系数全为正数 一般情况：要处理的等式约束和目标约束可写成 用 进基替换 ，可验证所有检验数保持非正 若 中没负数，原问题无可行解 否则可确定 其中 是出基变量 ， ， 其中 用 进基替换 得到新的检验数的过程如下： ① ①× ( ) + ② ② 所有检验数保持非正 进基 出基后的表 回到开始的单纯型表 常数项全部非负 检验数全部非正 已经得到最优解 一般情况：消除负的右边常数后可能在常数项中产生 新的负常数，例如，在原表中将第三行除以 得 变换后的前两个常数值取决于 所在列的前两个数据， 完全可能出现负数 继续迭代能否保证收敛？ 由于每次迭代是从一个不可行的基矩阵转到另一个 不可行的基矩阵（一旦遇到可行的基矩阵就得到了 最优解），而基矩阵的总数是有限的，如果不出现 循环，算法一定在有限步内停止于最优解 所以，关键问题是，迭代过程是否不会出现循环？ 为回答收敛问题，先确定一步迭代后下式中的 由于上式来自 ①× ( ) + ②，其中 可得 ① ② 如果 （相当于非退化条件），因为 所以 由于 和 都是由对应的基矩阵决定的， 说 明在 以后产生的基矩阵不可能等于 对应的基矩 阵，因此，在非退化条件下可以保证算法收敛于最 优解，在退化情况下，只要采取辅助措施避免在具 有相同 值的几个基矩阵中循环就可以保证收敛 为什么叫对偶单纯型法？ 原问题 对偶问题 和一次迭代后的 都是对偶问题的 可行解，目标值满足 ，该算法 的本质是 在对偶问题的可行顶点集中沿着目标函数下 降路径找到最优顶点，所以叫对偶单纯型法 可行集 例 1 的可行集和目标函数等值线如下图所示，其中 黄点是基本可行解，黑点是不可行基矩阵确定的点 对偶单纯型法的几何意义 对偶单纯型法 是从不可行区 域逐渐减少目 标函数值逼近 最优解，如右 图从 到最 优解 什么时候用对偶单纯型法？ 例、 等价问题 上述问题没有明显的初始可行基，需引入人工变量，但 有明显的对偶可行基，用对偶单纯型法不需要人工变量 原问题 结论：对偶单纯型法适用于 的下述线性规划问题 灵敏度分析 假定已求得最优可行基 ，并获得 等有关数据 对于标准线性规划问题 若某些参数发生变化，如 如何利用已知数据确定新的最优解？ 例1 最终单纯型表 如果目标函数改变： 最终单纯型表 继续迭代 如果常数向量改变： 最终单纯型表 其中新的常数向量为 ，如果 ，已经得到 最优解，否则可用对偶单纯型法继续迭代 能否从最终单纯型表中找出 ？ 初始单纯型表 最终单纯型表 一般情况：若在标准型初始矩阵 中存 在单位阵，比如 由于单纯型表的各列向量等于 所以 只要将最初的单位向量所在列的最终数据按单位向量在 单位矩阵中的位置排好就可以得到 注意： 中各 所在列数取决于基变量所在行数！ 对偶性与对偶算法 线性规划对偶性质 求解标准线性规划问题 最终要找到一个基阵 满足 而最优目标值等于 记 ，原问题有最优解时， 满足以下约束 可否在满足以上约束的解中找到 ，进而找到 ？ 设 是原问题的任意一个可行解，即满足 对任何满足不等式约束 的