3_5单纯形算法和表

图解法的启示 解的情况 唯一解 无穷多解 无界解 无可行解可行域是凸多边形 有界或无界 最优解在凸多边形的顶点处达到 1947年美国数学家丹捷格 G B Dantzig 提出了求解线性规划问题的方法 单纯形法 线性规划之父 3 1线性规划的基本定理 例 考虑下列多面集 x1 x1 x2 x3 x5 线性规划问题解的概念和性质 一 LP问题的各种解 可行解 满足约束条件和非负条件的决策变量的一组取值 最优解 使目标函数达到最优值的可行解 基本解 基本解 基本解 设AX b是含n个决策变量 m个约束条件的LP的约束方程组 B是LP问题的一个基 若令不与B的列相应的n m个分量 非基变量 都等于零 所得的方程组的解称为方程组AX b关于基B的基本解 简称为LP的基本解 基本可行解 满足非负条件的基本解 如果基变量中至少有一个分量为0 则该基本可行解是退化的 可行基 对应于基本可行解的基 第一步模型标准化 第二步按照基本解的定义 找基 多少个 不超过 确定基变量和非基变量 令非基变量为0 解出基变量 基变量和相应非基变量搭配构成基本解 定理3 3 必要性 由基本可行解定义直接证得充分性 不妨设X的前k个分量 0 则P1 Pk线性无关 X即为基本可行解 补齐得基 X即为退化的基本可行解 必要性 定理3 3之证明 反证法 充分性 X x1 xk 0 0 T不是极点 xj 0 矛盾 X不是基本可行解 引理 定理3 3之证明 续 定理3 2设线性规划的可行集非空 若该线性规划有有限最优解 则其最优值可在某个基本可行解上达到 有基本可行解最优解能达到 1 存在性 可行域非空 不妨设前k个非零 其他都为零 1 若P1 Pk线性无关 2 若P1 Pk线性相关 选取适当小的使得且至少有一个取等号 或 非零分量至少比x0少一个 若仍不是基本可行解 则如上继续进行 当只有一个非零分量时 该分量所对应的列向量一定是线性无关的 要证明的是设在非顶点x0处取得最优值 则存在顶点x 1 或x 2 也取得相同的最优值 2 最优解在极点处达到 定理 若目标函数在k 2 个点处达到最优值 则在这些极点的凸组合上也达到最优值 上述3个定理的一些有意义的启示 在可行域中寻找LP的最优解可以转化为只在可行域的极点中找 从而把一个无限的问题转化为一个有限的问题 线性规划的基本可行解和可行域的极点是一一对应的 类似于坐标与点的对应关系 若已知一个LP有两个或两个以上最优解 那么就一定有无穷多个最优解 3 2单纯形算法和单纯形表 例3 7 单纯形法的基本思想 极点 极点 极点 1 Fromwhere 初始 2 why how 为什么转移 怎么转移 3 Towhere 结束 解LP问题单纯形法的基本思路 初始可行基 设法在约束矩阵中构造出一个m阶单位阵 2 判别准则 检验数 进基变量 检验数离基变量 最小比值准则 1 确定初始基本可行解 LP标准化 A中含有一个m阶单位阵 例3 7 2 建立判别准则 判断 初始基本可行解或经过若干次迭代后得到的新基本可行解是否为最优解 对于基B 用非基变量表示基变量的表达式为 用非基变量表示目标函数的表达式 检验数 例3 7 之一 min max 最优性判别定理 之二 有无穷多个 最优解 的判别定理 判别准则 3 进行基变换 1 进基变量的确定 原则 正检验数 或最大正检验数 所对应的变量进基 目的是使目标函数得到改善 2 离基变量的确定 在保持解的可行性的前提下 使目标函数较快增大 当时 为使 需要 最大可取到 最小比值原则 离基变量 可行解 基本解 例3 7 目标函数得到了改善 用单纯形法从当前解迭代到下一个基本可行解时 两者之间只有一个基变量不同 从而也有一个非基变量不同 称两者为相邻的基本可行解 即相邻的顶点 定义 单纯形表 例3 7 建立初始单纯形表 假定B I b 0设minz c1x1 c2x2 cnxn 将目标函数改写为 z c1x1 c2x2 cnxn 0 初始单纯形表 基变换 新的单纯形表 作业 P1455 1 2 3 2 3启动机制 以X 0 作初始基本可行解进行迭代时 怎样才能较快地将所有的人工变量从基变量中全部 赶 出去 如果能全部 赶 出去的话 这会影响到得到最优解的迭代次数 大M法与两阶段法 一 大M法 M是一个很大的正数 将目标函数修改为 例 用大M法求解LP 解 引入松弛变量 剩余变量和人工变量将问题标准化 得 以对应的系数列向量构成一单位矩阵 取初始基为基变量 为非基变量 初始单纯形表 确定为进基变量 而为离基变量 以为主元素 基变换 调基 最优解 4 1 9 0 0 0 0 T 最优值 2 新LP最优解的情况 人工变量 0全部为非基变量 原LP有最优解有些为基变量 该人工变量与非基变量替换 得原LP最优解人工变量 0 原LP无可行解 大M法的不足 在用计算机求解时 不容易确定M的取值 且M过大容易引起计算误差 二 两阶段法 将新LP的求解过程分成两个阶段 第一阶段 求解第一个LP 原LP 辅助LP 原LP的可行域 D辅助LP的可行域 D 目的 通过解辅助LP来获得原LP的初始解 辅助LP的结果有三种可能情形 1 最优值 人工变量皆为非基变量 去掉人工变量后 得原LP的一个基本可行解 进入第二阶段 2 最优值 说明至少有一个人工变量不为零 原LP无可行解 不再需要进入第二个阶段计算 存在人工变量为基变量 但取值为零 把某个非基变量与该人工