版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
走讫点不同的单一路径规划问题这类问题可以采用网络图的最短路径算法(Dijkistra)进行求解。已知一个由链和节点组成的网络,其中节点代表由链连接的点。链代表节点之间的距离(或时间以及距离和时间的加权平均),Dijkstra算法的基本思想是:从始点Vs出发,逐步地向外探寻最短路,与每个节点对应,记录下一个数Wi,它表示从Vs到该点Vi的最短路。执行过程中分为已解节点集P和未解点集T,搜寻T中所有与P中节点直接相连的点,分别计算这些点到起始点的最短距离,进一步从中确定具有最短距离的节点,让该点从T集转入P集,并记录下该点到起始点的距离,以及所经过的P中的节点(路径)。经过若干次循环后,一旦绺Vp进入了P集合,计算结束,反向追踪获得最短距离的路径,就是所要搜索的最短路径。[实例5-6]起讫点不同的单一路径规划问题求解某公路网络如图所示,寻找从Vs到Vp之间行车时间最短的路线。节点代表公路的连接处,每条链上都标有相应的行车距离。Vs90V184V484V813866120132348V290V560V712615313248V348V6150V9求解的过程如下:第一步,第一个已解的节点就是始点Vs,与始点直接相连的是V1,V2和V3,分别计算它们与始点的距离,如表所示,可以看出V1距始点最近,因此V1选择进入已解节点集合P,其与始点的距离为90。第二步,找出与Vs和V1直接相连的点,它们是V2,V3和V4,分别计算它们与起始点的最短距离,V2为最近,因此V2进入已解节点集合,与起始点的距离是138,经过的路径是Vs-V2。第三步,重复上述步骤,找出与已解节点直接连接的最近的未解节点。直到到达终点Vp。通过求解,得到最佳路径为Vs—V1—V4—V8—Vp。这类问题非常适合利用计算机进行求解。起讫点不同的单一路径规划运输网张求解运算表格步骤已解节点与已解节点直接相连的未解节点相连的未解节点相关总成本第n个最近解点最小成本最新连接1VsV190V190Vs-V12VsV1V2V213890+66=156V2138Vs-V23VsV1V2V3V4V534890+84=174138+90=228V4174V1-V44Vs,V2V2,V4V4V3V5V8min{348,138+153}=291min{138+90,174+120}=228174+84=258V5228V2-V55VsV2V4V5V3V3V8V7V6348138+153=291174+84=258228+60=288228+132=360V8258V4-V86Vs,V2V2,V4V8V3V5V7Vpmin{348,138+153}=291min{138+90,174+120}=228258+132=390258+126=384V5228V2-V57Vs,V2V5V8V3V6V7V7Vpmin{348,138+153}=291228+132=360228+60=288258+132=390258+126=384V7288V5-V78VsV2V5,V7V7,V8V3V3V6Vp348138+153=291min{228+132,288+48}=336min{288+126,258+126}=384V3291V2-V39V3V5V7V8V6V6V6VpVp291+48=339228+132=360288+48=336228+126=354258+126=384V6336V7-V610V6V7V8VpVpVp336+150=480288+126=414258+126=384Vp384V8-Vp2.A公司以每箱100美元向日本B公司出口某商品2000箱。货物出口前,由A公司向中国人民保险公司投保水渍险、包装破裂及淡水雨淋险。水渍险、包装破裂险及淡水雨淋险的保险费率分别为0.6%、0.1%和0.3%,按发票金额110%投保。试计算该批货物的投保金额和保险费。解:投保金额=CIF总值×110%=100×2000×110%=220000(美元)保险费=投保金额×保险费率=220000×(0.6%+0.1%+0.3%)=2200(美元)答:该批货物的投保金额是220000美元,保险费是2200美元。3.A公司出口柴油机一批,共15箱,每箱重量0.38公吨,总体积为10.676立方米(班轮),经香港转船至苏丹港。已知:查阅货物分级表,柴油机属于10级货,计算标准为W/M;在中国——香港航线费率表中查出10级货从青岛运至香港的费率为22美元,香港中转费为13美元;再从香港——红海航线费率表中查出10级货的费率为95美元;最后查附加费率表,了解到苏丹港要收港口拥挤附加费,费率为基本运费的10%。试计算A公司应付船公司运费多少?解:总毛重15×0.38=5.7公吨运费吨的运价=22+13+95+95×10%=139.5(美元)总运费=10.676×139.5=1489.30(美元)答:A公司应付船公司运费为1489.30美元。4.某第三方物流公司一仓库内墙长42米,宽21米,高4.1米,沿着宽方向的走道宽2.6米,沿着长方向的走道宽1.8米(走道在中间),库房长方向墙距1米,宽方向墙距0.8米,库内无柱子、间壁墙、扶梯及其它固定设施;现用该仓库储存一批海尔洗衣机(立着堆放),包装长0.8米,宽解:(1)依题可知,该仓库被分隔成四块区域,每块区域长、宽计算如下:长:(42-2.6-0.8×2)/2=18.9宽:(21-1.8-1×2)/2=8.6(2)计算每块区域可堆放的洗衣机数:计算可堆放的层数:按库房高度计算:4.1/1=4层;按包装承压计算:1+110/50=3层;根据上述2种计算结果可知只能堆放3层。B:计算每层可堆放的洗衣机数:按洗衣机长度与每块区域长度方向一致计算:(18.9/0.8)×(8.6/0.6)=23×14=322台按洗衣机长度与每块区域宽度方向一致计算:(18.9/0.6)×(8.6/0.8)=31×10=310台根据仓容利用最大化的原则,选择每层堆放322台。(3)计算仓库最多可储存的洗衣机台数:3×322×4=3864台。答:该仓库最多能储存3864台饮水机。5.某中心仓库进货625块20mm×1000mm×2000mm的钢板,库房地坪单位面积载荷为3吨,可用高度为3m(密度取7.8吨/立方米)。问:该批货物的储存至少需要多少面积(取整)?解:(1)每块钢板重量:0.02×1×2×7.8=0.312吨每块面积为1×2=2平方米每块钢板单位面积重量:0.312÷2=0.156吨(2)按可用高度计算可迭层数=3÷0.02=150层按单位面积载荷可迭层数=3÷0.156=19(3)每平方堆重量=19×0.156=2.964吨(4)625块共需面积=625÷19×2=66㎡答:该批货物的储存至少需要66平方米。6.苏州某电子产品厂商每年采购电热圈50000箱,每批量订货费用4000元,经测算储存费用占每箱电热圈价款的20%。采购批量区间与价格如下表,求经济订货批量及总库存成本。订货量Q(箱)价格(元/箱)Q≤6000506000<Q≤7000457000<Q≤8000368000<Q≤9000329000<Q30解:(1)计算各区间经济订货批量(20分)Q=(2DCr/H)½订货量区间价格经济订货批量Q符合与否Q≤600050Q1=(2×50000×4000/(50×0.20))½=6324.56不符合6000<Q≤700045Q2=(2×50000×4000/(45×0.20))½=6666.67符合7000<Q≤800036Q3=(2×50000×4000/(36×0.20))½=7453.56符合8000<Q≤900032Q4=(2×50000×4000/(32×0.20))½=7905.70不符合9000<Q30Q5=(2×50000×4000/(30×0.20))½=8164.97不符合(2)根据上述计算结果,Q2、Q3符合要求,但不是最低价格,所以应结合更低的价格区间,采取比较全年部库存成本的方法,考虑Q2、Q3、Q4、Q5四种情况确定最佳订货批量(Q4、Q5订货批量应为区间临界点,即分别为8001和9001):(20分)全年总库存成本计算公式为:C=(D/Q)×Cr+(Q/2)×H+D×PC2=(50000/6666.67)×4000+(6666.67/2)×(45×0.2)+50000×45=2310000.00C3=(50000/7453.56)×4000+(7453.56/2)×(36×0.2)+50000×36=1853665.6C4=(50000/8001)×4000+(8001/2)×(32×0.2)+50000×32=1650600.10C5=(50000/9001)×4000+(9001/2)×(30×0.2)+50000×30=1549222.8综合上述计算结果,因为全年总库存成本C5=1549222.8最低,此时经济订货批量为9001。答:经济订货批量为9001箱,全年总库存成本为1549222.8元。7.某企业引进4台新设备(编号分别为A、B、C、D)欲组成新的生产线,其可排入的位置号为1、2、3、4。为使生产设备间搬运合理化,请利用新建法设计出设备的最佳排列次序及搬运量(设备间的物流量V及距离d如下表所示)。VABVACVADVBCVBDVCDV983425dd12d13d14d23d24d348102479解:将V、d数据分别由大到小和由小到大排序V(大→小)=(9,8,5,4,3,2)=(VAB,VAC,VCD,VBC,VAD,VBD)d(小→大)=(2,4,7,8,9,10)=(d14,d23,d24,d12,d34,d13)根据大物流-短距离的布置原则,可直接根据上表排序:设备排序:ABACCDBCADBD位置分布:142324213413对上述设备与位置号进行观察比对可得到如下对应方案:设备ABCD对应位置3或4124或3针对上表设备与位置对应方案分两种情况求搬运量:当A对应位置3时搬运量Z1=VAB×d13+VAC×d23+VAD×d34+VBC×d12+VBD+VCD×d24=9×10+8×4+3×9+4×8+2×2+5×7=220当A对应位置4时搬运量Z2=VAB×d14+VAC×d24+VAD×d34+VBC×d12+VBD+VCD×d23=9×2+8×7+3×9+4×8+2×10+5×4=173因为Z2<Z1,所以A应对应位置4。答:新设备A、B、C、D的最佳排列序即对应位置为4、1、2、3,此时最小搬运量为173。8.某产品结构图如下:AB(2)D(2)C(3)E(3)填表计算产品A的需求计划,并将相差数据填入下表:(已知产品A:提前期=2周,毛需求量及已分配量见下表,再有库存60)周12345678毛需求量201030304020已分配量0计划收到40计划库存净需求量计划投入(2)计算部件B的需求计划,并将相关数据填入下表:(已知部件B:提前期=1周,批量=30,安全库存10,已分配量见下表,现有库存100)。周12345678毛需求量已分配量计划收到计划库存净需求量计划投入(3)计算部件C的需求计划,并将相关数据填入下表:(已知部件C:提前期=3周,批量=90,安全库存20,已分配量见下表,现在库存50)。周12345678毛需求量已分配量计划收到计划库存净需求量计划投入8.解填表计算产品A的需求计划,并将相差数据填入下表:(已知产品A:提前期=2周,毛需求量及已分配量见下表,再有库存60)。表1产品A的需求计划表周12345678毛需求量201030304020已分配量0计划收到40计划库存403070401000净需求量3020计划投入3020计算部件B的需求计划,并将相关数据填入下表:(已知部件B:提前期=1周,批量=30,安全库存10,已分配量见下表,现有库存100)。周12345678毛需求量6040已分配量计划收到计划库存1001001004030净需求量10计划投入30(3)计算部件C的需求计划,并将相关数据填入下表:(已知部件C:提前期=3周,批量=90,安全库存20,已分配量见下表,现在库存50)。周12345678毛需求量90已分配量计划收到计划库存50505050净需求量60计划投入909.某超市集团有五个大卖场,其位置坐标如下表,现欲建一配中心,经查各卖场配送量如下表,请用重心法求出配送中心位置(X,Y)。区域位置配送量(吨)东1044000西238000南7010000北588000中642000解:X=(10×4000+2×8000+7×10000+5×8000+6×2000)/(4000+8000+10000+8000+2000)=5.563Y=(4×4000+3×8000+0×10000+8×8000+4×2000)/(4000+8000+10000+8000+2000)=3.5答:配送中心的位置坐标为(5.563,3.5)10.A公司选择三家食品供应商为旗下四家零售店供货,每日供货量分别是500、200、300个单位,四个零售店日销售量分别是200、300、100和400个单位,求最佳调运方案和总运费。门店供应商B1B2B3B4A16325A27584A33297解:建立供销平衡运价表: 门店供应商B1B2B3B4供货量A16325500A27584200A33297300日销售量2003001004001000做初始调运方案(最小元素法),并检验(位势法)门店供应商B1B2B3B4供货量A1(6)2000(2)100(5)2005004002000A2000(4)2002000A3(3)0(2)300003000日销售量2000300010004002000采用位势对上述方案进行检验,将运价分解为U和V两部分:门店供应商V1V2V3V4供货量B1B2B3B4U1A1(6)2000(2)100(5)2005004002000U2A2000(4)2002000U3A3(3)0(2)300003000日销售量20003000100040020001000列方程:U1+V1=6U1+V3=2U1+V4=5U2+V4=4U3+V1=3U3+V2=2令U1=0,则:U2=-1,U3=-3,V1=6,V2=5,V3=2,V4=5经检验,上表中A1、B2对应的运价3,而U1+V2=5,故应进行调整。调整(闭合回路法)原因:2002000300 0300调整后:200100200 200100200门店供应商V1V2V3V4供货量B1B2B3B4U1A10(3)200(2)100(5)2005004002000U2A2000(4)2002000U3A3(3)200(2)100003000日销售量20003000100040020001000重新列方程并检验,得出Ui+VI全部小于所对应的运价,故上述调整后的方案为最佳方案:即A1向B2运200单位,向B3运100单位,向B4运200单位;A2向B4运200单位;A2向B1运200单位,向B2运100单位。总运费为;200×3+100×2+200×5+200×4+200×3+100×2=3400。11.现有P1,p2两地,欲选择其一设配送中心,通过组织专家对p1,p2进行综合评价打分,获得关于P1,P2的评价分值如下表,请据此判断配送中心应设在哪?考虑因素权重系数P1得分P602得分劳动成本0.257060运输费用0.205060教育通讯0.108580税收结构0.357570资源和生产率0.106070合计1.00340340解:对P1,P2两地的评价分值进行加权计算并求和可得:考虑因素权重系数P1得分P2得分P1加权得分P2加权得分劳动成本0.25706017.515.0运输费用0.20506010.012.0教育通讯0.1085808.58.0税收结构0.35757026.324.5资源和生产率0.1060706.07.0合计1.0034034068.366.5因为P1得分高于P2得分,故应选P1作为配送中心地址。节约法原理节约法的原理如图7-4。如果从配送中心A到用户P1、P2的运输距离分别是C01和C02,P1和P2之间的距离运输距离是C12,如果不配送,则对每个用户需派一辆车来回送货。总运输距离为:C=2C01+2C02而如果配送,则可以只派一辆车一次给两个用户顺序送货。总运输距离为:C’=C01+C02+C12二者之间的节约量为:C=C-C’=(2C01+2C02)-(C01+C02+C12)=C01+C02-C12P1P2P1C12P2C02C01CC01AA如果把多个用户连在一起,则节约量更大。如果多个用户满足假定条件:(1)n∑b1≤Qk;j=1(2)C01+C02>C12,使得节约量大于0。则可以按节约量从大到小的顺序依次把用户迦成一条回路,直到整个回路各个用户的需求量之和不超过这辆载重车的载重量,就组成了一条节约量最大的配送回路,派出一辆车。然后再在剩下的用户中同样按节约量由大到小的顺序继续组织配送回路,派出车辆,这样下去一直到所有用户都组织完毕为止,就做完了一个完整的配送计划。节约法案例12.例如,某月某日,长江物流公司接受了武汉某商场经武汉市十个用户送货的任务单,多个品牌总运量共80吨,各个用户的需求量如表7-1,各点之间的路程如图7-5所示。公司现有10吨车二辆、5吨车二辆,,2吨车若干辆。需要制定配送计划。A10P11210P211911P31312109P41511141226P5131412152515P616142018241716P71712182023191721P8181114222221192215P920151624212318201718P10图7-5各个用户之间路程(路程单位:公里)制定配送计划的第一步,首先安排直送,把大量用户先用专车直送,剩下的小运量用户再统一安排配送。由图7-5可以看出,物流中心A到用户P1的路程仅10公里,可以由一辆10吨车来回运送4次,1天可以完成。P1剩下的20吨加上P2的10吨可以由另一辆10吨车运3次。派一辆10吨车专为P1用户来回运送四趟运10吨,来回算20公里。工作量为:10吨×20公里×4=800吨公里第二辆10吨车为P1送20吨,为P2送10吨,来回运三次。其工作量为:10吨×20公里×2+10吨×12公里×2=640吨公里表7-1用户需求量(吨)P160.0P212.0P31.0P41.5P50.5P60.5P7135P80.8P91.2P101.0把这些大运量用户直送安排完之后,P2还剩下2吨,其余小运量各用户再安排配送计划。第二步,制定详细具体的配送计划。首先要求配送用户的节约量,如图7-6。具体组织回路时,总是从最大的节约量开始,连接用户。例如图7-6中,最大的节约量为20,有三个20,随便哪一个都可以,例如我们选定P10和P5的交叉点上的20,但是这时要考虑一下它们的需求量之和(1.2+1.0),是否小于等于可用车的载重量,如果大于一辆车的载重量就不能够连,如果小于一辆车的载重量就可以连。第一辆配送车辆准备用5吨车,而P9和P10的需求量之和只有2.2吨,所以可以连,这样在这个格和P9所在格上做一个记号,例如①(表示第1条回路),这就意味着把P9和P10连起来。把P9和P10连起来,下一个连谁呢?还是选剩下的节约量最大的,在P10所在行,还有一个20,它在P10和P8的交叉点上,意味着P10和P8连接,需求量之和(1.2+1.0+0.8=3)小于载重量5,可以连,在这个20所在格以及P8所在格上做上相同的记号①,表示P10和P8连在一起了。由于车还没载满,继续连,再在剩下的里面找节约量最大的,这时注意,P10所在行已经满了,因为这一行已经有两个记号,表示它的两头都已经牵上手了,不能够牵手了。需求A2①P2①1.012P31.5②1515②P40.51314②2P5②0.5②139113P6②1.589514②13②P70.8①1187131312P8①1.2167912121220P9①1.01671212151620①20①P10图7-6各个用户之间节约量(路程单位:公里)注意一个规则:每行每列的记号都只能有两个,也必须有两个(包括用户格和配送中心A所在列的格中的记号,但A所在列的记号可以多于两个)。这样就能够在P10所在列的各个用户中找节约量最大的,为16,表示P9和P2牵手,需求量之和等于5,可以连,在16所在格和P2格打上相同的记号①。这时,一辆5吨车已经载满,这时把P2和P8分别与配送中心A牵手(即在它们的交叉点上打上相同的记号①),就完成了一个配送回路。这个配送回路就是A-P2-P9-P10-P8-A,用5吨车刚好装5吨货物循环送货,全路程长61公里,工作量305吨公里。再在剩下的用户中按同样的方法组织第二个回路,见图7-6中用②标记的回路。这条回路是:A-P4-P3-P5-P7-P6-A,用5吨车刚好装5吨循环送货,全长80公里,总任务量400吨公里。这样具体的运输计划就是:共用四辆车,二辆10吨车,二辆5吨车,都满载。10吨车搞P1和P2的直送;二辆5吨车都搞配送:第一辆运行路线:A-P2-P9-P10-P8-A;第二辆运行路线:A-P4-P3-P4-P7-P6-A。总任务量为2145吨公里。注意,这样做出来的具体配送计划可能不是惟一的,可能有几个方案。最后比较哪个最省,就用哪一个方案。三、计算题(一)最短路线计算(7分)某公司要把A市的一批产品运到H市,该公司根据这两个城市之间可选择的行车路线的地图,如图所示,图中,箭头代表两个地点之间的公路,每一公路都标明运输里程(公里),请给出从A到B的最短路线。(答案:A-C-D-E-F-H,总计里程为335公里)B95E55F120306080A150D140130H9050110210C160G(二)用标号法计算从①点到各个点的最短距离。(8分)44302744302720②③⑦492612401518121018204926120①12④14⑥30⑨01813201513⑤⑧3618183618解:①到②的最短距离为27;到③的线路为①—②—③,最短距离为30;到④的线路为①—④,最短距离为12;到⑤的线路为①—⑤,最短距离为18;到⑥的线路为①—④—⑥,最短距离为26;到⑦的线路为①—④—⑥—⑦,最短距离为44;到⑧的线路为①—⑤—⑧,最短距离为36;到⑨的线路为①—⑤—⑧—⑨,最短距离为49。(三)根据提供的评价数据,采用综合评分法选择确定某企业的供应商。(10分)评价指标:产品质量40分;价格35分;合同完成率25分。有关数据如下:供应商收到商品的数量(件)验收合格的数量(件)单价(元)合同完成率(%)甲200019208998乙240022008692丙6004809395丁100090090100解:根据已知条件得出:供应商甲:(1920÷2000)×40+86÷89×35+(98%×25)=96.7供应商乙:(2200÷2400)×40+86÷86×35+(92%×25)=94.7供应商丙:(480÷600)×40+86÷93×35+(95%×25)=88.1供应商甲:(900÷1000)×40+86÷90×35+(90%×25)=94.4甲供应商评分最高,故应选择甲供应商。(四)根据所提供的数据,计算某自动化仓库相关货物储存效率指标。(12分)指标数据指标数据占地面积4500M有效面积900M库房总容量5000t年仓储业务收入500万元报告期365天(含节假日60天)全年消耗货物总量12000t每日工作8小时巷道堆垛机额定载荷1000公斤报告期实际工作工时数1800小时实际工作载荷700公斤期初,固定资产平均占用780万元期末,固定资产平均占用775万元流动资产平均占用200万元流动资产平均占用180万元平均货物储存量1000t平均货物储存量1200t解:1、仓库利用率计算(1)仓库面积利用率=900÷4500×100%=20%(2)库房容积利用率=1000÷5000×100%=20%2、设备利用率:(1)设备能力利用率=700÷1000×100%=70%(2)设备时间利用率=1800÷〔(365-60)×8〕×100%=74%3、资金使用效率(1)期初单位货物固定资金占有量=780/1000=0.78万元/吨(2)期初单位货物流动资金占有量=200/1000=0.2万元/吨(3)期末单位货物固定资金占有量=775/1200=0.65万元/吨(4)期末单位货物流动资金占有量=180/1200=0.15万元/吨(5)单位货物固定资金平均占有量=(0.78+0.65)/2=0.7万元/吨(6)单位货物流动资金平均占有量=(0.2+0.15)/2=0.175万元/吨(7)流动资金周转次数=500×2÷(200+180)=2.6次/年(8)流动资金周转天数=(200+180)×360÷(2×500)=136.8天/次4、货物周转速度(1)货物年周转次数=12000×2÷(1000+1200)=11次/年(2)货物周转天数=(1000+1200)×360÷(2×12000)=33天/次(五)某运输企业欲将20台空调采用铁路运输从北京运到济南。(14分)1、空调由内机、外机、附件三部分组成,其具体数据如下:名称重量(kg)体积(mm3)内机2001960×600×1000外机65980×410×715附件8850×435×3752、北京到济南的距离为550公里,铁路的运费、装卸费计算标准如下:(1)密度大于170kg/m3的货物按0.65元/t·km计算,小于170kg/m3的货物按60元/m3计算,整车运输5元/km计算。(2)保险费按10万元的0.5%,装卸费为2000元计算。(3)按零担运输计算:名称密度(kg/m3)件数单价合计费用(元)内机170(=170)200.65×0.2×550或60×1.1761411.20外机398(﹥170)200.65×0.065×550464.75附件57.7(﹤170)2060×0.14168.00总费用2043.95根据以上条件,设计合理的运输方案。解:1、空调货物属于贵重物品,各种组成的部件均严格配套,且不能雨淋、暴晒,故采用铁路厢式货车运输。2、假设采用整车运输,其运费为:5.00×550=2750.00(元)因按整车运输的价格高于零担运输,故采用零担运输。3、保险费、装卸费合计:保险费:100000×0.5%=500元装卸费为2000元合计:2000+500=2500元4、此项运输总费用为:2043.95+2500=4543.95元,货物可在24小时送达。计算题1.某公司要把A市的一批产品运到B市,该公司根据这两个城市之间可选择的行车路线的地图,如图所示,图中,圆圈代表地点,箭头代表两个地点之间的公路,每一公路都标明运输里程,请给出从A到B的最短路线。ACACDFGEB20015026022527010012023090A1001601)从终点B开始逐步逆向推算,与B相连的有两个城市即E,G,先从E开始计算。到B只有一条公路,因此没有选择的余地,E-B就是最短路,记为(E-B)160。同样,G到B也只有一条路,最短路为G-B,记为(G-B)230。2)再看E,与E相连的有C,F,先从C开始计算,到E只有一条公路,因此没有选择的余地,C-E就是最短路,记为(C-E)270。同样,F到E也只有一条路,最短路为F-E,记为(F-E)90。用同样的方法,算出(F-C)120,(F-D)100,(F-A)260,……3)最后看A,与A相连的有三个城市即C,D,F,A到C再到B的最短路(A-C-F-E-B)530,A到D再到B的最短路是(A-D-F-E-B)560,A到F再到B的最短路是(A-F-E-B)520。 所以,三个路线中最短路是(A-F-E-B)520。2.求图一所示的运输网络中从V1至V5的最小费用最大流,弧旁的数字为C容量,b费率。解:给初始可行流为零流,如图二所示,(弧旁数字为C,F),这时F=0,B=0。V1V4V1V4V5V3V25,26,17,64,18,43,22,3图一V1V4V3V26,07,04,08,03,02,0图二作图二的费率网络图三,(弧旁数字为C,b),求得最短路V1-V4-V2-V3-V5,对应于图一得到调整量Q=min{4,3,6,5}=3,费率b1=1+2+1+2=6调整后可得可行流如图四所示。这时,F1=3,B1=F1b1=18。V1V4V5V3V1V4V5V3V25,36,37,04,38,03,32,0图四V1V4V5V3V221161423图三V55 作图四的伴随F的费用网络,求得最短路V1-V4--V3-V5,b2=1+3+2=6,调整量为Q=1,调整后的可行流示于图五,这时F2=F1+Q=4,B=18+F1b1=24。依次得到伴随F的费用网络,求最短路,然后调整,得图六……,最后得到最小费用最大流的解如图七所示,此时,F7=9,B=63,即最大流为9,最小费用为63。6,3V2V3V1V4V5V36,3V2V3V1V4V5V3V25,56,47,04,18,13,32,1图六2,13,38,05,42,13,38,05,44,47,0V5V4V14,47,0V5V4V1V1V4V1V4V5V3V25,56,57,44,48,53,02,0图七图五3.图1所示的运输网络,试求出最优路线。解:图中顶点V2,V4,V5,V7为奇数顶点,要使它成为欧拉图,需用加重复边的方法使这四个顶点变为偶次顶点。选择在(V2,V5)(V4,V7)上加重复边,得到的初始方案示于图2中,圈(V2,V5,V4,V7,V2)中,重复边总权为9+4=13,非重复边总权为5+7=12,所以此方案不满足最优条件,需继续调整。调整时在不满足条件的圈中,将重复边与非重复边对换,即将重复边由(v2,v5)(v4,v7)换成(v2,v7)(v4,v5),得到图3。经检验所有圈均满足最优条件,即得最优路线V1V1V2V7V4V3V6V55712481296910109图2V1V2V7V4V3V6V55712481296910109图15VV1V2V7V4V3V6V55712481296910109图34.现有一配送中心为八个零售商供货,各个零售商的需求量是Gi(吨),这些零售商由配送中心(标号是0)发出的8吨的载货车辆供应,具体数据如表1与表2所示,把各点之间的距离作为成本考虑的主要因素,即Cij=Dij(i,j=0,1,……,8),求最优的配送路线。表1:零售商和需求量用户i12345678需求量Gi21.54.531.542.53表2配送中心与零售商之间的距离中心0中心0零售商140零售商1零售商26065零售商2零售商3754075零售商3零售商49010050100零售商4零售商52005010050100零售商5零售商61007575907570零售商6零售商71601107590759070零售商7零售商8801007515010075100100零售
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 初中九年级英语Unit 5 Power of Ideas单元写作专题教学设计
- 初中地理《西北地区》区域地理复习教学设计
- 高三地理二轮复习围湖造田与填海造陆专题教学设计
- 掘金智能地脚灯万亿蓝海:核心瓶颈与全屋智能闭环
- 八年级历史期末复习综合卷2025:历史学科教学策略与方法
- 关于即将举行的产品展示活动邀请函5篇
- 业务招待活动申请审批函4篇
- 电影制片人项目投资绩效考评表
- 统编版语文五年级上册《12 古诗三首》教案教学设计
- 财务分析师年度绩效分析表
- 渔业生产与养殖技术规范
- 中央企业拖欠账款举报信范本
- (完整版)人行道块料拆除及恢复施工方案
- 2025年茂名村干部考试题库
- GB 28375-2025混凝土结构防火涂料
- 2025团校入团培训结业考试题库附完整答案详解(历年真题)
- GB 19577-2024热泵和冷水机组能效限定值及能效等级
- 《民法典》培训系列课件:第三编 租赁合同
- 2024中考道法时政热点《中国外交大事大盘点》课件
- 浙江博瑞中硝科技有限公司电子含氟气体项目环境影响报告书
- GB/T 31402-2023塑料和其他无孔材料表面抗菌活性的测定
评论
0/150
提交评论