运筹学基础及应用第3章-运输问题(胡运权).ppt

运筹学基础及应用第3章-运输问题(胡运权).ppt

《运筹学基础及应用第3章-运输问题(胡运权).ppt》由会员分享，可在线阅读，更多相关《运筹学基础及应用第3章-运输问题(胡运权).ppt（80页珍藏版）》请在冰点文库上搜索。

运筹学基础及应用,OperationsResearch,第三章,目,录,CONTENTS,例3.1某公司从两个产地A1、A2将物品运往三个销地B1,B2,B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：

应如何调运可使总运输费用最小？

1.运输规划问题的典例和数学模型,解：

产销平衡问题：

总产量=总销量500设xij为从产地Ai运往销地Bj的运输量，得到下列运输量表：

MinC=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij0（i=1、2；j=1、2、3）,1.运输规划问题的典例和数学模型,运输问题的一般形式：

产销平衡,A1、A2、Am表示某物资的m个产地；B1、B2、Bn表示某物质的n个销地；ai表示产地Ai的产量；bj表示销地Bj的销量；cij表示把物资从产地Ai运往销地Bj的单位运价。

设xij为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型：

1.运输规划问题的典例和数学模型,产地Ai（i=1,.,n）分配到销地Bj（j=1,.,n）物资的和=产地Ai的产量ai,销地Bj（j=1,.,n）接收到产地Ai（i=1,.,n）分配的物资和=销地Bj的产量bj,已知资料如下：

产销平衡,销量,运价,1.运输规划问题的典例和数学模型,当产销平衡时，其模型如下：

1.运输规划问题的典例和数学模型,产地Ai（i=1,.,n）分配到销地Bj（j=1,.,n）物资的和=产地Ai的产量ai,销地Bj（j=1,.,n）接收到产地Ai（i=1,.,n）分配的物资和=销地Bj的产量bj,产量=销量,当产大于销时，其模型如下：

1.运输规划问题的典例和数学模型,产地Ai（i=1,.,n）分配到销地Bj（j=1,.,n）物资的和产地Ai的产量ai,销地Bj（j=1,.,n）接收到产地Ai（i=1,.,n）分配的物资和=销地Bj的产量bj,产量销量,当产小于销时，其模型如下：

1.运输规划问题的典例和数学模型,产地Ai（i=1,.,n）分配到销地Bj（j=1,.,n）物资的和=产地Ai的产量ai,销地Bj（j=1,.,n）接收到产地Ai（i=1,.,n）分配的物资和销地Bj的产量bj,产量销量,特征：

1、平衡运输问题必有可行解，也必有最优解；2、运输问题的基本可行解中应包括m+n1个基变量。

1.运输规划问题的典例和数学模型,1.运输规划问题的典例和数学模型,运输问题的求解思路,1.运输规划问题的典例和数学模型,2.表上作业法,计算步骤：

（1）找出初始调运方案。

即在（mn）产销平衡表上给出m+n-1个数字格。

（最小元素法、西北角法或伏格尔法）,

（2）求检验数。

（闭回路法或位势法）判别是否达到最优解。

如已是最优解，则停止计算，否则转到下一步。

（3）对方案进行改善，找出新的调运方案。

（表上闭回路法调整）,确定m+n-1个基变量,（4）重复

（2）、（3），直到求得最优调运方案。

空格,表上作业法是一种求解运输问题的特殊方法，其实质是单纯形法。

2.表上作业法,例3.2某运输资料如下表所示：

问：

应如何调运可使总运输费用最小？

1、求初始方案：

最小元素法、西北角法、伏格尔法,2.表上作业法,基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。

3,11,3,10,1,9,2,7,4,10,5,8,总的运输费（31）+（64）+（43）+（12）+（310）+（35）=86元,方法1：

最小元素法,3,4,1,6,3,3,2.表上作业法,练习1,12,13,13,19,1,2,2.表上作业法,此法是纯粹的人为的规定，没有理论依据和实际背景，但它易操作，特别适合在计算机上编程计算，因而受欢迎。

方法如下：

