[工学]第六章运输问题.ppt

运输问题在工商管理中有着广泛的应用，它是一类特殊的线性规划问题，对于运输问题，当然可以用前面所介绍的单纯形法进行求解，但由于这类线性规划问题在结构上有其特殊性，我们可以找到比标准单纯形法更简单有效的专门方法，从而节约计算时间和费用，因此，这里把运输问题单列一章进行讨论。本章介绍运输问题的模型、表上作业法以及运输问题的一些实际应用。,运输问题,第六章,一、运输问题的提出及其数学模型 一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。,例题1：某公司从两个产地A1，A2将产品运往三个销地B1，B2，B3，各产地的产量、各销地的销量和各产地运往各销地的单位产品运费如表3-1所示。问如何调运，使得总运输费最小？,解：从表中可以看到，A1，A2两个产地的总产量为500件；B1，B2，B3三个销地的总销量为500件，因此这是一个产销平衡的运输问题。把A1，A2的产量全部分配给B1，B2，B3，正好满足这三个销地的需要。,此数学模型当然可用线性规划的常用方法求解（比如单纯形法），但求解的程序相对复杂，即使利用计算机程序来求解，其输入和解决问题的规模都受到限制。因此，管理运筹学中有专门的求解运输问题的程序，一般只要输入产点数，各产地的产量，销点数，各销地的销量，以及各产地到各销地的运输单价，立即可得到运输问题的最优解。把本例的相关数据输入运输问题的程序，得到最优解为：,先给出一般运输问题的线性规划模型。 我们用A1，A2，表示某种物资的m 个产地；B1，B2，Bn表示某种物资的n 个销地； 表示产地的产量；表示销地的销量； 表示把物资从产地i运到销地j的单位运价；并设 为从产地运到销地的运输量，则产销平衡的运输问题的线性规划数学模型如下所示,有时上述问题的一般模型会发生如下一些变化：,求目标函数值的最大值而不是最小值。有些运输问题中，其目标是找出利润最大或营业额最大的调运方案，这时要求目标函数的最大值。 当某些运输线路的运输能力有一定限制时，这时要在线性规划模型的约束条件上加上运输能力限制的约束条件。 当生产总量不等于销量总量，即产销不平衡时，这时需要通过一个假想仓库或假想生产地来化成产销平衡的问题，具体做法在后面阐述。,二、运输问题的求解 -表上作业法 直接采用单纯形法求解运输问题明显是不利的。好在运输问题具有特殊的结构，因此可以利用单纯形法的原理提出一种直接在运输表上计算以求解产销平衡运输问题的简便方法-表上作业法。它大大简化了计算过程的求解方法,计算过程如下： Step1 给出初始调运方案 （初始基可行解）。 对于有m个产地n个销地的产销平衡的问题，从其线性规划的模型上可知其有m+n 个约束方程，但由于产销平衡，前m 个约束方程之和等于后n 个约束方程之和，所以其数学模型最多只有m+n-1个独立的约束方程。实际上其正好是m+n-1个独立的约束方程，也就是说运输问题的约束方程组系数矩阵的秩等于m+n-1，因此其基可行解中基变量的个数为m+n-1。表上作业法中找初始基可行解，就是在mn产销平衡表上找出m+n-1个数字格，其相应的调运量就是基变量，格子中所填写的值即为基变量的值。,Step2 判断初始调运方案是否最优 求表中各空格（对应于非基变量）的检验数以判定当前解是否最优，若已是最优解则停止计算；否则转到下一步。,Step3.调整 确定入基变量与出基变量。从一个基可行解转换成另一个“更好“的基可行解，即进行方案调整。,Step4 重复2、3直至得到最优解。,三、例题,某食品公司有三个生产面包的分厂A1，A2，A3，有四个销售分公司B1，B2，B3，B4，其各分厂每日的产量、各分销售公司每日的销量以及各分厂到各分销售公司的单位运价如表3-2所示。问该公司应如何调运产品在满足各销点的需求量的前提下，总运费最少？,Step1求初始调运方案-最小元素法 求初始调运方案，也就是求初始基可行解有3种方法(西北角法、最小元素法、伏格尔法)，,在此只介绍最小元素法。该方法的基本思想是采用 “优先安排单位运价最小的产地与销地之间的运输业务”， 用这个规则来确定初始基可行解。,我们直接在运输表中的格子里填数表示基变量。为了把初始基可行解与运价分开，把运价放在每一栏的右上角，每一栏的中间填上初始基可行解（调运量）见表3-3。,在表上找到单位运价最小的开始分配运输量，并使取尽可能大的值，即取min（4，3）3，把所在空格里填上3，然后把A2的产量改写为4-3=1，把B1的销量改写为3-3=0，并把B1列划去。在剩下的33矩阵里找到运价最小的变量，取min（1，5）=1，A2的产量改为1-1=0，B3的销量改为5-1=4，并把A2行划去。在剩下的矩阵里找到运价最小的变量，取min（7，4）=4，A1的产量改为3，B3的销量改为0，并划去B3列。,Step2最优解的判别-位势法 同单纯形法一样，表上作业法也是用检验数来检验方案的最优性。检验已得的运输方案是否是最优的方法有两种：一种是闭回路法， 一种是位势法。,Step3方案的调整,表中带圈的数字是非基变量的检验数，可知所有检验数都大于等于零（基变量的检验数都等于零），此解是最优解，这时最小总运输费用为85元