（精）数学建模2000B题.ppt

2000网易杯全国大学生  数学建模竞赛题目 B题 钢管订购和运输 （3）约束条件 与 的钢管： 生产能力的限制: 运到 的钢管用完： ⑤ 变量非负性限制： 端点限制： s.t. (4)数学模型 其中每一 表示单位钢管从 到 的 最小运输费用，因而，求解 实际上是一个求最短 “最短路经”问题是图论中最基本的问题之一。 4、模型的求解 关键1 求出目标函数中的系数 关键2 确定约束条件中的 路径的问题。 “最短路经”问题的标准算法----弗洛伊德算法。 A1 3 2 5 80 10 10 31 20 12 42 70 10 88 10 70 62 70 30 20 20 30 450 104 301 750 606 194 205 201 680 480 300 220 210 420 500 600 3060 195 202 720 690 520 170 690 462 160 320 160 110 290 1150 1100 1200 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 S1 S2 S3 S4 S5 S6 S7 图一 其中 表示从 到 的最短路程，若不能相连， 求出铁路和公路的最短路径矩阵 用 表示。 运用Floyd算法，得出局部最短路径矩阵。 铁路和公路自身分别构成权矩阵，记为 和 。 铁路和公路的最短路径矩阵的统一 对公路，将 为公路局部最小运费矩阵。 对铁路，用铁路的费用 进行转换，得局部铁路 最小运费矩阵 。 令 对得到的A,再使用一次Floyd算法，得到全局的最短 每两点间最小运费矩阵，从中抽取出 到 之间 的子矩阵即为所需的 。 求最小费用矩阵 最小费用矩阵 20 260 382 560 660 760 992 1312 1410 1505 1660 2266 2452 2653 2757 7 280 110 262 450 510 620 842 1212 1310 1405 1560 2166 2352 2553 2657 6 870 730 712 510 330 570 792 1112 1210 1305 1460 2066 2252 2453 2557 5 970 830 762 610 510 620 842 1162 1310 1405 1560 2166 2352 2503 2607 4 1320 1180 1112 960 860 820 482 862 960 1055 1210 1816 2002 2203 2307 3 1920 1780 1712 1560 1460 1420 1142 712 860 955 1110 1716 1902 2053 2157 2 1420 1280 1212 1060 960 920 642 212 31 205 380 986 1402 1603 1707 1 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 注：表中的数据乘以0.1为对应的最小费用矩阵的元素。 最小费用矩阵 20 260 382 560 660 760 992 1312 1410 1505 1660 2266 2452 2653 2757 7 280 110 262 450 510 620 842 1212 1310 1405 1560 2166 2352 2553 2657 6 870 730 712 510 330 570 792 1112 1210 1305 1460 2066 2252 2453 2557 5 970 830 762 610 510 620 842 1162 1310 1405 1560 2166 2352 2503 2607 4 1320 1180 1112 960 860 820 482 862 960 1055 1210 1816 2002 2203 2307 3 1920 1780 1712 1560 1460 1420 1142 712 860 955 1110 1716 1902 2053 2157 2 1420 1280 1212 1060 960 920 642 21