2000年国赛B题：钢管订购和运输

2000年国赛B题：钢管订购和运输是2000年全国大学生数学建模竞赛的B题。

订货、运输与铺设范围

计划铺设天然气主管道 $A_{1} \to A_{2} \to \dots \to A_{15}$ 。七家钢厂 $S_{1}, \dots, S_{7}$ 可以生产所需钢管。把可铺设 1 千米主管道的钢管记为 1 单位钢管。

一旦由某钢厂承担制造任务，该厂的订单至少为 500 单位，且不能超过指定期限内的产量上限。各厂数据如下：

钢厂	S1	S2	S3	S4	S5	S6	S7
产量上限（单位钢管）	800	800	1000	2000	2000	2000	3000
出厂单价（万元/单位钢管）	160	155	155	160	155	150	160

管道沿线已有公路或施工公路。钢管可经铁路、公路运输，必须供应管道全线各铺设位置，不是只把钢管运到十五个编号点就算完成。

一单位钢管的铁路运输费用按里程区间计价：

超过 1000 千米后，每增加 1—100 千米，运费增加 5 万元。公路运价为每单位钢管每千米 0.1 万元；不足一整千米的部分按一千米收费。

以下用连接表表达原图的网络，所有路段长度均为千米。A 表示管道点，S 表示钢厂；原图未命名的车站在此依次记为 R1—R17。它们只是便于辨认同一节点的标记，不是新的设施。铁路与公路分别列出，表中没有连接的两点不另设直接路段。

除接驳道路外，主管道沿线本身也可进行公路运输。S7 与 R17 之间的 30 千米线段、S7 至 A15 的 20 千米线段属于原图细线道路；不应把钢厂所在位置一律当作铁路相连。

第三问保留上面的交通网络及 A1—A15 管道，并增加下列管道支线。新增点与原网络节点的对应关系为：A16=R9，A17=R12，A18=R13，A19=R14，A20=R15，A21=S6。原图将 S6 旁的 A21 放在括号中标出。

其中原来的 R9—A9 与 R12—A11 接驳位置也成为需铺设钢管的管道段；不能在管道需求中遗漏这两段。