运输问题1.ppt

第四章运输问题TransportationProblem 第1节数学模型 一 运输问题运输问题属于线性规划问题 因为其约束方程组的系数矩阵A具有特殊的结构 所以专门介绍一种比单纯形法更简便的求解方法 以节约计算时间和费用 第1节数学模型 例1 某食品公司经销的主要产品之一是糖果 它下面设有三个加工厂 每天的糖果生产量分别为A1 7t 吨 A2 4t A3 9t 该公司把这些糖果分别运往四个地区的门市部销售 各地区每天的销售量为B1 3t 吨 B2 6t B3 5t B4 6t 已知从每个加工厂到各销售门市部每吨糖果的运价 如下表所示 试问该食品公司应如何调运 在满足各门市部销售需要的情况下 使总的运费支出最少 第1节数学模型 二 运输问题的数学模型已知有m个生产地点 简称产地 可供应某种物资 其供应量 产量 分别为 有n个销售地点 简称销地 其需要量 销量 分别为 从到运输单位物资的运价 单位运价 为 将这些数据表示在如下的两个表中 问应如何调运 在满足各销地销量的情况下 使总的运费支出最少 第1节数学模型 产销平衡表两个表合二为一 单位运价表 第1节数学模型 例1 解 设xij为第i加工厂向第j门市部的糖果的供应量 cij表示第i加工厂向第j门市部供应糖果的单位运费 第1节数学模型 产销平衡运输问题的数学模型 设xij表示从产地Ai运往销地Bj的产品数量 第1节数学模型 特征 1 决策变量 m n 2 约束方程 m n 都是等式约束 3 目标函数 最小化 4 约束方程组系数矩阵A A中只有数字0或1 A的每一列只有两个非零元素1 5 各产地产量之和等于各销地销量之和 6 基变量 m n 1 7 对于产销平衡的运输问题 必有可行解和最优解 第1节数学模型 第2节表上作业法 一 表上作业法的解题思路表上作业法的实质是单纯形法在求解运输问题时的一种简化方法 属于单纯形法 又称为运输单纯形法 第2节表上作业法 二 表上作业法的特点表上作业法是一种迭代法用表上作业法求解运输问题 直接在表上进行 不必写出数学模型 第2节表上作业法 三 表上作业法的解题步骤1 找出初始基可行解 在产销平衡表上找出 m n 1 个数字格 形成初始产销平衡表方法 最小元素法2 求非基变量检验数 计算初始产销平衡表中空格的检验数 判别是否达到最优解 如果已达到 停止计算 否则转入3方法3 确定换入变量和换出变量 找出新的基可行解方法 闭回路调整法4 重复2 3 直到求出最优解 第2节表上作业法 一 确定初始基可行解 最小元素法基本思路从运费上考虑 优先安排单位运价最小的产地和销地之间的运输业务 最大限度地满足其产销量 从而实现 就近供应 第2节表上作业法 一 确定初始基可行解 最小元素法求解步骤第一 从单位运价表中找出最小运价 有两个或两个以上的最小单位运价 则任选其一 比较产量和销量 产量 销量 则划去该运价所在列 产量 销量 则划去该运价所在行 并在初始产销平衡表上填上相应的数字 第二 从单位运价表中未被划去的运价中再找最小运价 重复第一 第二 直到单位运价表中所有运价都被划去 并找出 m n 1 个数字格 第2节表上作业法 例2 用最小元素法找出例1的初始基可行解 产销平衡表和单位运价表合二为一 如下所示 第2节表上作业法 例2 解 初始产销平衡表 第2节表上作业法 小结 1 在初始产销平衡表上每填入一个数字 在单位运价表上就划去一行或一列 当表中只剩一个元素时 在初始产销平衡表上填数字时 在单位运价表上同时划去一行和一列 2 在单位运价表上共划去 m n 条直线 相当于单位运价表上所有cij都被划去两次 3 在初始产销平衡表上填了 m n 1 个数字格 每行数字之和 该行产量 每列数字之和 该列销量 第2节表上作业法 例3 判断下表给出的运输方案能否作为用 最小元素法 求解出的初始基可行解 作业10 作业10 用最小元素法找出下列运输问题的初始基可行解 1 2 其中M为任意大正数 表示含义为从A4到B4不存在运输路线 作业10答案 1 2 第2节表上作业法 二 求检验数 判别最优解基本思路计算空格 非基变量 的检验数 运输问题的目标函数要求实现最小化 当所有检验数 0时 所得的解是最优解 否则要进行解的改进 第2节表上作业法 二 求检验数 判别最优解 闭回路法求解步骤第一 在初始产销平衡表上 从每一空格出发找一条闭回路 以某空格为起点 用水平或垂直线向前画 碰到一数字格转90 有些情况下也可以不改变方向 然后继续前进 直到回到起始空格为止 第二 在一闭回路上 令某空格取值为 1 表示增加的运量 然后变化相应数字格的值 并计算该闭回路上运费的变化值 即为该空格的检验数 填入检验数表 第2节表上作业法 检验数的含义检验数表示变化的运费 即 若某空格 Ai Bj 的检验数 0 表示将该空格变为数字格使运输费用减少 则当前这个解不是最优解 反之 若所有空格的检验数都 0 表示不管怎样变换 都使运输费用增加 则目标函数已无法改进 当前这个解就是最优解 第2节表上作业法 例4 用闭回路法求例2所得的初始基可行解的检验数 第2节表上作业法 例4 解 检验数表 第2节表上作业法 例5 用闭回路法求下述某初始基可行解的检验数 数据同例1 第2节表上作业法 例5 解 检验数表 第2节表上作业法 小结 1 闭回路的顶点 除出发点为空格外 其他均为数字格 2 每个空格唯一存在一条闭回路 3 对于产销点过多的运输问题 空格的数目很大 计算检验数很繁琐 第2节表上作业法 二 求检验数 判别最优解 位势法求解步骤第一 仿照初始产销平衡表做一个表 在对应的数字格处填入单位运价cij 第二 在表的最右列和最下行分别增加一列ui和一行vj 使表中的单位运价等于它所在行和列的ui与vj之和 求出所有的ui和vj 并填写在表中 第三 计算各空格的检验数 填入检验数表 第2节表上作业法 例6 用位势法求例2所得的初始基可行解的检验数 第2节表上作业法 例6 解 检验数表 第2节表上作业法 例7 用位势法求下述某初始基可行解的检验数 数据同例1 第2节表上作业法 例7 解 检验数表 第2节表上作业法 小结当运输问题的产地和销地很多时 空格的数目很大 采用位势法计算检验数简便 第2节表上作业法 三 确定换入和换出变量 找出新的基可行解 直至求出最优解 闭回路调整法基本思想在初始产销平衡表中 选取检验数为负的所有空格中的最小者作为换入格 以对应空格为出发点画出闭回路 在经过的数字格中选择 1 的最小者 对应的数字格为换出格 然后对闭回路上各顶点的数据进行调整 得到另一个更好的基可行解 第2节表上作业法 三 确定换入和换出变量 找出新的基可行解 直至求出最优解 闭回路调整法求解步骤第一 确定换入格 在初始产销平衡表上 最小的负检验数所在的空格为换入格 有两个或两个以上的最小者 则任选其一 并以此空格为出发点 作一闭回路 第二 确定换出格 选择闭回路上标记为 1 的数字格中的最小者 记做 则该数字格为换出格 第三 调整 将闭回路上标记为 1 的数字格 加 标记为 1 的数字格 减 得到新的基可行解 第四 采用闭回路法或位势法求空格的检验数 若所有检验数都 0 则获得最优解 否则重复第一 第三 直至求出最优解 第2节表上作业法 例8 以例6所求的检验数为依据 求例1的最优解 检验数表初始产销平衡表 第2节表上作业法 例8 解 最优解检验数表z 85 第2节表上作业法 四 表上作业法的解1 无穷多 多重 最优解某个空格 非基变量 的检验数为0时 该运输问题有无穷多 多重 最优解 在已求得一个最优解的表中 以这样的空格出发做闭回路重新进行调整 得到另一个最优解 第2节表上作业法 2 退化解某个数字格 基变量 为0时 该运输问题为退化解 退化解出现的情况 确定初始解的各供需关系时 若在某格填入某数字后 出现该处的供应量与需求量相等 用闭回路调整法调整时 在闭回路上出现两个或两个以上的具有 1 标记的相等的最小值 第2节表上作业法 例9 用最小元素法求出下述运输问题的初始基可行解 第2节表上作业法 例9 解 初始基可行解 第2节表上作业法 例10 已知某初始产销平衡表 如下表 空格A2B4格的检验数 0 其余空格的检验数均 0 试确定调入 调出格 求出新的基可行解 第2节表上作业法 例10 解 下一个基可行解 第2节表上作业法 例10 解 再下一个基可行解 第2节表上作业法 五 表上作业法计算步骤框图 第2节表上作业法 例11 已知三个产地A1 A2 A3 四个销地B1 B2 B3 B4的产销量即单位运价如下表所示 求使总运费最少的调运方案 第2节表上作业法 例11 解 无穷多最优解 退化解z 6000 作业11 作业11 用表上作业法求解下列运输问题的最优解 1 2 作业11答案 1 2 第3节产销不平衡的运输问题 一 求解思路总产量不等于总销量 为使用表上作业法求解 将产销不平衡运输问题转化为产销平衡运输问题 第3节产销不平衡的运输问题 二 求解方法1 总产量 总销量 第3节产销不平衡的运输问题 解题思路 为借助于产销平衡的表上作业法求解 增加一个假想的销地Bn 1 由于实际上它不存在 因而由产地Ai i 1 2 m 调运到这个假想销地的物品数量xi n 1 就是就地存贮在Ai的物品数量 就地存贮的物品未经运输 所以其单位运价ci n 1 0 i 1 2 m 第3节产销不平衡的运输问题 第3节产销不平衡的运输问题 数学模型 第3节产销不平衡的运输问题 2 总产量 总销量 第3节产销不平衡的运输问题 解题思路 为借助于产销平衡的表上作业法求解 增加一个假想的产地Am 1 由于实际上它不存在 因而由它发往各个销地的物品数量xm 1 j j 1 2 n 就是各销地Bj所需物品的欠缺额 欠缺的物品未经运输 所以其单位运价cm 1 j 0 j 1 2 n 第3节产销不平衡的运输问题 第3节产销不平衡的运输问题 数学模型 第3节产销不平衡的运输问题 例12 用表上作业法求解下述运输问题的最优解 第3节产销不平衡的运输问题 例12 解 不产销平衡