木材运输的最优方案

1、 木材运输的最优方案一.摘要：运输是实现人和物空间位置变化的活动，是社会物质生产的必要条件之一,与人类的生产生活息息相关。高效的运输方案能够节约资源和能源，同时也能够节约费用，从而带来经济上的收益。一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的问题。本文讨论的就是木材运输费用最优化的问题，运用线性规划的数学模型遵循运输成本最低原则，引入x变量作为决策变量，建立目标函数，列出约束条件，借助matlab和lingo软件分别对三个问题进行了分析，得出其中的最优解，使得把木材

2、从3个产地运到5个市场的总运费最少。对于第一个问题，仅采用火车运输木材。在满足从每个产地运出的货物总量等于其产量，运输到每个市场的货物总量等于需求量的约束条件下，利用matlab软件进行线性规划，建立总运费最小的目标函数，求解得到运输费用最小的分配方案，最小运费为2816千美元。对于第二个问题，全部木材改用水路运输。在满足与第一个问题相同约束的条件下，还需考虑每年在每条线路上的船只的投资费用，采用哪一种运输路线就要对其进行投资，否则不需要，为了解决这一问题，我们引入了0-1规划。利用lingo软件进行线性规划，建立总运费最小的目标函数，求解得到运输费用最小的分配方案，最小运费为1628.1千美

3、元。针对第三问，在可以任意选择交通工具的情况下，确定最优的木材运输方案，假设把木材分为分别用火车和船只运输的两部分，先用最小元素法求最优解，在满足约束条件的基础上，对这两部分所需的费用相加，得到的最小的运输费用为。模型的建立遵循了简单明了的原则，运用专业数学软件求解，结果可行性高，具有推广性。关键词：运输模型 线性规划 matlab lingo 0-1规划 最小元素法 闭回路法 二问题的重述LT是一个木材公司，它有3个木材产地和5个销售市场。木材产地1、产地2、产地3每年的产量分别为15百万个单位、20百万个单位、15百万个单位。5个市场每年能卖出的木材量分别为11百万个单位、12百万个单位、

4、9百万个单位、10百万个单位、8百万个单位。 在过去，这个公司是用火车来运送木材的。后来随着火车运费的增加，公司正在考虑用船来运输木材。采用这种方式需要公司在使用船只上进行一些投资。除了投资成本以外，在不同线路上用火车运输和用船运输每百万单位的费用如下表所示： 表1 运输费用情况 产 地用火车运输每百万木材费用(千美元) 用船只运输每百万木材费用(千美元) 市场1 市场2 市场3 市场4 市场5 市场1 市场2 市场3 市场4 市场5 1 61 72 45 55 66 31 38 24 35 2 69 78 60 49 56 36 43 28 24 31 3 59 66 63 61 47 33

5、 36 32 26 其中“”表示不能用船只运输的路线。如果用船只运输的话，每年在每条线路上对船只的投资费用如下： 表2 新船运路线投资费用情况产 地对船只的投资（千美元）市场一市场二市场三市场四市场五1 27.5 30.3 23.8 28.5 2 29.3 31.8 27 25 26.5 3 28.3 27.5 26.8 24 问题一：假设全部货物还是都沿用火车运输，运输费用最少的运输方案是什么？最少运费是多少？问题二：假设全部货物都改用船只运输，运输费用最少的运输方案是什么？最少运费是多少？问题三：假设货物既可以用火车运输，也可以用船只运输，为使总运费最少，如何选择运输方案？最少的运费为多少

6、？ 三模型假设假设1.每一个产地都有一个固定的供应量，所有的供应量都必须配送到各个市场。假设2.每一个市场都有固定的需求量，整个需求量都必须由产地满足。假设3.从任何一个产地到任何一个销地的木材运输成本和所运输的数量呈线性比例关系，这个成本就等于运输的单位成本乘以运输数量。假设4.运输过程中不会出现其它客观问题（如交通事故、天气影响和工具维修等不利因素），木材可以安全到达目的地。四模型的建立问题一：1. 问题分析表4.1给出了3个产地和5个市场的木材供应量与需求量及各产地到各市场的每百万个单位的运输费用。 表3.1木材产销量及单位运价 3个木材生产地的总生产量与5个木材销售市场的销售总量是相等

