第六运输问题

第六运输问题第一页，共四十二页，编辑于2023年，星期一一、运输问题的提出及其数学模型

一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。

第二页，共四十二页，编辑于2023年，星期一例题1：某公司从两个产地A1，A2将产品运往三个销地B1，B2，B3，各产地的产量、各销地的销量和各产地运往各销地的单位产品运费如表3-1所示。问如何调运，使得总运输费最小？

第三页，共四十二页，编辑于2023年，星期一第四页，共四十二页，编辑于2023年，星期一解：从表中可以看到，A1，A2两个产地的总产量为500件；B1，B2，B3三个销地的总销量为500件，因此这是一个产销平衡的运输问题。把A1，A2的产量全部分配给B1，B2，B3，正好满足这三个销地的需要。

第五页，共四十二页，编辑于2023年，星期一第六页，共四十二页，编辑于2023年，星期一第七页，共四十二页，编辑于2023年，星期一此数学模型当然可用线性规划的常用方法求解（比如单纯形法），但求解的程序相对复杂，即使利用计算机程序来求解，其输入和解决问题的规模都受到限制。因此，管理运筹学中有专门的求解运输问题的程序，一般只要输入产点数，各产地的产量，销点数，各销地的销量，以及各产地到各销地的运输单价，立即可得到运输问题的最优解。把本例的相关数据输入运输问题的程序，得到最优解为：

第八页，共四十二页，编辑于2023年，星期一第九页，共四十二页，编辑于2023年，星期一先给出一般运输问题的线性规划模型。

我们用A1，A2，…，表示某种物资的m个产地；B1，B2，…，Bn表示某种物资的n个销地；表示产地的产量；表示销地的销量；表示把物资从产地i运到销地j的单位运价；并设为从产地运到销地的运输量，则产销平衡的运输问题的线性规划数学模型如下所示

第十页，共四十二页，编辑于2023年，星期一第十一页，共四十二页，编辑于2023年，星期一

有时上述问题的一般模型会发生如下一些变化：

求目标函数值的最大值而不是最小值。有些运输问题中，其目标是找出利润最大或营业额最大的调运方案，这时要求目标函数的最大值。

当某些运输线路的运输能力有一定限制时，这时要在线性规划模型的约束条件上加上运输能力限制的约束条件。当生产总量不等于销量总量，即产销不平衡时，这时需要通过一个假想仓库或假想生产地来化成产销平衡的问题，具体做法在后面阐述。

第十二页，共四十二页，编辑于2023年，星期一二、运输问题的求解

---表上作业法

直接采用单纯形法求解运输问题明显是不利的。好在运输问题具有特殊的结构，因此可以利用单纯形法的原理提出一种直接在运输表上计算以求解产销平衡运输问题的简便方法--表上作业法。它大大简化了计算过程的求解方法

第十三页，共四十二页，编辑于2023年，星期一

计算过程如下：

Step1给出初始调运方案（初始基可行解）。

对于有m个产地n个销地的产销平衡的问题，从其线性规划的模型上可知其有m+n个约束方程，但由于产销平衡，前m个约束方程之和等于后n个约束方程之和，所以其数学模型最多只有m+n-1个独立的约束方程。实际上其正好是m+n-1个独立的约束方程，也就是说运输问题的约束方程组系数矩阵的秩等于m+n-1，因此其基可行解中基变量的个数为m+n-1。表上作业法中找初始基可行解，就是在m×n产销平衡表上找出m+n-1个数字格，其相应的调运量就是基变量，格子中所填写的值即为基变量的值。

第十四页，共四十二页，编辑于2023年，星期一Step2判断初始调运方案是否最优

求表中各空格（对应于非基变量）的检验数以判定当前解是否最优，若已是最优解则停止计算；否则转到下一步。

第十五页，共四十二页，编辑于2023年，星期一Step3.调整

确定入基变量与出基变量。从一个基可行解转换成另一个"更好"的基可行解，即进行方案调整。

第十六页，共四十二页，编辑于2023年，星期一Step4重复2、3直至得到最优解。

第十七页，共四十二页，编辑于2023年，星期一三、例题第十八页，共四十二页，编辑于2023年，星期一某食品公司有三个生产面包的分厂A1，A2，A3，有四个销售分公司B1，B2，B3，B4，其各分厂每日的产量、各分销售公司每日的销量以及各分厂到各分销售公司的单位运价如表3-2所示。问该公司应如何调运产品在满足各销点的需求量的前提下，总运费最少？

第十九页，共四十二页，编辑于2023年，星期一第二十页，共四十二页，编辑于2023年，星期一Step1求初始调运方案---最小元素法

求初始调运方案，也就是求初始基可行解有3种方法(西北角法、最小元素法、伏格尔法)，

第二十一页，共四十二页，编辑于2023年，星期一在此只介绍最小元素法。该方法的基本思想是采用

“优先安排单位运价最小的产地与销地之间的运输业务”，

用这个规则来确定初始基可行解。

第二十二页，共四十二页，编辑于2023年，星期一我们直接在运输表中的格子里填数表示基变量。为了把初始基可行解与运价分开，把运价放在每一栏的右上角，每一栏的中间填上初始基可行解（调运量）见表3-3。

第二十三页，共四十二页，编辑于2023年，星期一在表上找到单位运价最小的开始分配运输量，并使取尽可能大的值，即取min（4，3）3，把所在空格里填上3，然后把A2的产量改写为4-3=1，把B1的销量改写为3-3=0，并把B1列划去。在剩下的3×3矩阵里找到运价最小的变量，取min（1，5）=1，A2的产量改为1-1=0，B3的销量改为5-1=4，并把A2行划去。在剩下的矩阵里找到运价最小的变量，取min（7，4）=4，A1的产量改为3，B3的销量改为0，并划去B3列。

第二十四页，共四十二页，编辑于2023年，星期一第二十五页，共四十二页，编辑于2023年，星期一第二十六页，共四十二页，编辑于2023年，星期一Step2最优解的判别--位势法

同单纯形法一样，表上作业法也是用检验数来检验方案的最优性。检验已得的运输方案是否是最优的方法有两种：一种是闭回路法，

一种是位势法。

第二十七页，共四十二页，编辑于2023年，星期一第二十八页，共四十二页，编辑于2023年，星期一第二十九页，共四十二页，编辑于2023年，星期一第三十页，共四十二页，编辑于2023年，星期一第三十一页，共四十二页，编辑于2023年，星期一Step3方案的调整

第三十二页，共四十二页，编辑于2023年，星期一第三十三页，共四十二页，编辑于2023年，星期一第三十四页，共四十二页，编辑于2023年，星期一第三十五页，共四十二页，编辑于2023年，星期一第三十六页，共四十二页，编辑于2023年，星期一表中带圈的数字是非基变量的检验数，可知所有检验数都大于等于零（基变量的检验数都等于零），此解是最优解，这时最小总运输费用为85元，具体的运输方案如下：A1分厂运5吨到销售公司B3，运2吨给销售公司B4；A3分厂运3吨给销售公司B1，运1吨给销售公司B4；A3分厂运6吨给销售公司B2，运3吨给销售公司B4。

第