物流运筹学(单纯形法).ppt

物流运筹学 第一章 线性规划模型及单纯形法 第五节 单纯形法 1 5 1单纯形法原理 1 5 2单纯形法计算步骤 学习要求 理解单纯形法的原理 会用单纯形法求解线性规划问题 1 5 1单纯形法原理 单纯形法原理 顶点的转移 单纯形法的每一步的可行解对应着图解法可行域中的一个顶点 即从可行域的一个顶点 基本可行解 开始 转移到另一个顶点 另一个基本可行解 的迭代过程 转移的条件是使目标函数值得到改善 逐步变优 当目标函数达到最优值时 问题也就得到了最优解 需要解决的问题 1 为了使目标函数逐步变优 怎么转移 2 目标函数何时达到最优 判断标准是什么 1 5 1单纯形法原理 单纯形法步骤 确定初始基本可行解 检验其是否为最优 寻找更好的基本可行解 停 否 是 主要工作 最优性检验 主要工作 1 基变换 将原来的基换成新的基 2 修正单纯形表 得到新的基本可行解 1 首先引入松弛变量或剩余变量使线性规划模型化为标准形式 且标准形式的系数矩阵中含有一个单位矩阵 型约束添加松弛变量 约束添加剩余变量变为等式约束 1 5 2单纯形法计算步骤 单纯形法步骤 2 确定初始基和初始基本可行解 写出基本可行解和目标函数值 3 最优性检验 1 计算机会成本行 2 计算检验数行 j 3 最优性检验 但所有检验数小于等于0时 得到最优解 计算结束 否则 转入下一步 4 基变换 1 用 j确定进基列向量和进基变量 2 用 规则确定出基列向量及出基变量 5 修正单纯形表 问题1 某工厂计划生产甲 乙两种产品 生产1kg的甲需耗煤9t 电力4kw h 油3t 生产1kg的乙需耗煤4t 电力5kw h 油10t 该厂现有煤360t 电力200kw h 油300t 已知甲产品每千克的售价为7万元 乙产品每千克的售价为12万元 在上述条件下决定生产方案 使得总收入最大 具体数据如表所示 1 5 2单纯形法计算步骤 约束条件 目标函数 此问题的线性规划模型 非标准形式 标准形式 1 5 2单纯形法计算步骤 第一步 引入松弛变量化为标准型 初始基 初始基本可行解 1 5 2单纯形法计算步骤 第二步 编制初始单纯形表并确定初始可行基 初始基本可行解 A 为了求解初始基本可行解的方便 选择单位矩阵为初始基 1 5 2单纯形法计算步骤 第二步 编制初始单纯形表并确定初始可行基 初始基本可行解 基变量 基变量的价值系数 机会成本行 这一行可以省略 价值系数 目标函数中决策变量的系数 检验数行作用 检验当前可行解是否最优 如果不是最优解 确定入基变量 初始基本可行解 在以上基本可行解中 即 甲 乙各生产0件 总的收入为 这个基本可行解显然不是最优解 从目标函数来考虑 还可以通过增加甲 乙的产量 来增加总收入 下面介绍 如何检验现有基本可行解是否为最优解 基本可行解 1 5 2单纯形法计算步骤 第三步 最优性检验 确定当前基本可行解是否是最优解 j检验数的计算 如果所有的检验数都小于等于0 则当前解为最优解 基变量 基变量的价值系数 基本可行解 因为基变量的检验数 1和 2都大于0 所以当前解不是最优 需要变换可行基 寻找新的解 即原来的非基变量x1 x2 要有一个被换为基变量 基变量中也要有一个被换为非基变量 以确定新的基 新的解 1 5 2单纯形法计算步骤 第四步 基变换 1 如果经过检验不是最优解 确定如何换基 首先确定由哪个非基变量作为进基变量 检验数 j中最大的正数对应的非基变量作为进基变量 2 用 检验数确定出基变量 检验数中最小的正数对应的基变量作为出基变量 主元列 确定入基变量 主元行 确定出基变量 主元素 检验数 用来确定出基变量 现分析 确定x1和x2谁入基 因为x2的系数最大 即单位收入最高 自然先考虑增加乙的产量 固确定x2为入基变量 如何确定入基变量 可以按照下述方法来理解 当x2定为入基变量后 必须从x3 x4 x5中换出来一个 并保证其余的变量在新可行解中还都是非负 即 x3 0 x4 0 x5 0 如何确定出基变量 可以按照下述方法来理解 因为x1仍为基变量 所以将x1 0 带入约束条件 得到 只能选x5作为出基变量 令x5 0 请思考为什么 因为 如果选取x3或x4作为出基变量 则会出现有的变量为负值 第五步 进行矩阵的初等变换 修正单纯形表继续进行最优性检验计算 X 1 0 30 240 50 0 T X 0 0 0 360 200 300 T Z 1 360 Z 0 0 B 1 P3 P4 P2 B 0 P3 P4 P5 初等变换过程 第 行除以10 变为 乘上 5 加上第 行 变为 乘上 4 加上第 行 变为 因为 1 0 所以当前解仍不是最优解 需要继续进行基变换 1 5 2单纯形法计算步骤 第五步 进行矩阵的初等变换 修正单纯形表继续进行最优性检验计算 X 1 0 30 240 50 0 T X 2 20 24 84 0 0 T X 0 0 0 360 200 300 T Z 1 360 Z 2 428 Z 0 0 B 1 P3 P4 P2 B 2 P3 P1 P2 B 0 P3 P4 P5 1 5 2单纯形法计算步骤 第六步 得到最优解 及目标函数最优值 写出结果 最优解为 X 2 20 24 84 0 0 T 目标函数最优值为 Z 2 428 即最优生产计划为 甲生产20件 乙生产24件 最大收入为 428万元 在最后的单纯形表中 所有非基变量的检验数 j 0 可以判断已得到最优解 此表即为最终单纯形表 对应的基 P3 P1 P2 为最优基 练习题