1、物流运输与配送物流运输与配送管理实务管理实务主讲：李主讲：李 颖颖郑州大学西亚斯国际学院郑州大学西亚斯国际学院商学院商学院第第2章章 物流运输规划物流运输规划本章知识结构本章知识结构物物流流运运输输规规划划合理选择运输方式合理选择运输方式运输问题与线性规划运输问题与线性规划 旅行路线问题旅行路线问题 小结与案例小结与案例 图论方法的应用图论方法的应用各种运输方式的特点各种运输方式的特点线性规划模型及单纯形法线性规划模型及单纯形法旅行路线问题及求解旅行路线问题及求解邮路问题、最小联通问邮路问题、最小联通问题及各自的求解方法题及各自的求解方法 目前我国最常用的运输方式有哪些？目前我国最常用的运输方
2、式有哪些？引言 每一个国家的经济地理环境和工业化程度不同，运输方式的构成也有差异。例如，在缺乏河流的内陆国家，就几乎没有水路运输；在工业化程度很低的国家，航空运输的比例比较低。就近代运输业发展的一段历史来看，船舶运输是较早使用的一种机械运输方式。1807年，世界上第一艘轮船在北美哈德逊河下水，揭开了机械运输的新纪元。其后，各种运输工具相继问世。1825年，世界上第一条铁路在英国正式通车，1861年，第一条输油管道铺设；1886年，以汽油为动力的汽车在德国问世。到1903年第一架飞机飞上了蓝天。在经历了整整一个世纪后，五种新型运输工具奠定了以五种运输方式为基本格局的运输业。2.1 合理选择运输方
3、式合理选择运输方式一、公路运输一、公路运输设施：公路、公路车站和车辆。设施：公路、公路车站和车辆。优点优点：对于小、中批量商品的近距离运输，运费较便：对于小、中批量商品的近距离运输，运费较便宜，而且经济；可以做到宜，而且经济；可以做到“门到门门到门”（doorto door)；包装成本低。包装成本低。缺点缺点：运输能力低；单位运费高；易遭偷盗；加剧拥：运输能力低；单位运费高；易遭偷盗；加剧拥挤与污染挤与污染二、铁路运输二、铁路运输设施：铁路、火车、车站及辅助设备设施：铁路、火车、车站及辅助设备优点优点：运载能力较大，适用于大宗货物的集中、迅速运：运载能力较大，适用于大宗货物的集中、迅速运 输；
4、中、远距离运输时，输；中、远距离运输时，运费比较便宜；受气运费比较便宜；受气 候条件的影响较小候条件的影响较小；在轨道上运输，安全性好；在轨道上运输，安全性好缺点缺点：灵活性差；对包装的要求较高；基建成本大。：灵活性差；对包装的要求较高；基建成本大。三、水上运输三、水上运输 设施：天然水道、港口和船舶。设施：天然水道、港口和船舶。优点优点：高运输能力；：高运输能力；低廉的单位运费低廉的单位运费。缺点缺点：速度慢；路线迂回；受天气影响大，可靠性差：速度慢；路线迂回；受天气影响大，可靠性差四、航空运输四、航空运输 设施：航空港、飞行器和航管设施。设施：航空港、飞行器和航管设施。优点优点：速度快速度
5、快；受地形条件限制小。；受地形条件限制小。缺点缺点：运输成本高；运载量有限；受气候影响大。：运输成本高；运载量有限；受气候影响大。五、管道运输五、管道运输 管道是一种集运输工具和运输线路于一身的管道是一种集运输工具和运输线路于一身的运输方式。采用管道运输，货物凭借高压气泵的运输方式。采用管道运输，货物凭借高压气泵的压力在管道内移动，到达目的地。压力在管道内移动，到达目的地。三种形式：液体管道、气体管道、浆质管道。三种形式：液体管道、气体管道、浆质管道。优点优点：可全天候工作可全天候工作；不需包装；单向运输；单；不需包装；单向运输；单位运营成本低。位运营成本低。缺点缺点：货物受限；机动灵活性小，
6、初期投资大。：货物受限；机动灵活性小，初期投资大。运输方式运输方式速速度度运运量量运价运价适合货物适合货物的特点的特点优优 点点缺缺 点点航空运输航空运输（飞机）最最快快少少最昂最昂贵贵贵重，急贵重，急需，时间需，时间要求紧要求紧速度快，包速度快，包装简单装简单运费高，有运费高，有重量限制重量限制水路运输水路运输（轮船）最最慢慢最最多多最便最便宜宜大宗货物大宗货物时间宽松时间宽松价格便宜价格便宜速度慢，受速度慢，受气候影响大气候影响大公路运输公路运输（汽车）较较慢慢较较少少较贵较贵灵活，量灵活，量少少,路程短路程短灵活，方便灵活，方便（door-to-door）装载量小，装载量小，不适合长途不
7、适合长途运输。运输。铁路运输铁路运输（火车）较较快快较较多多较便较便宜宜量大，时量大，时间较紧间较紧安全安全,可靠可靠中转作业时中转作业时间长间长管道运输管道运输（管道）连连续续大大便宜便宜气体、液气体、液体、连续体、连续性强性强货损货差少货损货差少，连续运输，连续运输适用产品较适用产品较少少各种交通运输方式的比较各种交通运输方式的比较 在选择运输工具的时候，主要考虑的因素：在选择运输工具的时候，主要考虑的因素：u运输数量：运输数量：1520吨以下的货物，采用公路运输；吨以下的货物，采用公路运输；1520吨以上的货物，采用铁路运输；吨以上的货物，采用铁路运输；数百吨以上的原材料之类的货物，应选
8、择水路运输。数百吨以上的原材料之类的货物，应选择水路运输。u运输价格：运输价格：u运输速度运输速度 航空最快达到航空最快达到900 1000km/h；铁路铁路80 250 km/h；公路公路80 120km/h；水路中的河运水路中的河运820 km/h，海运每小时海运每小时1030海里。海里。在选择运输工具的时候，主要在选择运输工具的时候，主要考虑的因素：考虑的因素：u货物性质货物性质u运输距离：运输距离：200公里以内，采用公路运输；公里以内，采用公路运输；200500公里的区域，采用铁路运输；公里的区域，采用铁路运输；500公里以上根据具体情况采用水路或公里以上根据具体情况采用水路或航空运
9、输；航空运输；u特别要求特别要求运运输输方方 式式选选择择的的原原则则贵重或急需的货物（数量不大）贵重或急需的货物（数量不大）航空航空 短途短途公路公路容易死亡、变质的容易死亡、变质的活物、鲜货物活物、鲜货物 长途且数量大长途且数量大铁路铁路大宗、笨重的货物（远距离运输）大宗、笨重的货物（远距离运输）水运或水运或铁路铁路 选择交通工具：选择交通工具：从乌鲁木齐到北京去开会，从乌鲁木齐到北京去开会，第二天必须赶到。第二天必须赶到。飞机飞机选择交通工具：选择交通工具：暑假从上海到大连旅游，暑假从上海到大连旅游，选择最经济的办法。选择最经济的办法。海轮海轮选择交通工具：选择交通工具：从重庆到武汉，沿
10、途从重庆到武汉，沿途观赏三峡风光。观赏三峡风光。江轮江轮选择交通工具：选择交通工具：从拉萨到西宁，沿途从拉萨到西宁，沿途参观访问。参观访问。汽车汽车选择交通工具：选择交通工具：从武汉到郑州探亲。从武汉到郑州探亲。火车火车选择运输方式选择运输方式 贵重或急需的货物，贵重或急需的货物，数量又不大的，多由数量又不大的，多由 运输。运输。航空航空选择运输方式选择运输方式 容易死亡、变质的，容易死亡、变质的，活物、鲜货，短程可由活物、鲜货，短程可由 运输。运输。公路公路选择运输方式选择运输方式 容易死亡、变质的，容易死亡、变质的，活物、鲜货，远程而又数活物、鲜货，远程而又数量大的可用量大的可用 运输。运
11、输。铁路铁路选择运输方式选择运输方式 大宗笨重的货物，大宗笨重的货物，远距离运输，尽可能利远距离运输，尽可能利用用 或或 运输。运输。水运水运铁路铁路选择运输方式选择运输方式 货物和数量货物和数量 起点至终点起点至终点 铁路公路铁路公路 河运海运河运海运 航空航空两箱急救药品两箱急救药品 北京北京-拉萨拉萨一吨活鱼一吨活鱼 密云水库密云水库-北京北京五十吨钢材五十吨钢材 上海上海-济南济南一万吨海盐一万吨海盐 天津天津-上海上海十万吨大米十万吨大米 武汉武汉-上海上海 例例2.读欧洲货物四种运输方式运费与运距相关曲线示意图，读欧洲货物四种运输方式运费与运距相关曲线示意图，回答问题。回答问题。运
12、距运距80千米时，最廉价的运输方式是千米时，最廉价的运输方式是_。80千米千米运距运距550千米时，最廉价的运输方式是千米时，最廉价的运输方式是_。最昂贵的运输方式是最昂贵的运输方式是_，它适合运送的货物特点是它适合运送的货物特点是_。总运价总运价080550距离距离/千米千米空运空运公路公路铁路铁路水路水路公路公路铁路铁路水运水运空运空运轻型、贵重、急需。轻型、贵重、急需。某公司有以下运输业务委托你公司进行某公司有以下运输业务委托你公司进行托运，请为其选择合适的运输方式并说明理由。托运，请为其选择合适的运输方式并说明理由。1.1.把两箱急救药和一批鲜花从广州运到北京。把两箱急救药和一批鲜花从
13、广州运到北京。2.2.把一批煤炭从山西运到秦皇岛。把一批煤炭从山西运到秦皇岛。3.3.把一批新鲜蔬菜从郊区运到市区。把一批新鲜蔬菜从郊区运到市区。4.4.有一批钢材，要从重庆运到武汉。有一批钢材，要从重庆运到武汉。5.5.有有1515万吨石油需要从非洲运到我国的上海。万吨石油需要从非洲运到我国的上海。6.6.把我国西部大量的天然气运到以上海为主的东把我国西部大量的天然气运到以上海为主的东部地区。部地区。一批鲜花、一批鲜花、两箱急救药两箱急救药 广州广州北京北京 航空、铁路航空、铁路 航航 空空（速度快、保鲜）（速度快、保鲜）一批煤炭一批煤炭山西山西秦皇岛秦皇岛 铁铁 路路 铁铁 路路（路远、运
14、量大）（路远、运量大）新鲜蔬菜新鲜蔬菜 郊区郊区市区市区 铁路、公路铁路、公路 公公 路路（方便、灵活）（方便、灵活）钢钢 材材重庆重庆武汉武汉水路、铁路、公路水路、铁路、公路 水水 路路（运量大，有河流（运量大，有河流，成本低），成本低）1515万吨石油万吨石油非洲非洲上海上海水运水运+管道管道+公路公路水运水运+公路公路 水运水运+公路公路（实现门到门）（实现门到门）天然气天然气 西部西部东部东部管管 道道 管道（特殊性）管道（特殊性）A公司首次承揽到三个集装箱运输业务，时公司首次承揽到三个集装箱运输业务，时间较紧，从上海到大连铁路间较紧，从上海到大连铁路1200公里，公路公里，公路150
15、0公里，水路公里，水路1000公里。该公司自有公里。该公司自有10辆辆10吨普通卡车和一个自动化立体仓库，经联吨普通卡车和一个自动化立体仓库，经联系附近一家联运公司虽无集装箱卡车，但却系附近一家联运公司虽无集装箱卡车，但却有专业人才和货代经验，只是要价比较高。有专业人才和货代经验，只是要价比较高。至于零星集装箱安排、落实车皮和船舱，至于零星集装箱安排、落实车皮和船舱，A公司实在心中无底，你认为采取什么措施比公司实在心中无底，你认为采取什么措施比较稳妥？较稳妥？（1）自己购买若干辆集装箱卡车，然后组织）自己购买若干辆集装箱卡车，然后组织运输。运输。（2）想法请铁路部门安排运输）想法请铁路部门安排
16、运输（3）水路最短，请航运公司来解决运输）水路最短，请航运公司来解决运输（4）联运公司虽无集卡，但可叫其租车完成）联运公司虽无集卡，但可叫其租车完成此项运输此项运输（5）没有合适的运输工具，辞掉该项业务）没有合适的运输工具，辞掉该项业务分析要点：分析要点：1）以请联运公司来承担此项任务为好，比较）以请联运公司来承担此项任务为好，比较稳妥，联运公司是第三方物流服务企业稳妥，联运公司是第三方物流服务企业2）第三方物流服务供应商，根据是够拥有资）第三方物流服务供应商，根据是够拥有资产可分为产可分为资产基础供应商资产基础供应商和和非资产基础供应非资产基础供应商商。我们选择的。我们选择的标准绝不是它有无
17、实际的物标准绝不是它有无实际的物流资产而是看专业人才和货代经验流资产而是看专业人才和货代经验，有资产，有资产的物流供应商价格可能低些，但灵活性差；的物流供应商价格可能低些，但灵活性差；而非资产基础供应商，则可根据不同需要而非资产基础供应商，则可根据不同需要“量体裁衣量体裁衣”，非常灵活，非常灵活3）邀请第三方物流服务供应商，应该做好如下工作）邀请第三方物流服务供应商，应该做好如下工作（1）对该联运公司做必要调查，看看信誉度如何。）对该联运公司做必要调查，看看信誉度如何。（2）进行必要的合同磋商，解决好合同的执行标准、）进行必要的合同磋商，解决好合同的执行标准、衡量标准、违约责任以及价格衡量标准
18、、违约责任以及价格（3）努力避免双方合作失败，既交货又派专人关心）努力避免双方合作失败，既交货又派专人关心此事此事（4）讲明如果服务质量好，可考虑长期合作的可能性。）讲明如果服务质量好，可考虑长期合作的可能性。其他方案欠稳妥，无把握，风险很大其他方案欠稳妥，无把握，风险很大案例启示：案例启示：企业生存与发展的不二法门就是盈利，但企业生存与发展的不二法门就是盈利，但是对于企业即将开展的新业务或相关业务是对于企业即将开展的新业务或相关业务来说，盈利的同时，经验和长期客户的开来说，盈利的同时，经验和长期客户的开发维护也是很重要的发维护也是很重要的 6、几种特殊的运输方式几种特殊的运输方式 1、集装箱
19、运输、集装箱运输1）概念）概念 集装箱是一个集装箱是一个大型的、标准化的、能反复大型的、标准化的、能反复使用使用的载货容器。的载货容器。集装箱运输就是以集装箱作为一个货物集集装箱运输就是以集装箱作为一个货物集合单元进行运输的一种运输方式。合单元进行运输的一种运输方式。标准集装箱标准集装箱侧开门集装箱侧开门集装箱侧开双门集装箱侧开双门集装箱全侧开门集装箱全侧开门集装箱开顶散货集装箱开顶散货集装箱冷藏集装箱冷藏集装箱 提高装卸效率，减轻劳动强度提高装卸效率，减轻劳动强度 减少了装卸所需要的时间和费用，加速了车船周转减少了装卸所需要的时间和费用，加速了车船周转 保证货物完整无损，避免货损货差保证货物
20、完整无损，避免货损货差 节省包装费用，简化理货手续节省包装费用，简化理货手续 减少营运费用，降低运输成本减少营运费用，降低运输成本 3 3）集装箱运输的缺陷）集装箱运输的缺陷 集装箱运输需要大量的初始投资集装箱运输需要大量的初始投资 建立新的管理体制、形成新的管理人员队伍建立新的管理体制、形成新的管理人员队伍 增加了一些潜在的不安全因素增加了一些潜在的不安全因素 英国搁浅货轮纳波利号散落货物 4）开展集装箱运输的条件）开展集装箱运输的条件 要有稳定的货源和经济腹地要有稳定的货源和经济腹地 要有良好的港口条件（深水港）和基础设施（如装卸）要有良好的港口条件（深水港）和基础设施（如装卸）较为发达的
21、内陆运输系统较为发达的内陆运输系统 高素质的经营管理者高素质的经营管理者 2、托盘运输托盘运输 1）概念：概念：托盘（托盘（pallet）是用于集装、堆放、搬运和运输的放置是用于集装、堆放、搬运和运输的放置作为单元负荷的货物和制品的水平平台装置。作为单元负荷的货物和制品的水平平台装置。托盘运输是货物按照托盘运输是货物按照一定要求成组一定要求成组装在一个标准托盘装在一个标准托盘上组合成为上组合成为一个运输单位一个运输单位并便于并便于利用铲车或托盘利用铲车或托盘升降进行装升降进行装卸、搬运和堆存的一种运输方式，它是卸、搬运和堆存的一种运输方式，它是成组运输的初级形态成组运输的初级形态。2）托盘运输
22、的特点）托盘运输的特点（1）提高运输效率提高运输效率 搬运或出入库场都可用机械操作，减少货物堆码作业，从而有利于提高运输效率，缩短货运时间，减少劳动强度。（2）便于理货，减少货损货差便于理货，减少货损货差 以托盘为运输单位，货物件数变少体积重量变大，而且每个托盘所装数量相等。既便于点数、理货交接，又可以减少货损货差事故。（3）投资比较小，收效比较快。）投资比较小，收效比较快。（4）托盘的回收利用，组织工作难度较大，会）托盘的回收利用，组织工作难度较大，会浪费一部分运力。浪费一部分运力。3）托盘运输具有一定的局限性，表现在以下几）托盘运输具有一定的局限性，表现在以下几方面：方面：1、托盘承运的货
23、物范围有限、托盘承运的货物范围有限 最适合托盘运输的货物是箱装罐头食品、硬纸盒装的消费品和袋及袋装的货物等比较小的包装商品。大的、形状不一的家具、机械以及散装冷冻等货物，不适合于采用托盘进行运输 2、托盘运输设备费用减少，但要增加托盘运、托盘运输设备费用减少，但要增加托盘运输费用。同时，由于增加了托盘的重量和体积输费用。同时，由于增加了托盘的重量和体积，相应地减少了运输工具的载量。，相应地减少了运输工具的载量。3、托盘运输向成组运输前进了一步，但它的、托盘运输向成组运输前进了一步，但它的效果还不足以改变传统的流通方式，特别是不效果还不足以改变传统的流通方式，特别是不能满足国际多式联运的要求。能
24、满足国际多式联运的要求。例如，它不能像集装箱那样，可以密封越过国境或快速转换各种运输方式。4）采用托盘运输应该注意的事项）采用托盘运输应该注意的事项 1、装载托盘货物的范围有一定限制，不是所有货、装载托盘货物的范围有一定限制，不是所有货物都可以用托盘运输。物都可以用托盘运输。2、必须符合托盘积载的规定。、必须符合托盘积载的规定。3、每一托盘货载，必须捆扎牢固具有足够的强度、每一托盘货载，必须捆扎牢固具有足够的强度和稳定，平衡。和稳定，平衡。既能够承受一般海上风险，经受装卸操作和移动，也能够在其上面承受一定的压力。4、货物以托盘运输时，必须在所有运输单证上注、货物以托盘运输时，必须在所有运输单证
25、上注明明“托盘运输托盘运输”字样字样。3、散装运输散装运输 1）含义含义：散装运输是指产品不带包装的运输，是用专用散装运输是指产品不带包装的运输，是用专用设备将产品直接由生产厂方送至用户使用的运输方设备将产品直接由生产厂方送至用户使用的运输方式。式。2）优点）优点：）节省包装材料和费用，减少货损）节省包装材料和费用，减少货损 ）减少工作环节，提高机械化、自动化程度）减少工作环节，提高机械化、自动化程度 4、国际多式联运、国际多式联运 1 1）含义：）含义：国际多式联运是指按照国际多式联运是指按照多式联运合同多式联运合同,以以至少至少两种不同的运输方式两种不同的运输方式，由，由多式联运经营人多式
26、联运经营人将货物从将货物从一国境内一国境内接管货物的地点运至接管货物的地点运至另一国境内另一国境内指定交付指定交付货物的地点。货物的地点。2）特征：）特征：（1）必须订立多式联运合同）必须订立多式联运合同（1）多式联运合同：是指多式联运经营人凭其收取全程运费，使用两种或两种以上不同运输工具，负责组织完成货物全程运输的合同。（2）托运人只与MTO有业务和法律上的关系。（托运人与各区段实际承运人不发生任何业务和法律上的关系）（2）必须由多式联运经营人对全程运输负责）必须由多式联运经营人对全程运输负责（3）必须是两种或两种以上不同运输方式组成的连贯）必须是两种或两种以上不同运输方式组成的连贯运输。运
27、输。（5）必须签发多式联运单据）必须签发多式联运单据（1）MTO在接管货物后签发多式联运单据（2）从发货地到收货地，一单到底（3）发货人凭多式联运单据向银行结汇。（4）收货人凭多式联运单据向MTO或代理提货。（6）必须是单一的运费率）必须是单一的运费率3）优点：）优点：（）手续简便，可以做到一次性托运，一（）手续简便，可以做到一次性托运，一次性付费，一次性投保，一单到底，统一次性付费，一次性投保，一单到底，统一理赔，全程负责理赔，全程负责（）安全可靠（）安全可靠（）统一理赔（）统一理赔（）可以实现门门运输（）可以实现门门运输（）具有单一运费率（）具有单一运费率案例 2004年年10月月4日，原
28、告日，原告A公司作为买方与温公司作为买方与温州市进出口公司州市进出口公司B签订一份售货确认书，购买一签订一份售货确认书，购买一批童装，数量批童装，数量500箱，总价为箱，总价为68180美元。美元。2005年年2月月11日，日，B公司以托运人身份将该批童装装公司以托运人身份将该批童装装于两个于两个20尺标箱内，交由多式联运经营人尺标箱内，交由多式联运经营人C承运承运。C公司签发了号码为公司签发了号码为RS95040的一式三份正的一式三份正本全程多式联运提单。本全程多式联运提单。A公司提货时箱子外观完好，打开箱子发现公司提货时箱子外观完好，打开箱子发现其中一个箱子是空的。另一个箱子货物被挤压而其
29、中一个箱子是空的。另一个箱子货物被挤压而无法按正常价值出售。无法按正常价值出售。问：多式联运人是否承担赔偿责任。问：多式联运人是否承担赔偿责任。解答：解答：集装箱货物的真实性问题。根据国际集装箱货物的真实性问题。根据国际航运惯例，在集装箱运输方式中，由托运航运惯例，在集装箱运输方式中，由托运人负责装箱的货物，从装箱托运后至交付人负责装箱的货物，从装箱托运后至交付收货人时的期间内，如集装箱箱体和封志收货人时的期间内，如集装箱箱体和封志完好，货物损坏或短缺，由托运人负责；完好，货物损坏或短缺，由托运人负责；如箱体损坏或封志破坏，箱内货物损坏或如箱体损坏或封志破坏，箱内货物损坏或短缺，由承运人负责。
30、短缺，由承运人负责。2.2 运输问题与线性规划运输问题与线性规划1、线性规划模型及求解方法 1）线性规划问题的数学表达式）线性规划问题的数学表达式 线性规划问题一般可以表示如下：线性规划问题一般可以表示如下：称为线性规划问题的称为线性规划问题的标准形式标准形式（其中右端常数（其中右端常数b1，b2，bm0）。）。),1(0),1(.)(min11njxmibxatsxcxfjnjijijnjjj变换一般变换一般LPLP为标准形式的方法：为标准形式的方法：（1 1）如果原问题目标函数求极大值）如果原问题目标函数求极大值：令令z1=z，转化为求极小值。，转化为求极小值。（2）若某个右端常数若某个右
31、端常数bi0 则以则以1乘该约束两端。乘该约束两端。（3）若某约束为若某约束为“”型的不等式约束型的不等式约束，则在左端加上一个非负变量，称为松弛变量，使不则在左端加上一个非负变量，称为松弛变量，使不等式化为等式；等式化为等式；若某约束为若某约束为“”型型，则在左端减去一个非负变量，称为剩余变量，或者仍则在左端减去一个非负变量，称为剩余变量，或者仍然称为松弛变量，使不等式转化为等式。（目标函数不变然称为松弛变量，使不等式转化为等式。（目标函数不变（4）若某个若某个xj的符号约束为的符号约束为xj0；那么令那么令xj=xj，则，则xj0；若某个若某个xj无符号限制无符号限制，令令xj=xjxj，
32、其中，其中xj0，xj0。（目标函数变）。（目标函数变）2）单纯形法）单纯形法 单纯形表单纯形表jcnmmcccc11BcBXbmcc 1mxx 1mbb 1nmmxxxx 11mnmmnmaaaa1,11,110010 0jijijcacj E单位阵单位阵 N非基阵非基阵基变量基变量XB非基变量非基变量XN检验数检验数基可行解基可行解 单纯形法单纯形法 单纯形法的求解过程就是对单纯形表的变换过程，其步单纯形法的求解过程就是对单纯形表的变换过程，其步骤为：骤为：（1）求初始基可行解，列出初始单纯形表）求初始基可行解，列出初始单纯形表（2）最优性检验：）最优性检验：若所有检验数若所有检验数 ，则
33、表中基可行解即为最优解，计算，则表中基可行解即为最优解，计算结束；结束；若存在若存在 ，则选最大者，则选最大者 所对应的变量所对应的变量 为入基变量，为入基变量，转步骤（转步骤（3）（3）检查单纯形表的第）检查单纯形表的第K列。列。若无正值，则为无界解；若无正值，则为无界解；若有一个以上的正值，按最小比值法若有一个以上的正值，按最小比值法 确定出基变量确定出基变量（4）用对角顶点法对单纯形表进行变换）用对角顶点法对单纯形表进行变换（5）返回步骤（）返回步骤（2）进行迭代）进行迭代 0j0jkkxlklikikiabaab0minlx 对角顶点法：对角顶点法：如下图所示，矩形的四个顶点分别对应四
34、个元素：如下图所示，矩形的四个顶点分别对应四个元素：D1、D2、D3、D4，若，若D1为需要变换的元素，它的对角元素是交叉为需要变换的元素，它的对角元素是交叉元素元素D3，另两个对角元素为，另两个对角元素为D2和和D4。对角顶点法就是：第对角顶点法就是：第i行第行第j列的元素新值列的元素新值D1为旧值为旧值D1减去两个对角元素减去两个对角元素D2、D4乘积除以交叉元素乘积除以交叉元素D3所得的值所得的值 即：即：D1=D1-D2*D4/D3D4D1D3主列主列j列列i行行主行主行D2 若对第对第i行第行第j列的元素列的元素7进行变换，则变进行变换，则变换过程为：换过程为：变换后第变换后第i行第
35、行第j列的元素为：列的元素为：7-3*2/8=25/43278主列主列j列列i行行主行主行 变换单纯形表：变换单纯形表：首先，将首先，将 行的元素除以交叉元素，行的元素除以交叉元素，即即 变换后的交叉元素变换后的交叉元素 然后，其他行的元素（除然后，其他行的元素（除k列）按对角顶点法变列）按对角顶点法变换换 最后，把最后，把k列（不含交叉）元素变为列（不含交叉）元素变为0，即，即 单纯形变换结束单纯形变换结束 l1,3,2,1mnjaaalkljlj1lkaliaik,0 例：求解下列线性规划问题例：求解下列线性规划问题3,2,1,093124.3)(min3232132131jxxxxxxx
36、xxtsxxxfj7,2,1,093124.003)(min732653214321765431jxxxxxxxxxxxxxt sMxMxxxxxxfj解：加入变量解：加入变量 ，则问题变换为如下形式，则问题变换为如下形式7654,xxxx5,2,1,093124.003)(min32532143215431jxxxxxxxxxxxt sxxxxxfj 3 0 -1 0 0 M M 0 4 1 1 1 1 0 0 0 M 1 -2 1 -1 0 -1 1 0 M 9 0 3 1 0 0 0 1 10M -2M 4M 1 0 -M 0 0 -3 正检验数中最大者对正检验数中最大者对应的列为主列应
37、的列为主列主元素化为主元素化为1,向量向量换入换入,换出换出 jcBCBXb764xxx1x2x3x4x5x6x7x 4 1 32x6xminmax表表1：列初始单纯形表：列初始单纯形表 （单位矩阵对应的变量为基变量）（单位矩阵对应的变量为基变量）最小的值对应最小的值对应的行为主行的行为主行 3 0 -1 0 0 M M 0 4 1 1 1 1 0 0 0 M 1 -2 1 -1 0 -1 1 0 M 9 0 3 1 0 0 0 1 10M -2M 4M 1 0 -M 0 0 -3 jcBCBXb764xxx1x2x3x4x5x6x7xminmax变换为：4-1*1=33 1 -2 1 -1
38、0 -1 1 06变换为：9-1*3=6变换为：1-1*(-2)=33变换为：1-1*(-1)=22变换为：1-1*0=11变换为：0-1*(-1)=11变换为：0-1*1=-1-1变换为：0-1*0=00变换为：0-(-2)*3=66变换为：1-(-1)*3=44变换为：0-0*3=00变换为：0-(-1)*3=33变换为：0-1*3=-3-3变换为：1-0*3=116M 6M 4M 4M 0 3M -4M 0 -3 +1000 3 0 -1 0 0 M M 0 3 3 0 2 1 1 -1 0 0 1 -2 1 -1 0 -1 1 0 M 6 6 0 4 0 3 -3 1 6M 6M 0
39、1+4M 0 3M -4M 0 -3 正检验数中最大者对正检验数中最大者对应的列为主列应的列为主列主元素化为1,向量换入,换出 jcBCBXb724xxx1x2x3x4x5x6x7x 1-11x7xminmax表表2：换基：换基（对角顶点法，主列化为单位向量，主元为（对角顶点法，主列化为单位向量，主元为1）最小的值对应最小的值对应的行为主行的行为主行 3 0 -1 0 0 M M 0 0 0 0 0 1 -1/2 -1/2-1/2 0 3 0 1 1/3 0 0 0 1/3 3 1 1 0 2/3 0 1/2 -1/2 1/6 3 0 0 3 0 3/2 -M -M -3/2 +1/2 正检验
40、数中最大者对正检验数中最大者对应的列为主列应的列为主列主元素化为1,向量换入,换出 jcBCBXb124xxx1x2x3x4x5x6x7x -9 3/23x1xminmax表表3：换基：换基（对角顶点法对角顶点法，主列化为单位向量，主元为主列化为单位向量，主元为1 1）最小的值对应最小的值对应的行为主行的行为主行 3 0 -1 0 0 M M 0 0 0 0 0 1 -1/2 1/2 -1/2 0 5/2 -1/2 1 0 0 -1/4 1/4 1/4-1 3/2 3/2 0 1 0 3/4 -3/4 1/4 -3/2 -9/2 0 0 0 -3/4 -M -M +3/4 -1/4 jcBCB
41、Xb324xxx1x2x3x4x5x6x7xmaxmax表表4：换基：换基（对角顶点法，主列化为单位向量，主元为对角顶点法，主列化为单位向量，主元为1 1）最优解为X=(0,5/2,3/2)目标函数值Z=-3/2 2、运输问题的最优解、运输问题的最优解 运输问题的求解方法有多种，例如线性规划方法、表上运输问题的求解方法有多种，例如线性规划方法、表上作业法、图上作业法等。作业法、图上作业法等。1）运输问题）运输问题 典型背景典型背景单一物资运输调度问题单一物资运输调度问题 设某种物品有设某种物品有:m个产地：个产地：产量：产量：n个销地：个销地：销量：销量：从产地从产地 到销地到销地 的单位运价
42、是的单位运价是 。求总运费最小的调度方案。求总运费最小的调度方案。nBBB,21mAAA,21maaa,21nbbb,21iAjBijc产量产量销量销量1A2AmA1B2BnB产地产地销地销地nb1b2b1a2ama11c21c1mc12c22c2mcnc1nc2mnc 运输问题的原始条件可以用运输问题的原始条件可以用“运输表运输表”表表示，运输表有一定的格式，图下图所示示，运输表有一定的格式，图下图所示 njmixnjbxmiaxxcxfijjmiijinjijminjijij,2,1,2,1,0,2,1,2,1,min1111）（运输问题的数学模型运输问题的数学模型由某一产地运往各个销地的
43、物由某一产地运往各个销地的物品数量之和等于该产地的产量品数量之和等于该产地的产量由各产地运往某一销地的物品由各产地运往某一销地的物品数量之和等于该销地的销量数量之和等于该销地的销量变量非负条件变量非负条件目标函数表示运输总费目标函数表示运输总费用，求极小化用，求极小化jiba如果如果 ，即供应量等于总需求量，称该运，即供应量等于总需求量，称该运输问题为产销平衡问题。数学模型为：输问题为产销平衡问题。数学模型为：njmixnjbxmiaxxcxfijjmiijinjijminjijij,2,1,2,1,0,2,1,2,1,min1111）（反之称为反之称为产销不平衡问题产销不平衡问题：如果如果
44、，即供应量大于总需求量，可增加一，即供应量大于总需求量，可增加一个虚构销售地，令其需求量为个虚构销售地，令其需求量为 ，数学，数学模型为：模型为：jibajinbab1 njmixnjbxmiaxxcxfijjmiijinjijminjijij,2,1,2,1,0,2,1,2,1,min1111）（11,2,1,2,1,0,2,1,2,1,min111111 njmixnjbxmiaxxcxfijjmiijinjijminjijij）（如果如果 ，即供应量小于总需求量，可增加一，即供应量小于总需求量，可增加一个虚构生产地，令其需求量为个虚构生产地，令其需求量为 ，数学模，数学模型为：型为：ji
45、baijmaba1 njmixnjbxmiaxxcxfijjmiijinjijminjijij,2,1,2,1,0,2,1,2,1,min1111）（njmixnjbxmiaxxcxfijjmiijinjijminjijij,2,11,2,1,0,2,1,1,2,1,min111111）（2.3 旅行路线问题旅行路线问题1、旅行路线问题表述、旅行路线问题表述 一个有一个有N个城市组成的一般网络，已知任意两个城市组成的一般网络，已知任意两城市之间的直达距离，寻找一条旅行路线，使其最城市之间的直达距离，寻找一条旅行路线，使其最终回归到出发城市，而且每个城市刚好经过一次，终回归到出发城市，而且每个城
46、市刚好经过一次，问如何规划路线才能使总的旅行距离最短？问如何规划路线才能使总的旅行距离最短？2、问题求解、问题求解 1）穷举法）穷举法 列出所有可能存在的路线，计算所有路线的距离，进列出所有可能存在的路线，计算所有路线的距离，进行比较，找出最短的那条路线就是最佳路线，这种方法称为行比较，找出最短的那条路线就是最佳路线，这种方法称为“穷举法穷举法”原理：原理：旅行路线问题是从一结点出发，经过旅行路线问题是从一结点出发，经过N-1个结点后再回个结点后再回到出发点。到出发点。N-1个结点有（个结点有（N-1）！种排列方法，因此，旅）！种排列方法，因此，旅行路线也有（行路线也有（N-1）！种。只要找出
47、）！种。只要找出N-1个结点的所有排列，个结点的所有排列，计算所有路线的长度，就能找到最佳路线。计算所有路线的长度，就能找到最佳路线。例子：设从例子：设从A点出发，经过所有的城市，最终回到点出发，经过所有的城市，最终回到A点，求最点，求最佳路线。已知各点间的距离佳路线。已知各点间的距离 d(A,B)=3，d(A,C)=5，d(A,D)=1，d(A,E)=4，d(B,E)=2，d(B,D)=6,，d(B,C)=1，d(C,E)=4，d(C,D)=5，d(D,E)=6。ABCDE 此处，此处，N=5，则（，则（N-1）！）！=4！=24 则所有的排列方式为：则所有的排列方式为：BCDE BCED
48、BDCE BDEC BECD BEDC CBDE CBED CDBE CDEB CEBD CEDB DBCE DBEC DCBE DCEB DEBC DECB EBCD EBDC ECBD ECDB EDBC EDCB可以计算每一条线路的距离，找其中最小的即可以计算每一条线路的距离，找其中最小的即BCDE=19 BCED=15 BDCE=22 BDEC=24 BECD=15BEDC=21 CBDE=22 CBED=15 CDBE=22 CDEB=21 CEBD=18 CEDB=24 DBCE=16 DBEC=18 DCBE=13DCEB=15 DEBC=15 DECB=15 EBCD=13 E
49、BDC=22ECBD=16 ECDB=22 EDBC=22 EDCB=19从上述数据可知，路线从上述数据可知，路线ADCBEA和和AEBCDA是最佳路线是最佳路线 2.4 图论方法的应用图论方法的应用 1、图论的基本知识、图论的基本知识 图论图论是数学的一个分支是数学的一个分支,以图为研究对象。以图为研究对象。这种图由若干给定的这种图由若干给定的点点和连接两点的和连接两点的线线构成构成,借以描述某些事物之间的关系借以描述某些事物之间的关系。用点代表事物。用点代表事物,用用连接两点的线表示两个事物之间具有特定关系。连接两点的线表示两个事物之间具有特定关系。（1 1）图论的起源）图论的起源 图论起
50、源于图论起源于1818世纪世纪,追朔到追朔到17361736年瑞士数学家年瑞士数学家欧拉出版第一本图论著作欧拉出版第一本图论著作,提出和解决著名提出和解决著名哥尼斯哥尼斯堡七桥堡七桥问题问题。图论不仅在许多领域图论不仅在许多领域,如计算机科学如计算机科学,运筹学运筹学,心理学等方面得到了广泛的应用心理学等方面得到了广泛的应用,而且学科本身也而且学科本身也获得长足发展获得长足发展,形成了拟阵理论形成了拟阵理论,超图理论超图理论,代数图代数图论论,拓扑图论等新分支拓扑图论等新分支哥尼斯堡七桥哥尼斯堡七桥(Knigsberg Bridges)问题问题 在哥尼斯堡，有七座桥将普莱格尔河中的两个岛及岛与
