单纯形法的几何意义ppt课件.ppt

第四步 若检验数中有些为正数 且它们所对应的系数bir中有正数 则需要换基 进行迭代运算 在所有大于零的检验数中选取最大的一个 设对应的非基变量为xr 则取xr为进基变量 并求最小比值 由此确定xjs为离基变量 若上述最小值同时在几个比值上达到 则选取其中下标最小的变量为离基变量 然后用pr代换pjs 得到新基 再接下一步 第五步 求出新基对应的典式以及基可行解x 1 然后以取代B x 1 取代x 0 返回第二步 从第二步到第五步的每一次循环 称为一次单纯形迭代 2 4退化情形的处理 最大检验数规则 最小下标规则 2 4退化情形的处理 一 退化问题可能会出现基的循环 2 4退化情形的处理 二 退化问题中避免基循环的方法 2 4退化情形的处理 P48Beale例子 用Bland法则求解 二 退化问题中避免基循环的方法 在第1 2行取得 故x5为离基变量 2 4退化情形的处理 由表2 15可知 x1 x3的检验数均为正数 由Bland规则 取x1为进基变量 因为最小比值 于是 b11为表2 15的枢元 新基为B1 p1 p6 p7 并将x5换为x1 得新基B1对应的单纯形表 见表2 16 对表2 15作初等行变换 进基的选择也符合 最大检验数规则 最小下标规则 二 退化问题中避免基循环的方法 2 4退化情形的处理 由表2 16可知 x2 x3的检验数均为正数 由Bland规则 取x2为进基变量 进基的选择也符合 最大检验数规则 二 退化问题中避免基循环的方法 2 4退化情形的处理 由表2 17可知 只有x3的检验数均为正数 取x3为进基变量 二 退化问题中避免基循环的方法 进基的选择 既符合最大检验数规则 又符合Bland规则 2 4退化情形的处理 由表2 18可知 x4 x5的检验数均为正数 由Bland规则 取x4为进基变量 进基的选择也符合 最大检验数规则 前4次迭代 用最大检验数规则和Bland规则的结论一样 具体结果都是表2 15与2 19 二 退化问题中避免基循环的方法 在第3行取得 故x7为离基变量 2 4退化情形的处理 由表2 19可知 x1 x5的检验数均为正数 由Bland规则取x1为进基变量 因为最小比值 于是 b31为表2 19的枢元 新基为B5 p3 p4 p1 并将x7换为x1 得新基B5对应的单纯形表 见表2 22 对表2 19作初等行变换 进基的选择 不符合最大检验数规则 否则x5才是进基变量 二 退化问题中避免基循环的方法 在第2行取得 故x4为离基变量 2 4退化情形的处理 由表2 22可知 只有x5的检验数为正数 故取x5为进基变量 因为最小比值 于是 b25为表2 22的枢元 新基为B6 p3 p5 p1 并将x4换为x5 得新基B6对应的单纯形表 见表2 23 对表2 22作初等行变换 进基的选择也符合 最大检验数规则 二 退化问题中避免基循环的方法 2 4退化情形的处理 最优值为f f x 由表2 23可知 检验数全部非正 故表2 23为最优解表 对应最优解为x 最优解表 二 退化问题中避免基循环的方法 2 4退化情形的处理 由Bland规则 x1为进基变量 对比 由最大检验数规则 x5为进基变量 x3为离基变量 x7为离基变量 采用Bland规则后 目标函数值得到了改善 也不在再现基的循环了 详见表2 20与2 22 二 退化问题中避免基循环的方法 2 4退化情形的处理 对比 二 退化问题中避免基循环的方法 2 4退化情形的处理 虽然Bland法则可避免循环 但一般说来求解LP的迭代效率较低 长期的实际表明 退化经常有 而循环极为罕见 一般方法 用单纯形法求解LP问题时 一般按照2 3节 P37 38 的步骤与规则 最大检验数规则 来进行单纯形迭代 对于退化问题万一遇到循环现象 再改用Bland规则 二 退化问题中避免基循环的方法 说明 2 4退化情形的处理 问题无可行解 当然就没有最优解 有可行解 但是目标函数在可行域上无下界 此时也无最优解 三 线性规划问题LP的解的情况 综合定理2 2至2 7 可得到如下结论 线性规划问题LP 不管是否退化 有且仅有如下三种可能情形 有最优解 且必能在基可行解中找到最优解 可行域为空集 定理2 8 若线性规划问题LP的可行域非空 且目标函数在可行域上有下界 则LP必有最优解 检验数全部 0时为最优解 2 6单纯形法的几何意义 第二章单纯形方法 第二章单纯形方法 在1 3节 图解法 已经得到如下结论 2 6单纯形法的几何意义 1 线性规划的可行域是一个什么形状 多边形 而且是 凸 的多边形 2 最优解在什么位置获得 在边界 而且是在某个顶点获得 这些结论具有普遍意义 对于两个以上变量的线性规划问题也成立 凸集 顶点 基可行解 x 1 2 6单纯形法的几何意义 一 基本概念 1 凸集和凸组合 1 直线段 并称x 1 x 2 为线段的端点 他们分别对应 0与 1 x 2 称线段上其余的点为线段的内点 端点 端点 内点 2 6单纯形法的几何意义 一 基本概念 1 凸集和凸组合 2 凸集 P62定义1 代数定义 凸集的几何意义 是集合中任意两点的连线仍在该集合中 即集中任意两点间的直线段上的所有点都属于该集合 从直观上讲 凸集无凹陷部分 其内部没有洞 凸集 非凸集 线段上的点 例如 凸集 非凸集 2 6单纯形法的几何意义 一 基本概念 凸集的特殊情况 一条线 一个点 空集 两点连线的中的任一点能够表示 如何表示三角形中的任一点呢 如何表示多维空间中的任一点呢 集合中任意两点的连线仍在该集合中 凸组合 2 6单纯形法的几何意义 一 基本概念 1 凸集和凸组合 3 凸组合 P63 直线段中任意一点皆为两端点的凸组合 两个点的凸组合 当时 称向量为x 1 与x 2 的凸组合 k个点的凸组合 设 0 i 1且则称是x 1 x 2 x k 的凸组合 注 凸集 集合中任意两点的凸组合仍然属于此集合 推广 凸集C中任意有限个点的凸组合仍属于C P69第5题 凸组合 凸组合 2 6单纯形法的几何意义 一 基本概念 2 极点 P63 凸集C的极点属于此集合C 但是 顶点 不能表示为C中任意两点的凸组合 只能表示为极点自身的凸组合 即是说 极点不能用不同的两点的连线表示 x 0 1 x 0 x 0 它不能成为C中任何两个不同点的连线的内点 内点 二维平面中的凸集与极点举例 有无数个极点 椭圆周上的点都是极点 1 多边形 2 6单纯形法的几何意义 一 基本概念 2 极点 P63 仅有有限个极点 没有极点 2 闭椭圆域 3 开圆域 4 第一象限 只有一个极点 即坐标原点 2 6单纯形法的几何意义 一 基本概念 3 超平面和闭半空间 1 超平面 2 闭半空间 集合H称为Rn中的超平面 其中 集合H 和H 称为Rn中的闭半空间 其中 即 H 和H 是由超平面H所划分的两个闭半空间 注 超平面H恰为两个闭半空间的交集 即H H H 平面中 超平面实为平面中的直线 而由此超平面所划分的两个闭半空间实为两个半平面 三维空间中 超平面就是通常所说的平面 闭半空间是闭凸集 P69第2题 闭半空间的交集是闭凸集 Rn中有限个闭半空间的交集称为多面凸集 多面凸集的极点又称为顶点 显然 多面凸集是闭凸集 但多面凸集不一定有界 有界的多面凸集称为凸多面体 2 6单纯形法的几何意义 一 基本概念 4 多面凸集和相邻极点 1 多面凸集 2 凸多面体 3 相邻极点 P64 换言之 多面凸集K的两个极点是x 1 x 2 是相邻极点 定义3 设K是Rn中的多面凸集 x 1 x 2 为K的两个极点 如果线段上的任意一点都不可能是K中其他任何线段的内点 则称x