管理学运输经济学运输合理化

会计学1管理学运输经济学运输合理化管理学运输经济学运输合理化第一节第一节第一节第一节不合理运输及其原因不合理运输及其原因不合理运输及其原因不合理运输及其原因 一、运输合理的三大要素一、运输合理的三大要素 成成本本、速速度度和和一一致致性性是是影影响响运运输输合合理理化化的的至至关关重重要要的的三三个个因因素。素。从从这这三三个个因因素素出出发发，具具体体的的运运输输作作业业就就涉涉及及到到运运输输方方式式的的选选择择，运运输输路路线线的的选选择择，及及计计划划运运输输设设备备的的使使用用时时间间，从从而而使使运运输输工工具具利利用用率率达达到到最最佳佳，并并同同时符合顾客的服务要求。时符合顾客的服务要求。第1页/共73页 1 1、成本。、成本。、成本。、成本。运运运运输输输输成成成成本本本本是是是是指指指指为为为为两两两两个个个个地地地地理理理理位位位位置置置置间间间间的的的的运运运运输输输输所所所所支支支支付付付付的的的的款款款款项项项项以以以以及及及及与与与与行行行行政政政政管管管管理理理理和和和和维维维维持持持持运运运运输输输输中中中中的的的的存存存存货货货货有有有有关的费用。关的费用。关的费用。关的费用。2 2、速度。、速度。、速度。、速度。运输速度是指完成特定的运输所需的运输速度是指完成特定的运输所需的运输速度是指完成特定的运输所需的运输速度是指完成特定的运输所需的时间时间时间时间。3 3、一致性。、一致性。、一致性。、一致性。运输的一致性是指在若干次装运中履行某运输的一致性是指在若干次装运中履行某运输的一致性是指在若干次装运中履行某运输的一致性是指在若干次装运中履行某一特定的运次所需的时间与原定时间或与前几次运一特定的运次所需的时间与原定时间或与前几次运一特定的运次所需的时间与原定时间或与前几次运一特定的运次所需的时间与原定时间或与前几次运输所需时间的一致性，它是输所需时间的一致性，它是输所需时间的一致性，它是输所需时间的一致性，它是运输可靠性的反映。运输可靠性的反映。运输可靠性的反映。运输可靠性的反映。第2页/共73页 例例例例11如图，某单位一月需要某种物资如图，某单位一月需要某种物资如图，某单位一月需要某种物资如图，某单位一月需要某种物资QQ吨，当用卡车吨，当用卡车吨，当用卡车吨，当用卡车一次运往，用户的月平均库存量为一次运往，用户的月平均库存量为一次运往，用户的月平均库存量为一次运往，用户的月平均库存量为Q/2Q/2；如果将该用；如果将该用；如果将该用；如果将该用户所需物资与其他用户的物资混合装车，每次给该企户所需物资与其他用户的物资混合装车，每次给该企户所需物资与其他用户的物资混合装车，每次给该企户所需物资与其他用户的物资混合装车，每次给该企业运送业运送业运送业运送Q/4Q/4，分，分，分，分4 4次运往，则该用户的月平均库存量降次运往，则该用户的月平均库存量降次运往，则该用户的月平均库存量降次运往，则该用户的月平均库存量降为为为为Q/8Q/8。显然，后者能使用户的库存费用降低了。显然，后者能使用户的库存费用降低了。显然，后者能使用户的库存费用降低了。显然，后者能使用户的库存费用降低了3 3倍。倍。倍。倍。（I）Q（II）Q/4库存量时间第3页/共73页 例例例例2 2 快速运输有利，还是较慢的运输有利？快速运输有利，还是较慢的运输有利？快速运输有利，还是较慢的运输有利？快速运输有利，还是较慢的运输有利？关于使用哪一种运输工具更有利的比较，不仅要看关于使用哪一种运输工具更有利的比较，不仅要看关于使用哪一种运输工具更有利的比较，不仅要看关于使用哪一种运输工具更有利的比较，不仅要看运运运运输费用，而且要考虑保管费用输费用，而且要考虑保管费用输费用，而且要考虑保管费用输费用，而且要考虑保管费用。图。图。图。图7-27-2的横轴按速度的快的横轴按速度的快的横轴按速度的快的横轴按速度的快慢排列顺序，即铁路、卡车、航空排列，也反映了运输费慢排列顺序，即铁路、卡车、航空排列，也反映了运输费慢排列顺序，即铁路、卡车、航空排列，也反映了运输费慢排列顺序，即铁路、卡车、航空排列，也反映了运输费用从低到高的顺序。用从低到高的顺序。用从低到高的顺序。用从低到高的顺序。速度成本第4页/共73页二、不合理运输的表现形式二、不合理运输的表现形式n n对流运输对流运输n n迂回运输迂回运输n n过远运输过远运输n n重复运输重复运输n n无效运输无效运输n n运力选择不当运力选择不当第5页/共73页1 1、对流运输、对流运输、对流运输、对流运输 是是指指同同类类的的或或可可以以互互相相代代替替的的货货物物的的相相向向运运输输，它它是是不不合合理理运运输输最最突突出出、最最普普遍遍的的一一种种，它它有有两两种种表现形式：表现形式：（1）明显对流。）明显对流。同同类类的的（或或可可以以互互相相代代替的）货物沿着同一线路相向运输。替的）货物沿着同一线路相向运输。（2）隐蔽对流。）隐蔽对流。当当同同类类的的（或或可可以以互互相相代代替替的的）货货物物在在不不同同运运输输方方式式的的平平行行路路线线上上或或不不同同时时间间进进行行相相反反方方向向的运输。的运输。第6页/共73页 例：有一条公路例：有一条公路例：有一条公路例：有一条公路A AD D，全长，全长，全长，全长400km400km，其中，其中，其中，其中B B、D D为煤炭为煤炭为煤炭为煤炭供应点，以供应点，以供应点，以供应点，以表示，表示，表示，表示，A A、C C为煤炭的销售点，以为煤炭的销售点，以为煤炭的销售点，以为煤炭的销售点，以表示，表示，表示，表示，各站点煤炭供求数量及站间距离如图各站点煤炭供求数量及站间距离如图各站点煤炭供求数量及站间距离如图各站点煤炭供求数量及站间距离如图7-37-3所示，试问如何所示，试问如何所示，试问如何所示，试问如何组织运输最为合理？组织运输最为合理？组织运输最为合理？组织运输最为合理？100km100km200kmABCD-3000t-500t+500t+3000t图图7-3 煤炭供应示意图煤炭供应示意图第7页/共73页2 2、迂回运输、迂回运输、迂回运输、迂回运输 由于由于由于由于物流网的纵横交错及车辆的机动、物流网的纵横交错及车辆的机动、物流网的纵横交错及车辆的机动、物流网的纵横交错及车辆的机动、灵活性，灵活性，灵活性，灵活性，在同一发站和到站之间，往往有在同一发站和到站之间，往往有在同一发站和到站之间，往往有在同一发站和到站之间，往往有不同的运输路径可供选择，不同的运输路径可供选择，不同的运输路径可供选择，不同的运输路径可供选择，凡不经过最短凡不经过最短凡不经过最短凡不经过最短路径路径路径路径的绕道运输，称为迂回运输。例：打的绕道运输，称为迂回运输。例：打的绕道运输，称为迂回运输。例：打的绕道运输，称为迂回运输。例：打的的的的 3.过远运输过远运输 这这是是一一种种舍舍近近求求远远的的商商品品运运输输。不不就就地地或或就就近近获获取取某某种种物物资资，却却舍舍近近求求远远从从外外地地或或远远处处运运来来同同种种物物资资，从从而而拉拉长长运运输输距距离离，造成运力浪费。造成运力浪费。第8页/共73页4重复运输（无效中转）重复运输（无效中转）重重重重复复复复运运运运输输输输是是是是指指指指同同同同一一一一批批批批货货货货物物物物由由由由产产产产地地地地运运运运抵抵抵抵目目目目的的的的地地地地，没没没没经经经经任任任任何何何何加加加加工工工工和和和和必必必必要要要要的的的的作作作作业业业业，也也也也不不不不是是是是为为为为联联联联运运运运及及及及中中中中转转转转需需需需要要要要，又又又又重重重重新装运到别处的现象。新装运到别处的现象。新装运到别处的现象。新装运到别处的现象。它它它它是是是是物物物物资资资资流流流流通通通通过过过过程程程程中中中中多多多多余余余余的的的的中中中中转转转转、倒倒倒倒装装装装，虚虚虚虚耗耗耗耗装装装装卸卸卸卸费费费费用用用用，造造造造成成成成车车车车船船船船非非非非生生生生产产产产性性性性停停停停留留留留，增增增增加加加加了了了了车车车车船船船船、货货货货物物物物作作作作业业业业量量量量，延延延延缓缓缓缓了了了了流流流流通通通通速速速速度度度度，增增增增大大大大了了了了货货货货损损损损，也也也也增增增增加加加加了了了了费用。费用。费用。费用。例：粮食的四散运输例：粮食的四散运输例：粮食的四散运输例：粮食的四散运输第9页/共73页5.5.无效运输无效运输 是是是是指指指指被被被被运运运运输输输输的的的的货货货货物物物物杂杂杂杂质质质质较较较较多多多多（如如如如煤煤煤煤炭炭炭炭中中中中的的的的矿矿矿矿石石石石、原原原原油油油油中中中中的的的的水水水水分分分分等等等等）使使使使运运运运输输输输能能能能力力力力浪浪浪浪费在不必要的物资运输。费在不必要的物资运输。费在不必要的物资运输。费在不必要的物资运输。例例例例如如如如我我我我国国国国每每每每年年年年有有有有大大大大批批批批圆圆圆圆木木木木进进进进行行行行远远远远距距距距离离离离的的的的调调调调运运运运，但但但但圆圆圆圆木木木木材材材材的的的的使使使使用用用用率率率率一一一一般般般般不不不不足足足足100%100%，而而而而是是是是70%70%左左左左右右右右，致致致致使使使使有有有有30%30%的的的的边边边边角角角角废废废废料料料料的的的的运运运运输输输输基本上是无效的。基本上是无效的。基本上是无效的。基本上是无效的。第10页/共73页 6 6运力选择不当运力选择不当 未考虑各种运输方式（工具）的优缺点未考虑各种运输方式（工具）的优缺点未考虑各种运输方式（工具）的优缺点未考虑各种运输方式（工具）的优缺点而进行不适当的选择造成的不合理，常见而进行不适当的选择造成的不合理，常见而进行不适当的选择造成的不合理，常见而进行不适当的选择造成的不合理，常见有以下几种形式：有以下几种形式：有以下几种形式：有以下几种形式：1 1）违违违违反反反反水水水水路路路路分分分分工工工工使使使使用用用用，弃弃弃弃水水水水走走走走陆陆陆陆的的的的运运运运输；输；输；输；2 2）铁路短途运输；）铁路短途运输；）铁路短途运输；）铁路短途运输；3 3）水运的过近运输。）水运的过近运输。）水运的过近运输。）水运的过近运输。第11页/共73页三、影响运输合理化的因素三、影响运输合理化的因素（一）外部因素（一）外部因素1、政府的交通管制、政府的交通管制 政政府府通通过过限限制制承承运运人人所所能能服服务务的的市市场场或或确确定定他他们们所所能能收收费费的的标标准准来来规规范范他他们们的的行行为为；通通过过支支持持或或提提供供诸诸如如公公路路或或航航空空交交通通控控制制系系统统之之类类的的通通行行权权来来促促进进承承运运人人。例例一一桥的单双号、禁止货车通行桥的单双号、禁止货车通行 如如英英国国和和德德国国，政政府府对对市市场场、服服务务和和费费率率保保持持绝绝对对的的控控制制，这这种种控控制制将将使使政政府府对对地地区区、行行业业或或厂厂商商的经济成功具有举足轻重的影响。的经济成功具有举足轻重的影响。第12页/共73页2 2、运输结构不合理、运输结构不合理、运输结构不合理、运输结构不合理如铁路能力过强，公路运力不足，造成用如铁路能力过强，公路运力不足，造成用如铁路能力过强，公路运力不足，造成用如铁路能力过强，公路运力不足，造成用铁路进行短途运输。铁路进行短途运输。铁路进行短途运输。铁路进行短途运输。3、运输能力不平衡、运输能力不平衡如武汉水路资源丰富，但码头能力不足，使有如武汉水路资源丰富，但码头能力不足，使有些用户弃水走陆。些用户弃水走陆。4、运输网布局的不合理、运输网布局的不合理交通运输网络的线路和港站的地区分布，及其运交通运输网络的线路和港站的地区分布，及其运输能力，直接影响运输网络的货物吸引范围，从输能力，直接影响运输网络的货物吸引范围，从而影响货运量在地区上的分布与变化。而影响货运量在地区上的分布与变化。第13页/共73页5运输参与者的目标运输参与者的目标不一致不一致 运输决策的参与者主要有运输决策的参与者主要有托运托运人、承运人、收货人及公众人、承运人、收货人及公众。托运人和收货人有共同的目的，托运人和收货人有共同的目的，就是要在规定的时间内以最低的就是要在规定的时间内以最低的成本将货物从起始地转移到目的成本将货物从起始地转移到目的地。地。承运人作为中间人，他则期望承运人作为中间人，他则期望以最低的成本完成所需的运输任以最低的成本完成所需的运输任务，同时获得最大的运输收入，务，同时获得最大的运输收入，并期望在提取和交付时间上有灵并期望在提取和交付时间上有灵活性，以便于能够使个别的装运活性，以便于能够使个别的装运整合成经济运输批量。整合成经济运输批量。第14页/共73页（二）内部因素（二）内部因素1.运输工具选择不当运输工具选择不当2.运输路线选择不合理运输路线选择不合理3.收费不合理收费不合理4.运输组织不当，缺乏全局性运输组织不当，缺乏全局性第15页/共73页四、运输合理化的有效措施四、运输合理化的有效措施10101、提高运输工具实载率。、提高运输工具实载率。n n充分利用运输工具的额定能力，减少车船充分利用运输工具的额定能力，减少车船空驶和不满载行驶的时间，减少浪费，从空驶和不满载行驶的时间，减少浪费，从而求得运输的合理化。而求得运输的合理化。n n具体手段：多渠道、多方面组织货源，政具体手段：多渠道、多方面组织货源，政策支持，物流网络化建设策支持，物流网络化建设第16页/共73页2、减少动力投入，增加运输能力、减少动力投入，增加运输能力 运输的投入主要是运输的投入主要是能耗和基础设能耗和基础设施的建设施的建设，在设施建设已定型和完，在设施建设已定型和完成的情况下，尽量减少能源投入，成的情况下，尽量减少能源投入，是少投入的核心。是少投入的核心。(1)(1)“满载超轴满载超轴”。“超轴超轴”的的含义就是在机车能力允许情况下，含义就是在机车能力允许情况下，多加挂车皮。多加挂车皮。(2)(2)水运拖排和拖带。水运拖排和拖带。将无动力将无动力驳船编成一定队形，一般是驳船编成一定队形，一般是“纵列纵列”，用拖轮拖带行驶，可以有比船，用拖轮拖带行驶，可以有比船舶载乘运输运量大的优点，求得合舶载乘运输运量大的优点，求得合理化。理化。3 3）汽车挂车。）汽车挂车。第17页/共73页3、发展社会化运输体系、发展社会化运输体系 运运运运输输输输社社社社会会会会化化化化的的的的含含含含义义义义是是是是发发发发展展展展运运运运输输输输的的的的大大大大生生生生产产产产优优优优势势势势，实实实实行行行行专专专专业业业业分分分分工工工工，打打打打破破破破一一一一家家家家一一一一户户户户自自自自成成成成运运运运输输输输体体体体系系系系的的的的状状状状况况况况，使使使使社会运输资源得到最有效的配置。社会运输资源得到最有效的配置。社会运输资源得到最有效的配置。社会运输资源得到最有效的配置。第18页/共73页 4、合理选择运输方式和运输工具、合理选择运输方式和运输工具 选择运输方式应考虑的因素：选择运输方式应考虑的因素：（1 1）运输物品的特性（物品的形状、单件重）运输物品的特性（物品的形状、单件重）运输物品的特性（物品的形状、单件重）运输物品的特性（物品的形状、单件重量和体积、危险性和易腐性量和体积、危险性和易腐性量和体积、危险性和易腐性量和体积、危险性和易腐性 ）；）；）；）；（2 2）运量（运输批量的大小）运量（运输批量的大小）运量（运输批量的大小）运量（运输批量的大小 ）；）；）；）；（3 3）运输距离；）运输距离；）运输距离；）运输距离；（4 4）在途时间（物品的到货期）在途时间（物品的到货期）在途时间（物品的到货期）在途时间（物品的到货期 ）；）；）；）；（5 5）运输费用。）运输费用。）运输费用。）运输费用。第19页/共73页 5尽量发展直达运输尽量发展直达运输 直达运输是追求运输合理化的重要直达运输是追求运输合理化的重要直达运输是追求运输合理化的重要直达运输是追求运输合理化的重要形式，可以形式，可以形式，可以形式，可以减少中转过载换装减少中转过载换装减少中转过载换装减少中转过载换装、提高、提高、提高、提高运输速度、节省装卸费用、降低中转运输速度、节省装卸费用、降低中转运输速度、节省装卸费用、降低中转运输速度、节省装卸费用、降低中转货损。例如组织多式联运货损。例如组织多式联运货损。例如组织多式联运货损。例如组织多式联运 第20页/共73页6配载运输配载运输 充分利用运输工具充分利用运输工具充分利用运输工具充分利用运输工具载重量和容积载重量和容积载重量和容积载重量和容积，合理安排装载的物品及载运方法，提高合理安排装载的物品及载运方法，提高合理安排装载的物品及载运方法，提高合理安排装载的物品及载运方法，提高运输工具实载率运输工具实载率运输工具实载率运输工具实载率 由于每辆车的载重量或容积有由于每辆车的载重量或容积有由于每辆车的载重量或容积有由于每辆车的载重量或容积有限，而各种货物的单位体积与重量又大限，而各种货物的单位体积与重量又大限，而各种货物的单位体积与重量又大限，而各种货物的单位体积与重量又大小不一，因而为提高货车的利用率，需小不一，因而为提高货车的利用率，需小不一，因而为提高货车的利用率，需小不一，因而为提高货车的利用率，需要对各种货物的装载进行配装。要对各种货物的装载进行配装。要对各种货物的装载进行配装。要对各种货物的装载进行配装。第21页/共73页假设：某配送中心有一辆载重量为假设：某配送中心有一辆载重量为假设：某配送中心有一辆载重量为假设：某配送中心有一辆载重量为GG的的的的货车，用于配送货车，用于配送货车，用于配送货车，用于配送n n种不同的货物，货种不同的货物，货种不同的货物，货种不同的货物，货物的单位重量分别为物的单位重量分别为物的单位重量分别为物的单位重量分别为wi(i=1,2n),wi(i=1,2n),每每每每种货物对应的价值系数分别为种货物对应的价值系数分别为种货物对应的价值系数分别为种货物对应的价值系数分别为pipi，XkXk表示第表示第表示第表示第k k种商品的装入量，则可以建种商品的装入量，则可以建种商品的装入量，则可以建种商品的装入量，则可以建立以下函数关系立以下函数关系立以下函数关系立以下函数关系第22页/共73页目标函数：约束条件：我们可以将每装一种商品视为一个阶段，装入的我们可以将每装一种商品视为一个阶段，装入的顺序不会影响最后的结果。所以，上述问题的求顺序不会影响最后的结果。所以，上述问题的求解一般采用运筹学动态规划中解一般采用运筹学动态规划中背包问题求解背包问题求解。第23页/共73页n n例：某车辆的载重量为例：某车辆的载重量为10t，配，配装三种不同的商品（装三种不同的商品（）。）。每种商品单位重量分别为每种商品单位重量分别为3t，4t，5t，其获利情况分别为，其获利情况分别为4千元、千元、5千元、千元、6千元。问如何配装利千元。问如何配装利润最大？润最大？目标函数：目标函数：约束条件：约束条件：答案：第24页/共73页货物配载的简化方法货物配载的简化方法货物配载的简化方法货物配载的简化方法在实际工作中，货物配装涉及在实际工作中，货物配装涉及2个个限制：限制：容积、载重量。容积、载重量。载重量：轻上重下载重量：轻上重下容积：体积大在下容积：体积大在下另外，对于一些品种少，体积比另外，对于一些品种少，体积比较规则的商品，可以采用手工较规则的商品，可以采用手工的方法进行配装计算。的方法进行配装计算。第25页/共73页n n例如：配装例如：配装2种商品种商品A、B，其，其单位体积分别为单位体积分别为Av、Bv，单位，单位重量分别为重量分别为Aw、Bw,车辆载重车辆载重量为量为W，容积为，容积为V。n n首先首先，观察商品外形尺寸，估，观察商品外形尺寸，估计容积利用率（计容积利用率（90%）；）；n n其次其次，设装入，设装入A、B商品的数量商品的数量分别为分别为Xa、Yb，则：，则：解上述方程，求整数解，即可得解上述方程，求整数解，即可得A、B的配载数量。的配载数量。第26页/共73页 7“四就四就”直拨运输直拨运输 “四四四四就就就就”直直直直拨拨拨拨，由由由由管管管管理理理理机机机机构构构构预预预预先先先先筹筹筹筹划划划划，就就就就厂厂厂厂、就就就就站站站站（码头）、（码头）、（码头）、（码头）、就就就就库、库、库、库、就就就就车（船）将物品分送给客户。车（船）将物品分送给客户。车（船）将物品分送给客户。车（船）将物品分送给客户。第27页/共73页 8发展特殊运输技术和运输工具发展特殊运输技术和运输工具 发发发发展展展展专专专专用用用用散散散散装装装装及及及及罐罐罐罐车车车车、大大大大型型型型半半半半挂挂挂挂车车车车、“滚滚滚滚装装装装船船船船”、集集集集装装装装箱箱箱箱船船船船、集集集集装装装装箱箱箱箱高高高高速速速速直直直直达达达达车车车车等等等等，针针针针对对对对商商商商品品品品的的的的特特特特性性性性，组织运输。组织运输。组织运输。组织运输。例如粮食的四散运输：散装、散运、散存、散卸例如粮食的四散运输：散装、散运、散存、散卸例如粮食的四散运输：散装、散运、散存、散卸例如粮食的四散运输：散装、散运、散存、散卸 9通过流通加工，减少无效运输通过流通加工，减少无效运输木材加工、钢材剪切加工等。木材加工、钢材剪切加工等。第28页/共73页 10优化运输路线优化运输路线n n发送者应如何分组来制定路线？发送者应如何分组来制定路线？n n 什么是最好的服务顾客的发送顺序？什么是最好的服务顾客的发送顺序？n n 哪一条路线应分派给哪一种车辆？哪一条路线应分派给哪一种车辆？n n 对对于于服服务务于于不不同同的的客客户户类类型型，什什么么是是最最好好的车辆类型？的车辆类型？n n客户是如何限制发送时间的？客户是如何限制发送时间的？第29页/共73页第二节第二节运输优化的基本问题运输优化的基本问题 所所谓谓运运输输优优化化，是是指指在在一一定定的的运运输输条条件件下下（如如道道路路、车车辆辆），如如何何使使输输送送量量最最大大，输输送送距距离最短，输送费用最省离最短，输送费用最省。运运输输优优化化通通常常是是运运用用运运筹筹学学和和系系统统工工程程中中的的方方法法解解决决。制制定定运运输输优优化化方方案案时时，先先要要解解决最短运输路线等基本问题。决最短运输路线等基本问题。第30页/共73页 一、求两点之间最短路径一、求两点之间最短路径 求最短路径，常常是运输优化求最短路径，常常是运输优化问题中首先要解决的问题，而且，问题中首先要解决的问题，而且，它本身也是一个优化问题。如武钢它本身也是一个优化问题。如武钢的钢材要运往神龙公司，汽车应按的钢材要运往神龙公司，汽车应按什么路线行驶，运距最短；再如，什么路线行驶，运距最短；再如，武钢的钢材如果放在武汉市地区的武钢的钢材如果放在武汉市地区的几个仓库，当需要调往多个用户时，几个仓库，当需要调往多个用户时，就要制定优化运输方案，制定方案就要制定优化运输方案，制定方案时首先要解决的是仓库到用户的最时首先要解决的是仓库到用户的最短运输路线问题。短运输路线问题。第31页/共73页 例：如图所示为一有六个节点的运输网络，网络例：如图所示为一有六个节点的运输网络，网络例：如图所示为一有六个节点的运输网络，网络例：如图所示为一有六个节点的运输网络，网络中的路权均以公里表示，求节点中的路权均以公里表示，求节点中的路权均以公里表示，求节点中的路权均以公里表示，求节点v v1 1至至至至v v6 6的最短路线的最短路线的最短路线的最短路线及路程。及路程。及路程。及路程。174522512V1V2V4V5V6V3第32页/共73页第33页/共73页 表中第一列为迭代序号，主栏中为历次迭代的表中第一列为迭代序号，主栏中为历次迭代的表中第一列为迭代序号，主栏中为历次迭代的表中第一列为迭代序号，主栏中为历次迭代的标号值，下面有标号值，下面有标号值，下面有标号值，下面有“-”-”的表示永久标号值，的表示永久标号值，的表示永久标号值，的表示永久标号值，V Vk k列记录列记录列记录列记录每次迭代所得到的永久性标号点，每次迭代所得到的永久性标号点，每次迭代所得到的永久性标号点，每次迭代所得到的永久性标号点，P P（V Vk k）为其相）为其相）为其相）为其相对应的永久标号；改进点即为迭代过程中标号值有对应的永久标号；改进点即为迭代过程中标号值有对应的永久标号；改进点即为迭代过程中标号值有对应的永久标号；改进点即为迭代过程中标号值有改进的点，导致点即为导致它们改进的点。改进的点，导致点即为导致它们改进的点。改进的点，导致点即为导致它们改进的点。改进的点，导致点即为导致它们改进的点。V1 V2 V3 V4 V5 V6 Vk P（Vk）改进点 导致点 1 0 V1 0 V1 V1 2 1 4 V2 1 V2,V3 V1 3 3 8 6 V3 3 V3 V4 V5 V2 4 8 5 V4 5 V5 V3 5 6 7 V5 6 V4，V6 V5 6 7 V6 7 V6 第34页/共73页 例：如图所示为一有六个节点的运输网络，网络例：如图所示为一有六个节点的运输网络，网络例：如图所示为一有六个节点的运输网络，网络例：如图所示为一有六个节点的运输网络，网络中的路权均以公里表示，求节点中的路权均以公里表示，求节点中的路权均以公里表示，求节点中的路权均以公里表示，求节点v v1 1至至至至v v6 6的最短路线的最短路线的最短路线的最短路线及路程。及路程。及路程。及路程。174522512V1V2V4V5V6V3第35页/共73页第36页/共73页二、多点之间最短路问题二、多点之间最短路问题n n在运输路线规划时，最常见的问在运输路线规划时，最常见的问题是多点之间最短路问题。例如，题是多点之间最短路问题。例如，配送中心一次按顺序为多个用户配送中心一次按顺序为多个用户配送商品，完成后返回配送中心。配送商品，完成后返回配送中心。或在配送网络中物流中心向配送或在配送网络中物流中心向配送中心配送也存在该问题。这类问中心配送也存在该问题。这类问题可以归纳为运筹学中题可以归纳为运筹学中旅行商问旅行商问题题和和中国邮递员问题。中国邮递员问题。第37页/共73页旅行商问题旅行商问题旅行商问题旅行商问题n n旅行商问题描述：旅行商问题描述：n n一个推销员从城市一个推销员从城市1出发到其他出发到其他城市，每个城市他只能去一次，城市，每个城市他只能去一次，且只能去一次，最后回到城市且只能去一次，最后回到城市1。问：如何选择行进路线，从而问：如何选择行进路线，从而使总行程最短？使总行程最短？n n旅行商问题的算法，目前已有旅行商问题的算法，目前已有多种。我们主要介绍最邻近法多种。我们主要介绍最邻近法和匈牙利算法。和匈牙利算法。第38页/共73页n n无向图的距离矩阵是对称的。穷举无向图的距离矩阵是对称的。穷举无向图的距离矩阵是对称的。穷举无向图的距离矩阵是对称的。穷举需要是需要是需要是需要是4!/24!/24!/24!/2次。先次。先次。先次。先减价减价减价减价d d d dijijijij从小到大排序。从小到大排序。从小到大排序。从小到大排序。取最小五个，取最小五个，取最小五个，取最小五个，下标每个出现下标每个出现下标每个出现下标每个出现两次即可，否则两次即可，否则两次即可，否则两次即可，否则换稍长的边换稍长的边换稍长的边换稍长的边。v1v2v5v4v311117223131086（一）旅行商问题（一）旅行商问题-匈牙利算法匈牙利算法第39页/共73页n n减价减价:每行每行减去该行的减去该行的最小值，最小值，再每列减去该再每列减去该再每列减去该再每列减去该列的最小值。列的最小值。列的最小值。列的最小值。再从下表中找出最再从下表中找出最再从下表中找出最再从下表中找出最小的五个元，检查它小的五个元，检查它小的五个元，检查它小的五个元，检查它们的下标是否满足要们的下标是否满足要们的下标是否满足要们的下标是否满足要求？不！就调整。求？不！就调整。求？不！就调整。求？不！就调整。第40页/共73页n n调整两次即得。调整两次即得。调整两次即得。调整两次即得。第41页/共73页n n最优路线：最优路线：v1v2v5v4v311117223131086x1x13 3x3x34 4x2x24 4x2x25 5x1x15 5第42页/共73页（二）旅行商问题（二）旅行商问题（二）旅行商问题（二）旅行商问题-最邻近法（有向图）最邻近法（有向图）最邻近法（有向图）最邻近法（有向图）n n由于规定推销员是从城市由于规定推销员是从城市1开始的，开始的，设推销员已走到城市设推销员已走到城市i，记，记表示由城市表示由城市表示由城市表示由城市1 1 1 1到城市到城市到城市到城市i i i i的中间城市的集合。的中间城市的集合。的中间城市的集合。的中间城市的集合。S表示到达城市表示到达城市i之前之前中途所经过的城中途所经过的城市集合市集合，则有：则有：因此，可选择（因此，可选择（i，S）作为描述过程）作为描述过程的的状态变量状态变量，决策为由一个城市走，决策为由一个城市走到另一个城市，并定义到另一个城市，并定义最优值函数最优值函数为从城市为从城市1开始经由开始经由k个中间城市的个中间城市的S集到城市集到城市i的的最短路线的距离最短路线的距离。第43页/共73页则动态规划的递推关系为：则动态规划的递推关系为：则动态规划的递推关系为：则动态规划的递推关系为：边界条件为：边界条件为：边界条件为：边界条件为：为最优决策函数为最优决策函数，它表示从城市，它表示从城市1开始经开始经k个中间个中间城市的城市的S集到城市集到城市i的最短路线上的最短路线上紧挨着城市紧挨着城市i前面的那个城市。前面的那个城市。第44页/共73页n n举例：求解举例：求解4个城市推销员问题个城市推销员问题。距离矩阵如表所示。设推销。距离矩阵如表所示。设推销员从城市员从城市1出发，经过每一个城出发，经过每一个城市且仅一次，最后回到城市市且仅一次，最后回到城市1。问怎样走行程最短？问怎样走行程最短？j:1234i：1 01020302 12018303 239054 343240第45页/共73页解：解：由边界条件可知：由边界条件可知：j:1234i：1 01020302 12018303 239054 343240第46页/共73页当K=1时，即从城市1开始，中间经过一个城市到达城市i的最短距离为：j:1234i：1 01020302 12018303 239054 343240第47页/共73页当K=2时，即从城市1开始，中间经过2个城市到达城市i的最短距离为：j:1234i：1 01020302 12018303 239054 343240决策函数：决策函数：决策函数：决策函数：决策函数：决策函数：第48页/共73页当K=3时，即从城市1开始，中间经过3个城市到达城市1的最短距离为：j:1234i：1 01020302 12018303 239054 343240决策函数：决策函数：故，推销员的最短旅行路线：故，推销员的最短旅行路线：14321，最短总距离为最短总距离为55。第49页/共73页j:12345i：1 0102030402 1201830253 23905104 34324085 452711100作业：第50页/共73页第三节第三节 直达供货系统的运输直达供货系统的运输 一、运输规划原理一、运输规划原理运输规划研究的是单一品种物资的典型运运输规划研究的是单一品种物资的典型运运输规划研究的是单一品种物资的典型运运输规划研究的是单一品种物资的典型运输问题输问题输问题输问题。运输问题是一种应用广泛的网络最优化模型，其主要目运输问题是一种应用广泛的网络最优化模型，其主要目的是为物资调的是为物资调运、车辆调度选择最经济的运输路线。有运、车辆调度选择最经济的运输路线。有些问题，比如有些问题，比如有m台机床加工台机床加工n种零件的问题，工厂的种零件的问题，工厂的合理布局问题等，虽要求与提法不同，但经过适当变化合理布局问题等，虽要求与提法不同，但经过适当变化也可以使用本模型求得最优解。也可以使用本模型求得最优解。第51页/共73页运输问题的一般提法是：运输问题的一般提法是：某种物资有某种物资有m个产地个产地iA，产量分别为，产量分别为),.,2,1(miai=，有，有n个销个销 地地jB，销量（需求最）分别为，销量（需求最）分别为),.,2,1(njbj=,已知已知iA到到jB的单位运的单位运 价为价为),.,2,1;,.,2,1(nnmicij=是平衡的，是平衡的，问应如何安排运输可使总运费最小？，问应如何安排运输可使总运费最小？假定假定ijx表示由表示由iA 到到jB的运输量，则平衡条件下的的运输量，则平衡条件下的 如下的线性规划模型：如下的线性规划模型：运输问题的一般提法和模型运输问题的一般提法和模型，假设产销，假设产销运输问题可写出运输问题可写出第52页/共73页 s.t),.,2,1(1miaxinjij=),.,2,1(1njbxjmiij=0ijx 平衡条件下的运输问题一定有最优解。平衡条件下的运输问题一定有最优解。显然，由于运输问题属线性规划问题，因此无疑可以用显然，由于运输问题属线性规划问题，因此无疑可以用单纯形方法单纯形方法求解，但由于其数学模型自身结构的特殊性，求解，但由于其数学模型自身结构的特殊性，也可以利用更简便的方法来求解。这与运输问题的特点也可以利用更简便的方法来求解。这与运输问题的特点有关。有关。第53页/共73页二、图上作业法二、图上作业法n n在交通图上，用表示生产地/供应地，供应量用表示，用表示销售地/需求地，需求量用表示。物流流动方向用，流量标在右边。把表明物流的流向、流量的交通图称为流向图。n n图上作业法的核心就是规划出物流的最优流向图，最优流向图是指没有对流、迂回运输的流向图。第54页/共73页n n图上作业法的步骤：1、根据任务，编制产销平衡表；2、绘制交通图；3、按就近运输的原则，绘制初始流向图，并检验；4、如不是最优图，调整初始方案；5、进一步检验调整后的流向图。第55页/共73页举例举例A3B3A4A1A2B1B4B2280180165118165252317118349第56页/共73页n n检验的方法：检验的方法：d内（外）内（外）0.5 dn n图上作业法的口诀：图上作业法的口诀：n n流向画右方，对流不应当；内圈外圈分别流向画右方，对流不应当；内圈外圈分别算，要求不过半圈长。算，要求不过半圈长。第57页/共73页二、表上作业法（最小元素法）二、表上作业法（最小元素法）二、表上作业法（最小元素法）二、表上作业法（最小元素法）表上作业法的解题步骤表上作业法的解题步骤 表上作业法的基本思想是表上作业法的基本思想是:先设法给出一个初始方先设法给出一个初始方案案,然后根据确定的判别准则对初始方案进行检查、调然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案，如图整、改进，直至求出最优方案，如图7-17-1所示。这和单所示。这和单纯形法的求解思想完全一致，但是具体的作法则更加纯形法的求解思想完全一致，但是具体的作法则更加简捷。简捷。确 定 初 始方 案（初始 基 本 可行解）判定是否最优？改进调整（换基迭代）结束否是图7-1 运输问题求解思路图第58页/共73页例某公司有三个工厂B1、B2、B3，生产中需要同一种原料，另有三个仓库A1、A2、A3可供应这种原料，由于供需双方两两间的相对位置不同因而运价不同，有关数据如下表：B1 B2 B3 B4 产量 A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 6 5 9 销 量 3 6 5 6 20问应如何安排运输才能使总运费为最小？问应如何安排运输才能使总运费为最小？第59页/共73页n n应用表上作业法通常可分为四个步骤：应用表上作业法通常可分为四个步骤：1、运用最小元素法确定初始方案、运用最小元素法确定初始方案2、检验（位势法），若所有空格检验数均大、检验（位势法），若所有空格检验数均大于等于于等于0，则初始方案为最优方案，则初始方案为最优方案3、调整、调整4、再检验、再检验第60页/共73页例例 某车间有四项产品加工任务某车间有四项产品加工任务B1、B2、B3、B4，该车间有，该车间有三种设备三种设备A1、A2、A3可用于加工这些产品，由于每种设可用于加工这些产品，由于每种设备的性能不同因而加工每一种产品的效率不同，有关数据备的性能不同因而加工每一种产品的效率不同，有关数据如下表：如下表：B1 B2 B3 B4 可利用工时 A1 6 7 5 3 14 A2 8 4 2 7 27 A3 5 9 10 6 19 需要工时 22 13 12 13 运价为单位时间加工的产品数量（运价为单位时间加工的产品数量（kg/h）,问应如何安问应如何安排加工才能使总效率最高排加工才能使总效率最高(加工的产品最多加工的产品最多)？运输问题实际上也可以看作是一个运输问题实际上也可以看作是一个mn分派问题。本分派问题。本例就是一个分派问题，因此完全可以用运输问题的解法求例就是一个分派问题，因此完全可以用运输问题的解法求解。解。三、三、最大元素法最大元素法第61页/共73页A2A3B2A1B3B4B1运输问题网络图运输问题网络图运输问题网络图运输问题网络图s2=27s3=19d1=22d2=13d3=12d4=13s1=14供应量供应地运价需求量需求地675384275910 6第62页/共73页运输问题线性规划模型运输问题线性规划模型运输问题线性规划模型运输问题线性规划模型供应地约束需求地约束第63页/共73页运输问题的表格表示运输问题的表格表示运输问题的表格表示运输问题的表格表示 B1 B2 B3 B4 6 7 5 3 A1 x11 x12 x13 x14 14 8 4 2 7 A2 x21 x22 x23 x24 27 5 9 10 6 A3 x31 x32 x33 x34 19 22 13 12 13 第64页/共73页初始基础可行解初始基础可行解最大元素法最大元素法 解最大化问题的基本思路可以有两种，一种是用解最大化问题的基本思路可以有两种，一种是用最大元素法，使检验数为正数达到最优最大元素法，使检验数为正数达到最优，另一种是使，另一种是使用最小元素法，需要用最大运价减去每一运价形成新用最小元素法，需要用最大运价减去每一运价形成新的产销平衡表。的产销平衡表。12 722756858第65页/共73页-2 11=(c14+c21)-(c11+c24)=(3+8)(6+7)=-2 经检验，检验数 112，故需调整方案。这时的总产品数为 Z 42241763563120460(kg)第66页/共73页 运输问题的一个应用实例运输问题的一个应用实例运输问题的一个应用实例运输问题的一个应用实例 某公司承担某公司承担6个港口城市个港口城市A、B、C、D、E、F之间之间的四条固定航线的物资运输任务，已知道的四条固定航线的物资运输任务，已知道4个航线的个航线的起点、终点城市及每天的航班数如下表：起点、终点城市及每天的航班数如下表：航线 起点 终点 每天航班数 1 E D 3 2 B C 2 3 A F 1 4 D B 1假定各航线使用相同型号的船只，各城市之间的航程天数航程天数航程天数航程天数如下表：A B C D E F A 0 1 2 14 7 7 B 0 3 13 8 8 C 0 15 5 5 D 0 17 20 E 0 3 F 0第67页/共73页已知道每条船只每次装卸货物的已知道每条船只每次装卸货物的时间各需要时间各需要1天，问该公司至少天，问该公司至少需要配备多少船只才能满足所需要配备多少船只才能满足所有航线的运货需求？有航线的运货需求？n n解：这是一个生产能力配备问解：这是一个生产能力配备问题。可考虑将公司所需配备的题。可考虑将公司所需配备的船只数分为两个部分：（船只数分为两个部分：（1）载载货航程所需的周转船只数货航程所需的周转船只数。如航线如航线1，在港口，在港口E装货装货1天，天，由由E到到D航程航程17天，在天，在D卸货卸货1天，天，共共19天，每天天，每天3班，共需周转船班，共需周转船只数只数57条。如此计算的各航线条。如此计算的各航线周转船只数共周转船只数共91条条，详见下表：，详见下表：第68页/共73页航线航线装货装货天数天数航程航程天数天数卸货卸货天数天数小计小计航班航班数数需船需船只数只数1.ED1171193572.BC13152103.AF 1719194.DB 113115115合计合计91第69页/共73页（2 2）各港口间调度所需船只数。各港口间调度所需船只数。各港口间调度所需船只数。各港口间调度所需船只数。n n由于各港口每天到达的船只数与所需要的船只数不由于各港口每天到达的船只数与所需要的船只数不由于各港口每天到达的船只数与所需要的船只数不由于各港口每天到达的船只数与所需要的船只数不等，必须对各港口的供需进行平衡。如等，必须对各港口的供需进行平衡。如等，必须对各港口的供需进行平衡。如等，必须对各港口的供需进行平衡。如D D每天到达的每天到达的每天到达的每天到达的船只有船只有船只有船只有3 3条，发出则只需要条，发出则只需要条，发出则只需要条，发出则只需要1 1条，各港口条，各港口条，各港口条，各港口每天余缺的每天余缺的每天余缺的每天余缺的船只数船只数船只数船只数如下表：如下表：如下表：如下表：港口港口城市城市ABCDEF每天每天到达到达012301每天每天需求需求120130余缺余缺数数-1-122-31第70页/共73页n n要使得配备的船只数最少，其实要使得配备的船只数最少，其实质就是要使用于周转的空船数最质就是要使用于周转的空船数最少。因此可建立如下的运输问题，少。因此可建立如下的运输问题，运价是运价是各港口间的航程天数各港口间的航程天数，其，其产销平衡表为：产销平衡表为：n nA B E A B E 每天多余船只每天多余船只C 2 C 2 1 1 3 5 3 5 1 1 2 2D 14 13 D 14 13 17 17 2 2 2 2F 7 8 F 7 8 1 1 3 1 3 1每天缺少船只每天缺少船只1 1 31 1 3第71页/共73页n n因因因因13=-1213=-12，故需将方案调整为：，故需将方案调整为：，故需将方案调整为：，故需将方案调整为：n nA B E A B E 每每天多余船只天多余船只n n C 2 C 2 1 1 3 3 5 5 1 1 2 2n n D 14 13 D 14 13 1 1 17 17 1 1 2 2n n F 7 8 3 F 7 8 3 1 1 1 1 每天缺少船只每天缺少船只1 1 31 1 3n n 所有检验数已全部非正，故得到最优方案。所有检验数已全部非正，故得到最优方案。所有检验数已全部非正，故得到最优方案。所有检验数已全部非正，故得到最优方案。按该方案所需的空船总数是：按该方案所需的空船总数是：按该方案所需的空船总数是：按该方案所需的空船总数是：Z=40Z=40。所以，该。所以，该。所以，该。所以，该公司应配备的船只总数应是：公司应配备的船只总数应是：公司应配备的船只总数应是：公司应配备的船只总数应是：91+40=13191+40=131条。条。条。条。第72页/共73页