现要求将20吨货物从城市1运输到城市5,运输路径固定为从城市1先后经过城市2、城市3、城市4到城市5。运输期间可以自由选择三种不同的运输方式:铁路、公路、航空运输。但是为了便于运输,在运输路径中相邻的两个地点之间只能采取一种运输方式。另外,规定若交接前后交通工具为不同类型,将会因更换运输方式产生额外支出。应选择怎样的运输方案使总支出最少? 下表一给出了每一对城市之间运输一吨货物的成本。第二张表列出了在更换运输每吨货物需要的额外支出。 表1:不同路径上选择不同运输方式的单位成本 城市1-2 城市2-3 城市3-4 城市4-5 铁路 30 25 40 60 公路 25 40 45 50 航空 40 20 50 45 表2:更换运输工具的单位费用 转换为铁路 转换为公路 转换为航空 从铁路 0 5 12 从公路 8 0 10 从航空 15 10 0