(典型例题)《运筹学》运输问题汇总

1、一运筹学运输问題一 2008/11 第3章 运输问题 Transportation problem 2008/11 一运筹学运输问題一 3.1 运输问题的典例和数学模型 一、典例： 某食品公司经营糖果业务，公司下设三个工厂Al、A2、 A3,四个销售门市部Bl、B2、B3、B4。已知每天各自的生产 屋、销售量及调运时的单位运输费用情况。问：如何调运町 使总费用最小？ 生产量：A1 - 7 吨，A2 - 4 吨，A3 9吨 销售量：B1 - 3 吨，B2 - 6 吨，B3 - 5 吨，B4 - 6 吨 运筹学运输问題一 2008/11 2008/11 一运筹学运输问題一 二、建立模型 设 Xij

2、第i产地到第j销地之间的调运量，则有 3 4 Min z = S Xjj i=l j=l 调运运筹学运输问題一 2008/11 产量限制 XH+X12+X13+X=7 X21 +X22+X23+X24 二 销量限制 X31+X32+X33+X34 Xll+X21+X31=3 X14+X24+X34=6 2 32 3 2 32 3 1 1A1 1A X X 6 5 - - - - 2 32 3 + + 运筹学运输问題一 2008/11 一般模型表示： 设有个 m产地、n个销地，其中第 i个产地的产疑为 a.第 j个 销地的销量为br ILSao 若第 i个产地到第 j个销地每调运单 位物资的运费

3、力 C 则使总费用最少的调运模世为： m I) Min z = S S %“门 i=l j=i z.xa = Ch (i = l,2,.m) m Di产 bj (ji2卫) 4=1 Xij no (i = l 2 ,m; j = l 2 ,n) 2008/11 一运筹学运输问題一 三.模型的特点 1.变量数:mxii个 2约束方稈数：ni+n个 最人独立方程数：in+n-l 3.系数列向量结构: 第 i个分量 第 m+j个分量 运筹学运输问題一 2008/11 xu X12 Xln X21 X22 X2n %2 i=l c 1 1 0 0 .0 . 0 0 i=2 0 0 : 0 1 1 1

4、0 : 0 . U . i 二 m 0 : 0 0 0 0 * 0 1 : 1 1 . 丄 j=l 1 0 0 1 0 0 . 1 0 0 j 二 2 0 1 : 0 0 1 .0 . n 1 : : 0 . V i=n 0 : 01 0 0 1 . 0 : 0 1 2008/11 - 一运筹学运输问題一 3.2 运输问题的表上作业算法和程序求 解 表上作业法步骤：初始方案最优性检验改进方案 一、 初始方案的确定 1. 最小元素法 2. Vogel 法 二、 最优性检验 1. 闭回路法 2. 位势法 三、 方案改进方法 在闭回路内改进。2008/11 一运筹学运输问題一 Z=C-C3+C23C

5、2i = l=Qii Bl B2 B3 B4 产量 AZ=C12-C14+C24-C22=2=Q12 Al (0) (2) 5 2 7 A2 3 (2) (1) 1 4 A3 (9) 6 (12) 3 9 销量 3 6 5 6 2008/11 一运筹学运输问題一 Vogel 法： B1 B2 B3 B4 产at A1 5 2 7 A2 3 1 4 A3 6 3 9 销 3 6 5 6 产销平衡表 B1 B2 B3 B4 行两垠小元索Z怎 A1A1A2A2A3A3 两小素耒 列最元Z 单位运价表 涂 B1 B2 B3 B4 产量 A1 /,.Td A Q 7 O A2 3 (i) -1 (-1)

6、 4 A3 (10) 6 / 1 9 (12) 3 销量 3 6 5 6 A1 A2 Bl B2 B3 B4 1 1 , in 1 4 S ) 产销平衡表 运筹学运输问題一 2008/11 2008/11 一运筹学运输问題一 检验数表 Bl Bl B3 B4 产量 Al (0) 5 2 7 A2 3 (1) 1 4 A3 6 (12) 3 9 销量 3 6 5 6 B1 B1 B3 B4 行位势 B1 B1 B3 B4 A1 (3) 3 10 1 7 A1 JLx JL 11 3 10 A2 1 (1) 8 -1 A2 1 9 2 8 A3 02) (52) 4 A3 7 4 10 5 列位势

7、 2 8 2 9 位势法： 位势表： 单位运价表 1. 数字格处上添上刈曲的运价： 2. 计算行位势和列位势； 令 11产 1,则依 Cij=Ui+Vj 计算各 5 和 Vj 3. 计算空格处位势； 九 ij=Ui+Vj 4. 计算空格处检验数: 运筹学运输问題一 2008/11 程序求解: (1)使川LINDO程序求解：同求解LP模型o (2)使用EXCEL求解: 2008/11 运筹学运输问題一 3. 3 产销不平衡运输问题及其应用 一、产俏不平衡问题 1.产 销 n Min z= 2 X Sy X) ) i=lj=l 工 a (i=12m) : 二 )Dij = bj 012卫) r-1

8、 兀卩 AO (i = l,.,m;j = l,.,n) m n m Min z= E E CijXij+oXi，n+i i=l j=l i=l r n+l 工勺=di (i = 12m) y=i m 工兀= (j= 1,2,n + l) /=i 兀 20 (i= 1,m;j = 1,n,n + l)2008/11 一运筹学运输问題一 产销问题单位运价农 Bl B2 - Bn B11+1 产量 Al G i Ci2 Cm 0 ai A2 i i C21 1 1 C _ c22 C211 1 1 0 1 1 a? ! 0 1 Am 1 Cnii 0 1 Cm2 0 1 Cmn 1 0 1 1 3

