《运筹学运输规划》PPT课件.ppt

Chapter3运输规划 TransportationProblem 运输规划问题的数学模型表上作业法运输问题的应用 本章主要内容 运输规划问题的数学模型 例3 1某公司从两个产地A1 A2将物品运往三个销地B1 B2 B3 各产地的产量 各销地的销量和各产地运往各销地每件物品的运费如下表所示 问 应如何调运可使总运输费用最小 运输规划问题的数学模型 解 产销平衡问题 总产量 总销量 500设xij为从产地Ai运往销地Bj的运输量 得到下列运输量表 MinC 6x11 4x12 6x13 6x21 5x22 5x23s t x11 x12 x13 200 x21 x22 x23 300 x11 x21 150 x12 x22 150 x13 x23 200 xij 0 i 1 2 j 1 2 3 运输规划问题的数学模型 运输问题的一般形式 产销平衡 A1 A2 Am表示某物资的m个产地 B1 B2 Bn表示某物质的n个销地 ai表示产地Ai的产量 bj表示销地Bj的销量 cij表示把物资从产地Ai运往销地Bj的单位运价 设xij为从产地Ai运往销地Bj的运输量 得到下列一般运输量问题的模型 运输规划问题的数学模型 变化 1 有时目标函数求最大 如求利润最大或营业额最大等 2 当某些运输线路上的能力有限制时 在模型中直接加入约束条件 等式或不等式约束 3 产销不平衡时 可加入假想的产地 销大于产时 或销地 产大于销时 定理 设有m个产地n个销地且产销平衡的运输问题 则基变量数为m n 1 表上作业法 表上作业法是一种求解运输问题的特殊方法 其实质是单纯形法 表上作业法 例3 2某运输资料如下表所示 问 应如何调运可使总运输费用最小 表上作业法 解 第1步求初始方案 方法1 最小元素法基本思想是就近供应 即从运价最小的地方开始供应 调运 然后次小 直到最后供完为止 3 11 3 10 1 9 2 7 4 10 5 8 3 4 1 6 3 3 表上作业法 总的运输费 3 1 6 4 4 3 1 2 3 10 3 5 86元 元素差额法对最小元素法进行了改进 考虑到产地到销地的最小运价和次小运价之间的差额 如果差额很大 就选最小运价先调运 否则会增加总运费 例如下面两种运输方案 15 5 10 总运费是z 10 8 5 2 15 1 105 最小元素法 表上作业法 5 15 10 总运费z 10 5 15 2 5 1 85 后一种方案考虑到C11与C21之间的差额是8 2 6 如果不先调运x21 到后来就有可能x11 0 这样会使总运费增加较大 从而先调运x21 再是x22 其次是x12 用元素差额法求得的基本可行解更接近最优解 所以也称为近似方案 表上作业法 方法2 Vogel法 1 从运价表中分别计算出各行和各列的最小运费和次最小运费的差额 并填入该表的最右列和最下行 3 11 3 10 1 9 2 7 4 10 5 8 表上作业法 2 再从差值最大的行或列中找出最小运价确定供需关系和供需数量 当产地或销地中有一方数量供应完毕或得到满足时 划去运价表中对应的行或列 重复1 和2 直到找出初始解为至 3 11 3 10 1 9 2 7 4 10 5 8 5 表上作业法 7 1 1 3 5 2 1 5 表上作业法 7 1 3 5 2 7 5 3 表上作业法 1 1 3 5 1 5 3 6 3 1 2 该方案的总运费 1 3 4 6 3 5 2 10 1 8 3 5 85元 表上作业法 第2步最优解的判别 检验数的求法 求出一组基可行解后 判断是否为最优解 仍然是用检验数来判断 记xij的检验数为 ij由第一章知 求最小值的运输问题的最优判别准则是 所有非基变量的检验数都非负 则运输方案最优 求检验数的方法有两种 闭回路法位势法 位势法求检验数是根据对偶理论推导出来的一种方法 设平衡运输问题为 设前m个约束对应的对偶变量为ui i 1 2 m 后n个约束对应的对偶变量为vj j 1 2 n 则运输问题的对偶问题是 4 2运输单纯形法TransportationSimplexMethod 记原问题基变量XB的下标集为I 由对偶性质知 原问题xij的检验数的相反数是对偶问题的松弛变量 ij 当 i j I时 ij 0 因而有 解上面第一个方程 将ui vj代入第二个方程求出 ij 4 2运输单纯形法TransportationSimplexMethod 表上作业法 闭回路的概念 为一个闭回路 集合中的变量称为回路的顶点 相邻两个变量的连线为闭回路的边 如下表 表上作业法 例下表中闭回路的变量集合是 x11 x12 x42 x43 x23 x25 x35 x31 共有8个顶点 这8个顶点间用水平或垂直线段连接起来 组成一条封闭的回路 一条回路中的顶点数一定是偶数 回路遇到顶点必须转90度与另一顶点连接 表中的变量x32及x33不是闭回路的顶点 只是连线的交点 表上作业法 闭回路 例如变量组不能构成一条闭回路 但A中包含有闭回路 变量组变量数是奇数 显然不是闭回路 也不含有闭回路 表上作业法 用位势法对初始方案进行最优性检验 1 由 ij Cij Ui Vj 计算位势Ui Vj 因对基变量而言有 ij 0 即Cij Ui Vj 0 令U1 0 2 再由 ij Cij Ui Vj 计算非基变量的检验数 ij 3 11 3 10 1 9 2 7 4 10 5 8 4 3 6 3 1 3 0 1 5 3 10 2 9 1 2 1 1 10 12 当存在非基变量的检验数 kl 0 说明现行方案为最优方案 否则目标成本还可以进一步减小 表上作业法 当存在非基变量的检验数 kl 0且 kl min ij 时 令Xkl进基 从表中知可选X24进基 第3步确定换入基的变量 第4步确定换出基的变量 以进基变量xkl为起点的闭回路中 标有负号的最小运量作为调整量 对应的基变量为出基变量 并打上 以示换出作为非基变量 min 闭回路中各偶顶点运量 闭回路中偶顶点标负号 奇顶点标正号 表上作业法 3 11 3 10 1 9 2 7 4 10 5 8 4 3 6 3 1 3 调整步骤为 在进基变量的闭回路中标有正号的变量加上调整量 标有负号的变量减去调整量 其余变量不变 得到一组新的基可行解 然后求所有非基变量的检验数重新检验 1 2 5 表上作业法 当所有非基变量的检验数均非负时 则当前调运方案即为最优方案 如表此时最小总运费 Z 1 3 4 6 3 5 2 10 1 8 3 5 85元 3 11 3 10 1 9 2 7 4 10 5 8 5 3 6 3 1 2 0 2 5 3 10 3 9 0 2 2 1 12 9 表上作业法 表上作业法的计算步骤 表上作业法 表上作业法计算中的问题 1 若运输问题的某一基可行解有多个非基变量的检验数为负 在继续迭代时 取它们中任一变量为换入变量均可使目标函数值得到改善 但通常取 ij 0中最小者对应的变量为换入变量 2 无穷多最优解产销平衡的运输问题必定存最优解 如果非基变量的 ij 0 则该问题有无穷多最优解 表上作业法 退化解 表格中一般要有 m n 1 个数字格 但有时在分配运量时则需要同时划去一行和一列 这时需要补一个0 以保证有 m n 1 个数字格作为基变量 一般可在划去的行和列的任意空格处加一个0即可 利用进基变量的闭回路对解进行调整时 标有负号的最小运量 超过2个最小值 作为调整量 选择任意一个最小运量对应的基变量作为出基变量 并打上 以示作为非基变量 表上作业法 12 4 11 4 8 3 10 2 9 5 11 6 0 2 9 2 1 12 8 12 4 2 8 14 如下例中 11检验数是0 经过调整 可得到另一个最优解 表上作业法 11 4 4 3 1 3 7 7 8 2 10 6 3 4 1 6 0 6 在x12 x22 x33 x34中任选一个变量作为基变量 例如选x34 例 用最小元素法求初始可行解 运输问题的应用 求极大值问题目标函数求利润最大或营业额最大等问题 运输问题的应用 求解方法 将极大化问题转化为极小化问题 设极大化问题的运价表为C 用一个较大的数M M max cij 去减每一个cij得到矩阵C 其中C M cij 0 将C 作为极小化问题的运价表 用表上用业法求出最优解 运输问题的应用 例3 3下列矩阵C是Ai I 1 2 3 到Bj的吨公里利润 运输部门如何安排运输方案使总利润最大 运输问题的应用 得到新的最小化运输问题 用表上作业法求解即可 运输问题的应用 产销不平衡的运输问题当总产量与总销量不相等时 称为不平衡运输问题 这类运输问题在实际中常常碰到 它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解 当产大于销时 即 数学模型为 运输问题的应用 由于总产量大于总销量 必有部分产地的产量不能全部运送完 必须就地库存 即每个产地设一个仓库 假设该仓库为一个虚拟销地Bn 1 bn 1作为一个虚设销地Bn 1的销量 即库存量 各产地Ai到Bn 1的运价为零 即Ci n 1 0 i 1 m 则平衡问题的数学模型为 具体求解时 只在运价表右端增加一列Bn 1 运价为零 销量为bn 1即可 运输问题的应用 当销大于产时 即 数学模型为 由于总销量大于总产量 故一定有些需求地不完全满足 这时虚设一个产地Am 1 产量为 运输问题的应用 销大于产化为平衡问题的数学模型为 具体计算时 在运价表的下方增加一行Am 1 运价为零 产量为am 1即可 运输问题的应用 例3 4求下列表中极小化运输问题的最优解 因为有 运输问题的应用 所以是一个产大于销的运输问题 表中A2不可达B1 用一个很大的正数M表示运价C21 虚设一个销量为b5 180 160 20 Ci5 0 i 1 2 3 4 表的右边增添一列 得到新的运价表 运输问题的应用 下表为计算结果 可看出 产地A4还有20个单位没有运出 运输问题的应用 3 生产与储存问题 例3 5某厂按合同规定须于当年每个季度末分别提供10 15 25 20台同一规格的柴油机 已知该厂各季度的生产能力及生产每台柴油机的成本如右表 如果生产出来的柴油机当季不交货 每台每积压一个季度需储存 维护等费用0 15万元 试求在完成合同的情况下 使该厂全年生产总费用为最小的决策方案 运输问题的应用 解 设xij为第i季度生产的第j季度交货的柴油机数目 那么应满足 交货 x11 10生产 x11 x12 x13 x14 25x12 x22 15x22 x23 x24 35x13 x23 x33 25x33 x34 30 x14 x24 x34 x44 20 x44 10 把第i季度生产的柴油机数目看作第i个生产厂的产量 把第j季度交货的柴油机数目看作第j个销售点的销量 设cij是第i季度生产的第j季度交货的每台柴油机的实际成本 应该等于该季度单位成本加上储存 维护等费用 可构造下列产销平衡问题 运输问题的应用 由于产大于销 加上一个虚拟的销地D 化为平衡问题 即可应用表上作业法求解 运输问题的应用 该问题的数学模型 Minf 10 8x11 10 95x12 11 1x13 11 25x14 11 1x22 11 25x23 11 4x24 11 0 x33 11 15x34 11 3x44 运输问题的应用 最优生产决策如下表 最小费用z 773万元 表上作业法解决下列运输问题 习题