方案1、运输方式的选择现要求将20吨货物从城市1运输到城市5,运输路径固定为从城市1先后 经过城市2、城市3、城市4到城市5运输期间可以自由选择三种不同的运输 方式：铁路、公路、航空运输但是为了便于运输，在运输路径中相邻的两个地 点之间只能采取一种运输方式另外，规定若交接前后交通工具为不同类型，将 会因更换运输方式产生额外支出应选择怎样的运输方案才能使总支出最少？下表一给出了每一对城市之间运输一吨货物的成本第二张表列出了在更 换运输方式时每吨货物需要的额外支出不同路径上选择不同运输方式的单位成本城市1-2城市2-3城市3-4城市4-5铁路30254060公路25404550航空40205045更换运输工具的单位费用转换为铁路转换为公路转换为航空从铁路0512从公路8010从航空15100分析：本案例可以套用经典的最短路分段设计问题—共 4 段路径：1-2、2-3、3-4、4-5 o将城市1看做顶点1注意到有三种运输方式从城市1到2,因此将城市2化为3个顶点：T2、 G2、H2 （T2表示通过铁路到城市2； G2表示通过公路到城市2； H2表示通过航 空方式到城市2） o类似地，城市i都可化作3个顶点：Ti、Gi、Hi, i二2, 3, 4, 5 （分别表 示通过铁路、公路、航空方式到城市i）。
根据路径，连有向线段连线上的权为运输一吨货物的总成本比如从T2到T3表示从城市2运输到城市3,保持铁路运输方式不变，运 费为25,故权为25又如从G4到H5表示，从城市4经航空运输到城市5,运费为45,由于运 输方式由公路转为航空，更换运输工具的费用为10,即总费用55,故权为55为了求从城市1到城市5运输的最少支出，即求图论模型中从起点（代表 城市1）到终点（代表城市5）的最短路，由于代表城市5的顶点共3个：T5、 G5、H5 （分别表示通过铁路、公路、航空方式到城市5）不妨再取一个虚拟顶 点5代表终点（城市5）,其中，从顶点T5 （G5、H5）到顶点5的权为0 （没有 任何费用支出）From \ To1 |T262 |H2T3G3H3□G4H4T5G5H5513025 40T225453262334030H2405020T340506263484560H355555014605557G4685055H4756545T50G50H5 0 5 04-23-2009StageFrom Input StateTo Output StateDistanceCumulative DistanceDistance to 511T230301502T2T325551203T3T44095954T4G555150555G5501500From 1To 5Min. Distance=150CPU =0求解结果:结论:从城市1运输1吨货物到城市5的最省费用为150,因此运输20吨的费用 为 3000o运输方案为：从城市1通过铁路运输先后经过城市2、城市3、城市4、再 转为公路运输到达目的地城市5。