[经管营销]第二章-23运输问题.pptVIP

2.4 运输问题 2.4.1 运输问题的一般模型 2.4.2 表上作业法 2.4.3 产销不平衡问题 3.运输问题网络图 二.模型 运输问题的一般模型 有m个产地生产某种物资，有n个地区需要该类物资. 令a1, a2, …, am表示各产地产量，b1, b2, …, bn表示各销地的销量，?ai=?bj 称为产销平衡。 设xij表示产地 i 运往销地 j 的物资量，cij表示对应的单位运费，则我们有运输问题的数学模型如下： 运输问题的表格表示 对偶变量法(10) σ14= c14-(u1+v4)=3-(- 4+0)=7 7 5 5 对偶变量法(11) σ24= c24-( u2+v4)=7-(-2+0)=9 9 5 5 7 对偶变量法(12) σ31= c31-(u3+v1)=5-(6+10)=-11 -11 5 5 7 9 对偶变量法(13) σ32= c32-( u3+v2)=9-(6+6)=-3 -3 5 5 7 9 -11 * 2.4.1 运输问题的一般模型 一. 一般提法 1.产销平衡问题 A1（a1） A2（a2） 产地： . . . Am（am） B1（b1） B2（b2） 销地： . . . Bn（bn） 已知从Ai到Bj的单位运价为cij,且 问题：如何制定最合理的物资调运方案， 使总运费最低？ 2.产销不平衡问题（化为产销平衡问题来解决） 供不应求： 供大于求： A2 A3 B2 A1 B3 B4 B1 a2=27 a3=19 b1=22 b2=13 b3=12 b4=13 a1=14 供应量 供应地 运价 需求量 需求地 6 7 5 3 8 4 2 7 5 9 10 6 供应地约束 需求地约束 设从Ai 到Bj的运量是xij(i=1,2,3;j=1,2,3,4) 运输问题有m?n个决策变量，m+n个约束条件。由于有产销平衡条件，只有m+n–1个约束相互独立，因此，运输问题的基变量只有m+n–1 个. 模型特点： （1）有有限最优解 （2）系数矩阵中每列只有两个1，其余全为0。 （3）基变量的个数=m+n-1 2.4.2 表上作业法 运输问题的求解步骤 确定初始可行方案 西北角法 最小元素法** 沃格尔法 最优性检验 闭回路法 位势法** 调整新方案： 闭回路法** 最小元素法（1） 方法：最先满足最小的运费安排调运。 一.确定初始可行方案-----最小元素法 最小元素法（2） 最小元素法（3） 最小元素法（4） 最小元素法（5） 最小元素法（6） 初始可行方案为：x11=1，x14 =13 x21 =2 ，x22 =13 x23 =12, x31 =19 相应的运费为：Z0=232 方法评价：优点：较简便易行， 有目标观念。 缺点：只从单一格出发， 无全局观念。 注：（1）有数字格表示基变量， 其个数为m+n-1，空格表示非基变量。 （2）每填上一个数后，则只能划去一行（或一列）。 （3）若中间过程填上一个数后，同时划去一行和一列，有数字格的个数将少1个，这时，要在所划去的该行（或该列）上任意一格填一个0，此格当有数格对待。 二.最优性检验---位势法（对偶变量法） 方法：⑴ 由数字格cij=ui+vj计算位势 ui (行位势), vj (列位势), （先任意指定一个位势值） ⑵ 计算检验数σij= cij -（ui+vj） ( 数字格检验数为0) 验证检验数公式σij= cij -（ui+vj） σij= cij –cBB-1pij