2.表上作业法,方法二：

西北角法（或左上角法）,在满足约束条件下尽可能的给最左上角的变量最大值.,8,8,6,4,8,14,所以，初始基可行解为：

（8,8,6,4,8,14）目标函数值Z372,例3.3某运输资料如下表所示：

2.表上作业法,练习2,8,13,13,14,6,6,2.表上作业法,最小元素法的缺点是：

为了节省一处的费用，有时造成在其他处要多花几倍的运费。

伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。

差额越大，说明不能按最小运费调运时，运费增加越多。

因而对差额最大处，就应当采用最小运费调运。

例如下面两种运输方案。

最小元素法：

总运费是z=108+52+151=105,另一种方法：

总运费z=105+152+51=85,2.表上作业法,1）从运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。

3,11,3,10,1,9,2,7,4,10,5,8,10-3=7,2-1=1,5-4=1,3-1=2,9-4=5,3-2=1,8-5=3,2.表上作业法,方法三：

Vogel法,2）再从差值最大的行或列中找出最小运价确定供需关系和供需数量。

当产地或销地中有一方数量供应完毕或得到满足时，划去运价表中对应的行或列。

重复1）和2），直到找出初始解为至。

3,11,3,10,1,9,2,7,4,10,5,8,5,2.表上作业法,7,1,3,5,2,7,5,3,2.表上作业法,1,1,3,5,1,5,3,6,3,1,2,该方案的总运费:

（13）（46）（35）（210）（18）（35）85元,2.表上作业法,14,例3.4某运输资料如下表所示：

2.表上作业法,14,8,例3.4某运输资料如下表所示：

2.表上作业法,14,8,8,例3.4某运输资料如下表所示：

2.表上作业法,14,8,8,例3.4某运输资料如下表所示：

12,2.表上作业法,14,8,8,例3.4某运输资料如下表所示：

12,2,4,2.表上作业法,练习3,1,2,13,12,13,19,2.表上作业法,2、最优解的判别（检验数的求法）,求检验数的方法有两种：

闭回路法对偶变量法（位势法）,

（1）闭合回路法：

ij0（因为目标函数要求最小化）表格中有调运量的地方为基变量，空格处为非基变量。

ij0表示运费增加。

2.表上作业法,闭回路：

从空格出发顺时针（或逆时针）画水平（或垂直）直线，遇到填有运量的方格可转90，然后继续前进，直到到达出发的空格所形成的闭合回路。

调运方案的任意空格存在唯一闭回路。

注：

1.每一空格有且仅有一条闭回路；2.如果某数字格有闭回路，则此解不是可行解。

若令则,运费的增量,分析：

2.表上作业法,以最小元素法的初始解为例。

假设产地A1供应1个单位的物品给销地B1。

则解的变化和目标函数的变化如何。

2.表上作业法,要保证产销平衡，则,称为闭回路,1,2.表上作业法,1,2,2.表上作业法,1,2,1,2.表上作业法,10,2,1,1,2.表上作业法,1,2,1,12,10,2.表上作业法,1,2,1,-1,12,10,检验数中有负数，说明原方案不是最优解。

2.表上作业法,练习4,5,5,7,9,-3,-11,2.表上作业法,ui,vj,m个,n个,

（2）对偶变量法（位势法）,设其对偶变量为：

2.表上作业法,uivj无约束（i=1,2,m;j=1,2,n）,标准型运输问题的对偶问题模型为：

则运输问题变量xij的检验数为：

2.表上作业法,用位势法对初始方案进行最优性检验的方法：

3）由ij=Cij-（ui+vj），求出非基变量的检验数。

2.表上作业法,1）在给定初始解的表上增加一行和一列，在列中填入ui，在行中填入vj。

2）令u10，再按cij-（ui+vj）=0（基变量的cij求出其余的ui与vj。

3,11,3,10,1,9,2,7,4,10,5,8,u1,u2,u3,v3,v4,v1,v2,注意：

