( (典型例题典型例题) )运筹学运运筹学运输问题输问题3.1 3.1 运输问题的典例和数学模型运输问题的典例和数学模型一、典例： 某食品公司经营糖果业务，公司下设三个工厂A1、A2、A3，四个销售门市部B1、B2、B3、B4。已知每天各自的生产量、销售量及调运时的单位运输费用情况。问：如何调运可使总费用最小？生产量：A17吨， A2 4吨， A3 9吨销售量：B1 3吨，B2 6吨，B3 5吨，B4 6吨产地单位运价销地B1 B2 B3 B4 A1A2A3 3 11 3 10 1 9 2 8 7 4 1052008/112-运筹学 运输问题-调运示意图调运示意图A1A2A3B1B2B3B47吨4吨9吨3吨6吨5吨6吨x11x12x13x14x21x22x23x24x31x32x33x34产地销地2008/113-运筹学 运输问题-二、建立模型二、建立模型设 xij第i产地到第j销地之间的调运量，则有Min z = cij xij34i=1 j=1x11+x12+x13+x14=7x11+x21+x31=3xij0,(i=1,2,3；j=1,2,4)产量限制销量限制x21+x22+x23+x24=4x31+x32+x33+x34=9x12+x22+x32=6x13+x23+x33=5x14+x24+x34=62008/114-运筹学 运输问题-一般模型表示：一般模型表示： 设有个m产地、n个销地，其中第i个产地的产量为ai，第j个销地的销量为bj，且ai=bj。若第i个产地到第j个销地每调运单位物资的运费为cij，则使总费用最少的调运模型为：Min z = cij xijni=1 j=1m2008/115-运筹学 运输问题-三、模型的特点三、模型的特点1.变量数：mn个2.约束方程数：m+n个 最大独立方程数：m+n-13.系数列向量结构：Pij=0110第i个分量第m+j个分量2008/116-运筹学 运输问题-x11 x12 x1n x21 x22 x2n , xm1 xm2 xmn1 1 1 0 0 0 0 0 00 0 0 1 1 1 0 0 00 0 0 0 0 0 1 1 11 0 0 1 0 0 1 0 00 1 0 0 1 0 0 1 00 0 1 0 0 1 0 0 1i=1i=2i=mj=1j=2j=n2008/117-运筹学 运输问题- 3.2 3.2 运输问题的表上作业算法和程序求运输问题的表上作业算法和程序求解解表上作业法步骤: 初始方案最优性检验改进方案一、初始方案的确定1.最小元素法最小元素法2.VogelVogel法法二、最优性检验1.闭回路法闭回路法2.位势法位势法三、方案改进方法在闭回路闭回路内改进。2008/118-运筹学 运输问题-产地销地A1 A2 A3B1 B2 B3 B4产地销地A1 A2 A3B1 B2 B3 B4产地销地A1 A2 A3B1 B2 B3 B4产量销量3 11 3 10 1 9 2 8 7 4 10 5 6343133 6 5 67 4 93 6 5 67 4 9产量销量363521(1) (2)(1)(-1)(10)(12)z=c11-c13+c23-c21=1=11z=c12-c14+c24-c22=2=12(0)(2)(2)(9)(1)(12)单位运价表产销平衡表2008/119-运筹学 运输问题-产地销地A1 A2 A3B1 B2 B3 B47 4 9产量销量3 6 5 6635213产地销地A1 A2 A3B1 B2 B3 B4行两最小元素之差列两最小元素之差3 11 3 10 1 9 2 8 7 4 10 5 0 1 12 5 1 3 0 1 22 - 1 30 1 -2 - 1 27 6 - - 1 2Vogel法:产销平衡表2008/1110-运筹学 运输问题-产地销地A1 A2 A3B1 B1 B3 B4 3 10 1 8 4 5 位势法:(3) (9)(7)(-2)(1)(-2)2.计算行位势和列位势；令u1=1，则依cij=ui+vj 计算各ui和vj 3.计算空格处位势；ij=ui+vj行位势列位势 12-1-42894.计算空格处检验数：ij=cij- ij1.数字格处上添上对应的运价；销地A1 A2 A3B1 B1 B3 B43 11 3 10 1 9 2 8 7 4 10 5 产地单位运价表位势表:2008/1111-运筹学 运输问题-产地销地A1 A2 A3B1 B1 B3 B47 4 9产量销量3 6 5 6635213(0) (2)(2)(9)(1)(12)检验数表2008/1112-运筹学 运输问题-程序求解：程序求解：(1) 使用LINDO程序求解: 同求解LP模型。(2) 使用EXCEL求解： 2008/1113-运筹学 运输问题-3.3 3.3 产销不平衡运输问题及其应用产销不平衡运输问题及其应用Min z= cij xijni=1j=1m一、产销不平衡问题1产销Min z= cijxij+0xi,n+1ni=1 j=1mi=1m2008/1114-运筹学 运输问题-产地销地A1 A2 AmB1B2BnC11C12C1n C21C22C2n Cm1Cm2CmnBn+1 产销问题单位运价表销量产量b1b2bna1 a2 amaibj2008/1115-运筹学 运输问题-Min z= cij xijni=1j=1m2销产Min z= cijxij +0xm+1,jni=1 j=1mj=1n2008/1116-运筹学 运输问题-产地销地A1 A2 AmB1B2BnC11C12C1n C21C22C2n Cm1Cm2CmnAm+1销产问题单位运价表0 0 0销量产量b1b2bna1 a2 ambjai2008/1117-运筹学 运输问题- 例一：某工厂按合同规定必须于当年的每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂的生产能力及生产每台柴油机的成本如表示。又如果生产出来的柴油机当季不交货，每台每积压一个季度需要存储维护费用0.15万元。要求在完成合同的情况下，做出使全年生产费用最小的决策。季度生产能力(台)单位成本(万元/台)2535301010.811.111.011.3二、应用模型2008/1118-运筹学 运输问题-模型：模型：设 xij第i季度生产，用于第j季度交货的数量。obj. min z= cij xiji=1j=1 4 4x11+x12+x13+x1425 x22+x23+x2435 x33+x3430 x4410x11 =10x12+x22 =15x13+x23+x33 =25x14+x24+x34+x44=20xij 0 ,(i=1,4;j=1,4)供应：需求：2008/1119-运筹学 运输问题-单位费用表：单位费用表： 10.8 10.9511.10 11.25 M 11.10 11.25 11.40 M M 11.00 11.15 M MM 11.30单位：万元供应需求2008/1120-运筹学 运输问题-例二：例二： 某餐馆承办宴会，每晚连续举行，共举行五次。宴会上需用特殊的餐巾，根据参加的人数，预计每晚的需要量为：第一天1000条，第二天700条，第三天800条，第四天1200条，第五天1500条，五天之后，所有的餐巾作废。宴会中用过的餐巾经过洗涤处理后可以重复使用，这样可以降低使用成本。已知每条新餐巾需要1元的费用，送洗时可选择两种方式：快洗仅需要一天时间，每条洗涤费用为0.2元，慢洗需要两天时间，每条洗涤费用0.1元。问：如何安排，可使总费用最低？2008/1121-运筹学 运输问题-建立模型：建立模型：设 xj第j天使用新毛巾的数量；yij第i天送第j天使用快洗 餐巾的数量；zij第i天送第j天使用慢洗餐巾的数量；第一天：x1=1000第二天：x2+y12=700第三天：x3+z13+y23=800第四天：x4+z14+z24+y34=1200第五天：x5+z15+z25+z35+y45=1500需求约束供应约束新购餐巾： x1+x2+x3+x4+x55200第一天送洗：y12+z13+z14+z151000第二天送洗：y23+z24+z25700第三天送洗：y34+z35800第四天送洗：y451200xj0，yij0，zij0，（i=1,4；j=1,5）Min z=xj+0.2yij+0.1zij2008/1122-运筹学 运输问题-新 购 第一天第二天第三天第四天111110 M0.20.10.10.10MM0.20.10.10MMM0.20.10供应需求产量销 量5200 1000 700 800 1200MMM0.20.101000700800120015003700产销平衡表2008/1123-运筹学 运输问题-例三： 有A、B、C三个化肥厂供应四个地区、的农用化肥，三个工厂每年各自的产量为A-50万吨，B-60万吨，C-50万吨。四个地区的需求量分别是地区最高50万吨，最低30万吨，地区为70万吨，地区为30万吨以下，地区不低于10万吨。问：如何调运，可使总的调运费用最小？单位调运费用如下表所示。产地销地A1A2A3B1 B2 B3 B4 产量销量16 13 22 17 14 13 19 15 19 20 23 单位运价表50 60 5030-50 70 0-30 10-单位：万元/万吨设 xij-第i工厂调至第j需求地区的化肥数量2008/1124-运筹学 运输问题-A B C D 161613221717 14141319151519192023 M MM0M0M0供应需求产量销 量50 60 50 50 302070301050产销平衡表2008/1125-运筹学 运输问题-三、扩大的运输问题三、扩大的运输问题例：在前面的例题中，若既可以从Ai运到Bj，也可以经过中间站T1、T2、T3、T4或者Ai、Bj转运，称扩大的运输问题。几点说明：1.所有的产地、销地、中间站均视作产地、销地；2.转运量可定位总的产量之和；3.不能出现循环倒运现象，允许自身往自身最多调运一次，运价为Cij=0；4.实际产地产量为转运量与该产地实际产量之和，实际销地 销量为转运量与实际销量之和。2008/1126-运筹学 运输问题-A1 A2 A3T1 T2 T3 T4B1 B2 B3 B4A1 A2 A3T1 T2 T3 T4B1 B2 B3 B40 1 3 1 0 - 3 - 02 1 4 3 3 5 - 2 1 - 2 33 11 3 10 1 9 2 8 7 4 10 52 3 1 1 5 - 4 - 2 3 2 33 1 7 11 9 4 3 2 10 10 8 50 1 3 2 1 0 1 1 3 1 0 2 2 1 2 0 2 8 4 6 4 5 2 7 1 8 2 4 1 - 2 6 2 4 1 1 8 5 8 - 4 2 2 2 6 7 4 60 1 4 2 1 0 2 1 4 2 0 3 2 1 3 0产销产量销量27 24 2920 20 20 2020 20 20 2020 20 2020 20 20 2023 26 25 26产销平衡表2008/1127-运筹学 运输问题-结束结束