要铺设一条\(A_1→A_2→…→A_{15}\)的输送天然气的主管道，如图所示。经筛选后可以生产这种主管道钢管的钢厂有\(S_1 ,S_2,…,S_7\)。图中粗线表示铁路,单细线表示公路,双细线表示要铺设的管道(假设沿管道或者原有公路,或者建有施工公路),圆圈表示火车站,每段铁路、公路和管道旁的阿拉伯数字表示里程(单位:km)。为方便计算, 1km主管道钢管称为1单位钢管。

一、问题描述

一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂\(S_i\) 在指定期限内能生产该钢管的最大数量为\(s_i\)个单位，钢管出厂销价1单位钢管为\(p_i\) 万元，如下表：

单位钢管的铁路运价如下表：

1000km以上每增加1至100km运价增加5万元。公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点\(A_1,A_2,...,A_{15}\) ，而是管道全线）。请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。

二、数学模型

2.1 模型假设

假设沿管道或者原来有公路，或者建有施工公路；
运费只按铁路、公路里程收取，即不考虑火车、汽车由于停靠站等其他一切外因带来的费用；
钢管在铺设过程中以1km为单位进行铺设；
钢管可由铁路、公路运往铺设路线任一地点；
所有钢管在指定期限内都能按时生产并运送指定地点；
钢管铺设过程中由站点向左右两边进行铺设。

2.2 符号说明

2.3 数学模型

三、计算过程

使用计算机求解上述数学规划时, 需要对非线性约束条件进行处理。引进0-1变量

把约束条件第一式转化为线性约束

3.1 运费矩阵的计算

下面介绍购买单位钢管及从\(S_i(i=1 ,2,…,7)\)运送到\(A_j(j = 1 ,2,…,15)\)的最小购运费用的计算过程。
计算铁路任意两点间的最小运输费用
  由于铁路运费不是连续的,故不能直接构造铁路费用赋权图,用Floyd算法来计算任意两点间的最小运输费用。但可以首先构造铁路距离赋权图,用Floyd算法来计算任意两点间的最短铁路距离值,再依据题中的铁路运价表,求出任意两点间的最小铁路运输费用。这就可以巧妙地避开铁路运费不是连续的问题。
首先构造铁路距离赋权图\(G=(V,E_1,W_1)\),其中\(V = \{S_1,…,S_7,A_1, ,…,A_{15} ,B_1,，…,B_{17}\}\)，
各顶点的编号如上图所示，

，有

\(d_{ij}^{(1)}\) 表示两点\(i,j\)之间的铁路距离，然后应用Floyd算法求得任意两点间的最短铁路距离。
根据铁路运价表，可以得到铁路费用赋权完全图\(G1= (V,E_1,W_1)\)，其中\([c_{ij}^{(1)}]_{39 \times 39}\)，这里\(c_{ij}\)为第\(i,j\)顶点间的最小铁路运输费用，若两点间的铁路距离值为无穷大，则对应的铁路运输费用也为无穷大。

构造公路费用的赋权图
构造公路费用赋权图\(G2=( V,E_2, W_2)\)，其中\(V\)同上，\(d_{ij}^{(2)}\)为\(i,j\)之间的公路距离。

，有

计算任意两点间的最小运输费用
由于可以用铁路、公路交叉运送,所以任意相邻两点间的最小运输费用为铁路、公路两者最小运输费用的最小值。构造铁路公路的混合赋权图\(G=(V,E,W)，W=[c_{ij}^{(3)}]_{39 \times 39}\)，其中\(c_{ij}^{(3)}=\min(c_{ij}^{(1)},c_{ij}^{(2)})\)，对图\(G\)应用Floyd算法，就可以计算出所有顶点对之间的最小运输费用，最后提取需要的\(S_i(i=1 ,2,…,7)\)到\(A_j(j=1,2,…,15)\)的最小运送费用C,(单位:万元)，如下表所列。

单位钢管从钢厂\(S_i\)运输到\(A_j\)的运输费用

3.2 总费用的计算

**单位钢管从钢厂\(S_i\)运输到\(A_j\)的运输量 **

即厂家\(S_1\)往\(A_4\)节点运输335单位钢管，往\(A_6\)节点运输200单位钢管，往\(A_7\)节点运输265单位钢管，共计800单位。其它钢厂以此类推…………最小费用为127.8632亿元。

3.3 Python计算代码

#铁路赋权图

#公路赋权图

#最小费用

#运输量的计算
s=[800 800 1000 2000 2000 2000 3000];
path=zeros(39,39);
path1=zeros(39,39);
path2=zeros(39,39);
cf=zeros(7,15);
w=zeros(39,39);c=zeros(39,39);c2=zeros(39,39);
w(1,29)=20;w(1,30)=202;w(2,30)=1200;w(3,31)=690;w(4,34)=690;w(5,33)=462;
w(6,38)=70;w(7,39)=30;w(23,25)=450;w(24,25)=80;w(25,27)=1150;
w(26,28)=306;w(27,30)=1100;w(28,29)=195;w(30,31)=720;w(31,32)=520;
w(32,34)=170;w(33,34)=88;w(34,36)=160;w(35,36)=70;w(36,37)=320;
w(37,38)=160;w(38,39)=290;
w=w+w';
for i=1:39
    for j=1:39
        if(i~=j)&& w(i,j)==0
            w(i,j)=200000000;
        end
    end
