《运筹学》课程电子教案（PPT课件讲稿）第四章 运输问题

Q第四章运输问题 本章要求: 掌握运输问题的数学模型 掌握运输问题的求解方法 化产销不平衡问题为平衡问题 学会用计算机求解 OR2

OR2 1 第四章 运输问题 本章要求： 掌握运输问题的数学模型 掌握运输问题的求解方法 化产销不平衡问题为平衡问题 学会用计算机求解

Q4.1运输问题的数学模型 ◆运输问题一般表述为: 某企业有m个产地(生产厂)Ai,其产量 分别为a,i=-1,2,m,n个销地(销售商) B,其销售量分别为b,j=1,2,,n,从A到B 的每单位物资的运费为Cj要求拟定总运 费最小的调运方案。 OR2

OR2 2 4.1运输问题的数学模型  运输问题一般表述为： 某企业有m个产地（生产厂）Ai，其产量 分别为ai, i=1,2,…m, n个销地（销售商） Bj，其销售量分别为bj, j=1,2,…n,从Ai到Bj 的每单位物资的运费为Cij.要求拟定总运 费最小的调运方案

输表 地 产地B1B2 Bn产量 A C11C al C21C2 a2 A CmlCm2 mn 销量」bb2 br OR2

OR2 3 运输表 . 销地 产地 B1 B2 … Bn 产量 A1 C11 C12 … C1n a1 A2 C21 C22 … C2n a2 … … … … … … Am Cm1 Cm2 … Cmn am 销量 b1 b2 … bn

运输问题的数学模型 设从A到B的运输量为x,(假定产销平衡) 则总运费:minZ=∑Cxj 产量约束:∑x=ai=1,2,m 销量约束:如x=bj=1,2,n, 非负性约東:xj≥0 OR2

OR2 4 运输问题的数学模型 设从Ai 到Bj的运输量为xij,（假定产销平衡） 则总运费： minZ= ∑∑ Cij xij 产量约束： ∑xij = ai i=1,2,…m, 销量约束： ∑xij = bj j=1,2,…n, 非负性约束： xij ≥0 n m n j=1 i=1 j=1 m i=1

4.2表上作业法 ◆计算步骤: 1、给出初始方案 2、检验是否最优 3、调整调运方案,Goto2 OR2

OR2 5 4.2表上作业法  计算步骤： 1、给出初始方案 2、检验是否最优 3、调整调运方案 , Go to 2

Q例题1 某建材公司有三个水泥厂A1、A、A3, 四个经销商B1、B2、B3、B4,其产量 销量、运费如下表 销地 产地B1B2B3B4产量 Al A2 842-3 7742 3594 9 A3 6 4 销量 14 OR2

OR2 6 例题1  某建材公司有三个水泥厂A1、A2、A3， 四个经销商B1、B2、B3、B4，其产量、 销量、运费如下表： 销地 产地 B1 B2 B3 B4 产量 A1 A2 A3 8 4 2 7 7 4 3 5 9 2 1 6 1 9 4 销量 3 2 4 5 14

4.2.1求初始调运方案 ◆用最小元素法(也可用西北角法或 vogel 法)给出初始基可行解: 在运费表中找出最小元素,尽最大 可能用完一个厂的产量,或满足一个商 家的销量。得到满足者用线划去。 逐次寻找最小元素,直至分配完毕 注意:如填写一个数字同时满足了 商,则需在同行或同列中填写 个数字0,以保证恰好有m+n-1个数字 OR2

OR2 7 4.2.1求初始调运方案  用最小元素法（也可用西北角法或vogel 法）给出初始基可行解： 在运费表中找出最小元素，尽最大 可能用完一个厂的产量，或满足一个商 家的销量。得到满足者用线划去。 逐次寻找最小元素，直至分配完毕 注意：如填写一个数字同时满足了 一厂一商，则需在同行或同列中填写一 个数字0，以保证恰好有m+n-1个数字

q例1之初始方案(P119 最小元素法:圈定C24 B1B2B3B4 量 A18 A24 774 3594 /594 A32 销量|3 OR2

OR2 8 例1 之初始方案（P119） 最小元素法：圈定C24 B1 B2 B3 B4 产量 A1 8 7 3 2 1 A2 4 7 5 /5 9 4 A3 2 4 9 6 4 销量 3 2 4 5

例1初始方案(续1) 圈定C31 B1B2B3B4 A18 A2 3-594 o/5|94 A3 /3 销量/3 OR2

OR2 9 例1初始方案（续1） 圈定C31 B1 B2 B3 B4 产量 A1 8 7 3 2 1 A2 4 7 5 /5 9 4 A3 /3 4 9 6 4 1 销量 3 2 4 5

例1初始方案(续2) ◆圈定C13 B1B2B3B4产量 at A2 7742 o/5Y4 A3 ②/3 销量 435 OR2

OR2 10 例1初始方案（续2）  圈定C13 B1 B2 B3 B4 产量 A1 8 7 /1 2 1 A2 4 7 5 /5 9 4 A3 /3 4 9 6 4 1 销量 3 2 4 3 5