教学材料《运筹学》-第3章

3.1产销平衡运输问题及数学模型第二步，建立目标函数:该问题的总费用为第三步，确定约束条件:由于每个产地的产量都要运到各个需求地，因此有如下等式成立:同时，每个需求地的需求量均得到满足，因此有如下等式成立:上一页下一页返回3.1产销平衡运输问题及数学模型另外，从第2个产粮地运往第j个需求地的运输量均为非负。综上，得到该运输问题的数学模型:上一页下一页返回3.1产销平衡运输问题及数学模型3.1.2产销平衡运输问题的数学模型(1)一般模型。对于一般的产销平衡运输问题，可以描述为:有m个产地(A1

、A2、A3

，…,Am)，生产或供应某种物资，其产量分别为;有n个销地(B1,B2，...，Bn)，其需要量分别为b1,b2,…，bn

;总的产量等于总的销量;已知从第i个产地到第j个销地的单位运价为cij，在满足各地需要的前提下，求总运输费用最小的调运方案。对于产销平衡运输问题，通常设xij(i=1,2,...，m;j=1,2,...,n)为第i个产地到第j个销地的运量，则数学模型为上一页下一页返回3.1产销平衡运输问题及数学模型\模型(3-1)可简写为上一页下一页返回3.1产销平衡运输问题及数学模型(2)模型特征。a.矩阵中所有元素要么为“1"，要么为“0"-b.矩阵(3-3)中，每一列中都只有两个元素为“1"，分别位于第i行和第m+j行;c.基变量的个数为m+n-1。(3)运输问题模型的对偶形式。上一页返回3.2产销平衡运输问题求解—表上作业法从模型上可以看到，运输问题也是线性规划问题，可用单纯形法求解，但由于运输问题数学模型具有特殊的结构，因此存在更简便的计算方法一表上作业法，其实质也是单纯形法，求解思路如图3-1所示。与单纯形法类似，如何确定初始方案(初始基可行解)、如何判别一个方案是否最优、如何对方案进行调整是求解的关键所在。因此，表上作业法包括三个部分:初始方案的确定、判优和方案调整。3.2.1初始方案确定确定初始方案的方法很多，在本教材中只介绍三种较为常用的方法:最小元素法、西北角法和伏格尔法。

