运输网络线路优化计算题(课堂PPT).ppt

1五、运输优化方法五、运输优化方法运输网络合理优化问题*节约法优化配送运输路线问题最短路径算法*研究从各资源点向各需求点运研究从各资源点向各需求点运输某种物资，考虑各点资源量输某种物资，考虑各点资源量和需求量限制，确定一组运输和需求量限制，确定一组运输方案，使方案，使总的运输费用总的运输费用最小最小。如何从许多可供选择如何从许多可供选择的路线中选出的路线中选出最佳的最佳的运输路线运输路线的方法。的方法。求出运输网络中每一对求出运输网络中每一对O-D对之对之间的间的最短最短运输距离、运输距离、最短最短运行运行时间以及时间以及最省最省的运输费用。的运输费用。2运输问题的表示网络图、线性规划模型、运输表运输表初始基可行解西北角法西北角法、最小元素法、最小元素法、伏格尔法非基变量的检验数闭回路法、闭回路法、对偶变量法确定进基变量，调整运量，确定离基变量1、运输网络合理优化问题、运输网络合理优化问题32321341运输问题网络图s2=27s3=19d1=22d2=13d3=12d4=13s1=14供供应应量量供应地供应地运价运价需需求求量量需求地需求地67538427591064运输问题线性规划模型供供应应地地约约束束需需求求地地约约束束5运输问题的表格表示运输问题的表格表示6西北角法西北角法思想：思想：又称左上角法，不考虑产销两地的运输距离（或单位运费），单纯按照产销平衡表从西北角（左上角）至东南角（右下角）的方向，根据供应量和需求量，逐一分配给变量xij最大可能的数量。如果某一行或某一列同时得到满足，只划去一行（列），保留另一列（行），继续安排。初始基可行解的确定初始基可行解的确定7初始基可行解西北角法（1）81313146608 00196613 00008初始基可行解西北角法（2）8131314669最小元素法最小元素法思想：思想：就近供应就近供应，即从单位运价表中最小最小的运价开始确定供销关系，然后次小次小，一直到给出初始可行解为止。10初始基础可行解最小元素法（1）11最小元素法（2）12最小元素法（3）13最小元素法（4）14最小元素法（5）15最小元素法（6）16最小元素法（6）初始可行解172 2、产销不平衡的运输问题、产销不平衡的运输问题 在实际问题中，往往供需(或产销)不平衡，有时供大于需，有时需大于供。这类问题的解决方法是：当供大于需时，当供大于需时，增设一个虚拟的销地；当需大于供时，当需大于供时，增设一个虚拟的产地；这样将不平衡的运输问题不平衡的运输问题化为平衡的运输问平衡的运输问题题来解决。18 销地销地产地产地B B1 1B B2 2B B3 3供应量供应量A A1 12 27 74 42525A A2 23 36 65 53535需求量需求量101025251515 60 60 5050 销地销地产地产地B B1 1B B2 2B B3 3B B4 4供应量供应量A A1 12 27 74 40 02525101015150 0A A2 23 36 65 50 0353525251010需求量需求量101025251515(10)(10)6060供大于需供大于需增设一个虚拟的销地增设一个虚拟的销地(B B4 4)运价运价供需平衡供需平衡从各个产地到虚从各个产地到虚设的销地设的销地(B B4 4)间间的单位运输费用的单位运输费用都假设为都假设为0 0 19 销地销地产地产地B B1 1B B2 2B B3 3供应量供应量A A1 18 87 74 41515A A2 23 35 59 92525需求量需求量202010102020 40 405050 销地销地产地产地B B1 1B B2 2B B3 3供应量供应量A A1 18 87 74 415151515A A2 23 35 59 9252520205 5A A3 30 00 00 0（10)10)5 55 5需求量需求量2020101020205050供小于需供小于需增设一个虚拟的产地增设一个虚拟的产地(A(A3 3)供需平衡供需平衡从虚设的产地到从虚设的产地到各个销地间的单各个销地间的单位运输费用都假位运输费用都假设为设为0 0 20当供应量大于需求量时：设一个假想销地DJ+12122当供应量小于需求量时：设一个假想产地OI+1232、节约法优化配送运输路线问题、节约法优化配送运输路线问题假设假设1、配送的是同一种货物、配送的是同一种货物2、各个用户的坐标（、各个用户的坐标（x，y）即需求量均为已知）即需求量均为已知3、配送中心有足够的运输能力、配送中心有足够的运输能力条件条件1、方案能满足所有用户的要求、方案能满足所有用户的要求2、不使任何一辆车超载、不使任何一辆车超载3、每一辆车每天的总运行时间或者行驶里程不超过规定的上限、每一辆车每天的总运行时间或者行驶里程不超过规定的上限4、能够满足用户到货时间的要求、能够满足用户到货时间的要求241、各客户与物流中心相连，得总费用；2、计算每两个用户间的节约里程；3、将各对用户间的节约里程排序；4、从最大节约里程的用户对开始连接，逐渐形成回路，直到达到车辆载重标准。5、将已连接的客户从剩余的节约里程排序中去掉；6、再从剩下的节约里程集合中继续以上过程，直到全部用户都连接起来。求解步骤求解步骤25节约量节约量 S Sij ij=2d=2d0i 0i+2d+2d0j 0j （d d0i 0i+d+d0j 0j+d+dijij ）=d=d0i 0i+d+d0j 0j d dijijPiPjd0id0jdij基本思想基本思想26中心中心0 0用户用户1 1用户用户2 2用户用户3 3用户用户4 4用户用户5 5中心中心0 09 9用户用户1 16 61010121213137 7141417177 710108 87 717173 3用户用户2 2用户用户3 3用户用户4 4用户用户5 51616例题例题27中心中心0 0用户用户1 1用户用户2 2用户用户3 3用户用户4 4用户用户5 5中心中心0 09 9用户用户1 16 61010121213137 7141417177 710108 87 717173 3用户用户2 2用户用户3 3用户用户4 4用户用户5 51616S12=9+6-7=8S13=9+10-14=5S14=9+12-17=4S15=9+13-7=15S23=6+10-7=9S24=6+12-8=10S25=6+13-10=9S34=10+12-3=19S35=10+13-17=6S45=12+13-16=9节约量节约量 S Sijij=2d=2d0i 0i+2d+2d0j0j （d d0i0i+d+d0j0j+d+dijij ）=d=d0i0i+d+d0j0j d dijij28（1）3-4（2）1-5（3）2-4（3-4-2）（4）2-3、4-5、2-5（5）0-3-4-2-5-1-0用户用户1 1854159109619用户用户2 2用户用户3 3用户用户4 4用户用户5 5929节约法的优点节约法的优点（1）一方面体现出优化运输过程，与一般方法相比缩短了运输路程；（2）体现了物流配送网络的优势，实现了企业物流活动的整合；（3）思路简单、清晰，便于执行。30节约法的缺点节约法的缺点 （1）过于强调节约路程，而没有考虑行程中的时间因素，在许多情况下，时间更能决定物流配送的成本与服务质量。（2）不能对客户的需求进行灵活多变的处理，更适合需求稳定或是需求时间不紧迫的情况，显然不能满足现代多变的市场环境。（3）既要缩短总路程，又要充分利用车辆的运输空间，减少配送车次，往往导致结果并不是总路程最短。31节约法的改进建议节约法的改进建议 由以上的分析可知由以上的分析可知,节约法简便易行节约法简便易行,同时也有一些弊端同时也有一些弊端。是否可以通过改进使其成为一种最优的方法呢是否可以通过改进使其成为一种最优的方法呢？撇开其他因撇开其他因素素，只考虑运输路线是否最短只考虑运输路线是否最短，这就是不可能的这就是不可能的。早在人们早在人们研究这一问题时就发现研究这一问题时就发现，即使不考虑运输工具的载运空间即使不考虑运输工具的载运空间，而只考虑在多个节点之间寻求最短巡回路线时而只考虑在多个节点之间寻求最短巡回路线时(运筹学中的运筹学中的货郎担问题货郎担问题)，虽然人们可以利用动态规划的方法虽然人们可以利用动态规划的方法，可是计可是计算量太大算量太大，当节点的个数足够多时当节点的个数足够多时，即使利用计算机仍是不即使利用计算机仍是不可取的可取的，而在配送路线中还要考虑运输工具载运空间和配送而在配送路线中还要考虑运输工具载运空间和配送时间的限制时间的限制。但是但是，这并不意味着节约法是不可改进的这并不意味着节约法是不可改进的，只只是在配送路线选择决策时是在配送路线选择决策时，通常考虑通常考虑较优较优的原则的原则，而不是而不是最最优化优化原则原则.32节约法的改进建议节约法的改进建议1 1)深入了解客户深入了解客户,加强与客户的信息交流加强与客户的信息交流.客户的需求是企业物流服务水平的准绳。只有深入客户的需求是企业物流服务水平的准绳。只有深入了解客户群体了解客户群体，进行周密细致的研究进行周密细致的研究，才能了解客户对才能了解客户对商品的品种、规格、型号、供货期、服务收费及所需的商品的品种、规格、型号、供货期、服务收费及所需的物流增值服务等情况物流增值服务等情况，并在此基础上建立客户管理档案并在此基础上建立客户管理档案，对未来需求进行预测对未来需求进行预测，这样才能以适当向客户提供高质这样才能以适当向客户提供高质量的物流服务量的物流服务,从而使企业与客户之间建立稳定的关系从而使企业与客户之间建立稳定的关系，为企业迎来充裕的时间规划配送方案为企业迎来充裕的时间规划配送方案。33节约法的改进建议节约法的改进建议2 2)通过对客户需求的时间变化进行分类通过对客户需求的时间变化进行分类,增加配送的灵活性增加配送的灵活性 客户需求的时间变化决定了运送前的货物联合组装和对客户需求的时间变化决定了运送前的货物联合组装和对物流网络的有效利用物流网络的有效利用。所以所以，企业应对客户进行分类企业应对客户进行分类，对不对不同的客户实施不同的配送策略与收费同的客户实施不同的配送策略与收费。按着客户需求的时间按着客户需求的时间变化可把客户分两类变化可把客户分两类：需求稳定或备货期较长的客户需求稳定或备货期较长的客户和和需求需求变化无常或备货期较短的客户变化无常或备货期较短的客户。对于对于前一种前一种客户客户，应充分利应充分利用节约法用节约法，对其过程详细的规划对其过程详细的规划，尽可能缩短配送的总过程尽可能缩短配送的总过程与总的配送时间与总的配送时间，提高设备的利用率提高设备的利用率，节约成本节约成本；对对后一种后一种客户要尽可能利用节约法原理来实施客户要尽可能利用节约法原理来实施，但在必要时但在必要时，为了支为了支持企业的竞争战略持企业的竞争战略，实现对客户的承诺实现对客户的承诺，也可对特定客户进也可对特定客户进行单个配送行单个配送。34节约法的改进建议节约法的改进建议3 3)节约法的实施过程节约法的实施过程，要综合考虑路程长短和时间因素要综合考虑路程长短和时间因素。配送过程费用和服务质量取决于配送过程费用和服务质量取决于时间时间与与路程路程的综合因素的综合因素,所以应该在实施过程中综合考虑这两个因素所以应该在实施过程中综合考虑这两个因素。可以采用以可以采用以下指标代替各节点间的距离的措施下指标代替各节点间的距离的措施:(1)(1)中间的过程指标用中间的过程指标用:(:(路长路长正常速度正常速度正常速度概率正常速度概率+路长路长非常速度非常速度非常速度概率非常速度概率)；或者用或者用:(:(非常速度路长非常速度路长非常速度非常速度+正常速度路长正常速度路长正正常速度常速度););(2 2)如果服务需求稳定如果服务需求稳定,配送的起止时间是固定的配送的起止时间是固定的，则中间的则中间的过程指标用过程指标用:(:(路程长度路程长度/平均车速平均车速)。35节约法的改进建议节约法的改进建议4 4)配送的总体过程实际上还会受商品分拣、装卸、搬配送的总体过程实际上还会受商品分拣、装卸、搬运设备和货物组装的共同影响运设备和货物组装的共同影响。如果在这些环节上出现不当如果在这些环节上出现不当，如设备落后而延长备如设备落后而延长备货期货期，管理不善增加这些过程中的商品损坏和组装管理不善增加这些过程中的商品损坏和组装错误等错误等，都会提高成本都会提高成本，降低服务质量降低服务质量。因此因此，在在优化配送过程优化配送过程，不但要优化配送路线和配送过程不但要优化配送路线和配送过程，还要提高配送过程其他环节的管理水平和设备的现还要提高配送过程其他环节的管理水平和设备的现代化水平代化水平。36最短路径算法1、采用、采用Dijkstra算法算法 基本思想基本思想：从vs出发，逐步向外探寻最短路。执行过程中，与每个点对应，记录下一个数（称为这个点的标号），它或者表示从vs到该点的最短路的权（称为P标号），或者是从vs到该点的最短路的上界（称为T标号），方法的每一步是去修改T标号，并且把某一个具T标号的点改变为具P标号的点，从而使D中具P标号的顶点数多一个，直至求出从vs到各点的最短路。2、应用结论、应用结论：如果P是D中从vs到vj的最短路，vi是中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。3、各路径上权值、各路径上权值wij037例题237184566134105275934682求从求从1到到8的最短路径的最短路径38237184566134105275934682X=1,w1=0min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1X=1,4,w4=1w4=1w1=0439237184566134105275934682X=1,4min c12,c16,c42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2X=1,2,4,w2=2w1=0w4=1w2=240237184566134105275934682X=1,2,4min c16,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3X=1,2,4,6,w6=3w2=2w4=1w1=0w6=341237184566134105275934682X=1,2,4,6min c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3X=1,2,4,6,7,w7=3w2=2w4=1w1=0w6=3w7=342237184566134105275934682X=1,2,4,6,7min c23,c25,c75,c78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6X=1,2,4,5,6,7,w5=6w2=2w4=1w1=0w6=3w7=3w5=643237184566134105275934682X=1,2,4,6,7min c23,c53,c58,c78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8X=1,2,3,4,5,6,7,w3=8w2=2w4=1w1=0w6=3w7=3w5=6w3=844237184566134105275934682X=1,2,3,4,6,7min c38,c58,c78=min 8+6,6+4,3+8=min 14,10,11=10X=1,2,3,4,5,6,7,8,w8=10w2=2w4=1w1=0w6=3w7=3w5=6w3=8w8=1045237184566134105275934682X=1,2,3,4,5,6,7,81到到8的最短路径为的最短路径为1，4，7，5，8，长度为，长度为10。w2=2w4=1w1=0w6=3w7=3w5=6w3=8w8=1046作业1 运输问题的合理优化471.1.（）是在一般货物运价的基础上，加上或减去一定的百分比）是在一般货物运价的基础上，加上或减去一定的百分比后公布的，适用于指定地区内少数货物的运输。后公布的，适用于指定地区内少数货物的运输。A.A.整箱货运价整箱货运价 B.B.特种货物运价特种货物运价 C.C.货物等级运价货物等级运价 D.D.一般货物运价一般货物运价 2.2.在综合运输体系中，（在综合运输体系中，（）是实现运输的基础。）是实现运输的基础。A.A.一体化的运输系统一体化的运输系统 B.B.多元化的运输系统多元化的运输系统 C.C.交通实体网络系统交通实体网络系统 D.D.交通基础网络系统交通基础网络系统 3.3.国际多式联运通常是以（国际多式联运通常是以（）为运输单元的。）为运输单元的。A.A.集装箱集装箱 B.B.卡车卡车 C.C.火车火车 D.D.轮船轮船 4.4.在国际多式联运的运输组织形式中，其中是主要组织形式的是（）在国际多式联运的运输组织形式中，其中是主要组织形式的是（）。A.A.海陆联运海陆联运 B.B.陆陆联运陆陆联运 C.C.陆桥运输陆桥运输 D.D.海空联运海空联运 5.5.在国际多式联运的运输组织形式中，（）又称为空桥运输。在国际多式联运的运输组织形式中，（）又称为空桥运输。A.A.海陆联运海陆联运 B.B.陆陆联运陆陆联运 C.C.陆桥运输陆桥运输 D.D.海空联运海空联运 486.6.运输提供的主要功能有（运输提供的主要功能有（）。）。A.A.产品生产产品生产 B.B.产品转移产品转移 C.C.产品储存产品储存 D.D.产品销售产品销售 E.E.产品延伸产品延伸 7.7.现代交通运输主要的运输方式有（现代交通运输主要的运输方式有（）。）。A.A.公路运输公路运输 B.B.铁路运输铁路运输 C.C.航空运输航空运输 D.D.水路运输水路运输E.E.管道运输管道运输8.8.国际多式联运的特征有（国际多式联运的特征有（）。）。A.A.必须订立国际多式联运合同必须订立国际多式联运合同 B.B.全程运输必须使用国际多全程运输必须使用国际多式联运单据式联运单据 C.C.全程运输必须使用两种或两种以上不同的运输全程运输必须使用两种或两种以上不同的运输方式方式 D.D.必须是国际间的货物运输必须是国际间的货物运输 E.E.多式联运经营人对全程多式联运经营人对全程运输负责运输负责 9.9.常见的国际多式联运运输组织形式有（常见的国际多式联运运输组织形式有（）。）。A.A.海陆联运海陆联运 B.B.陆陆联运陆陆联运 C.C.陆桥运输陆桥运输 D.D.海空联运海空联运 E.E.空桥运空桥运输输 10.10.以下运输方式中，在空间和时间方面具有充分的自由性，以下运输方式中，在空间和时间方面具有充分的自由性，可以实现可以实现“门到门门到门”运输的是（运输的是（）A、公路运输、公路运输 B、铁路运输、铁路运输 C、水路运输、水路运输 D、航空运输、航空运输 BCABCDEABCDEAACDE49 11、运输结点具有（、运输结点具有（）功能。这一功能将各个运输线路联结）功能。这一功能将各个运输线路联结成一个系统，便各个线路通过结点变得更为贯通，并且通成一个系统，便各个线路通过结点变得更为贯通，并且通过转换使运输更好地衔接在一起。过转换使运输更好地衔接在一起。A、衔接功能、衔接功能 B、连接功能、连接功能 C、集结功能、集结功能 D、转运功能、转运功能 12、（、（）深刻体现了交通运输业中的分工专业化与一体化的）深刻体现了交通运输业中的分工专业化与一体化的对立统一。对立统一。A、多式联运、多式联运 B、综合运输体系、综合运输体系 C、交通网络规划、交通网络规划 D、交通、交通枢纽建设枢纽建设 13、集装箱多式联运这一运输链一体化形式，它的柔性主要体、集装箱多式联运这一运输链一体化形式，它的柔性主要体现在运输链的（现在运输链的（）A、灵活性、灵活性 B、统一性、统一性 C、多变性、多变性 D、多样性、多样性 ABD50 1.综合运输体系是各种运输方式的总体或总和。综合运输体系是各种运输方式的总体或总和。2.所谓陆桥运输是指采用集装箱专用列车或卡车，把横贯大陆所谓陆桥运输是指采用集装箱专用列车或卡车，把横贯大陆的铁路或公路作为中间的铁路或公路作为中间“桥梁桥梁”，使大陆两端的集装箱海，使大陆两端的集装箱海运航线与专用列车或卡车连接起来的一种连贯运输方式。运航线与专用列车或卡车连接起来的一种连贯运输方式。严格地讲，陆桥运输也是一种海陆联运形式。严格地讲，陆桥运输也是一种海陆联运形式。3在考虑运输优化问题时，对不平衡运输问题，一般不能转在考虑运输优化问题时，对不平衡运输问题，一般不能转化为平衡运输问题来考虑。化为平衡运输问题来考虑。4.准确核算运输成本是制定运价的重要依据。准确核算运输成本是制定运价的重要依据。5综合运输体系的核心问题是（综合运输体系的核心问题是（）。）。A各种运输方式的合理分工与协调发展各种运输方式的合理分工与协调发展 B交通科技创新交通科技创新 C加大综合运输体系建设的投入加大综合运输体系建设的投入 D运输市场的自由运输市场的自由竞争竞争ABBA AA51 6（）是国际多式联运的主要组织形式。）是国际多式联运的主要组织形式。A海陆联运海陆联运 B陆陆联运陆陆联运 C海空联运海空联运 D陆空联陆空联运运7目前世界上最长的一条陆桥运输线是（目前世界上最长的一条陆桥运输线是（）。）。A美国大陆桥美国大陆桥 B西伯利亚大陆桥西伯利亚大陆桥 C加拿大大陆桥加拿大大陆桥 D新欧亚大陆桥新欧亚大陆桥8运输市场管理活动的实施运输市场管理活动的实施,必须采用（必须采用（）。）。行政手段行政手段 B法律手段法律手段 C经济手段经济手段 D以上三种的综合以上三种的综合9从运输成本的内容构成看，主要由（从运输成本的内容构成看，主要由（）构成的。）构成的。A基础设施成本基础设施成本 B运转设备成本运转设备成本 C营运成本营运成本 D作业成本作业成本 E 中转成本中转成本 10优化行业结构、提高生产效率、改善经营环境和促进行业优化行业结构、提高生产效率、改善经营环境和促进行业发展是（发展是（）。）。A运输市场管理的任务运输市场管理的任务 B运输市场管理的目标运输市场管理的目标C运输市场管理的职能运输市场管理的职能 D运输市场管理的特性运输市场管理的特性BADABCDA52 1在运输过程中，与每一次运输配送直接相关的费用，并与在运输过程中，与每一次运输配送直接相关的费用，并与运输里程和运输量成正比的费用，称为（运输里程和运输量成正比的费用，称为（）。）。A固定成本固定成本 B变动成本变动成本C综合成本综合成本 D公共成本公共成本2我国在确定运输价格时，必须遵循（我国在确定运输价格时，必须遵循（）的原则。）的原则。A运输合理化运输合理化 B以运输价值为基础以运输价值为基础C政策性政策性 D比价关系合理性比价关系合理性3构成国际多式联运必须具备构成国际多式联运必须具备()基本条件。基本条件。A具有一份多式联运合同和使用一份全程多式联运单证具有一份多式联运合同和使用一份全程多式联运单证B是省际间的货物运输是省际间的货物运输C是国际间的货物运输是国际间的货物运输D是至少两种不同运输方式的连续运输是至少两种不同运输方式的连续运输E由一个多式联运经营人对货物运输的全程负责由一个多式联运经营人对货物运输的全程负责531-1.1-1.某公司从两个产地某公司从两个产地A A1 1,A,A2 2将物品运往三个销地将物品运往三个销地B B1 1，B B2 2，B B3 3,各产地的产量、各销地的销量和各产地运往各各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示：销地的每件物品的运费如下表所示：问应如何调运，使得总运输费最小？问应如何调运，使得总运输费最小？（1）用数学规划模型表示上述问题；）用数学规划模型表示上述问题；（2）用最小元素法确定初始可行解。）用最小元素法确定初始可行解。54 设设x xijij表示从产地表示从产地A Ai i调运到调运到B Bj j的运输量（的运输量（i=1i=1，2 2；j j=1=1，2 2，3 3），例如，），例如，x x1212表示从表示从A A1 1调运到调运到B B2 2的物品数量，的物品数量，现将安排的运输量列表如下：现将安排的运输量列表如下：55 根据上表可写出此问题的数学模型。满足产地产量的约束条件为：x11+x12+x13=200，x21+x22+x23=300.满足销地销量的约束条件为：x11+x21=200，x12+x22=300，x13+x23=200.56所以该运输问题的线性规划的模型如下：目标函数：minf=6x11+4x12+6x13+6x21+5x22+5x23约束条件：x11+x12+x13=200，x21+x22+x23=300，x11+x21=150，x12+x22=150，x13+x23=200.xij0.(i=1，2；j=1，2，3)571-21-2、有三个起运站，四个目的地，供应量为50，50，75，需求量为40，55，60，20，各起运站到目的地的单位运费分别为：C C1111=3=3，C C1212=1=1，C C1313=4=4，C C1414=5=5，C C2121=7=7，C C2222=3=3，C C2323=8=8，C C2424=6=6，C C3131=2=2，C C3232=3=3，C C3333=9=9，C C3434=2.=2.（1）用运输表和数学规划模型表示上述运输问题；（2）用西北角法或最小元素法确定其初始可行解；（3）用闭回路法求其最优调运方案。58运输表（平衡运输问题运输表（平衡运输问题）1 12 23 34 4供应量供应量1 13 31 14 45 550502 27 73 38 86 650503 32 23 39 92 27575需求量需求量4040555560602020175175终点终点起点起点运输成本运输成本59运输问题表述为线型规划形式：运输问题表述为线型规划形式：min.f(x)=3X11+X12+4X13+5X14+7X21+3X22+8X23+6X24+2X31+3X32+9X33+2X34Subjectto:X11+X12+X13+X14=50X21+X22+X23+X24=50X31+X32+X33+X34=75X11+X21+X31=40X12+X22+X32=55X13+X23+X33=60X14+X24+X34=20所有所有Xij060用单纯形法解得：X X1313=50=50，X X2222=40=40，X X2323=10=10，X X3131=50=50，X X3232=15=15，X X3434=20=20，总运费为：f(x)=50f(x)=504+404+403+103+108+408+402+152+153+203+202 2 =565 =56561123供应量供应量1314502738503239100需求量需求量405060终点终点起点起点运输成本运输成本1-31-3、供供需需不不平平衡衡问问题题(见见下下表表)，3 3个个供供应应点点和和3 3个个需需求求点点，但但供供需需不不平平衡衡，供供应应总总量量大大于于需需求求总总量量，其其差差额额为为5050，请将其转化为平衡运输问题，并求优化方案。请将其转化为平衡运输问题，并求优化方案。62123虚拟点4供应量1314050273805032390100需求量40506050终点终点起点起点运输成本运输成本化为平衡运输问题化为平衡运输问题 引进虚拟需求点引进虚拟需求点4 4，需求量为，需求量为5050，运费为，运费为0 0，转化为平，转化为平衡运输问题，求解。衡运输问题，求解。63作业作业2 2 最短路径算法最短路径算法646 62 27 74 43 36 63 31 16 61 13 36 67 72-12-1、求下图中，从、求下图中，从 1 1 到到 8 8 的最短路径的最短路径656274363161367Ps=0666274363161367Ps=02,1676274363161367Ps=02,1(3)(5)(9)686274363161367Ps=02,1(5)(9)3,1(8)696274363161367Ps=02,15,23,1(9)(8)706274363161367Ps=02,15,23,18,3(9)(14)716274363161367Ps=02,15,23,18,39,2(13)(14)726274363161367Ps=02,15,23,18,39,213,6(14)7315345233355766744289982-2、假设在下图中,有9个结点组成有向网络，试求从“起点1”到达“终点9”的最短路径。74