运筹学第三章运输问题.

2019/12/161运筹学OPERATIONSRESEARCH2019/12/162第三章运输问题运输问题的数学模型表上作业法产销不平衡的运输问题及应用2019/12/163§1运输问题的典例及数学模型一、引例某公司从三个产地，，将产品运往四个销地，，，各产地的产量，各销地的销量，及各产地往各销地的运费单价如表所示。应如何调运可使运费最小？1A2A1B2B3B3A4B销地运费单价产地B1B2B3B4产量（吨）A13113107A219284A3741059销量（吨）36562019/12/164解：从表中可知：总产量=总销量。这是一个产销平衡的运输问题。假设表示从产地运往销地的产品数量，建立如下表格：ijxij.4,3,2,1;3,2,1ji于是可建立如下的数学模型：销地运费单价产地B1B2B3B4产量（吨）A13113107A219284A3741059销量（吨）365611x12x13x21x22x23x31x32x33x14x24x34x2019/12/165目标函数：34333231242322211413121151047829103113xxxxxxxxxxxxMinZ约束条件：947343332312423222114131211xxxxxxxxxxxx产量约束销量约束20204,3,2,1;3,2,1,06563342414332313322212312111jixxxxxxxxxxxxxij2019/12/166设有m个产地，分别为;n个销地，分别是；从产地运往销地的单位运价是，运量是产地的产量；是销地的销量。mAAA,....,21nBBB,....,21iAjBijcijxisiAjdjB二、一般运输问题数学模型则该运输问题的模型如下：2019/12/167njmixmisxnjdxtsxcfMinijinjijjmiijminjijij,...,1,,...1,0,...1,...,1.1111说明：当时，称其为产销平衡的运输问题，否则产销不平衡。njjmiids112019/12/168说明：从上述模型可以看出：（1）这是一个线性规划的模型；（2）变量有m×n个；（3）约束条件有m+n个；（4）系数矩阵非常稀疏；系数矩阵的秩一般为（m+n-1),而非m+n。若直接用单纯形法求解，显然单纯形表比较庞大，于是在单纯形法的基础上创建了表上作业法求解运输问题这一特殊的线性规划问题2019/12/169从第一节的运输问题的数学模型可知，运输问题实际上也属于线性规划，但由于运输问题的特殊性（变量个数较多，系数矩阵的特点），如果用单纯形表格方法迭代，计算量很大。今天介绍的“表上作业法”，是针对运输问题的特殊求解方法，实质还是单纯形法，但减少了计算量。表上作业法适用于求解产销平衡的运输问题。（产销不平衡的问题可转化为平衡问题）§2运输问题的表上作业法2019/12/1610表上作业法一般步骤：1、找出初始基本可行解；2、检查各非基变量的检验数，是否达到最优性条件，若达到，则得最优解；否则转第三步；3、确定出基变量、进基变量，用闭回路方法进行调整，得到新的基可行解；4、重复第二、第三步，直至得到最优解。2019/12/1611一、确定初始基本可行解：对于有m个产地n个销地的产销平衡问题，有m个关于产量的约束方程和n个关于销量的约束方程。表面上，共有m+n个约束方程。但由于产销平衡，其模型最多只有m+n-1个独立的约束方程，所以运输问题实际上有m+n-1个基变量。在m×n的产销平衡表上给出m+n-1个数字格，其相对应的调运量的值即为基变量的值。2019/12/1612销地运费单价产地B1B2B3B4产量（吨）A13113107A219284A3741059销量（吨）3656那么在该例中，应有3+4-1=6个基变量。2019/12/16131.最小元素法最小元素法的思想是就近供应，即对单位运价最小的变量分配运输量。在表上找到单位运价最小的x21，并使x21取尽可能大的值，即x21=3,把A1的产量改为1，B1的销量改为0，并把B1列划去。在剩下的3×3矩阵中再找最小运价，同理可得其他的基本可行解。销地运费单价产地B1B2B3B4产量（吨）A13113107A219284A3741059销量（吨）3656销地产地B1B2B3B4产量A143730A231410A363930销量306054063020203113108510294712019/12/1615表中填有数字的格对应于基变量(取值即为格中数字），而空格对应的是非基变量（取值为零）.在求初始基本可行解时要注意的一个问题：当我们取定xij的值之后，会出现Ai的产量与Bj的销量都改为零的情况，这时只能划去Ai行或Bj列，但不能同时划去Ai行与Bj列。（或者在同时划去Ai行与Bj列时，在该行或该列的任意空格处填加一个0。）这样可以保证填过数或零的格为m+n-1个，即保证基变量的个数为m+n-1个。2019/12/16162.Vogel法Vogel法的思想是:一地的产品如果不能按照最小运费就近供应，就考虑次小运费，这就有差额，差额越大，说明不能按最小运费调运时，运费增加得越多。因而差额越大处，就应当采用最小运费调运。销地运费单价产地B1B2B3B4产量（吨）A13113107A219284A3741059销量（吨）36562019/12/1617销地产地B1B2B3B4A1520007A2311116A3631222251111332220203113102947110852019/12/1618二、最优解的判别判别解的最优性需要：计算检验数。方法有两种闭回路：是在已给出的调运方案的运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前进，遇到代表基变量的填入数字的格可转90度（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭回路。一个空格存在唯一的闭回路。1.闭回路法因为任意非基向量均可表示为基向量的唯一线性组合，因此对于任意空格都能够找到、并且只能找到唯一的一条闭回路。销地产地B1B2B3B4产量A1437A2314A3639销量3656108531131029471销地产地B1B2B3B4产量A1（+）14（-）37A2（-）31（+）4A3639销量36561085311310294712019/12/1620销地产地B1B2B3B4产量A1（+）14（-）37A2（-）31（+）4A3639销量3656108531131029471从非基变量出发，找到一个闭回路如上表所示。回路有四个顶点，除外，其余都为基变量。调整调运量：，运费增加了3元；，运费减少3元，运费增加2元；，运费减少1元调整后，总运费增加：3-3+2-1=1元。说明如果让为基变量，运费就会增加，其增加值1作为的检验数，111x123x113x11x121x11x11x11x2019/12/1621闭回路法计算检验数：就是对于代表非基变量的空格（其调运量为零），把它的调运量调整为1，由于产销平衡的要求,必须对这个空格的闭回路中的各顶点的调运量加上或减少1。最后计算出由这些变化给整个运输方案的总运输费带来的变化。以这个变化的数值，作为各空格（非基变量）的检验数。判别最优解准则：如果所有代表非基变量的空格的检验数都大于等于零，则已求得最优解；否则继续改进找出最优解。2019/12/16222.位势法（1）对运输表上的每一行赋予一个数值，对每一列赋予一个数值，称为行（列)位势。（2）行（列)位势的数值是由基变量的检验数所决定的，即基变量要满足：非基变量的检验数就可以用公式求出。0jiijijvucjiijijvuciujvijx销地产地B1B2B3B4uiA112430A2311-1-1A3106123-5vj29310311310851029471销地产地B1B2B3B4产量A1437A2314A3639销量36561085311310294712019/12/1624我们先给u1赋个任意数值，不妨设u1=0，则从基变量x11的检验数求得v3=c13-u1=3-0=3。同理可以求得v4=10，u2=-1，等等见上表。检验数的求法，即用公式，如。销地产地B1B2B3B4uiA112430A2311-1-1A3106123-5vj29310311310851029471jiijijvuc1203111111vuc2019/12/1625位势法计算检验数：检验数：ijnmijijijijBijijPvvuucYPcPBCc),...,(1,...,11又因为基变量的检验数为0，于是由（m+n-1)个基变量的检验数可解出，进而计算其他非基变量的检验数。0jiijvuc),...,(1,...,1nmvvuu其中TijP)0...0,1....,0,1,....0(第i个分量第m+j个分量2019/12/1626三、改进运输方案的办法——闭回路调整法当表中的某个检验数小于零时，方案不为最优，需要调整。方法是：选取所有负检验数中最小的非基变量作为入基变量，以求尽快实现最优。（1）确定调整量：例：取，表明增加一个单位的运输量，可使得总运费减少1。在以为出发点的闭回路中，找出所有偶数顶点的调运量：，则调整量（2）调整方法：把所有闭回路上为偶数顶点的运输量都减少这个值，奇数顶点的运输量都增加这个值(见下表)。12424x314x123x1)3,1min(24x24x2019/12/1627销地产地B1B2B3B4uiA112430A2311-1-1A3106123-5vj29310311310851029471销地产地B1B2B3B4uiA14(+1)3(-1)0A231(-1)+1-1A363-5vj29310311310851029471调整运量后的新方案：销地产地B1B2B3B4产量A1527A2314A3639销量36562019/12/1629销地产地B1B2B3B4uiA102520A23211-2A396123-5vj39310311310851029471对上表用位势法进行检验如下表，可知已达最优解。2019/12/1630表上作业法的一般步骤：1、用最小元素法或Vogel法确定初始基可行解；2、判断是否为最优：用闭回路法或位势法计算空格检验数，若所有检验数均非负，则已得到最优解；否则进入第三步；3、从所有负检验数中选择最小者对应空格作为进基变量，从此点出发作闭回路，确定调整量，奇点处增加，偶点处减少。2019/12/1631例：用表上作业法，求解下面的运输问题：销地产地甲乙丙丁产量137645224322343853销量3322解:用最小元素法确定初始基可行解，如下表所示：2019/12/1632销地产地甲乙丙丁产量1337062405（0）2243222(-2）3433853（-4）销量3（3）3（7）2（6）2（4）销地产地甲乙丙丁产量130205（0）21-1-122(-2）353653（-4）销量3（3）3（7）2（6）2（4）++--2019/12/1633销地产地甲乙丙丁产量133706425（0）22432202(-2）3433853（-4）销量3（3）3（7）2（5）2（4）销地产地甲乙丙丁产量130125（0）21-1202(-2）353753（-4）销量3（3）3（7）2（5）2（4）++--2019/12/1634销地产地甲乙丙丁产量13376425（0）224032202(-2）3433853（-3）销量3（3）3（6）2（5）2（4）131125（0）210202(-2）343643（-3）销量3（3）3（6）2（5）2（4）此时所有非基变量的检验数均非负，故已达最优解。2019/12/163