(1)最小元素法(MatrixMinimum)。下一页返回3.2产销平衡运输问题求解—表上作业法最小元素法的基本思想:就近供应，即优先考虑单位运价最小(或运距最短)的供销路线，最大限度地满足其需求量。即从单位运价中最小的运价开始确定供销关系，然后次小，一直到求出初始基本可行解为止。首先，找出运价表中最小的元素，在对应的格中填入最多可以供应的数量，若某行(列)的产量(销量)已满足，则把所在行(列)划去;然后，再从未划去的元素中找到最小值，重复上述步骤，直至得到一个初始方案(基本可行解)。(2)西北角法(NorthwestCornerMethod)。西北角法，是确定初始调运方案的基本方法之一，其基本思想是:优先满足运价表中西北角(左上角)空格的产销需求，从运价表的西北角位置开始，依次安排m个产地和n个销地之间的运量。上一页下一页返回3.2产销平衡运输问题求解—表上作业法(3)伏格尔法(Vogel'sApproximationMethod)。伏格尔法又称差值法，基本思想是:若某供应地的物资如不能按最小运费就近供应，就要考虑次小运费，最小运费和次小运费之间的差额越大，说明未按最小运费调运所增加的运费越多，因此，对于差额最大产销路线，尽量采用最小运费进行调运。一般来说，与西北角法和最小元素法相比，伏格尔法得到的初始方案更优。伏格尔法要求首先计算出各行各列中最小的cij，与次小的cij之间的差的绝对值，在具有最大差值的行或列中，选择具有最小的cij的方格来决定基变量的数值。上一页下一页返回3.2产销平衡运输问题求解—表上作业法这样就可以避免将运量分配到该行(或该列)具有次小的cij的方格中，以保证得到较小的目标函数值。伏格尔法的具体计算步骤如下:①算出各行各列中最小元素和次小元素的差额，选出最大的差额(若几个差额同为最大，可任取其一)。②在差额最大的行或列中的最小元素处填上尽可能大的数。③对未划去的行列重复以上步骤，直到得到一个初始解。由此可见，伏格尔法同最小元素法除在确定供求关系的原则上不同外，其余步骤相同。一般来说，伏格尔法给出的初始解比用最小元素法给出的初始解更接近最优解。上一页下一页返回3.2产销平衡运输问题求解—表上作业法

(4)退化解及“0”元素的添加。在确定初始方案时，每次添完数字后，都只划去一行或一列，只有在添加最后一个元素时除外(同时划去一行和一列)。但有时会出现退化解(基变量取值为零)的情形。3.2.2运输方案判优对于一个确定的运输方案，可以使用闭回路法和位势(对偶)变量法来进行检验，判别其是否最优。

(1)闭回路法。上一页下一页返回3.2产销平衡运输问题求解—表上作业法考查运输方案对应的运输表，从一个代表非基变量的空格出发，沿水平或垂直方向前进，当遇到代表基变量的数字格时顺时针或逆时针旋转90度，然后继续寻找数字格，直至回到出发点，由此形成的封闭折线叫作闭回路。例如，某一运输方案中非基变量x11所对应的闭回路如表3-25所示。闭回路法的思路:计算非基变量(空格)的检验数，当所有非基变量的检验数均大于或等于零(非负)时，运输方案达到最优。对于一个确定的空格，闭回路是唯一的。由于任意基变量是非基变量的唯一线性组合，因此对于某一空格只可以找到唯一的闭回路。上一页下一页返回3.2产销平衡运输问题求解—表上作业法在计算检验数时规定:起始顶点(空格)为偶数次顶点，与偶数次顶点相邻的顶点则为奇数顶点，偶数次顶点和奇数次顶点交错排列。对于闭回路来说，偶数次顶点的个数等于奇数次顶点的个数。非基变量检验数通过公式(3-8)求得。(2)位势(对偶)变量法。①原理:对于运输问题模型的对偶形式见式(3-7)，因此检验数,若令则有对于基变量，由于检验数为零，所以对于非基变量，上一页下一页返回3.2产销平衡运输问题求解—表上作业法②步骤:第一步，构造位势方程组:cij=ui+vj，此时cij对应于基变量。第二步，令ui为0，求得ui和vj。第三步，求非基变量检验数:，此时cij对应于非基变量。3.2.3运输方案调整当非基变量的检验数中有负数时，说明当前方案不是最优方案，因此需要调整，闭回路法是常用的调整方法，步骤如下:①对于某一非基变量xij，若σij<0，则以该空格为起始顶点做闭回路;上一页下一页返回3.2产销平衡运输问题求解—表上作业法②确定调整量0，0=min{该闭回路中奇数次顶点调运量}。③将奇数次顶点对应的调运量减去θ，偶数次顶点对应调运量加上θ。调整后，某一奇数次顶点对应的调运量将变为0，另有一偶数次顶点对应的调运量变为xij+θ，前者出基，后者入基。上一页返回3.3产销不平衡的运输问题表上作业法仅用于求解产销平衡运输问题。对于产销不平衡运输问题，首先需要将其转化为产销平衡运输问题，然后再使用表上作业法进行求解。3.3.1产量大于销量的运输问题产量大于销量的运输问题可以描述为:有m个产地(A1,A2,A3,…,Am)，生产或供应某种物资，其产量分别为有n个销地(B1,B2，...，Bn)，其需要量分别为总的产量大于总的销量(即)，已从第i个产地到第j个销地的单位运价为cij，在满足各地需要的前提下，求总运输费用最小的调运方案。下一页返回3.3产销不平衡的运输问题产量大于销量的运输模型为在用表上作业法求解时，在原