9、iu 销量 bi b2 bn XaiLb j 2008/11 一运筹学运输问題一 2.销产 m n n Min z= Z YCijgj +Eo-xm+p j i=l j=l j=l n n Min z=工工 (i= 1,2,jn,m+ 1) (i= 1,m,m + l; j PHJ 工 p(ji2,n) 运筹学运输问題一 2008/11 18 销产问题单位运价表 Bl B2 - Bn 产量 A1 G i Ci2 Cm ai A2 1 1 C21 1 1 C22 一 C211 1 1 a2 1 1 1 1 Am 1 ClDl 1 1 1 1 Cmn 1 1 elm Am+i 0 0 0 Eb j

10、工 ai 销量 bi b2 - bn 运尊学运输问題一 二、应用模型 例一：某工厂按合同规定 必须于当年的每个季度末 分别提供10、15、25、20 台同一规格的柴油机。已 知该厂的生产能力及生产 每台柴油机的成本如表示。 又如果生产出来的柴油机 当季不交货，每台每积压 一个季度需要存储维护费 用0.15万元。要求在完成 合同的情况下，做出使全 年生产费用最小的决策。2008/11 季 生产能力 单位成本 度 冶） （万元/台） I 25 10. 8 n 35 11. 1 HI 30 11. 0 IV 10 11. 3 一运筹学运输问題一 2008/11 模型: 设Xlj第i季度生产，用于第j

11、季度交货的数量。 min z=工工 5j 乂门 i=lj=l X11+X12+X13+X1425 需求： %22+*23+*2435 *33+%3430 X44W10 I x* 0 , (i=l, , 4; j=l, , 4) 2008/11 运筹学运输问題一 单位费用表： 单位：万元 1 II III IV I 10. 8 10. 95 11. 10 11. 25 n M 11. 10 11. 25 11. 40 HI M M 11. 00 11. 15 IV M M M 11. 30 XU =10 x12+x22 =15 x13+x23+x33 =25 X14+X24+X34+X4, 产2

12、0 obj. 1 III IV 一运筹学运输问題一 2008/11 例二: 某餐馆承办宴会，每晚连续举行，共举行五次。 宴会上需用特殊的餐巾，根据参加的人数，预计每 晚的需要量为：第一天1000条，第二天700条，第三 天800条，第四天1200条，第五天1500条，五天之后, 所有的餐巾作废。宴会中用过的餐巾经过洗涤处理 后可以重复使用，这样可以降低使用成本。已知每 条新餐巾需要1元的费用，送洗时可选择两种方式： 快洗仅需要一天时间，每条洗涤费用为0. 2元，慢洗 需要两天时间，每条洗涤费用0.1元。问：如何安排, 可使总费用最低？ 2008/11 一运筹学运输问題一 建立模型： 设 勺一第

13、 j天使用新毛山的数屋:：丫门一第 i天送第 j 天使用快洗 餐巾的数量；2门一第 i天送第 j天使用慢洗餐巾的数量； Min z=EXj+E E0. 2丫门+刀 EO. lz 一运筹学运输问題一 2008/11 需求约束 第一天：X=1000 第二天：x2+y12= 供应约朿 新购餐 I : X1+X2+X3+X.1+X55200 第一天送洗：yi2+zl3+zl-1+zl51000 第二天送洗：y23+Z24+Z25S700 第三天送洗：y34+z35800 第四天送洗：y450 ZijhO, 一运筹学运输问題一 2008/11 一 23 一运筹学运输问題一 例三： 有A、B、C三个化肥厂

14、供应四个地区I、II. III. IV的农用化肥， 三个工厂每年各自的产量为A-50万吨，B60万吨，C50万吨。四个 地区的需求量分别是I地区最高50万吨，最低孔万吨，II地区为70万 吨，III地区为30万吨以下，IV地区不低于10万吨。问：如何调运，可 使总的调运费用最小？单位调运费用如下表所示。 单位运价表 单位：万元/万吨 Bl B2 B3 B4 产量 设Xij第i工厂 Al 16 13 22 17 50 调至第j需求地区 A2 14 13 19 15 60 的化肥数量 A3 19 20 23 50 产销平衡2008/11 一运筹学运输问題一 2008/11 销量 30-50 70

15、0-30 10- 一运筹学运输问題一 2008/11 26 一运筹学运输问題一 三.扩大的运输问题 例：在前面的例题中,若既可以从 Ai运到 Bj,也可以经过中间站 Tl、T2、T3、T4 或者 Ai、Bj转运，称扩大的运输问题。 几点说明： 1所有的产地、销地、中间站均视作产地、销地； 2. 转运量可定位总的产最之和； 3. 不能出现循环倒运现象，允许自身往自身最多调运一次， 运价为 Gj二 0； 4. 实际产地产量为转运量与该产地实际产量之和，实际销地 销疑为转运虽与实际销疑之和。2008/11 一25一 产销半衡衣 2008/11 沁 A1 A2 A3 T1 T2 T3 T4 B1 B2 B3 B4 产量 A1 0 1 3 2 1 4 3 3 11 3 10 27 A2 1 0 3 5 2 1 9 2 8 24 A3 3 一 0 1 2 3 4 10 5 29 T1 2 3 1 0