第六运输问题.pptVIP

第30页，共42页，星期日，2025年，2月5日第1页，共42页，星期日，2025年，2月5日一、运输问题的提出及其数学模型

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

第2页，共42页，星期日，2025年，2月5日例题1：某公司从两个产地A1，A2将产品运往三个销地B1，B2，B3，各产地的产量、各销地的销量和各产地运往各销地的单位产品运费如表3-1所示。问如何调运，使得总运输费最小？

第3页，共42页，星期日，2025年，2月5日第4页，共42页，星期日，2025年，2月5日解：从表中可以看到，A1，A2两个产地的总产量为500件；B1，B2，B3三个销地的总销量为500件，因此这是一个产销平衡的运输问题。把A1，A2的产量全部分配给B1，B2，B3，正好满足这三个销地的需要。

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

第8页，共42页，星期日，2025年，2月5日第9页，共42页，星期日，2025年，2月5日先给出一般运输问题的线性规划模型。

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

第10页，共42页，星期日，2025年，2月5日第11页，共42页，星期日，2025年，2月5日

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

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

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

第12页，共42页，星期日，2025年，2月5日二、运输问题的求解

---表上作业法

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

计算过程如下：

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

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

第14页，共42页，星期日，2025年，2月5日Step2判断初始调运方案是否最优

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

第15页，共42页，星期日，2025年，2月5日Step3.调整

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

第16页，共42页，星期日，2025年，2月5日Step4重复2、3直至得到最优解。第17页，共42页，星期日，2025年，2月5日三、例题第18页，共42页，星期日，2025年，2月5日某食品公司有三个生产面包的分厂A1，A2，A3，有四个销售分公司B1，B2，B3，B4，其各分厂每日的产量、各分销售公司每日的销量以及各分厂到各分销售公司的单位运价如表3-2所示。问该公司应如何调运产品在满足各销点的需求量的前提下，总运费最少