运筹学运输问题完整版本.ppt

运输问题 简介 运输问题是线性规划问题的特例 产地 货物发出的地点 销地 货物接收的地点 产量 各产地的可供货量 销量 各销地的需求数量 运输问题就是研究如何组织调运 既满足各销地的需求 又使总运费最小 一 运输模型 引例 某饮料在国内有三个生产厂 分布在城市A1 A2 A3 其一级承销商有4个 分布在城市B1 B2 B3 B4 已知各厂的产量 各承销商的销售量及从Ai到Bj的每吨饮料运费为Cij 为发挥集团优势 公司要统一筹划运销问题 求运费最小的调运方案 1 决策变量 设从Ai到Bj的运输量为xij 2 目标函数minZ 4x11 12x12 4x13 11x14 2x21 10 x22 3x23 9x24 8x31 5x32 11x33 6x34 3 约束条件 产量之和等于销量之和 故要满足 运输问题的LP模型 供应平衡条件 产地A1 x11 x12 x13 x14 16产地A2 x21 x22 x23 x24 10产地A3 x31 x32 x33 x34 22 销售平衡条件 销地B1 x11 x21 x31 8销地B2 x12 x22 x32 14销地B3 x13 x23 x33 12销地B4 x14 x24 x34 14 非负性约束xij 0 i 1 2 3 j 1 2 3 4 二 表式运输模型 三 运输问题的三种类型 产销平衡 产大于销 产小于销 四 运输模型的特点 决策变量m n约束方程m n系数矩阵的结构如下 例题的系数矩阵 约束1约束2约束3约束4约束5约束6约束7 运输问题求解思路 先找到一个初始基可行解 判断其是否最优 如果是 计算结束 得到最佳运输方案 如果不是 则迭代到相邻的基可行解 向目标函数减少的方向 直到求得最优解 为了能按上述思路求解运输问题 要求每一步都必须是基可行解 1 解必须满足模型中的所有约束条件 2 基变量对应的约束方程组的系数列向量线性无关 3 解中非零变量xij的个数不能大于 m n 1 个 原因是运输问题中虽有 m n 个结构约束条件 但由于总产量等于总销量 故只有 m n 1 个结构约束条件是线性独立的 所以一般我们在迭代过程中都保持基变量的个数为 m n 1 个 表上作业法 表上作业法适合于产销平衡的运输问题求解步骤 找出初始方案 初始基可行解 产销平衡表上给出m n 1个数字 最优性检验 计算各非基变量的检验数 当 ij 0最优 因为现在是求最小化问题 方案调整与改进 确定进基变量和离基变量 找出新的基可行解 一 确定初始方案 西北角法最小元素法 就近运给 从单位运价表中最小运价开始确定供销关系 逐次挑选最小元素 安排运量min ai bj 最大差额法 沃格尔法 不能按最小运费就近供应 就考虑次小运费 各行 各列 的最小运费与次小运费之差称为行差 列查 差额越大 说明不能按最小运费调运时 运费增加最多 对最大差额处就采用最小运费调运 西北角法 西北角法按照运输表格中的位置 安排最西北角 也就是左上角的位置 优先运输 初始基可行解 x11 8 x12 8 x22 6 x23 4 x33 8 x34 14 Z 372 8 8 6 4 8 14 8 最小元素法 人们容易直观想到 为了减少运费 应优先考虑单位运价最小 或运距最短 的供销业务 最大限度地满足其供销量 即对所有的i和j 从单位运价表中逐次挑选最小元素 安排运量min ai bj 若xij ai 则产地Ai的可供物品已用完 以后不再继续考虑这个产地 且Bj的需求量由bj减少为bj ai 即当产小于销 划去该元素所在行 如果xij bj 则销地Bj的需求已全部得到满足 以后不再考虑这个销地 且Ai的可供量由ai减少为ai bj 即当产大于销 划去该元素所在列 然后在余下的继续进行 直到安排完所有供销任务 初始基可行解 x13 10 x14 6 x21 8 x23 2 x32 14 x34 8 Z 246 8 2 10 14 8 6 最大差额法 沃格尔法 初看起来 最小元素法十分合理 但是 有时按某一最小单位运价优先安排物品调运时 却可能导致不得不采用运费很高的其它供销点对 从而使整个运输费用增加 对每一个供应地或销售地 均可由它到各销售地或到各供应地的单位运价中找出最小单位运价次最小单位运价 并称这两个单位运价之差为该供应地或销售地的罚数 当罚数的值不大 当不能按最小单位运价安排运输时造成的运费损失不大 反之 如果罚数的值很大 不按最小运价组织运输就会造成很大的损失 故应尽量按最小单位运价安排运输 列罚数 行罚数 1011 12513 14 2012 2213 8 301 3212 8 476 412 12 500 52 2 4 初始基可行解 x13 12 x14 4 x21 8 x24 2 x32 14 x34 8 Z 244 二 解的最优性检验 从以上得的初始解之后 即应对这个解进行最优性判别 看它是不是最优解 闭回路法 对偶变量法 闭回路法 要判定运输问题的某个解是否为最优解 可仿照一般单纯形法 检验这个解的各非基变量 对应于运输表中的空格 的检验数 若有某空格 Ai Bj 的检验数为负 说明将xij变为基变量将使运输费用减少 故当前这个解不是最优解 若所有空格的检验数全非负 则不管怎样变换解均不能使运输费用降低 即目标函数值已无法改进 这个解就是最优解 由线性规化的模型可以看出 ij cij CBB 1Pij运输问题的目标函数要求为最小 即当 ij 0视为最优 也就是说只要存在 ij小零 此时就不能得到最优解 闭回路法就为我们提供了一种计算非基变量检验数的方法 8 2 10 14 8 6 以最小元素法 C11 C21 C23 C31 4 2 3 4 1 C22 C32 C34 C14 C13 C23 10 5 6 11 4 3 1 这样会得到初始调运方案的检验数 在这个之中存在检验数小于零 所以此时没有得到最优解 从中可以看出为了求某个空格 非基变量 的检验数 先要找出它在运输表上的闭回路 这个闭回路的顶点 除这个空格外 其它均为填有数字的格 基变量格 它是由水平线段和竖直线段依次联接这些顶点构成的一封闭多边形 可以证明 每个空格都唯一存在这样的一条闭回路 闭回路可以是一个简单的矩形 也可以是由水平和竖直边线组成的其它更复杂的封闭多边形 位于闭回路上的一组变量 它们对应的运输问题约束条件的系数列向量线性相关 因而在运输问题基可行解的迭代过程中 不允许出现全部顶点由填有数字的格构成的闭回路 这就是说 在确定运输问题的基可行解时 除要求非零变量的个数为 m n 1 个外 还要求运输表中填有数字的格不构成闭回路 当然还要满足所有约束条件 用前述最小元素法 西北角法和VOGEL法得到的解满足这些条件 对偶变量法 dualvariablemethod 也称为位势法用闭回路法判定一个运输方案是否为最优方案 需要找出所有空格的闭回路 并计算出其检验数 当运输问题的产地和销地很多时 空格的数目很大 计算检验数的工作十分繁重 而且对偶变量法就要简便的多 对于产销平衡问题 若用分别表示前m个约束等式相应的对偶变量 用表示后n个等式约束相应的对偶变量 即有对偶变量及对偶规划 3 7 线性规划问题的检验数Xj的检验数可表示为 所以运输问题某量的Xij的检验数为 现设我们已得到了运输问题的一个基可行解 其基变量是 对应于这些基变量的检验数都为零 即这些基变量的检验数可写为方程组 3 9 显然 上述方程组有m n 1个方程 运输表中每个产地和每个销地都对应原运输问题的一个约束条件 从而也对应各自的一个对偶变量 由于运输表中每行和每列都含有基变量 可知这样构造的方程组中含有全部m n个对偶变量 可以证明 方程组 3 9 有解 且由于对偶变量数比方程数多一个 故解不唯一 方程 3 9 的解称为位势 若由 3 9 解得的某组解满足 3 7 的所有约束条件 即对所有i和j均有其检验数大于0 即 由前面的互补松定理 此时对偶问题与原问题同时达到最优解 若由 3 9 解得的某组解不满足 3 7 的所有约束条件 即非基变量的检验数有负值存在 则上面得到的运输问题的解不是最优解 需要进行解的调整 用位势法对表3 5给出的运输问题作最优性检验 8 2 10 14 8 6 uiu1u2u3 vjv1v2v3v4 1 对于上表中增加一位势列ui和位势行vj 如下所示 2 计算位势 依据上面的基变量建立方程组 并据此计算出运输表各行和各列的位势 对于左式的计算 为计算方便 常任意指定一位势等于一个较小的整数或零 为了和书上一致 我们假定u2 0 由此可算出 V1 3 V3 3 u1 1 v4 10 u3 4V2 9 将其填入表中的圆括号内 如上页所示 一般情况下我们不用列方程求解 直接在表中假设任意一个位势为0 不妨我们也假设u2 0 8 2 10 14 8 6 Ui vj U2 0 Ui vj U2 0 V1 2 V3 3 U1 1 V4 10 U3 4 V2 9 3 计算各个非基变量的检验数 1 11 C11 U1 V1 1 2 1 1 10 12 由以上可以看出 位势法与用闭回路法算出的检验数完全相同 因 24 1 0 故这个解不是最优解 三 解的改进 对于某一个 ij小于0 则此时不存在最优解 所以必须对其进行改进 改进的方法 在运输表中找出这个空格对应的闭回路Lij 在满足所有约束条件的前提下 使Xij尽量增大并相应调整此闭回路上其它顶点的运输量 以得到另一个更好的基可行解 解改进的具体步骤 1 以Xij为换入变量 找出它在运输表中的闭回路 2 以空格 Ai Bj 为第一个奇数顶点 沿闭回路的顺 或逆 时针方向前进 对闭回路上的顶点依次编号 3 在闭回路上的所有偶数顶点中 找出运输量最小的项点 格子 以该格中的变量为换出变量 4 以为调整量 将该闭回路上所有奇数顶点处的运输量都增加这一数值 所有偶数顶点处的运输量都减去这一数值 从而得出一新的运输方案 该运输方案的总运费比原运输方案减少 改变量等于 然后 再对得到的新解进行最优性检验 如不是最优解 就重复以上步骤继续进行调整 一直到得出最优解为止 继续对上例的解进行改进 解 由前面的表可知 由于 24 1 0 故以X24为换入变量 它对应的闭回路示于如下表 8 2 10 14 8 6 在该闭回路的偶数顶点位于格 A1 B4 和 A2 B3 由于 8 2 10 14 8 6 所以对x24 2x14 2x13 2x23 2 2 2 2 2 8 2 12 14 8 4 现在用位势法或闭回路法求这个新基可行解各非基变量的检验数 结果如上图所示 0 2 2 1 9 12 由于所有非基变量的检验数全非负 故这个解为最优解 从图中我们还可以看出 有一个非基变量的检验数为0 所以存在无穷多最优解 补充说明 1 若运输问题的某一基可行解有几个非基变量的检验数均为负 在继续进行迭代时 取它们中的任一变量均可使目标函数值得到改善 但通常取 ij 0中最小者对应的变量为换入变量 2 当迭代到运输问题的最优解时 如果某非基变量的检验数等于零 则说明该运输问题有多重 无穷多 最优解 3 当运输问题某部分产地的产量和 与某一部分销地的销量和相等时 在迭代过程中有可能在某个格填入一个运量时需同时划去运输表的一行和一列 这时就出现了退化 在运输问题中 退化解是时常发生的 为了使表上作业法的迭代工作进行下去 退化时应在同时划去的一行或一列中的某个格中填入数字0 表示这个格中的变量是取值为0的基变量 使迭代过程中基可行解的分量恰好为 m n 1 个 第三节运输问题的进一步讨论 在运输问题中 并不是所有的运输问题都是产销平衡的 往存在产销不平衡问题 所以要利用表上作业法进行 就必须将产销不平衡问题化为产销平衡的问题进行求解 产大于销 对于这种问题 我们可以增加一个销地 使其变为产销平衡问题 例 增加一个销地 50 46 5046 5050 初始基可行解 最小元素法 12 15 6 12 1 4 初始基可行解 x13 15 x21 6 x22 12 x31 12 x33 1 x34 4 Z 140 最优性检验 0 2 6 3 2 5 11 6 2 3 2 非基变量x32的检验数 32 2 即让非基变量x32进基 Z 140 闭回路调整 x32进基最小调整量为12 x22离基 非最优方案的调整所有偶点的值都加上调整量 所有奇点的值都减去调整量 基可行解 x13 15 x21 18 x31 0 x32 12 x31 1 x34 4 Z 116 基变量的检验数 ij cij ui vj 0 且令u1 0 计算位势量ui和vj 最优性检验 所有非基变量xij的检验数 ij cij ui vj 0 即得最优解 0 2 6 3 5 13 6 2 3 2 产小于销 对于这种问题 我们可以增加一个产地 使其变为产销平衡问题 增加一个产地 例 2223 2323 初始基可行解 10 0 5 7 1 初始基可行解 x12 10 x13 0 x21 7 x23 5 x31 1 Z 46 最优性检验 0 1 2 2 2 2 1 0 检验数 ij 0 得最优解 x12 10 x13 0 x21 7 x23 5 x31 1 Z 46由于非基变量x33的检验数 33 0 为多重最优解 让x33进 x31离 另一最优解 x12 10 x13 0 x21 8 x23 4 x33 1上例x12 10 x13 0 x21 7 x23 5 x31 1 表示销地B1脱销1个单位 然而x12 10 x13 0 x21 8 x23 4 x33 1 则表示销地B3脱销1个单位 二 有转运的运输问题 有时 需先将物品由产地运到某个中间转运站 可能是另外的产地 销地或中间转运仓库 然后再转运到销售目的地 有时 经转运比直接运到目的地更为经济 总之 在很多情况下 在决定运输方案时有必要把转运也考虑进去 对于这样的问题 求解起来相当复杂 我们简要的给大家说一下原理 studybyyourself 第四节运输问题应用举例 生产与储存问题例1 某厂按合同规定须于当年每个季度末分别提供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个销售点的销量 成本加储存费用看作运费 可构造下列产销平衡问题 目标函数 Minf 10 8x11 10 95x12 11 1x13 11 25x14 11 1x22 11 25x23 11 4x24 11 0 x33 11 15x34 11 3x44 例2 自来水分配问题 水价90元 千吨 管理费45元 千吨 引水费价格如下表 如何分配供水量 保障各区最低需求 获利最大 利润 收入 成本 收入最大 成本最小 则利润最大 收入 每天供水总量是一常数 水价也是常数 则每天总收入也是常数 每天供水总量若能全部售出 每天总收入则能达到最大 丁区最高需求不限 每天总供水量能全售出 每天总收入是常数 与水量分配无关 可以不与考虑 成本 各区管理费相同45元 kt 每天售水总量是一常数 则管理费也是常数 各区引水费不同 如果总的引水费达到最小 总成本则最低 如何分配水量 既满足最低需求 又使总的引水费最低 分析 最大需求量 供水总量 50 60 50 160 四区最低需求量 30 70 10 110 故丁区最大需求量160 110 10 60 四区最大需求 50 70 30 60 210 比供水总量160多50 则是一个产小于销的不平衡问题 产小于销的运输问题化为平衡问题 虚设水库D 供水量50 各区的最低需求为基本需求 不允