第五章货物运输,方案的优化方法.ppt

* 本章重点 第五章 货物运输方案的优化方法 产销平衡运输问题的数学模型 产销平衡运输问题的表上作业法  本章内容 运输问题的数学模型 表上作业法 运输问题的扩展 §1 货物运输问题 bn … b2 b1 需求量 Bn … B2 B1 需方 供方 Am A2 A1 am a2 a1 供应量 供需平衡 运价 bn … b2 b1 需求量 Bn B2 B1 需方 供方 Am A2 A1 am a2 a1 供应量 cmn cm2 cm1 c2n c22 c21 c1n c12 c11 … … … … 如何建立供需搭配，使总的运输费用最小？ 供 需 平 衡 表 数学模型 设从Ai到Bj的物资运量为xij ， 产销平衡运输问题的数学模型。 Ai的产品全部供应出去 Bj的需求全部得到满足 m n 平衡表、运价表和二为一： 约束条件或解可用产销平衡表表示: ui?vj无约束 （i=1,2, …,m;j=1,2, …,n) ui vj 设ui,vj为对偶变量，对偶问题模型为 m个 n个 §2 初始调运方案的编制 计算步骤： (1) 找出初始调运方案。即在(m×n)产销平衡表上给出m+n-1个数字格。(最小元素法或差值法） (2) 求检验数。（闭回路法或位势法） 判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。 (3) 对方案进行改善，找出新的调运方案。（表上闭回路法调整） 确定m+n-1个基变量 (4) 重复（2）、（3），直到求得最优调运方案。 空格 例 运输问题供需平衡表和运价表如下，求最优调运方案。 6 5 6 3 需求量（T） 9 5 10 4 7 A3 4 8 2 9 1 A2 7 10 3 11 3 A1 供应量（T） B4 B3 B2 B1 供 需 ⑴最小元素法 3 1 4 6 3 3 Z=4×3+3×10+3×1+1×2+6×4+3×5=86 该方案总运费： . ② 差额法 分别计算各行、各列次小、最小运价的差额，优先在最大差额处进行供需搭配。 步骤： 10 计算未划去行、列的差额； 20 找出最大差额对应的最小元素cij进行供需分配； 30 在未被划去的行、列重新计算差额。 6 5 6 3 销量 9 A3 4 A2 7 A1 供量 B4 B3 B2 B1 销 产 6 3 1 5 2 列差额 1 5 10 4 7 A3 1 8 2 9 1 A2 0 10 3 11 3 A1 行差额 B4 B3 B2 B1 6 5 6 3 销量 9 A3 4 A2 7 A1 供量 B4 B3 B2 B1 销 产 6 3 1 2 列差额 2 5 10 4 7 A3 1 8 2 9 1 A2 0 10 3 11 3 A1 行差额 B4 B3 B2 B1 3 6 5 6 3 销量 9 A3 4 A2 7 A1 供量 B4 B3 B2 B1 销 产 6 2 1 2 列差额 5 10 4 7 A3 1 8 2 9 1 A2 0 10 3 11 3 A1 行差额 B4 B3 B2 B1 3 3 6 5 6 3 销量 9 3 A3 4 A2 7 A1 供量 B4 B3 B2 B1 销 产 6 2 1 差额 5 10 4 7 A3 6 8 2 9 1 A2 7 10 3 11 3 A1 差额 B4 B3 B2 B1 3 5 1 2 §3 调运方案的改进 ① 闭回路法 闭回路：从空格出发顺时针(或逆时针)画水(或垂直)直线，遇到填有运量的方格可转90°，然后继续前进，直到到达出发的空格所形成的闭合回路。 调运方案的任意空格存在唯一闭回路。 6 5 6 3 销量 9 3 6 A3 4 1 3 A2 7 2 5 A1 供量 B4 B3 B2 B1 销 产 差额法方案 一、最优调运方案的判定 ① 闭回路法 闭回路：从空格出发顺时针(或逆时针)画水平(或垂直)直线，遇到填有运量的方格可转90°，然后继续前进，直到到达出发的空格所形成的闭合回路。 调运方案的任意空格存在唯一闭回路。 6 5 6 3 销量 9 3 6 A3 4 1 3 A2 7 2 5 A1 供量 B4 B3 B2 B1 销 产 3 1 4 6 3