货物运输问题解答.doc

数学建模 标题：货物运输问题 某货物运输公司有，，，， 种型号的汽车. 由于运 输条件，当地货源等各种因素，每种型号的汽车运输货物到不同城市所得的利润如表1. 设一种汽车只能到一个城市，每个城市都只能要一种型号的汽车，应如何安排发货？ 表1 城市1 城市2 城市3 城市4 城市5 3 2 1 4 5 7 1 6 7 3 4 2 5 4 3 2 1 5 6 3 6 4 3 9 4 问题的描述： 这是关于货物的运输问题。需要用ABCDE五种型号的汽车运输货物到12345号城市。要求一种型号的车只能运输到一个城市，一个城市只能要一种型号的车。已知每种型号到各个城市的利润，要的出一个最优方案使得最终的利润最大。 分析过程： 一种型号汽车只能到一个城市，每个城市只能要一种型号汽车。所以我们可以将其转化为指派问题。但考虑到一般的指派问题都是求解最小值问题。所以我们要对各个利润取其相反数，则最大利润问题转化为最小值问题。往往指派问题系数都是最小值。所以根据匈牙利法的基本原理“效率矩阵的任一行或一列加上或减去任一常熟，指派问题的最优解不会受到影响”。有这一思想。我们便可适当加减数使得系数矩阵中的各个元素都是大于等于0的数。即可转化为一般的指派问题求解.得出最优运输方式，对应的即是最大利润。 建立的模型： 符号说明： z 目标函数的函数值 用匈牙利法求解： 找出利润矩阵最大元素9，之后减去C中元素得到B 找出矩阵每行的最小元素，并且分别从行中减去，有 找出矩阵每列的最小元素，再分别从行中减去，有 (1) 从第一行开始，若该行只有一个零元素，就对这个零元素标记，对标记零元素所在列画一条直线，若该行没有零元素或者有两个以上的零元素，则转下一行，以此进行到最后一行。 (2)从第一列开始，若该行只有一个零元素，就对这个零元素标记，对标记零元素所在行画一条直线，若该列没有零元素或者有两个以上的零元素，则转下一列，以此进行到最后一行。 (3)由于所划行列数相加不为5，此时出现僵局，找出没有划的元素除零以外的最小元素1，另k=1，再进行矩阵变换 (4)在已划行的元素加0，未划行的元素加1，在已列行的元素减1，未划列的元素加0，有 重复(1)(2)操作，得出 用Matlab求解： 符号说明： z 目标函数的函数值 Fij 第i种型号的汽车运输到第j号城市的利润 B 最优分派矩阵 c=[3 2 1 4 5 7 1 6 7 3 4 2 5 4 3 2 1 5 6 3 6 4 3 9 4]; C=-c; A=[1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 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 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 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 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 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 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 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 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 1 0 0 0 0 1]; b=[1;1;1;1;1;1;1;1;1;1]; Aeq=[]; beq=[]; lb=zeros(25,1); vub=ones(25,1); [x,fval]=linprog(C,A,b,Aeq,beq,lb,vub); B=reshape(x,5,5) B = 0.0000 0.0000 0.0000 0.0000 1.0000 1.0000 0.0000 0.0000 0.0000 0.0000 0.0000 1.0000 0.0000 0.0000 0.0000 0.0