【运筹学】运输问题一条龙服务

运输问题，其实就是把东西从一个地方运到另一个地方去，然后求最小运费这类的问题

比如说我有m个产地，n个销地，已知产地的产量和销地的销量以及产地和销地一一对应的运费，问你怎么安排运输能把产地的东西全部卖掉而且运费最小

这种题的模型比较复杂，因为每个产地都可以运往所有的销地，就像这样

运输问题的任务就是求出上面所有线的运输量……

写成式子可能会看起来更令人舒服一点

第一行（目标函数）表示求运费的最小值

第二行（约束条件1）表示销往j处的产品总数等于各产地销往j处产品数的总和

第三行（约束条件2）表示i出运出的产品总数等于从i销往各销地处产品数之和

然后所有运量大于等于0

单纯形法，上！

……

溜了溜了

很显然传统的单纯形法会算死，解运输问题的方法叫做表上作业法，顾名思义就是在表格上搞事情

上面说到的表格指的是产销平衡表和单位运价表

你的任务就是把产销平衡表上的空都填满

第一步：我们从确定初始基可行解开始

有两种方法，最小元素法和伏格尔法

最小元素法：在运价表里面找最小的运价（比如说是cij），然后给这两个地方进行最大程度的运输，也就是i地有多少就运出多少，或者j地要多少就给多少，取决于哪个更小

然后找表上的次小以此类推，很简单，谁都会

伏格尔法：刚才的最小元素法看起来很有道理，但是你可能因为贪一时的低运价导致你最后被迫选择了高运价而导致运费爆表，而伏格尔法看起来就要理性一点

做法是选出每行每列运价的最小和次小值，并用次小减去最小，得出的结果放在该行/列的最后面（方便比较），就像这样

然后在所有差额里面选出最大的那个，然后在其对应的行/列里面选出最小运费的那个进行最大程度的运输

每次算出一个运量之后都要重新计算差额

这样你的表上就会出现m+n-1个数字，如果少于m+n-1的话就说明你在写上某些数字的时候同时划掉了一行和一列，这样你就需要在这个数字对应的行和列里面找没被划掉的最小运价对应的空格里面写上0，假装它也是个基变量（其实原则上加哪里都可，但是这么加更接近于最优解）。

第二步：看看你写出来的是不是最优解

在你得出初始基可行解之后，表上还有好多空格，这些空格是要你算检验数的，如果所有的检验数都大于0，那么就是最优解了，计算检验数的方法也有两种

闭回路法：从每个空格出发，都存在一条闭回路回到这个空格，关于这条回路的唯一要求就是转角必须为数字格，就像这样：

然后从这个空格开始在转角处依次写上1，-1,1，-1,1，-1……就像这样

然后这个空格处的检验数就是回路上各拐角的运费乘上刚刚写上的1或-1，比如说上图中第一行第一列的检验数就是3-3+2-1=1，以此方法可以算出所有空格的检验数

位势法：有的时候回路不一定那么好找，而位势法可以强行算出各空格的检验数。首先你得在已经算出初始基可行解的产销平衡表的最右边加上一列ui，最下面加上一行vj，就像这样

找到你所有的基变量，让其对应的运价减去对应的u，v之和等于0，令u1=0，就像这样

其原理就是基变量对应的检验数为0

这样就可以算出所有的u和v

然后看空格（非基变量），用空格处对应的运价减去对应的u，v之和，所得结果即为检验数。

第三步：改进你的解

闭回路调整法：如果检验数出现了负数，就选最小的那个负检验数，以它为起点作闭回路，在拐角处标上1，-1,1，-1……（和上面的一样）然后看看在你标过-1的地方，哪个数是最小的（这个数指的是你之前算出来的运量），然后回路上各转角依次加上或减去那个最小的数（你标的是1就加上，标的是-1就减去），得到新的解，然后再次验证是否为最优解，循环上述流程，直到出现最优解。

产销不平衡怎么办？

看看哪个少了，如果是产量>销量就加一个虚拟销地，销量为原来产量和销量的差值，销往虚拟销地的运价全部为0

如果销量＞产量那就加一个虚拟产地，产量为销量和产量的差值，从虚拟产地运出的运价全部为0

然后你就有了产销平衡表，就可以按照上面的步骤来算了。

数学 秃头 运筹学 运输问题