由于钢管从钢厂Si运到运输点Aj要通过铁路和公路运输，而铁路运输费用是分段函数，与全程运输总距离有关。又由于钢厂Si直接与铁路相连，所以可先求出钢厂Si到铁路与公路相交点bj的最短路径。 依据钢管的铁路运价表，算出钢厂Si到铁路与公路相交点bj的最小铁路运输费用，并把费用作为边权赋给从钢厂Si到bj的边。再将与bj相连的公路、运输点Ai及其与之相连的要铺设管道的线路（也是公路）添加到图上，根据单位钢管在公路上的运价规定，得出每一段公路的运费，并把此费用作为边权赋给相应的边。这样就转换为以单位钢管的运输费用为权的赋权图，再利用E.W.Dijkstra的最短路算法计算出一个单位钢管从钢厂运到工地的最少费用系数阵?cij?，MATLAB程序见附录一。
表3 表中对应的值为对应两点最优路径单位钢管运输费用
A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15
S1 170.7 160.3 140.2 98.6 38 20.5 3.1 21.2 64.2 92 96 106 121.2 128 142 S2 215.7 205.3 190.2 171.6 111 95.5 86 71.2 114.2 142 146 156 171.2 178 192 S3 230.7 220.3 200.2 181.6 121 105.5 96 86.2 48.2 82 86 96 111.2 118 132 S4 260.7 250.3 235.2 216.6 156 140.5 131 116.2 84.2 62 51 61 76.2 83 97 S5 255.7 245.3 225.2 206.6 146 130.5 121 111.2 79.2 57 33 51 71.2 73 87 S6 265.7 255.3 235.2 216.6 156 140.5 131 121.2 84.2 62 51 45 26.2 11 28 S7 275.7 265.3 245.2 226.6 166 150.5 141 131.2 99.2 76 66 56 38.2 26 2 (2)根据以上结果, 继续求解非线性规划模型：
715minZ? ?i?1?(pj?1i?cij)xij?0.05???1?yj?yj??1?zj?zj?
??j?115?7??xi j?yj?zj;(j?1,2,?,15)?i?1??zj?yj?1?Aj,j?1;(j?1,2,?,14)s.t? 1515?500?xij?si或?xij?0;(i?1,2,?,7)??j?2j?2???xij?0 i?1,?,7,j?2,?,151515ij15由于不能直接处理约束条件：500?到如下模型：
?xj?2?si或?xij?0，我们可先将此条件改为?xij?si，得
j?2j?2715minZ? ?i?1?(pj?1i?cij)xij?0.05???1?yj?yj??1?zj?zj?
??j?115?7??xi j?yj?zj;(j?1,2,?,15)?i?1??zj?yj?1?Aj,j?1;(j?1,2,?,14)s.t?15??xij?si;(i?1,2,?,7)?j?2???xij?0 i?1,?,7,j?2,?,15
用LINGO求解，程序见附录二。分析结果后发现购运方案中钢厂S7的生产量不足500单位，下面我们采用不让钢厂S7生产和要求钢厂S7的产量不小于500个单位两种方法计算： 1）不让钢厂S7生产,程序见附录三。
计算结果：Z1?1278632（万元）（此时每个钢厂的产量都满足条件）. 2）要求钢厂S7的产量不小于500个单位，程序见附录四。
计算结果：Z2?1285281（万元） （此时每个钢厂的产量都满足条件）. 比较这两种情况，得最优解为，minZ?min(Z1,Z2)?Z1=1278632（万元）。
所以根据上述的模型，得运输总费用最小为：1278632（万元）。
具体的购运计划和铺设方案如表4，表5：
表4 问题一的订购和调运方案
订购量 S1 S2 S3 S4 S5 S6 S7 800 800 1000 0 1015 1556 0 A2 0 179 0 0 0 0 0 A3 0 0 0 0 508 0 0 A4 40 0 336 0 92 0 0 A5 295 321 0 0 0 0 0 A6 200 0 0 0 0 0 0 A7 265 0 0 0 0 0 0 A8 0 300 0 0 0 0 0 A9 0 0 664 0 0 0 0 A10 0 0 0 0 0 351 0 A11 0 0 0 0 415 0 0 A12 0 0 0 0 0 86 0 A13 0 0 0 0 0 333 0 A14 0 0 0 0 0 621 0 A15 0 0 0 0 0 165 0
A1 A2 A3 A4 A5 A6 A7 A8 A9 A10
表5 问题一的铺设方案
y 0.000000 104.0000 226.0000 468.0000 606.0000 184.5000 189.5000 125.0000 505.0000 321.0000 0.000000 75.00000 282.0000 0.000000 9.500000 15.50000 76.00000 175.0000 159.0000 30.00000 z A11 A12 A13 A14 A15 270.0000 75.00000 199.0000 286.0000 165.0000 145.0000 11.00000 134.0000 335.0000 0.000000
问题二：针对问题一的求解模型，讨论钢厂钢管的销售价格变化对购运计划和总费用影响及钢厂钢管产量的上限变化对购运计划和总费用的影响．
定义 方案中运往各点Ai的运输量的变化量的绝对值之和称为运输方案变化量．
1、讨论钢厂钢管的销售价格变化对购运计划和总费用的影响
当钢厂钢管销售价格变化时，会对购运计划和总费用造成影响。为了更好地观察每一个钢厂钢管销售价格所造成的影响，采用比较法，即每次只让一个钢厂钢管的销售价格发生相同的变化，其余钢厂钢管的销售价格不发生变化。
我们将各个钢厂单位钢管的销价分别增加1万元和减少1万元，借助LINGO软件得出相应的总费用、运输方案、订购方案变化情况如表6、表7所示
钢厂 S1 S2 S3 S4 S5 S6 S7 表6 各个钢厂单位钢管的销价分别增加1万元 总费用 总费用变化量 运输方案变化量 0 1279432 800 订购方案变化量 0 0 0 0 30 712 0 1279432 1279632 1278632 1279639 1279834 1278632 800 1000 0 1007 1202 0 0 0 0 40 712 0 钢厂 S1 S2 S3 S4 S5 S6 S7
表7 各个钢厂单位钢管的销价分别减少1万元 总费用 总费用变化量 运输方案变化量 0 800 1277832 0 1277832 800 订购方案变化量 0 0 0 0 712 30 0 1277632 1278632 1277263 1277068 1278632 1000 0 1369 1564 0 0 0 712 40 0 由上述表格观察分析可得： S6钢厂销价变化对总费用影响最大，S5,S6钢厂钢管的销价的变化对购运计划影响最大。
2、讨论钢厂钢管产量的上限的变化对购运计划和总费用的影响
同样采用比较法，即每次只让一个钢厂钢管产量的上限的发生相同的变化，其余钢厂钢管产量的上限不发生变化。将各个钢厂的产量的上限分别增加100个单位和减少100个单位，分别计算，得到购运计划和总费用变化情况如表8、表9所示
表8 各个钢厂钢管的产量的上限分别增加100个单位
钢厂 S1 S2 S3 S4 S5 S6 S7 总费用 1268332 1275132 1276132 1278632 1278632 1278632 1278632 总费用变化量 10300 3500 2500 0 0 0 0 运输方案变化量 218 404 1786 0 0 844 0 订购方案变化量 200 200 200 0 0 0 0 钢厂 S1 S2 S3 S4 S5 S6 S7
表9 各个钢厂钢管的产量的上限分别减少100个单位 总费用 总费用变化量 运输方案变化量 260 1288932 10300 1244 1282132 3500 订购方案变化量 200 200 200 0 0 0 0 1281132 1278632 1278632 1278632 1278632 2500 0 0 0 0 200 0 0 0 0 由上述表格观察分析可得：S1钢厂钢管的产量的上限的变化对总费用影响最大，购运计划影响较小。
五、 结果分析
由于总费用由订购费用和运输费两部分组成，运输费又由一般线路上的运输费和铺设管道上的运输费组成。利用求网络中最短路径的Dijkstra算法，进行改进得到新的算法，可对含多种权重计算方式的网络进行搜索，得出最小费用路径（最短路径），算出两点之间的最优路径，进而根据非线性规划，借助于Lingo软件求解即可求出相应的结果。
六、 模型的评价及改进
1．优点：
1）本问题中运用了求网络中最短路径的Dijkstra算法，进行改进得到新的算法，可对含多种权重计算 方式的网络进行搜索，算出两点之间的最优路径，计算结果准确。
2）本问题构造出的模型算法较简单，也可以运用相应的其他编程软件来得到比较满意的结果。
2．缺点：
1）由于本问题有现成的比较先进的解法，但由于缺乏基本的数学软件资料和相应的算法资料，不能将其准确求解。
2） 于在求解最短路时，我们用人工计算容易将问题复杂化，同时，容易出错。 3）作为图论问题的技术而言，求解过程较难，且不易求出最优解 3．模型改进
本问题中需要用现成的先进的网络流求解，但本问题没有求解，实际上本问题中加权穷举法，可采用相应的网络法来代替。在求解问题三时可用最小树求解，同时，我们可将本问题运用于时间的变化等范围的推广。
参考文献：
[1]甘应爱，田丰等等.运行学.清华大学出版社,北京,1994。
[2]袁亚湘.孙文瑜著.最优化理论与方法.科学出版社，北京，1997. [3]徐俊明著.图论及其应用.中国科学技术大学出版社，合肥，1997. 附录一
S 1-S7与A1-A15间的最小费用矩阵 A=[];
for i=1:39
for j=1:39 A(i,j)=inf; end end
for j=1:39 A(j,j)=0; end
A(1,2)=104;A(2,1)=104;A(2,3)=301;A(3,2)=301; A(3,4)=750;A(4,3)=750;A(4,5)=606;A(5,4)=606; A(5,6)=194;A(6,5)=194;A(6,7)=205;A(7,6)=205; A(7,8)=201;A(8,7)=201;A(8,9)=680;A(9,8)=680;
A(9,10)=480;A(10,9)=480;A(10,11)=300;A(11,10)=300; A(11,12)=220;A(12,11)=220;A(12,13)=210;A(13,12)=210; A(13,14)=420;A(14,13)=420;A(14,15)=500;A(15,14)=500; A(15,22)=20;A(22,15)=20;A(15,39)=20;A(39,15)=20; A(14,38)=30;A(38,14)=30;A(14,21)=110;A(21,14)=110; A(13,37)=62;A(37,13)=62;A(12,35)=10;A(35,12)=10; A(11,34)=10;A(34,11)=10;A(10,32)=70;A(32,10)=70; A(9,31)=42;A(31,9)=42;A(8,30)=12;A(30,8)=12; A(7,16)=31;A(16,7)=31;A(7,29)=10;A(29,7)=10; A(6,28)=5;A(28,6)=5;A(5,27)=10;A(27,5)=10; A(4,26)=600;A(26,4)=600;A(3,24)=2;A(24,3)=2; A(2,23)=3;A(23,2)=3;A(23,25)=450;A(25,23)=450;
A(24,25)=80;A(25,24)=80;A(25,26)=1150;A(26,25)=1150;
A(26,30)=1100;A(30,26)=1100;A(17,30)=1200;A(30,17)=1200; A(30,16)=202;A(16,30)=202;A(16,29)=20;A(29,16)=20; A(29,28)=195;A(28,29)=195;A(28,27)=306;A(27,28)=306; A(30,31)=720;A(31,30)=720;A(31,18)=690;A(18,31)=690; A(31,32)=520;A(32,31)=520;A(32,33)=170;A(33,32)=170; A(33,19)=690;A(19,33)=690;A(33,36)=160;A(36,33)=160; A(33,34)=88;A(34,33)=88;A(34,20)=462;A(20,34)=462; A(33,36)=160;A(36,33)=160;A(36,35)=70;A(35,36)=70; A(36,37)=320;A(37,36)=320;A(37,38)=160;A(38,37)=160; A(38,21)=70;A(21,38)=70;A(38,39)=290;A(39,38)=290;