运输问题的数学模型.ppt

解先作出这问题的产销平衡表和单位运价表，见表3-3，表3-4表3-3单位运价表表3-4产销平衡表确定初始基可行解01这与一般线性规划问题不同。02产销平衡的运输问题总是存在可行解。因有03必存在xij≥0，i=1，…，m，j=1，…，n04这就是可行解。又因0≤xij≤min(aj，bj)05故运输问题必存在最优解。06确定初始基可行解的方法很多，有西北角法，最小元素法和伏格尔(Vogel)法。一般希望的方法是既简便，又尽可能接近最优解。下面介绍两种方法：12从表3-3中找出最小运价为1，这表示先将A2的产品供应给B1。因a2＞b1，A2除满足B1的全部需要外，还可多余1吨产品。在表3-4的(A2，B1)的交叉格处填上3。得表3-5。并将表3-3的B1列运价划去。得表3-6。3这方法的基本思想是就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小。一直到给出初始基可行解为止。以例1进行讨论。素法表3-5.表3-6在表3-6未划去的元素中再找出最小运价2，确定A2多余的1吨供应B3，并给出表3-7，表3-8。在表3-8未划去的元素中再找出最小运价3；这样一步步地进行下去，直到单位运价表上的所有元素划去为止，最后在产销平衡表上得到一个调运方案，见表3-9。这方案的总运费为86元。用最小元素法给出的初始解是运输问题的基可行解，其理由为：用最小元素法给出的初始解，是从单位运价表中逐次地挑选最小元素，并比较产量和销量。当产大于销，划去该元素所在列。当产小于销，划去该元素所在行。然后在未划去的元素中再找最小元素，再确定供应关系。这样在产销平衡表上每填入一个数字，在运价表上就划去一行或一列。表中共有m行n列，总共可划(n+m)条直线。但当表中只剩一个元素时，这时当在产销平衡表上填这个数字时，而在运价表上同时划去一行和一列。此时把单价表上所有元素都划去了，相应地在产销平衡表上填了(m+n-1)个数字。即给出了(m+n-1)个基变量的值。这(m+n-1)个基变量对应的系数列向量是线性独立的。证若表中确定的第一个基变量为它对应的系数列向量为:01因当给定的值后，将划去第i1行或第j1列，即其后的系数列向量中再不出现ei1或em+j1，因而不可能用解中的其他向量的线性组合表示。类似地给出第二个，…，第(m+n-1)个。这(m+n-1)个向量都不可能用解中的其他向量的线性组合表示。故这(m+n-1)个向量是线性独立的。02用最小元素法给出初始解时，有可能在产销平衡表上填入一个数字后，在单位运价表上同时划去一行和一列。这时就出现退化。关于退化时的处理将在2.4节中讲述。2.伏格尔法最小元素法的缺点是：为了节省一处的费用，有时造成在其他处要多花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费调运。伏格尔法的步骤是：在表3-3中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行，见表3-10。从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表3-10中B2列是最大差额所在列。B2列中最小元素为4，可确定A3的产品先供应B2的需要。得表3-11同时将运价表中的B2列数字划去。

如表3-12所示。对表3-12中未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。重复第一、二步。直到给出初始解为止。用此法给出例1的初始解列于表3-13。由以上可见：伏格尔法同最小元素法除在确定供求关系的原则上不同外，其余步骤相同。伏格尔法给出的初始解比用最小元素法给出的初始解更接近最优解。01本例用伏格尔法给出的初始解就是最优解。02判别的方法是计算空格(非基变量)的检验数cij-CBB-1Pij，i,j∈N。因运输问题的目标函数是要求实现最小化，故当所有的cij-CBB-1Pij≥0时，为最优解。下面介绍两种求空格检验数的方法。01闭回路法；02位势法032-2最优解的判别1.闭回路法在给出调运方案的计算表上，如表3-13，从每一空格出发找一条闭回路。它是以某空格为起点。用水平或垂直线向前划，当碰到一数字格时可以转90°后，继续前进，直到回到起始空格为止。闭回路如图3-1的(a),(b),(c)等所示。从每一空格出发一定存在和可以找到唯一的闭回路。因(m+n-1)个数字格(基变量)对应的系数向量是一个基。任一空格(非基变量)对应的系数向量是这个基的线性组合。如Pij,i,j∈N可表示为其中Pik