7、的，运用线性规划的知识建立运输费用最小的目标函数，生产基地的产量与输出量相等，销售市场的销量与输入量相等作为约束条件，求解得到最小运输费用的运输方案。2.符号说明 符号表示意义木材生产地Ai的生产量市场Bj的需求量 把木材从产地Ai运到Bj的运输量把木材从产地Ai运到Bj的每百万个单位运价Z最小运输费用3.建立线性规划模型（模型一）由上述问题分析，得到以运输费用最小的规划模型： 目标函数 约束条件的建立如下： 问题二：1.问题分析假设全部木材都用船只运输，从三个产地运到五个市场，分别从三个产地运出的总量必须小于产地的产量，运到五个市场的总量必须不小于市场的需求量，并且如果从i地运到j市场，则这

8、条路就需要船只投资费用，如果不需要从i地运到j市场，那么就不需要额外的费用，最后，用从i地运到j市场单位运费乘以从i地运到j市场的木材的量再求和在与从i地运到j市场路线的船只费用相加，就可以得到运输木材的所有费用。2.符号的说明 Vi 第i个木材产地 Wj 第j个木材市场Dij 从i地运到j市场的运费Mij从i地运到j市场所运木材的质量Xij 描述木材是否从i地运到j市场Cij 从i地运到j市场所需要的船只投资费用3.建立模型假设从i地运到j市场的运费为Dij，所运木材的质量为mij，所需要的船只投资费用为cij，用xij=0或1表示木材从i地运到j市场或者不从i地运到j市场。总费用为：Z=（

9、Cij*Mij+Xij*Dij） 约束条件如下：(1) 从三个产地运出的总量必须小于产地的产量 M1j<=15 M2j<=20 M3j<=15(2) 运到五个市场的总量必须不小于市场的需求量：(3) 从i地运到j市场，则这条路就需要船只投资费用，如果不需要从i地运到j市场，那么就不需要额外的费用：Xij=0或1若Mij=0，则Xij=0综合以上分析，建立问题二的模型如下： Min=(Cij*Mij+Xij*Dij)M1j<=15 M2j<=20 M3j<=15 Mi1=11 Mi2=12 Mi3=9 s.t. Mi4=10 Mi5=8Xij=0或1Mij=0

10、，则Xij=0对模型三：1.问题的分析在第一问的与第二问的基础上，可以比较俩种不同运输方式的运费的大小，明显木材用船只运输的费用不管是运输多少单位的木材都比火车要小，所以只考虑全部木材都用船只运输，从三个产地运到五个市场，并且场地的供应量与需求量相等，这是产销平衡运输问题，如果从i地运到j市场，则要加上这条路的船只投资费用，如果不需要从i地运到j市场，那么就不需要对船只投资额外的费用，最后，用从i地运到j市场单位运费乘以从i地运到j市场的木材的量再求和在与从i地运到j市场路线的船只费用相加，就可以得到运输木材的所有费用。2.符号的说明Vi第i个木材产地Wj第j个木材市场Xij从i地用火车运到j

11、市场的质量Cij从i地用火车运到j市场每单位物资的运价Yij木材从i地用船只运到j市场的质量Dij木材从i地用船只运到j市场每单位物资的运价Qij描述木材是否从i地用船只运到j市场Pij需要的船只投资费用3. 模型的建立为了解决只有船只运输的情况下运费最少，下面用最小元素法分析求出最优解。最小元素法的基本思想是优先满足单位运价最小的供销业务。首先找出运价最小的，并以最大限度满足其供销量为原则确定供销业务。同样的方法反复进行直到确定了所有的供销业务，得到一个完整的调运方案即初始基本可行解为止。首先列出船的运费表，如下，并在此基础上用最小元素法找到木材用船运输的方案表。船的方案表与运费表方案表运费

