运筹学5-单纯形法ppt课件

第五章单纯形法 1 线性规划问题的解2单纯形法3求初始基的人工变量法 1 线性规划问题的解 1 解的基本概念 定义在线性规划问题中 约束方程组 2 的系数矩阵A 假定 的任意一个阶的非奇异 可逆 的子方阵B 即 称为线性规划问题的一个基阵或基 基阵 非基阵 基向量 非基向量 基变量 非基变量 令 则 定义在约束方程组 2 中 对于一个选定的基B 令所有的非基变量为零得到的解 称为相应于基B的基本解 定义在基本解中 若该基本解满足非负约束 即 则称此基本解为基本可行解 简称基可行解 对应的基B称为可行基 定义在线性规划问题的一个基本可行解中 如果所有的基变量都取正值 则称它为非退化解 如果所有的基本可行解都是非退化解 称该问题为非退化的线性规划问题 若基本可行解中 有基变量为零 则称为退化解 该问题称为退化的线性规划问题 基本解中最多有m个非零分量 基本解的数目不超过个 非可行解 解的集合 可行解 基本解 最优解 基本可行解 解空间 2 解的基本性质 判别可行解为基可行解的准则 定理1线性规划问题的可行解是基可行解的充要条件是它的非零向量所对应的列向量线性无关 线性规划问题的基本定理 定理2和定理3 定理2线性规划问题有可行解 则它必有基可行解 定理3若线性规划问题有最优解 则一定存在一个基可行解是它的最优解 几点结论 若线性规划问题有可行解 则可行域是一个凸多边形或凸多面体 凸集 且仅有有限个顶点 极点 线性规划问题的每一个基可行解都对应于可行域上的一个顶点 极点 若线性规划问题有最优解 则最优解必可在基可行解 极点 上达到 线性规划问题的基可行解 极点 的个数是有限的 不会超过个 上述结论说明 线性规划的最优解可通过有限次运算在基可行解中获得 2单纯形法 例1 1 单纯形法的引入 解 1 确定初始可行解 B P3P4P5 I 令X1 X2 0 X 1 0 0 30 60 24 TZ 1 0 2 判定解是否最优 Z 0 40X1 50X2当X1从0 或X2从0 Z从0 X 1 不是最优解 3 由一个基可行解 另一个基可行解 50 40选X2从0 X1 0 X2 min 30 2 60 2 24 2 12X2 进基变量 X5 出基变量 B2 P3P4P2 1 2 代入 式 令X1 X5 0X 2 0 12 6 36 0 TZ 2 600 2 判断 40 0 X 2 不是最优解 3 选X1从0 X5 0 X1 min 6 1 36 3 6X1进基 X3出基 B3 P1P4P2 令X3 X5 0X 3 6 12 0 18 0 TZ 3 840 2 15 0 X 3 不是 3 选X5从0 X3 0 X5 min 18 2 12 1 2 9X5进基 X4出基 B4 P1P5P2 令X3 X4 0X 4 15 15 2 0 0 9 TZ 4 975 0 0 0 X2 X1 X 4 X 1 X 2 X 3 Z 40X1 50X2 单纯形法小结 单纯形法是这样一种迭代算法 如下图 当Zk中非基变量的系数的系数全为负值时 这时的基本可行解Xk即是线性规划问题的最优解 迭代结束 X1 Z1 保持单调增 保持可行性 保持可行性 保持可行性 保持可行性 保持单调增 保持单调增 保持单调增 X2 X3 Xk Z2 Z3 Zk 当Zk中非基变量的系数全为负值时 这时的基本可行解Xk即是线性规划问题的最优解 迭代结束 2 线性规划的典则形式 标准型 3 最优性判别定理 在线性规划问题的典式中 设X 0 x1 x2 xm 0 0 为对应于基B的一个基可行解 若有 j 0 j m 1 m 2 n 则X 0 是线性规划问题的最优解 基B为最优基 证 设X为线性规划问题的一个可行解 必有X 0 当 j 0 则 X 0Z CX 0 Z 0 Z 0 X CX故X 0 为线性规划问题的最优解 在线性规划问题的典式中 设X 0 x1 x2 xm 0 0 为对应于基B的一个基可行解 若有 j 0 j m 1 m 2 n 且 j k 0则线性规划问题有无穷多个最优解 无穷多最优解判别定理 在线性规划问题的典式中 设X 0 为对应于基B的一个基可行解 若某一非基变量xj k的检验数 j k 0且对应的列向量P m k a1 m k a2 m k am m k 0则线性规划问题具有无界解 即无有限最优解 无界解判别定理 4 基可行解改进定理 在线性规划问题的典式中 设X 0 x1 x2 xm 0 0 为对应于基B的一个基可行解 若满足以下条件 某个非基变量的检验数 k 0 m 1 k n aik i 1 2 m 不全小于或等于零 即至少有一个aik 0 1 k m bi 0 I 1 2 m 即X 0 为非退化的基可行解 则从X 0 出发 一定能找到一个新的基可行解X 1 使得CX 1 CX 0 5 单纯形表 将线性规划问题典式中各变量及系数填写在一张表格中 该表即为单纯形表 单纯形方法的矩阵表示 对应I式的单纯形表 I表 初始单纯形表 对应B式的单纯形表 B表 迭代 当CN CBB 1N 0时 即为最优单纯形表 1 确定初始基域初始基本可行解 列出初始单纯形表 3 若有 j 0 Pj全 0 停止 没有有限最优解 否则转 4 2 对应于非基变量检验数 j全小于零 若是 停止 得到最优解 若否 转 3 6 单纯形法的迭代步骤 定Xr为出基变量 arm k为主元 由最小 比值法求 Max j m k Xm k进基变量 j 0 4 转 2 5 以arm k为中心 换基迭代 从步骤 2 5 的每一个循环 称为一次单纯形迭代 单纯形表计算步骤举例给定线性规划问题 初始基 最优单纯形表 B 1 初始基可行解 最优值 初始单纯形表 唯一最优解 例2 达到最优状态时 若存在非基变量为零 则为有无穷多最优解 例3 可以为零 例4 例5 无法获得初始基和初始基可行解 3求初始基的人工变量法 求解线性规划问题的单纯形法第一步就是要找到一个初始可行基并求出初始基可行解 以它作为迭代的起点 获得初始可行基及初始基可行解的途径主要有 1 试算法 2 人工变量法 在约束方程组中的每一个没有单位向量的约束方程中人为加入一个变量 使系数矩阵中凑成一个单位方阵 以形成一个初始可行基阵 约束条件 a11x1 a12x2 a1nxn xn 1 b1a21x1 a22x2 a2nxn xn 2 b2 am1x1 am2x2 amnxn xn m bmx1 x2 xn xn 1 xn m 0 s t 人工变量 人工基 等价否 大M法 两阶段法 大M法与二阶段法的一些说明由于人工变量在原问题的解中是不能存在的 应尽快被迭代出去 因此人工变量在目标函数中对应的价值系数应具有惩罚性 称为罚系数 大M法实质上与原单纯型法一样 M可看成一个很大的常数人工变量被迭代出去后就不会再成为基变量当检验数都满足最优条件 但基变量中仍有人工变量 说明原线性规划问题无可行解大M法手算很不方便 因此提出了二阶段法计算机中常用大M法二阶段法手算可能容易 例6 大M法 最优解 人工变量被迭代出去后就不会再成为基变量 例4 未达到最优状态 但无法继续改进 即无有限最优解 例5 已达到最优状态 但基变量中的人工变量未退出 故无可行解