基变量的检验数ij=Cij-（ui+vj）=0,4,3,6,3,1,3,2.表上作业法,3,10,1,2,4,0,-1,-5,3,10,2,9,令u1=0,u1+v3=3,u1+v4=10,u2+v3=2,u2+v1=1,u3+v2=4,u3+v4=5,4,3,6,3,1,3,2.表上作业法,5,2,4,3,6,3,1,3,

（1）,

（2）,

（1）,（-1）,（10）,（12）,当存在非基变量的检验数ij0，说明现行方案为最优方案，否则目标成本还可以进一步减小。

注意：

非基变量的检验数ij=cij-（ui+vj）,11=c11-（u1+v1）=3-（0+2）=1,31=c31-（u3+v1）=7-（2-5）=10,24=c24-（u2+v4）=8-（10-1）=-1,22=c22-（u2+v2）=9-（9-1）=1,12=c12-（u1+v2）=11-（0+9）=2,33=c33-（u3+v3）=10-（3-5）=12,3,11,3,10,1,9,2,7,4,10,5,8,3、解的改进闭合回路调整法（原理同单纯形法一样）,当在表中空格处出现负检验数时，表明未得最优解。

若有两个或两个以上的负检验数时，一般选用其中最小的负检验数，以它对应的空格为调入格，即以它对应的非基变量为换入变量。

做一闭合回路。

（1）确定换入基的变量：

当存在非基变量的检验数kl0且kl=minij时，以Xkl为换入变量，找出它在运输表中的闭合回路。

接上例：

解的改进的具体步骤：

2.表上作业法,2,4,3,6,3,1,3,3,11,3,10,1,9,2,7,4,10,5,8,

（1）,

（2）,

（1）,（-1）,（10）,（12）,

（2）顶点编号：

以空格（Ak,Bl）（或进基变量xik）为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的顶点依次编号。

1,3,2,4,2.表上作业法,2,4,3,6,3,1,3,3,11,3,10,1,9,2,7,4,10,5,8,

（1）,

（2）,

（1）,（-1）,（10）,（12）,

（2）顶点编号：

以空格（Ak,Bl）（或进基变量xik）为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的顶点依次编号。

1,3,2,4,换出变量X23,（3）确定换出基的变量：

在该闭回路上，从所有偶数号格点的调运量中选出最小值的顶点（格子），以该格子中的变量为换出变量。

（4）确定新的运输方案：

以换出变量的运输量为调整量，将该闭回路上所有奇数号格的调运量加上调整量，所有偶数号格的调运量减去，其余的不变，这样就得到一个新的调运方案。

该运输方案的总运费比原运输方案减少，改变量等于换出变量的检验数。

（5）然后，再对得到的新解进行最优性检验，如不是最优解，就重复以上步骤继续进行调整，一直到得出最优解为止。

2.表上作业法,2,3,6,3,1,

（1）,

（1）,

（1）,

（1）,3,11,3,10,1,9,2,7,4,10,5,8,4,3,2.表上作业法,3,10,3,9,vj,-5,A3,-2,A2,0,A1,ui,B4,B3,B2,B1,5,3,6,3,1,2,3,11,3,10,1,9,2,7,4,10,5,8,重新求所有非基变量的检验数：

2.表上作业法,3,10,3,9,vj,-5,A3,-2,A2,0,A1,ui,B4,B3,B2,B1,5,3,6,3,1,2,

（2）,

（2）,

（1）,（12）,（9）,（0）,当所有非基变量的检验数均非负时，则当前调运方案即为最优方案，如表此时最小总运费：

Z=（13）（46）（35）（210）（18）（35）85元,3,11,3,10,1,9,2,7,4,10,5,8,2.表上作业法,表上作业法的计算步骤：

2.表上作业法,表上作业法计算中的问题：

（1）若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代时，取它们中任一变量为换入变量均可使目标函数值得到改善，但通常取ij0中最小者对应的变量为换入变量。

（2）无穷多最优解产销平衡的运输问题必定存最优解。

如果非基变量的ij0，则该问题有无穷多最优解。

如上例：

11的检验数是0，经过调整，可得到另一个最优解。

2.表上作业法,退化解：