end
for k=1:39
    for i=1:39
        for j=1:39
            if w(i,j)>w(i,k)+w(k,j)
                w(i,j)=w(i,k)+w(k,j);
                path(i,j)=k;
            end
        end
    end
end
c1=w;
for i=1:39
    for j=1:39
        if c1(i,j)==0 
            c1(i,j)=0;
        end
        if c1(i,j)>0 && c1(i,j)<=300
            c1(i,j)=20;
        end
        if c1(i,j)>300 && c1(i,j)<=350
            c1(i,j)=23;
        end
        if c1(i,j)>350 && c1(i,j)<=400
            c1(i,j)=26;
        end
        if c1(i,j)>400 && c1(i,j)<=450
            c1(i,j)=29;
        end
        if c1(i,j)>450 && c1(i,j)<=500
            c1(i,j)=32;
        end
        if c1(i,j)>500 && c1(i,j)<=600
            c1(i,j)=37;
        end
        if c1(i,j)>600 && c1(i,j)<=700
            c1(i,j)=44;
        end
        if c1(i,j)>700 && c1(i,j)<=800
            c1(i,j)=50;
        end
        if c1(i,j)>800 && c1(i,j)<=900
            c1(i,j)=55;
        end
        if c1(i,j)>900 && c1(i,j)<=1000
            c1(i,j)=60;
        end
        if c1(i,j)>1000 && rem(c1(i,j),100)==0
            c1(i,j)=(floor((c1(i,j)-1000)/100))*5+60;
        end
        if c1(i,j)>1000 && rem(c1(i,j),100)~=0
            c1(i,j)=(floor((c1(i,j)-1000)/100))*5+65;
        end
    end
end
c2(1,14)=31;c2(6,21)=110;c2(7,22)=20;c2(8,9)=104;c2(9,10)=301;c2(9,23)=3;
c2(10,11)=750;c2(10,24)=2;c2(11,12)=606;c2(11,27)=600;c2(12,13)=194;
c2(12,26)=10;c2(13,14)=205;c2(13,28)=5;c2(14,15)=201;c2(14,29)=10;
c2(15,16)=680;c2(15,30)=12;c2(16,17)=480;c2(16,31)=42;c2(17,18)=300;
c2(17,32)=70;c2(18,19)=220;c2(18,33)=10;c2(19,20)=210;c2(19,35)=10;
c2(20,21)=420;c2(20,37)=62;c2(21,22)=500;c2(21,38)=30;c2(22,39)=20;
c2=c2+c2';
for i=1:39
    for j=1:39
        if(i~=j)&&c2(i,j)==0
            c2(i,j)=200000000;
        end
    end
end
for k=1:39
    for i=1:39
        for j=1:39
            if c2(i,j)>c2(i,k)+c2(k,j)
                c2(i,j)=c2(i,k)+c2(k,j);
                path1(i,j)=k;
            end
        end
    end
end
c3=c2;
c2=0.1*c2;
for i=1:39
    for j=1:39
        if c1(i,j)<c2(i,j)
            c(i,j)=c1(i,j);
        end
        if c1(i,j)>c2(i,j)
            c(i,j)=c2(i,j);
        end
        if c1(i,j)==c2(i,j)
            c(i,j)=c2(i,j);
        end
    end
end
for i=1:39
    for j=1:39
        for k=1:39
            if c(i,j)>c(i,k)+c(k,j)
                c(i,j)=c(i,k)+c(k,j);
                path2(i,j)=k;
            end
        end
    end
end
for i=1:39
    for j=1:39
        if (i<=7)&&(j>=8)&&(j<=22)
            cf(i,j-7)=c(i,j);
        end
    end
end
% xlswrite('F:\第三道问题：钢管运输问题\钢管运输问题1.xlsx',cf,'sheet1','b3:p9');
% xlswrite('F:\第三道问题：钢管运输问题\钢管运输问题1.xlsx',w,'sheet2','b4:AN42');
% xlswrite('F:\第三道问题：钢管运输问题\钢管运输问题1.xlsx',c1,'sheet2','b54:AN92');
% xlswrite('F:\第三道问题：钢管运输问题\钢管运输问题1.xlsx',c3,'sheet3','b4:AN42');
% xlswrite('F:\第三道问题：钢管运输问题\钢管运输问题1.xlsx',c2,'sheet3','b54:AN92');
% xlswrite('F:\第三道问题：钢管运输问题\钢管运输问题1.xlsx',c,'sheet4','b4:AN42');

使用计算机求解上述数学规划时，需要对约束条件（20）进行处理。我们引进0 −1 变量，求得总费用的最小值为 127.8632 亿。

参考文献

1. 钢管订购与运输优化模型
2. 钢管运输模型
3. 最短路+最小费用+线性规划（钢管订购和运输问题）