管道订购与运翰问题 541 VV之间原来就有公路就选择新旧公路中较短的一条.这样,我们就把铁路运输网络转 换成了公路运输网络 销价等价转换法则:按单位费用相等将任意钢厂的单位销价转换为公路单位运价 对于钢厂S;的销售单价p,我们可以虚设一条公路线,连接钢厂S;及另一虚拟钢厂 S,其长度为l1,并且满足l1=0.1×p2;从而将钢厂的销售单价转换成公路运输单价,而新 钢厂S的销售价为0 将铁路和销价转换为公路的过程可以由计算机编程实现 通过上述的分析我们可以将原问题化为一个相对简单的产量未定的运输问题,利用 A1到A15之间的管道距离和钢厂和站点之间的公路距离建立一个产量未定的运输问题的 模型但是由于A1,A2,…A1并不能代表所有的实际需求点(实际需求点是n个单位管 道),因此,我们可以用 Floyd算法进一步算出7个钢厂到所有实际的n个需求点(对于问题 n=5171;对于问题三,n=5903)的最短路径,并由此得出一个具有7个供应点、n个需 求点的产量未定的运输模型 5模型的建立 产量未定的运输模型 根据假设4,我们可以将每一单位的管道看成一个需求点,向一单位管道的所在地运输 钢管即为向一个点运输钢管,对每个点,我们可以根据该点的位置和最短等价公路距离,求 出各钢厂与该点之间最小单位运输费用C;(销价已经归入运输费用之中了),设总共有m 个供应点(钢厂),n个需求点,我们就可以得到一个产量未定的运输模型: 有m个供应点、n个需求点,每个供应点的供应量u1∈|0}U500,sl;每个需求点需 要1单位,运输单价矩阵为C,求使得总运输费用最小的运输方案, 其数学规划模型 F ∈0U1500,S t x=0或1 其中: CuC12… C 出…为单位费用矩阵 CmI C X= …为决策矩阵,也为0-1矩阵 6模型的求解 对于本题,上述01规划规模宏大,现有的一些算法不能胜任,我们必须具体问题具体