第五章 单纯形法ppt课件VIP

第五章单纯形法 一 问题的提出二 单纯形法的基本思路和原理三 单纯形法的表格形式四 人工变量法五 几种特殊情况 一 问题的提出 图解法只能解决二维的线性规划问题 那更多变量的问题怎么办 jsj 通过代数算法搜寻最优解 单纯形法 就是这样的一种代数搜寻法 线性规划问题的解一般有无穷多个 如果不缩小搜寻范围 工作量太大 我们首先将最优解缩小在一个有限的范围 一 问题的提出 回顾图解法 我们知道 最优解必定在可行域的顶点上取得 而顶点的个数总是有限的 多维线性规划问题的可行域也存在有限个顶点 如果能够从一个顶点开始 通过某种方式向更优顶点转移 总会找到最优点 首先面临的问题 如何通过代数方法找到第一个顶点 一 问题的提出 图解法中的例1 5模型为 Maxz 50 x1 100 x2s t 1 x1 1 x2 3002 x1 1 x2 4000 x1 1 x2 250 x1 0 x2 0 一 问题的提出 从其标准形的解向量开始研究 Maxz 50 x1 100 x2s t 1 x1 1 x2 1 x3 0 x4 0 x5 3002 x1 1 x2 0 x3 1 x4 0 x5 4000 x1 1 x2 0 x3 0 x4 1 x5 250 xj 0 j 1 2 3 4 5 一 问题的提出 顶点对应的解向量有何代数特征 O 0 0 300 400 250 A 0 250 50 150 0 B 50 250 0 50 0 C 100 200 0 0 50 D 200 0 100 0 50 答案 都有两个变量取值为0 且非负 X1 X2 O 0 0 A 0 250 B 50 250 C 100 200 D 200 0 一 问题的提出 既然顶点解向量中有两个变量取值为0 而标准形中又有三个约束方程 是否可以直接通过这种方式找顶点 如令x1 0 x2 0 则x3 300 x4 400 x5 250可得到解 0 0 300 400 250 一 问题的提出 又如 令x3 0 x5 0 由约束条件 x1 x2 x3 3002x1 x2 x4 400 x2 x5 250可得到解 50 250 0 50 0 一 问题的提出 若令x2 0 x5 0 会怎样 由约束方程可知 x1 x2 x3 300 x1 x3 3002x1 x2 x4 400 2x1 x4 400 x2 x5 250 0 250 显然不能得到相应的解 一 问题的提出 为什么令x2 0 x5 0时不能得到解 因为其余三个变量的系数列向量为该矩阵是非可逆矩阵 即去掉x2和x5后的三个约束方程线性相关 这种情况下得不到解 一 问题的提出 既然如此 如果我们在技术矩阵中取出三列 组成一个可逆阵 令其余两列对应的变量为零 则一定可以得到一个解 一 问题的提出 如 取1 2 3列得到 此矩阵为可逆阵 故令x4 0 x5 0 一定可以得到一个解 对应的解为 75 250 25 0 0 一 问题的提出 基的概念 已知A是约束条件的m n阶系数矩阵 其秩为m 设B是A矩阵中的一个非奇异 可逆 的m m阶子矩阵 则称B为线性规划问题的一个基 B由A中的m个线性无关列向量组成 一 问题的提出 一个基对应一组概念 非基变量 基变量 基向量 非基向量 对应基本解 0 0 300 400 250 一 问题的提出 0 0 300 400 250 0 300 0 100 50 0 400 100 0 150 0 250 50 150 0 300 0 0 200 50 200 0 100 0 50 不存在 100 200 0 0 50 50 250 0 50 0 75 250 25 0 0 基本解 是 x3 x5 p3 p5 x1 x2 x4 p1 p2 p4 B2 p1 p2 p4 是 x3 x4 p3 p4 x1 x2 x5 p1 p2 p5 B3 p1 p2 p5 是 x1 x2 p1 p2 x3 x4 x5 p3 p4 p5 B10 p3 p4 p5 否 x1 x3 p1 p3 x2 x4 x5 p2 p4 p5 B9 p2 p4 p5 否 x1 x4 p1 p4 x2 x3 x5 p2 p3 p5 B8 p2 p3 p5 是 x1 x5 p1 p5 x2 x3 x4 p2 p3 p4 B7 p2 p3 p4 否 x2 x3 p2 p3 x1 x4 x5 p1 p4 p5 B6 p1 p4 p5 是 x2 x4 p2 p4 x1 x3 x5 p1 p3 p5 B5 p1 p3 p5 x2 x5 p2 p5 x1 x3 x4 p1 p3 p4 B4 p1 p3 p4 否 x4 x5 p4 p5 x1 x2 x3 p1 p2 p3 B1 p1 p2 p3 是否可行 非基变量 非基向量 基变量 基向量 基 一 问题的提出 基本解可能可行 也可能不可行 满足非负约束条件的基本解叫基本可行解 相应的基称为可行基 否则为非可行基 一 问题的提出 A 0 250 50 150 0 B 50 250 0 50 0 C 100 200 0 0 50 D 200 0 100 0 50 O 0 0 300 400 250 E 75 250 25 0 0 F 0 300 0 100 50 G 0 400 100 0 150 H 300 0 0 200 50 一 问题的提出 线性规划解的集合关系 基本解 最优解 基本可行解 可行解 一 问题的提出 显然 将搜索范围控制在基本可行解内 将大大减少搜索工作量 但是 即使取得一个基 得到的解还不一定可行 如何才能保证取得一个可行基呢 一 问题的提出 总结 1 可行域顶点对应的解必为基本可行解 有n m个变量取值为0 满足非负条件 2 一个基对应一组基本解 可能可行 也可能不可行 3 最优解必定在基本可行解中 二 单纯形法的基本思路和原理 单纯形法的基本思路 首先找到一个顶点 然后判断它是否最优 如果不是 则通过更换顶点的方式找到更优的顶点 直到找到最优顶点 二 单纯形法的基本思路和原理 第一步 找到一个顶点 初始基本可行解 二 单纯形法的基本思路和原理 思考 1 令n m个变量为0 非基变量 是否一定可以找到 答案 不一定 如例中x2 0 x5 0时不能得到解 可行的办法 找到一个基 二 单纯形法的基本思路和原理 2 一个基是否一定对应可行域顶点 答案 不一定 必须是可行基 一般来说 判断一个基是否是可行基 需要在求出其基本解后才能判断 二 单纯形法的基本思路和原理 3 那有没有办法在求出解之前保证我们取得的基为可行基 解决办法 保证右端项非负 找到一个单位矩阵 必定是一个可行基 二 单纯形法的基本思路和原理 如范例系数阵 存在3阶单位阵 初始可行基 右端项非负 二 单纯形法的基本思路和原理 基本可行解为 0 0 300 400 250 此可行基称为初始可行基 对应的解称为初始基本可行解 初始基本可行解在上页矩阵中一目了然 二 单纯形法的基本思路和原理 第二步 最优性检验 二 单纯形法的基本思路和原理 对应于每一组基本解 目标函数都可以表示成非基变量的函数 称为典式 如 初始基本可行解 0 0 300 400 250 其非基变量为x1 x2目标函数为Maxz 50 x1 100 x2 二 单纯形法的基本思路和原理 典式Z 50 x1 100 x2如果x1增加1 Z会怎样 答案 Z增加50 如果x2的值增加1 Z会怎样 答案 Z增加100 二 单纯形法的基本思路和原理 x1 x2的取值是否有增加的可能 分析 该解中非基变量x1 x2的取值为0 其值完全有可能增加 说明此时目标函数值还有增加的可能 没有达到最优 二 单纯形法的基本思路和原理 再如 基本解 50 250 0 50 0 其非基变量为x3 x5由约束方程可得 x1 50 x3 x5x2 250 x5目标函数为Maxz 50 x1 100 x2 27500 50 x3 50 x5 二 单纯形法的基本思路和原理 典式Z 27500 50 x3 50 x5如果x3增加1 Z会怎样 答案 Z减少50 如果x5的值增加1 Z会怎样 答案 Z减少50 可见要使Z增加 只有使x3和x5减少 二 单纯形法的基本思路和原理 x3 x5的取值是否有减少的可能 分析 该解中非基变量x1 x2的取值为0 其值不可能再减少 所以Z值不可能再增加 说明此基本解对应的目标函数值已经达到最优 二 单纯形法的基本思路和原理 由以上分析 可见 完全可以由典式中的系数来判断解是否最优 如 Z 50 x1 100 x2系数 0 未达到最优 Z 27500 50 x3 50 x5系数 0 达到最优 这些系数我们称为检验数 二 单纯形法的基本思路和原理 检验数的概念 若只用非基变量来表示目标函数 将所有基变量从目标函数中用非基变量替换出去 此时目标函数中各非基变量的系数即为各非基变量的检验数 把变量xj的检验数记为 j 显然基变量的检验数为0 二 单纯形法的基本思路和原理 最优解判别准则 对于求最大目标函数的问题中 对于某个基本可行解 若所有检验数 j 0 则这个基本可行解是最优解 对于求最小目标函数的情况 当所有非基变量检验数 j 0时 目标值最优 对应的基本可行解为最优解 二 单纯形法的基本思路和原理 第三步 基变换 二 单纯形法的基本思路和原理 在保证右端常数项非负前提下 基变量与非基变量互换 换基 使检验数由正 非最优 变为非正 最优 为了换基 就要合理的确定进基变量和出基变量 二 单纯形法的基本思路和原理 进基变量的确定 最大检验数原则 确保目标值增加最快 例中初始解 1 50 2 100 则选x2入基 二 单纯形法的基本思路和原理 出基变量的确定 最小比值原则min 300 1 400 1 250 1 250 x5出基 以进基变量系数列中的正数为分母 以相应的方程右端常数为分子 系数为0和负不考虑 二 单纯形法的基本思路和原理 范例中 确定了x2为入基变量后 把约束方程1 x1 1 x2 1 x3 0 x4 0 x5 3002 x1 1 x2 0 x3 1 x4 0 x5 4000 x1 1 x2 0 x3 0 x4 1 x5 250中入基变量x2的正系数除以对应的右端常数 得b1 a12 300 1 300b2 a22 400 1 400b3 a32 250 1 250其中b3 a32的值最小 故确定原基变量中第三个约束方程中的基变量x5为出基变量 二 单纯形法的基本思路和原理 得到新的基 p2 p3 p4 令x1 x5 0 得x2 x3 300 x2 x4 400 x2 250求得新的基本可行解 0 250 50 150 0 目标函数值z 50 x1 100 x2 50 0 100 250 25000目标函数值得到了改进 思考 若不按最小比值法确定出基变量会怎么样 请大家计算一下 若在第一次迭代中不选x5出基 而让x3或x4出基 会出现什么情况 二 单纯形法的基本思路和原理 若让x3出基 则新的基为 p2 p4 p5 求得解为 0 300 0 100 50 非可行 若让x4出基 则新的基为 p2 p3 p5 求得解为 0 400 100 0 150 非可行 结论 按最小比值原则确定出基变量 可确保解可行 二 单纯形法的基本思路和原理 事实上 若取得的基不是单位阵 也可以通过初等行变换 将其化为单位阵 如基 p1 p2 p4 二 单纯形法的基本思路和原理 显然 该基本解为 50 250 0 50 0 二 单纯形法的基本思路和原理 如此迭代直到所有检验数均非正 则找到了线性规划问题的最优解 二 单纯形法的基本思路和原理 单纯形法求解思路总结 第一步找到初始可行基 单位阵 第二步检验解是否为最优 所有检验数 0 第三步基变换 最大检验数原则确定进基变量 最小比值原则确定出基变量 重复以上步骤直到得到最优解 三 单纯形法的表格形式 0 Z 0 250 1 0 x5 400 1 0 x4 300 1 0 x3 比值bi ai2 CB 基变量XB 迭代次数 单纯形表的基本结构 以范例的初始表为例 三 单纯形法的表格形式 表格形式可以使求解过程更简洁明了 但需要先从一般数学模型里推导出检验数的表达式和每个解对应的目标函数值 下面以例说明检验数和目标函数值公式的推导过程 三 单纯形法的表格形式 将范例线性规划模型表示为maxZ c1x1 c2x2 c3x3 c4x4 c5x5假设基变量为x1 x2 x3 基为单位矩阵 则约束条件可以表示为x1 a 14x4 a 15x5 b 1x2 a 24x4 a 25x5 b 2x3 a 34x4 a 35x5 b 3 三 单纯形法的表格形式 则Z c1b 1 c2b 2 c3b 3 c4 c1a 14 c2a 24 c3a 34 x4 c5 c1a 15 c2a 25 c3a 35 x5基本解对应的目标值为 c1b 1 c2b 2 c3b 3 检验数 1 2 3 0 4 c4 c1a 14 c2a 24 c3a 34 c4 c1a 14 c2a 24 c3a 34 5 c5 c1a 15 c2a 25 c3a 35 c5 c1a 15 c2a 25 c3a 35 三 单纯形法的表格形式 检验数的一般表达式为 j cj zj其中zj c1a 1j c2a 2j cma mj 每个解对应的目标函数值 z c1b1 c2b2 cmbm 非基变量xj的目标函数系数 第一个约束方程中基变量的目标函数系数 第一个约束方程中非基变量xj的技术系数 三 单纯形法的表格形式 观察系数矩阵和基变量的目标函数系数 找到规律 计算检验数变得更直观 三 单纯形法的表格形式 对于范例 其系数矩阵和基变量的目标函数系数 故目标函数值Z 0 300 0 400 0 250 z1 0 1 0 2 0 0 1 c1 z1 50 0 三 单纯形法的表格形式 0 Z 0 0 0 0 100 50 j cj zj 0 0 0 0 0 zj 250 1 0 x5 400 1 0 x4 300 1 0 x3 比值bi ai2 CB 基变量XB 迭代次数 主元 迭代 将主列变为单位列向量 办法 在其它行上加上主行的若干倍 使主元变为1 主列其它元素变为0 最大检验数 最小比值 三 单纯形法的表格形式 1 100 0 0 0 50 j cj zj 25000 100 0 0 100 0 zj 100 x2 150 2 0 x4 50 1 0 x3 检验数还有正数 故还需进一步迭代 三 单纯形法的表格形式 2 50 0 50 0 0 j cj zj 27500 50 0 50 100 50 zj 100 x2 0 x4 50 x1 所有检验数均非正 已求得最优解 三 单纯形法的表格形式 课堂练习用单纯形法求解 第五章习题 第5题 1 三 单纯形法的表格形式 0 0 0 5 8 12 j 0 0 0 0 0 0 0 Zj 4 48 1 0 0 1 4 12 0 x6 11 11 0 1 0 1 1 1 0 x5 20 3 20 0 0 1 1 2 3 0 x4 0 0 0 0 5 8 12 比值 b x6 x5 x4 x3 x2 x1 cB xB 迭代次数 三 单纯形法的表格形式 1 0 0 4 4 0 j 48 1 0 0 1 4 12 Zj 12 4 1 12 0 0 1 12 1 3 1 12 x1 21 2 7 1 12 1 0 11 12 2 3 0 0 x5 8 8 1 4 0 1 3 4 1 0 0 x4 1 0 0 0 5 8 12 比值 b x6 x5 x4 x3 x2 x1 cB xB 迭代次数 三 单纯形法的表格形式 0 0 4 1 0 0 j 80 0 0 4 4 8 12 Zj 4 3 1 6 0 1 3 1 6 0 1 12 x1 4 5 3 1 12 1 2 3 5 12 0 0 0 x5 32 3 8 1 4 0 1 3 4 1 0 8 x2 2 0 0 0 5 8 12 比值 b x6 x5 x4 x3 x2 x1 cB xB 迭代次数 三 单纯形法的表格形式 1 5 12 5 12 5 0 0 0 j 84 1 5 12 5 12 5 5 8 12 Zj 2 1 5 2 5 3 5 0 0 1 12 x1 4 1 5 12 5 8 5 1 0 0 5 x3 5 2 5 9 5 11 5 0 1 0 8 x2 3 0 0 0 5 8 12 比值 b x6 x5 x4 x3 x2 x1 cB xB 迭代次数 四 人工变量法 例 LP问题的标准型Maxz 5x1 2x2 3x3 x4s t x1 2x2 3x3 152x1 x2 5x3 20 x1 2x2 4x3 x4 26x1 x2 x3 x4 0问题 如何找到初始可行基 四 人工变量法 解决办法 构造初始可行基 人工变量 四 人工变量法 实际上 构造问题的约束条件为 s t x1 2x2 3x3 x5 152x1 x2 5x3 x6 20 x1 2x2 4x3 x4 26x1 x2 x3 x4 x5 x6 0 四 人工变量法 构造初始基为 p4 p5 p6 非基变量为x1 x2 x3 初始解为 0 0 0 26 15 20 出现新的问题 0 0 0 26 是否是原问题的解 四 人工变量法 显然 原问题的约束方程和构造问题的约束方程一般情况下不同解 只有一种情况下 两者同解 人工变量都为0时 事实上 不管中间过程如何 只要构造问题的最优解中人工变量为0 该最优解也就是原问题的最优解 四 人工变量法 为迫使构造问题的最优解中人工变量为0 将其目标函数表示为 Maxz 5x1 2x2 3x3 x4 Mx5 Mx6 罚因子 M为足够大的正数 四 人工变量法 此法称为 大M法 大M法求解实例 四 人工变量法 0 0 0 8M 7 3M 4 3M 6 j 35M 26 M M 1 8M 4 3M 2 3M 1 Zj 6 5 26 0 0 1 4 2 1 1 x4 4 20 1 0 0 5 1 2 M x6 5 15 0 1 0 3 2 1 M x5 0 M M 1 3 2 5 比值 b x6 x5 x4 x3 x2 x1 cB xB 迭代次数 四 人工变量法 8M 5 7 5 0 0 0 7M 5 13 5 M 5 16 5 j 3M 2 3M 5 7 5 M 1 3 7M 5 3 5 M 5 9 5 Zj 25 3 10 4 5 0 1 0 6 5 3 5 1 x4 20 4 1 5 0 0 1 1 5 2 5 3 x3 15 7 3 3 5 1 0 0 7 5 1 5 M x5 1 M M 1 3 2 5 比值 b x6 x5 x4 x3 x2 x1 cB xB 迭代次数 四 人工变量法 M 2 7 M 13 7 0 0 0 25 7 j 53 7 2 7 13 7 1 3 2 10 7 Zj 52 7 2 7 6 7 1 0 0 3 7 1 x4 25 3 25 7 2 7 1 7 0 1 0 3 7 3 x3 15 7 3 7 5 7 0 0 1 1 7 2 x2 2 M M 1 3 2 5 比值 b x6 x5 x4 x3 x2 x1 cB xB 迭代次数 四 人工变量法 M 8 3 M 2 3 0 25 3 0 0 j 112 3 8 3 2 3 1 34 3 2 5 Zj 11 0 1 1 1 0 0 1 x4 25 3 2 3 1 3 0 7 3 0 1 5 x1 10 3 1 3 2 3 0 1 3 1 0 2 x2 3 M M 1 3 2 5 比值 b x6 x5 x4 x3 x2 x1 cB xB 迭代次数 四 人工变量法 原问题最优解 25 3 10 3 0 11 最优目标值 112 3若人工变量在罚因子的作用下最终不能出基 即构造问题的最优解中人工变量取值不为0 则原问题无可行解 四 人工变量法 罚因子的引入 使计算变得复杂 在构造初始基后 还有一种求解办法 两阶段法 第一阶段 使人工变量出基 找到一个原问题的可行解 第二阶段 从找到的可行解继续原问题的迭代 找到最优解 四 人工变量法 如上例 构造第一阶段的目标函数 Maxz x5 x6约束条件同样为s t x1 2x2 3x3 x5 152x1 x2 5x3 x6 20 x1 2x2 4x3 x4 26x1 x2 x3 x4 x5 x6 0 四 人工变量法 解第一阶段问题 四 人工变量法 四 人工变量法 得到原问题的一个基本可行解 0 15 7 25 7 52 7 四 人工变量法 第二阶段 把基本可行解填入表中 四 人工变量法 故最优解 25 3 10 3 0 11 最优值 112 3 课堂练习 第98页第6题 用大M法或两阶段法求解 找得到进基变量 却找不到出基变量 此为无界解情况 五 几种特殊情况 1 无可行解若LP问题的最终解里有人工变量大于0 则此LP问题无可行解 例如 某LP问题经两次迭代 得到如下单纯形表 五 几种特殊情况 五 几种特殊情况 表中所有检验数都小于或等于零 可见目标函数值不可能再增加 但此时人工变量a1没有出基 其取值为4 故原线性规划问题无可行解 五 几种特殊情况 2 无界解在某次迭代中 若存在一个大于0的检验数 j 而该列的系数aij i 1 2 m 都小于或等于0 则此线性规划问题无界 五 几种特殊情况 只有x2的检验数大于0 但ai2均小于0 此线性规划问题为无界解情况 五 几种特殊情况 3 无穷多最优解一般情况下 达到最优时 基变量的检验数等于0 非基变量的检验数小于0 如果最优表中 有非基变量的检验数等于零 则有无穷多最优解 例如 五 几种特殊情况 已最优 但非基变量x5的检验数为0 可以判断此LP问题有无穷多最优解 五 几种特殊情况 将检验数为0的非基变量x5选为入基变量进行迭代 可得另一个最优解 五 几种特殊情况 第一组最优解X1 50 250 0 50 0 第二组最优解X2 100 200 0 0 50 事实上 其余的最优解都可以表示为X1和X2的线性组合 aX1 1 a X2 其中0 a 1 最优值为15000 五 几种特殊情况 4 进基变量的相持及其突破单纯形法中进基变量的确定是以 最大检验数原则 如果两个或者多个检验数同时最大 应该选择哪个变量进基 解决办法 选择下标最小者 五 几种特殊情况 选择下标小的