数学建模运输问题求解

问题说明:                                     表1

设一种汽车只能到一个城市，每个城市都只能要一种型号的汽车，应如何安排发货？

问题分析:

   约束条件：一种汽车只能到一个城市，每个城市都只能要一种型号的汽车

   决策目标：分派后使利润最大

模型假设：

设变量Cij（i,j=1、2、3、4、5）表示派第i号车到第j座城市的利润，引入变量Xij，其取值只能是0（当不指派第i号车到第j座城市）或1(当指派第i号车到第j座城市)

当问题要求极大时的数学模型是：

    5     5

Max=∑i ∑j CijXij 

 i=1    j=1

∑i Xij=1(j=1、2、3、4、5)

∑j Xij=1(i=1、2、3、4、5)

模型求解：

方法1匈牙利法：

   第一步：找出效率矩阵每行最大元素，并从每行中减去，再找出每列的最大元素，再从每列中减去

    | 3 2 1 4 5 | 5      | -2 -3 -4 -1  0 |     | -2  0 -4 -1  0 |

     | 7 1 6 7 3 | 7      |  0 -6 -1  0 -4 |     |  0 -3 -1  0 -4 |

  A= | 4 2 5 4 3 | 5  —〉| -1 -3  0 -1 -1 | —〉| -1  0  0 -1 -2 |

     | 2 1 5 6 3 | 6      | -4 -5 -1  0 -3 |     | -4 -2 -1  0 -3 |

     | 6 4 3 9 4 | 9      | -3 -5 -6  0 -5 |     | -3 -2 -6  0 -5 |

                             0 -3  0  0  0

第二步：从第一行开始若该行只有一个0元素，就对这个0打上（）号，对打（）0元素所在列画一条直线。若该行没有0元素或有两个以上0元素则转下一行（已划去的不包括在内），依次进行到最后一行。

从第一列开始若该列只有一个0元素，就对这个0打上（）号（已划去的不包括在内），对打（）0元素所在行画一条直线。若该列没有0元素或有两个以上0元素则转下一列，依次进行到最后一列。

| -2   0  -4  -1 （0）|

     |（0）-3  -1   0  -4  |

     | -1   0 （0）-1  -2  |

     | -4  -2  -1 （0）-3  |

     | -3  -2  -6   0  -5  |

第三步：矩阵中所有0元素或被划去，或打上（）号，但打（）号的0元素个数小于5。从矩阵未被直线覆盖的数字中找出一个最小的数-1。对矩阵每行当该行有直线覆盖时，令Ui=0，无直线覆盖的，令Ui=k。对矩阵每列，当该列有直线覆盖时，令Vj=-k，无直线覆盖的，令Vj=0。从原矩阵的每个元素分别减去Ui和Vj，得到一个新的矩阵。

| -2   0  -4  -1   0 | 0      | -2  0 -4 -2  0 |

     |  0  -3  -1   0  -4 | 0      |  0 -3 -1 -1 -4 |

     | -1   0   0  -1  -2 | 0  —〉| -1  0  0 -2 -2 |

     | -4  -2  -1   0  -3 |-1      | -3 -1  0  0 -2 |

     | -3  -2  -6   0  -5 |-1      | -2 -1 -5  0 -4 |

   0   0   0   1   0

第四步：重复第二步

| -2   0  -4  -2 （0）|

     |（0）-3  -1  -1  -4  |

     | -1 （0） 0  -2  -2  |

     | -3  -1 （0） 0  -2  |

     | -2  -1  -5 （0）-4  |

第五步：得到最优矩阵

 | 0 0 0 0 1 |

     | 1 0 0 0 0 |

     | 0 1 0 0 0 |

     | 0 0 1 0 0 |

     | 0 0 0 1 0 |

方法2运用matlab求解：

往往指派问题系数都是最小值，所以根据匈牙利法的基本原理“效率矩阵的任一行或一列加上或减去任一常数，指派问题的最优解不会受到影响”所以在不影响结果的前提下用效率矩阵中的最大值减去效率矩阵求解。

function yunshu 

c=[6 7 8 5 4

    2 8 3 2 6 

    5 7 4 5 6

    7 8 4 3 6

    3 5 6 0 5];

c=c(:);

a=zeros(10,25);

for  i=1:5

a(i,(i-1)*5+1:5*i)=1;

a(5+i,i:5:25)=1;

end

b=ones(10,1);

[x,fval]=linprog(c,[],[],a,b,zeros(25,1),ones(25,1));

AP=reshape(x,5,5)

调用M文件yunshu得到效率矩阵:

AP =

    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.0000    0.0000    1.0000    0.0000    0.0000

    0.0000    0.0000    0.0000    1.0000    0.0000

结果分析：

上述最优矩阵表示派A车到城市5，B车到城市1，C车到城市2，D车到城市3，E车到城市4可获得最大利润Max=5+7+2+5+9=28