线性规划的图解法与单纯形解法.ppt

运筹学OperationsResearch 吴清烈 东南大学经济管理学院电子商务系暨管理工程研究所02583795358wql 线性规划的图解法与单纯形解法 线性规划问题的图解法线性规划单纯形解法的原理线性规划单纯形解法的计算步骤单纯形法计算的矩阵描述线性规划单纯形求解的大M法线性规划单纯形求解的两阶段法线性规划单纯形求解可能的循环现象线性规划单纯形法的改进 线性规划问题的图解法 图解法 就是用作图的方法求解线性规划问题 简单 直观的图解法一般只适用于具有两个决策变量的线性规划问题 用图解法求解实际线性规划问题 一般按照如下基本步骤 Step1画直坐标系 Step2根据约束条件画出可行域 Step3画过坐标原点的目标函数线 Step4确定目标函数值的增大方向 目标函数线法线方向 Step5目标函数线沿着增大方向平行移动 与可行域相交且有最大目标函数值的顶点 即为线性规划问题的最优解 线性规划问题的图解法举例 maxz 2x1 x2 3x1 x2 12x1 x2 5x2 3x1 x2 0 线性规划问题求解的几种可能结局 存在唯一最优解 如上例 存在无穷多个最优解 如在上例中 将目标函数改为maxz 3x1 x2 这时Q1与Q2以及Q1与Q2之间的所有点均为最优解 存在无界解 有可行解但无有界最优解 如在上例中 只含有x2 3一个约束 可行域为无界 z的取值可无穷大 无解或无可行解 如下述线性规划问题maxz 2x1 x2x1 x2 2 x1 x2 5x1 x2 0 约束条件矛盾 因而无可行解 由图解法得到的启示 线性规划问题求解的基本依据是 线性规划问题的最优解总可在可行域的顶点中寻找 寻找线性规划问题的最优解只需比较有限个顶点处的目标函数值 线性规划问题求解时可能出现四种结局 唯一最优解 无穷多个最优解 无有界解 无解或无可行解 如果某一线性规划问题有最优解 我们可以按照这样的思路来求解 先找可行域中的一个顶点 计算顶点处的目标函数值 然后判别是否有其它顶点处的目标函数值比这个顶点处的目标函数值更大 如有 转到新的顶点 重复上述过程 直到找不到使目标函数值更大的新顶点为止 线性规划单纯形解法的原理 单纯形方法的基本思想从可行域中的一个基可行解出发 判别它是否已经是最优解 如不是 寻找下一个基可行解 并且同时努力使目标函数得到改进 如此迭代下去 直到找到最优解或判定问题无解为止 单纯形算法必须解决三个方面的问题 1 如何确定初始的基可行解 2 如何进行解的最优性判别 3 如何寻找改进的基可行解 确定初始的基可行解 标准型的线性规划问题 系数矩阵中存在一个单位阵 以单位阵为一初始可行基 令非基变量取值为零 便得到一基可行解 最优性检验和解的判别 对标准型的一般线性规划问题 经过变换 迭代总可将线性规划约束条件中非基变量移至 方程右边 得如下形式 最优性检验和解的判别 将上式代入目标函数式中 整理得 令 最优性检验和解的判别 再令 称为检验数 在线性规划模型中 可以用检验数替代目标函数中的价值系数cj 最优解的判别定理 定理1最优解的判别定理 定理2有无穷多最优解的判别定理 最优解的判别定理 定理3有无界解的判别定理 寻找改进的基可行解 当检验某个基可行解不是最优 也非无界 那么就应该从该顶点 基可行解 处出发 寻找一个新的能使目标函数值改进的相邻顶点 基可行解 注 称两个基可行解为相邻的 是指它们之间变换且仅变换一个基变量 具体的方法是 在基变量中 选出一个 让它变为非基变量 同时 从非基变量中 选出一个 让它变为基变量 从而构造一个新基 我们希望 每变换一次 就得到一个新的基可行解 并且是尽可能使目标函数值改进的基可行解 换入变量的确定 如果存在多个 j 0 则取 假定存在一个 我们取 为换入变量 换出变量的确定 换出变量的确定 若 我们选 为换出变量 寻找改进的基可行解 可以证明 x1 x2 xl 1 xl 1 xm xm k 所对应的m个列向量P1 P2 Pl 1 Pl 1 Pm Pm k线性无关 因而B P1 P2 Pl 1 Pl 1 Pm Pm k 是一个新基 最佳换入换出变量确定 单纯形表 单纯形算法的计算步骤 将线性规划问题化成标准型 找出或构造一个m阶单位矩阵作为初始可行基 建立初始单纯形表 计算各非基变量xj的检验数 j 若所有 j 0 则问题已得到最优解 停止计算 否则转入下步 在大于0的检验数中 若某个 k所对应的系数列向量Pk 0 则此问题是无界解 停止计算 否则转入下步 根据max j j 0 k原则 确定xk为换入变量 进基变量 再按 规则计算 min bi aik aik 0 bl aik确定xl为换出变量 建立新的单纯形表 此时基变量中xk取代了xl的位置 以aik为主元素进行迭代 把xk所对应的列向量变为单位列向量 即aik变为1 同列中其它元素为0 转第 步 单纯形算法计算举例 单纯形法计算举例 P1P2P3P4P5b 单纯形法计算举例 单纯形法计算举例 单纯形法计算举例 单纯形法计算的矩阵描述 单纯形法计算的矩阵描述 单纯形法计算的矩阵描述 单纯形法计算的矩阵描述 单纯形法计算的矩阵描述 单纯形法计算的矩阵描述 单纯形法计算的矩阵描述 线性规划求解的人工变量法 人工变量法引用人工变量是用单纯形法求解线性规划问题时解决可行解问题的常用方法 人工变量法的基本思路是 若原线性规划问题的系数矩阵中没有单位向量 则在每个约束方程中加入一个人工变量便可在系数矩阵中形成一个单位向量 由于单位阵可以作为基阵 因此 可选加入的人工变量为基变量 然后 再通过基变换 使得基变量中不含非零的人工变量 如果在最终单纯形表中还存在非零的人工变量 这表示无可行解 线性规划求解的人工变量法 线性规划求解的人工变量法 为了使加入人工变量后线性规划问题的最优目标函数值不受影响 我们赋予人工变量一个很大的负价值系数 M M为任意大的正数 由于人工变量对目标函数有很大的负影响 单纯形法的寻优机制会自动将人工变量赶到基外 从而找到原问题的一个可行基 这种方法我们通常称其为大M法 线性规划求解的大M法 线性规划求解的大M法 线性规划求解的大M法举例 线性规划求解的大M法举例 线性规划求解的大M法举例 线性规划求解的两阶段法 线性规划求解的两阶段法 然后用单纯形法求解所构造的新模型 若得到w 0 这时 若基变量中不含人工变量 则说明原问题存在基可行解 可进行第二步计算 否则 原问题无可行解 应停止计算 第二阶段 单纯形法求解原问题第一阶段计算得到的最终单纯形表中除去人工变量 将目标函数行的系数 换成原问题的目标函数后 作为第二阶段计算的初始表 继续求解 线性规划求解两阶段法举例 线性规划求解两阶段法举例 线性规划求解两阶段法举例 单纯形法计算可能的循环现象 单纯形法计算可能的循环现象 在求解线性规划单纯形方法的计算过程循环极少出现 但还是可能的 为防止出现循环现象 先后有人提出了一些方法 如 勃兰特法