运筹学基础及应用(第五版)_(第三章运输问题).ppt

2019 12 20 1 运筹学operationsresearch 2019 12 20 2 第三章运输问题 运输问题的数学模型表上作业法产销不平衡的运输问题及应用 2019 12 20 3 1运输问题的典例及数学模型 一 引例 某公司从三个产地 将产品运往四个销地 各产地的产量 各销地的销量 及各产地往各销地的运费单价如表所示 应如何调运可使运费最小 2019 12 20 4 解 从表中可知 总产量 总销量 这是一个产销平衡的运输问题 假设表示从产地运往销地的产品数量 建立如下表格 于是可建立如下的数学模型 2019 12 20 5 目标函数 约束条件 产量约束 销量约束 20 20 2019 12 20 6 设有m个产地 分别为 n个销地 分别是 从产地运往销地的单位运价是 运量是产地的产量 是销地的销量 二 一般运输问题数学模型 则该运输问题的模型如下 2019 12 20 7 说明 当时 称其为产销平衡的运输问题 否则产销不平衡 2019 12 20 8 说明 从上述模型可以看出 1 这是一个线性规划的模型 2 变量有m n个 3 约束条件有m n个 4 系数矩阵非常稀疏 系数矩阵的秩一般为 m n 1 而非m n 若直接用单纯形法求解 显然单纯形表比较庞大 于是在单纯形法的基础上创建了表上作业法求解运输问题这一特殊的线性规划问题 2019 12 20 9 从第一节的运输问题的数学模型可知 运输问题实际上也属于线性规划 但由于运输问题的特殊性 变量个数较多 系数矩阵的特点 如果用单纯形表格方法迭代 计算量很大 今天介绍的 表上作业法 是针对运输问题的特殊求解方法 实质还是单纯形法 但减少了计算量 表上作业法适用于求解产销平衡的运输问题 产销不平衡的问题可转化为平衡问题 2运输问题的表上作业法 2019 12 20 10 表上作业法一般步骤 1 找出初始基本可行解 2 检查各非基变量的检验数 是否达到最优性条件 若达到 则得最优解 否则转第三步 3 确定出基变量 进基变量 用闭回路方法进行调整 得到新的基可行解 4 重复第二 第三步 直至得到最优解 2019 12 20 11 一 确定初始基本可行解 对于有m个产地n个销地的产销平衡问题 有m个关于产量的约束方程和n个关于销量的约束方程 表面上 共有m n个约束方程 但由于产销平衡 其模型最多只有m n 1个独立的约束方程 所以运输问题实际上有m n 1个基变量 在m n的产销平衡表上给出m n 1个数字格 其相对应的调运量的值即为基变量的值 那么在该例中 应有3 4 1 6个基变量 2019 12 20 12 1 最小元素法最小元素法的思想是就近供应 即对单位运价最小的变量分配运输量 在表上找到单位运价最小的x21 并使x21取尽可能大的值 即x21 3 把a1的产量改为1 b1的销量改为0 并把b1列划去 在剩下的3 3矩阵中再找最小运价 同理可得其他的基本可行解 3 11 3 10 8 5 10 2 9 4 7 1 2019 12 20 13 表中填有数字的格对应于基变量 取值即为格中数字 而空格对应的是非基变量 取值为零 在求初始基本可行解时要注意的一个问题 当我们取定xij的值之后 会出现ai的产量与bj的销量都改为零的情况 这时只能划去ai行或bj列 但不能同时划去ai行与bj列 或者在同时划去ai行与bj列时 在该行或该列的任意空格处填加一个0 这样可以保证填过数或零的格为m n 1个 即保证基变量的个数为m n 1个 2019 12 20 14 2 vogel法vogel法的思想是 一地的产品如果不能按照最小运费就近供应 就考虑次小运费 这就有差额 差额越大 说明不能按最小运费调运时 运费增加得越多 因而差额越大处 就应当采用最小运费调运 3 11 3 10 2 9 4 7 1 10 8 5 2019 12 20 15 二 最优解的判别判别解的最优性需要 计算检验数 方法有两种 闭回路 是在已给出的调运方案的运输表上从一个代表非基变量的空格出发 沿水平或垂直方向前进 遇到代表基变量的填入数字的格可转90度 当然也可以不改变方向 继续前进 这样继续下去 直至回到出发的那个空格 由此形成的封闭折线叫做闭回路 一个空格存在唯一的闭回路 1 闭回路法 因为任意非基向量均可表示为基向量的唯一线性组合 因此对于任意空格都能够找到 并且只能找到唯一的一条闭回路 2019 12 20 16 从非基变量出发 找到一个闭回路如上表所示 回路有四个顶点 除外 其余都为基变量 调整调运量 运费增加了3元 运费减少3元 运费增加2元 运费减少1元调整后 总运费增加 3 3 2 1 1元 说明如果让为基变量 运费就会增加 其增加值1作为的检验数 2019 12 20 17 闭回路法计算检验数 就是对于代表非基变量的空格 其调运量为零 把它的调运量调整为1 由于产销平衡的要求 必须对这个空格的闭回路中的各顶点的调运量加上或减少1 最后计算出由这些变化给整个运输方案的总运输费带来的变化 以这个变化的数值 作为各空格 非基变量 的检验数 判别最优解准则 如果所有代表非基变量的空格的检验数都大于等于零 则已求得最优解 否则继续改进找出最优解 2019 12 20 18 2 位势法 1 对运输表上的每一行赋予一个数值 对每一列赋予一个数值 称为行 列 位势 2 行 列 位势的数值是由基变量的检验数所决定的 即基变量要满足 非基变量的检验数就可以用公式求出 2019 12 20 19 我们先给u1赋个任意数值 不妨设u1 0 则从基变量x11的检验数求得v3 c13 u1 3 0 3 同理可以求得v4 10 u2 1 等等见上表 检验数的求法 即用公式 如 2019 12 20 20 位势法计算检验数 检验数 又因为基变量的检验数为0 于是由 m n 1 个基变量的检验数可解出 进而计算其他非基变量的检验数 其中 第i个分量 第m j个分量 2019 12 20 21 三 改进运输方案的办法 闭回路调整法 当表中的某个检验数小于零时 方案不为最优 需要调整 方法是 选取所有负检验数中最小的非基变量作为入基变量 以求尽快实现最优 1 确定调整量 例 取 表明增加一个单位的运输量 可使得总运费减少1 在以为出发点的闭回路中 找出所有偶数顶点的调运量 则调整量 2 调整方法 把所有闭回路上为偶数顶点的运输量都减少这个值 奇数顶点的运输量都增加这个值 见下表 2019 12 20 22 调整运量后的新方案 2019 12 20 23 对上表用位势法进行检验如下表 可知已达最优解 表上作业法的一般步骤 1 用最小元素法或vogel法确定初始基可行解 2 判断是否为最优 用闭回路法或位势法计算空格检验数 若所有检验数均非负 则已得到最优解 否则进入第三步 3 从所有负检验数中选择最小者对应空格作为进基变量 从此点出发作闭回路 确定调整量 奇点处增加 偶点处减少 2019 12 20 24 例 用表上作业法 求解下面的运输问题 解 用最小元素法确定初始基可行解 如下表所示 2019 12 20 25 2019 12 20 26 2019 12 20 27 此时所有非基变量的检验数均非负 故已达最优解 2019 12 20 28 一 产销不平衡的运输问题 例1 某公司从两个产地 将产品运往三个销地 各产地的产量 各销地的销量 及各产地往各销地的运费单价如表所示 应如何调运可使运费最小 3产销不平衡的运输问题及应用 例1 某公司从两个产地 将产品运往三个销地 各产地的产量 各销地的销量 及各产地往各销地的运费单价如表所示 应如何调运可使运费最小 例1 某公司从两个产地 将产品运往三个销地 各产地的产量 各销地的销量 及各产地往各销地的运费单价如表所示 应如何调运可使运费最小 例1 某公司从两个产地 将产品运往三个销地 各产地的产量 各销地的销量 及各产地往各销地的运费单价如表所示 应如何调运可使运费最小 例1 某公司从两个产地 将产品运往三个销地 各产地的产量 各销地的销量 及各产地往各销地的运费单价如表所示 应如何调运可使运费最小 例1 某公司从两个产地 将产品运往三个销地 各产地的产量 各销地的销量 及各产地往各销地的运费单价如表所示 应如何调运可使运费最小 例1 某公司从两个产地 将产品运往三个销地 各产地的产量 各销地的销量 及各产地往各销地的运费单价如表所示 应如何调运可使运费最小 2019 12 20 29 易知这个问题中 总产量 总销量 即 这时可考虑增加一个假想产地 其产量是 总销量 总产量 150 他到各销地的单位运费是 于是得到如下的表格 2019 12 20 30 例2 某单位有三个区 一区 二区 三区 每年需要生活用煤和取暖用煤各3000吨 1000吨 2000吨 由河北临城 山西盂县两处煤矿负责供应 两地价格和煤质相同 两煤矿的供应能力分别是1500吨 和4000吨 由煤矿至该单位三个区的单位运价如表所示 由于供应能力限制 经研究决定 一区供应量可减少0 300吨 二区全部满足 三区不能少于1500吨 试求使得运费最小的运输方案 2019 12 20 31 根据题意 添加虚拟产地后 可作出产销平衡的运价表 2019 12 20 32 例 设有三个化肥厂供应四个地区的化肥 假设等量的化肥在这个地区的使用效果相同 各厂的产量 各地区的需要量 单位运价如表所示 求出运费最省的调拨方案 2019 12 20 33 解 无论考虑需求的上限还是下限 这都是一个产销不平衡的问题 当考虑下限时 产 销 当考虑需求上限时 产 销 于是可以考虑在满足最低需求的情况下 兼顾最高需求 即将每个地区的需求分为最低需求和 最高 最低 需求 最低部分必须满足 高出的部分可满足也可不满足 虽然销地 的需求无上限 但根据生产能力 最多可以给她分配60万吨 另外若将最高需求考虑进来 则需添加虚拟产地d 其产量应为50万吨 于是可给出如下的产销平衡及运价表 2019 12 20 34 2019 12 20 35 二 生产与存储问题 例4 某厂按照合同规定须于当年每季度末分别提供10 15 25 20台同一规格的柴油机 已知该厂各季度的生产能力及生产每台柴油机的成本如表所示 又如果生产出来的柴油机当季不交货 每台每积压一个季度 存储维护费用0 15万元 要求在完成合同的情况下 使得全年生产 存储 费用最小的决策 2019 12 20 36 注意 单位运价如何确定 故设 表示第季度生产 用于第季度交货的产品数量 可建立数学模型 2019 12 20 37 三 转运问题 以本章引例为例 产品从3个产地运往4个销地 现考虑 1 各产地的产品不一定直接运往销地 可以将产品集中后再一起运 2 运往个销地的产品也可先运给其中几个 再转运给其他销地 3 除产 销地外还可以有几个中间转运站 在产地之间 销地之间 或产地与销地之间进行转运 已知单位运价表如下 问在考虑产销地之间直接运输和非直接运输的各种可能方案下 如何安排运输方案 可使总运费最小 2019 12 20 38