表格中一般要有（m+n-1）个数字格。

但有时在分配运量时则需要同时划去一行和一列，这时需要补一个0，以保证有（m+n-1）个数字格作为基变量。

一般可在划去的行和列的任意空格处加一个0即可。

利用进基变量的闭回路对解进行调整时，标有负号的最小运量（超过2个最小值）作为调整量，选择任意一个最小运量对应的基变量作为出基变量，并打上“”以示作为非基变量。

2.表上作业法,产销不平衡的运输问题当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。

当产大于销时，即：

数学模型为：

3.运输问题的进一步讨论,由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，假设该仓库为一个虚拟销地Bn+1，bn+1作为一个虚设销地Bn+1的销量（即库存量）。

各产地Ai到Bn+1的运价为零，即Ci,n+1=0,（i=1，m）。

则平衡问题的数学模型为：

具体求解时,只在运价表右端增加一列Bn+1，运价为零,销量为bn+1即可,3.运输问题的进一步讨论,当销大于产时，即：

数学模型为：

由于总销量大于总产量,故一定有些需求地不完全满足,这时虚设一个产地Am+1，产量为：

3.运输问题的进一步讨论,销大于产化为平衡问题的数学模型为：

具体计算时，在运价表的下方增加一行Am+1，运价为零。

产量为am+1即可。

3.运输问题的进一步讨论,例3.4求下列表中极小化运输问题的最优解。

因为有：

3.运输问题的进一步讨论,所以是一个产大于销的运输问题。

表中A2不可达B1，用一个很大的正数M表示运价C21。

虚设一个销量为b5=180-160=20，Ci5=0，i=1,2,3,4，表的右边增添一列，得到新的运价表。

3.运输问题的进一步讨论,下表为计算结果。

可看出：

产地A4还有20个单位没有运出。

用前面的方法求运输方案：

3.运输问题的进一步讨论,例3.5某市有三个造纸厂A1，A2，A3，其纸的产量分别为8，5和9个单位，有4个集中用户B1，B2，B3，B4，其需用量分别为4，3，5和6个单位。

由各造纸厂到各用户的单位运价如表314所示，请确定总运费最少的调运方案。

3.运输问题的进一步讨论,解：

由于总产量22大于总销量18，故本问题是个产销不平衡运输问题。

增加一假想销地B5，用表上作业法求解。

3.运输问题的进一步讨论,3.运输问题的进一步讨论,例3.5由n个地区需要某种物资，需要量分别不少于bj（j=1,n）。

这些物资均由某公司分设在m个地区的工厂供应，各工厂的产量分别不大于ai（i=1,m）,已知从第i个地区至第j个需求地区单位物资的运价为cij，又，试写出其对偶问题，并解释对偶变量的经济意义。

由于在变量相等的情况下，表上作业法的计算远比单纯形法简单得多。

所以在解决实际问题时，人们常常尽可能把某些线性规划的问题化为运输问题的数学模型。

3.应用问题举例,解：

由题给出的条件，数学模型可写为:

对偶问题可写为：

3.应用问题举例,对偶变量ui的经济意义为在i产地单位物资的价格，vj的经济意义为在第j销地单位物资的价格。

对偶问题的经济意义为：

如该公司欲自己将该种物资运至各地销售，其差价不能超过两地之间的运价（否则买主将在i地购买自己运至j地），在此条件下，希望获利为最大。

3.应用问题举例,已知资料如下表所示，问如何供电能使总的输电费用为最小？

电力供需表,单位输电费用,练习：

3.应用问题举例,初始方案,单位输电费用,电力供需表,3.应用问题举例,ij,-（ui+vj）,=,cij,（ui+vj）,3.应用问题举例,成本表,（ui+vj）,调运方案,3.应用问题举例,ij=cij-（ui+vj）,成本表,调运方案,3.应用问题举例,（ui+vj）,C=5200,ij=cij-（ui+vj）,3.应用问题举例,试用表上作业法求最优解,3.应用问题举例,最小总费用为945。

3.应用问题举例,THANKYOU!

THANKYOU!