12、表产地销量V1V2V3V4V5产量V1V2V3V4V5W111415313824-35W25105203643282431W312315-33363226需求量11129108以此，得到一初始方案： V1 V2 V3 V4V5 W1 11 4 - W25105 W3-123D11=11 , D13=4， D23=5，D24=10， D25=5， D32=12，D35=3.（有数格）D12=D15=D21=D22=D33=D34=0（空格） (说明：由题可知D14,D31不能用船只运输，不考虑这两处的运输量）所以初始运费方案为Ymin=11x31+27.5+24x4+23.8+5x28+27+2

13、4x10+25+31x5+26.5+33x12+28.3+26x3+24=1628.1(千美元）注：（）有数格是基变量，共m+n-1=3+5-1=7个。空格是非基变量，共划去m+n=8条线；（）如果填上一个变量之后能同时划去两条线（一行与一列），就须在所划去的该行或该列填一个0，此0格当有数格对待。由上面的结论可知最小费用为1628.1千美元。为了检验上面的结果的精确性，又建立了0-1线性规划模型。假设木材从i地用火车运到j市场的质量为Xij，所需运费为Cij；木材从i地用船只运到j市场的质量为Yij，所需运费为Dij，用Qij=0或1表示木材从i地用船只运到j市场或者不从i地用船只运到j市场

14、，所对应需要的船只投资费用为Pij。可得总费用为：Z=（Cij*Xij+Yij*Dij+PijQij）约束条件如下：（1）从三个产地运出的总量必须小于产地的产量: X1j+Y1j<=15 X2j+Y2j<=20 X3j+Y3j<=15（2）运到五个市场的总量必须不小于市场的需求量：Xi1+Yi1=11 Xi2+Yi2=12 Xi3+Yi3=9 Xi4+Yi4=10 Xi5+Yi5=8(4) 从i地运到j市场，则这条路就需要船只投资费用，如果不需要从i地运到j市场，那么就不需要额外的费用：Qij=0或1若Yij=0，则Qij=0.综合以上分析，建立问题三的模型如下： Min=（

15、Cij*Xij+Yij*Dij+PijQij）X1j+Y1j<=15 X2j+Y2j<=20 X3j+Y3j<=15Xi1+Yi1=11 Xi2+Yi2=12 Xi3+Yi3=9 s.t. Xi4+Yi4=10 Xi5+Yi5=8Qij=0或1若Yij=0，则Qij=0.五模型的求解问题一：以上模型为一次线性问题，可以借助matlab软件求解，在matlab中编辑窗口中输入程序，可得到用火车运输木材的最优化方案，结果如下表格所示：木材最优运输分配方案 单位：百万木材 市场产地 V1 V2 V3 V4V5 W1 6 0 9 00 W2200108 W3312000所以得到的最小

16、运输费用为2816千美元。问题二:以上模型的目标函数是一次型，即线性问题，可以用lingo软件求解，编写lingo程序见附录。点击“求解”按钮，得到最优解，总费用为1628.100千美元，木材的运输计划如图： 木材最优运输分配方案 单位：百万木材 市场产地 V1 V2 V3 V4V5 总和 W1 11 0 4 0015 W200510520 W301200315 总和11129108 所以得到的最小运输费用为1628.100千美元。由图可知满足从三个产地运出的总量小于产地的产量，运到五个市场的总量等于市场的需求量。所以此结果符合约束条件。问题三：用最小元素法所得结果如下：木材最优运输分配方案

17、单位：百万木材 市场产地 V1 V2 V3 V4V5 W1 11 0 4 00 W2005105 W3012003用0-1规划验证，与lingo求解结果一样。编程见附录。综合以上方案，为了使木材的运费最少的运输分配方案为只用船只运输，即得到的最小运输费用为1628.100千美元。六结果的分析与检验对问题三：用最小元素法解线性规划问题时，在迭代过程中每次求得一个基本可行解以后，都要检验它是不是最优解，如果不是最优解，就要继续进行迭代，直到求得最优解或者判定无最优解。下面用闭回路法来检验是不是最优解。在运输问题中，每个空格对应一个非基变量。因此，我们需要求出每个空格的检验数。由于目标要求极小，用闭

18、回路法比较简单，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案。 对方案表中每一空格，确定一条由空格出发的闭回路。 闭回路是由水平或垂直线组成的闭合图形。闭回路上的顶点除了这个空格外，其余均为有数格。表1 市场产地 V1 V2 V3 V4V5 W1 11 4 W255105 W3123可以证明，对每一个空格都存在而且惟一存在这样一条封闭回路。表2 市场产地 V1 V2 V3 V4V5 W1 11 4 W2 5105 W3 12333表3 市场产地 V1 V2 V3 V4V5 W1 11 4 W2 5105 5 W3123表4 市场产地 V1 V2 V3 V4V5 W1 11 4 W

19、25105 W3 1233表5 市场产地 V1 V2 V3 V4V5 W1 11 4 W25105 W31233表6 V1 V2 V3 V4V5 W1 11 4 W25105 W31233计算出空格的检验数等于闭回路上由此空格起奇数顶点运价与偶数顶点运价负值的代数和。表一：不同产地船的运输费用 单位：千美元产地用船只运输每百万木材费用(千美元) 市场1市场2市场3市场4市场513138243523643282431333363226如表一与表16的数据得各个表16的检验数,g21=36-31+24-28=1 g12=38-24+28-31+26-33=4g34=32+31-24-26=13 g

20、15=35+28-24-31=8g22=43+26-31-33=5 g33=36+31-28-26=13当所有空格检验数 gij 0则当前方案是最优的，若尚有空格检验数小于零，表明当前方案尚有待调整，g ij 具有确切的经济意义，它表示由wi往vj增运1单位时，引起的总运输成本的变化数。若所有的空格检验数都大于等于零，表明任何一个空格处调运1单位都会引起总成本的上升，这表明当前方案不能再改进，即定为最优方案案。由此可知上面的用船只运输的方案为最优方案。 七模型评价模型的优点：1. 本文建立的函数是以最少运费为目标的单目标规划函数，采用matlab和lingo编程，实用价值高，结果准确。2. 本

21、文所建立的模型分析思路简洁清晰，可以紧密联系到现实实际问题，只需要更改数据便可求其他的运输问题，具有推广性。3. 对第三问，我们先对其分析得到最优解，再用lingo编程验证了结果的最优性，使最后的结果更加真实可靠，具有说服力。模型的缺点：1.在实际生活中，运输问题一把不会达到供求量与需求量相等的情况，而我们的模型只是针对产销平衡运输问题的，具有狭隘性。2.模型给出的约束条件可能也不太现实八参考文献：【1】袁新生 邵大宏 郁时炼，LINGO和EXCEL在数学建模中的应用，北京：科学出版社，2008年11月【2】吴建国 ，数学建模案列精编 ，北京：中国水利水电出版社，2005【3】 运输问题的资源

22、模型 ， 九附录对问题一用matlab的编程：程序代码：% 火车运输优化方案c=61,72,45,55,66,69,78,60,49,56,59,66,63,61,47;Aeq=1,1,1,1,1,0,0,0,0,0,0,0,0,0,0 0,0,0,0,0,1,1,1,1,1,0,0,0,0,0 0,0,0,0,0,0,0,0,0,0,1,1,1,1,1 1,0,0,0,0,1,0,0,0,0,1,0,0,0,0 0,1,0,0,0,0,1,0,0,0,0,1,0,0,0 0,0,1,0,0,0,0,1,0,0,0,0,1,0,0 0,0,0,1,0,0,0,0,1,0,0,0,0,1,0 0

23、,0,0,0,1,0,0,0,0,1,0,0,0,0,1;beq=15 20 15 11 12 9 10 8;vlb=0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;vub=11;12;9;10;8;11;12;9;10;8;11;12;9;10;8;x,fval=linprog(c,Aeq,beq,vlb,vub)程序运行结果：x = 6.0000 0.0000 9.0000 0.0000 0.0000 2.0000 0.0000 0.0000 10.0000 8.0000 3.0000 12.0000 0.0000 0.0000 0.0000fval =2.8160e+003对

24、问题二用lingo软件求解，编写lingo程序如下：MODEL: SETS: AB/W1 W2 W3/:WI; ！该集合表示3个场地，属性WI表示各产地的最大供货能力；BC/V1 .V5/:VJ; ！该集合表示5个市场，属性VJ表示市场的需求； LINKS(AB,BC):C,X,M,D; ！衍生集合LINKS有3*5=15个成员，定义4个与集合LINKS有关的属性：C、X、M和D，其中D和C相当于具有15个元素的常数矩阵，X和M为决策变量； ENDSETS DATA: WI=15,20,15; VJ=11,12,9,10,8; D=27.5,30.3,23.8,100,28.5 29.3,31

25、.8,27,25,26.5 100,28.3,27.5,26.8,24; C= 31,38,24,100,35 36,43,28,24,31 100,33,36,32,26; ENDDATA MIN=SUM(LINKS(I,J):C(I,J)*M(I,J)+X(I,J)*D(I,J); FOR(AB(I):SUM(BC(J):M(I,J)<WI(I);！各产地生产能力约束； FOR(BC(J):SUM(AB(I):M(I,J)=VJ(J);！各市场所需的约束； FOR(LINKS:BIN(X); ！对X进行0-1约束； FOR(LINKS(I,J):X(I,J)=IF( M(I,J)#E

26、Q#0,0,1);！即约束条件Mij=0，则Xij=0； END程序结果如下：Local optimal solution found. Objective value: 1628.100 Extended solver steps: 0 Total solver iterations: 82 Variable Value Reduced Cost WI( W1) 15.00000 0.000000 WI( W2) 20.00000 0.000000 WI( W3) 15.00000 0.000000 VJ( V1) 11.00000 0.000000 VJ( V2) 12.00000 0.0

27、00000 VJ( V3) 9.000000 0.000000 VJ( V4) 10.00000 0.000000 VJ( V5) 8.000000 0.000000 C( W1, V1) 31.00000 0.000000 C( W1, V2) 38.00000 0.000000 C( W1, V3) 24.00000 0.000000 C( W1, V4) 100.0000 0.000000 C( W1, V5) 35.00000 0.000000 C( W2, V1) 36.00000 0.000000 C( W2, V2) 43.00000 0.000000 C( W2, V3) 28

28、.00000 0.000000 C( W2, V4) 24.00000 0.000000 C( W2, V5) 31.00000 0.000000 C( W3, V1) 100.0000 0.000000 C( W3, V2) 33.00000 0.000000 C( W3, V3) 36.00000 0.000000 C( W3, V4) 32.00000 0.000000 C( W3, V5) 26.00000 0.000000 X( W1, V1) 1.000000 0.000000 X( W1, V2) 0.000000 0.000000 X( W1, V3) 1.000000 0.0

29、00000 X( W1, V4) 0.000000 0.000000 X( W1, V5) 0.000000 0.000000 X( W2, V1) 0.000000 0.000000 X( W2, V2) 0.000000 0.000000 X( W2, V3) 1.000000 0.000000 X( W2, V4) 1.000000 0.000000 X( W2, V5) 1.000000 0.000000 X( W3, V1) 0.000000 0.000000 X( W3, V2) 1.000000 0.000000 X( W3, V3) 0.000000 0.000000 X( W

30、3, V4) 0.000000 0.000000 X( W3, V5) 1.000000 0.000000 M( W1, V1) 11.00000 0.000000 M( W1, V2) 0.000000 4.000000 M( W1, V3) 4.000000 0.000000 M( W1, V4) 0.000000 80.00000 M( W1, V5) 0.000000 8.000000 M( W2, V1) 0.000000 1.000000 M( W2, V2) 0.000000 5.000000 M( W2, V3) 5.000000 0.000000 M( W2, V4) 10.

31、00000 0.000000 M( W2, V5) 5.000000 0.000000 M( W3, V1) 0.000000 70.00000 M( W3, V2) 12.00000 0.000000 M( W3, V3) 0.000000 13.00000 M( W3, V4) 0.000000 13.00000 M( W3, V5) 3.000000 0.000000 D( W1, V1) 27.50000 0.000000 D( W1, V2) 30.30000 0.000000 D( W1, V3) 23.80000 0.000000 D( W1, V4) 100.0000 0.00

32、0000 D( W1, V5) 28.50000 0.000000 D( W2, V1) 29.30000 0.000000 D( W2, V2) 31.80000 0.000000 D( W2, V3) 27.00000 0.000000 D( W2, V4) 25.00000 0.000000 D( W2, V5) 26.50000 0.000000 D( W3, V1) 100.0000 0.000000 D( W3, V2) 28.30000 0.000000 D( W3, V3) 27.50000 0.000000 D( W3, V4) 26.80000 0.000000 D( W3

33、, V5) 24.00000 0.000000 Row Slack or Surplus Dual Price 1 1628.100 -1.000000 2 0.000000 4.000000 3 0.000000 0.000000 4 0.000000 5.000000 5 0.000000 -35.00000 6 0.000000 -38.00000 7 0.000000 -28.00000 8 0.000000 -24.00000 9 0.000000 -31.00000 10 0.000000 -27.50000 11 0.000000 -30.30000 12 0.000000 -2

34、3.80000 13 0.000000 -100.0000 14 0.000000 -28.50000 15 0.000000 -29.30000 16 0.000000 -31.80000 17 0.000000 -27.00000 18 0.000000 -25.00000 19 0.000000 -26.50000 20 0.000000 -100.0000 21 0.000000 -28.30000 22 0.000000 -27.50000 23 0.000000 -26.80000 24 0.000000 -24.00000对问题三用lingo软件求解，编写lingo程序如下：MODEL: SETS: AB/W1 W2 W3/:WI; ！该集合表示3个场地，属性WI表示各产地的最大供货能力；BC/V1 .V5/:VJ; ！该集合表示5个市场，属性VJ表示市场的需求；LINKS(AB,BC):X,Y,C,D,P,Q; ！衍生集合LINKS有3*5=15个成员，定义6个与集合LINKS有关的属性：C、X、M和D，其中D、C和P相当于具有15个元素的常数矩阵，X、Y和Q为决策变量； ENDSETS DATA: WI=15,20,15; VJ=11,12,9,10,8; P=27.5,30.3,