第三章运输问题(研究生).ppt

第三章 运输问题 本章主要内容 第一节 运输问题的数学模型及其特征 1. 运输问题的定义 2. 运输问题的数学模型 运输问题的约束方程组系数矩阵及特征 3. 运输问题的特征 闭回路 第二节 运输问题的求解--表上作业法 第一步：编制初始调运方案 最小元素法 Vogel 法 第二步：计算各非基变量的检验数 1. 闭回路法 2. 位势法 位势及检验数的求法 第四步：调整调运方案 表上作业法计算中应注意的问题 第三节 产销不平衡的运输问题及应用 运输问题的求解软件（WINQSB） 作业：用表上作业法求解下列运输问题. 检验数全部非负，已经是最优调运方案； 总费用 C*= 2×3 + 9×0 + 7×6 + 3×5 + 4×3 + 2×4 = 83 6 4 8 3 需求量 7 5 2 4 8 A3 5 2 4 3 1 A2 9 7 10 9 2 A1 库存量 B4 B3 B2 B1 0 5 4 3 3 6 0 -6 -5 2 9 7 7 3 5 3 1 11 3 1.解的情况 唯一：非基变量检验数全部大于0； 无穷多解：至少存在一个非基变量检验数等于0。 2.退化情况： 在确定初始基可行解的时候，当填(i,j)格子时，若ai=bj, 则xij=ai=bj, 但此时只能划去一行或一列，在后面的填充过程中相应格子要填0。 3.调整时，若闭回路上出现两个或两个以上偶顶点取值同时达到最小，只能选一个变量出基。 课堂练习 用表上作业法求解下列运输问题. 6 5 6 3 需求量 9 5 10 4 7 A3 4 8 2 9 1 A2 7 10 3 11 3 A1 供应量 B4 B3 B2 B1 6 5 6 3 需求量 9 5 10 4 7 A3 4 8 2 9 1 A2 7 10 3 11 3 A1 供应量 B4 B3 B2 B1 4 3 1 3 6 3 6 5 6 3 需求量 9 5 10 4 7 A3 4 8 2 9 1 A2 7 10 3 11 3 A1 供应量 B4 B3 B2 B1 4 3 1 3 6 3 0 3 10 -1 2 -5 9 1 2 1 -1 10 12 调整量为 min{3,1}=1，出基变量为x23. 6 5 6 3 需求量 9 5 10 4 7 A3 4 8 2 9 1 A2 7 10 3 11 3 A1 供应量 B4 B3 B2 B1 5 3 1 3 6 2 最优解: 0 3 10 -2 3 -5 9 0 2 2 1 9 12 由于x11的检验数为0，所以最优解不唯一。 6 5 6 3 需求量 9 5 10 4 7 A3 4 8 2 9 1 A2 7 10 3 11 3 A1 供应量 B4 B3 B2 B1 5 1 3 3 6 2 0 3 10 -2 3 -5 9 2 2 1 9 12 0 最优解: 表上作业法是以产销平衡为前提的： 实际中，往往遇到产销不平衡的运输问题 1.产大于销（供过于求） 2.销大于产（供不应求） 产销不平衡运输问题向产销平衡运输问题的转化 产大于销的运输问题： 数学模型 设xi n+1 是产地Ai 的储存量，化成标准形 其中 引入一个虚拟的销地（需求量等于 ），并令各个产地到虚拟销地的单位运费为0。 产小于销的运输问题： 引入一个虚拟的产地（产量等于 ）， 并令该虚拟产地到各销地的单位运费为0。 总供应量为19千吨，而总需求量为15千吨 例2： A1、A2、A3三个蔬菜生产地生产的蔬菜主要供应B1、B2、B3、B4四个城市。已知三个产地今年的蔬菜产量预计分别为7千吨、5千吨和7千吨；四个城市今年的蔬菜需求量分别为2千吨、3千吨、4千吨和6千吨；从每个蔬菜产地平均运输1千吨蔬菜到各个城市的单位费用(万元)见下表，你能否替他们编制一个总运费最省的蔬菜调运方案？ 单位运费 B1 B2 B3 B4 供应量 A1 2 11 3 4 7 A2 10 3 5 9 5 A3 7 8 1 2 7 需求量 2 3 4 6 ? 6 2 9 4 B4 4 4 3 2 需求量 7 0 1 8 7 A3 5 0 5 3 10 A2 7 0 3 11 2 A1 供应量 B5 B3 B2 B1 需求地 生产地 0 0 -2 2 0 4 3 0 8 2 5 7 2 3 3 4 3 2 2 2 3 8 7 最优解中x15=2, x25=2，表示两个产地没有运出去的蔬菜量。 假如例2中各产地的蔬菜总产量不是19千吨，而是12千吨，就成了一个供不应求的运输问题。 单位运费 B1 B2