运输问题课件

运输问题课件例题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。表上作业法中找初始基可行解,就就是在m×n产销平衡表上找出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列划去。在剩下得3×3矩阵里找到运价最小得变量,取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元,具体得运输方案如下:A1分厂运